FunSearch and Structured SAT Search for Weak Schur Partitions
The weak Schur problem asks how large an interval of consecutive integers can be partitioned into a fixed number of classes with no class containing a monochromatic solution to $a+b=c$ with $a\neq b$. We investigate whether FunSearch, an evolutionary program-search method guided by a large language model, can discover effective construction strategies for this classical combinatorial problem. In our adaptation, FunSearch evolves a priority function used by a fixed greedy solver, while a separate validity check enforces the weakly sum-free condition. This approach matches the known exact values for two, three, and four classes and reaches $WS(5)\geq195$. We then explore a complementary SAT-based approach. Guided by structural information from a 207-element construction communicated by Fred Rowley (Rowley, 2026), our SAT search produces and verifies a distinct valid five-class partition of $\{1,\ldots,207\}$. Thus the strongest construction obtained in this project reaches $WS(5)\geq207$, eleven integers beyond the best published lower bound of 196. The contrast between the two approaches also exposes a limitation of our FunSearch formulation: its greedy solver makes local, irreversible decisions, whereas SAT can enforce global structure across the whole partition.
Authors
- Eric Ramos
- Jingxuan Feng (ORCID: https://orcid.org/0009-0003-6855-3840)
- Caleb Hartman (ORCID: https://orcid.org/0009-0009-9378-3967)
- Pablo Christofferson
- Omar M. Elshinawy
- Suleman Khan
- Rebecca Vicenzi
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-17
- DOI
- https://doi.org/10.48550/arxiv.2611.22032
- Primary Topic
- Constraint Satisfaction and Optimization
- Type
- preprint