G.A. FREIMAN, H. HALBERSTAM, AND I. RUZSA:

“INTEGER SUM SETS CONTAINING LONG ARITHMETIC PROGRESSIONS”

AN EXPOSITION BY VSEVOLOD F. LEV

The main result of [FHR92] shows that if A is a dense set of integers or a dense set of residues modulo a prime, then the three-fold sumset 3A contains long arithmetic progressions. The integer version (Corollary 1 below) can be easily deduced from the finite field version, which is as follows.

Theorem 1 ([FHR92, Theorem 3]). If p is a prime, A ⊆ 𝔽_{p}, and α = |A|/p, then 3A contains an arithmetic progression of length at least

\frac{1}{8π} αp^{(α^{3}/16)}.

In fact, [FHR92, Theorem 3] is slightly more general, addressing the sumset mA with arbitrary m ≥ 3 and showing that it actually contains at least (α/2)p progressions (not necessarily disjoint) of length Ω(αp^{α^{m/(m−2)}/16}); however, these niceties do not seem to be of great importance. On the other hand, the condition that p is prime is pretty much irrelevant: for it is very easy to pass from dense sets in 𝔽_{p} to dense integer sets and then to dense sets in ℤ/Nℤ, and the other way round; see Corollary 1 below.

As Theorem 1 shows, if A ⊆ 𝔽_{p}, then for 3A to contain long progressions it suffices that the density of A is at least (log p)^{− \frac{1}{3} +ε} with ε > 0.

Theorem 1 was sharpened by Green who proved in [G02, Theorem 4] that if A ⊆ ℤ/Nℤ has density at least α, then the sumset 3A actually contains a progression of length at least

2^{−24}α^{5}( log(1/α))^{−2}N^{α^{2}/250 log(1/α)}

(which, roughly, is N^{α^{2+ε}}). On the other hand, an example presented in [FHR92] shows that 3A may fail to contain a progression of length N^{2/ log(1/α)}; this expression is conjectured in [FHR92] to be close to the best possible lower bound.

It is interesting to compare theorems of Freiman-Halberstam-Ruzsa and Green with the results, due to Bourgain and Green, on arithmetic progressions in the two-fold sumset 2A.

2 SUM SETS CONTAINING LONG PROGRESSIONS

Theorem 2 (Bourgain [B90]). There is an absolute constant c > 0 such that if A, B ⊆ ℤ/Nℤ have cardinalities αA and βN, respectively, then A + B contains an arithmetic progression of length at least e^{c((αβ log N)^{1/3}−log log N)}.

Theorem 3 (Green [G02]). There is an absolute constant c > 0 such that if A, B ⊆ ℤ/Nℤ have cardinalities αA and βN, respectively, then A+B contains an arithmetic progression of length at least e^{c((αβ log N)^{1/2}−log log N)}.

In connection with the last two theorems, Ruzsa [R91] constructed sets A ⊆ ℤ/Nℤ with |A| = (1/2 − ε)N such that 2A does not contain progressions of length e^{C_{ε}(log N)^{2/3+ε}}.

A presentation and comparison of the above-mentioned results can be found in [G02].

As we have indicated, Theorem 1 readily yields the integer version.

Corollary 1 ([FHR92, Theorem 1]). If N is a positive integer, A ⊆ [1, N], and α = |A|/N, then 3A contains an arithmetic progression of length at least c_{1}αN^{c_{2}α^{3}}, where c_{1} and c_{2} are positive absolute constants.

To derive Corollary 1 from Theorem 1, choose a prime p ∈ (6N, 12N] and apply the theorem to the canonical image of A in 𝔽_{p}, observing that this canonical image has density at least α/12.

In the rest of this note we present the original Freiman-Halberstam-Ruzsa proof of Theorem 1.

Proof of Theorem 1. Let f denote the indicator function of A and let f̂ be the (normalized) Fourier transform of f; that is,

f̂(u) = \frac{1}{p} ∑_{a∈A} e_{p}(−au); u ∈ 𝔽_{p},

