A power saving for square-difference-free sets

Introduction

For a positive integer $N$, write $[N] = \{1,\ldots,N\}$. A set $A \subseteq[N]$ is square-difference-free if

Thus the restriction concerns differences in the integers. Define

Our main result is a fixed power saving in this extremal problem.

Theorem 1.1. There are absolute constants $c > 0$ and $C < \infty$ such that, for every integer $N \geq1$ and every square-difference-free set $A \subseteq[N]$,

Equivalently, every subset of $[N]$ larger than $CN^{1-c}$ contains distinct elements whose absolute difference is the square of a positive integer.

The exponent obtained here is positive and absolute, but extremely small. The argument does not yield a useful numerical value or an optimal exponent. All finite constructions in the proof are fixed independently of $N$ and $A$; their size affects the constants and the exponent.

Remark 1.2 (Square-difference colorings). Theorem $1.1$ gives a polynomial bound for the classical square-difference coloring problem [2], Section 4. Fix its constants $c,C$, reducing $c$ so that $0 < c < 1$ if necessary. Whenever integers $r,N \geq1$ satisfy $N > (Cr)^{1/c}$, every $r$-coloring of $[N]$ has same-colored elements $a$, $a+d^2$ with $d \geq1$. Indeed, a largest color class has size at least $N/r > CN^{1-c}$. Only the two endpoints must share a color; no color restriction is imposed on $d$. Equivalently, if $G_N$ is the graph on $[N]$ joining distinct integers whose absolute difference is a square, then

since its independent sets are exactly the square-difference-free sets.

Previous work

The problem originates in a question of Lovász. Furstenberg [8] and Sárközy [16] proved independently that $s(N) = o(N)$, using ergodic theory and the circle method, respectively. Sárközy’s quantitative estimate has the form $s(N) \leq N/(\log N)^{1/3+o(1)}$; see also the historical account in [3]. Pintz, Steiger and Szemerédi [14] strengthened this to

for an absolute $c_{\mathrm{PSS}} > 0$. Their argument combines concentration on arithmetic progressions with an iteration that increases the collection of large Fourier coefficients. Bloom and Maynard [3] subsequently obtained

for an absolute $c_{\mathrm{BM}} > 0, using bounds for the additive energy of rational numbers with small denominators to improve the density-increment argument.

Green and Sawhney [9] prove

for an absolute $c_1 > 0$. Their arithmetic level-$d$ inequality transfers product-space hypercontractive estimates to rational Fourier coefficients. Theorem 1.1 answers affirmatively the fixed-power question posed in [9]. Adajar et al. [1] extend the arithmetic level-$d$ approach to fixed integer polynomials having a root modulo every positive integer. For degree at least two they obtain a density saving $\exp(-c(\log N)^\mu)$ for every fixed $0 < \mu< 1/2$, with constants depending on the polynomial and $\mu$.

In the opposite direction, Ruzsa [15] constructed square-difference-free sets of size $\gg N^{\gamma_0}$, where

His construction uses a set of residues with no square differences modulo a squarefree integer to restrict selected digits of an integer expansion. Beigel and Gasarch [2] and Lewko [12] obtained the improved exponent

by exhibiting suitable sets of twelve residues modulo 205. Krachun’s construction [11] passes the three-quarter threshold and gives

A substantial gap remains between this lower exponent and the upper exponent $1-c$ in Theorem 1.1.

Reflection positivity yields multilinear inequalities through the chessboard method of Fröhlich and Lieb [7] and its abstract formulation by Fröhlich, Israel, Lieb and Simon [6]. Hatami [10] characterizes graph seminorms through mixed Hölder inequalities. Conlon and Lee [4] use finite reflection groups to obtain such inequalities for absolute-value inputs, and also for real-valued inputs when the two defining sets of simple reflections are disjoint. The signed mixed inequality is a classical feature of the chessboard method; its role here is to permit Fourier lifts that can change sign. We construct a finite-field probability law with the particular cycle support, reflection positivity and conditional mixing needed for the integer problem, and prove the signed inequality for that law directly.

The rational-frequency energy estimates of Bloom and Maynard [3] and the product-space methods of Green and Sawhney [9] are methodological precedents for the arithmetic part. The argument retains rational Fourier analysis and rescaling along square-step progressions. Here the quantity compared between scales is a multilinear functional of a signed Fourier lift.

Outline of the proof

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. The comparison with shorter intervals is available for every residue specification. A separate estimate makes a fixed positive proportion of those specifications negligible; these two estimates produce the contraction.

Here is the quantity to be controlled. Choose a fixed even integer $d$ and a fixed set $V$ of $d$ labels. For a finite set $\mathcal{P}$ of sufficiently large primes, put $X_{\mathcal{P}}=\prod_{p\in\mathcal{P}}\mathbb{F}_p$. We will construct a probability law for a tuple $(z_v)_{v\in V}$ in $X_{\mathcal{P}}$, and for a real function $g$ on this space define

Its $d$-th root will be a seminorm satisfying $|\mathbb{E}g|\leq Z_{\mathcal{P}}(g)^{1/d}$. To apply it to $A\subseteq[N]$, take $\mathcal{P}$ to be the primes between a fixed threshold $P$ and $N^\beta$, where $\beta>0$ is fixed and small. Let $G$ retain the rational Fourier coefficients of $1_A$ at frequencies of squarefree reduced denominator at most $N^\beta$ whose prime factors all belong to $\mathcal{P}$, including the zero frequency. Section 5 defines this Fourier lift precisely. It is real and its mean is exactly $|A|/N$, although its values may have either sign. With these choices, write $Y(N,A)=Z_{\mathcal{P}}(G)$. The seminorm bound gives

