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

1. Let k be a real number. Prove that there exist an integer N and a subset A ⊂ ℤ_{N} of size δN (say) such that |Â(r)| ⩽ δN/k whenever r ≠ 0, and such that the convolution A ∗ A is not approximately constant. (This means that there is some absolute constant η > 0 such that |A ∗ A(x) − δ^{2}N| ⩾ ηδ^{2}N for at least ηN values of x.) What relationship must hold between k and δ for this to be possible?

2. Let B = {e_{1}, …, e_{m}} be a basis for an m-dimensional vector space. Prove that |nB| = \binom{m+n−1}{n}.

3. Let G be a Plünnecke graph with vertex set V_{0} ∪ V_{1} ∪ … ∪ V_{n}. Suppose that |V_{0}| = 1, |V_{1}| = m and that the vertex in V_{0} is joined to every vertex in V_{1}. Assume first that n = 2, and prove that |V_{n}| ⩽ \binom{m+n−1}{n}, with equality if and only if G is isomorphic to the graph defined in lectures with vertex set {0} ∪ B ∪ … ∪ nB. Is this result true for n > 2? [I have only recently thought of this question and do not know the answer to the last part. If the answer is yes then it seems hardish but shouldn’t be impossible.]

4. Let Λ be a lattice, let K be a centrally symmetric convex body and let λ_{1}, …, λ_{n} be the successive minima of K with respect to Λ. Is it necessarily possible to choose a basis b_{1}, …, b_{n} of Λ (as opposed to ℝ^{n}) such that b_{i} ∈ λ_{i}\overline{K} for every i?

5. In the proof of Minkowski’s second theorem, why would it not be possible to replace the map ϕ by the simpler map ∑_{i=1}^{n} x_{i}b_{i} ↦ ∑_{i=1}^{n} λ_{i}x_{i}b_{i}?

6. Let Λ be a lattice and let K be a centrally symmetric convex body. Define a grid to be a set of the form {∑_{i=1}^{n} a_{i}x_{i} : r_{i} ⩽ a_{i} ⩽ s_{i}}, where x_{1}, …, x_{n} are independent vectors in Λ. Prove that K contains a grid of cardinality c|K|/ det Λ, where c is a constant depending on n only, and |K| stands for the volume of K.

7. Let G ⊂ ℝ^{n} be a discrete subgroup (meaning that there is a neighbourhood of zero with no non-zero point of G in it) containing n linearly independent vectors. Prove that G is a lattice. Prove the converse (which is easier).

8. Let P be the arithmetic progression (a, a + d, …, a + (m − 1)d). Map P to ℤ as follows. First multiply everything by r. Then map to ℤ_{N} via the usual quotient map from ℤ, where N > m^{2} (this condition is not very important) is prime and r is not a multiple of N. Finally, embed into ℤ in the usual way. Show that the image of P under this map is contained in a two-dimensional arithmetic progression of size at most C|P |, where C is an absolute constant.

9. (Easier Waring’s problem.) Prove that for every k there is a constant C = C(k) such that every integer can be written as ±x_{1}^{k} ± … ± x_{m}^{k} with m ⩽ C. [Hint: think about the proof of Weyl’s inequality.]

10. A set A of integers is called a Sidon set if no integer can be written in more than one way as a + b with a, b ∈ A, a ⩽ b. Show that there is a constant c > 0 such that, for every N, the set \{1, 2, …, N\} has a subset of size at least c\sqrt{N} which is a Sidon set. [Hint: consider the set of points of the form (x, x^{2}) in ℤ_{p}^{2}.]

11. Show that for every C there is a centrally symmetric convex body in ℝ^{2} of area at least 1/100 and diameter at least C which contains no non-zero points in ℤ^{2}.

12. Check the following simple facts, some of which I assumed in lectures.

(i) For every pair of positive integers k and d, every finite subset of ℤ^{d} is isomorphic of order k to a subset of ℤ.

(ii) The composition of two homomorphisms/isomorphisms of order k is a homomorphism/isomorphism of order k.

(iii) ϕ : A → B is an isomorphism of order k if and only if ϕ induces a bijection (in the obvious way) between kA and kB.

(iv) If I = {x ∈ ℤ_{p} : (j − 1)p/k ⩽ x < jp/k}, then the “identity map” from I to ℤ is an isomorphism of order k.

(v) If A is a d-dimensional arithmetic progression and B is isomorphic (of order 2) to A, then B is a d-dimensional arithmetic progression.

(vi) If A and B are finite subsets of ℤ and A is isomorphic of order k to B for every k, then there exist integers a ≠ 0 and b such that the map x ↦ ax + b is a bijection from A to B.

(vii) If A is isomorphic of order rs to B and k + l = r, then kA − lA is isomorphic of order s to kB − lB.

(viii) If A is a proper d-dimensional arithmetic progression, then |rA − sA| ⩽ (r + s)^{d}|A|.

(ix) If A is a proper d-dimensional arithmetic progression, then A − A is contained in a union of 2^{d} translates of A.

(x) A d-dimensional arithmetic progression of cardinality n contains a one-dimensional arithmetic progression of cardinality at least n^{1/d}.

13. Disprove the following statement. There exists an absolute constant B such that, whenever A is a finite subset of ℤ with |A + A| ⩽ C|A|, we also have |A − A| ⩽ BC|A|. [I think it is possible to prove an upper bound of the form C^{α}|A| for some α < 2, but this is quite a bit harder.]

14. Prove that if B ⊂ {1, 2, …, n} is a set of cardinality at least 99n/100 and ϕ : B → ℤ is a homomorphism, then ϕ is an affine map.

15. Let X be a subset of size n of an abelian group G. Suppose that X^{4} contains at least 99n^{3}/100 quadruples (a, b, c, d) such that a + b = c + d. Prove that X is contained in a coset of a subgroup of G of size at most 11n/10. (These numbers are off the top of my head, and therefore unnecessarily generous.)

16. For the following two unitary maps from ℂ^{ℤ_{N}} to ℂ^{ℤ_{N}}, find an orthonormal basis of eigenvectors and calculate the corresponding eigenvalues.

(i) f ↦ g, where g(x) = f(x − 1).

(ii) f ↦ N^{−1/2}f̂.

Comments/corrections to wtg10@dpmms.