Power savings for intersective polynomial differences and prime arguments

Sets of whole numbers with no square difference are smaller than N by a fixed power of N.

3 papers September 24, 2026 Explained by AI

Pick numbers from 1 to N so that no two differ by a perfect square. Such a set must be a vanishing share of the numbers, but earlier bounds shrank that share only slowly. One paper proves the size is at most a constant times N to the power 1 − c, for a fixed tiny c. Two more papers claim similar savings for other polynomial differences and for prime inputs.

First step

1977

Hillel Furstenberg and András Sárközy, independently

Significance

Major

It answers the fixed-power question of Green and Sawhney on a classical problem in additive combinatorics.

Trust

Formal proof listed

Field

Combinatorics

3 papers

The explanation

Pick numbers from 1 to 20, but no two may differ by a perfect square: 1, 4, 9 or 16. How many can you take? One good choice is 1, 3, 6, 8, 11, 13, 16 and 18. These are the numbers that leave remainder 1 or 3 when divided by 5. Any difference between two of them leaves remainder 0, 2 or 3. A square never leaves remainder 2 or 3. A difference with remainder 0 would need to be at least 25 to be a square. So no difference is a square. A computer check confirms that 8 numbers is the most possible here.

The trick breaks at 26, because 26 − 1 = 25. Is there always some way to keep a fixed share of the numbers? No. In 1977 and 1978, Hillel Furstenberg and András Sárközy proved independently that the best share shrinks toward zero as the range growsSource 1. A set with no square difference is called square-difference-free. The open question was how fast its share must shrink.

Sárközy's bound saved a small power of the logarithm of N, the top of the rangeSource 2. A logarithm grows very slowly: the natural log of a billion is about 21. Later work sharpened this, including Bloom and Maynard in 2022Source 3. In 2025, Ben Green and Mehtaab Sawhney proved a much stronger saving factor, about e to the power c√(log N)Source 4. They asked whether a power saving holds. That means a bound of the form C times N to the power 1 − c, for fixed numbers c above zero and CSource 5.

From below, the record is far smaller. In 1984, Imre Ruzsa built square-difference-free sets of size about N to the power 0.733Source 6. In 2026, Dmitry Krachun pushed the exponent just past 0.75Source 7. A large gap remains between that and any upper boundSource 8.

This family has three papers. The first proves the power saving for squaresSource 9 Source 5. The exponent c is a fixed number above zero, but extremely smallSource 10. The proof gives no useful value for itSource 11. Even so, the shape matters. If c were 0.01, N to the power 0.99 would be ten times smaller than N once N has 100 digits. The gap keeps growing after that.

The second paper replaces squares with the values of other polynomials, h(1), h(2), h(3) and so on. Some polynomials can be dodged by a large set. Take h(x) = x² + 1. Its values 2, 5, 10, 17, 26 are never multiples of 3. So the multiples of 3 avoid every such difference, keeping a third of all numbersSource 12. A polynomial is called intersective when, for every whole number q, some value of it is a multiple of q. This is exactly the condition needed for the share to shrinkSource 13. The value for each q may come from a different factor of h, and no whole-number root is neededSource 14.

For every intersective h of degree k at least 2, with a positive leading term, the second paper claims a power saving. The exponent depends only on the degree kSource 15. The constant C may depend on every coefficient of hSource 16. Before this, the best general saving was of the form e to the power (log N) to some fixed power below 1/2Source 17.

The third paper allows only prime inputs, so the forbidden differences are h(2), h(3), h(5), h(7) and so on. Here the needed condition is a little stronger. For each q, h must hit a multiple of q at an input sharing no factor with q. Under that condition, the paper claims a power savingSource 18. One example is h(x) = (x − 1)². Forbidding only the differences (p − 1)², for primes p, already forces a power savingSource 19. The best earlier bound, by Rice, saved only a power of log NSource 20. In this paper the exponent may depend on hSource 21. The proof also uses a result about the zeros of Dirichlet L-functions, functions that track primes in remainder classes. That result comes from a companion paper in the same releaseSource 22.

The main obstacle was that classical methods gain only slowly at each step. The new proof builds a quantity that is never negative. It is at least a fixed power of the density, the share of numbers in the set. It then shows this quantity shrinks by a power of NSource 23. A key move zooms in on numbers spaced D² apart and relabels them as 1, 2, 3 and so on. A square difference in the relabeled set would give one in the original setSource 24. For general polynomials, this zoom changes the polynomial, so the paper tracks a whole family of related polynomialsSource 25.

How sure is this? A computer proof checker called Lean has checked a formal version of the square result. It states that fixed constants c above zero and C work for every N. The polynomial and prime papers are not in the Lean scope note, so they remain claims. The prime paper also depends on the companion zero-free result. No specialist review of these papers has been published.

What it doesn't show. This does not give a usable value for the exponent c, or close the gap with the best known constructions.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Major if the proofs hold. Lean has checked a formal version of the square result. The polynomial and prime results are outside the Lean note. The prime result relies on a companion zero-free theorem, and no specialist review is published.

Words used

Square-difference-free: A set of whole numbers where no two members differ by a perfect square such as 1, 4 or 9.
Power saving: A bound of the form C times N to the power 1 − c, smaller than N by the growing factor N to the c.
Intersective polynomial: A polynomial that, for every whole number q, takes some value that is a multiple of q.
Density: The share of the numbers from 1 to N that belong to the set.
Dirichlet L-function: A function from number theory whose zeros control how primes spread among remainder classes.
Lean: A computer program that checks each step of a formally written proof.

The original papers (3)

