On the van der Corput property for cubes

Introduction

Answering a question of Lovász, Furstenberg [5] and Sárközy [20] independently proved that if $A \subseteq[N] := \{1,\ldots,N\}$ has no nonzero square difference, then $|A| = o(N)$. Sárközy’s proof gave

Pintz, Steiger, and Szemerédi [16 Theorem 1] used a more elaborate version of Sárközy’s density increment strategy to prove

Bloom and Maynard [2] later improved this bound to

for some absolute constant $c > 0$. Recently, Green and Sawhney [7] combined Sárközy’s density increment strategy with their arithmetic level-$d$ inequality to show that, for some absolute $c > 0$,

Fan and Lott [4] subsequently used the van der Corput property for squares to improve this to

for some absolute constant $c > 0$.

A longstanding question is whether there is an absolute constant $c > 0$ such that every $A \subseteq[N]$ with no nonzero square difference satisfies the power-saving bound $|A| \ll N^{1-c}$. Very recently, OpenAI [14] released a preprint claiming such a bound.

The lower bound of Fan and Lott [4 Theorem 1.3] shows that the van der Corput method cannot yield a power saving for sets with no nonzero square difference. For cubes, however, we obtain a power saving by exploiting the oddness of $x \mapsto x^3$, which makes the complete cubic exponential sums real.

Write $e(t) = \exp(2\pi i t)$. Let $F \subseteq\mathbb{Z}$, let $N$ be a positive integer, and let $\delta> 0$. Consider a real trigonometric polynomial

such that

1. $P(\theta) \ge0$ for every $\theta\in\mathbb{R}/\mathbb{Z}$,

2. $P(0) = 1$,

3. $a_n = 0$ if $1 \le n \le N$ and $n \notin F \cup(-F)$,

4. $0 \le a_0 \le\delta$.

We call a polynomial of the form (2) satisfying (i)–(iii) a van der Corput witness for $F$ of degree at most $N$. Its nonconstant coefficients may have either sign. In the trigonometric characterization of Kamae and Mendès France [9] and Ruzsa [18], $F$ has the van der Corput property if for every $\delta> 0$ there exist an integer $N$ and a witness for $F$ satisfying (iv).

Suppose that $A \subseteq[N]$ and $(A-A) \cap F \subseteq\{0\}$. For any $P$ satisfying (i)–(iv), Fourier orthogonality gives

We give the argument in the proof of Corollary 1.2.

For the set of shifted primes $F = \{p-1 : p\text{ prime}\}$, Green [6, Theorems 1.1 and 1.2] constructed a witness of degree at most $N$ with $a_0 \ll N^{-c}$ for some absolute $c > 0$. It follows that $|A| \ll N^{1-c}$ whenever $A \subseteq[N]$ contains no two elements differing by one less than a prime.

Several other sets of forbidden differences admit power savings by the van der Corput method. Fan and Lott [3] proved that if $A-A$ contains no nonzero sum of two squares, then $|A| \ll_{\varepsilon} N^{7/8+\varepsilon}$ for every $\varepsilon> 0$. Younis [22] proved that $|A| \ll N^{1-c}$ for some absolute $c > 0$ if $A-A$ contains no integer of the form $n\lfloor2^{1/3}n\rfloor$ with $n \in\mathbb{N} = \{1,2,\ldots\}$. Kalogirou, Lott, Magyar, and Singha Roy [8] proved that for each odd $k \ge3$ and even $s \ge2$ there is a $c_{k,s} > 0$ such that $|A| \ll_{k,s} N^{1-c_{k,s}}$ if $A-A$ contains no sum of $s$ positive $k$th powers.

Matolcsi and Ruzsa [12, Theorem 2.5 and Corollary 2.6] proved that if $B \subseteq\mathbb{Z}/q\mathbb{Z}$ contains no two elements whose difference is a nonzero cube modulo $q$, then $|B| \le q^{1-\kappa}$, where $\kappa= 0.1195357\ldots$. Our construction, like theirs, uses compatible witnesses for cubic residues modulo powers of each prime.

Ninčević and Slijepčević [13, Theorems 1 and 2] studied the van der Corput property for the values of odd polynomials $h \in\mathbb{Z}[x]$ of degree $k \ge3$ with positive leading coefficient. They constructed witnesses of degree at most $N$ with nonnegative coefficients and $a_0 \ll_h (\log N)^{-1/k}$. For $h(n) = n^k$ they also proved that every such witness satisfies $a_0 \gg_k 1/\log N$.

