Additive Number Theory Examples Sheet 3. W. T. G.

1. (i) Deduce the following extension of Roth’s theorem from Ruzsa’s lemma (and Plünnecke’s inequality). For every C there exists n such that, if A ⊂ ℤ, |A| ⩾ n and |A + A| ⩽ C|A|, then A contains an arithmetic progression of length three.

(ii) Using the Balog-Szemerédi theorem, deduce a further extension.

2. Let A ⊂ ℤ_{N}. Define a k-cube in A to be a mapping ϕ : {0, 1}^{k} → ℤ_{N} of the form ϕ(ϵ) = x_{0} + ∑_{i=1}^{k} ϵ_{i}x_{i}, where x_{0}, x_{1}, …, x_{k} belong to ℤ_{N} and the image of ϕ lies in A. (For example, a 2-cube can be thought of as a quadruple (a, a + b, a + c, a + b + c) ∈ A^{4}.)

(i) Let A have size δN. Prove that A contains at least δ^{2^{k}}N^{k+1} k-cubes.

(ii) Suppose that A is quadratically α-uniform. Prove that A contains at most (δ^{8} + c(α))N^{4} 3-cubes, where c(α) tends to zero as α tends to zero.

3. Obtain a decent lower bound (without appealing to the geometry of numbers) for the size of the Bohr neighbourhood B(r_{1}, …, r_{k}; δ).

4. Let A be a subset of ℤ_{N} of cardinality δN. Prove that A+A+A contains an arithmetic progression (mod N) of length N^{c}, where c depends on δ only. Give an example of a set A such that the longest arithmetic progression in A + A + A has length N^{c′} for some c′ that tends to zero with δ. (You ought to be able to get c proportional to δ^{2} and c′ proportional to log(1/δ). Closing the gap between these two bounds is an important open problem.)

5. (Hard - in fact, probably an unsolved problem.) Let ϵ > 0, let N be prime and let A and B be subsets of ℤ_{N} of size ⌈N/2⌉. If N is large enough (as a function of ϵ), prove that there exists some x ∈ ℤ_{N} such that A ∩ (B + x) has cardinality between (\frac{1}{4} − ϵ)N and (\frac{1}{4} + ϵ)N. What can go wrong if N is not prime?

6. Let f be an increasing function. Obtain an estimate for |∑_{x⩽n} f(x)e(αx + β)| under the assumption that (a, q) = 1 and |α − a/q| ⩽ q^{−2}.

7. By carrying out the following steps, prove that the subset A = {x : |x^{2}| ⩽ N/10000} of ℤ_{N} discussed in lectures satisfies max_{r≠0} |Â(r)| = O(\sqrt{N} log N).

(i) Prove that if f(x) = ω^{ax^{2}} then |f̂(r)| = \sqrt{N} for every r.

(ii) Set M = ⌊N/10000⌋, let I = [−M, M] and notice that A(x) = I(x^{2}) for every x. Use the inversion formula to write an expression for A(x) in terms of the Fourier coefficients of I.

(iii) Finish off by using (i) and a simple estimate for the sizes of the Fourier coefficients of I.

8. Prove also that A contains significantly more than 10^{−16}N^{2} arithmetic progressions (in ℤ_{N}) of length four. (You should find 7(ii) helpful here as well.)

9. Let A be a subset of I = {x ∈ ℤ : |x| ⩽ n} of cardinality δN. Prove that there is a constant k, depending on δ only, such that kA − kA contains the whole of I. (I’m not quite sure how to do this question but I know it’s known.)

10. Show that there are constants 0 < β < α^{3} ⩽ 1 such that, for infinitely many N, ℤ_{N} contains a set of size αN with at most βN^{2} triples of the form (a, a + d, a + 2d) (mod N).

11. Let A ⊂ ℕ. Suppose that

∀α ∈ ℝ ∀ϵ > 0 ∃q ∈ A ∥qα∥ ⩽ ϵ .

Prove that

∀ϵ > 0 ∃N ∈ ℕ ∀α ∈ ℝ ∃q ⩽ N ∥qα∥ ⩽ ϵ .

(That is, obtain a result which is uniform over α.)