A power saving for intersective polynomial differences with an exponent depending only on the degree (PDF, opens in a new tab)
October 5, 2026
A Power Saving for Polynomial Differences at Prime Arguments (PDF, opens in a new tab)
October 5, 2026
A power saving for square-difference-free sets (PDF, opens in a new tab)
September 24, 2026

Lean notes

All quoted lines (25)

Furstenberg and S\'ark\"ozy proved independently that $s(N)=o(N)$ , using ergodic theory and the circle method, respectively.
A power saving for square-difference-free sets Back to text
S\'ark\"ozy's quantitative estimate has the form $s(N)\le N/(\log N)^{1/3+o(1)}$ ; see also the historical account in.
A power saving for square-difference-free sets Back to text
Bloom and Maynard subsequently obtained $s(N)\ll \frac{N}{(\log N)^{c_{\rm BM}\log\log\log N}}$ for an absolute $c_{\rm BM}>0$ , using bounds for the additive energy of rational numbers with small denominators to improve the density-increment argument.
A power saving for square-difference-free sets Back to text
Their arithmetic level- $d$ inequality transfers product-space hypercontractive estimates to rational Fourier coefficients.
A power saving for square-difference-free sets Back to text
Theorem … answers affirmatively the fixed-power question posed in.
A power saving for square-difference-free sets Back to text
In the opposite direction, Ruzsa constructed square-difference-free sets of size $\gg N^{\gamma_0}$ , where $\gamma_0=\frac12\left(1+\frac{\log 7}{\log 65}\right) =0.733077\ldots.$
A power saving for square-difference-free sets Back to text
Krachun's construction passes the three-quarter threshold and gives $\liminf_{N\to\infty}\frac{\log s(N)}{\log N} \ge 0.752796455874514\ldots.$
A power saving for square-difference-free sets Back to text
A substantial gap remains between this lower exponent and the upper exponent $1-c$ in Theorem ….
A power saving for square-difference-free sets Back to text
Our main result is a fixed power saving in this extremal problem.
A power saving for square-difference-free sets Back to text
The exponent obtained here is positive and absolute, but extremely small.
A power saving for square-difference-free sets Back to text
The argument does not yield a useful numerical value or an optimal exponent.
A power saving for square-difference-free sets Back to text
This is the necessary local condition for polynomial differences in every set of positive density: if $h$ has no root modulo $q$ , the multiples of $q$ contain no difference in $h(\N_+)$ .
A power saving for intersective polynomial differences with an exponent depending only on the degree Back to text
This is the necessary local condition for polynomial differences in every set of positive density: if $h$ has no root modulo $q$ , the multiples of $q$ contain no difference in $h(\N_+)$ .
A power saving for intersective polynomial differences with an exponent depending only on the degree Back to text
The condition allows the roots at different moduli to arise from different factors of $h$ ; a rational root is not required.
A power saving for intersective polynomial differences with an exponent depending only on the degree Back to text
The exponent is common to all polynomials of a fixed degree.
A power saving for intersective polynomial differences with an exponent depending only on the degree Back to text
The constants $C_h,N_h$ may depend on every coefficient of $h$ , and $h$ remains fixed as $N$ grows.
A power saving for intersective polynomial differences with an exponent depending only on the degree Back to text
Their arithmetic level- $d$ inequality and random sparsification also underpin the recent general-polynomial result of Adajar et al.: for every fixed intersective $h$ of degree at least two and every fixed $0<\mu<1/2$ , $|A|\le N\exp\bigl(-c_{h,\mu}(\log N)^\mu\bigr)$ for sufficiently large $N$ .
A power saving for intersective polynomial differences with an exponent depending only on the degree Back to text
We prove a power-saving bound when these local conditions hold at every modulus.
A Power Saving for Polynomial Differences at Prime Arguments Back to text
The example $h(x)=(x-1)^2$ gives a power saving when only the differences $(p-1)^2$ are forbidden; it therefore implies a power saving for sets avoiding all nonzero square differences as well.
A Power Saving for Polynomial Differences at Prime Arguments Back to text
Rice's theorem covers every prime-intersective polynomial of degree $k\ge2$ , with $|A|\ll_{h,c}N(\log N)^{-c} \qquad\text{for every }c<\frac{1}{2k-2},$ and gives a stronger bound for quadratics.
A Power Saving for Polynomial Differences at Prime Arguments Back to text
All constants in the theorem depend only on the fixed polynomial.
A Power Saving for Polynomial Differences at Prime Arguments Back to text
This fixed half-plane is a theorem input from that companion, stronger than the classical zero-free regions near $\Re s=1$ .
A Power Saving for Polynomial Differences at Prime Arguments Back to text
The proof constructs a nonnegative quantity that dominates a fixed power of the density, and then proves that this quantity decreases by a power of the interval length.
A power saving for square-difference-free sets Back to text
Splitting that class into progressions of common difference $D^2$ and rescaling preserves square-difference avoidance: a square difference in a rescaled set would give a square difference in $A$ .
A power saving for square-difference-free sets Back to text
We retain this organization, but polynomial values require two additional compatibilities: the polynomial changes when one passes to a progression, and the local distribution supplied by the multilinear construction need not be the natural distribution of polynomial values.
A power saving for intersective polynomial differences with an exponent depending only on the degree Back to text

Other sources

183Power savings for planar halving lines and k -setsCombinatorics
172Classification of finite Euclidean Ramsey configurationsCombinatorics
171The hypercube Ramsey conjectureCombinatorics
164Hindman’s finite sums and products conjectureCombinatorics
162Counterexamples to Ryser’s covering conjectureCombinatorics

Browse Combinatorics Open since the 1970s Lean-checked results