LECTURE NOTES 2 FOR 254A

TERENCE TAO

1. The structure of sets essentially closed under addition

Let Z be an abelian group, and let A be a non-empty finite subset of Z which is essentially closed under addition in the sense that |A + A| ∼ |A|. In the previous week’s notes, we were able to deduce quite a bit of information about A. For instance, from sumset estimates we know that any additive combination A ± A ± A … ± A of A also has cardinality comparable to A. In fact by combining this with Rusza’s quotient lemma we have a stronger statement, that any such additive combination is contained in the union of O(1) translates of A − A. In particular the set G := A − A is very close to being a subgroup of Z, in the sense that G + G ⊆ X + G for some small set X. Throughout these notes we call a set X small if we have |X| = O(1).

Let us make some notation. We say that a set A′ is a refinement of another set A if A′ ⊆ A and |A′| ∼ |A|. We say that a set A′ is a small convolution of another set A if A′ = X +A for some small set A. We say that A′ is a refined small convolution of A if it is the refinement of a small convolution of A. Thus the set G = A − A mentioned above is a refined small convolution of itself. Observe that the relation of being a refined small convolution is transitive (but not quite symmetric, recall that to cover a set by its refinement could require a logarithmic number of covers).

This is already a fairly satisfactory state of affairs. For comparison with the exactly closed under addition case, if we know that |A + A| = |A| then we know that A is a translate A = x + G of some subgroup G of Z, so in particular G = A − A and G + G = G.

However, we can still ask for more. We know a lot about the structure of finite abelian groups G; they are the direct product of a finite number of cyclic groups (we won’t prove this fact here, but it is standard in any graduate algebra course). This is a very explicit description of these sets. We could ask for a similarly explicit description of sets essentially closed under addition.

To get an idea of what one could hope for, note first that if A is essentially closed under addition, and A′ is a refinement, then A′ is also essentially closed under addition, since

|A′| ≤ |A′ + A′| ≤ |A + A| ∼ |A| ∼ |A′|.

Also, if A is essentially closed under addition, and A′ is a small convolution of A, i.e. A′ = X + A for some small set X, then A′ is also essentially closed under addition, since

|A′| ≤ |A′ + A′| = |X + X + A + A| ≤ |X + X||A + A| ≲ |A| ≤ |A′|.

Thus any characterization of sets essentially closed under addition must be stable under both refinement and small convolutions, and hence under refined small convolutions. It must also be stable under Cartesian products and bijective Freiman homomorphisms of order at least 2; to remind you of the terminology, let us recall

Definition 1.1. Let k ≥ 2, let A ⊂ Z be the subset of one abelian group, and let B ⊂ Z′ be the subset of another abelian group.

A Freiman homomorphism of order k ϕ : A → B is a map such that for any x_{1}, …, x_{k}, y_{1}, …, y_{k} ∈ A, we have

ϕ(x_{1}) + … + ϕ(x_{k}) = ϕ(y_{1}) + … + ϕ(y_{k})

whenever

x_{1} + … + x_{k} = y_{1} + … + y_{k}.

If moreover ϕ is bijective and the inverse is also a Freiman homomorphism of order k, we say that ϕ is a Freiman isomorphism of order k.

Thus, for instance, bijective Freiman homomorphisms of order at least 2 preserve the size of A and cannot increase the size of A + A. Note that bijective Freiman homomorphisms are not necessarily Freiman isomorphisms, which would in fact preserve the size of A + A.

In light of these invariances, the best structure theorem one can hope for is something of the form

Conjecture 1.2. Let A be essentially closed under addition. Then A is a refined small convolution of a set P, where P is some explicit set which is very similar to a product of finite cyclic groups, which is manifestly essentially closed under addition, and is also stable under Cartesian products and bijective Freiman homomorphisms of order at least 2.

It turns out that this conjecture is more or less true, for very satisfactory classes of objects P. When the ambient group Z is torsion free or has very large torsion, one can take P to be something called a generalized arithmetic progression and the result is known as Freiman’s theorem. When the ambient group Z has small torsion, then one can take P to be a genuine subgroup of Z and the result is due to Rusza (and is in fact quite short, given all the machinery we’ve already developed). There are intermediate cases where Z has intermediate or mixed torsion where one can state some theorems of a similar flavor, but we won’t do so here.

2. The bounded torsion case

We begin with the case where Z has bounded torsion, i.e. there is some small positive integer r = O(1) such that rx = 0 for all x ∈ Z. For instance, Z could be the direct sum of a large number of copies of Z/rZ. In this case we have Theorem 2.1. [?] Let Z have bounded torsion, and let A ⊆ Z be essentially closed under addition. Then A is a refinement of a subgroup G of Z.

