Authors Timothy Gowers, Oliver Janzer,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29
www.theoryofcomputing.org
Subsets of Cayley Graphs
That Induce Many Edges
Timothy Gowers∗ Oliver Janzer†
Received October 24, 2018; Revised October 6, 2019; Published December 22, 2019
Abstract: Let G be a regular graph of degree d and let A ⊂ V (G). Say that A is η-closed if
the average degree of the subgraph induced by A is at least ηd. This says that if we choose a
random vertex x ∈ A and a random neighbour y of x, then the probability that y ∈ A is at least
η. This paper was motivated by an attempt to obtain a qualitative description of closed subsets
of the Cayley graph Γ whose vertex set is Fn21 ⊗ · · · ⊗ Fn2d with two vertices joined by an edge
if their difference is of the form u1 ⊗ · · · ⊗ ud . For the matrix case (that is, when d = 2), such
a description was obtained by Khot, Minzer and Safra, a breakthrough that completed the
proof of the 2-to-2 conjecture. In this paper, we formulate a conjecture for higher dimensions,
and prove it in an important special case. Also, we identify a statement about η-closed sets
in Cayley graphs on arbitrary finite Abelian groups that implies the conjecture and can be
considered as a “highly asymmetric Balog–Szemerédi–Gowers theorem” when it holds. We
conclude the paper by showing that this statement is not true for an arbitrary Cayley graph.
It remains to decide whether the statement can be proved for the Cayley graph Γ.
ACM Classification: G.2.1
AMS Classification: 68R05, 15A69
Key words and phrases: Unique Games Conjecture, tensors, Cayley graphs
∗ Supported by a Royal Society 2010 Anniversary Research Professorship. He also held a Research Chair of the Fondation
Sciences Mathématiques de Paris while this research was carried out.
† Supported by the Fondation Sciences Mathématiques de Paris while part of this research was carried out.
© 2019 Timothy Gowers and Oliver Janzer
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2019.v015a020
T IMOTHY G OWERS AND O LIVER JANZER
1 Introduction
The Unique Games Conjecture, formulated by Khot [6] in 2002, is a central conjecture in theoretical
computer science. If true, it implies that for a wide class of natural problems it is NP-hard to find even a
very crude approximate solution in polynomial time. Recently, a weakening of the conjecture known as
the 2-to-2 Games Conjecture, where the approximation is required to be less crude (so it is easier to prove
hardness) was proved by Khot, Minzer and Safra [7], a result that is considered as a major step towards
the Unique Games Conjecture itself. More precisely, after work by various authors, the problem had been
reduced to a statement about a certain Cayley graph, and Khot, Minzer and Safra proved that statement.
The Cayley graph Γ in question has as its vertex set the set of all m × n matrices over F2 , with two
vertices joined by an edge if their difference has rank 1. Let us say that a subset A ⊂ Mm,n (F2 ) is η-closed
if the probability that A + B ∈ A, when A is chosen uniformly from A and B is chosen uniformly from all
rank-1 matrices, is at least η. In graph terms, this is the probability that a random neighbour of a random
point in A is itself in A.
A simple example of an η-closed set is the set {A ∈ Mm,n (F2 ) : Ax = y}, for some pair of vectors
x ∈ Fn2 , y ∈ Fm 2 . Indeed, if Ax = y and B is a random matrix of rank 1, then x ∈ ker B with probability
roughly 1/2. But if x ∈ ker B, then (A + B)x = y, so A + B ∈ A as well. A very similar, but distinct,
example is the set {A ∈ Mm,n (F2 ) : AT x = y}. Let us call sets of one of these two kinds basic sets.
We can form further examples by taking intersections of a small number of basic sets. For example,
if x1 , . . . , xk are linearly independent and we take a set of the form
{A ∈ Mm,n (F2 ) : Ax1 = y1 , . . . , Axk = yk },
then with probability approximately 2−k each xi belongs to ker B, so for any A in the set, A + B belongs to
the set with probability approximately 2−k . The result of Khot, Minzer and Safra is the following.
Theorem 1.1. For every η > 0 there exist δ > 0 and a positive integer k such that if A is any η-closed
subset of Mm,n (F2 ), then there exists an intersection C of at most k basic sets such that |A ∩ C| ≥ δ |C|
and C 6= 0.
/
In other words, every closed set is dense inside some intersection of a small number of basic sets.
It is well known and not hard to see that this in fact leads to a characterization (at least qualitatively)
of closed sets. Indeed, observe first that if A is η-closed, then the subgraph induced by A has average
degree at least η|B|, where B is the set of rank-1 matrices, and maximal degree at most |B|. Therefore,
any subset of A of size at least (1 − η/4)|A| has average degree at least η|B|/2. It follows from this
observation and Theorem 1.1 that we can find disjoint subsets A1 , . . . , Ar of A, subsets C1 , . . . , Cr of
Mm,n (F2 ), a positive real number δ = δ (η) and a positive integer k = k(η) with the following properties.
1. The sets Ai are disjoint.
2. Each Ci is an intersection of at most k basic sets.
3. For each i, |Ai ∩ Ci | ≥ δ |Ci |.
4. | i Ai | ≥ η|A|/4.
S
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 2
S UBSETS OF C AYLEY G RAPHS T HAT I NDUCE M ANY E DGES
Conversely, if such sets exist, then the probability that a random matrix A ∈ A belongs to some Ai is at
least η/4. If it belongs to Ai , then we can use the following lemma. We write u ⊗ v for the rank-1 matrix
M with Mi j = ui v j , which sends a vector x to the vector hx, viu. Note also that (u ⊗ v)T sends x to hx, uiv.
Lemma 1.2. Let C be an intersection of at most k basic sets and let A ⊂ C be a subset of relative density
at least δ . Then A is 2−k (δ − 2−(m−k) )-closed.
Proof. Let us set C(x, y) = {A ∈ Mm,n (F2 ) : Ax = y}, and C0 (x, y) = {A ∈ Mm,n (F2 ) : AT x = y}. Let
x1 , . . . , xk , y1 , . . . , yk be non-zero vectors such that
r k
C= C(xi , yi ) ∩ C0 (xi , yi ).
\ \
i=1 i=r+1
Let u ⊗ v be a rank-1 matrix. If there exists i ≤ r such that hxi , vi =6 0, then (A + u ⊗ v)(xi ) = yi + u,
so A + u ⊗ v ∈ / C(xi , yi ) and hence A + u ⊗ v ∈/ C. Similarly, if there exists i > r such that hxi , ui 6= 0, then
(A + u ⊗ v)T (xi ) = yi + v and again A + u ⊗ v ∈ / C.
We shall now bound from below the probability that A + u ⊗ v ∈ A given that A ∈ A and that
hxi , vi = 0 for every i ≤ r and hxi , ui = 0 for every r < i ≤ k, noting that the condition on u ⊗ v states that
(u, v) ∈ U ×V for a pair of subspaces U and V with codimensions that add up to at most k, a condition
that occurs with probability 2−k .
Let us now condition further on the choice of v ∈ V . That means that we fix v, choose a random u ∈ U,
and add u ⊗ v to A. If we allow u to take the value 0, then the resulting matrix is uniformly distributed in
the affine subspace A +U ⊗ v, so the probability that it is in A is equal to the relative density of A inside
this affine subspace.
The translates of U ⊗ v by matrices in C partition C. Let us write them as W1 , . . . , Ws , and let the
relative density of A inside Wi be δi . Then, still fixing v, we have that
δi2
P[A + u ⊗ v ∈ A] = ∑ P[A ∈ Wi ] P[A + u ⊗ v ∈ A | A ∈ Wi ] = ∑ ≥ δ.
i i sδ
This statement is true regardless of v, so we deduce that the probability that A + u ⊗ v ∈ A given that
A ∈ A and (u, v) ∈ U × (V \ {0}) is at least δ . If we now insist that u 6= 0, we reduce this probability by
at most 2−(m−k) , so the result is proved.
Let B ∈ B be chosen uniformly at random. Given the lemma above, applied to the sets Ai and Ci , we
deduce that the conditional probability that A + B ∈ Ai given that A ∈ Ai is at least some c(δ , k) > 0, and
from that it follows that A is c(δ , k)η/4-closed.
Thus, a set A is η-closed for some not too small η if and only if an appreciable fraction of A is
efficiently covered by disjoint intersections of few basic sets.
Barak, Kothari and Steurer suggest in [1] that establishing a higher-dimensional analogue of The-
orem 1.1 may be a useful step toward obtaining a proof of the full Unique Games Conjecture. The
main purpose of this paper is to formulate a possible higher-dimensional analogue of Theorem 1.1
(Conjecture 1.4) and prove some partial results towards it. However, we do not claim a reduction of the
Unique Games Conjecture to Conjecture 1.4.
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 3
T IMOTHY G OWERS AND O LIVER JANZER
We say that A ⊂ Fn21 ⊗· · ·⊗Fn2d is η-closed if with probability at least η, we have A+u1 ⊗· · ·⊗ud ∈ A,
when A ∈ A and vectors ui ∈ Fn2i \ {0} are chosen independently and uniformly at random.
Problem 1.3. Give a qualitative description of η-closed sets A ⊂ Fn21 ⊗ · · · ⊗ Fn2d .
To see that this is indeed a generalization of the problem about matrices considered above, we identify
Mm,n (F2 ) with Fm n
2 ⊗ F2 in the usual way, which leads to a slight reformulation of Theorem 1.1 in terms
of tensor products. Note first that under this identification, the set
{M ∈ Mm,n (F2 ) : Mx1 = · · · = Mxa = M T y1 = · · · = M T yb = 0}
becomes the set H ⊗ K, where H = hy1 , . . . , yb i⊥ and K = hx1 , . . . , xa i⊥ . It follows that an intersection of
at most k basic sets is either empty or a translate of H ⊗ K for some pair of subspaces H ⊂ Fm n
2 , K ⊂ F2
with codim(H) + codim(K) ≤ k.
In the higher-dimensional case, there is a richer class of sets A ⊂ Fn21 ⊗ · · · ⊗ Fn2d that are η-closed.
To describe them, we introduce the following piece of notation, which we shall use repeatedly in the
rest of the paper. Given a non-empty subset I ⊂ [d], write FI2 for i∈I Fn2i , so that we naturally have
N
c
Fn21 ⊗ · · · ⊗ Fn2d = FI2 ⊗ FI2 . Here and elsewhere in the paper, I c stands for [d] \ I.
Now we say that C is k-simple if there exists a collection of subspaces HI ⊂ FI2 of codimension at
most k, one for each non-empty subset I ⊂ [d], such that C is a translate of the set
\ c
(HI ⊗ FI2 )
I⊂[d],I6=0/
(where H[d] ⊗ F20/ is just H[d] ), which is a subspace of Fn21 ⊗ · · · ⊗ Fn2d . It is not hard to see that this subspace
contains at least a proportion c(d, k) > 0 of all rank-1 tensors u1 ⊗ · · · ⊗ ud (provided that n1 , . . . , nd are
sufficiently large), so it is c(d, k)-closed. It follows that any translate of it is c(d, k)-closed too.
We now make the following conjecture.
Conjecture 1.4. For any η > 0 and any positive integer d, there exist k = k(d, η) and ρ = ρ(d, η) > 0
with the following property. Let A ⊂ Fn21 ⊗ · · · ⊗ Fn2d be η-closed. Then there is a k-simple set C such that
|A ∩ C| ≥ ρ|C|.
Note that in the d = 2 case, we allow translates of sets (H{1} ⊗ H{2} ) ∩ H{1,2} rather than just translates of
H{1} ⊗ H{2} , so Conjecture 1.4 might seem to be weaker than Theorem 1.1. However, this actually makes
no difference, since when intersecting with H{1,2} , the cardinality of the set drops by a factor at most 2k .
The main result of this paper, stated later in this section, is a proof of Conjecture 1.4 in an important
special case.
1.1 What can be said about more general Cayley graphs?
It is tempting to try to prove Conjecture 1.4 by identifying and proving a statement that applies to a much
wider class of Cayley graphs, of which Conjecture 1.4 would be a special case. We would begin with an
Abelian (or even non-Abelian) group G and a pair of subsets A, B ⊂ G, where we think of B as the set of
generators, satisfying the hypothesis that |{(a, b) ∈ A × B : a + b ∈ A}| ≥ η|A||B|. We shall say in this
situation that A is (B, η)-closed (in G).
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 4
S UBSETS OF C AYLEY G RAPHS T HAT I NDUCE M ANY E DGES
Another way of writing the condition is
h1A ∗ µB , 1A i ≥ ηα,
where α is the density of A, µB is the characteristic measure of B (that is, the function that takes the value
|G|/|B| on B and 0 elsewhere) and we define f ∗ g(x) to be Ey+z=x f (y)g(z). By the Cauchy-Schwarz
inequality the left-hand side is at most k1A ∗ µB k2 k1A k2 = k1A ∗ µB k2 α 1/2 , where inner products and L p
norms are defined using expectations, so our hypothesis implies that k1A ∗ µB k22 ≥ η 2 α. It is easy to see
that this “mixed energy” k1A ∗ µB k22 can be at most α, with equality if and only if a + b − b0 ∈ A for every
a ∈ A, b, b0 ∈ B.
At this point let us recall the so-called asymmetric Balog–Szemerédi–Gowers theorem, which can be
found in [9] as Theorem 2.35. (For a useful alternative presentation of the theorem, see also [3].) The
main assumption of the theorem is that A, B are two finite subsets of an Abelian group, with densities α
and β , such that k1A ∗ 1B k22 ≥ ηαβ 2 (which is equivalent to saying that k1A ∗ µB k22 ≥ ηα), but there is
also an assumption that A is not too much bigger than B. The precise statement is as follows.
Theorem 1.5. For every ε > 0 there exists a constant C = C(ε) with the following property. Let G be a
finite Abelian group, let L ≥ 1, let 0 < η ≤ 1 and let A and B be finite subsets of G with densities α and
β , such that α ≤ Lβ and k1A ∗ 1B k22 ≥ 2ηαβ 2 . Then there exist a subset H ⊂ G such that |H + H| ≤
Cη −C Lε |H|, a subset X ⊂ G of size at most Cη −C Lε |A|/|H| such that |A ∩ (X + H)| ≥ C−1 η C L−ε |A|,
and some x ∈ G such that |B ∩ (x + H)| ≥ C−1 η C L−ε |B|.
More qualitatively speaking, if A is not too much larger than B and k1A ∗ 1B k22 is within a constant of its
largest possible value, then there is a set H of small doubling such that a small number of translates of H
cover a substantial proportion of A, and some translate of H covers a substantial proportion of B. It is not
hard to see that the converse holds as well.
This theorem cannot be used to prove Conjecture 1.4 because of the condition that α ≤ Lβ , which
does not apply here since the set A in Conjecture 1.4 can be much bigger than the set B. That raises the
following question, which generalizes Problem 1.3.
Question 1.6. Let G be a finite Abelian group, let η > 0, and let A, B ⊂ G be subsets such that A is
(B, η)-closed in G. What can be said about A, B and the relationship between them?
A similar question can of course be asked with the slightly weaker hypothesis that k1A ∗ 1B k22 ≥ η 2 αβ 2 ,
but we shall concentrate on the question as stated, since it is more closely related to Conjecture 1.4.
An immediate observation is that we cannot hope to say anything interesting about the structure of
B, even if η = 1. For example, η = 1 if A = G and B is an arbitrary subset of G. For a more general
example, one can let A be an arbitrary union of cosets of some subgroup H and let B be an arbitrary subset
of H. For a slightly different example, let G = Fn2 , let B be the set {e1 , . . . , en } of standard basis vectors,
and let A be a union of n/3-dimensional affine subspaces Vi , such that each Vi is a random translate of the
subspace generated by n/3 randomly chosen e j . Then if x ∈ Vi and b ∈ B, the probability that x + b ∈ Vi
is 1/3, so A is 1/3-closed.
Any general statement will have to be weak enough to allow for examples like these. The last
example shows that we cannot hope to find a single set H of small doubling and cover a large portion of A
efficiently with translates of H, unless H is of constant size, in which case the conclusion becomes trivial.
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 5
T IMOTHY G OWERS AND O LIVER JANZER
To sketch briefly why not, observe first that by Freiman’s theorem we can assume that H is a subspace.
Next, note that for each vector x, the probability that it belongs to the span of a random n/3 standard basis
vectors is exponentially small in the size of the support of x. We can also use the following simple lemma.
Lemma 1.7. Let H be a subspace of dimension d and let k ≤ d. Then the number of vectors in H of
support size at most k is at most the number of vectors of support size at most k in the subspace generated
by the first d standard basis vectors e1 , . . . , ed , namely ∑ki=0 di .
Proof. Let u1 , . . . , ud be a basis for d. By Gaussian elimination, we can convert u1 , . . . , ud into a basis
v1 , . . . , vd and find coordinates t1 , . . . ,td such that vi (t j ) = δi j . Then the support size of ∑i λi vi is at least
the number of non-zero λi , which proves the result.
When d is large, it follows that the proportion of vectors in H of small support is very small.
Combining these observations, one can show that for every η there exists d such that if H is a d-
dimensional subspace, then the probability that a random subspace V of dimension n/3 is (H, η/2)-closed
is at most η/2. This in turn can be used to prove that with high probability the set A described above (for
a suitable number of Vi ) is not (H, η)-closed for any H of dimension d or above.
However, these examples do not rule out a weakening along the following lines.
Question 1.8. Let G be a finite Abelian group, let η > 0, and let A, B be subsets of G such that A is
(B, η)-closed in G. Does it follow that A has a non-empty subset A0 such that A0 is (B, η 0 )-closed in G,
and |A0 + A0 | ≤ C|A0 |, where η 0 > 0 and C are constants that depend on η only?
An argument similar to the one we mentioned just after the statement of Theorem 1.1 shows that if
the answer is yes, then we can find a collection of disjoint subsets A1 , . . . , Am that cover a substantial
proportion of A, each one with small doubling and each one (B, η 0 )-closed (with a slightly smaller η 0 ).
Thus, we would be able to obtain a conclusion similar to that of Theorem 1.5 but without the requirement
that the structured sets are all translates of one another.
A positive answer would also imply Conjecture 1.4. Indeed, by Freiman’s theorem Ai is contained in
a subspace Vi not much larger than Ai . This reduces the conjecture to the case where A is a subspace. In
that case, a very simple corollary of our main result, Corollary 1.12 (stated later) proves the conjecture.
However, the answer to Question 1.8 is easily seen to be negative (which implies that it is also
negative if we assume the weaker mixed-energy hypothesis instead). The example we are about to give
was communicated to us privately by Boaz Barak as a counterexample to a related but slightly different
statement.
For convenience let n be odd, let A ⊂ Fn2 be the set of all vectors with (n ± 1)/2 coordinates equal
to 1, and let B be the set of standard basis vectors. Then it is easy to see that A is (B, η)-closed for
η = (n + 1)/2n ≈ 1/2. Suppose now that we could find a subset A0 ⊂ A such that |A0 + A0 | ≤ C|A0 |, and
A0 is (B, η 0 )-closed. By Freiman’s theorem, A0 is contained in a subspace V that is not much bigger than
A0 , which implies that V is (B, c)-closed for some positive constant c = c(η). That implies that at least
cn of the standard basis vectors belong to V . Let W be the subspace spanned by these basis vectors.
The maximum number of elements of A that can belong to a translate x +W of W is 2(cn)−1/2 |W |, and
therefore |A0 | ≤ 2(cn)−1/2 |V |. This contradicts the fact that V is not much bigger than A0 .
In this paper we formulate a yet weaker conjecture and prove that it still implies Conjecture 1.4.
Unfortunately, we also give a counterexample to the weaker conjecture. The counterexample does not
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 6
S UBSETS OF C AYLEY G RAPHS T HAT I NDUCE M ANY E DGES
make the implication vacuous, however, because the implication depends on a non-trivial theorem that is
true and of some interest: it is just that for a general Cayley graph (on a finite Abelian group) one cannot
deduce the hypotheses of the theorem from the assumption that a set is η-closed. It is conceivable that
one might be able to prove Conjecture 1.4 (and thereby also give a different proof of the theorem of Khot,
Minzer and Safra) by using additional properties of the particular Cayley graph that that conjecture is
about.
How, then, might one try to find a conjecture that would not be contradicted by the “two-layers”
example just discussed? One observation that suggests a possible way forward is the following. Suppose
that we extend the set by adding a few more layers. If, say, we take not just the middle two layers but the
middle ε −1 layers (or thereabouts), then we obtain a new set inside which the first set has relative density
approximately 2ε, and this new set is (1 − 2ε)-closed, since a random element of the set will be in one of
the interior layers with probability approximately (and in fact slightly bigger than) 1 − 2ε, and adding an
arbitrary basis vector to such an element will give another element of the set.
So perhaps we could hope that if A is (B, η)-closed, then there is a set C that is (B, 1 − ε)-closed such
that |A ∩C| ≥ δ |C| for some δ that depends on η and ε only.
However, simple modifications of the example show that this is too much to ask. For instance, we
can take as our set A the set of all x ∈ Fn2 such that m or m + 1 coordinates are equal to 1 and all but the
first 2m coordinates are zero. If m is around n/4, say, then the resulting set is (B, 1/4)-closed, but there is
no prospect of A living densely in a set that is almost perfectly closed, because of the need to add basis
vectors corresponding to coordinates beyond 2m.
A further example to consider is the set of all x ∈ Fn2 such that at most n/3 coordinates are equal to
1. This set is (B, 1/3)-closed (at least—in fact it is more like (B, 2/3)-closed because the probability
that a random element of the set has exactly bn/3c coordinates equal to 1 is approximately 1/2), but for
similar reasons to the previous example, one cannot find an almost perfectly closed set with a significant
proportion of its elements in the set.
However, the picture changes if we ask for slightly less. Let us informally call a set C good if there is
a proportional-sized subset B0 ⊂ B such that C is (B0 , 1 − ε)-good for some small constant ε. Thus, now
we ask only that C should be almost closed for a large subset of B rather than for the whole set.
It is not immediately clear how to use this definition, because the statement that |A ∩C| ≥ δ |C| for
a good set C can be true for uninteresting reasons. For example, we could take C to be the union of a
subspace V generated by n/5 basis vectors together with an arbitrary subset of A of cardinality 2δ |V |. To
remedy this, we insist that C is “related to A” in the graph in a different sense from that of A being dense
in C.
Here, then, is a question that replaces Question 1.8.
Question 1.9. Is it true that for every η, ε > 0 there exist c > 0, δ > 0 and positive integer l with
the following property? Let G be a finite Abelian group and let A, B ⊂ G be subsets such that A is
(B, η)-closed. Then there is a subset B0 ⊂ B and a non-empty subset C ⊂ G with the following properties.
1. |B0 | ≥ δ |B|.
2. C is (B0 , 1 − ε)-closed.
3. C ⊂ x ∈ G : 1A ∗ µB ∗ · · · ∗ µB ∗ µ−B ∗ · · · ∗ µ−B (x) ≥ c where the number of µB s and µ−B s in the
convolution is l.
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 7
T IMOTHY G OWERS AND O LIVER JANZER
Condition (3) is saying that for any x ∈ C, the probability that x − b1 − · · · − bl + bl+1 + · · · + b2l ∈ A,
when the bi are chosen uniformly and independently at random from B, is at least c. When the group G is
Fn2 for some n, we can and will simplify it, since B = −B.
To see that this question improves on Question 1.8, let us consider the two problematic examples
for that question. If m is odd and A ⊂ Fn2 consists of all sequences with (m ± 1)/2 1s and with no 1s
after the mth coordinate, then let C be the set of all sequences with no 1s after the mth coordinate that
have between (m − 1)/2 − ε −1 and (m + 1)/2 + ε −1 1s. If l = ε −1 , then for any x ∈ C, the probability
that x − b1 − · · · − bl ∈ A is at least (m/(2n))l . (This is because conditional on bi ∈ {e1 , . . . , em } this
probability is at least 1/2l .) Moreover, if B0 = {e1 , . . . , em }, then for every b ∈ B0 and every c ∈ C that is
not on the boundary (in the obvious sense), we have that b + c ∈ C, so C is (B0 , 1 − ε)-closed.
Now let us look at the example where A is the set of all sequences with at most n/3 1s. This time let
C be the set of all sequences that are 0 after the first 2n/3 coordinates and have at most n/3 + ε −1 1s, and
let B0 = {e1 , . . . , e2n/3 }. Then for any x ∈ C, the probability that x − b1 − · · · − bl ∈ A is at least (1/3)l ,
where l = ε −1 . Moreover, C is (1 − ε)-closed, again because adding an element of B0 to a non-boundary
element of C gives an element of C.
Finally, note that even in the case where G is the group of n1 × n2 matrices over F2 and B is the set
of matrices of rank 1, we cannot necessarily take B0 to equal B in Question 1.9. Indeed, if u ∈ Fn22 is
and A = {M ∈ G : Mu = 0}, then for any c > 0 and any l, if n1 and n2 are sufficiently large,
non-zero
then x ∈ G : 1A ∗ µB ∗ · · · ∗ µB ∗ µ−B ∗ · · · ∗ µ−B (x) ≥ c ⊂ A, where the number of µB s and µ−B s in the
convolution is l. However, it is easy to see that no subset of A is (B, 3/4)-closed.
1.2 Our main result
Let us now see why a positive answer to Question 1.9 would imply Conjecture 1.4. The deduction
will be easy once we have established the following theorem, which is the main result of this paper. In
the statement of the theorem, and in the rest of this paper, G denotes Fn21 ⊗ · · · ⊗ Fn2d and B denotes the
multiset {u1 ⊗ · · · ⊗ ud : ui ∈ Fn2i for all i} (which is a multiset only because some of the ui can be zero).
Note that the notion of (B, η)-closedness can be generalized in an obvious way to multisets.
Theorem 1.10. For any θ > 0, there exists ε = ε(d, θ ) > 0 with the following property. Let δ > 0.
Then there exists a positive integer k = k(d, δ ) with the following property. For any B0 ⊂ B with
|B0 | ≥ δ |B| and any A ⊂ G which is (B0 , 1 − ε)-closed, there exists a k-simple set D ⊂ G such that
|D ∩ A| ≥ (1 − θ )|D|.
We remark that in the case where B0 = B the proof is easy, and D can be chosen to be the whole of G.
It is convenient to state the following corollary separately, which follows from Theorem 1.10 by
taking θ = 1/2.
Corollary 1.11. There exists ε = ε(d) > 0 such that for any δ > 0, there exists a positive integer
k = k(d, δ ) with the following property. For any B0 ⊂ B with |B0 | ≥ δ |B| and any A ⊂ G which is
(B0 , 1 − ε)-closed, there exists a k-simple set D ⊂ G which has |D ∩ A| ≥ (1/2)|D|.
Let us see why Conjecture 1.4 follows from Corollary 1.11 and a positive answer to Question 1.9 in
the case of the group G and the subset B ⊂ G of rank-1 tensors. Let η > 0. Pick ε = ε(d) so that the
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 8
S UBSETS OF C AYLEY G RAPHS T HAT I NDUCE M ANY E DGES
conclusion of Corollary 1.11 holds. If the answer to Question 1.9 is positive for G and B, then we can
choose c > 0, δ > 0, and a positive integer l such that the conclusion of the question is true. Now let
A ⊂ G be η-closed. This is saying that A is (B, η)-closed. By the conclusion of Question 1.9, there
exista set B0 ⊂ B with |B0 | ≥ δ |B| , and a non-empty subset C ⊂ G such that C is (B0 , 1 − ε)-closed and
C ⊂ x ∈ G : 1A ∗ µB ∗ · · · ∗ µB (x) ≥ c , where the number of µB s in the convolution is l. Define B0 to be
the multiset that consists of the set B0 together with the multiset of all u1 ⊗ · · · ⊗ ud with ui ∈ Fn2i for each
i and with at least one ui equal to 0. Note that |B0 | ≥ δ |B| and C is (B0 , 1 − ε)-closed. By Corollary 1.11,
there exists a k-simple set D ⊂ G, for some k = k(d, δ ), which has |D ∩ C| ≥ (1/2)|D|. Now pick x ∈ D
and b1 , . . . , bl ∈ B uniformly and independently at random. The probability that x − b1 − · · · − bl ∈ A is at
least c/2. Therefore, there exists some y ∈ G such that when x ∈ D is randomly chosen, the probability
that x − y ∈ A is at least c/2. That is,
1 1
|(D − y) ∩ A| ≥ c|D| = c|D − y|.
2 2
But D − y is a k-simple set, which finishes the proof of Conjecture 1.4.
Another simple corollary of Theorem 1.10 is the following result, which is Conjecture 1.4 in the case
where A is a subspace.
Corollary 1.12. For any η > 0 and any positive integer d, there exists some k = k(d, η) with the following
property. If V ⊂ G is a subspace which is η-closed, then V contains a k-simple subspace. That is,
\ c
V⊃ (HI ⊗ FI2 )
I⊂[d],I6=0/
for some collection of subspaces HI ⊂ FI2 of codimension at most k.
Proof. Since V is a vector space, the condition that V is η-closed says that u1 ⊗ · · · ⊗ ud ∈ V for at least
a proportion of η of all rank-1 tensors u1 ⊗ · · · ⊗ ud . Thus, there exists some B0 ⊂ B with |B0 | ≥ η|B|
such that V is (B0 , 1)-closed. Taking θ sufficiently close to 0 in Theorem 1.10, it follows that V ⊃ D for
a k-simple set D, where k depends only on d and η. Then D is a translate of
\ c
(HI ⊗ F2I )
I⊂[d],I6=0/
for some HI ⊂ FI2 of codimension at most k. Since V is a vector space, it follows that
\ c
V⊃ (HI ⊗ FI2 ).
I⊂[d],I6=0/
In the next section, we shall prove Theorem 1.10. In the last section, we show that the answer to
Question 1.9 is negative.
2 The proof of Theorem 1.10
Note that G = Fn21 ⊗ · · · ⊗ Fn2d can be viewed as the set of d-dimensional (n1 , . . . , nd )-arrays over F2 which
in turn can be viewed as Fn21 n2 ...nd , equipped with the entry-wise dot product.
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 9
T IMOTHY G OWERS AND O LIVER JANZER
The proof of Theorem 1.10 will be reasonably simple once we have established the following result.
In the statement of this lemma, and in the rest of this section, we write kB to mean the set of elements of
G that can be written as a sum of at most k elements of B, where B is some fixed (multi)subset of G.
Lemma 2.1. For all δ > 0 and d ∈ N there exist f1 (d), f3 (d) > 0 and f2 (d, δ ) ∈ N with the following
property. Let B0 ⊂ B be a multiset such that |B0 | ≥ δ |B|. Then there exists a multiset Q whose elements
are chosen from f1 (d)B0 (but with arbitrary multiplicity) with the following property. The set of arrays
r ∈ G with r.q = 0 for at least (1 − f3 (d))|Q| choices q ∈ Q is contained in
c
∑ VI ⊗ F2I
I⊂[d],I6=0/
for a collection of subspaces VI ⊂ FI2 that each have dimension at most f2 (d, δ ).
In order to deduce Theorem 1.10 from this lemma, we shall use Fourier analysis. Recall that if A is a
subset of G of density α, then by Parseval’s identity we have α = ∑r |1 cA (r)|2 . Also, if B is a multiset in
G, then by Parseval’s identity and the convolution law, h1A ∗ µB , 1A i = ∑r |1
cA (r)|2 µ
bB (r) (for a multiset B,
we define µB (x) = (|G|/|B|)B(x) where B(x) is the multiplicity of x in B). Thus, the condition that A is
(B, η)-closed can be rewritten as the inequality
∑ |1cA (r)|2 µbB (r) ≥ η ∑ |1cA (r)|2 .
r r
Another fact we shall use later is that if W is a subspace of G, then µc r.w
W (r) equals Ew∈W (−1) , which is
1 if r belongs to the orthogonal complement of W and 0 otherwise.
Lemma 2.2. Let G be an Abelian group, let A ⊂ G be a finite subset, let η1 , η2 > 0, and let b1 , b2 ∈ G.
Suppose that A is ({b1 }, 1−η1 )-closed and ({b2 }, 1−η2 )-closed in G. Then A is ({b1 +b2 }, 1−η1 −η2 )-
closed in G.
Proof. Let Abad = {a ∈ A : a + b2 6∈ A}. Then |Abad | ≤ η2 |A|, by hypothesis. So when a ∈ A is chosen
randomly, we have that
P[a + b1 + b2 6∈ A] ≤ P[a + b1 6∈ A] + P[a + b1 ∈ Abad ] ≤ η1 + η2 .
The result follows.
We are now in a position to deduce Theorem 1.10 from Lemma 2.1. In the proof, and in the rest of
this section, whenever a new function gi appears, we mean that there exists a function gi with the claimed
property.
Proof of Theorem 1.10. Let θ , δ > 0, B0 ⊂ B with |B0 | ≥ δ |B|, and suppose that A ⊂ G is (B0 , 1 − ε)-
closed, where ε is to be specified. Let B00 = {b ∈ B0 : A is ({b}, 1 − 2ε)-closed}. Clearly, |B00 | ≥
(1/2)|B0 |. Using Lemma 2.1, we can find a multiset Q with elements chosen from g1 (d)B00 such that the
set of arrays r ∈ G with r.q = 0 for at least (1 − g2 (d))|Q| choices q ∈ Q (where g2 (d) > 0) is contained
in
c
∑ VI ⊗ FI2
I⊂[d],I6=0/
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 10
S UBSETS OF C AYLEY G RAPHS T HAT I NDUCE M ANY E DGES
for subspaces VI ⊂ FI2 of dimension at most g3 (d, δ ). Then, by Lemma 2.2, A is ({b}, 1−2g1 (d)ε)-closed
for every b ∈ Q, since each such b is an element of g1 (d)B00 . In particular, A is (Q, 1 − 2g1 (d)ε)-closed,
and therefore
∑ |1cA (r)|2 µbQ (r) ≥ (1 − 2g1 (d)ε) ∑ |1cA (r)|2 .
r r
By Markov’s inequality, it follows that
g1 (d)ε
∑ |1c 2
A (r)| ≤ |1c 2
A (r)| .
bQ (r)<1−2g2 (d)
r:µ
g2 (d) ∑
r
Choosing ε = ε(d, θ ) > 0 to be at most θ g2 (d)/g1 (d), we therefore have
∑ |1c
A (r)| ≥ (1 − θ ) ∑ |1A (r)| .
2 c 2
bQ (r)≥1−2g2 (d)
r:µ r
bQ (r) ≥ 1 − 2g2 (d) then r.q = 0 for at least (1 − g2 (d))|Q| choices q ∈ Q. Thus, we have
Now if µ
∑ |1cA (r)|2 ≥ (1 − θ ) ∑ |1cA (r)|2 (2.1)
r∈T r∈G
c
where T = ∑I⊂[d],I6=0/ VI ⊗ FI2 . Let
c
R = T⊥ = VI⊥ ⊗ FI2 .
\
I⊂[d],I6=0/
Because µ
cR is the characteristic function of T , (2.1) is equivalent to the inequality
∑ |1cA (r)|2 µcR (r) ≥ (1 − θ ) ∑ |1cA (r)|2 ,
r∈G r∈G
which in physical space is the inequality
h1A ∗ 1A , µR i ≥ (1 − θ )k1A k22 = (1 − θ )α,
where α is the density of A. Equivalently,
hµA ∗ µR , 1A i ≥ 1 − θ ,
which tells us that if a random element of A is added to a random element of R, then the sum belongs
to A with probability at least 1 − θ . The number of triples (a1 , a2 , r) ∈ A × A × R with a1 + a2 = r is
therefore at least (1 − θ )|A||R|, and therefore, by averaging, there exists a ∈ A such that |(R − a) ∩ A| ≥
(1 − θ )|R| = (1 − θ )|R − a|. But R − a is g3 (d, δ )-simple, so we can take k = g3 (d, δ ) and D = R − a.
It remains to prove Lemma 2.1.
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 11
T IMOTHY G OWERS AND O LIVER JANZER
2.1 The proof of Lemma 2.1 in the matrix case
For the reader’s convenience, in this subsection we give the proof of Lemma 2.1 in the matrix case: that
is, the case when d = 2. Accordingly, in this subsection, G will be the group Fn21 ⊗ Fn22 and B will be the
multiset that consists of all rank-1 matrices u1 ⊗ u2 with u1 ∈ Fn21 and u2 ∈ Fn22 , with multiplicity. (As
already remarked, the non-trivial multiplicity comes from when u1 or u2 is zero.)
Lemma 2.3. Let B0 ⊂ B be such that |B0 | ≥ δ |B|. Then there exist k depending only on δ , a subspace
U ⊂ Fn21 , and a subspace Vu ⊂ Fn22 for each u ∈ U, such that all these subspaces have codimension at
most k, and such that every u ⊗ v with u ∈ U, v ∈ Vu belongs to 16B0 . Moreover, we can insist that all Vu
have the same codimension.
Proof. For each u ∈ Fn21 , let
B0u = {v ∈ Fn22 : u ⊗ v ∈ B0 } and let T = {u ∈ Fn21 : |B0u | ≥ (δ /2)2n2 }.
By averaging, we have that |T | ≥ (δ /2)2n1 .
If u ∈ T , then B0u has density at least δ /2 in Fn22 , so by Bogolyubov’s lemma (see for example
Proposition 4.39 of [9]) 4B0u = 2B0u − 2B0u contains a subspace Wu of codimension at most k1 = k1 (δ ).
By Bogolyubov’s lemma again, there is a subspace U of codimension at most k1 contained in 4T . Let
u ∈ U. Then pick t1 ,t2 ,t3 ,t4 ∈ T arbitrarily such that u = t1 + t2 + t3 + t4 and set Vu = 4i=1 Wti . Note that
T
Vu has codimension at most 4k1 for every u ∈ U. If v ∈ Vu , then ti ⊗ v ∈ 4B0 for i = 1, . . . , 4, therefore
u ⊗ v ∈ 16B0 . Thus, we can take k = 4k1 .
For the last assertion, note that we may replace Vu with any subspace of it, and we still have
u ⊗Vu ⊂ 16B0 .
In the next three lemmas k is a positive integer, U is a subspace of Fn21 and for each u ∈ U, Vu is a
subspace of Fn22 such that all these subspaces have codimension at most k and all the Vu have the same
codimension. We take Q = u∈U (u ⊗Vu ) and prove that this choice is suitable for Lemma 2.1.
S
Lemma 2.4. There exists an absolute constant ε > 0 with the following property. The set of arrays
r ∈ G with r.q = 0 for at least (1 − ε)|Q| choices q ∈ Q is contained in W12 +W1 ⊗ Fn22 + Fn21 ⊗W2 where
W12 ⊂ Fn21 ⊗ Fn22 ,W1 ⊂ Fn21 and W2 ⊂ Fn22 are subspaces of dimension at most f (k).
Before we prove this lemma, we need to establish the following result. In the statement, and in the
n
rest of this section, we use the following convention for the multiplication of arrays r ∈ Fn21 ⊗ · · · ⊗ F2a+b
n n
and s ∈ Fn21 ⊗ · · · ⊗ Fn2a . Define rs ∈ F2a+1 ⊗ · · · ⊗ F2a+b to be the array with
(rs)ia+1 ,...,ia+b = ∑ r j ,..., j ,i
1 a a+1 ,...,ia+b s j1 ,..., ja .
j1 ,..., ja
Note that in the case when r is a matrix and s is a vector, this is not quite the same as the standard
convention since we sum over the first coordinate of the matrix instead of the second. If r and s are arrays
of the same size, then we use the notation r.s for the product of r and s, since then it coincides with the
obvious notion of dot product, and it is useful to think of it that way.
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 12
S UBSETS OF C AYLEY G RAPHS T HAT I NDUCE M ANY E DGES
Lemma 2.5. For m = 2k+3 , let r1 , . . . , rm ∈ G be such that for every i ≤ m there are at least (3/4)|Q|
choices of q ∈ Q such that ri .q = 0. Then there exist i 6= j such that (ri − r j )w = 0 for at least ρ(k)2n1
choices w ∈ Fn21 , for some positive function ρ(k). Thus, there exist i 6= j such that ri − r j has rank at most
l(k).
Proof. For each i ≤ m, there are at least |U|/2 choices of u ∈ U such that ri .(u ⊗ v) = 0 for more than
|Vu |/2 choices of v ∈ Vu . But ri .(u ⊗ v) = (ri u).v, so this implies that ri u ∈ Vu⊥ .
It follows that for at least |U|/4 choices of u ∈ U we have ri u ∈ Vu⊥ for at least m/4 choices of i ≤ m.
Since m/4 > |Vu⊥ |, for every such u there exist i 6= j with ri u = r j u. Thus, for some i 6= j, there are at
least |U|/(4m2 ) choices of u ∈ U with ri u = r j u. The result follows.
Lemma 2.5 reduces Lemma 2.4 to the following.
Lemma 2.6. There exists an absolute constant ε 0 > 0 with the following property. The set of arrays r ∈ G
of rank at most l such that r.q = 0 for at least (1−ε 0 )|Q| choices q ∈ Q is contained in W1 ⊗Fn22 +Fn21 ⊗W2
where W1 ⊂ Fn21 and W2 ⊂ Fn22 are subspaces of codimension at most f (k, l).
Indeed, take ε 0 as given by Lemma 2.6 and let ε = min(ε 0 /2, 1/4). We claim that ε is suitable for
Lemma 2.4. Take l(k) as given by Lemma 2.5. Choose a maximal set x1 , x2 , . . . , xt ∈ G with the property
that for every i ≤ t, we have xi .q = 0 for at least (1 − ε)|Q| choices q ∈ Q, and for every 1 ≤ i < j ≤ t,
xi − x j has rank greater than l(k). By Lemma 2.5, t ≤ 2k+3 . Now if some r ∈ G has r.q = 0 for at least
(1 − ε)|Q| choices q ∈ Q, then by the maximality of the x j ’s it follows that r − xi has rank at most l(k) for
some i ≤ t. Moreover, (r − xi ).q = 0 for at least (1 − ε 0 )|Q| choices q ∈ Q, so by Lemma 2.6, r − xi is
contained in W1 ⊗ Fn22 + Fn21 ⊗W2 where W1 ,W2 have codimension at most g(k) and do not depend on r.
So we may take W12 to be the span of all the xi .
Proof of Lemma 2.6. We shall prove that we can take ε 0 to be 1/8, W1 to be U ⊥ and W2 to be a subspace
that we define as follows. Let
n2 ⊥ |U|
X = x ∈ F2 : x ∈ Vu for at least choices u ∈ U .
10 · 2l
Since |Vu⊥ | ≤ 2k for every u ∈ U, we have
|U| · 2k
|X| ≤ = 10 · 2k+l .
|U|/10 · 2l
Let W2 = span(X).
Now let r be a matrix of rank at most l such that r.q = 0 for at least 7|Q|/8 choices of q ∈ Q. Then
ru ∈ Vu⊥ for at least 3|U|/4 choices of u ∈ U. Since r has rank at most l, we have r ∈ Fn21 ⊗ H2 (r) for
some subspace H2 (r) ⊂ Fn22 with dim(H2 (r)) ≤ l. By definition, for any v 6∈ W2 , the number of u ∈ U
with v ∈ Vu⊥ is at most |U|/(10 · 2l ). Since |H2 (r)| ≤ 2l and ru ∈ H2 (r) for every u ∈ U, the number of
u ∈ U with ru ∈ Vu⊥ \W2 is at most |U|/10. It follows that for more than |U|/2 choices u ∈ U we have
ru ∈ W2 . This in fact implies that ru ∈ W2 for all u ∈ U. Take a basis y1 , . . . , ya for W2 and extend it to a
basis y1 , . . . , ya , y01 , . . . , y0b for Fn22 . Choose xi , x0j ∈ Fn21 such that
r= ∑ xi ⊗ yi + ∑ x0j ⊗ y0j .
1≤i≤a 1≤ j≤b
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 13
T IMOTHY G OWERS AND O LIVER JANZER
For every u ∈ U, we have
ru = ∑ (xi .u)yi + ∑ (x0j .u)y0j ,
1≤i≤a 1≤ j≤b
so x0j .u = 0 holds for every 1 ≤ j ≤ b and every u ∈ U. Thus, r ∈ Fn21 ⊗W2 +U ⊥ ⊗ Fn22 .
2.2 The proof of Lemma 2.1 in the general case
It is convenient to introduce a few definitions.
Definition 2.7. Let k be a positive integer and let ε > 0. Let Q be a multiset with elements chosen from
G (with arbitrary multiplicity). We say that Q is (k, α)-forcing if the set of all arrays r ∈ G with r.q = 0
for at least α|Q| choices q ∈ Q is contained in a set of the form
c
∑ VI ⊗ FI2
I⊂[d],I6=0/
for some choice of subspaces VI ⊂ FI2 of dimension at most k.
Note that the conclusion of Lemma 2.1 is that the multiset Q is ( f2 (d, δ ), 1 − f3 (d))-forcing.
Definition 2.8. We say that the hypothesis (H) holds for d if the following is true. For every δ > 0
there exist f1 (d), f2 (d, δ ) and f3 (d) > 0 such that if B0 ⊂ B is such that |B0 | ≥ δ |B|, then there exists a
multiset Q, with elements chosen from B ∩ f1 (d)B0 , that is ( f2 (d, δ ), 1 − f3 (d))-forcing.
Hypothesis (H) is the one that really interests us, since if it holds for every d then Lemma 2.1 is
proved. However, in order to get an induction to work we shall need a slight strengthening that says that
we can ask for the elements of Q to belong to a large subspace of a suitable form.
Definition 2.9. We say that the hypothesis (H’) holds for d if the following is true. For every δ > 0
and every positive integer l there exist f1 (d), f2 (d, δ , l) and f3 (d) > 0 such that if B0 ⊂ B is such that
|B0 | ≥ δ |B|, and for every non-empty I ⊂ [d], LI ⊂ FI2 is a subspace of codimension at most l, then there
exists a multiset Q, with elements chosen from
c
B ∩ ( f1 (d)B0 ) ∩
\
(LI ⊗ FI2 ),
I
that is ( f2 (d, δ , l), 1 − f3 (d))-forcing.
In what follows, we shall prove that if (H) holds for d, then so does (H’), and that if (H’) holds
for all d 0 < d, then (H) holds for d. This completes the proof since (H) holds for d = 1. Indeed, if
B0 ⊂ Fn21 has |B0 | ≥ δ · 2n1 , then by Bogolyubov’s lemma, 4B0 = 2B0 − 2B0 contains a subspace U ⊂ Fn21
of codimension at most g(δ ). If x.u = 0 for over half the elements of U, then the set of u ∈ U with x.u = 0
is not contained in a proper subspace, so x ∈ U ⊥ , which has dimension at most g(δ ). This implies that U
is (g(δ ), 3/4)-forcing.
The next few results are needed for technical reasons. The set introduced in the next definition
behaves well under certain algebraic operations, such as intersecting with a dense subspace. It is a
generalization of the set u∈U (u ⊗Vu ) used in the previous subsection.
S
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 14
S UBSETS OF C AYLEY G RAPHS T HAT I NDUCE M ANY E DGES
Definition 2.10. Suppose that we build a collection of subspaces as follows. We begin with a subspace
U ⊂ Fn21 . Then for each u1 ∈ U we take a subspace Uu1 ⊂ Fn22 , for each u1 ∈ U and u2 ∈ Uu1 we take a
subspace Uu1 ,u2 ⊂ Fn23 , and so on up to subspaces Uu1 ,...,ud−1 . Now let Q be the multiset that consists of all
tensors u1 ⊗ · · · ⊗ ud such that u1 ∈ U, u2 ∈ Uu1 , . . . , ud ∈ Uu1 ,...,ud−1 . If all the subspaces in the collection
have codimension at most l, then we say that Q is an l-system.
Lemma 2.11. Let Q be an l-system and let Q0 be a l 0 -system. Then Q ∩ Q0 contains an (l + l 0 )-system.
Proof. Let Q have spaces as in Definition 2.10 and let Q0 have spaces Uu0 0 ,...,u0 . We define an (l + l 0 )-
1 k−1
system P contained in Q ∩ Q0 as follows. Let V = U ∩ U 0 . Suppose we have defined Vv1 ,...,v j−1 for all
j ≤ k. Let v1 ∈ V, v2 ∈ Vv1 , . . . , vk−1 ∈ Vv1 ,...,vk−2 . We let
Vv1 ...,vk−1 = Uv1 ...,vk−1 ∩Uv01 ...,vk−1 .
This is well-defined and has codimension at most l + l 0 in Fn2k . Let P be the corresponding (l + l 0 )-
system.
Lemma 2.12. Let B0 ⊂ B be a multiset such that |B0 | ≥ δ |B|. Then there exists an f1 (d, δ )-system with
elements chosen from f2 (d)B0 .
Proof. The proof is by induction on d. The case d = 1 is an easy application of Bogolyubov’s lemma.
Suppose that the lemma has been proved for all d 0 < d and let B0 ⊂ B be a multiset such that |B0 | ≥ δ |B|.
Let D be the multiset {v2 ⊗ · · · ⊗ vd : v2 ∈ Fn22 , . . . , vd ∈ Fn2d }. For each u ∈ Fn21 , let
B0u = {s ∈ D : u ⊗ s ∈ B0 } and let T = {u ∈ Fn21 : |B0u | ≥ (δ /2)|D|}.
By averaging, we have that |T | ≥ (δ /2)2n1 . Now by the induction hypothesis, for every t ∈ T , there
exists an f1 (d − 1, δ /2)-system Pt in Fn22 ⊗ · · · ⊗ Fn2d (the definition is analogous to the definition of a
system in Fn21 ⊗ . . . Fn2d ), which is contained in f2 (d − 1)Bt0 . By Bogolyubov’s lemma, 4T = 2T − 2T
contains a subspace U ⊂ Fn21 of codimension at most g1 (δ ). For each u ∈ U, write u = t1 + t2 + t3 + t4
arbitrarily with ti ∈ T , and let
Qu = Pt1 ∩ Pt2 ∩ Pt3 ∩ Pt4 ,
which is a 4 f1 (d − 1, δ /2)-system, by Lemma 2.11. Now Q = u∈U (u ⊗ Qu ) is an f1 (d, δ )-system
S
provided that f1 (d, δ ) ≥ max(4 f1 (d − 1, δ /2), g1 (δ )). Moreover, for any u ∈ U, s ∈ Qu , we have u ⊗ s ∈
4 f2 (d − 1)B0 , so Q is suitable provided that f2 (d) ≥ 4 f2 (d − 1).
The next lemma is the last ingredient needed to prove that (H’) follows from (H).
Lemma 2.13. Let Q be a k-system, and for each non-empty I ⊂ [d] let LI ⊂ FI2 be a subspace of
c
codimension at most l. Let T = I (LI ⊗ FI2 ). Then Q ∩ T contains an f (d, k, l)-system.
T
Proof. Let the spaces of Q be Uu1 ,...,u j−1 . It suffices to prove that for every 1 ≤ j ≤ d, and every
u1 ∈ U, . . . , u j−1 ∈ Uu1 ,...,u j−2 , the codimension of
\ [ j]\I
(u1 ⊗ · · · ⊗ u j−1 ⊗Uu1 ,...,u j−1 ) ∩ (LI ⊗ F2 )
I⊂[ j], j∈I
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 15
T IMOTHY G OWERS AND O LIVER JANZER
in u1 ⊗ · · · ⊗ u j−1 ⊗Uu1 ,...,u j−1 is at most g1 (d, l). Thus, it suffices to prove that for every I ⊂ [ j] with j ∈ I,
the codimension of
[ j]\I
(u1 ⊗ · · · ⊗ u j−1 ⊗Uu1 ,...,u j−1 ) ∩ (LI ⊗ F2 )
in u1 ⊗ · · · ⊗ u j−1 ⊗Uu1 ,...,u j−1 is at most g2 (l). But this is equivalent to the statement that
!
O
ui ⊗Uu1 ,...,u j−1 ∩ LI
i∈I\{ j}
i∈I\{ j} ui ) ⊗Uu1 ,...,u j−1 , which clearly holds with g2 (l) = l.
N
has codimension at most g2 (l) in (
Lemma 2.14. If (H) holds for d, then so does (H’).
Proof. Let B0 and LI be given as in (H’). By Lemma 2.12, we can choose a g1 (d, δ )-system in g2 (d)B0 .
Thus, by Lemma 2.13,
c
(g2 (d)B0 ) ∩ (LI ⊗ FI2 )
\
I
contains a g3 (d, δ , l)-system B00 . Note that B00 ⊂ B with |B00 | ≥ g4 (d, δ , l)|B|, where g4 (d, δ , l) > 0. By
hypothesis (H) applied to B00 in place of B0 , it follows that there is a multiset Q, with elements chosen
from B ∩ g5 (d)B00 ⊂ B ∩ g5 (d)g2 (d)B0 , which is (g6 (d, δ , l), 1 − g7 (d))-forcing. Now Q ⊂ Ic
I (LI ⊗ F2 ),
T
finishing the proof.
The next result generalizes Lemma 2.5. To state it, we need to find the equivalent of low-rank matrices
in the higher-dimensional case. The definition we use is essentially the same as that of the partition
rank of a tensor (see for example [8] for a discussion of this notion). Indeed, if a tensor has partition
rank at most k, then it is k-degenerate (in the sense of the next definition), and conversely if a tensor is
k-degenerate, then it has partition rank is at most 2d−1 k.
The second author has shown that the partition rank is also related to the analytic rank of a tensor
[4, 5], which we do not define here (but again see [8]), with a polynomial dependence, improving on
the previously known Ackermann dependence. In this section we use a very similar argument, but since
we do not care about bounds, we present it in qualitative form for ease of reading and for the sake of
completeness.
Definition 2.15. Let k be a positive integer. We say that r ∈ G is k-degenerate if there is a collection of
subspaces HI ⊂ FI2 , one for each non-empty proper subset I ⊂ [d] and each one of dimension at most k,
such that
r∈ ∑ HI ⊗ HIc .
I⊂[d−1],I6=0/
c c
If r ∈ HI ⊗ FI2 with dim(HI ) ≤ k, then r ∈ HI ⊗ HI c for some HI c ⊂ FI2 of dimension at most k. (This
follows by writing r as ∑ j≤m s j ⊗ t j with {s j } a basis for HI and letting HI c be the span of all t j .) Thus, r
is k-degenerate if and only if we have the apparently weaker condition that
c
r∈ ∑ HI ⊗ FI2
I⊂[d−1],I6=0/
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 16
S UBSETS OF C AYLEY G RAPHS T HAT I NDUCE M ANY E DGES
for some collection of subspaces HI ⊂ FI2 of dimension at most k, or equivalently the condition that
r∈ ∑ FI2 ⊗ HI c
I⊂[d−1],I6=0/
Ic
for some collection of subspaces HI c ⊂ F2 of dimension at most k.
Lemma 2.16. Suppose that (H) holds for d − 1. Let D be the multiset
n
{u1 ⊗ · · · ⊗ ud−1 : u1 ∈ Fn21 , . . . , ud−1 ∈ F2d−1 }.
(i) Let D0 ⊂ D, and for each t ∈ D0 , let Ut be a subspace of Fn2d of codimension at most k with
the codimensions of the Ut all equal. Let Q be the multiset t∈D0 (t ⊗ Ut ). If m = 2k+3 , and
S
r1 , . . . , rm ∈ G have the property that for every i, ri .q = 0 holds for at least (3/4)|Q| choices of
q ∈ Q, then there exist i 6= j such that (ri − r j )(v1 ⊗ · · · ⊗ vd−1 ) = 0 for at least f1 (k)|D0 | choices
of v1 ⊗ · · · ⊗ vd−1 ∈ D0 , where f1 (k) > 0 depends only on k.
(ii) Let c > 0 and let r ∈ G be such that r(v1 ⊗ · · · ⊗ vd−1 ) = 0 for at least c|D| choices v1 ⊗ · · · ⊗ vd−1 ∈
D. Then r is f2 (d, c)-degenerate.
(iii) Let δ > 0 and let B0 ⊂ B be such that |B0 | ≥ δ |B|. Then there exists Q ⊂ B ∩ 4B0 with the
following property. If m ≥ f3 (δ ) and r1 , . . . , rm ∈ G are such that for each i, ri .q = 0 for at least
(3/4)|Q| choices q ∈ Q, then there exist i 6= j such that ri − r j is f4 (d, δ )-degenerate.
(iv) Let δ > 0 and let B0 ⊂ B be such that |B0 | ≥ δ |B|. Then there exist Q ⊂ B ∩ 4B0 and a subspace
[d]
V[d] ⊂ F2 of dimension at most f3 (δ ) with the following property. Any array r with r.q = 0 for at
least (3/4)|Q| choices q ∈ Q can be written as r = x + y where x ∈ V[d] and y is f4 (d, δ )-degenerate.
Proof. (i) By averaging, for every i ≤ m there are at least |D0 |/2 choices of t ∈ D0 such that ri .(t ⊗u) =
0 for more than half the u ∈ Ut . But ri .(t ⊗ u) = (rit).u, so for these t we have that rit ∈ Ut⊥ . By
further averaging, it follows that for at least |D0 |/4 choices of t ∈ D0 we have that rit ∈ Ut⊥ for at
least m/4 choices of i ≤ m. Since m/4 > |Ut⊥ |, for every such t, there exist i 6= j with rit = r j t.
Thus, for some i 6= j, there are at least |D0 |/(4m2 ) choices of t ∈ D0 with rit = r j t, which implies
the statement we wish to prove.
n
(ii) Write r = ∑i si ⊗ wi where si ∈ Fn21 ⊗ · · · ⊗ F2d−1 and {wi } is a basis for Fn2d . Note that r(v1 ⊗ · · · ⊗
vd−1 ) = 0 if and only if si .(v1 ⊗ · · · ⊗ vd−1 ) = 0 for every i. Let D0 be the multiset consisting of
all v1 ⊗ · · · ⊗ vd−1 with si .(v1 ⊗ · · · ⊗ vd−1 ) = 0 for every i. By assumption, |D0 | ≥ c|D|. Since
(H) holds for d − 1, there exists a multiset Q, with elements chosen from g1 (d)D0 , which is
(g2 (d, c), 1 − g3 (d))-forcing. Since si .q = 0 for every q ∈ Q, it follows that there exist subspaces
VI ⊂ FI2 for every I ⊂ [d − 1], I 6= 0, / of dimension at most g2 (d, c) such that
[d−1]\I
si ∈ ∑ VI ⊗ F2
I
for all i. In particular,
c
r∈ ∑ VI ⊗ FI2 .
I⊂[d−1],I6=0/
Thus, r is g2 (d, c)-degenerate.
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 17
T IMOTHY G OWERS AND O LIVER JANZER
(iii) Let D0 = {t ∈ D : t ⊗ u ∈ B0 for at least (δ /2)2nd choices u ∈ Fn2d }. Clearly, we have |D0 | ≥
(δ /2)|D|. Moreover, by Bogolyubov’s lemma, for every t ∈ D0 , there exists a subspace Ut ⊂ Fn2d
of codimension at most g4 (δ ) such that t ⊗ Ut ⊂ 4B0 . After passing to suitable subspaces, we
may assume that all Ut have the same codimension. Now let Q = t∈D0 (t ⊗ Ut ). By (i), if
S
f3 (δ ) ≥ 2g4 (δ )+3 , then there exist i 6= j such that (ri − r j )t = 0 for at least g5 (δ )|D0 | choices t ∈ D0
(where g5 (δ ) > 0) and therefore also for at least g6 (δ )|D| choices t ∈ D (where g6 (δ ) > 0). By
(ii), it follows that ri − r j is g7 (d, δ )-degenerate.
(iv) Choose Q as in (iii) and let r1 , . . . , rm be a maximal set such that for all i we have ri .q = 0 for at
least (3/4)|Q| choices q ∈ Q, and for all i 6= j, ri − r j is not f4 (d, δ )-degenerate. Then, by (iii),
we have m < f3 (δ ). Let V[d] be the span of all the ri . The result follows by the maximality of
{r1 , . . . , rm }.
The next lemma is the key step to complete the proof of Lemma 2.1. In order to state it, we need
to introduce a total ordering ≺ of the non-empty subsets of [d − 1]. It does not matter exactly what the
ordering is, but we require it to have the property that if J ( I then J ≺ I.
To understand the point of the next lemma, observe that we take an array r that belongs to the sum of
a certain set of subspaces, some of which depend on r, and we show, using the hypothesis that r.q = 0
for almost all q ∈ Q, that it is contained in a similar sum, but with the subspace corresponding to I c no
longer depending on r. By applying this lemma repeatedly, we shall remove all dependence on r from the
right-hand side.
Lemma 2.17. Suppose that (H’) holds for every d 0 < d. Let δ > 0 and let B0 ⊂ B be such that |B0 | ≥ δ |B|.
c
Let I ⊂ [d − 1], I 6= 0/ and for each J ≺ I let WJ ⊂ FJ2 ,WJ c ⊂ FJ2 be subspaces of dimension at most k.
[d]
In addition, let W[d] ⊂ F2 be a subspace of dimension at most k. Then there exists a multiset Q with
elements chosen from B ∩ f1 (d)B0 with the following property. Any array
c
r ∈ W[d] + ∑ (WJ ⊗ FJ2 + FJ2 ⊗WJ c ) + ∑ FJ2 ⊗ HJ c (r)
J≺I JI
with dim(HJ c (r)) ≤ k and the property that r.q = 0 for at least (1 − f2 (d))|Q| choices q ∈ Q is contained
in a subspace
c
W[d] + ∑ (UJ ⊗ FJ2 + FJ2 ⊗UJ c ) + ∑ FJ2 ⊗ KJ c (r)
JI J I
Jc c
for some UJ ⊂ FJ2 ,UJ c ⊂ F2 not depending on r and some KJ c (r) ⊂ FJ2 possibly depending on r, all of
dimension at most f3 (d, δ , k).
Proof. After reordering if necessary, we may assume that I = [a] for some 1 ≤ a ≤ d − 1. The next claim
gives us a multiset Q with certain properties. Once we have it, we shall use those properties to show that
Q satisfies the conclusion of the lemma.
Claim. There exist a multiset Q0 with elements chosen from
I\J
(WJ⊥ ⊗ F2 )
\
J⊂I,J6=I,J6=0/
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 18
S UBSETS OF C AYLEY G RAPHS T HAT I NDUCE M ANY E DGES
which is (h1 (d, δ , k), 1 − h2 (d))-forcing (with h2 (d) > 0), and for each s ∈ Q0 , a multiset Qs with ele-
c
ments chosen from FI2 which is (h3 (d, δ ), 1 − h4 (d))-forcing (with h4 (d) > 0) such that maxs∈Q0 |Qs | ≤
2 mins∈Q0 |Qs | and setting Q to be the multiset
{s ⊗ t : s ∈ Q0 ,t ∈ Qs } =
[
(s ⊗ Qs ),
s∈Q0
the elements of Q belong to B ∩ h5 (d)B0 .
Proof of Claim. Let C be the multiset {u1 ⊗ · · · ⊗ ua : ui ∈ Fn2i } and let D be the multiset {ua+1 ⊗ · · · ⊗ ud :
ui ∈ Fn2i }. For each s ∈ C, let Ds = {t ∈ D : s ⊗t ∈ B0 }. Also, let C0 = {s ∈ C : |Ds | ≥ (δ /2)|D|}. Clearly,
|C0 | ≥ (δ /2)|C|. By Lemma 2.12, for every s ∈ C0 there exists a g1 (d, δ )-system Rs in g2 (d)Ds . By (H’)
applied to dimension a, there exists a multiset Q0 with elements chosen from
I\J
C ∩ (g3 (d)C0 ) ∩ (WJ⊥ ⊗ F2 )
\
J⊂I,J6=I,J6=0/
which is (g4 (d, δ , k), 1 − g5 (d))-forcing for some g5 (d) > 0. For every s ∈ Q0 , choose s1 , . . . , sl ∈ C0 with
l ≤ g3 (d) such that s = s1 + · · · + sl , and let Ps = i≤l Rs . By Lemma 2.11, Ps contains a g6 (d, δ )-system,
T
therefore |Ps | ≥ g7 (d, δ )|D| for some g7 (d, δ ) > 0. By (H) for d − a, for every s ∈ Q0 there exists a
multiset Qs with elements chosen from D ∩ g8 (d)Ps which is (g9 (d, δ ), 1 − g10 (d))-forcing for some
g10 (d) > 0. Notice that if we repeat every element of Qs the same number of times, then the multiset we
obtain is still (g9 (d, δ ), 1 − g10 (d))-forcing, so we may assume that maxs∈Q0 |Qs | ≤ 2 mins∈Q0 |Qs |. Define
Q = {s ⊗ t : s ∈ Q0 ,t ∈ Qs } =
[
(s ⊗ Qs ).
s∈Q0
Note that as Rs ⊂ g2 (d)Ds for all s ∈ C0 , we have s ⊗ Rs ⊂ g2 (d)B0 for all s ∈ C0 . But the elements of
Q0 are chosen from g3 (d)C0 , so s ⊗ Ps ⊂ g3 (d)g2 (d)B0 for all s ∈ Q0 . Finally, the elements of Qs are
chosen from g8 (d)Ps , so the elements of s ⊗ Qs are chosen from g8 (d)g3 (d)g2 (d)B0 for every s ∈ Q0 .
This completes the proof of the claim.
Now let us show that Q does indeed satisfy the conclusion of the lemma. Since for every s ∈ Q0 , Qs is
(h3 (d, δ ), 1 − h4 (d))-forcing, there exist subspaces VJ (s) ⊂ FJ2 for every J ⊂ I c , J 6= 0,
/ with dimension at
I c
most h3 (d, δ ) such that the set of arrays t ∈ F2 with t.q = 0 for at least (1 − h4 (d))|Qs | choices q ∈ Qs is
contained in
I c \J
∑ VJ (s) ⊗ F2 .
J⊂I c ,J6=0/
Let f2 (d) = (1/4)h2 (d)h4 (d). Now if r ∈ G has r.q = 0 for at least (1 − f2 (d))|Q| choices q ∈ Q,
then by averaging, for at least (1 − (1/2)h2 (d))|Q0 | choices s ∈ Q0 , we have r.(s ⊗ t) = 0 for at least
(1 − h4 (d))|Qs | choices t ∈ Qs . Therefore (noting that r.(s ⊗ t) = (rs).t),
I c \J
rs ∈ ∑ VJ (s) ⊗ F2
J⊂I c ,J6=0/
for at least (1 − (1/2)h2 (d))|Q0 | choices s ∈ Q0 .
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 19
T IMOTHY G OWERS AND O LIVER JANZER
Now let
h2 (d)
g11 (d, k) = and g12 (d, δ , k) = h3 (d, δ ) + 2d+1 k.
2 · 2k
c
Let X be the subset of FI2 consisting of those arrays x such that for at least g11 (d, k)|Q0 | choices s ∈ Q0 ,
there exists some
t(s) ∈ VI c (s) + ∑ ((FJ2 ⊗WJ c )s)
J⊂I,J6=I
for which x − t(s) is g12 (d, δ , k)-degenerate. (Here and below, for a subspace L ⊂ G and an array s ∈ FI2 ,
c
we write Ls for the subspace {rs : r ∈ L} ⊂ FI2 .) Choose a maximal subset {x1 , . . . , xm } ⊂ X such that no
xi − x j with i 6= j is 2g12 (d, δ , k)-degenerate. Then there do not exist i 6= j, s ∈ Q0 and
t ∈ VI c (s) + ∑ ((FJ2 ⊗WJ )s) c
J⊂I,J6=I
with xi − t and x j − t both g12 (d, δ , k)-degenerate. It follows, by the definition of X and the fact that the
dimension of
VI c (s) + ∑ ((FJ2 ⊗WJ c )s)
J⊂I,J6=I
d
is at most h3 (d, δ ) + 2d k, that mg11 (d, k)|Q0 | ≤ |Q0 | · 2h3 (d,δ )+2 k , and therefore that m ≤ g13 (d, δ , k).
Thus, there exists a set Y ⊂ X of size at most g13 (d, δ , k) such that for any x ∈ X, there exists some y ∈ Y
such that x − y is 2g12 (d, δ , k)-degenerate. Let Z = span(Y ). Then dim(Z) ≤ g13 (d, δ , k), and for every
x ∈ X there is some z ∈ Z such that x − z is 2g12 (d, δ , k)-degenerate.
Let
c
r ∈ W[d] + ∑ (WJ ⊗ FJ2 + FJ2 ⊗WJ c ) + ∑ FJ2 ⊗ HJ c (r)
J≺I JI
with dim(HJ c (r)) ≤ k and the property that r.q = 0 for at least (1 − f2 (d))|Q| choices q ∈ Q. Let Q0 (r)
be the submultiset of Q0 consisting of those s ∈ Q0 for which
I c \J
rs ∈ ∑ VJ (s) ⊗ F2 .
J⊂I c ,J6=0/
As we have seen two paragraphs above,
1
0
|Q (r)| ≥ 1 − h2 (d) |Q0 |.
2
Note that we can write r = r1 + r2 + r3 + r4 where
c c
r1 ∈ ∑ WJ ⊗ FJ2 , r2 ∈ ∑ (WJ ⊗ FJ2 + FJ2 ⊗WJ ) + ∑ FJ2 ⊗ HJ (r),
c c
J⊂I,J6=I,J6=0/ J≺I,J6⊂I J I
r3 ∈ W[d] + ∑ FJ2 ⊗WJ c and r4 ∈ FI2 ⊗ HI c (r).
J⊂I,J6=I,J6=0/
Since the elements of Q0 belong to
I\J
(WJ⊥ ⊗ F2 ),
\
J⊂I,J6=I,J6=0/
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 20
S UBSETS OF C AYLEY G RAPHS T HAT I NDUCE M ANY E DGES
we have r1 s = 0 for every s ∈ Q0 .
Since dim(WJ ), dim(WJ c ), dim(HJ c (r)) ≤ k, r2 s is 2d+1 k-degenerate. Indeed, we have s ∈ Q0 , so also
s ∈ C, therefore for any J ⊂ [d − 1] we may write s = s1 ⊗ s2 where s1 ∈ FI∩J I∩J c
2 and s2 ∈ F2 . Then
c c c
(WJ ⊗ FJ2 )s ⊂ (WJ s1 ) ⊗ F2I ∩J .
c
Hence, if J 6⊂ I, then any tensor in (WJ ⊗ FJ2 )s is k-degenerate. Similarly, any tensor in (FJ2 ⊗WJ c )s or in
(FJ2 ⊗ HJ c (r))s is k-degenerate, so r2 s is indeed 2d+1 k-degenerate.
Also,
r3 s ∈ ∑ ((FJ2 ⊗WJ c )s).
J⊂I,J6=I
It follows that for every s ∈ Q0 (r), there exists some
t(s) ∈ VI c (s) + ∑ ((FJ2 ⊗WJ )s) c
J⊂I,J6=I
such that r4 s − t(s) is g12 (d, δ , k) = (h3 (d, δ ) + 2d+1 k)-degenerate (we have used that dim(VJ (s)) ≤
h3 (d, δ )). In particular, if t 6∈ X, then the number of choices s ∈ Q0 (r) for which r4 s = t is at most
g11 (d, δ , k)|Q0 |. On the other hand, notice that r4 s ∈ HI c (r) for every s ∈ Q0 . Since |HI c (r)| ≤ 2k , it
follows that r4 s ∈ X for at least
1
|Q0 (r)| − 2k g11 (d, δ , k)|Q0 | = |Q0 (r)| − h2 (d)|Q0 | ≥ (1 − h2 (d))|Q0 |
2
choices s ∈ Q0 .
Let X(r) = X ∩ HI c (r). Let t1 , . . . ,tα be a maximal linearly independent subset of X(r) and extend
it to a basis t1 , . . . ,tα ,t10 , . . . ,tβ0 for HI c (r). Now if a linear combination of t1 , . . . ,tα ,t10 , . . . ,tβ0 is in X,
then the coefficients of t10 , . . . ,tβ0 are all zero. Write r4 = ∑i≤α si ⊗ ti + ∑ j≤β s0j ⊗ t 0j for some si , s0j ∈ FI2 .
Since r4 q ∈ X for at least (1 − h2 (d))|Q0 | choices q ∈ Q0 , we have, for all j, that s0j .q = 0 for at least
(1 − h2 (d))|Q0 | choices q ∈ Q0 . Thus, as Q0 is (h1 (d, δ , k), 1 − h2 (d))-forcing, there exist subspaces
LJ ⊂ FJ2 (J ⊂ I, J 6= 0), / not depending on r and of dimension at most h1 (d, δ , k), such that
I\J
s0j ∈ ∑ LJ ⊗ F2
J⊂I,J6=0/
for all j. Thus,
c
r4 ∈ ∑ si ⊗ ti + ∑ LJ ⊗ FJ2 .
i≤α J⊂I,J6=0/
Moreover, for every i ≤ α, we have ti ∈ X, so there exist zi ∈ Z such that ti − zi is 2g12 (d, δ , k)-degenerate.
It follows that
c
r4 ∈ FI2 ⊗ Z + ∑ FJ2 ⊗ KJ0 c (r) + ∑ LJ ⊗ FJ2
J⊃I,J6=I,J⊂[d−1] J⊂I,J6=0/
Jc
for some KJ0 c (r) ⊂ F2 of dimension at most α · 2g12 (d, δ , k) ≤ 2k · 2g12 (d, δ , k). This finishes the proof
of the lemma.
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 21
T IMOTHY G OWERS AND O LIVER JANZER
We are now in a position to complete the proof of Lemma 2.1.
Proof of Lemma 2.1. As remarked earlier, it suffices to prove that (H) holds for all d. But (H) implies
(H’), and (H) holds for d = 1, therefore it suffices to prove, assuming that (H’) holds for all d 0 < d, that
(H) holds for d.
[d]
Let B0 given as in the definition of (H). By Lemma 2.16 (iv), there exist Q0/ ⊂ B ∩ 4B0 and V[d] ⊂ F2
of dimension at most g1 (δ ) such that if r.q = 0 for at least (3/4)|Q0/ | choices q ∈ Q0/ , then r can be written
as r = x + y, where x ∈ V[d] and y is g2 (d, δ )-degenerate. By repeated application of Lemma 2.17, for all
I ⊂ [d − 1] with I 6= 0,
/ in the order given by ≺, we obtain for each such I a multiset QI with elements
c
chosen from B ∩ g3 (d)B0 , subspaces VI ⊂ FI2 , VI c ⊂ FI2 of dimension at most g4 (d, δ ), and we also obtain
a constant g5 (d) > 0 such that the following statement holds. If r ∈ G is such that for each I ⊂ [d − 1] we
have that r.q = 0 for at least (1 − g5 (d))|QI | choices of q ∈ QI , then
c
r ∈ V[d] + ∑ (VI ⊗ FI2 + FI2 ⊗VI c ).
I⊂[d−1],I6=0/
Moreover, after taking several copies of each QI , we may assume that maxI |QI | ≤ 2 minI |QI |. Now let
g5 (d)
g6 (d) = ,
2 · 2d−1
let Q = I QI , and suppose that r.q = 0 for at least (1 − g6 (d))|Q| choices q ∈ Q. Then, by averaging, for
S
every I ⊂ [d − 1] we have r.q = 0 for at least (1 − g5 (d))|QI | choices of q ∈ QI . Thus, Q is (g7 (d, δ ), 1 −
g6 (d))-forcing, where g7 (d, δ ) = max(g1 (δ ), g4 (d, δ )).
3 The counterexample to Question 1.9
We shall now present an example that gives a negative answer to Question 1.9. The example is easy
to define, but it takes a little work to prove that it has the properties we require. In what follows, let
G = Fn2 . For a vector v ∈ G write |v| for the number of entries equal to 1 in v. Then our set A will be
{v ∈ Fn2 : |v| ≤ n/2 − 1020 n3/4 }, and our set B will be {v ∈ Fn2 : |v| = n1/2 }.
We prove that A is η-closed with respect to B where η > 0 is some absolute constant.
First we show that when n is sufficiently large, the probability that a uniformly random element u ∈ A
has |u| ≤ n/2 − 1020 n3/4 − 1050 n1/4 is at least some absolute constant η1 > 0. Note that
n l
k (k + 1)(k + 2) · · · (k + l) k
n = ≥
k+l
(n − k − l + 1)(n − k − l + 2) · · · (n − k) n−k
n/2−10 n 21 3/4 n /2−10 l1/4 21 21
k l 2·10
When k ≥ n/2 − 1021 n3/4 , then ( n−k ) ≥ ( n/2+10 l l
21 n3/4 ) = ( n1/4 /2+1021 ) = (1 − n1/4 /2+1021 ) . It is not hard
to see that when l = 1050 n1/4 , then this is at least some absolute constant c > 0. This means that
1050 n1/4 1050 n1/4
n n
∑ ≥c ∑ ,
i=0 n/2 − 1020 n3/4 − 1050 n1/4 − i i=0 n/2 − 1020 n3/4 − i
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 22
S UBSETS OF C AYLEY G RAPHS T HAT I NDUCE M ANY E DGES
which implies that the probability that a uniformly random element u ∈ A has |u| ≤ n/2 − 1020 n3/4 −
1050 n1/4 is at least some absolute constant η1 > 0.
We now show that when n is sufficiently large, u ∈ Fn2 has |u| ≤ n/2 − 1020 n3/4 − 1050 n1/4 and v ∈ B
is uniformly randomly chosen, then with probability at least 1/2, we have u + v ∈ A. For simplicity we
assume that |u| = n/2 − 1020 n3/4 − 1050 n1/4 . Then it suffices to prove that with probability at least 1/2,
we have
n1/2
u·v ≥ − 1040 n1/4 , (3.1)
2
where to define the dot product we view u and w as elements of Rn .
Let m = n1/2 and let w1 , . . . , wm be standard basis vectors of Fn2 , chosen independently and uniformly
at random. Note that the expected number of i 6= j such that wi = w j is at most 1, so almost surely this
number is at most log n. In particular, almost surely we have n1/2 − 2 log n ≤ |w1 + · · · + wm | ≤ n1/2 .
Choose uniformly randomly an element v ∈ B with minimal Hamming distance from w1 + · · · + wm ∈ Fn2 .
This algorithm defines a uniformly random element of v ∈ B, and almost surely u · v ≤ u · w1 + · · · + u ·
wm + 4 log n. However, u · w1 + · · · + u · wm is distributed as Bin(n1/2 , 1/2 − 1020 n−1/4 − 1050 n−1/2 ). By
1/2
Chernoff’s inequality, this is at least n 2 − 1030 n1/4 with probability at least 9/10, say, so equation (3.1)
holds with probability more than 1/2. Hence, A is indeed (B, η)-closed for some positive absolute
constant η.
What we shall prove next is that for this η, with ε = 0.99, say, there do not exist c, δ and l with the
properties described in Question 1.9. In fact, we shall prove the slightly stronger statement that for any
δ > 0 and positive integer l, if n is sufficiently large then there do not exist C ⊂ A + lB and B0 ⊂ B with
|B0 | ≥ δ |B| such that C is (B0 , 0.99)-closed. Since for sufficiently large n, we have A + lB ⊂ A0 = {v ∈
Fn2 : |v| ≤ n/2 − 1015 n3/4 }, it suffices to prove the same statement but with A + lB replaced by A0 . From
now on, we always assume that n is sufficiently large.
The proof relies on two lemmas and a definition.
Lemma 3.1. If B0 ⊂ B has |B0 | ≥ δ |B|, then µc
B0 (u) ≥ 0.98 for at most exp(n
2/3 ) vectors u ∈ Fn .
2
Definition 3.2. Given B0 ⊂ B, we say u ∈ A0 is B0 -compatible if the number of w ∈ B0 with |u + w| ≤ |u|
is at least |B0 |/3.
Note that if we fix some u ∈ A0 and take a random w ∈ B, then the probability that |u + w| ≤ |u| is
much less than 1/3. Indeed, writing X for the expected number of indices i for which wi = 1 and ui = 0,
and Y for the expected number of indices i for which wi = 1 and ui = 1, we have E[X −Y ] ≥ 2 · 1015 n1/4 ,
while the standard deviation of X −Y is around n1/4 . So X ≤ Y holds with quite small probability.
Thus, for any large B0 ⊂ B, intuitively we expect only a small proportion of elements of A0 to be
B0 -compatible. The next lemma makes this precise.
Lemma 3.3. Let B0 ⊂ B have |B0 | ≥ δ |B|. Then the number of those u ∈ A0 which are B0 -compatible is at
most exp(−n3/4 )|A0 |.
Let us see why these two lemmas are sufficient. Suppose that C ⊂ A0 is (B0 , 0.99)-closed for some B0 ⊂ B
with |B0 | ≥ δ |B|. Let w ∈ B0 be chosen at random. Then the expected number of u ∈ C such that u + w ∈ C
is at least 0.99|C|, so by considering all such pairs {u, u + w} and noting that (u + w) + w = u, we see that
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 23
T IMOTHY G OWERS AND O LIVER JANZER
there are on average at least (0.99/2)|C| choices of u ∈ C such that |u + w| ≤ |u|. Therefore, if u ∈ C is
chosen at random, the average number of w ∈ B0 such that |u + w| ≤ |u| is at least (0.99/2)|B0 |. It follows
that for at least |C|/10 elements of C the number of such w is at least |B0 |/3, so at least |C|/10 elements
of A0 are B0 -compatible. Lemma 3.3 then implies that C has density at most 10 exp(−n3/4 ) in G. Let us
write γ for this density.
On the other hand, since C is (B0 , 0.99)-closed, we have the inequality
∑ µcB (u)|Ĉ(u)|2 ≥ 0.99 ∑ |Ĉ(u)|2 ,
0
u∈G u∈G
which implies that
2 2
∑ B0 (u)|Ĉ(u)| ≥ 0.01 ∑ |Ĉ(u)| .
µc
B0 (u)≥0.98
u∈G:µc u∈G
Using Lemma 3.1, together with the observations that µcB0 (u) ≤ 1 and |Ĉ(u)| ≤ γ for every u ∈ G and that
∑u∈G |Ĉ(u)|2 = γ, we deduce that exp(n2/3 )γ 2 ≥ 0.01γ, so γ ≥ 0.01 exp(−n2/3 ). For sufficiently large n,
this contradicts the upper bound for γ that we obtained a few lines above.
It remains to prove the two lemmas. The next two results are preparation for the proof of Lemma 3.1.
Lemma 3.4. Let V be a subspace of Fn2 of dimension d such that every v ∈ V has |v| ≥ n8/15 . Then V
has a basis {v1 , . . . , vd } such that for every i, the set Ii = {k ≤ n : vi (k) = 1, v j (k) = 0 for all j 6= i} has
size at least n8/15 /2d−1 . Here and below, the kth entry of a vector v is denoted by v(k).
Proof. We use induction on d. The case d = 1 easily follows from the assumption on V . Let V 0 have
dimension d + 1 and suppose that for a d-dimensional subspace V ⊂ V 0 , v1 , . . . , vd and I1 , . . . , Id have
been chosen satisfying the requirements. Choose some v ∈ V 0 \V . Replacing v by v − v1 if necessary,
we may assume that v(k) = 0 for at least |I1 |/2 choices k ∈ I1 . Similarly, we may assume that v(k) = 0
for at least |Ii |/2 choices k ∈ Ii for every i ≤ d. Thus, there exist subsets J1 , . . . , Jd of {1, . . . , n} of size
at least n8/15 /2d each such that for every i ≤ d and every k ∈ Ji we have vi (k) = 1 but v j (k) = 0 for
all j with j 6= i, j ≤ d, and v(k) = 0. Let J = {k ≤ n : v(k) = 1}. By the assumption on V 0 , we have
|J| ≥ n8/15 . Now it is easy to see that we can define v01 to be v1 or v1 − v and achieve that v01 (k) = 0 for
at least |J|/2 choices of k ∈ J. Similarly, we can define v02 , . . . , v0d such that each v0i is vi or vi − v and
v01 (k) = · · · = v0d (k) = 0 for at least |J|/2d choices k ∈ J. Then for any i, j ≤ d, we have v0i (k) = vi (k) for
every k ∈ J j , and it follows that for any i ≤ d and k ∈ Ji , we have v0i (k) = 1 but v0j (k) = 0 for all j 6= i, and
v(k) = 0. Thus, the set {v01 , . . . , v0d , v} is suitable so the lemma is proved.
Corollary 3.5. Let t be a positive integer not depending on n and let V be a subspace of Fn2 of dimension
t such that every v ∈ V has |v| ≥ n8/15 . Then the density of those w ∈ B with w · v = 0 for all v ∈ V is less
than (1.9)−(t−1) .
Proof. We shall be slightly sketchy about the some of the details when they are very standard. As always,
we assume that n is sufficiently large. Let v1 , . . . , vt be a basis given by Lemma 3.4 with d = t. Let w be
a random vector in B, let i < t, and let us consider the probability that w.vi = 0 given that w.v j = 0 for
every j < i.
The expected number of non-zero coordinates of w in the union of the two intervals Ii and Ii+1 is
at least n1/30 /2t−1 , which tends to infinity, and the probability that it is at least half this number tends
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 24
S UBSETS OF C AYLEY G RAPHS T HAT I NDUCE M ANY E DGES
to 1 (very rapidly). If we condition further on this number, and if it is indeed at least n1/30 /2t , then the
probability that the number of non-zero coordinates of w in Ii is even is almost exactly 1/2. Therefore, the
probability that w.vi = 0 given that w.v j = 0 for every j < i is less than 1/(1.9).
Since this is true for every i ≤ t − 1, we obtain the result.
Proof of Lemma 3.1. Suppose that the result is not true. Let r be a positive integer to be specified later
and pick R = {u1 , . . . , ur } such that µc
B0 (ui ) ≥ 0.98 for i = 1, 2, . . . , r. Then for each i, we have ui · w = 0
for at least 99% of all w ∈ B0 . Therefore there is a subset B00 ⊂ B0 with |B00 | ≥ |B0 |/2 such that each
w ∈ B00 has ui · w = 0 for at least 98% of the ui . The number of subsets of R of size (49/50)r is at most
r r
= ≤ (50e)r/50 ≤ (1.8)49r/50 .
49r/50 r/50
Let t = 49r/50. Then there exists a subset T of R of size t such that the number of w ∈ B with w · u = 0
for all u ∈ T is at least
|B00 | δ
≥ |B|.
(1.8)t 2 · (1.8)t
Choose the smallest positive integer t with
δ
≥ (1.9)−(t−1)
2 · (1.8)t
(and with r = 50t/49 an integer). Then the density of those w ∈ B with w · u = 0 for all u ∈ T is at least
(1.9)−(t−1) .
Now let Q be the set of all u ∈ Fn2 with µc 2/3 ). Let t and
B0 (u) ≥ 0.98 and assume that |Q| ≥ exp(n
r be as above and choose u1 , . . . , ur ∈ Q such that for every j, the (Hamming) distance of u j from
span(u1 , . . . , u j−1 ) is at least n8/15 . (This is possible because the number of u ∈ Fn2 with Hamming
distance at most n8/15 from an r-dimensional vector space is at most 2r exp(O(n8/15 log n)) < exp(n2/3 ).)
Applying Corollary 3.5 to V = span(T ), where T is a subset of {u1 , . . . , ur } of size t, we find that the
density of those w ∈ B with w · u = 0 for all u ∈ T is less than (1.9)−(t−1) , which is a contradiction.
Proof of Lemma 3.3. In this proof, unless specified otherwise, we will view Fn2 as a subset of Rn and
accordingly, the dot product is defined as u · w = ∑i u(i)w(i) where the summation is in R. Then
|u + w| ≤ |u| is equivalent to u · w ≥ |w|/2. Hence u is B0 -compatible if u · w ≥ |w|/2 for at least |B0 |/3
vectors w ∈ B0 .
Let t be a fixed positive integer, not depending on n, to be specified later. For a multiset T =
{u1 , . . . , ut } ⊂ A0 write sT = ∑ti=1 ui − (t/2)q where q is the vector in Fn2 consisting of ones. Let ak = sT (k)
and σT2 = ∑nk=1 a2k . We say that T is bad if σT2 ≥ 1000tn.
Claim 1. If T is not bad, then the number of w ∈ B with ui · w ≥ |w|/2 for all i is at most |B|/100 t .
Proof of Claim 1. If ui · w ≥ |w|/2 for all i, then sT · w ≥ 0. Note that sT · w = ∑k≤n ak w(k). We shall view
w as a random variable, chosen uniformly of all elements of B. What we need to prove is that
" #
1
P ∑ ak w(k) ≥ 0 ≤ .
k≤n 100 t
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 25
T IMOTHY G OWERS AND O LIVER JANZER
Let m = n1/2 and let w1 , . . . , wm be standard basis vectors of Fn2 , chosen independently and uniformly
at random. Note that the expected number of i 6= j such that wi = w j is at most 1, so almost surely this
number is at most log n. In particular, almost surely we have n1/2 − 2 log n ≤ |w1 + · · · + wm | ≤ n1/2 .
Choose uniformly randomly an element w ∈ B with minimal Hamming distance from w1 + · · · + wm ∈ Fn2 .
This algorithm defines a uniformly random element of w ∈ B such that almost surely we have
! !
∑ ∑ wi (k) − w(k) ≤ ∑ ∑ wi (k) − ∑ wi (k) + ∑ ∑ wi (k) − w(k)
k≤n i≤m k≤n i≤m i≤m k≤n i≤m
≤ 2 log n + 2 log n = 4 log n,
where all the summations are taken in R, except ∑i≤m wi , which is taken in Fn2 .
At this point, we apply the following version of Chernoff’s inequality, which appears as Theorem 3.4
in [2].
Let Xi (1 ≤ i ≤ m) be independent random variables satisfying Xi ≤ E[Xi ] + M, for 1 ≤ i ≤ m. We
consider the sum X = ∑i Xi with expectation E[X] = ∑i E[Xi ] and variance Var(X) = ∑i Var(Xi ). Then,
we have
λ2
P(X ≥ E[X] + λ ) ≤ exp − .
2(Var(X) + Mλ /3)
We now take Xi = ∑k≤n ak wi (k) for 1 ≤ i ≤ m. Since |ak | ≤ t, the conditions of the theorem hold with
M = 2t. As ui ∈ A0 for all i, we have ∑k≤n ak ≤ t(n/2 − 1015 n3/4 ) − tn/2 = −1015tn3/4 . Then
∑k≤n ak 1
E[X] = m ≤ − 1015tn1/4 ,
n 2
and by the assumption that T is not bad,
∑k≤n a2k
Var(X) ≤ m ≤ 1000tn1/2 .
n
Thus, taking λ = 1014tn1/4 in the above theorem it follows that
" #
1028t 2 n1/2
14 1/4 1
P ∑ ∑ ak wi (k) ≥ −10 tn ≤ exp − ≤ t
.
i≤m k≤n
1/2 14
2(1000tn + 2t · 10 tn /3) 1/4 2 · 100
But
∑ ak w(k) = ∑ ak wi (k) + ∑ ak (w(k) − ∑ wi (k))
k≤n i≤m,k≤n k≤n i≤m
≤ ∑ ak wi (k) + t ∑ (w(k) − ∑ wi (k)) ,
i≤m,k≤n k≤n i≤m
and ∑k≤n |(w(k) − ∑i≤m wi (k))| ≤ 4 log n almost surely, it follows that
" #
1
P ∑ ak w(k) ≥ 0 ≤
k≤n 100 t
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 26
S UBSETS OF C AYLEY G RAPHS T HAT I NDUCE M ANY E DGES
and Claim 1 is proved.
Claim 2. If u1 , u2 , . . . , ut are independently and uniformly randomly chosen elements of A0 then the
probability that T = {u1 , . . . , ut } is bad is o(exp(−n7/8 )).
Proof of Claim 2. Recall that T is bad if and only if
!2
∑ ∑ ui (k) − t/2 ≥ 1000tn.
k≤n i≤t
u1 , . . . , ut are randomly chosen from A0 but with probability 1 − o(exp(n−7/8 )) all of them have |ui | ≥
n/2 − n99/100 so we may assume that u1 , . . . , ut are randomly chosen from the set
A00 = {v ∈ Fn2 : n/2 − n99/100 ≤ |v| ≤ n/2 − 1015 n3/4 }.
It is not hard to see that we can write ui = xi + yi where xi and yi are random variables taking values in Fn2
and having the property that xi (k) are independent Bernoulli with parameter 1/2 and |yi | ≤ 2n99/100 with
probability 1 − o(exp(−n7/8 )). Then it suffices to prove that
!2
P ∑ ∑ xi (k) − t/2 ≥ 500tn = o(exp(−n7/8 )).
k≤n i≤t
Let Xi = (∑i≤t xi (k) − t/2)2 for 1 ≤ k ≤ n. Then the Xi are i.i.d. random variables with E[Xi ] = t/4 and
Var(Xi ) = O(1). Thus, by Theorem 3.4 from [2] (which is the theorem stated above), taking λ = 100tn
and M = t 2 , it follows that
!2
(100tn)2
P ∑ ∑ xi (k) − t/2 ≥ 500tn ≤ exp −
2 · 100tn/3)
= o(exp(−n7/8 )),
k≤n i≤t 2(nO(1) + t
finishing the proof of Claim 2.
We are now in a position to complete the proof of the lemma. Let t be the smallest positive integer
with
1 δ
t
< .
100 100(6e)t
Let the density of B0 -compatible elements in A0 be α. Pick v1 , . . . , v6t independently and uniformly
randomly from A0 . Then with probability α 6t , every vi is B0 -compatible. If that is the case, then for every
i, there are at least |B0 |/3 vectors w ∈ B0 with vi · w ≥ |w|/2. It follows that there is some B00 ⊂ B0 with
|B00 | ≥ |B0 |/100 such that for every w ∈ B00 we have vi · w ≥ |w|/2 for at least t choices of i. The number of
t-sets in {v1 , . . . , v6t } is at most (6e)t so there must exist a t-set T = {u1 , . . . , ut } ⊂ {v1 , . . . , v6t } (multisets
are allowed) such that the number of w ∈ B with ui · w ≥ |w|/2 for each i is at least
|B00 | δ |B| |B|
≥ > .
(6e)t 100(6e)t 100 t
By Claim 1, it follows that T is bad. Thus, the probability that T = {u1 , . . ., ut } is bad when u1 , . . . , ut are
independently and uniformly randomly chosen from A0 , is at least α 6t / 6tt . Hence, by Claim 2, we have
α 6t / 6tt = o(exp(−n7/8 )), and we get α = o(exp(−n3/4 )).
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 27
T IMOTHY G OWERS AND O LIVER JANZER
Acknowledgement
We are grateful to both referees for their valuable suggestions.
References
[1] B OAZ BARAK , P RAVESH K. KOTHARI , AND DAVID S TEURER: Small-set expansion in Shortcode
Graph and the 2-to-2 Conjecture, 2019. [doi:10.4230/LIPIcs.ITCS.2019.9, arXiv:1804.08662] 3
[2] FAN C HUNG AND L INYUAN L U: Concentration inequalities and martingale inequalities: A survey.
Internet Mathematics, 3(1):79–127, 2006. Available at Project Euclid. 26, 27
[3] B EN G REEN: The asymmetric Balog-Szemerédi-Gowers theorem. Lecture notes. 5
[4] O LIVER JANZER: Low analytic rank implies low partition rank for tensors, 2018. [arXiv:1809.10931]
16
[5] O LIVER JANZER: Polynomial bound for the partition rank vs the analytic rank of tensors, 2019.
[arXiv:1902.11207] 16
[6] S UBHASH K HOT: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp. 767–775.
ACM Press, 2002. [doi:10.1145/509907.510017] 2
[7] S UBHASH K HOT, D OR M INZER , AND M ULI S AFRA: Pseudorandom sets in Grassmann graph
have near-perfect expansion. In Proc. 59th FOCS, pp. 592–601. IEEE Comp. Soc. Press, 2018.
[doi:10.1109/FOCS.2018.00062] 2
[8] S HACHAR L OVETT: The analytic rank of tensors and its applications. Discrete Analysis, 2019:7, 10
pp. [doi:10.19086/da.8654, arXiv:1806.09179v5] 16
[9] T ERENCE TAO AND VAN H. V U: Additive Combinatorics. Cambridge Univ. Press, 2006.
[doi:10.1017/CBO9780511755149] 5, 12
AUTHORS
Timothy Gowers
Professor
Department of Pure Mathematics and Mathematical Statistics
University of Cambridge
w t gowers dpmms cam ac uk
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 28
S UBSETS OF C AYLEY G RAPHS T HAT I NDUCE M ANY E DGES
Oliver Janzer
Graduate student
Department of Pure Mathematics and Mathematical Statistics
University of Cambridge
oj224 cam ac uk
https://sites.google.com/view/oliver-janzer/home
ABOUT THE AUTHORS
T IMOTHY G OWERS was an undergraduate at the University of Cambridge, where he also
did his Ph. D. under the supervision of Béla Bollobás. His main research interest
is combinatorics, particularly those parts that lie at the interface with other areas of
mathematics. He is a Royal Society Research Professor, and holds this position at the
University of Cambridge.
O LIVER JANZER grew up in Budapest, Hungary. He obtained his Bachelor and Masters
degrees at the University of Cambridge, where he is currently a Ph. D. student of Timothy
Gowers. His main research interests are extremal graph theory and additive combina-
torics.
T HEORY OF C OMPUTING, Volume 15 (20), 2019, pp. 1–29 29