Lower bounds for sets avoiding kth-power differences
Follow the latest progress by email.
Let D_k(N) be the greatest size of a subset of {1,…,N} whose nonzero differences avoid k-th powers. What lower growth exponents can explicit constructions achieve for k≥2?
Why it matters and what counts as progress
Why it matters: Better exponents enlarge rigorously constructed sets avoiding these arithmetic differences.
What counts as progress: A construction giving D_k(N)≥N^ρ eventually for a larger stated ρ, with certified block conditions and comparisons made separately for each k.
How the problem developed
- 1984 · Lower bound [1]
Imre Z. Ruzsa Developed a construction for sets avoiding square differences, a foundation for later power-difference-free bounds.
- 2015 · Improved lower bound [2]
Mark Lewko Improved lower bounds related to the Furstenberg–Sárközy theorem for square and higher-power differences.
- 2026 · Formalized generalization [4]
J. D. Jones and collaborators Formalized a general kth-power-difference construction, including explicit k=4 and k=6 instances; the record does not claim optimality or general upper bounds.
- 2 Aug 2026 · Square difference result [3]
Dmitry Krachun Posted a stronger square-difference-free construction with exponent about 0.752796; this result concerns squares only.
AI contributions 2
AI agents extend a difference-free construction to all powers
For every k≥2, a nonempty pool of ranked blocks on pairwise coprime square-free moduli, with ranks strictly decreasing along nonzero k-th-power-residue difference arcs, gives α(k,P)≤liminf log D_k(N)/log N and eventually D_k(N)≥N^ρ for every ρ<α(k,P). Two separate nine-block instances give α(4,P₄)=0.912145042700…>0.9121 and α(6,P₆)=0.950825559086…>0.9508; each exceeds the specified six-residue Ruzsa-transfer comparator.
AI-generated construction raises a square-difference-free lower bound
An eleven-block construction yields α∞≤liminf log D(N)/log N for the largest square-difference-free subset D(N) of {1,…,N}. Every exponent ρ<α∞ holds eventually, and the formal proof certifies α∞>0.7537.
Sources
- Ruzsa residue transfer
- Mark Lewko, An improved lower bound related to the Furstenberg–Sárközy theorem
- Krachun square-difference construction
- Directed power-difference construction
- AI and human roles
- Lean verification record
- Jones, square-difference-free result and proof stages
- Jones, formalization and verification record
- Jones, AI contribution disclosure
- Naslund, later stronger exponent
Website timeline
Publication dates and editorial changes.
AI agents extend a difference-free construction to all powers
AI-generated construction raises a square-difference-free lower bound