By allowing the cosine coefficients to have either sign, we obtain a power saving for cubes.

such that

Taking $X = \lfloor N^{1/3} \rfloor$ and applying Theorem 1.1 with $3\varepsilon$ in place of $\varepsilon$ gives a witness of degree at most $N$ with $a_0 \ll_{\varepsilon} N^{-1/60+\varepsilon}$. Applying (3) gives the following corollary.

Previously, the best upper bound was due to Adajar et al. [1 Theorem 1.1]. They combined the method of Green and Sawhney with exponential sum estimates in the style of Rice [17] to show that for every $0 < \mu< 1/2$ there is a $c_{\mu} > 0$ such that

for all sufficiently large $N$.

In the first version of their paper on squares [4 Section 1], Fan and Lott announced the van der Corput power saving for cube differences that we prove here. After they submitted that version to arXiv, OpenAI released a preprint claiming a power saving for intersective polynomial differences by a different method [15 Theorem 1.1]. In the cubic case, Corollary 1.2 gives $|A| \ll_c N^{1-c}$ for every $0 < c < 1/60$, whereas the parameters in that preprint give $c = c_3 \le[72006(1201!)^{48001}]^{-1}$.¹

Let $D_3(N)$ denote the largest size of a subset of $[N]$ with no nonzero cube difference. Using a construction of Ruzsa [19 Theorem 2] and a computer-assisted search, Lewko [11 Theorem 4] proved that

There is still a considerable gap between this exponent $\beta$ and the exponent $59/60$ in Corollary 1.2. One may ask whether $D_3(N) \sim CN^{\gamma}$ for some $C > 0$ and $\gamma\in[\beta, 59/60]$. A weaker conjecture is that the limit

exists. Ruzsa [19 Section 4] asked the corresponding question for squares.

Acknowledgments

Andrew Lott and Ákos Magyar thank the Erdős Center of the HUN-REN Alfréd Rényi Institute of Mathematics for its support and hospitality during the spring 2026 Simons Semester. Máté Matolcsi and Ákos Magyar were supported by grant NKFIH-154121. Imre Z. Ruzsa was supported by grant NKFIH-146387. This work was funded by a Simons Foundation International grant administered by the Simons Foundation [SFI-MPS-TSM-00026118, Á.M.].

AI disclosure

A large language model (LLM) was used as a sounding board during the developmental phase of the project. The LLM was also used for copyediting. However, the final argument is the authors’ own, and the manuscript was written and verified by the authors, who take full responsibility for the contents of the proof.

Sketch of the proof.

Our starting point is to define local weight functions $W_{p,K}$ on the groups $\mathbb{Z}/p^K\mathbb{Z}$, where $p$ is prime and $K \in\mathbb{N}$, attached to a parameter $0 < \gamma_p < 1$. These functions are densities, relative to uniform measure, of geometric probability distributions defined by $\Pr(p^j \mid n) = \gamma_p^j$. Extending them as $p^K$-periodic functions, we show that the corresponding exponential sums

are nonnegative. With suitable optimized choices of $\gamma_p$, these sums recover the self-compatible modular witness functions constructed by Matolcsi–Ruzsa; see [12 Lemma 2.4 and Theorem 2.5] and the remark below. We will use simpler parameter choices. The local weights $W_{p,K}$ are constant on the “valuation shells” $\{n \in\mathbb{Z}/p^K\mathbb{Z}: v_p(n) = k\}$, where $v_p(n) = j$ if $p^j \mathrel{\|} n$. Thus they can be expressed as linear combinations of the Ramanujan sums $c_{p^k}(n)$:

with coefficients $b_{p^k}$ independent of the underlying group $\mathbb{Z}/p^K\mathbb{Z}$. This allows one to define the coefficients $b_d = \prod_{p^k\mathrel{\|}d} b_{p^k}$ and the global truncated weight function

By exploiting the multiplicative properties of the coefficients $b_d$ and the functions $c_d(n)$ we obtain the crucial estimate

where by $\mathbb{E}_n f(n)$ we denote the mean value of a periodic function over its period. The reason behind this estimate is that $S_R(a,q)$ can be approximated via the complete exponential sum

where $a_p \equiv a(q/p^m)^{-1} \pmod{p^m}$ for $p^m \mathrel{\|} q$, and $W_D(n) = \sum_{d\mid D} b_d c_d(n) = \prod_{p^K\mathrel{\|}D} W_{p,K}(n)$.

For $X \ge1$ and $R \ge1$, define the weighted exponential sum