so that |f̂(u)| ≤ f̂(0) = α for every u ∈ 𝔽_{p}, and

∑_{u∈𝔽_{p}} |f̂(u)|^{2} = α  (1)

by Parseval.

We observe that for z ∈ 𝔽_{p} we have z ∈ 3A if and only if the sum

∑_{u∈𝔽_{p}} (f̂(u))^{3} e_{p}(uz)

is positive. To split this sum into the main and residual parts, for fixed δ > 0 which will be specified later we set

U := {u ∈ 𝔽_{p}: |f̂(u)| > δα}

SUM SETS CONTAINING LONG PROGRESSIONS 3

and write

∑_{u∈𝔽_{p}} (f̂(u))^{3} e_{p}(uz) = f_{M}(z) + f_{R}(z),

where f_{M}(z) and f_{R}(z) are defined by

f_{M}(z) = ∑_{u∈U} (f̂(u))^{3} e_{p}(uz), f_{R}(z) = ∑_{u∉U} (f̂(u))^{3} e_{p}(uz).

Notice, that (1) yields

|f_{R}(z)| ≤ δα ∑_{u∈𝔽_{p}} |f̂(u)|^{2} = δα^{2}; z ∈ 𝔽_{p}.  (2)

Consequently, to prove that an arithmetic progression is contained in 3A, it suffices to show that for every term z of this progression we have |f_{M}(z)| > δα^{2}. To this end, we choose the midterm of the progression to be an arbitrary element of 𝔽_{p} on which f_{M} is large in absolute value, and we select the difference of the progression so that f_{M} changes slowly in the direction, determined by this difference. More precisely, we act as follows.

As

E_{z}|f_{M}(z)| ≥ E_{z}f_{M}(z) = (f̂(0))^{3} = α^{3}

(in view of 0 ∈ U), there exist c ∈ 𝔽_{p} with |f_{M}(c)| ≥ α^{3}; this c will serve the midterm of the progression. To find the difference of the progression, we start with observing that

|U| ≤ α^{−1}δ^{−2}

by (1). Taking into account that 0 ∈ U and U is symmetric, by a standard application of the Dirichlet box principle, there exist d ∈ 𝔽_{p} \ {0} such that

∥du/p∥ ≤ p^{−2/|U|} ≤ p^{−2αδ^{2}}

holds for every u ∈ U, with ∥ · ∥ denoting the distance-from-the-nearest-integer function. We select d to be the difference of our progression.

For every integer k we have

|f_{M}(c + kd) − f_{M}(c)| ≤ ∑_{u∈U} |f̂(u)|^{3}| e_{p}(kdu) − 1|

≤ 2π ∑_{u∈U} |f̂(u)|^{3}∥kdu/p∥

≤ 2πkp^{−αδ^{2}}α ∑_{u∈𝔽_{p}} |f̂(u)|^{2}

= 2πkα^{2}p^{−αδ^{2}} (where we used (1) once again). By our choice of c an in view of (2), if

α^{3} − 2πkα^{2}p^{−2αδ^{2}} > δα^{2},

then 3A contains a (2k + 1)-term arithmetic progression. The last condition can be re-written as

k < \frac{1}{2π} (α − δ)p^{2αδ^{2}}.

Consequently, choosing, say, δ := α/\sqrt{2}, we ensure that 3A contains a progression of length at least 0.1αp^{α^{3}}. □

References

[B90] J. Bourgain, On arithmetic progressions in sums of sets of integers, in “A Tribute to Paul Erdős”, CUP (1990), 105–109.

[FHR92] G.A. Freiman, H. Halberstam, and I. Ruzsa, Integer sum sets containing long arithmetic progressions, J. London Math. Soc. 2 46 (1992), 193–201.

[G02] B. Green, Arithmetic progressions in sumsets, Geom. and Funct. Anal. 12 (2002), 584– 597.

[R91] I.Z. Ruzsa, Arithmetic progressions in sumsets, Acta Arith. 60:2 (1991), 191–202.