Skip to content
DraconiticResearch
Search Sources API
197,693 studies31 sourcesUpdated 6 min ago
PreprintCC BY 4.0arXiv

Large solution-free sets via combinatorial degenerations

  • Paul Hametner
  • Jozsef Solymosi
Open at sourcePDFDOICite

Abstract

Consider the linear form L(x,y,z,w) = 3x+y−2z−2w. For a positive integer N, denote by rL(N) the largest size of a subset of {1,2,…,N} that avoids nontrivial solutions to L = 0. We show that rL(N) = Ω(N0.5608687), improving the lower bound for Problem 16 in Green's list of open problems. Our proof uses the method of combinatorial degenerations to turn a finite certificate into large solution-free sets. In fact, we can improve Ruzsa's lower bound of N1/2−o(1) for many four-variable equations. Consider L(x,y,z,w) = ax+by−cz−dw with a,b,c,d∈ ℤ>0, a+b=c+d, {a,b} ≠ {c,d} and abcd not a square. We show that there is εL > 0 such that rL(N) = ΩL(N1/2 + εL). Furthermore, we show that for primitive translation-invariant linear forms L in s variables, the lower bound Ωs(N1/(s−1)) coming from a greedy construction is never optimal.

Related

  1. Congruence Jumping in Polynomial Divisibility Systems: Arithmetic Structure and Solution Sets
    Max A. Alekseyev, Dmitry I. Khomovsky
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  2. The replica symmetric solution for hypergraph independent sets in the critical regime
    Matthew Jenssen, Will Perkins, Aditya Potukuchi +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. On the Solution Sets of the Cone-Volume Map
    Tom Baumbach, Zhang Chen, Martin Henk
    arXivPreprintCC BY 4.0Full textGeometry & topologyarXiv
  4. Unmanned Aerial Vehicle Delivery Route Planning in Cold Weather Using Neural Combinatorial Optimization and Adaptive Large Neighborhood Search
    Jiankai Fang, Jianyou Xu, Hongkun Wang +3
    MathematicsPeer-reviewedCC BY 4.0General mathematicsCrossref
  5. A Logic for Minor-Free Graph Classes: Model Checking, Dependence, and Combinatorial Reconfiguration
    Nikolas Mählmann, Patrice {Ossona de Mendez}, Nicole Schirrmacher +4
    arXivPreprintCC BY 4.0Full textLogic & foundationsarXiv

Cite

BibTeXRIS
BibTeX
@misc{hametner2026large,
  title = {{Large solution-free sets via combinatorial degenerations}},
  author = {Paul Hametner and Jozsef Solymosi},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.13972},
  eprint = {2609.13972},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.13972},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Large solution-free sets via combinatorial degenerations
AU  - Paul Hametner
AU  - Jozsef Solymosi
PY  - 2026
DA  - 2026/09/12
PB  - arXiv
DO  - 10.48550/arxiv.2609.13972
UR  - https://arxiv.org/abs/2609.13972
AB  - Consider the linear form L(x,y,z,w) = 3x+y−2z−2w. For a positive integer N, denote by r_L(N) the largest size of a subset of {1,2,…,N} that avoids nontrivial solutions to L = 0. We show that r_L(N) = Ω(N^0.5608687), improving the lower bound for Problem 16 in Green's list of open problems. Our proof uses the method of combinatorial degenerations to turn a finite certificate into large solution-free sets. In fact, we can improve Ruzsa's lower bound of N^1/2−o(1) for many four-variable equations. Consider L(x,y,z,w) = ax+by−cz−dw with a,b,c,d∈ ℤ_>0, a+b=c+d, {a,b} ≠ {c,d} and abcd not a square. We show that there is ε_L > 0 such that r_L(N) = Ω_L(N^1/2 + ε_L). Furthermore, we show that for primitive translation-invariant linear forms L in s variables, the lower bound Ω_s(N^1/(s−1)) coming from a greedy construction is never optimal.
ER  -