We will take $R = X^{1/20}$. A major/minor arc argument then yields the uniform estimate

Taking $\eta= C_{\varepsilon}X^{-1/20+\varepsilon}$ with a sufficiently large constant, we add $\eta$ and normalize:

Then $P_X \ge0$, $P_X(0) = 1$, and its constant Fourier coefficient is

providing the witness polynomial in Theorem 1.1. A short, well-known argument then gives Corollary 1.2.

The arithmetic factors

We define the finite exponential sums that appear in the major-arc approximation to $T_X(\theta)$ and prove their required properties. We begin with nonnegative local modular witnesses attached to primes, following the modular construction of Matolcsi–Ruzsa; see [12 Section 2].

Local weight functions attached to a prime.

Fix a prime $p$ and a parameter $0 < \gamma= \gamma_p < 1$, whose value will be determined later. For $K \ge1$, consider the probability distribution on $\mathbb{Z}/p^K\mathbb{Z}$ that is uniform on each valuation shell $\{v_p(n) = j\}$, defined by

The uniform distribution corresponds to $\gamma= p^{-1}$. On $\mathbb{Z}/p^K\mathbb{Z}$, we use the valuation: $v_p(n) = j$ when $p^j \parallel n$ and $j < K$, while $v_p(0) = K$. Then

We define the local weight function $W_{p,K}$ on this group as the density of this probability distribution relative to uniform distribution, namely as

We consider this function as a $p^K$-periodic function on the integers and set $W_{p,0} = 1$. It is clear from the construction that it has mean value one over any of its periods, i.e. for every $m \ge K$, the numbers $p^{-m}W_{p,K}(n)$, $n \bmod p^m$ also form a probability distribution. The probability distributions modulo $p^K$ are compatible as $K$ varies, namely one has the compatibility property

If $v_p(n)=j<K$, all lifts $n+tp^K$ of $n$ have valuation $j$, and their weights equal $W_{p,K}(n)$. For the zero residue modulo $p^K$, one lift has weight $(p\gamma)^{K+1}$ and the other $p-1$ lifts have weight $p(1-\gamma)(p\gamma)^K/(p-1)$. Hence their average is

This compatibility underlies the construction of the global weight on $\mathbb{Z}$.

Positivity of local modular witness functions.

For $p\nmid a$ and $s\geq1$, define

where $\varphi$ is the Euler totient function. The change of variable $u\mapsto-u$ shows that these are real and lie in $[-1,1]$. We include a proof of the following standard estimate for completeness.

Proof. For $p\neq3$ and $s\geq2$, first partition the units $u$ into residue classes modulo $p^{s-1}$. On the residue class represented by $u$, replacing $u$ by $u+tp^{s-1}$ multiplies the phase by $e(3au^2t/p)$. Summing over $t\bmod p$ gives zero.

For $p=3$ and $s\geq3$, the permutation $u\mapsto u+3^{s-2}$ of the units changes the phase by $e(au^2/3)=e(a/3)\neq1$. The other terms in the binomial expansion are divisible by $3^s$, so the sum again vanishes.

Finally, the complete sum $\sum_{x\bmod p}e(ax^3/p)$ has absolute value at most $2\sqrt{p}$. Indeed, when $p\equiv2\pmod3$, the map $u\mapsto u^3$ is a permutation and the sum is zero. When $p\equiv1\pmod3$, the cubic exponential sum is the sum of the two Gauss sums associated with the nontrivial cubic characters, each of absolute value $\sqrt{p}$.

Subtracting the term $x=0$ and dividing by $p-1$ proves the asserted lower bound.

For $m\geq1$, put $K=\lceil m/3\rceil$ and define the local modular witness functions

In particular, with the choices

one has $F_{p,m}(a)\ge0$ for every $m\ge0$ and every $a$ coprime to $p$.

Proof. Note that if $p^{K}\mid n$ then $\mathrm{e}(an^{3}/p^{m})=1$. If $v_{p}(n)=j<K$, write $n=p^{j}u$. The conditional average of the phase on this shell is $U_{p^{m-3j}}(a)$. Thus, summing over $0\le j<K$ gives

The first term is the contribution of the residues satisfying $p^{K}\mid n$.

For $m\ge1$, separating the $j=0$ term for $F_{p,m+3}$ and shifting the remaining indices gives

The term $U_{p^{m+3}}(a)$ vanishes by Lemma 3.1. The lemma gives $F_{p,3}(a)=\gamma$, proving (10) also for $m=0$. Formula (12) gives the stated initial values for $m=1,2$.

