Part III Quasirandomness Examples Sheet 1. W. T. G.

1. Prove that for every a > 0 there exists c > 0 with the following property. Whenever A_{1}, …, A_{m} is a collection of subsets of {1, 2, …, n} such that ||A_{i}| − n/2| ⩽ cn for every i and ||A_{i} ∩ A_{j}| − n/4| ⩽ cn for all but at most cm^{2} pairs (i, j) then it is also the case that ||A_{i} ∩ A_{j} ∩ A_{k}| − n/8| ⩽ an for all but at most am^{3} triples (i, j, k). [You may quote results from the course if that helps.]

2. Prove that for every a > 0 there exists c > 0 with the following property. Let X and Y be sets of sizes m and n, respectively. Let f : X × Y → [−1, 1] be a function such that ∑_{x}(∑_{y} f(x, y))^{2} ⩽ cmn^{2} and ∑_{y}(∑_{x} f(x, y))^{2} ⩽ cm^{2}n. Then for any functions u, v : X × Y → [−1, 1] we have the inequality

| ∑_{x,x′∈X} ∑_{y,y′∈Y} u(x, y)f(x, y′)v(x′, y)| ⩽ am^{2}n^{2} .

Explain why this result can be used to shorten the proof in the notes that if a bipartite graph G has few 4-cycles then the “sum over rectangles” of the corresponding function f is small.

3. Let G be a graph with vertex set X of size n and with p\binom{n}{2} edges . Prove that the following two statements are equivalent, in the sense of the lectures.

(i) For any two sets A, B ⊂ X the number of pairs (x, y) ∈ A × B such that xy is an edge of G differs from p|A||B| by at most cn^{2}.

(ii) For any set A ⊂ X the number of edges spanned by the set A differs from p\binom{|A|}{2} by at most c′n^{2}.

4. Let u, v, w and x be vectors in ℝ^{n}. Write out a concise expression for the composition of the linear maps (or product of the matrices) u ⊗ v and w ⊗ x.

5. Let A(x, y) be a real symmetric n × n matrix. Prove that if u is a unit vector that maximizes the sum ∑_{x,y} A(x, y)u(x)u(y) then u is an eigenvector with the largest possible eigenvalue.

6. Let A(x, y) be a real matrix, but not necessarily symmetric this time. Suppose that u and v are unit vectors such that ∑_{x,y} A(x, y)u(x)v(y) is maximized. Show that Av = λu for some constant λ. Let B(x, y) = A(x, y) − λu(x)v(y). Prove that ⟨Bw, v⟩ = 0 for every vector w. By using these facts, or otherwise, show that A can be written as a sum ∑_{i=1}^{n} λ_{i}u_{i}(x)v_{i}(y), with both the u_{i} and v_{i} forming orthonormal bases. Prove that the u_{i} and v_{j} are eigenvectors of the matrices A^{T} A and AA^{T}, respectively. What are the corresponding eigenvalues? [Warning: I could have made mistakes in the details of this question, but if any of the statements are false then find modified statements that are true and prove them. To a lesser extent, this applies to the whole sheet.]

7. In lectures we proved the homomorphisms version of the counting lemma. Prove the version that deals with isomorphic embeddings.

8. Prove that there is a function f : {1, 2, …, n}^{2} → {−1, 1} such that ∑_{x,x′} ∑_{y,y′} f(x, y)f(x, y′)f(x′, y)f(x′, y′) ⩽ Cn^{3} for some absolute constant C. [Hint: choose f randomly.]

9. Let p be a prime of the form 4n + 3 and let ℤ_{p} stand for the set of integers mod p. Define a function f : ℤ_{p}^{2} → {−1, 1} by setting f(x, y) = 1 if y − x is a quadratic residue, and f(x, y) = −1 otherwise. Prove that ∑_{x,x′} ∑_{y,y′} f(x, y)f(x, y′)f(x′, y)f(x′, y′) ⩽ Cn^{3} for some absolute constant C. [NB: the hint in the previous question was compulsory!]