Thus a fixed power decay for $Y$ proves the theorem.

The tuple law is constructed separately over each prime field, then multiplied over the primes, collecting the field labels into vectors $z_v\in X_{\mathcal{P}}$. Every individual field label is uniform. The law has two further properties with distinct purposes. First, it is reflection positive: specified involutions of $V$ exchange two halves, and the matrix coupling the half-tuples is symmetric positive semidefinite. Repeated Cauchy–Schwarz across these cuts proves the signed mixed inequality and seminorm bound (Proposition 4.1). Second, outside a part of mass at most $p^{-4}$, a designated directed cycle of 24 labels has nonzero square differences in $\mathbb{F}_p$, and each of its edge pairs is uniform among pairs with such a difference. This exact pair law supplies the arithmetic input below. The full reflection-positive law and its normalized nonexceptional part also satisfy conditional mixing, which makes inputs with large Fourier denominators negligible (Lemma 4.3). Section 3 constructs these laws from the graph estimates of Section 2.

The approximation errors require control of signed lifts beyond their means. Every fixed moment of $G$ grows more slowly than any fixed positive power of $N$, uniformly in the prime set and in every retained family of complete denominator classes. Lemma 5.2 proves this by a conditional square-function estimate and symmetrization. The same bounds, with an explicit fiber-size cost, remain available after specifying some prime coordinates. Combined with conductor decay, they justify the Fourier truncations used in both estimates that follow.

For the change of scale, fixing prime coordinates whose product is at most a sufficiently small fixed power of $N$ makes the low Fourier coefficients exact averages on an integer residue class modulo an integer $D$. 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$. The seminorm’s square-affine symmetries therefore compare the specialized functional with the same functional at length $\lfloor N/D^2\rfloor$, up to a factor tending to one and a power-decaying error (Proposition 7.2). This comparison applies to all specified residues, without using the exceptional splitting.

The arithmetic cancellation uses the normalized nonexceptional prime laws. Set aside the finitely many primes below the tuple-law threshold, together with modulus 8, in one fixed modulus $M_0$. Independently choose one residue modulo $M_0$ for each slot. A fixed positive proportion of these assignments has strict square differences along the designated cycle: they are 1 modulo 8 and nonzero squares modulo every odd prime dividing $M_0$. For such an assignment, divide $[N]$ into ordered intervals. Unless all cycle slots choose the same interval, one directed edge goes from an earlier interval to a later one. Truncating and expanding the other slots reduces its contribution to the selected pair law. A signed kernel supported on actual shifts $m^2$ then bounds that contribution using the absence of integer square differences (Propositions 6.1 and 8.2). The event that all cycle slots choose one interval is itself small.

Finally, Section 9 expands the exceptional submeasures by inclusion–exclusion. Exceptional prime sets of large product are bounded directly by moment estimates. A smaller exceptional prime set with product $q_B$ leads to the shorter scale approximately $N/(M_0q_B)^2$. Its mass remains summable even after multiplication by $q_B$; this absorbs the factor of $q_B^{2a_0}$ incurred by a sufficiently small proposed decay exponent $a_0$. Combining this bound with the universal scale comparison and the cancellation on a positive proportion of small-residue assignments gives a strict weighted recurrence. Induction proves $Y(N,A) \ll N^{-a_0}$, and the density inequality above gives Theorem 1.1 with $c=a_0/d$. Figure 1 records the principal inputs to this assembly.

Conventions

All averages on finite sets are with respect to uniform probability measure unless another measure is displayed. All $L^r$ norms of functions on $X_P$ use its uniform product measure. Empty products are 1; the product over an empty prime set is a one-point space. We write $e(t)=\exp(2\pi i t)$ and identify rational frequencies modulo 1. The conductor of a rational frequency is its reduced positive denominator; the conductor of 0 is 1.

For nonnegative quantities, $U \ll V$ means $U \le CV$ for a constant with the dependencies stated in context. A uniform bound $U=N^{o(1)}$ means that for every $\varepsilon>0$ there is a constant $C_\varepsilon$ such that $U \le C_\varepsilon N^\varepsilon$ for all allowed data. Fixed tuple sizes and fixed moment orders may affect $C_\varepsilon$; sets, intervals, chosen residues and retained frequency families may not. All final choices of parameters are made independently of $N$ and $A$.

Finite-field square constraints

This section controls systems of square constraints on independent field variables. A single constraint is close to a constant kernel in operator norm. Replacing constraints one at a time then counts any fixed directed graph without loops or opposite edges. Applying this count to a four-cycle of two lists gives the operator estimate needed for the tuple measures.

Throughout, finite sets carry uniform probability measure, and $e(t)=\exp(2\pi i t)$. For an odd prime $p$, write

For finite sets $X,Y$, the operator associated with a kernel $K:X\times Y\to\mathbb{R}$ is

We use $\lVert K\rVert_{\mathrm{op}}$ to mean the norm of $T_K$ from $L^2(Y)$ to $L^2(X)$. A constant kernel $c$ therefore denotes the operator $f\mapsto c\mathbb{E}f$.

Lemma 2.1 (Counting directed square constraints). Let $p$ be an odd prime and let $G=(W,E)$ be a finite directed graph with no loops and at most one edge on each unordered pair of distinct vertices. Put $m=|E|$, and let $(z_w)_{w\in W}$ be independent uniform elements of $\mathbb{F}_p$. Then

The assertion includes the empty graph, whose product is 1.