For $p\ne3$, our choice in (11) satisfies

Hence Lemma 3.1 implies $F_{p,1}(a)\ge0$, and it is easy to see that $F_{p,2}(a)=\gamma_{p}>0$.

For $p=3$, the bound $U_{3},U_{9}\ge-1$ and the choice $\gamma_{3}=1/2$ suffice for both initial values to be nonnegative. Finally, the recurrence (10) implies positivity at every higher modulus $p^{m}$.

Remark. The sums $F_{p,m}(a)$ can be evaluated explicitly. If $m=3j+r$ with $r\in\{0,1,2\}$ and $p\nmid a$, then

We have chosen the parameters $\gamma=\gamma_{p}$ above for their simplicity, and have not optimized them. If

then $F_{p,m}(a)\ge0$ for all $m\ge0$ and $p\nmid a$ if and only if $\gamma\ge t_{p}/(1+t_{p})$. Extend (9) to all numerators $a$ by the same formula. One may replace $W_{p,\lceil m/3\rceil}$ by $W_{p,m}$ in that formula: the weights agree below valuation $\lceil m/3\rceil$, and the remaining tail has the same mass and phase 1. Compatibility then gives $F_{p,m}(pa)=F_{p,m-1}(a)$ for $m\ge1$. For $p\ne3$, choosing $\gamma=t_{p}/(1+t_{p})$ recovers the self-compatible family in [12 Lemma 2.4], with the base witness averaged under multiplication by nonzero cubes. For $p=3$, the optimal choice in this family is $\gamma=\cos(\pi/9)/(1+\cos(\pi/9))$; at modulus 27 it gives the invariant optimal base witness used in [12 Theorem 2.5], and the higher powers agree with its recursive extension. Thus the geometric probability laws give a realization of those modular witnesses. We keep the simpler choices in (11); optimizing them does not improve the exponent obtained from the estimates below. The properties of the parameters $\gamma_{p}$ that we need are summarized in the following lemma.

Proof. The second assertion and the inequality $1/p < \gamma_p$ follow immediately from (11). The upper bound in (i) is also immediate for $p=3$. For $p\ne3$, that upper bound is equivalent to

which follows from the arithmetic–geometric mean inequality $2\sqrt{p}\le p^{2/3}+p^{1/3}$.

Ramanujan sums and the global weight function $w_R$.

Recall the definition of the Ramanujan sums

In particular for $d=p^k$

We now express $W_{p,K}$ as a linear combination of $c_{p^k}$, $0\le k\le K$. These $K+1$ functions form an orthogonal basis for the space of functions constant on valuation shells, with respect to the inner product

To be more precise, one has

Indeed, after expanding the two Ramanujan sums, a pair of characters has nonzero contribution only if their frequencies agree modulo one. Reduced fractions with denominators $p^k$ and $p^\ell$ cannot agree mod 1 unless $k=\ell$; in that case there are exactly $\varphi(p^k)$ matching pairs.

Thus one may write

The constant coefficient is $b_1=1$, since $W_{p,K}$ has mean one. For $1\le k\le K$, direct calculation (or the probability interpretation) gives

Dividing by $\varphi(p^k)=p^{k-1}(p-1)$ yields

A crucial fact is that the coefficients $b_{p^k}$ do not depend on the truncation level $K \ge k$. This allows us to extend them multiplicatively, defining $b_d := \prod_{p^k\parallel d} b_p^k$ with $b_1=1$. Note that for $p \ne3$, our choice of the $\gamma_p$ parameters gives $b_p = 2/(\sqrt{p}+2)$, while $b_3=1/4$. Since $0 < b_p \le\gamma_p$, we obtain

For $R \ge1$, define the global weight function

By (19), $\mathcal{E}_R \subseteq[1,R^3]$, so the defining sum is finite. Although every local weight $W_{p,K}$ is nonnegative, the truncated global weight $w_R$ may have either sign.

Lower bounds for the global witness function at rational points $a/q$.

Our aim is to show that the periodic mean of $w_R(n)e(an^3/q)$ is bounded below by a small negative quantity. We write $\mathbb{E}_n f(n)$ for the mean of a periodic function $f:\mathbb{Z}\to\mathbb{C}$ over any of its periods; the value is independent of the period chosen.

Let

denote the mean value of the periodic phase function $c_d(n)e(an^3/q)$ over its period. By (20),