10.  Let f : {1, 2, …, n}^{2} → {−1, 1} be any function.  Prove that

∑_{x,x′} ∑_{y,y′} f(x, y)f(x, y′)f(x′, y)f(x′, y′) ⩾ n^{3}.

11. Let H be a graph with k vertices, which we think of as fixed and small. Prove that for every a > 0 there exists c > 0 such that if at most cn^{k} functions from V (H) to V (G) are homomorphisms, then it is possible to remove at most an^{2} edges from G in such a way that G no longer contains any copies of H.

12. (A proof of the Erdős-Stone theorem.) Let H be a fixed graph, as above. Write ex(n, H) for the largest density of any graph with n vertices that does not contain any copy of H. Turán’s theorem implies that if H is the complete graph on k vertices (and if n is a multiple of k − 1) then ex(n, H) = 1 − 1/(k − 1). Suppose now that the chromatic number of H is r. Prove that the limit of ex(n, H) as n tends to ∞ is 1 − 1/(r − 1). [Hint: Let G be an extremal graph. Remove a few edges from G in such a way that if the resulting graph contains a K_{r} then it also contains several copies of H. Most of the work is contained in the previous question.]

13. Let A be a subset of {1, 2, …, n}^{2} of cardinality at least δn^{2}. Prove that there exists some pair (u, v) ∈ ℕ^{2} such that A ∩ ((u, v) − A) = {(a, b) ∈ A : (u − a, v − b) ∈ A} has cardinality at least cδn^{2} for some absolute constant c > 0. Deduce that the theorem about corners can be strengthened so that it guarantees that A contains a triple (x, y), (x, y + d), (x + d, y) with d > 0.

14. Let A be a subset of ℤ_{N} and define a graph G(A) with vertex set ℤ_{N} by joining x to y if and only if x + y ∈ A. By considering 4-cycles in G, prove that G is c-quasirandom if and only if A is c-uniform. It follows that the sum of the fourth powers of the eigenvalues of G is the sum of the fourth powers of the Fourier coefficients of A. Can you prove this more directly?

15. Let A, B, C, D be four subsets of ℤ of size N. Suppose that there are αN^{3} quadruples (a, b, c, d) ∈ A × B × C × D such that a + b = c + d. Prove that there are at least αN^{3} quadruples (a, b, c, d) ∈ A^{4} with a + b = c + d.

16. Suppose that A has size N and contains at least αN^{2} arithmetic progressions of length 3. Prove that there are at least αN^{3} quadruples (a, b, c, d) ∈ A^{4} with a + b = c + d.

17. Let A be a subset of ℤ_{N} of size at most (1/20) log N. Prove that there exists r ≠ 0 such that |Â(r)| ⩾ |A|/2.

18. Let N be a prime, let P be an arithmetic progression mod N, and let A be the set of all x ∈ ℤ_{N} such that x^{2} ∈ P. Let |P | = δN.

(i) Prove that for every r ≠ 0 the Fourier coefficient Â(r) has modulus at most C log N\sqrt{N} for some absolute constant C. [Hint: A(x) = P (x^{2}). Now split up P into a sum of trigonometric functions.]

(ii) Prove that the cardinality of A is approximately equal to δN, and give an estimate for the error. [Again, write A as above and use the alternative expression to estimate ∑ |A(x)|^{2}.]

(iii) Show also that if P, Q and R are progressions mod N, then the number of pairs (x, d) such that x^{2} ∈ P, (x + d)^{2} ∈ Q and (x + 2d)^{2} ∈ R is approximately |P ||Q||R|N^{−1}, and again give an estimate for the error.

(iv) Prove that the number of progressions of length 4 in A is at least cδ^{3}N^{2}, for some absolute constant c > 0.

Remarks, corrections, comments to wtg10@dpmms.cam.ac.uk.