Clearly the converse is true: subgroups are essentially closed under addition, and hence so are refinements. One may wonder what happed to the small convolutions, but in the bounded torsion case a small convolution X + G of a subgroup G is a refinement of the slightly larger subgroup ⟨X⟩ + G, where ⟨X⟩ is the subgroup generated by X (and clearly has cardinality at most r^{|X|} = O(1). Clearly the subgroup property is stable under Cartesian products; it takes a little more effort to see that a Freiman homomorphic image of order 2 of a subgroup is a translated subgroup (Exercise 1), which is thus a refinement of a slightly larger subgroup.

Proof Without loss of generality we may assume that 0 ∈ A (since we can just add it in if it isn’t already there). Then A is a refinement of A−A, and so it suffices to show that the set G_{0} := A − A is a refinement of some subgroup. If we let ⟨G_{0}⟩ be the group generated by G_{0}, it thus suffices to show that |⟨G_{0}⟩| ≲ |G_{0}|.

As mentioned in the previous section, we already know that

G_{0} + G_{0} ⊆ X + G_{0}

for some small set X. Iterating this we see that

G_{0} + G_{0} + G_{0} ⊆ X + X + G_{0}
G_{0} + G_{0} + G_{0} + G_{0} ⊆ X + X + X + G_{0}

etc. Doing this r times and taking unions, we thus obtain

⟨G_{0}⟩ ⊂ ⟨X⟩ + G_{0},

and hence

|⟨G_{0}⟩| ≤ |⟨X⟩||G_{0}| ≤ r^{|X|}|G_{0}| ≲ |G_{0}|

as desired.

Doing this argument a little more carefully and explicitly one can get a more precise statement: if |A+A| ≤ K|A| and Z has torsion r, then A is contained in a subgroup G of cardinality at most K^{2}r^{K^{4}}|A|. Thus this theorem is only effective when r and K are fairly small, otherwise the passage from X to ⟨X⟩, in particular, is rather lossy.

3. The torsion-free case

We now turn to the torsion-free case (when nx ≠ 0 for all x ∈ Z\{0} and n = 1, 2, 3, …), which is substantially more difficult. As far as I know, nobody has managed to adapt the simple argument in the previous section to this case (of course, one would have to replace “subgroup” by another notion, e.g. “generalized arithmetic progression”, since in the torsion-free case all non-trivial subgroups are infinite). It is still possible to proceed, but we must now supplement our combinatorial techniques with a powerful new weapon - the Fourier transform.

Before we do so, though, let us try to figure out what “subgroup” should be replaced with in the torsion-free case. To put it another way, what explicit finite sets P are there which are manifestly essentially closed under addition?

A simple example is the interval [0, N] := {n ∈ Z : 0 ≤ n ≤ N} in the torsion-free group Z. Since |[0, N]| = N + 1 and [0, N] + [0, N] = [0, 2N], we see that [0, N] is essentially closed under addition. More generally, (and keeping in mind that our sets P should be stable under Cartesian products), if we have any multi-index N := (N_{1}, …, N_{d}), we can define the box

[0, N] := {(n_{1}, …, n_{d}) ∈ Z^{d} : 0 ≤ n_{i} ≤ N_{i} for i = 1, …, d}.

Since |[0, N]| = ∏_{i=1}^{d}(N_{i} + 1) and [0, N] + [0, N] = [0, 2N], we see that

|[0, N] + [0, N]| ≤ 2^{d}|[0, N]|

and so [0, N] is essentially closed under addition if d is bounded. We call d the dimension or rank of the box [0, N], and call the number |[0, N]| = ∏_{i=1}^{d}(N_{i} + 1) the volume of the box.

We also need to be stable under bijective Freiman homomorphisms of order 2. To this end, we make the following definitions. If ϕ : Z^{d} → Z is an affine homomorphism (i.e. the translation of a genuine homomorphism) and [0, N] is a box of dimension d, we call ϕ([0, N]) an generalized arithmetic progression of dimension d, length N and volume |[0, N]|. If ϕ is in fact injective on [0, N], then we call this generalized arithmetic progression proper. It is easy to see that a generalized arithmetic progression takes the form

P := {a + ∑_{i=1}^{d} n_{i}v_{i} : 0 ≤ n_{i} ≤ N_{i} for i = 1, …, d} = {a + n · v : n ∈ [0, N]}

for some fixed group elements a, v_{1}, …, v_{d} ∈ Z, where v := (v_{1}, …, v_{d}) ∈ Z^{d}, and the dot product n · v is defined in the obvious manner. Also, it is clear that this progression is proper if all the sums a + ∑_{i=1}^{d} n_{i}v_{i}. When d = 1 this is clearly just the familiar notion of arithmetic progression. We call a = ϕ(0) the base point of the progression P, and we call v_{1}, …, v_{d} the basis vectors of P.

If ϕ is injective on [0, N], then it is definitely a bijective Freiman homomorphism of order 2 from [0, N] to ϕ([0, N]), and hence all proper generalized arithmetic progressions are essentially closed under addition if the dimension is bounded. (Conversely, these are the only images of [0, N] under bijective Freiman homomorphisms; see Exercise 2). It is not as obvious, but in fact even the improper generalized arithmetic progressions are essentially closed under addition; we will see this in the next section.

We can now state Freiman’s theorem, which asserts that up to refined small convolution, proper generalized arithmetic progressions are the only sets essentially closed under addition.

Theorem 3.1 (Freiman’s theorem). [2] Let Z be a torsion-free abelian group, and let A ⊆ Z be essentially closed under addition. Then A is a refined small convolution of a proper generalized arithmetic progression P of bounded rank.

It turns out we can drop the “small convolution” bit of this theorem; more on this later.

We now sketch how this theorem is proven. Firstly, we observe using Rusza’s quotient lemma that it suffices to show that some arithmetic combination of A, such as 2A − 2A, can be refined to a proper generalized arithmetic progression. Next, we use some Freiman isomorphisms to set Z to be a cyclic group, of order not much larger than |A|. The task is now to find a large arithmetic progression in 2A − 2A. It is here that the Fourier transform comes in handy; 2A − 2A is the Fourier support of the non-negative function |χ̂_{A}|^{4}. The fact that A is essentially closed under addition and that A is a large subset of Z will mean that |χ̂_{A}|^{4} is concentrated on a small set, which will imply that 2A − 2A contains the “dual” of that set. This dual is something known as a Bohr neighbourhood. The last step is to show that Bohr neighbourhoods contain large proper generalized arithmetic progressions.

4. Reduction to finding a large arithmetic progression inside 2A − 2A

Let A be essentially closed under addition. Our task is to place A inside (a small convolution) of a proper generalized arithmetic progression P of comparable size. Clearly we may assume that A is large, since the task is trivial if A = O(1).

It may seem strange, but up to small convolutions, the task of placing A inside P is almost the same as placing P inside A, or in some enlargement of A such as 2A − 2A. This is analogous to the statement in group theory that if a group contains a group H of small index. then G is contained in a small extension of H. To extend this to our situation of sets essentially closed under addition, we recall (a consequence of) Rusza’s quotient lemma from last week’s notes, which we rephrase here in our new language:

Lemma 4.1 (Rusza’s quotient lemma). If |A + B| ∼ |A| ∼ |B|, then A is a refined small convolution of B − B.

Thus if we can find a proper generalized arithmetic progression P of bounded rank such that |A + P | ∼ |A| ∼ |P |, Rusza’s quotient lemma will then give that A is a refined small convolution of P − P. Since P is a generalized arithmetic progression of bounded rank, P − P is a refined small convolution of P, and the claim then follows. (To see what is going on here, pretend that the progression P is actually a subgroup. Then the condition |A + P | ∼ |P | asserts that the quotient set A/P is small, and thus that A is contained in a small convolution of P).

So, we need to find a large proper progression P which is essentially A-invariant. But from sumset estimates we already know that all additive combinations of A, such as 2A − 2A, are already essentially A-invariant. Thus if we can find a proper generalized arithmetic progression P which refines 2A−2A and is of bounded rank, then we are done.

It remains to show that 2A − 2A contains a large subset (of cardinality ∼ |A|) which is also a proper generalized arithmetic progression of bounded rank. To do this we first use Freiman homomorphisms to restrict A to an abelian group Z of comparable cardinality.

5. Restricting A to a cyclic group

Right now A is a subset of an arbitrary torsion-free abelian group Z. This group, being infinite is far too large to do any accurate Fourier analysis on, given how finite A is. (The uncertainty principle tells us that Fourier analysis is more useful when applied to large objects rather than small ones). On the other hand, we don’t really use all of Z - in fact, we are only looking for progressions inside 2A − 2A. This set is reasonably small (it has size ∼ |A|) and behaves sort of like a group, so it seems reasonable that we can somehow quotient out the rest of Z and just work in a group of order comparable to A. This we can do, thanks to the technology of Freiman homomorphisms.

We will need Freiman isomorphisms of order 8 on A. These will induce Freiman isomorphisms of order 2 on 2A−2A, which is enough to preserve proper generalized arithmetic progressions (Exercise 2).

First note that since Z is torsion free, A can be mapped onto the integers via a Freiman isomorphism of order 8 (Lemma 2 of last week’s notes). So we can assume that Z is the integers Z. This is better than Z being arbitrary, however the infinite nature of Z will still cause problems (because we will soon want to talk about a “random dilation” of A, and this only makes sense for finite groups). So now we truncate the integers to be finite.

By translating A we may assume that A lives on the positive integers, and in particular lies inside the interval [1, p/8] for some very large prime p ≫ |A|. Since [1, p/8] can be mapped via a Freiman isomorphism of order 8 into the field Z/pZ, we can thus assume now that A lives inside the field Z/pZ. (This is no longer torsion free, but we will not need the torsion-free assumption any more).

We have now localized A to live in a finite group, but this is not particularly useful right now because p could be so much larger than |A| that A only will occupy a tiny fraction of Z/pZ, which suggests via the uncertainty principle that Fourier analysis at this stage would not be helpful. To fix this we will perform a random projection of A onto a much smaller group Z/NZ, for some N which is comparable in size to A (we will choose N later).

But first, we use a random dilation trick, to give us some freedom to avoid some obstacles later on. Let λ be a randomly chosen invertible element of the field Z/pZ; this induces an additive isomorphism x → λx on Z/pZ. In particular, we observe that the set λA is Freiman isomorphic to A of order 8 (in fact, of any order). So we have the freedom to randomly dilate A. (Of course, A would then no longer live in [0, p/8], but we soon use a pigeonholing trick to compensate for this fact).

Now let N ≪ p be chosen later, and define the projection π : Z/pZ → Z/NZ by setting

π(n) := (n mod N) for all N = 0, 1, 2, …, p − 1.

This is not quite an additive homomorphism, however note that for j = 0, 1, …, 7, π is a Freiman homomorphism of order 8 when restricted to the set Z_{j} := (jp/8, (j + 1)p/8], which is a set which occupies roughly \frac{1}{8} of the original field Z/pZ. By the pigeonhole principle, for each λ there exists a 0 ≤ j < 8 such that the set A′ := λA ∩ Z_{j} refines λA. Thus if we set B := π(A′) ⊆ Z/NZ, then the map π : A′ → B is a surjective Freiman homomorphism of order 8.

This is beginning to look pretty good, but there is a problem: this map might not be injective (so that there might be collisions π(x) = ϕ(x′) for two distinct x, x′ ∈ A′). More generally, there may be collisions in 8A′, so that

π(x_{1}) + … + π(x_{8}) = π(x′_{1}) + … + π(x′_{8})

while x_{1}+…+x_{8} ≠ x′_{1}+…+x′_{8}, where all sixteen elements are in A′; this is the only obstruction to π being a Freiman isomorphism of order 8. Fortunately, this type of collision rarely occurs, if N is large enough and λ is chosen randomly. Indeed, if we do have the above collision, then the integer (x_{1} + … + x_{8}) − (x′_{1} + … + x′_{8}) must be a non-zero multiple of N. Thus we will have no collisions if the set 8A′ − 8A′ ⊆ λ(8A − 8A) contains no multiples of N, where we think of elements of Z/pZ as being integers from 0 to p − 1. However, for each non-zero element y in 8A − 8A, the probability that the randomly dilated element λy will be a multiple of N is O(1/N), since p is prime. Thus, if we choose N ≫ |8A − 8A|, there will be a non-zero probability that there are no collisions. Since |8A − 8A| ∼ |A|, we can do this by choosing N to be a sufficiently large but bounded multiple of |A|.

To summarize, if we choose N large but still comparable to A we can find a refinement A′ of λA which is Freiman-isomorphic of order 8 to a subset B of Z/NZ. If we can show that 2B − 2B contains a proper bounded-rank generalized arithmetic progression of size comparable to |B|, this implies (by pulling back the Freiman isomorphisms) that 2A′−2A′, and hence 2A−2A, similarly contain a proper boundedrank generalized arithmetic progression of size comparable to |B| = |A′| ∼ |A|, and we will be done.

Thus to conclude the proof of Freiman’s theorem, we have to prove

Proposition 5.1. Let N be a large integer, and let A be a subset of Z/NZ with cardinality |A| ∼ N and such that |A+A| ∼ |A|. (The latter condition is superfluous from the former, but there is a reason why we still keep it around, which we will get to later). Then 2A − 2A contains a proper bounded-rank generalized arithmetic progression P of cardinality |P | ∼ N.

Now we have achieved the goal of making A a large subset of the group, which allows for Fourier analysis to enter the picture. This we will do in the next section.

(A remark: The observant reader may ask why we aren’t done already proving Freiman’s theorem, because Z/NZ is certainly a proper arithmetic progression, and by our assumptions it isn’t much larger than A itself. The problem is that the projection π is not an isomorphism on all of Z/NZ; at best it is an isomorphism on smaller sets such as 8A or 2A−2A, and you can’t pull the progression Z/NZ to get any sort of meaningful progression in the original group. So Freiman isomorphisms are somewhat subtle maps - once you stray too far from the original set A (where “too far” depends on the order of the isomorphism), the mapping properties become terrible.)

Note, by the way, that since the magnitude of N is determined up to a constant, one can easily arrange matters so that N is prime (e.g. by using the prime number theorem; much more elementary proofs are available that there is a prime between N and CN for large enough N and some large absolute constant C).

6. Fourier analysis on finite abelian groups

Let Z be an additive finite abelian group. Then there exists a map e : Z × Z → S^{1}, where S^{1} := {z ∈ C : |z| = 1} is the unit circle, which is multiplicative in the sense that

e(x + x′, ξ) = e(x, ξ)e(x′, ξ); e(x, ξ + ξ′) = e(x, ξ)e(x, ξ′) for all x, x′, ξ, ξ′ ∈ Z

and which is non-degenerate in the sense that for every non-zero x there exists a ξ such that e(x, ξ) ≠ 1, and similarly for every non-zero ξ there exists a x such that e(x, ξ) ≠ 1. We call e a bi-character of Z. Note in particular that e(0, ξ) = e(x, 0) = 1, and e(x, −ξ) = e(−x, ξ) = \overline{e(x, ξ)} for all x, ξ ∈ Z. We usually refer to x as the position variable and ξ as the frequency variable.

The existence of such a bi-character is easiest to see in the cyclic case Z = Z/NZ, in which case one can just take

e(x, ξ) := exp(2πixξ/N).

Also, if Z is the direct sum Z = Z_{1} × Z_{2} of two smaller abelian groups, with bi-characters e_{1} and e_{2} respectively, then the tensor product

e_{1} ⊗ e_{2}((x_{1}, x_{2}), (ξ_{1}, ξ_{2})) := e_{1}(x_{1}, ξ_{1})e_{2}(x_{2}, ξ_{2})

is a bi-character on Z. Since every finite abelian group is the direct sum of cyclic groups, we thus see that every abelian group has at least one such bi-character. (There are actually many bi-characters, basically because Z contains lots of automorphisms, but it never makes much of a difference in Fourier analysis which one you pick. One can make things more canonical by letting ξ range not in Z, but rather in the dual group Z^{∗}, which consists of the characters on Z., in which case e(x, ξ) is just the tautological map of ξ applied to x.)

Once one selects and fixes a bi-character e, one can then do Fourier analysis. Let dx denote normalized counting measure on Z, thus

∫_{Z} f(x) dx := \frac{1}{|Z|} ∑_{x∈Z} f(x),

and let dξ denote discrete measure on Z, thus

∫_{Z} g(ξ) dξ := ∑_{ξ∈Z} g(ξ).

The functions e(·, ξ) then form an orthonormal basis of L^{2}(Z, dx) (Exercise 3). Because of this, if we define define the Fourier transform f̂(ξ) of a complex-valued function f(x) on Z by the formula

f̂(ξ) := ⟨f, e(·, ξ)⟩_{L^{2}(Z,dx)} := ∫_{Z} f(x)\overline{e(x, ξ)} dx

then we have the Fourier inversion formula

f(x) = ∫_{Z} f̂(ξ)e(x, ξ) dξ = ∑_{ξ∈Z} f̂(ξ)e(x, ξ)

(Exercise 3). Furthermore, we have the Parseval relation

⟨f, g⟩_{L^{2}(Z,dx)} = ⟨f̂, ĝ⟩_{L^{2}(Z,dξ)}

and hence the Plancherel formula

∥f∥_{L^{2}(Z,dx)} = ∥f̂∥_{L^{2}(Z,dξ)}

(Exercise 3). Furthermore, if we define convolution

f ∗ g(x) := ∫_{Z} f(y)g(x − y) dy

then we have

{ \atop f ∗ g}(ξ) = f̂(ξ)ĝ(ξ)

(Exercise 3), and if we define reflection f̃ by

f̃(x) := \overline{f(−x)}

then we have

ˆf̃(ξ) = \overline{f̂}(ξ)

(Exercise 3).

We now apply these Fourier identities to the characteristic function f(x) = χ_{A}(x) of some subset A ⊆ Z of cardinality |A| = c|Z| for some 0 < c ≤ 1; we shall think of c as being reasonably close to 1. Then from Plancherel we have

∑_{ξ∈Z} |χ̂_{A}(ξ)|^{2} = ∫_{Z} |χ_{A}(x)| dx = c  (1)

while from the triangle inequality we have the crude pointwise estimate

|f̂(ξ)| ≤ ∫_{Z} |χ_{A}(x)| dx ≤ c.  (2)

Together, these bounds imply that the number of “large” Fourier coefficients is rather small: for any 0 < ε ≤ 1, we have

|{ξ ∈ Z : |χ̂_{A}(ξ)| ≥ εc}| ≤ ε^{−2}c^{−1}.  (3)

This is a basic consequence of orthogonality; the only way that |χ̂_{A}(ξ)| = |⟨χ_{A}, e(·, ξ)⟩| can come close to the theoretical maximum of c is if χ_{A} is close to parallel to the character e(·, ξ), but because the characters are all orthogonal, it is difficult for χ_{A} to be close to parallel to too many of these characters at once. Later on we will obtain a more refined estimate for these “resonant frequencies” ξ where the Fourier transform is large.

Now suppose that A is essentially closed under addition, so that |A + A| ≤ K|A| for some K = O(1). Then χ_{A} ∗ χ_{A} is supported on A + A which has normalized measure at most cK. On the other hand, we have

∥χ_{A} ∗ χ_{A}∥_{L^{1}(Z,dx)} = ∥χ_{A}∥_{L^{1}(Z,dx)}∥χ_{A}∥_{L^{1}(Z,dx)} = c^{2},

and hence by Hölder’s inequality (or Cauchy-Schwarz)

∥χ_{A} ∗ χ_{A}∥_{L^{2}(Z,dx)} ≥ c^{3/2}K^{−1/2}.

By Plancherel this implies that

∑_{ξ∈Z} |χ̂_{A}(ξ)|^{4} ≥ c^{3}K^{−1}.  (4)

In contrast, notice from (1), (2) that

∑_{ξ∈Z} |χ̂_{A}(ξ)|^{4} ≤ c^{2} ∑_{ξ∈Z} |χ̂_{A}(ξ)|^{2} = c^{3}  (5)

so we have a very precise control on the l^{4} norm of χ̂_{A} here, especially if K is small. In fact, we can even get a concentration estimate on χ̂_{A}. A slight modification of (5) gives

∑_{ξ∈Z:|χ̂_{A}(ξ)|≤εc} |χ̂_{A}(ξ)|^{4} ≤ ε^{2}c^{2} ∑_{ξ∈Z} |χ̂_{A}(ξ)|^{2} = ε^{2}c^{3},

so if we choose ε := \frac{1}{2\sqrt{K}}, then by (4) we have

∑_{ξ∈Λ} |χ̂_{A}(ξ)|^{4} ≥ \frac{3}{4} ∑_{ξ∈Z} |χ̂_{A}(ξ)|^{4}  (6)

where Λ is the set of resonant frequencies

Λ := \{ξ ∈ Z : |χ̂_{A}(ξ)| ≥ \frac{c}{2\sqrt{K}} \}.

On the other hand, from (3) we have

|Λ| ≤ 4Kc^{−1}.  (7)

Thus, if A is essentially closed under addition, a small set Λ of frequencies will dominate the L^{4} norm of χ̂_{A}. (This should be contrasted with the case when A is exactly closed under addition: see Exercise 4).

To access this structural information about |χ̂_{A}(ξ)|^{4}, we introduce the function f(x) defined by

f := χ_{A} ∗ χ_{A} ∗ χ̃_{A} ∗ χ̃_{A}.

Observe from our Fourier identities that f is supported on 2A−2A and has Fourier transform

f̂(ξ) = |χ̂_{A}(ξ)|^{4}.

In particular, f has non-negative Fourier transform which is in some sense highly concentrated in Λ. Remember that we wanted to show that 2A − 2A contained a large arithmetic progression; it thus suffices to show that the support of f contains a large proper arithmetic progression. By the Fourier inversion formula, it thus suffices to find a large proper bounded-rank generalized arithmetic progression P for which the Fourier series

f(x) = ∑_{ξ∈Z} |χ̂_{A}(ξ)|^{4}e(x, ξ)  (8)

is non-zero for all x ∈ P.

Now we use the fact that |χ̂_{A}|^{4} is concentrated in Λ; by the uncertainty principle, this should mean that f should be concentrated on some sort of dual set of Λ. To make this precise, let X ⊆ Z denote the set

X := {x ∈ Z : |e(x, ξ) − 1| < 1/4 for all x ∈ Λ};  (9)

this is an example of a Bohr set and we will have more to say about this set later. Then it is clear that

Re ∑_{ξ∈Λ} |χ̂_{A}(ξ)|^{4}e(x, ξ) ≥ \frac{3}{4} ∑_{ξ∈Z} |χ̂_{A}(ξ)|^{4},

so in particular

| ∑_{ξ∈Λ} |χ̂_{A}(ξ)|^{4}e(x, ξ)| ≥ \frac{3}{4} ∑_{ξ∈Z} |χ̂_{A}(ξ)|^{4}.

On the other hand, from (6) and the triangle inequality we have

| ∑_{ξ∈Z\Λ} |χ̂_{A}(ξ)|^{4}e(x, ξ)| ≤ \frac{1}{3} ∑_{ξ∈Λ} |χ̂_{A}(ξ)|^{4}.

Adding this together, we see thus see that the expression (8) is non-zero for all x ∈ X. In other words, the Bohr set X is contained in 2A − 2A. (It is not yet clear how useful this is, because we haven’t shown any lower bounds on the size of X, but we will come to this shortly).

Let us now apply the above discussion to the situation inherited from the previous section, in which we have a refinement A of Z_{N} such that |A + A| ∼ |A|; thus both c and K are comparable to one, and so by (7) Λ is a small set. We have shown that 2A−2A contains a Bohr set X, which is sort of a dual to Λ. Thus all we need to do is show that the Bohr set contains a proper bounded-rank generalized arithmetic progression P of size comparable to N, and we will have proven Freiman’s theorem. This is the purpose of the next section.

7. Some lattice theory

Let us remind ourselves of the current situation. We have a large integer N, and a small set Λ in Z/NZ, so that |Λ| = O(1). We wish to show that the Bohr set (9) contains a proper bounded-rank generalized arithmetic progression of volume ∼ N.

We haven’t fixed the bicharacter e yet; let us use the standard one e(x, ξ) := exp(2πixξ/N). Then our Bohr set takes the form

X = \{x ∈ Z : ∥\frac{xξ}{N} ∥ < δN for all x ∈ Λ\}

for some small absolute constant δ (corresponding to the 1/4 factor in (9); one can shrink X a bit and take δ to be 1/20 for concreteness). Here ∥x∥ denotes the distance from the real number x to the nearest integer.

In contrast, note that the set

\{x ∈ R : ∥\frac{xξ}{N} ∥ = 0\}

is an infinite arithmetic progression for each x ∈ Λ. So X is in some sense the intersection of |Λ| = O(1) many neighbourhoods of arithmetic progressions, and we have to somehow show that X thus itself contains a large generalized arithmetic progression of bounded rank. To do this we use some lattice theory.

First note that we can erase 0 from Λ since it contributes nothing to the Bohr set. Let us now enumerate Λ as Λ = {ξ_{1}, …, ξ_{k}} for some k = O(1). We work on the torus T^{k} := R^{k}/Z^{k}, and isolate the vector

w := (\frac{ξ_{1}}{N} , …, \frac{ξ_{k}}{N}) + Z^{k}

in this torus. Since Nw = 0, the expression xw ∈ T^{k} makes sense for every x ∈ Z/NZ. Observe that the set

X′ := {x ∈ Z/NZ : xw ∈ B(0, δ)},

where B(0, δ) is the ball of radius δ around the origin in the torus T^{k}, is contained in the Bohr set X. Thus it will suffice to show that X′ contains a proper bounded-rank generalized arithmetic progression P of cardinality ∼ N.

As a warm up let us first show the much weaker statement that |X′| ∼ N (so that we at least have enough elements to support such a large arithmetic progression). We can cover the torus T^{k} by about O((C/δ)^{k}) balls of radius δ/2. By the pigeonhole principle, one of these balls, say B(x_{0}, δ/2), contains at least ≳ (δ/C)^{k}N multiples of w. Subtracting, this means that B(x_{0}, δ/2) − B(x_{0}, δ/2) = B(0, δ) contains ≳ (δ/C)^{k}N multiples of w. Since δ is an absolute constant and k = O(1), we see that |X′| ≳ N and we are done.

We still have to construct P. The idea is to use basis vectors v_{i} ∈ Z/NZ such that v_{i}w is very close to the origin; this will allow us to use many multiples of v_{i} in our progression and still have the property that xw ∈ B(0, δ) for all x ∈ P. Of course we need the progression to be proper, which we will achieve by ensuring that the v_{i}w are “linearly independent”.

We turn to the details. We will work locally in the ball B(0, δ), and observe that the torus T^{k} is indistinguishable from Euclidean space R^{k} in this region. This allows us to use tools from linear algebra.

We use the greedy algorithm. Let X′w := {xw : x ∈ X′}; these are the multiples of w which lie in B(0, δ), and we have already seen that this set is quite large, |X′w| = |X′| ∼ N. Let v_{1}w be the non-zero element of X′w which is closest to the origin (if there is a tie, choose arbitrarily). Let v_{2}w be the non-zero element of X′w which is linearly independent from v_{1}w and is closest to the origin. Let v_{3}w be the non-zero element of X′w which is linearly independent from v_{1}w and v_{2}w and which is closest to the origin. We continue in this manner until we can go no further; we thus obtain linearly independent vectors v_{1}w, …, v_{k′}w in X′w for some 1 ≤ k′ ≤ k which span X′w. For j = 1, …, k let r_{j} = |v_{j}w| denote the distance from v_{j}w to the origin, thus 0 ≤ r_{1} ≤ r_{2} ≤ … ≤ r_{k′} ≤ δ.

We now use a volume packing argument to get upper bounds on the distances r_{j}. For j = 0, …, k′, let V_{j} denote the span of v_{1}w, …, v_{j}w, thus {0} = V_{0} ⊂ V_{1} ⊂ V_{2} ⊂ … ⊂ V_{k′} form a k′-dimensional complete flag of subspaces. Let π_{j} denote the orthogonal projection onto V_{j}, and consider the “box”

B = {x ∈ V_{k′} : |π_{j+1}(x) − π_{j}(x)| < r_{j}/2k for all 0 ≤ j < k′}.

Note from the triangle inequality that this box is contained in B(0, δ/2). Observe that B cannot contain any multiples of w other than the origin. For, if we had some non-zero multiple vw of w in B, let V_{j} be the first subspace in the flag which contains v_{j}, thus vw is independent of v_{1}, …, v_{j−1}. By the triangle inequality, we would then have

|vw| = |π_{j}(vw)| < r_{1}/2k + … + r_{j}/2k ≤ r_{j},

contradicting the minimality of r_{j}.

If we now let B/2 denote the set {x/2 : x ∈ B}, then by convexity and symmetry we have B/2 − B/2 = B. Thus by the previous discussion, the sets xw + B/2 are disjoint as x varies over X′. Since the sets xw + B/2 lie in the k′-dimensional disk B(0, 2δ) ∩ V_{k′}, and |X′| ∼ N, a volume packing argument thus yields that the k′-dimensional volume of B/2 is O(1/N) (allowing constants to depend in δ and k), so the same applies to B. But a simple computation shows that the k′-dimensional measure of B is comparable to r_{1} … r_{k′}, so we have shown that

r_{1} … r_{k′} ≲ 1/N.  (10)

Now let N_{1}, …, N_{k′} ≥ 1 be positive integers such that N_{j} is the integer part of 1 + \frac{δ}{kr_{j}}. By the previous (and the assumption k = O(1)) we have

N_{1} … N_{k′} ≳ N.

If we let P ⊆ Z/NZ be the generalized arithmetic progression

P := {∑_{j=1}^{k′} n_{j}v_{j} : 0 < n_{j} ≤ N_{j} for all j = 1, …, k′}

then P has volume ≳ N, and by construction we also see that P w ⊆ B(0, δ). Thus P is contained inside X′ and is thus contained inside the Bohr set. Also from linear independence we see that P is proper (note that the linear combinations never leave B(0, δ), so we don’t encounter any wraparound issues arising from the torus, and we are done. This completes the proof of Freiman’s theorem.

(Remark: one can get more precise bounds on r_{1} … r_{k}, by a classical theorem known as Minkowski’s second theorem, but we do not need to do so here.)

8. Some more lattice theory: Proper and improper generalized arithmetic progressions

The main result of this section is the following result of Gowers and Walters:

Theorem 8.1. Let Z be a torsion-free abelian group. Then every generalized arithmetic progression in Z with bounded rank is the refinement of a proper generalized arithmetic progression with equal or lesser rank.

Now observe that any small convolution X + P of a generalized arithmetic progression P of bounded rank d is a refinement of a generalized arithmetic progression of rank d+|X|; indeed, X is clearly contained in a rather small arithmetic progression Q of rank |X| and volume 2^{|X|}, and then X + P is a refinement of the generalized arithmetic progression Q + P. Thus by Lemma 8.1, the small convolution of a proper bounded-rank progression is the refinement of another proper bounded-rank progression. This allows us to remove the “small convolution” caveat in Freiman’s theorem.

The proof I give here is not Gowers and Walters’ original proof (which I haven’t seen), and is probably much clumsier, but it does illustrate some interesting techniques from lattice theory.

Before we prove this theorem, let us recall an algebraic analogue which has a similar flavor.

Lemma 8.2. Let Γ be a lattice in R^{d}, i.e. a discrete additive subgroup. Then there is an invertible linear transformation which transforms Γ to the standard lattice Z^{k} for some 0 ≤ k ≤ d. We call k the rank of the lattice Γ.

If one thinks of finitely generated lattices as the analogue of generalized progressions, and invertible images of the standard lattice as the analogue of proper generalized progressions, then we see that this lemma is in some sense an algebraic analogue of Theorem 8.1.

Proof This result can be proven algebraically (using the fact that every finitely generated torsion-free group is isomorphic to some standard lattice), but we will use an analytic proof, similar in spirit to the Euclidean algorithm (which in fact corresponds to the d = 1 case of this Lemma).

We first observe that we may assume that the vectors in Γ span R^{d}, else we could pass from R^{d} to a smaller vector space and continue the argument. With this assumption, we will show that Γ is in fact isomorphic to Z^{d}.

Since Γ is discrete, there exists some ball B(0, ε) which contains no lattice point in Γ other than the origin. We fix this ε > 0.

By the spanning assumption, we can find d linearly independent vectors v_{1}, …, v_{d} in Γ, so in particular the volume |v_{1} ∧ … ∧ v_{d}| is strictly positive. On the other hand, by Minkowski’s theorem (Exercise 5) we know that this volume is bounded from below by some constant c = c(ε) > 0 depending only on ε.

We now use the method of descent. Let ⟨v_{1}, …, v_{d}⟩ be the lattice consisting of integer combinations of the v_{1}, …, v_{d}. This is a sublattice of Γ. If it is in fact equal to Γ, then Γ is clearly isomorphic to Z^{d} since we can use an invertible transformation to map the linearly independent vectors v_{1}, …, v_{d} to the generators of Z^{d}. Now suppose that the vectors ⟨v_{1}, …, v_{d}⟩ do not generate Γ. Then the halfopen paralleopiped {∑_{i=1}^{d} t_{i}v_{i} : 0 ≤ t_{i} < 1} generated by the vectors v_{1}, …, v_{d}, being a fundamental domain of ⟨v_{1}, …, v_{d}⟩, must contain a lattice point w in Γ which is non-zero. Write w = ∑_{i=1}^{d} t_{i}v_{i}; without loss of generality we may assume that t_{d} > 0. We may also assume that t_{d} ≤ 1/2 since we could replace w by v_{1} +…+v_{d} −w otherwise. Then the volume |v_{1} ∧…∧v_{d−1} ∧w| is at most half that of |v_{1} ∧ … ∧ v_{d}|. We thus replace v_{d} by w and repeat the above argument. Because of our absolute lower bound on the volume of paralleopipeds, this argument must eventually terminate, at which point we have found the desired presentation for Γ.

Call a lattice vector v in Γ irreducible if it is not of the form nw for some integer n > 1 and some w ∈ Γ. Clearly every lattice vector is the integer multiple of an irreducible lattice vector.

One corollary of the above Lemma is that irreducible vectors can always be factored out:

Corollary 8.3. Let Γ be a lattice of rank k, and let w be a non-zero irreducible vector in Γ. Then we have a factorization Γ = ⟨w⟩ + Γ′ where ⟨w⟩ is the space of integer multiples of w, and Γ′ is a lattice of rank k − 1.

Proof By Lemma 8.2 we may take Γ equal to Z^{k}, at which point w takes the form (a_{1}, …, a_{k}) for some integers a_{1}, …, a_{k}. Since v is irreducible, the a_{1}, …, a_{k} have no common factor, and thus we have n_{1}a_{1} + … + n_{k}a_{k} = 1 for some integers n_{1}, …, n_{k}. By use of row operations (which leaves Z^{k} invariant) we may thus assume that w is equal to the basis vector e_{k}. But then the claim follows by setting Γ′ := Z^{k−1}.

We now prove Theorem 8.1. We shall actually prove the following variant, which is clearly equivalent to Theorem 8.1 but is easier to prove for inductive purposes:

Proposition 8.4. Let Z be a torsion-free abelian group, let P be a generalized arithmetic progression in Z of rank k = O(1), and let Q be a generalized arithmetic progression in Z of rank d = O(1) and cardinality |Q| = O(1). Then Q + P is a refinement of a proper generalized arithmetic progression of bounded rank.

Thus we have split our progression into a large progression P and a small progression Q. The reason we do this is that our inductive step will sometimes reduce the rank k of the large progression at the cost of increasing the rank d of the small progression, and then use a different argument to reduce the small rank d while keeping the large rank k constant.

Proof As mentioned above, we will induct on both k and d. We call a pair P′, Q′ of progressions with ranks k′, d′ simpler than P, Q with ranks k, d if k′ < k, or if k′ = k and d′ < d, or if k′ = k and d′ = d and P′ has a smaller volume than P. We may assume inductively that the Proposition has already been proven for all pairs P′, Q′ of progressions which are simpler than P, Q.

The basic idea is to use the fact that an arithmetic progression can be improper only when there is at least one collision between two different sums in the progression. One can then use this collision to reduce the rank of either P or Q without increasing the size of P and Q too much.

First let us look at the case where P is improper; we will aim to use this improperness to drop the rank k of P by one; the small progression Q will make its appearance at the end. We may assume that P has base point 0, i.e.

P := {n · v : n ∈ [0, N]}

for some multivector v ∈ Z^{k} and multinumber N := (N_{1}, …, N_{k}). It will be convenient to rescale by N. If x ∈ R^{k}, let x/N denote the vector

x/N := (x_{1}/N_{1}, …, x_{k}/N_{k}),

and let v′ denote the multivector

v′ := (N_{1}v_{1}, …, N_{k}v_{k}),

thus we have

P = {x · v′ : x ∈ [0, N]/N}.

Since P is improper, we have some x, x′ ∈ [0, N]/N such that x · v′ = x′ · v′. Let ker(v′) ⊆ Z^{k}/N be the lattice

ker(v′) := {x ∈ Z^{k}/N : x · v′ = 0};

we thus see that ker(v′) contains a non-zero vector w ∈ [−N, N]/N, namely w := x − x′. We may of course assume that w is irreducible in ker(v′).

Morally, Corollary 8.3 should now let us replace the rank k lattice Z^{k}/N by one of rank k − 1, but we are not dealing with the infinite lattice here, only a bounded subset of it, and so we have to do a little more work.

Write w = (w_{1}, …, w_{k}). Without loss of generality we may assume that the k^{th} coefficient dominates in the sense that

|w_{j}| ≤ |w_{k}| for j = 1, …, k.  (11)

One should think of this as saying that w is essentially aligned with the e_{k} basis vector. In particular w_{k} is non-zero.

Now suppose that w is small, |w| ≪ 1. Then we can replace P by a progression of the same rank but smaller volume, allowing us to use the induction hypothesis.

Here’s how. Let N′ denote the multinumber

N′ := (kN_{1}, …, kN_{k−1}, N_{k}|w_{k}|).

Observe that for every x ∈ [0, N]/N there exists some integer n such that x − nw lies in [−N′, N′]/N, just by the Euclidean algorithm in the k^{th} co-ordinate. Since x · v′ = (x − nw) · v′, we can thus cover the arithmetic progression P by another progression P′ of the same rank k, but of volume O(|[−N′, N′]|) = O(|w_{k}||[0, N]|). This is smaller if |w| is sufficiently small. Thus in this case one can use the induction hypothesis to close the argument. (Note that P′ can easily be verified to be a small convolution of P, so that P is thus a refinement of P′).

It remains to consider the case when w is never small; i.e. there is a ball B^{k}(0, ε) in R^{k} which contains no lattice point of ker(v′) other than the origin, where ε = ε(k) > 0 depends only on k. This tells us (by volume-packing arguments) that the lattice ker(v′) is fairly sparse; for instance, it can only have a bounded number of elements in the bounded set [−N, N]/N. In particular this implies that

|P | ∼ |[0, N]|.

Define a linear projection π_{w} from R^{k} to R^{k−1} by

π_{w}(x) = x − \frac{x_{k}}{w_{k}} w.

Let Γ ⊆ R^{k−1} denote the lattice Γ := π_{w}(Z^{k}/N); this lattice Γ is discrete (indeed, it lives in the discrete lattice \frac{1}{|w_{k}|N_{1}...N_{k}} Z^{k−1}) and has rank k − 1 (since it contains Z^{k−1}/N). Now, let B(0, C) be a large ball in R^{k−1}. We claim that the set Γ ∩ B(0, C) has O(|[0, N]|) elements and that

P ⊆ (Γ ∩ B(0, C)) · v′.

To verify the latter claim, let x · v′ be any element of P. Since w · v′ = 0, we have x · v′ = π_{w}(x) · v′. But since x ∈ [0, N]/N, a simple computation using (11) shows that π_{w}(x) ∈ Γ ∩ B(0, C) if C is large enough depending on k, and we are done. To prove the former claim, note that Γ consists of elements of the form π_{w}(x) for some x = (x_{1}, …, x_{k}) ∈ Z^{k}. Since π_{w}(w) = 0, we may assume that |x_{k}| < |w_{k}|. But then if π_{w}(x) ∈ B(0, C), one easily sees that |x| ≲ 1. Since x also lies in Z^{k}/N, the claim follows.

Since Γ ∩ B(0, C) has O(|[0, N]|) elements, we see by volume packing arguments (noting that Γ contains Z^{k−1} and so we can start tiling all of R^{k−1} with integer translates of B(0, C)) that

|R^{k−1}/Γ| ≳ 1/|[0, N]|.  (12)

The plan is to replace the progression P by the slightly larger object (Γ∩B(0, C))·v′, which has rank k − 1. The trouble is that we have not yet demonstrated that Γ ∩ B(0, C) is an arithmetic progression. We already know that Γ is a lattice of rank k −1, and hence by Lemma 8.2 can be generated by k −1 linearly independent lattice vectors. In principle, this allows us to cover Γ ∩ B(0, C) by an arithmetic progression of rank k −1, but if the parallelopiped generated by these vectors is too degenerate then this progression will be very inefficient (it will require many more points than |[0, N]|, and so we will no longer be able to use the induction hypothesis since the old progression P will not be a refinement of the new one). So we need a way to obtain a non-degenerate parallelopiped in Γ. Fortunately we can re-use the algorithm from the previous section. Let u^{1} be a non-zero vector in Γ of minimal length; let u^{2} be a non-zero vector linearly independent of u^{1} with minimal length subject to these constraints; and so forth up to u^{k−1} (we must get k − 1 vectors this way because Γ spans R^{k−1}. By repeating the volume packing argument used to prove (10) in the last section, we have that

|u^{1}| … |u^{k−1}| ∼ |R^{k−1}/Γ|.  (13)

In particular, this implies that the vectors u^{1}, …, u^{k−1} are not very degenerate:

|R^{k−1}/Γ| ≤ |u^{1} ∧ … ∧ u^{k−1}| ≤ |u^{1}| … |u^{k−1}| ≲ |R^{k−1}/Γ|.  (14)

Also by the greedy nature of the construction, and the fact that Γ contains Z^{k−1}/N, we see that the vectors u^{i} are all bounded.

Let U be the sublattice Γ generated by the linearly independent vectors u^{1}, …, u^{k−1}. By (14) we see that U has bounded index:

|Γ/U| ≲ 1.

In particular Γ is a small convolution of U, and Γ ∩ B(0, C) is a small convolution of U ∩ B(0, 2C).

Let x be any element of U ∩ B(0, 2C). Since x ∈ U, we have

x = ∑_{i=1}^{k−1} n_{i}u^{i}

for some integers n_{i}. These integers can be computed by Cramer’s rule:

n_{i} = \frac{u^{1} ∧ … ∧ u^{i−1} ∧ x ∧ u^{i+1} ∧ … ∧ u^{k−1}}{u^{1} ∧ … ∧ u^{k−1}}

where the quotient of two (k−1)-forms in R^{k−1} is defined in the obvious manner. By (14) we thus have n_{i} = O(1/|u^{i}|). Thus U ∩B(0, 2C), and hence (U ∩B(0, 2C))·v′, is contained in an arithmetic progression of rank k − 1 and size

[⌊C/|w_{1}|⌋, …, ⌊C/|w_{k−1}|⌋]

which thus has volume

≲ \frac{1}{|w_{1}| … |w_{k−1}|} ≲ \frac{1}{|R^{k−1}/Γ|} ≲ |[0, N]|

by (14) and (12).

To summarize, we have covered the arithmetic progression P, which has rank k and cardinality |P | ∼ |[0, N]|, by a small convolution of another arithmetic progression - call it P′ - which has rank k − 1 and volume O(|[0, N]|). Since every small set can be contained in a small arithmetic progression, we thus see that P is a refinement of Q′ + P′ for some small arithmetic progression Q′. We now apply the induction hypothesis, replacing P by P′ (thus reducing the rank of P) and adding Q′ to Q (this increases the rank of Q, but we still have a simpler pair of progressions by definition) to get what we want. This concludes the induction when P is improper.

Now we look at the case when P is proper; the idea is now to work with Q in much the same way that P was worked on in the previous argument.

If Q + P is already proper, then we are done. So suppose Q + P is improper; we thus have q, q′ ∈ Q and p, p′ ∈ P such that q + p = q′ + p′. Since P is already proper, we have q ≠ q′.

By translation symmetry we may assume Q has base point 0, so

Q := {a + m · y : m ∈ [0, M]}

for some multivector y ∈ Z^{d}, and some multinumber M of rank d; since Q is small, M is bounded. Since we have q − q′ ∈ P − P, we thus have m · y ∈ P − P for some m ∈ [−M, M]. We can write m = cm′ where m′ is irreducible in Z^{d}, and c = O(1) is non-zero. Then m′ · v ∈ (P − P)/c.

By Corollary 8.3, Z^{d} is the direct sum of a lattice of rank d − 1, and the integer multiples ⟨m′⟩ of m′. Since M is small, we can thus cover Q by Q′ + [−C, C]m′ · v for some small arithmetic progression Q′ of rank d − 1, and some bounded constant C. Thus we have

Q + P ⊆ Q′ + ( ⋃_{|r|≤C} \frac{r}{c} (P − P) + P).

But one can easily verify that (⋃_{|r|≤C} \frac{r}{c} (P − P) + P) is contained in a progression P′ of the same rank as P and of comparable volume. Thus Q + P is a refinement of the simpler pair of progressions Q′ + P′, and we can use the induction hypothesis again. This closes the induction.

9. Disassociated sets, and Chang’s refinement of Freiman’s theorem

In previous sections we have proven Freiman’s theorem, which states that if |A + A| ≤ K|A| then A is a refined small convolution of an arithmetic progression P of dimension d at most d ≤ C_{K}, where the constants of the refinement and small convolution are at most C′_{K}. However, the estimates we have for the dimension d are pretty bad; our bound for C_{K} is essentially the same as |Λ|, which is as large as K^{C}, while the bound for C′_{K} is exponential in the dimension and thus looks like exp(CK^{C}).

Recently, Chang [1] has refined the dimension bound from K^{C} to CK log K (which is close to the optimal conjecture of CK), with a corresponding improvement of the C′_{K} constant to exp(CK(log K)^{2}). The idea is to use more information about the resonant set Λ than just merely bounding the size |Λ| as in (7).

Let us recall our situation. We are working in a cyclic group Z/NZ, and have a subset A of Z/NZ of size |A| = cN, and we consider the resonant set

Λ := {ξ ∈ Z/NZ : |χ̂_{A}(ξ)| ≥ αc}

for some 0 < α < 1 (in the previous applications, we had α := 1/(2\sqrt{K})). Then the Plancherel identity

∑_{ξ∈Z/NZ} |χ̂_{A}|^{2} = c

gives the cardinality bound

|Λ| ≤ α^{−2}c^{−1}.

This bound is fairly sharp (see for instance Q4). However, we can do a bit better.

Definition 9.1. A cube of dimension d is a generalized arithmetic progression of dimension d, base point equal to 0, and all lengths N_{1}, …, N_{d} equal to 1; in other words, a cube is a set of the form

{∑_{i=1}^{d} ϵ_{i}v_{i} : ϵ_{i} = 0, 1}

for some basis vectors v_{1}, …, v_{d}. Alternatively, a cube is any linear image of [0, 1]^{d}.

Theorem 9.2. [1] With the above notation, Λ is contained in a cube of dimension O(α^{−2} log(1/c)).

This result is especially impressive in the case α ∼ 1 and c ≪ 1. Then the set Λ has cardinality O(1/c), but here we are saying a much stronger statement, that Λ is in fact contained in a cube of dimension O(log(1/c)). (In the context of Q6, this implies that any subgroup of cardinality c is contained in a cube of dimension O(log(1/c)), which is a true but not entirely obvious statement. To get some idea of what’s going on, observe that the set {1, 2, …, N} is contained in the cube with basis vectors 2^{0}, 2^{1}, …, 2^{⌊log_{2} N⌋}).

To prove this theorem we need a definition.

Definition 9.3. A set ξ_{1}, ξ_{2}, …, ξ_{n} of frequencies is said to be dissociated if the cube

{∑_{i=1}^{d} ϵ_{i}ξ_{i} : ϵ_{i} = 0, 1}

is proper. Equivalently, the only solution to

∑_{i=1}^{d} ϵ_{i}ξ_{i} = 0; ϵ_{i} ∈ {−1, 0, 1}

occurs when all the ϵ_{i} are equal to zero.

A key example to keep in mind here is when ξ_{j} = 2^{j}. The intuition then is that dissociated frequencies behave much like lacunary frequencies.

To prove Theorem 9.2, it will suffice to show Proposition 9.4. With the above notation, any dissociated set ξ_{1}, ξ_{2}, …, ξ_{n} in Λ can have cardinality at most O(α^{−2} log(1/c)).

Let us see why Proposition 9.4 implies Theorem 9.2. Let ξ_{1}, …, ξ_{n} be a maximal dissociated set in Λ. Then any other frequency ξ in Λ must be of the form

ξ = ∑_{i=1}^{n} ϵ_{i}ξ_{i}

for some ϵ_{i} ∈ {−1, 0, 1}, since otherwise we could add ξ to our dissociated set and contradict maximality. But this means that all vectors ξ in Λ are contained in the cube with basis vectors ±ξ_{1}, …, ±ξ_{n}, and we are done.

We now prove the Proposition. First we observe that we can replace Λ by the slight variant

Λ_{θ} := \{ξ ∈ Z/NZ : Ree^{iθ}χ̂_{A}(ξ) ≥ \frac{1}{2}αc\}.

Since one can cover Λ by a finite number of the Λ_{θ}, it suffices to prove the claim for a single Λ_{θ}.

Fix θ, and consider the normalized exponential sum

f(x) := \frac{e^{−iθ}}{\sqrt{n}} ∑_{j=1}^{n} e^{2πiξ_{j}x/n}.

From Plancherel’s theorem, we see that this function is normalized in L^{2}:

∥f∥_{L^{2}(Z/NZ;dx)} = 1.

Also from Parseval’s inequality, we know that f has a large inner product with χ_{A}:

⟨f, χ_{A}⟩_{L^{2}(Z/NZ;dx)} = \frac{1}{\sqrt{n}} ∑_{j=1}^{n} e^{−iθ}\overline{χ̂_{A}(ξ_{j})},

and hence by construction of Λ_{θ}

Re\frac{1}{N} ∑_{x∈A} f(x) ≳ \frac{1}{\sqrt{n}}nαc,

or equivalently

\frac{1}{|A|} ∑_{x∈A} Ref(x) ≳ \sqrt{n}α.

Our aim is to show that n = O(α^{−2} log(1/c)). If this is not true, then \sqrt{n}α ≫ log(1/c)^{1/2}, and hence we have

\frac{1}{|A|} ∑_{x∈A} Ref(x) ≫ log(1/c)^{1/2}.  (15)

Thus while f is L^{2} normalized, its average on the subset A of Z/NZ is somewhat large. If we just use the L^{2} bound, we cannot get a contradiction, because the hypothesis |A| = cN combined with the L^{2} normalization only allows us to bound the left-hand side of (15) by O(c^{−1/2}) (how? use Cauchy-Schwarz). Fortunately, we can take advantage of the dissociativity to improve our bounds on f. The point is that f is composed of dissociated frequencies, which should act in a largely independent manner, and so we expect a “large deviation estimate” or “law of large numbers” that says that the magnitude of f does not fluctuate very much, and indeed we expect exponential decay estimates for the set where f is very large (this is where the log is eventually going to come from). Specifically, we have

Lemma 9.5. In the above notation, we have

∫_{Z/NZ} e^{Ref(x)} dx ≲ 1.

Proof The presence of the exponential is a familiar one when dealing with a sum of “independent” quantities, since the exponential converts this to a product of independent quantities, at which point one can exploit the independence.

Since

Ref(x) = n^{−1/2} ∑_{j=1}^{n} cos(2πξ_{j}x/n − θ)

we have

e^{Ref(x)} = ∏_{j=1}^{n} e^{n^{−1/2} cos(2πiξ_{j}x/n−θ)}.

Now we estimate the exponential by a Taylor expansion:

e^{n^{−1/2} cos(2πiξ_{j}x/n−θ)} ≤ 1 + n^{−1/2} cos(2πiξ_{j}x/n − θ) + O(n^{−1}).

Since (1 + O(n^{−1}))^{n} = O(1), we thus have

e^{Ref(x)} ≲ ∏_{j=1}^{n}(1 + n^{−1/2} cos(2πiξ_{j}x/n − θ)),

which we split using exponentials as

e^{Ref(x)} ≲ ∏_{j=1}^{n}(1 + \frac{1}{2}n^{−1/2}e^{−iθ}e^{2πiξ_{j}x/n} + \frac{1}{2}n^{−1/2}e^{iθ}e^{−2πiξ_{j}x/n}).

Now we multiply this out. The right-hand side contains a 1, plus a whole bunch of multiples of plane waves e^{2πiξx/n} for various values of ξ. However, since the ξ_{j} are dissociated, none of those plane waves are constant. Thus if we sum in x, they all cancel, and we obtain

∫_{Z/NZ} e^{Ref(x)} dx ≲ 1

as desired. □

From this Lemma and the Jensen inequality

exp(\frac{1}{|A|} ∑_{x∈A} Ref(x)) ≤ \frac{1}{|A|} ∑_{x∈A} e^{Ref(x)}

we obtain the desired contradiction to (15), since |A| = cN, and Proposition 9.4 follows.

10. Exercises

• Q1. Let G be a subgroup of an abelian group Z, and let ϕ : G → G′ be a Freiman homomorphism of order 2 from G to some subset G′ of another abelian group Z′. Show that G′ is the translate of some subgroup of Z′. (Hint: first normalize so that ϕ(0) = 0).

• Q2. Let P be a proper generalized arithmetic progression, and let ϕ : P → ϕ(P) be a Freiman homomorphism of order 2 from P to some subset ϕ(P) of an abelian group Z. Show that ϕ(P) is a generalized arithmetic progression of the same length as P, and furthermore that ϕ(P) is proper if ϕ is injective. (Hint: This is a very similar argument to Q1. First normalize so that P is a box and ϕ(0) = 0).

• Q3. Verify all the unproved claims in Section 6.

• Q4. Let A be a subset of a finite abelian group Z with |A| = c|Z| and |A + A| = |A|, and let e(x, ξ) be a fixed bi-character used to define the Fourier transform. Show that there is a set Λ ⊆ Z of size |Λ| = c^{−1} such that |χ̂_{A}| = cχ_{Λ}; thus one has perfect concentration of the Fourier transform in a small set. Contrast this with the computations in Section 6. Show in addition that Λ is a subgroup of Z.

• Q5. Let Λ be a lattice (i.e. a discrete additive subgroup) of R^{d} whose quotient space R^{d}/Λ has finite volume. (A typical example is Z^{d}). Let K be a convex bounded subset of R^{d} which is symmetric around the origin, and such that |K| > 2^{d}R^{d}/Λ. Show that K must contain a lattice point in Λ other than the origin. (This is Minkowski’s first theorem. Hint: adapt some of the arguments in Section 7). Give an example to show that the constant 2^{d} in the above theorem cannot be improved.

• Q6*. Prove (13) by doing a volume packing argument on the quotient space R^{d}/Γ. (It is possible to compute a sharp constant in (13) - in fact, it is 2^{d}/|B(0, 1)| - and the claim in fact holds for all possible norms on R^{d}, not just the Euclidean one. This statement is known as Minkowski’s second theorem, but we will not prove it here).

• Q7 (a). Let a_{1}, …, a_{N} be a square-summable sequence of positive reals:

∑_{j=1}^{N} a_{j}^{2} ≤ 1.

For any λ > 0, prove the bound

P (| ∑_{j=1}^{N} ε_{j}a_{j}| > λ) ≲ e^{−cλ^{2}}

for some absolute constant c > 0, where the ε_{j} = ±1 are independent, identically distributed unbiased random signs, and P denotes the probability of an event. (Hint: compute the expectation of exp(t ∑_{j=1}^{N} ε_{j}a_{j}) for any parameter t > 0, in the spirit of Lemma 9.5.) This is of course a special case of the law of large numbers.

• Q7(b) Under the same assumptions on a_{i}, prove Zygmund’s inequality

|{θ ∈ [0, 2π] : | ∑_{j=1}^{N} a_{j}e^{2πi2^{j}θ}| > λ}| ≲ e^{−cλ^{2}}

for any λ > 0. (In fact, one can replace the frequencies 2^{j} by any other dissociated set).

References

[1] M. Chang,A polynomial bound in Freiman’s theorem, Duke Math. J. 113 (2002), no. 3, 399– 419.

[2] G. Freiman, Structure theory of set addition, Asterisque 258 (1999), 1–33.

[3] B. Green, Edinburgh lecture notes on Freiman’s theorem, preprint.

[4] I. Ruzsa, An analog of Freiman’s theorem in groups, Structure theory of set addition, Astérisque No. 258 (1999), 323–326.

Department of Mathematics, UCLA, Los Angeles CA 90095-1555

E-mail address: tao@math.ucla.edu