The means $C_d(a,q)$ and $S_R(a,q)$ are real: replacing $n$ by $-n$ conjugates the phase and leaves the weights unchanged. The key is to show that $S_R(a,q)$ is a truncated divisor sum.

Proof. A common period of the functions $c_d(n)$ and $e(an^3/q)$ is $\Delta=[d,q]$. For every prime $p\mid\Delta$, write $k_p=v_p(d)$, $m_p=v_p(q)$, and $\ell_p=\max(k_p,m_p)$. If $p\mid q$, set

The inverse $q_p^{-1}$ (mod $p^{m_p}$) exists, and $a_p$ is coprime to $p$. The additive character and the Ramanujan sum factor as

Indeed, the first identity follows from the fact that $1/q\equiv\sum_{p\mid q}q_p^{-1}/p^{m_p}\pmod{1}$. The Chinese remainder theorem applied to $\Delta=\prod_{p\mid\Delta}p^{\beta_p}$ yields the factorization

where, for $m\ge1$ and $\ell=\max(k,m)$,

with $c_{p^0}=1$. For $m=0$, the exponential is interpreted as 1 and no numerator is needed.

If $m=0$ and $k\ge1$, the local factor is the mean of $c_{p^k}$, hence zero. Suppose now that $m\ge1$ and $k\ge1$. For $0\le r\le k$, put

This is a normalized exponential sum, so $|A_r|\le1$. The identity $c_{p^k}(n)=p^k1_{p^k\mid n}-p^{k-1}1_{p^{k-1}\mid n}$ implies $\mathcal{L}_p(k,m;a_p)=A_k-A_{k-1}$. If $k>\lceil m/3\rceil$, then $3(k-1)\ge m$, so the phase is one on both supports and $A_k=A_{k-1}=1$. This proves the asserted support property. It also gives $|\mathcal{L}_p|\le2$ when $k\ge1$; when $k=0$, the local factor is an average of numbers of modulus one and has absolute value at most one. The stated bound follows from (24).

Proof of Proposition 3.4. Let $D=D(q)$. Multiplicativity and (17) give

Thus, by the Chinese remainder theorem,

Indeed, each local weight function $W_{p,\lceil m/3\rceil}$ is $p^m$-periodic and Lemma 3.2 applies with $a=a_p$. By Lemma 3.5,

Every omitted coefficient satisfies $b_d < R^{-1}$, so the absolute value of the omitted contribution is at most

Together with the nonnegativity in (26), this proves (21). Finally, for $q=1$ only $d=1$ contributes, so $S_R(0,1)=1$.

Lifting to integer cubes via the circle method.

Using a major/minor arc decomposition, we approximate $\operatorname{Re} T_X(\theta)$ on the major arcs by the product of the real arithmetic factor $S_R(a,q)$ and a nonnegative Archimedean term. The two elementary formulas for $c_d$ in (15) serve different purposes: the divisor formula is used in the major-arc approximation, and the character formula allows us to apply Weyl’s inequality on the minor arcs.

A preliminary bound.

The quantity

appears in both the major-arc approximation and the minor-arc estimate. We will use the following bound.

Proof. Note that on $\mathcal E_R$ one has $1\le(R b_d)^{3+\varepsilon}$. Extending a sum of non-negative terms to all integers and using multiplicativity, we obtain

This Euler product converges. Indeed, put $r_p=p\gamma_p^{4+\varepsilon}$. By Lemma 3.3,

and, since $b_{p^k}\le\gamma_p^k$,

For sufficiently large $p$, the estimate $\gamma_p\ll p^{-1/2}$ gives $r_p=O_{\varepsilon}(p^{-1-\varepsilon/2})$. Thus the local factor is $1+O_{\varepsilon}(p^{-1-\varepsilon/2})$, and the finitely many remaining factors are finite. This proves (28).

Approximation on the major arcs.

We derive the major-arc approximation by partial summation.

Proof. We use the divisor formula

For a fixed divisor $f$, the function $f\mathbf{1}_{f\mid n}e(an^3/q)$ has period $fq$ and its mean value over its period is

Its partial sums, after subtracting the mean times the number of terms, are $O(fq)$. Indeed, the sum of the absolute values over a period is $fq$, and $|A_f(a,q)|\leq1$. After subtracting the mean, complete periods cancel and the remaining terms contribute at most $O(fq)$.

The function $H(t)=h_X(t)e(\beta t^3)$ vanishes at both endpoints of $[0,X]$ and satisfies

Thus summation by parts gives

Multiplying by $b_d\mu(d/f)$ and summing over $f\mid d$ and $d\in\mathcal{E}_R$, we obtain the arithmetic factor

The total error is bounded using (27). Finally, $S_R(a,q)$ is real. Taking real parts and substituting $u=t^3/X^3$ gives

as required. $\square$

Minor-arc estimates.

We use the standard cubic Weyl inequality. If $(a,q)=1$ and $|\theta-a/q|\le q^{-2}$, then

uniformly in the real linear coefficient $\xi$, see [21 Lemma 2.4] or [10 equation (1)].

Proof. For every $1\le Y\le X$, the right side of (29) is at most

Indeed, the expression $Y^4/q+Y^3+qY$ increases with $Y$ and the second inequality follows from $q>Q$, $X\ge Q$, and $q\le X^3/Q$.

Summation by parts against $h_X$, whose total variation is $O(X^{-1})$, gives

uniformly in $\xi$. Using the character formula for the Ramanujan sum, we may write

Since

we have $\sum_{d\in\mathcal{E}_R}b_d\varphi(d)\le A_R$. Therefore

Proof of the main result.

We are now in a position to prove the main result. First we show the existence of the witness function $P_X(\theta)$.

Proof of Theorem 1.1. It suffices to treat $0<\varepsilon<1/20$ and sufficiently large $X$. Apply the preceding estimates with $\varepsilon/2$ in place of $\varepsilon$, and put $R=X^{1/20}$, $Q=X^{4/5}$. Given $\theta\in\mathbb{T}=\mathbb{R}/\mathbb{Z}$, Dirichlet approximation with $H=\lfloor X^3/Q\rfloor$ gives a reduced fraction $a/q$ such that

Also $|\beta| \le q^{-2}$ because $q \le H$.

If $q \le Q$, Proposition 3.4 and Lemma 4.2, together with $0 \le J \le1$, imply

If $q > Q$, Lemma 4.3 yields $|T_X(\theta)| \ll_{\varepsilon} A_RX^{\varepsilon/2}Q^{-1/4}$. Lemma 4.1 therefore reduces the three errors, up to factors bounded by $X^{\varepsilon}$, to

This implies the lower bound $\operatorname{Re} T_X(\theta) \ge-C_{\varepsilon}X^{-1/20+\varepsilon}$ uniformly in $\theta$.

If $\theta= 0$, we have $a = 0$, $q = 1$, and $\beta= 0$ in Lemma 4.2. Since $S_R(0,1) = J(0) = 1$, it follows

Take $\eta= C_{\varepsilon}X^{-1/20+\varepsilon}$, with $C_{\varepsilon}$ large enough that $\operatorname{Re} T_X(\theta) + \eta\ge0$ for all $\theta$. Since $T_X(0) = 1 + o(1)$, the denominator $T_X(0) + \eta$ is positive for sufficiently large $X$. Define

Then $P_X \ge0$, $P_X(0) = 1$, and its constant Fourier coefficient is

All nonzero frequencies are $\pm n^3$ with $1 \le n \le X$, and the cosine coefficients are real because $h_X(n)w_R(n)$ is real. For $X$ in a bounded range, use $P_X \equiv1$ and enlarge the implied constant. This completes the proof for all $X \ge1$. □

Corollary 1.2 now follows from the following short, well-known argument.

Proof of Corollary 1.2. Put $X = \lfloor N^{1/3}\rfloor$ and apply Theorem 1.1 with $3\varepsilon$ in place of $\varepsilon$. Embed $A$ in the cyclic group $G = \mathbb{Z}/L\mathbb{Z}$, where $L = 2N + 1$, and set $\widehat{1_A}(j) = \sum_{a \in A} e(aj/L)$. By orthogonality we have

Indeed, a nonconstant term could contribute only if $a-b \equiv\pm n^3 \pmod L$ for some $a,b \in A$. Since $|a-b| \le N-1$ and $n^3 \le N$, the congruence would be an equality in $\mathbb{Z}$, contradicting our assumption on the set $A$.

The terms on the left of (30) are nonnegative; hence, using the fact that $P_X(0) = 1$, we have

For $A \ne\varnothing$, this implies

Steve Fan, Andrew Lott, and Ákos Magyar

Department of Mathematics, University of Georgia, Athens, GA 30602, USA

[email protected], [email protected], [email protected]

Máté Matolcsi

HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary

Department of Analysis and Operations Research, Institute of Mathematics, Budapest University of Technology and Economics, Budapest, Hungary

[email protected]

Imre Z. Ruzsa

HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary

[email protected]