Bipartite graphs of approximate rank 1.

W. T. Gowers

§1. Introduction.

Quasirandomness is a central concept in graph theory, and has played an important part in arithmetic combinatorics as well. Roughly speaking, a notion of quasirandomness for a mathematical object such as a graph or a subset of a finite Abelian group is a property P such that any object that has P will automatically have many other properties that a randomly chosen object would be expected to have. For instance, a graph G with n vertices and p\binom{n}{2} edges is called c-quasirandom if there are at most (p^{4} + c)n^{4} ordered 4-cycles—that is, quadruples (x, y, z, w) of vertices such that xy, yz, zw and xw are all edges of G. If this property holds, then it can be shown that every set A of vertices in G spans approximately p\binom{|A|}{2} edges, just as we would expect if G were a random graph with edge-probability p.

This fact and many others like it go back to papers of Thomason [T] and Chung, Graham and Wilson [CGW]. (See also the fundamental papers of Alon [A] and Alon and Milman [AM].) In this paper we shall consider a generalization of the notion of a quasirandom graph to what we call a bipartite graph of approximate rank 1. A bipartite graph has this property if its bipartite adjacency matrix is a quasirandom perturbation of a rank-1 matrix, or equivalently, if the graph behaves like a random bipartite graph with the given degree sequence. To get some idea of what these properties mean, let us take a bipartite graph G with vertex sets X and Y, of cardinalities m and n, respectively, and let us write d_{1}(x) for the degree of a vertex x ∈ X and d_{2}(y) for the degree of a vertex in Y. If we choose large subsets A ⊂ X and B ⊂ Y, then how many edges do we expect there to be between A and B? Well, each vertex x ∈ A has a neighbourhood of size d_{1}(x) in Y, and if we choose a random neighbour of x then we “expect” that its distribution in Y will be roughly proportional to the degree sequence in Y. In particular, the probability that a random neigbour of x belongs to B should be approximately |E(G)|^{−1} ∑_{y∈B} d_{2}(y). (Note that |E(G)|, the number of edges of G, is equal to ∑_{y∈Y} d_{2}(y).) Therefore, we “expect” the number of edges between A and B to be about ∑_{x∈A} d_{1}(x)|E(G)|^{−1} ∑_{y∈B} d_{2}(y). Writing δ_{1}(x) and δ_{2}(y) for the normalized degrees d_{1}(x)/|Y | and d_{2}(y)/|X|, and β = |E(G)|/|X||Y | for the density of G, we can rewrite this as β^{−1} ∑_{x∈A} ∑_{y∈B} δ_{1}(x)δ_{2}(y).

If the number of edges between A and B really is always about β^{−1} ∑_{x∈A} ∑_{y∈B} δ_{1}(x)δ_{2}(y), then there is a certain sense, familiar from the conventional theory of quasirandom graphs, in which the adjacency matrix of G is approximated by the rank-1 matrix β^{−1}δ_{1} ⊗ δ_{2}. (This is notation for the function from X × Y to ℝ that takes the value β^{−1}δ_{1}(x) ⊗ δ_{2}(y) at (x, y).) Writing G(x, y) for the adjacency matrix, we shall prove that a certain graph-theoretic property is equivalent to the statement that the function f = G − β^{−1}δ_{1} ⊗ δ_{2} is quasirandom in a sense that is explained in [G3] and which we shall recall in the next section. We can then use known characterizations of quasirandom functions to deduce related characterizations of graphs with approximate rank 1.

This is not the first time that quasirandom graphs with prescribed degree sequences have been considered: indeed, Chung and Graham have a paper on the subject [CG]. However, they look at graphs rather than bipartite graphs. One can convert any graph into a bipartite graph by doubling up its vertex set, so our results imply some characterizations of the class of graphs considered by Chung and Graham (we have not tried to deduce all their results, or even thought about whether this can be done). However, there is no obvious way of deducing our results from theirs, since a rank-1 bipartite graph has rank 2 if it is considered as a graph. (In case this remark is unclear, if G is a bipartite graph with vertex sets X and Y, then we use the term “adjacency matrix” for the obvious corresponding function defined on X ×Y. However, if we think of G as a graph with vertex set X ∪Y that just happens to be bipartite, then its adjacency matrix is a function defined on (X ∪ Y)^{2}. This adjacencey matrix will contain two blocks, each a copy of the bipartite adjacency matrix.)

The motivation for our results is not generalization for the sake of it, but the fact that graphs of approximate rank 1 arise naturally in the context of a proof in [G2] of the Balog-Szemerédi theorem [BS]. In the fourth section of the paper, we shall prove that if G is any dense bipartite graph with vertex sets X and Y, then X has a large subset X′ such that the induced subgraph G(X′, Y) of G has approximate rank 1. This argument can be iterated (the next step would be to apply it to the graph G(X \ X′, Y)), and this results in a “one-sided” regularity lemma for G: we can partition the vertex set X into not too many sets X_{1}, …, X_{k} in such a way that almost all of the graphs G(X_{i}, Y) are “nice” in the sense that they have approximate rank 1.

Many of the results we state are more like templates: they illustrate techniques of proof that may have to be slightly modified for applications. In the fifth section, we give an example of this. We apply results from the earlier sections, some directly and some after appropriate modification, in order to obtain a new proof of a theorem of Green and Konyagin in additive combinatorics. Our bound is weaker than theirs, but the proof has certain interesting features and gives an idea of how the methods of this paper can be used.

2. Basic facts about quasirandom functions.

In this section we briefly review the properties we shall need from quasirandom functions. As is customary, we present the definition as a theorem: the theorem states that certain properties of a function are equivalent, and the function is called quasirandom if it has one of these properties. As is also customary, we state these properties in terms of constants c_{i}, and when we say that a property involving c_{i} implies a property involving c_{j} we mean that for every c_{j} > 0 there exists c_{i} > 0 such that the implication is valid. Actually, the dependences between the constants will be very important to us later, so we shall be explicit about them after we have stated the theorem in a more qualitative way.

Theorem 1.1. Let X and Y be sets of sizes m and n respectively and let f : X × Y → [−1, 1]. Then the following statements are equivalent.

(i) ∑_{x,x′∈X} ∑_{y,y′∈Y} f(x, y)f(x′, y)f(x, y′)f(x′, y′) ⩽ c_{1}m^{2}n^{2}.

(ii) For any pair of functions u : X → [−1, 1] and v : Y → [−1, 1] we have the inequality |∑_{x,y} f(x, y)u(x)v(y)| ⩽ c_{2}mn.

(iii) For any pair of sets X′ ⊂ X and Y′ ⊂ Y we have the inequality |∑_{x∈X′} ∑_{y∈Y′} f(x, y)| ⩽ c_{3}mn. Moreover, if ∑_{x,y} f(x, y) = 0 then they are also equivalent to the following further statement.

(iv) For any pair of sets X′ ⊂ X and Y′ ⊂ Y we have the inequality ∑_{x∈X′} ∑_{y∈Y′} f(x, y) ⩽ c_{4}mn.

We shall say that f is c-quasirandom if it has property (i) above with c_{1} = c.

A proof of this result can be found in [G3 §3], where the following dependences are obtained between the constants c_{i}. If (i) holds, then (ii) holds with c_{2} = c_{1}^{1/4}. It follows that (iii) and (iv) also hold with constant c_{1}^{1/4}. Moreover, these implications are valid for an arbitrary real-valued function f, and not just one that takes values in [−1, 1]. In the opposite direction, if (iv) and the extra hypothesis on f hold, then (ii) holds with c_{2} = 12c_{4}. If (iii) holds, then (ii) holds with c_{2} = 4c_{3}. Finally, if (ii) holds, then (i) holds with c_{1} = c_{2}.

The expression in (i) can be used to define a norm on functions f : X × Y → ℝ, which we shall denote by ∥f∥_{U_{2}} since it is closely related to the so-called U_{2}-norm for functions defined on finite Abelian groups. Let us briefly see why this is so. We shall prove the result for complex-valued functions.

Lemma 2.2. Let X and Y be finite sets, and for any four functions f_{1}, …, f_{4} from X ×Y to ℂ define [f_{1}, f_{2}, f_{3}, f_{4}] to be

𝔼_{x,x′∈X}𝔼_{y,y′∈Y} f_{1}(x, y)\overline{f_{2}(x, y′)}\overline{f_{3}(x′, y)}f_{4}(x′, y′) .

Define also ∥f∥_{U_{2}} to be [f, f, f, f]^{1/4}. Then we have the inequality

[f_{1}, f_{2}, f_{3}, f_{4}] ⩽ ∥f_{1}∥_{U_{2}}∥f_{2}∥_{U_{2}}∥f_{3}∥_{U_{2}}∥f_{4}∥_{U_{2}} .

Proof. This is a standard application of the Cauchy-Schwarz inequality. Observe that the left hand side can be written

𝔼_{x,x′}(𝔼_{y}f_{1}(x, y)\overline{f_{3}(x′, y)})(𝔼_{y′} \overline{f_{2}(x, y′)}f_{4}(x′, y′)) .

Applying the Cauchy-Schwarz inequality, we deduce that

[f_{1}, f_{2}, f_{3}, f_{4}] ⩽ [f_{1}, f_{1}, f_{3}, f_{3}]^{1/2}[f_{2}, f_{2}, f_{4}, f_{4}]^{1/2} .

The same argument, but interchanging the roles of x and y, shows that

[f_{1}, f_{2}, f_{3}, f_{4}] ⩽ [f_{1}, f_{2}, f_{1}, f_{2}]^{1/2}[f_{3}, f_{4}, f_{3}, f_{4}]^{1/2} .

Applying the second inequality to the two terms on the right of the first then proves the lemma. □

Lemma 2.3. Let X and Y be finite sets. Then the function ∥.∥_{U_{2}} defined in the previous lemma is a norm on the space ℂ^{X×Y}.

Proof. It is easy to check that [f, f, f, f] is non-negative, and zero only when f is zero. Indeed,

[f, f, f, f] = 𝔼_{x,x′} |𝔼_{y}f(x, y)\overline{f(x′, y)}|^{2} .

This is an expectation over pairs (x, x′) of terms that are real and non-negative. Moreover, if f(u, y) ≠ 0 for some u, y, then the term corresponding to the pair (u, u) is strictly positive. Obviously ∥λf∥ = |λ|∥f∥ for any λ ∈ ℂ, so it remains to check the triangle inequality. But

∥f + g∥^{4} = [f + g, f + g, f + g, f + g] .

Since [f_{1}, f_{2}, f_{3}, f_{4}] is “quadrilinear” (the inverted commas are there since there are complex conjugates to think about, but the word “quadrisesquilinear” is not exactly pretty), the term on the right splits up as a sum of 16 such terms, with each f_{i} equal to f or g. Applying Lemma 2.2 to each of these terms and then using the binomial theorem, we deduce easily that

[f + g, f + g, f + g, f + g] ⩽ (∥f∥ + ∥g∥)^{4} .

This proves the lemma. □

Thus, a quasirandom function is one with small U_{2}-norm. We have chosen the “correct” normalization for the U_{2}-norm, which is the one that has order of magnitude 1 for dense graphs regardless of the sizes of X and Y. Indeed, it is slightly more natural (though completely equivalent to the definition we gave above) to define f to be c-quasirandom if it satisfies the inequality

𝔼_{x,x′∈X}𝔼_{y,y′∈Y} f(x, y)f(x, y′)f(x′, y)f(x′, y′) ⩽ c .

A further characterization of quasirandom functions can be read out of a discussion in [G4]. If X and Y are sets of size m and n, respectively, and f : X × Y → ℝ is any function, then f can be written in the form ∑_{i=1}^{t} λ_{i}u_{i} × v_{i}, where t = min{m, n} and (u_{i}) and (v_{i}) are orthonormal sequences. This is known as the (or rather a) singular-value decomposition of f, and it is the non-symmetric analogue of the spectral decomposition of a symmetric matrix. We shall refer to the λ_{i} as the singular values of f. A proof that the singular-value decomposition exists is given as Theorem 2.6 in [G4] (but the result itself goes back to the 19th century). From the proof we have a fact that will be used later: that the largest modulus of any λ_{i} is equal to the largest inner product of f with any function u ⊗ v such that ∥u∥_{2} = ∥v∥_{2} = 1.

We remark that we are again using the uniform probability measures on X and Y to define our inner products. That is, when we say that ∥u_{i}∥_{2} = 1, we mean that (𝔼_{x∈X}u_{i}(x)^{2})^{1/2} = 1. More generally, if u and u′ are two functions from X to ℂ, we define ⟨u, u′⟩ to be 𝔼_{x∈X}u(x)\overline{u′(x)}, with similar definitions for Y. Similar definitions also apply to functions defined on X × Y. For example, if f : X × Y → ℂ, then we define ∥f∥_{2} to be (𝔼_{x∈X}𝔼_{y∈Y} |f(x, y)|^{2})^{1/2}.

The following result, which is easy to prove, is very similar to Lemma 2.8 of [G4]. We give the proof in the complex case, but will apply it only in the real case.

Lemma 2.4. Let X and Y be sets of size m and n, respectively, and let f : X × Y → ℂ be a function with a singular-value decomposition ∑_{i=1}^{t} λ_{i}u_{i} ⊗ v_{i}. Then ∑_{i} |λ_{i}|^{2} = ∥f∥_{2}^{2} and ∑_{i} |λ_{i}|^{4} = ∥f∥_{U_{2}}^{4}.

Proof. These two statements are both proved by setting f = ∑_{i} λ_{i}u_{i} ⊗ v_{i}, expanding out the right-hand sides of the identities to be proved, and exploiting the orthnormality of the sequences (u_{i}) and (v_{i}). We shall abbreviate 𝔼_{x∈X} and 𝔼_{y∈Y} by 𝔼_{x} and 𝔼_{y}, respectively. For the first identity,

∥f∥_{2}^{2} = ∑_{i=1}^{t} ∑_{j=1}^{t} λ_{i}\overline{λ_{j}}𝔼_{x}𝔼_{y}u_{i}(x)v_{i}(y)\overline{u_{j}(x)v_{j}(y)}

= ∑_{i=1}^{t} ∑_{j=1}^{t} λ_{i}\overline{λ_{j}}⟨u_{i}, u_{j}⟩⟨v_{i}, v_{j}⟩

= ∑_{i=1}^{t} |λ_{i}|^{2} ,

and for the second,

∥f∥_{U_{2}}^{4} = ∑_{i,j,k,l} λ_{i}\overline{λ_{j}λ_{k}}λ_{l}𝔼_{x,x′}𝔼_{y,y′}u_{i}(x)v_{i}(y)\overline{u_{j}(x)v_{j}(y′)u_{k}(x′)v_{k}(y)}u_{l}(x′)v_{l}(y′)

= ∑_{i,j,k,l} λ_{i}\overline{λ_{j}λ_{k}}λ_{l}⟨u_{i}, u_{j}⟩⟨v_{i}, v_{k}⟩⟨u_{l}, u_{k}⟩⟨v_{l}, v_{j}⟩

= ∑_{i=1}^{t} |λ_{i}|^{4} ,

since if a term is non-zero then we must have i = j, i = k, k = l and j = l, and then all four inner products are 1. □

From this we obtain the following extra characterization of quasirandom functions.

Theorem 2.5. Let X and Y be sets of size m and n, respectively, and let f : X × Y → ℂ be a function such that ∥f∥_{2} ⩽ 1. Let λ_{1}, …, λ_{k} be the singular values of f. Then the following three statements are equivalent.

(i) f is c_{1}-quasirandom.

(ii) ∑_{i} |λ_{i}|^{4} ⩽ c_{1}. (iii) max_{i} |λ_{i}| ⩽ c_{2}.

Proof. As we have remarked, f is c_{1}-quasirandom if and only if ∥f∥_{U_{2}}^{4} ⩽ c_{1}, so the equivalence between (i) and (ii) follows straight from the second part of Lemma 2.4.

It is trivial that ∑_{i} |λ_{i}|^{4} ⩽ max_{i} |λ_{i}|^{2} ∑_{i} |λ_{i}|^{2}. Therefore, if (iii) holds, then ∑_{i} |λ_{i}|^{4} ⩽ c_{2}^{2}, by the first part of Lemma 2.4 and our assumption that ∥f∥_{2} ⩽ 1. Conversely, if (ii) holds then we clearly have max_{i} |λ_{i}|^{4} ⩽ c_{1}, so (iii) holds with c_{2} = c_{1}^{1/4}. □

In practice, we shall apply Theorem 2.5 to functions f that map into the interval [−1, 1], so that it will be obvious that the L_{2}-estimate holds.

The next lemma gives us some information under weaker hypotheses than those of Lemma 2.4.

Lemma 2.6. Let X and Y be two finite sets, let f : X × Y → ℂ be a function and suppose that f = ∑_{i=1}^{t} λ_{i}u_{i} ⊗ v_{i}, with (u_{i}) an orthonormal sequence and (v_{i}) an arbitrary sequence of vectors of L_{2}-norm 1. Then ∑_{i} |λ_{i}|^{2} = ∥f∥_{2}^{2} and ∑_{i} |λ_{i}|^{4} ⩽ ∥f∥_{U_{2}}^{4}.

Proof. We shall make use of the calculations in Lemma 2.4. For the first statement, notice that all we use about the sequences (u_{i}) and (v_{i}) is the fact that δ_{ij} = ⟨u_{i}, u_{j}⟩⟨v_{i}, v_{j}⟩, which is true under our weaker hypotheses. (There is no mystery about this: if ⟨u, u′⟩ = 0 then it is easy to check that ⟨u ⊗ v, u′ ⊗ v′⟩ = 0 for any two vectors v and v′.)

For the second statement, notice that under the weaker hypotheses we can still use the orthonormality of the sequence (u_{i}) to replace the last line of the calculation by ∑_{i=1}^{t} ∑_{k=1}^{t} |λ_{i}|^{2}|λ_{k}|^{2}⟨v_{i}, v_{k}⟩⟨v_{k}, v_{i}⟩, which equals ∑_{i=1}^{t} ∑_{k=1}^{t} |λ_{i}|^{2}|λ_{k}|^{2}|⟨v_{i}, v_{k}⟩|^{2}. Since all terms are non-negative, this double sum is at least as big as its diagonal, which is ∑_{i=1}^{t} |λ_{i}|^{4} because ⟨v_{i}, v_{i}⟩ = 1 for every i. □

We finish this section with a further lemma about U_{2}-norms. It tells us that if f and g are close in the U_{2} norm, then for most pairs x, x ∈ X the numbers 𝔼_{y}f(x, y)f(x′, y) and 𝔼_{y}g(x, y)g(x′, y), which we think of as “joint degrees” in the two “graphs” f and g, are approximately equal.

Lemma 2.7. Let X and Y be finite sets and let f and g be functions from X × Y to ℂ. Then

𝔼_{x,x′} |𝔼_{y}(f(x, y)\overline{f(x′, y)} − g(x, y)\overline{g(x′, y)})|^{2} ⩽ ∥f − g∥_{U_{2}}^{2}(∥f∥_{U_{2}} + ∥g∥_{U_{2}})^{2} .

Proof. Let h = f − g. Then

𝔼_{y}(f(x, y)\overline{f(x′, y)} − g(x, y)\overline{g(x′, y)}) = 𝔼_{y}f(x, y)\overline{h(x′, y)} + E_{y}h(x, y)\overline{g(x′, y)} .

By Minkowski’s inequality,

\begin{aligned}(𝔼_{x,x′} |𝔼_{y} & f(x, y)\overline{h(x′, y)} + 𝔼_{y}h(x, y)\overline{g(x′, y)}|^{2})^{1/2} \\ & ⩽ (𝔼_{x,x′} |𝔼_{y}f(x, y)\overline{h(x′, y)}|^{2})^{1/2} + (𝔼_{x,x′} |𝔼_{y}h(x, y)\overline{g(x′, y)}|^{2})^{1/2} . \end{aligned}

Now 𝔼_{x,x′} |𝔼_{y}f(x, y)\overline{h(x′, y)}|^{2} is another way of writing [f, f, h, h], to use the notation of Lemma 2.2. Therefore, by that lemma, it is at most ∥f∥_{U_{2}}^{2}∥h∥_{U_{2}}^{2}. Similarly, 𝔼_{x,x′} |𝔼_{y}h(x, y)\overline{g(x′, y)}|^{2} is at most ∥g∥_{U_{2}}^{2}∥h∥_{U_{2}}^{2}. Putting all this information together gives the result. □

§3. Characterizing functions of approximate rank 1.

We are now ready to prove some results about functions from X × Y to ℝ that can be approximated by functions of rank 1. To obtain results about bipartite graphs, all one then needs to do is restrict attention to functions that take the value 0 or 1 everywhere.

We shall generalize concepts such as normalized degrees and density from graphs to functions in the obvious way. That is, if f : X × Y → ℝ and x ∈ X then we let δ_{1}(x) = 𝔼_{y}f(x, y). Similarly, if y ∈ Y then δ_{2}(y) is defined to be 𝔼_{x}f(x, y). Finally, the density d of G is 𝔼_{x,y}f(x, y). (Now that we are using normalized degrees, it is more convenient to use the letter d rather than β.) This density does not have to lie in the interval [0, 1], but for Theorem ??, which is the main result of the section, and the result that we shall apply later on, it will. We shall also write δ_{1}(x, x′) for the joint degree 𝔼_{y}δ(x, y)δ(x′, y).

Lemma 3.1. Let X and Y be finite sets and let h : X × Y → ℂ. Then

𝔼_{x}|𝔼_{y}h(x, y)|^{2} ⩽ ∥h∥_{U_{2}}^{2} .

Proof. This is a simple application of the Cauchy-Schwarz inequality:

(𝔼_{x}|𝔼_{y}h(x, y)|^{2})^{2} = (𝔼_{y,y′}𝔼_{x}h(x, y)\overline{h(x, y′)})^{2}
⩽ 𝔼_{y,y′} |𝔼_{x}h(x, y)\overline{h(x, y′)}|^{2}
= 𝔼_{x,x′}𝔼_{y,y′}h(x, y)\overline{h(x, y′)}\overline{h(x′, y)}h(x′, y′)
= ∥h∥_{U_{2}}^{4} ,

which implies the result. □

Lemma 3.2. If X and Y are finite sets and u : X → ℝ and v : Y → ℝ, then ∥u ⊗ v∥_{U_{2}} = ∥u ⊗ v∥_{2}.

Proof. We can write u ⊗ v = λu′ ⊗ v′ with λ = ∥u∥_{2}∥v∥_{2} and ∥u′∥_{2} = ∥v′∥_{2} = 1. Then Lemma 2.4 tells us that ∥u ⊗ v∥_{U_{2}}^{4} = λ^{4}, which proves this lemma. □

The next lemma tells us that if f is close to a function of rank 1, then that function is approximately unique in L_{2}. This is true whether “close” means close in L_{2} or close in the U_{2}-norm. We state it non-symmetrically, but obviously the same is true with the roles of the us and vs exchanged.

Lemma 3.3. Let X and Y be finite sets, let u_{1} and u_{2} be functions from X to ℂ and let v_{1} and v_{2} be functions from Y to ℂ. Suppose that either ∥u_{1} ⊗ v_{1} − u_{2} ⊗ v_{2}∥_{2} or ∥u_{1} ⊗ v_{1} − u_{2} ⊗ v_{2}∥_{U_{2}} is at most ϵ∥u_{1}∥_{2}∥v_{1}∥_{2} (which equals both ϵ∥u_{1} ⊗ v_{1}∥_{2} and ϵ∥u_{1} ⊗ v_{1}∥_{U_{2}})). Then there exists a complex number λ such that ∥u_{1} − λu_{2}∥_{2} ⩽ ϵ∥u_{1}∥_{2} and ∥v_{1} − λ^{−1}v_{2}∥_{2} ⩽ ϵ∥v_{1}∥_{2}/(1 − ϵ).

Proof. Choose λ so that u_{1} − λu_{2} is orthogonal to u_{2}. We know that

u_{1} ⊗ v_{1} − u_{2} ⊗ v_{2} = (u_{1} − λu_{2}) ⊗ v_{1} + λu_{2} ⊗ (v_{1} − λ^{−1}v_{2}) .

By Lemma 2.8, both the L_{2}-norm and the U_{2}-norm of this function are at least ∥u_{1} − λu_{2}∥_{2}∥v_{1}∥_{2}, so if one of them is at most ϵ∥u_{1}∥_{2}∥v_{1}∥_{2} then ∥u_{1} −λu_{2}∥_{2} ⩽ ϵ∥u_{1}∥_{2}. It follows that ∥λu_{2}∥_{2} ⩾ (1 − ϵ)λ∥u_{1}∥_{2}.

Lemma 2.8 also tells us that both the L_{2}-norm and the U_{2}-norm of the function above are at least ∥λu_{2}∥_{2}∥v_{1} −λ^{−1}v_{2}∥_{2}. Therefore, if either of them is at most ϵ∥u_{1}∥_{2}∥v_{1}∥_{2}, then ∥u_{1} − λu_{2}∥_{2} ⩽ ϵ∥u_{1}∥_{2}∥v_{1}∥_{2}/∥u_{2}∥_{2}, which is at most ϵ∥v_{1}∥/(1 − ϵ). □

Notice that there is an obvious converse to Lemma 3.3. If such a λ exists, then from the fact that

u_{1} ⊗ v_{1} − u_{2} ⊗ v_{2} = (u_{1} − λu_{2}) ⊗ v_{1} + λu_{2} ⊗ (v_{1} − λ^{−1}v_{2})

we have immediately that both the L_{2}-norm and the U_{2}-norm of u_{1} ⊗ v_{1} − u_{2} ⊗ v_{2} are at most

∥u_{1} − λu_{2}∥_{2}∥v_{1}∥_{2} + ∥λu_{2}∥_{2}∥v_{1} − λ^{−1}v_{2}∥_{2} ,

which is at most ϵ∥u_{1}∥_{2}∥v_{1}∥_{2} + ϵ(1 + ϵ)∥u_{1}∥_{2}∥v_{1}∥_{2}, which equals (2ϵ + ϵ^{2})∥u_{1}∥_{2}∥v_{1}∥_{2}.

Lemma 3.4. Let X and Y be finite sets and let f : X × Y → ℂ be a function with singular-value decomposition ∑_{i=1}^{t} λ_{i}u_{i} ⊗ v_{i}. Then

max_{i} |λ_{i}| = max{⟨f, u ⊗ v⟩ : ∥u∥_{2} = ∥v∥_{2} = 1} .

Proof. Let u and v be unit vectors. Then

⟨f, u ⊗ v⟩ = ∑_{i=1}^{t} λ_{i}⟨u, u_{i}⟩⟨v, v_{i}⟩ .

By Bessel’s inequality and the Cauchy-Schwarz inequality, |∑_{i=1}^{t}⟨u, u_{i}⟩⟨v, v_{i}⟩| ⩽ 1. It follows that the left-hand side is at most the right-hand side. For the reverse inequality, let i be such that |λ_{i}| is maximized and set u = u_{i} and v = v_{i}. □

We shall now give some characterizations of functions from X × Y to ℂ that can be approximated in L_{2} by functions of rank 1. Later we shall use them to help us prove facts about functions that can be approximated in the U_{2}-norm.

Theorem 3.5. Let f : X × Y → ℂ and let ∑_{i=1}^{t} λ_{i}u_{i} ⊗ v_{i} be the singular-value decomposition of f with |λ_{1}| ⩾ |λ_{2}| ⩾ . . .. Then the following statements are equivalent.

(i) There exist u : X → ℂ and v : Y → ℂ with ∥u∥_{2} = ∥v∥_{2} = 1, and a constant λ ∈ ℂ, such that ∥f − λu ⊗ v∥_{2}^{2} ⩽ c_{1}∥f∥_{2}^{2}.

(ii) ∑_{i⩾2} |λ_{i}|^{2} ⩽ c_{2}∥f∥_{2}^{2}.

(iii) ∥f∥_{U_{2}}^{4} ⩾ (1 − c_{3})∥f∥_{2}^{4}.
(iv) 𝔼_{x,x′}𝔼_{y,y′} |f(x, y)f(x′, y′) − f(x, y′)f(x′, y)|^{2} ⩽ c_{4}∥f∥_{2}^{4}.

Proof. If (ii) holds, then we can let u = u_{1}, v = v_{1} and λ = λ_{1}. Then ∥f − λu ⊗ v∥_{2} = ∑_{i⩾2} |λ_{i}|^{2}, by Lemma 2.4, so (i) holds with c_{1} = c_{2}.

If (i) holds, then ∥f∥_{2} ⩽ |λ| + c_{1}^{1/2}∥f∥_{2}. It follows that ∑_{i=1}^{t} |λ_{i}|^{2} ⩽ |λ|^{2} + 2|λ|c_{1}^{1/2}∥f∥_{2} + c_{1}∥f∥_{2}^{2}. We can also deduce from (i) and the Cauchy-Schwarz inequality that |⟨f, u ⊗ v⟩| ⩾ |λ| − c_{1}^{1/2}∥f∥_{2}. Therefore, by Lemma 3.4, |λ_{1}| ⩾ |λ| − c_{1}^{1/2}∥f∥_{2}, which implies that |λ_{1}|^{2} ⩾ |λ|^{2} −2c_{1}^{1/2}|λ|∥f∥_{2} +c_{1}∥f∥_{2}^{2}. It follows that ∑_{i⩾2} |λ_{i}|^{2} ⩽ 4c_{1}^{1/2}|λ|∥f∥_{2}. Since also |λ| ⩽ ∥f∥_{2}(1 + c_{1}^{1/2}), this is at most 4(c_{1}^{1/2} + c_{1})∥f∥_{2}^{2}. Therefore, (ii) holds with c_{2} = 4(c_{1}^{1/2} + c_{1}).

The remaining equivalences are even more straightforward. Suppose that (ii) holds. Note first that ∥f∥_{U_{2}} ⩽ ∥f∥_{2} by Lemma 2.4 and the fact that the ℓ_{4}-norm is dominated by the ℓ_{2}-norm. We also have that

∥f∥_{2}^{4} = (|λ_{1}|^{2} + ∑_{i⩾2} |λ_{i}|^{2})^{2} ⩽ ∥f∥_{U_{2}}^{4} + (2c_{2} + c_{2}^{2})∥f∥_{2}^{4} .

Therefore, (iii) is true with c_{3} = 2c_{2} + c_{2}^{2}.

Now suppose that (iii) holds. Then

(∑_{i=1}^{t} |λ_{i}|^{2})^{2} ⩽ (1 − c_{3})^{−1} ∑_{i=1}^{t} |λ_{i}|^{4} ⩽ (1 − c_{3})^{−1}|λ_{1}|^{2}(∑_{i=1}^{t} |λ_{i}|^{2}) .

It follows that ∑_{i=1}^{t} |λ_{i}|^{2} ⩽ (1 − c_{3})^{−1}|λ_{1}|^{2}, and therefore that (ii) is true with c_{2} = (1 − c_{3})^{−1} − 1.

Finally, we show that (iii) and (iv) are equivalent by showing that the left-hand side of (iv) is another way of writing 2(∥f∥_{2}^{4} − ∥f∥_{U_{2}}^{4}). Indeed, expanding out the square gives us two “outer” terms, |f(x, y)|^{2}|f(x′, y′)|^{2} and |f(x, y′)|^{2}|f(x′, y)|^{2}, both of which have expectation ∥f∥_{2}^{4}, and two “inner” terms, f(x, y)\overline{f(x, y′)f(x′, y)}f(x′, y′) and its complex conjugate, both of which have expectation ∥f∥_{U_{2}}^{4}. Thus, (iv) is saying that ∥f∥_{U_{2}}^{4} ⩾ (1 − c_{4}/2)∥f∥_{2}^{4}. □

Let f be as above. Then we shall write ff^{∗} for the function from X^{2} to ℂ defined by the formula ff^{∗}(x, x′) = 𝔼_{y}f(x, y)\overline{f(x′, y)}. If we think of f as a matrix, then ff^{∗} is the product of f with its adjoint—hence the notation.

Lemma 3.6. Let X and Y be finite sets, and let f : X × Y → ℂ be a function with singular-value decomposition ∑_{i=1}^{t} λ_{i}u_{i} ⊗ v_{i}. Then ff^{∗} = ∑_{i=1}^{t} |λ_{i}|^{2}u_{i} ⊗ \overline{u_{i}}.

Proof. Since f(x, y) = ∑_{i=1}^{t} λ_{i}u_{i}(x)v_{i}(y), we have

ff^{∗}(x, x′) = 𝔼_{y} ∑_{i=1}^{t} ∑_{j=1}^{t} λ_{i}\overline{λ_{j}}u_{i}(x)v_{i}(y)\overline{u_{j}(x′)v_{j}(y)} .

But 𝔼_{y}v_{i}(y)\overline{v_{j}(y)} = δ_{ij}, so this equals ∑_{i=1}^{t} |λ_{i}|^{2}u_{i}(x)\overline{u_{i}(x′)}, which proves the lemma. □

The next result characterizes functions f : X × Y → ℂ that are close in the U_{2}-norm to a function of rank 1. As we shall see, this is true if and only if ff^{∗} is close to a rank-1 function in the L_{2}-norm.

Theorem 3.7. Let X and Y be finite sets, and let f : X × Y → ℂ be a function with singular-value decomposition ∑_{i=1}^{t} λ_{i}u_{i} ⊗ v_{i}, with |λ_{1}| ⩾ … ⩾ |λ_{t}|. Then the following statements are equivalent.

(i) There exist u : X → ℂ and v : Y → ℂ with ∥u∥_{2} = ∥v∥_{2} = 1, and a constant λ ∈ ℂ, such that ∥f − λu ⊗ v∥_{U_{2}}^{4} ⩽ c_{1}∥f∥_{U_{2}}^{4}.

(ii) ∑_{i⩾2} |λ_{i}|^{4} ⩽ c_{2}∥f∥_{U_{2}}^{4}.

(iii) There exists a function u : X^{2} → ℂ such that ∥u∥_{2} = 1, and a constant μ ∈ ℝ_{+}, such that ∥ff^{∗} − μu ⊗ \overline{u}∥_{2}^{2} ⩽ c_{3}∥f∥_{U_{2}}^{4}.

(iv) 𝔼_{x_{1},x_{2},x_{3},x_{4}} |ff^{∗}(x_{1}, x_{3})ff^{∗}(x_{2}, x_{4}) − ff^{∗}(x_{1}, x_{4})ff^{∗}(x_{2}, x_{3})|^{2} ⩽ c_{4}∥f∥_{U_{2}}^{8}.

Proof. The first equivalence is similar to the corresponding equivalence in Theorem 3.5. As there, it is trivial that if (ii) holds then (i) holds with the same constant.

If (i) holds, then ∥f∥_{U_{2}} ⩽ |λ| + c_{1}^{1/4}∥f∥_{U_{2}}, so ∑_{i=1}^{t} |λ_{i}|^{4} ⩽ (|λ| + c_{1}^{1/4}∥f∥_{U_{2}})^{4}. Writing g = f − λu ⊗ v, we have that |⟨g, u ⊗ v⟩| ⩽ ∥g∥_{2} ⩽ ∥g∥_{U_{2}} ⩽ c_{1}^{1/4}∥f∥_{U_{2}} by the Cauchy-Schwarz inequality, the fact that the U_{2}-norm is dominated by the L_{2}-norm, and (i). Therefore, |⟨f, u ⊗ v⟩| ⩾ |λ| − c_{1}^{1/4}∥f∥_{U_{2}}. Therefore, by Lemma 3.4, |λ_{1}| ⩾ |λ| − c_{1}^{1/4}∥f∥_{U_{2}}, so |λ_{1}|^{4} ⩾ (|λ| − c_{1}^{1/4}∥f∥_{U_{2}})^{4}. It follows that

\begin{aligned}∑_{i⩾2} |λ_{i}|^{4} & ⩽ (|λ| + c_{1}^{1/4}∥f∥_{U_{2}})^{4} − (|λ| − c_{1}^{1/4}∥f∥_{U_{2}})^{4} \\ & = 3c_{1}^{1/4}∥f∥_{U_{2}}|λ|^{3} + 3c_{1}^{3/4}∥f∥_{U_{2}}|λ| . \end{aligned}

But (i) also implies that |λ| ⩽ (1 + c_{1}^{1/4})∥f∥_{U_{2}}, so this implies (ii) with c_{2} = 3c_{1}^{1/4}(1 + c_{1}^{1/4})^{3} + 3c_{1}^{3/4}(1 + c_{1}^{1/4}). In particular, if c_{1} ⩽ 1, then it implies (ii) with c_{2} = 30c_{1}^{1/4} and for sufficiently small c_{1} it implies it with c_{2} = 4c_{1}^{1/4}.

The equivalence of (ii) and (iii) follows easily from Theorem 3.5 and Lemma 3.6. Indeed, suppose first that (ii) is true and set μ_{i} = |λ_{i}|^{2}. By Lemma 3.6, the singularvalue decomposition of ff^{∗} is ∑_{i=1}^{t} μ_{i}u_{i} ⊗ \overline{u_{i}}, and by Lemma 2.4 we know that ∥f∥_{U_{2}}^{4} = ∑_{i=1}^{t} |λ_{i}|^{4} = ∑_{i=1}^{t} μ_{i}^{2} = ∥ff^{∗}∥_{2}^{2}. Therefore, (ii) is telling us that ∑_{i⩾2} μ_{i}^{2} ⩽ c_{2}∥ff^{∗}∥_{2}^{2}, which says that ∥ff^{∗} − μ_{1}u_{1} ⊗ \overline{u_{1}}∥_{2}^{2} ⩽ c_{2}∥ff^{∗}∥_{2}^{2} = c_{2}∥f∥_{U_{2}}^{4}.

Conversely, if (iii) is true, then the implication of (ii) from (i) in Theorem 3.5 tells us that ∑_{i⩾2} μ_{i}^{2} ⩽ 4(c_{3}^{1/2} + c_{3})∥ff^{∗}∥_{2}^{2}, which says that ∑_{i⩾2} |λ_{i}|^{4} ⩽ 4(c_{3}^{1/2} + c_{3})∥f∥_{U_{2}}^{4}.

Similarly, the equivalence of (ii) and (iv) is just the equivalence between (ii) and (iv) of Theorem 3.5, but applied to the function ff^{∗}. □

As remarked earlier, one can deduce results about graphs from results about functions. If f is the characteristic function of a bipartite graph G with vertex sets X and Y, then ff^{∗}(x, x′) = |N_{x} ∩ N_{x′}|/|Y |, which we denoted earlier by δ_{1}(x, x′). The next theorem combines several of the results stated so far. The equivalences involving (ii) are “weak” equivalences, in that the dependences between the c_{i} involve the U_{2}-norm of G. We make this remark precise in the proof.

Corollary 3.8. Let X and Y be finite sets and let G be a bipartite graph with vertex sets X and Y of size m and n. Then the following statements are equivalent.

(i) There exist functions u : X → ℝ and v : Y → ℝ with ∥u∥_{2} = ∥v∥_{2} = 1 and a real number λ such that ∥G − λu ⊗ v∥_{U_{2}}^{4} ⩽ c_{1}∥G∥_{U_{2}}^{4}.

(ii) There exist functions u : X → ℝ and v : Y → ℝ with ∥u∥_{2} = ∥v∥_{2} = 1 and a real number λ such that for every subset X′ ⊂ X and every subset Y′ ⊂ Y the number of edges from X′ to Y′ differs from λ(∑_{x∈X′} u(x))(∑_{y∈Y′} v(y)) by at most c_{2}mn.

(iii) 𝔼_{x_{1},x_{2},x_{3},x_{4}} |δ(x_{1}, x_{3})δ(x_{2}, x_{4}) − δ(x_{1}, x_{4})δ(x_{2}, x_{3})|^{2} ⩽ c_{3}∥G∥_{U_{2}}^{4}.

Moreover, the equivalence between (i) and (ii) holds for the same pair of functions u and v.

Proof. If we set f = G−λu⊗v, then (i) is equivalent to saying that f is c_{1}-quasirandom. That is, it is equivalent to saying that f satisfies property (i) of Theorem 1.1. Property (ii) of this theorem is easily seen to be equivalent to property (iii) of Theorem 1.1. Therefore, the equivalence of (i) and (ii) follows immediately from the equivalence of (i) and (iii) in Theorem 1.1. The dependences in that theorem imply that if (i) holds then (ii) holds with constant c_{1}^{1/4}∥G∥_{U_{2}} and that if (ii) holds then (i) holds with constant 4c_{2}∥G∥_{U_{2}}^{−4}.

The equivalence of (i) and (iii) is just the equivalence of (i) and (iv) in Theorem 3.7 applied to the function G. □

Before the last main result of the section we need two further technical lemmas. They have very similar proofs, but not quite similar enough for it to be worth the effort to deduce them from a single more abstract lemma.

Lemma 3.9. Suppose that X and Y are finite sets and that f and g are functions from X × Y to ℂ. Then

𝔼_{x,x′} |𝔼_{y}(f(x, y)\overline{f(x′, y)} − g(x, y)\overline{g(x′, y)})|^{2} ⩽ ∥f − g∥_{U_{2}}^{2}(∥f∥_{U_{2}} + ∥g∥_{U_{2}})^{2}

Proof. Let h = f − g. Then

f(x, y)\overline{f(x′, y)} − g(x, y)\overline{g(x′, y)} = f(x, y)\overline{h(x′, y)} + h(x, y)\overline{g(x′, y)} .

By Minkowski’s inequality, the square root of the quantity we wish to bound is therefore at most

(𝔼_{x,x′} |𝔼_{y}f(x, y)\overline{h(x′, y)}|^{2})^{1/2} + (𝔼_{x,x′} |𝔼_{y}h(x, y)\overline{g(x′, y)}|^{2})^{1/2} .

Now 𝔼_{x,x′} |𝔼_{y}f(x, y)\overline{h(x′, y)}|^{2} = [f, f, h, h], so by Lemma 2.2 it is at most ∥f∥_{U_{2}}^{2}∥h∥_{U_{2}}^{2}. A similar assertion is true for the second term, and the result follows easily. □

Lemma 3.10. Suppose that Z is a finite set and that f and g are functions from Z to ℂ. Then

𝔼_{z,z′} |f(z)\overline{f(z′)} − g(z)\overline{g(z′)}|^{2} ⩽ ∥f − g∥_{2}^{2}(∥f∥_{2} + ∥g∥_{2})^{2}

Proof. Once again we apply the standard trick for showing that products are close, observing that

f(z)\overline{f(z′)} − g(z)\overline{g(z′)} = f(z)(\overline{f(z′)} − \overline{g(z′)}) + (f(z) − g(z))\overline{g(z′)} .

Again let h = f − g. Let us regard both sides of the above identity as functions from Z^{2} to ℂ and apply Minkowski’s inequality. It tells us that

(𝔼_{z,z′} |f(z)\overline{f(z′)} − g(z)\overline{g(z′)}|^{2})^{1/2} ⩽ (𝔼_{z,z′} |f(z)\overline{h(z′)}|^{2})^{1/2} + (𝔼_{z,z′} |h(z)\overline{g(z′)}|^{2})^{1/2} .

The right-hand side is equal to ∥h∥_{2}(∥f∥_{2} + ∥g∥_{2}), so the result is proved. □

The message of the next result is that if f is a function from X × Y to ℝ_{+} and f can be approximated by a rank-1 function λu ⊗ v, then we can identify in a very simple way what u, v and λ are. (By Lemma 3.3, they are approximately unique up to multiplication of u by a scalar and v by the inverse of that scalar.) Indeed, u and v are proportional to the (normalized) degrees of the vertices in X and Y, respectively. To obtain the constant of proportionality, one looks at d = 𝔼_{x,y}f(x, y). Of course, this will not work if d = 0, so the result is valid only when d is non-zero, and gets progressively weaker when d gets smaller.

It turns out that this problem persists to some extent even if f takes values that are real and positive (the case that will eventually interest us). When we prove that (i) implies (ii) below, we shall obtain a “weak” result, in that the constant c_{2} that we obtain will depend not just on c_{1} but also on the ratio d^{−1}∥f∥_{U_{2}}. After the proof, we shall give a simple example that demonstrates that this weakness is necessary.

Theorem 3.11. Let X and Y be sets of size m and n, respectively, and let f : X ×Y → ℂ. Then the following four statements are equivalent.

(i) There exist functions u : X → ℂ and v : Y → ℂ such that ∥f −u⊗v∥_{U_{2}}^{4} ⩽ c_{1}∥f∥_{U_{2}}^{4}.

(ii) ∥f − d^{−1}δ_{1} ⊗ δ_{2}∥_{U_{2}}^{4} ⩽ c_{2}∥f∥_{U_{2}}^{4}.

(iii) 𝔼_{x,x′} |δ_{1}(x, x′) − (d^{−2}∥δ_{2}∥_{2}^{2})δ_{1}(x)δ_{1}(x′)|^{2} ⩽ c_{3}∥f∥_{U_{2}}^{4}.
(iv) 𝔼_{y,y′} |δ_{2}(y, y′) − (d^{−2}∥δ_{1}∥_{2}^{2})δ_{2}(y)δ_{2}(y′)|^{2} ⩽ c_{4}∥f∥_{U_{2}}^{4}.

Proof. Trivially (ii) implies (i) with c_{1} = c_{2}. To see that (i) implies (ii), we apply Lemma 3.1 to the function h(x, y) = f(x, y) − u(x)v(y). Setting α = 𝔼_{x}u(x) and β = 𝔼_{y}v(y), this tells us that

𝔼_{x}|δ_{1}(x) − βu(x)|^{2} ⩽ c_{1}^{1/2}∥f∥_{U_{2}}^{2} .

That is, ∥δ_{1} − βu∥_{2} ⩽ c_{1}^{1/4}∥f∥_{U_{2}}. Similarly, ∥δ_{2} − αv∥_{2} ⩽ c_{1}^{1/4}∥f∥_{U_{2}}. It follows that

∥δ_{1} ⊗ δ_{2} − αβu ⊗ v∥_{U_{2}} ⩽ ∥δ_{1} ⊗ (δ_{2} − αv)∥_{U_{2}} + ∥(δ_{1} − βu) ⊗ αv∥_{U_{2}}
= ∥δ_{1} ⊗ (δ_{2} − αv)∥_{2} + ∥(δ_{1} − βu) ⊗ αv∥_{2}
⩽ c_{1}^{1/4}∥f∥_{U_{2}}(∥δ_{1}∥_{2} + α∥v∥_{2}) .

Now Lemma 3.1 applied to f tells us that ∥δ_{1}∥_{2} ⩽ ∥f∥_{U_{2}}, and α∥v∥_{2} ⩽ ∥u∥_{2}∥v∥_{2} = ∥u ⊗ v∥_{U_{2}} ⩽ (1 + c_{1}^{1/4})∥f∥_{U_{2}}. Therefore, we have shown that

∥δ_{1} ⊗ δ_{2} − αβu ⊗ v∥_{U_{2}} ⩽ c^{1/4}(2 + c_{1}^{1/4})∥f∥_{U_{2}}^{2} .

From Lemma 3.4 with u and v equal to the constant functions 1_{X} and 1_{Y}, respectively, and f = h, we find that |𝔼_{x,y}h(x, y)| ⩽ ∥h∥_{U_{2}}. (This uses Lemma 2.4 as well.) We are assuming that ∥h∥_{U_{2}} ⩽ c_{1}^{1/4}∥f∥_{U_{2}}. It follows that |αβ − d| ⩽ c_{1}^{1/4}∥f∥_{U_{2}}, and therefore that ∥αβu ⊗ v − du ⊗ v∥_{U_{2}} ⩽ c_{1}^{1/4}∥f∥_{U_{2}}∥u∥_{2}∥v∥_{2}, which is at most c_{1}^{1/4}(1 + c_{1}^{1/4})∥f∥_{U_{2}}^{2}.

Thus, by the triangle inequality,

∥δ_{1} ⊗ δ_{2} − du ⊗ v∥_{U_{2}} ⩽ c_{1}^{1/4}(3 + 2c_{1}^{1/4})∥f∥_{U_{2}}^{2} ,

and by (i) and the triangle inequality again this tells us that

∥f − d^{−1}δ_{1} ⊗ δ_{2}∥_{U_{2}} ⩽ c_{1}^{1/4}∥f∥_{U_{2}} + d^{−1}c^{1/4}(3 + 2c_{1}^{1/4})∥f∥_{U_{2}}^{2} .

Notice that the c_{2} that we have obtained is equal to (c_{1}^{1/4} +d^{−1}∥f∥_{U_{2}}c^{1/4}(3+2c_{1}^{1/4}))^{4}, so it depends on the quantity d^{−1}∥f∥_{U_{2}}, as we warned that it would.

Now let us prove that (ii) implies (iii). We do this by applying Lemma 3.9 to the functions f and d^{−1}δ_{1} ⊗ δ_{2}, from which we learn that

𝔼_{x,x′} |δ_{1}(x, x′) − (d^{−2}∥δ_{2}∥_{2}^{2})δ_{1}(x)δ_{1}(x′)|^{2} ⩽ ∥f − d^{−1}δ_{1} ⊗ δ_{2}∥_{U_{2}}^{2}(∥f∥_{U_{2}} + ∥d^{−1}δ_{1} ⊗ δ_{2}∥_{U_{2}})^{2} .

By (ii) and the triangle inequality, we know that ∥d^{−1}δ_{1} ⊗ δ_{2}∥_{U_{2}} ⩽ (1 + c_{2}^{1/4})∥f∥_{U_{2}}. Therefore, the right-hand side of the above inequality is at most c_{2}^{1/2}(2 + c_{2}^{1/4})^{2}∥f∥_{U_{2}}^{4}, which establishes (iii) with c_{3} = c_{2}^{1/2}(2 + c_{2}^{1/4})^{2}.

Finally, we prove that (iii) implies (i). Note first that δ_{(}x, x′) is just a different notation for ff^{∗}(x, x′). Therefore, property (iii) implies property (iii) of Theorem 3.7. We therefore have property (i) of that theorem (by the theorem) with constant 4(c_{3}^{1/2} + c_{3}), and hence property (i) of this theorem with the same constant.(A tiny extra ingredient is the observation that if f is real then its singular-value decomposition is real, so that the u, v and λ that come out of Theorem 3.7 are all real.)

Finally, notice that statements (i) and (ii) are symmetric in X and Y. Therefore, the equivalence with (iii) implies the equivalence with (iv) with exactly the same dependences. (Thus, interestingly, if you know that δ_{1}(x, x′) tends to be roughly proportional to δ_{1}(x)δ_{1}(x′) then you know the same for δ_{2}. However, this is a “weak” implication.) □

To see why the weakness was necessary in the above result, consider the following example (or rather, class of examples). The basic idea behind it is to construct a function of the form u ⊗ v + u′ ⊗ v′ in such a way that u, v, u′ and v′ are all positive, ∥u ⊗ v∥_{U_{2}} is much bigger than ∥u′ ⊗ v′∥_{U_{2}}, but 𝔼_{x,y}u(x)v(y) is much smaller than 𝔼_{x,y}u′(x)v′(y). This means that (i) is true, but (ii) is false.

To be more concrete, let X_{1} ⊂ X and Y_{1} ⊂ Y be subsets of density β, and let u and v be their characteristic functions. Let u′ and v′ be the characteristic functions of X and Y. Then let f = u ⊗ v + β^{2}u′ ⊗ v′. Now ∥u ⊗ v∥_{U_{2}} = ∥u∥_{2}∥v∥_{2} = β, and ∥β^{2}u′ ⊗ v′∥_{U_{2}} = β^{2}. Therefore, ∥f − u ⊗ v∥_{U_{2}} ⩽ β∥u ⊗ v∥_{U_{2}} ⩽ β(1 − β)^{−1}∥f∥_{U_{2}}, so we have (i) with constant β(1 − β)^{−1}.

Now the density d of f is 2β^{2}. If x ∈ X_{1} and y ∈ Y_{1} then d^{−1}δ_{1}(x)δ_{2}(y) = d^{−1}(β + β^{2})^{2} ⩽ 1/2 + 3β, whereas f(x, y) = 1. If x ∈ X_{1} and y ∈ Y_{2} then d^{−1}δ_{1}(x)δ_{2}(y) = (β + β^{2})β^{2} ⩽ 2β^{3}, and the same is true if x ∈ X_{2} and y ∈ Y_{1}. In both these cases f(x, y) = 0. Finally, if x ∈ X_{2} and y ∈ Y_{2} then d^{−1}δ_{1}(x)δ_{2}(y) = d^{−1}β^{4} = β^{2}/2.

We can split g = f −d^{−1}δ_{1} ⊗δ_{2} into four pieces of rank 1, by looking at its restrictions to the four sets X_{i} ×Y_{j}. The calculations above show that the part in X_{1} ×Y_{1} has U_{2}-norm at least β(1/2 − 3β), since g is constant, and the constant is at least 1/2 − 3β. Similarly, the parts in X_{1} × Y_{2} and X_{2} × Y_{1} have U_{2}-norm at most 2β^{3}. Finally, the part in X_{2} × Y_{2} has U_{2}-norm at most β^{2}/2, since g is constant and the constant lies between 0 and β^{2}/2. It follows that the U_{2}-norm of g is at least β(1/2 − 3β) − 2β^{3} − β^{2}/2, which is at least β/3 if β is sufficiently small.

We know that ∥f∥_{U_{2}} ⩾ β (since u′ and v′ are positive), so this tells us that f is not close to d^{−1}δ_{1} ⊗ δ_{2} in the U_{2}-norm. More precisely, (ii) is not true with a constant that tends to zero with β, while (i) is true with a constant that is roughly proportional to β. This shows that in order to obtain (ii), we need c_{1} to be small in a way that depends not just on c_{2} but also on the function f. In other words, the weak implication cannot be replaced by a strong one.

A special case that will interest us later is when a graph (or function) can be approximated by a function of the form 1 ⊗ v. The next theorem characterizes such functions in a way that is quite similar to the characterizations of Theorem 3.11, though we add one further characterization. However, for this theorem, perhaps surprisingly, all the implications are strong ones, except that the extra characterization (v) implies the others only weakly.

Theorem 3.12. Let X and Y be finite sets and let f : X × Y → ℝ_{+}. Then the following statements are equivalent.

(i) There exists a function v : Y → ℝ_{+} such that ∥f − 1 ⊗ v∥_{U_{2}}^{4} ⩽ c_{1}∥f∥_{U_{2}}^{4}.

(ii) ∥f − 1 ⊗ δ_{2}∥_{U_{2}}^{4} ⩽ c_{2}∥f∥_{U_{2}}^{4}.
(iii) 𝔼_{x,x′} |δ_{1}(x, x′) − ∥δ_{2}∥_{2}^{2}|^{2} ⩽ c_{3}∥f∥_{U_{2}}^{4}.
(iv) 𝔼_{y,y′} |δ_{2}(y, y′) − δ_{2}(y)δ_{2}(y′)|^{2} ⩽ c_{4}∥f∥_{U_{2}}^{4}.
(v) 𝔼_{y}|𝔼_{x}f(x, y)u(x)|^{2} ⩽ c_{5}∥f∥_{U_{2}}^{2}∥u∥_{2}^{2} for every function u : X → ℝ of mean 0.

Proof. First let us show that (ii) and (iv) are exactly equivalent, by showing that their left-hand sides are equal. If we set g(x, y) = f(x, y) − δ_{2}(y), then the left-hand side of (ii) is equal to ∥g∥_{U_{2}}^{4}, which is equal to 𝔼_{y,y′}|𝔼_{x}g(x, y)g(x, y′)|^{2}. But

\begin{aligned}𝔼_{x}g(x, y)g(x, y′) & = 𝔼_{x}f(x, y)f(x, y′) − 𝔼_{x}f(x, y)δ_{2}(y′) − 𝔼_{x}f(x, y′)δ_{2}(y) + δ_{2}(y)δ_{2}(y′) \\ & = δ_{2}(y, y′) − δ_{2}(y)δ_{2}(y′) , \end{aligned}

from which the equality follows.

The proof that (ii) implies (iii) is almost identical to the proof that (ii) implies (iii) in Theorem 3.11. Indeed, let us prove a more general result that implies them both. Suppose that ∥f −u⊗v∥_{U_{2}}^{4} ⩽ c_{2}∥f∥_{U_{2}}^{4}. We can then apply Lemma 3.9 to the functions f and u⊗v, concluding that

𝔼_{x,x′} |𝔼_{y}(f(x, y)\overline{f(x′, y)} − u(x)\overline{u(x′)}|v(y)|^{2})|^{2} ⩽ ∥f − u ⊗ v∥_{U_{2}}^{2}(∥f∥_{U_{2}} + ∥u ⊗ v∥_{U_{2}})^{2} .

By (ii) and the triangle inequality, ∥u ⊗ v∥_{U_{2}} ⩽ (1 + c_{2}^{1/4})∥f∥_{U_{2}}, so

𝔼_{x,x′} |δ_{1}(x, x′) − u(x)\overline{u(x′)}∥v∥_{2}^{2}|^{2} ⩽ c_{2}^{1/2}(2 + c_{2}^{1/4})^{2}∥f∥_{U_{2}}^{4} .

Specializing to the case u = 1 and v = δ_{2} tells us that (ii) implies (iii), and specializing to the case u = δ_{1} and v = d^{−1}δ_{2} tells us that (ii) implies (iii) in Theorem 3.11.

We finish the proof that all of (i), (ii), (iii) and (iv) are equivalent by proving that (iii) implies (i) and (i) implies (ii). The proofs are very similar to the corresponding proofs in Theorem 3.11 but slightly more complicated.

First, notice that (iii) implies property (iii) of Theorem 3.7 with the same constant c_{3}. It therefore gives us property (i) of Theorem 3.7 with constant 4(c_{3}^{1/2} + c_{3}), which we shall call c_{6}. Now the proof of that implication actually tells us slightly more—that ∥f − λu ⊗ v∥_{U_{2}}^{4} ⩽ c_{6}∥f∥_{U_{2}}^{4} where λ, u and v are the beginning of the singular-value decomposition of f. Since f is a non-negative function, λ, u and v can all be taken to be real and non-negative. It follows that ∥ff^{∗} − λ^{2}u ⊗ u∥_{2}^{2} ⩽ c_{6}∥f∥_{U_{2}}^{4} as well, since if f = ∑_{i=1}^{t} λ_{i}u_{i}⊗v_{i} with (u_{i}) and (v_{i}) both orthonormal sequences then ff^{∗} = ∑_{i=1}^{t} |λ_{i}|^{2}u_{i}⊗\overline{u_{i}}. But (iii) tells us that ∥ff^{∗} − ∥δ_{2}∥_{2}^{2}1 ⊗ 1∥_{2}^{2} ⩽ c_{3}∥f∥_{U_{2}}^{4}, so it follows from Minkowski’s inequality that ∥λ^{2}u ⊗ u − ∥δ_{2}∥_{2}^{2}1 ⊗ 1∥_{2} ⩽ (c_{3}^{1/2} + c_{6}^{1/2})∥f∥_{U_{2}}^{2}.

We also know that λ^{2}∥u ⊗ u∥_{2} ⩾ ∥ff^{∗}∥_{2} − c_{6}^{1/2}∥f∥_{U_{2}}^{2} = (1 − c_{6}^{1/2})∥f∥_{U_{2}}^{2}. Therefore, ∥λ^{2}u ⊗ u − ∥δ_{2}∥_{2}^{2}1 ⊗ 1∥_{2} ⩽ (c_{3}^{1/2} + c_{6}^{1/2})(1 − c_{6}^{1/2})^{−1}λ^{2}∥u ⊗ u∥_{2}. Let c_{7} = (c_{3}^{1/2} + c_{6}^{1/2})(1 − c_{6}^{1/2})^{−1}. It follows from Lemma 3.3 that there is some constant function ρ such that ∥λu − ρ∥_{2} ⩽ c_{7}λ∥u∥_{2}. Therefore, ∥(λu − ρ) ⊗ v∥_{U_{2}} ⩽ c_{7}λ∥u∥_{2}∥v∥_{2}. Hence, by the triangle inequality,

∥f − ρ ⊗ v∥_{U_{2}} ⩽ c_{6}^{1/4}∥f∥_{U_{2}} + c_{7}λ∥u∥_{2}∥v∥_{2} .

We also know that ∥λu⊗v∥_{U_{2}} ⩽ (1+c_{6}^{1/4})∥f∥_{U_{2}}, so this is at most (c_{6}^{1/4}+c_{7}(1+c_{6}^{1/4}))∥f∥_{U_{2}}. We have just established (i) with constant c_{1} = (c_{6}^{1/4} + c_{7}(1 + c_{6}^{1/4}))^{4}.

If we now apply Lemma 3.1 to the function f(x, y) − ρv(y) (but with x and y interchanged) we find that 𝔼_{y}|δ_{2}(y) − ρv(y)|^{2} ⩽ ∥f − ρ ⊗ v∥_{U_{2}}^{2}, which we know is at most c_{1}^{1/2}∥f∥_{U_{2}}^{2}. That is, ∥δ_{2} − ρv∥_{2} ⩽ c_{1}^{1/4}∥f∥_{U_{2}}. (Here we are sometimes using ρ to stand for a constant function and sometimes to stand for the relevant constant.)

Now ρ ⊗ v = 1 ⊗ ρv, so the above estimates give us

\begin{aligned}∥f − 1 ⊗ δ_{2}∥_{U_{2}} & ⩽ ∥f − 1 ⊗ ρv∥_{U_{2}} + ∥1 ⊗ (ρv − δ_{2})∥_{U_{2}} \\ & ⩽ c_{1}^{1/4}∥f∥_{U_{2}} + c_{1}^{1/4}∥f∥_{U_{2}} = 2c_{1}^{1/4}∥f∥_{U_{2}} . \end{aligned}

This proves (ii) with constant c_{2} = 2c_{1}^{1/4}.

To complete the proof of the lemma, we shall show that (iii) and (v) are equivalent. Since it is no harder, we shall do this for complex functions. Notice that property (v) is saying that if we associate with f a linear map from L_{2}(X) to L_{2}(Y) in the obvious way, then the restriction of this map to the set of functions with mean zero has norm at most c_{5}^{1/2}∥f∥_{U_{2}}. The proof that it follows from (iii) is the following simple calculation:

𝔼_{y}|𝔼_{x}u(x)f(x, y)|^{2} = 𝔼_{y}𝔼_{x,x′}u(x)\overline{u(x′)}f(x, y)\overline{f(x′, y)}
= 𝔼_{x,x′}u(x)\overline{u(x′)}δ_{1}(x, x′)
= 𝔼_{x,x′}u(x)\overline{u(x′)}(δ_{1}(x, x′) − α)
⩽ (𝔼_{x,x′}|u(x)|^{2}|u(x′)|^{2})^{1/2}(𝔼_{x,x′}|δ_{1}(x, x′) − α|^{2})^{1/2} .

Here α = ∥δ_{2}∥_{2}^{2}, the mean of δ_{1}(x, x′). The first term in the final product equals ∥u∥_{2}^{2} and the second is at most c_{3}^{1/2}∥f∥_{U_{2}}^{2} by hypothesis.

Finally, let us assume (v). We begin by deducing from it a statement about arbitrary functions u. Let u : X → ℂ be a function with mean τ and write u(x) = τ + v(x). Then

𝔼_{x,x′}δ_{1}(x, x′)u(x)\overline{u(x′)} = 𝔼_{x,x′}δ_{1}(x, x′)(τ + v(x))(\overline{τ} + \overline{v(x′)}) .

The right-hand side splits up into four parts, which we shall consider separately.

The first term is |τ|^{2}𝔼_{x,x′}δ_{1}(x, x′), which equals |τ|^{2}∥δ_{2}∥_{2}^{2}. The second is τ𝔼_{x,x′}δ_{1}(x, x′)\overline{v(x′)}. Now

𝔼_{x,x′}δ_{1}(x, x′)\overline{v(x′)} = 𝔼_{x,x′}𝔼_{y}f(x, y)\overline{f(x′, y)}\overline{v(x′)}
= 𝔼_{y}δ_{2}(y)𝔼_{x′} \overline{f(x′, y)}\overline{v(x′)}
⩽ ∥δ_{2}∥_{2}(𝔼_{y}|𝔼_{x′}f(x′, y)v(x′)|^{2})^{1/2} ,

which is at most ∥δ_{2}∥_{2}c_{5}^{1/2}∥v∥_{2}∥f∥_{U_{2}}, by (v). Since both τ and ∥v∥_{2} are at most ∥u∥_{2} and

∥δ_{2}∥_{2}^{2} = 𝔼_{x,x′}δ_{1}(x, x′) ⩽ (𝔼_{x,x′}|δ_{1}(x, x′)|^{2})^{1/2} = ∥f∥_{U_{2}}^{2} ,

it follows that the second term is at most c_{5}^{1/2}∥f∥_{U_{2}}^{2}∥u∥_{2}^{2}. The third term is just the complex conjugate of the second, so it is bounded in the same way. And finally the fourth term equals 𝔼_{y}|𝔼_{x}f(x, y)v(x)|^{2} and so by (v) it is at most c_{5}∥f∥_{U_{2}}^{2}∥v∥_{2}^{2} ⩽ c_{5}∥f∥_{U_{2}}^{2}∥u∥_{2}^{2}.

This shows that for any u we have the inequality

𝔼_{x,x′}δ_{1}(x, x′)u(x)\overline{u(x′)} − |𝔼_{x}u(x)|^{2}∥δ_{2}∥_{2}^{2} ⩽ (2c_{5}^{1/2} + c_{5})∥f∥_{U_{2}}^{2}∥u∥_{2}^{2} .

Now let us apply this inequality to the function u(x) = \overline{f(x, y)}, obtaining the inequality

𝔼_{x,x′}δ_{1}(x, x′)\overline{f(x, y)}f(x′, y) − |𝔼_{x}f(x, y)|^{2}∥δ_{2}∥_{2}^{2} ⩽ (2c_{5}^{1/2} + c_{5})∥f∥_{U_{2}}^{2}𝔼_{x}|f(x, y)|^{2} .

Now let us take the expectation over y of both sides. The first term on the left-hand side has mean 𝔼_{x,x′}|δ_{1}(x, x′)|^{2}, while the second equals |δ_{2}(y)|^{2}∥δ_{2}∥_{2}^{2}, which has mean ∥δ_{2}∥_{2}^{4}, which also equals (𝔼_{x,x′}δ_{1}(x, x′))^{2}. Therefore, the expectation of the left-hand side is the variance of δ_{1}(x, x′). The expectation of the right-hand side is (2c_{5}^{1/2}+c_{5})∥f∥_{U_{2}}^{2}∥f∥_{2}^{2}, so we obtain (iii) with constant c_{3} = (2c_{5}^{1/2} + c_{5})∥f∥_{2}^{2}/∥f∥_{U_{2}}^{2}. □

We shall be particularly interested in the case where f is the characteristic function of a bipartite graph, and especially in the fact that property (iii) implies all the others. Notice that

∥δ_{2}∥_{2}^{2} = 𝔼_{y}(𝔼_{x}f(x, y))^{2} = 𝔼_{x,x′}𝔼_{y}f(x, y)f(x′, y) = 𝔼_{x,x′}δ_{1}(x, x′) ,

so (iii) is the statement that the variance of δ_{1}(x, x′) is small compared with 𝔼_{x,x′}δ_{1}(x, x′)^{2}. In the case of a bipartite graph, this says that almost all the intersections of pairs of neighbourhoods N(x) and N(x′), with x, x′ ∈ X, have about the same size.

This property should be compared with quasirandomness. If the average density of a neighbourhood is δ and almost all pairs of neighbourhoods intersect in a set of density approximately δ^{2}, then the graph is quasirandom. If, however, we have just the weaker property that the intersections of pairs of neighbourhoods have about the same size (without the further property that this size is almost minimal) then we obtain the weaker, but still useful, conclusion that G can be “quasirandomly approximated” by the very simple function 1 ⊗ δ_{2}. In fact, the only difference between this and quasirandomness is that a quasirandom graph looks like a random graph where all edges are chosen independently with some probability p, whereas a graph with the weaker intersections property looks like a graph where the edges are again chosen independently, but now the probability of choosing the edge xy is given by some number p(y) ∈ [0, 1] that can depend on y. Furthermore, it is easy to identify p(y): it is just the normalized degree of y.

We finish this section by remarking that the weak implication in Theorem 3.12 was necessarily so. To see this, suppose that f has singular-value decomposition ∑_{i=1}^{t} λ_{i}u_{i} ⊗ v_{i} and suppose that u_{1} = 1. Then ff^{∗} = ∑_{i=1}^{t} |λ_{i}|^{2}u_{i} ⊗ u_{i}, from which it follows that 𝔼_{x,x′}δ_{1}(x, x′)^{2} = ∑_{i=1}^{t} |λ_{i}|^{4}, as we already know. Now in this case δ_{2}(y) = ∑_{i=1}^{t} λ_{i}𝔼_{x}u_{i}(x)v_{i}(y), which equals λ_{1}v_{1}(y), since 𝔼_{x}u_{1}(x) = 1 and 𝔼_{x}u_{i}(x) = 0 for every i > 1 (because all the other u_{i} are orthogonal to the constant function 1). Therefore, ∥δ_{2}∥_{2}^{4} = |λ_{1}|^{4}. It follows that the variance 𝔼_{x,x′} |δ_{1}(x, x′) − ∥δ_{2}∥_{2}^{2}|^{2} of δ_{1}(x, x′) equals ∑_{i>1} |λ_{i}|^{4}. Notice that in this case property (iii) is exactly equivalent to properties (ii) and (iv).

It is an easy consequence of Lemma 3.4 that the norm of the restriction to functions of mean 0 of the linear map corresponding to f is equal to the largest value of |λ_{i}| such that i ≠ 1. Therefore, if we wish to bound the variance of δ_{1}(x, x′) in terms of this norm, then we are trying to bound an ℓ_{4}-norm in terms of an ℓ_{∞}-norm, which we cannot do. However, we do at least have the inequality

∑_{i⩾2} |λ_{i}|^{4} ⩽ max_{i⩾2} |λ_{i}|^{2} ∑_{i=1}^{t} |λ_{i}|^{2} = max_{i⩾2} |λ_{i}|^{2}∥f∥_{2}^{2} .

This is why it is not surprising that a ratio of the form ∥f∥_{2}^{2}/∥f∥_{U_{2}}^{2} appears in the proof that (v) implies (iii).

§4. Some weak regularity lemmas.

Theorem 3.12 would be just a curiosity were it not for the fact that graphs that satisfy property (iii) arise naturally in connection with a technique used in [G2] to prove a quantitative version of the Balog-Szemerédi theorem. In this section we shall begin by giving an answer to the following rather general-sounding question. Suppose you have a (not too sparse) bipartite graph G with vertex sets X and Y. How nice can you make G by restricting to a (not too small) subset X′ ⊂ X? Notice that we are not allowed to restrict Y —for that question it is well known that one can restrict to a quasirandom graph. In our case, the best structure we could possibly hope for is exactly the structure described at the end of the previous section, namely a graph that resembles a random graph where the edge xy is chosen with probability p(y). The reason for this is simple: if we actually do define a random graph this way, then with high probability, any restriction of the graph to a subset of the form X′ × Y will still resemble a random graph where the edge xy is chosen with probability p(y). The main result of this section is that we can actually find this structure. Once we have shown this (the proof is not very hard), we shall draw some consequences.

At the heart of the proof is the following lemma, which is a small generalization of Lemma 7.4 of [G2]. The slightly peculiar use of (1 + η)^{1/2} instead of 1 + η is not an important feature of the statement: it just makes it a little bit more convenient to use later.

Lemma 4.1. Let G be a bipartite graph with vertex sets X and Y of size m and n, and let γ, α, η and ϵ be positive constants. Suppose that there are at least ϵm^{2} pairs (x, x′) ∈ X^{2} such that |N(x) ∩ N(x′)| ⩾ α(1 + η)^{1/2}n. Then there is a subset B ⊂ X of size at least (ϵγ)^{4η^{−1} log(α^{−1})}m such that |N(x) ∩ N(x′)| ⩾ αn for all but at most γ|B|^{2} pairs (x, x′) ∈ B^{2}.

Proof. Let r be a positive integer to be chosen later. Pick y_{1}, …, y_{r} in Y uniformly at random and let B = N(y_{1}) ∩ … ∩ N(y_{r}). Define a pair (x, x′) to be good if |N(x) ∩ N(x′)| ⩾ α(1 + η)^{1/2}n and bad if |N(x) ∩ N(x′)| < αn and let the numbers of these pairs belonging to B be g(B) and b(B) respectively. A good pair will belong to B^{2} with probability at least α^{r}(1 + η)^{r/2}, while a bad pair will belong with probability less than α^{r}, so the expected value of g(B) − γ^{−1}b(B) is at least α^{r}m^{2}(ϵ(1 + η)^{r/2} − γ^{−1}). Let r be such that ϵ(1 + η)^{r/2} − γ^{−1} ⩾ 1. Then there must exist for this r a set B such that g(B) − γ^{−1}b(B) ⩾ α^{r}m^{2}, which implies that |B| ⩾ α^{r/2}m and b(B) ⩽ γ|B|^{2}.

It remains to choose an appropriate value for r. A simple calculation shows that the inequality we needed is satisfied when r = 8η^{−1} log(ϵ^{−1}γ^{−1}) (the fact that this is not necessarily an integer is compensated for by the fact that the simple calculation was not optimized, so we shall ignore it). This gives us our set B with cardinality at least α^{4η^{−1} log(ϵ^{−1}γ^{−1})}m = (ϵγ)^{4η^{−1} log(α^{−1})}m, which proves the lemma. □

Corollary 4.2. Let G be a bipartite graph with vertex sets X and Y of sizes m and n respectively, let δ, η, ϵ and γ be positive constants less than 1. Suppose that there are at least ϵm^{2} pairs (x, x′) ∈ X^{2} such that δ_{1}(x, x′) ⩾ δ(1 + η)^{1/2}. Then there is a constant α ⩾ δ and a subset B ⊂ X of density at least (ϵγ)^{8η^{−2} log(δ^{−1})^{2}} with the following two properties.

(i) δ_{1}(x, x′) ⩾ α for all but at most γ|B|^{2} pairs (x, x′) ∈ B^{2}.

(ii) δ_{1}(x, x′) ⩽ α(1 + η) for all but at most ϵ|B|^{2} pairs (x, x′) ∈ B^{2}.

In particular, 𝔼_{x,x′∈B}|δ_{1}(x, x′) − α|^{2} ⩽ ϵ + α^{2}(γ + η^{2}).

Proof. We prove this result by iterating the previous lemma. Let B_{0} = X and let Δ_{0} = δ. Since δ_{1}(x, x′) ⩾ Δ_{0}(1 + η)^{1/2} for at least ϵ|B_{0}|^{2} pairs (x, x′) ∈ B_{0}^{2}, Lemma 4.1 gives us a subset B_{1} ⊂ B_{0} of size at least (ϵγ)^{4η^{−1} log(Δ_{0}^{−1})}|B_{0}| such that δ_{1}(x, x′) ⩾ Δ_{0} for all but at most γ|B_{1}|^{2} pairs (x, x′) ∈ B_{1}^{2}.

If we also have δ_{1}(x, x′) ⩽ Δ_{0}(1 + η) for all but at most ϵ|B_{1}|^{2} pairs (x, x′) ∈ B_{1}^{2} then B_{1} has the property we require of our set B. Otherwise, let Δ_{1} = Δ_{0}(1 + η)^{1/2}. We then know that δ_{1}(x, x′) ⩾ Δ_{1}(1 + η)^{1/2} for at least ϵ|B_{1}|^{2} pairs (x, x′) ∈ B_{1}^{2}, which is the assumption we first started with except that B_{0} and Δ_{0} have been replaced by B_{1} and Δ_{1}.

We are therefore in a position to iterate, producing a sequence of sets B_{0} ⊃ B_{1} ⊃ … and real numbers Δ_{i} = δ(1 + η)^{i/2}. Since Δ_{i} cannot exceed 1, the iteration must stop after at most t = 2 log_{1+η}(δ^{−1}) ⩽ 2η^{−1} log(δ^{−1}) steps, at which point we have found a set B with the required property. Moreover, each B_{i} has density at least (ϵγ)^{4η^{−1} log(Δ_{0}^{−1})} times the density of B_{i−1}. Therefore the set B we eventually find has density at least ((ϵγ)^{4η^{−1} log(δ^{−1})})^{t}, which is at least the bound stated.

The estimate for 𝔼_{x,x′∈B}|δ_{1}(x, x′) − α|^{2} follows from the fact that if we choose a random pair (x, x′) ∈ B^{2}, then the probability that δ_{1}(x, x′) > α(1 + η) is at most ϵ, in which case we still know that δ_{1}(x, x′) ⩽ 1, and the probability that δ_{1}(x, x′) < α is at most γ, in which case we know that δ_{1}(x, x′) ⩾ 0. □

Remark. An interesting feature of the above result is that it is only the dependence on η that is exponentially expensive. Thus, it can be applied to quite sparse sets (not as sparse as n^{99/100}, say, but much sparser than n/ log n), and we can ask for ϵ to be very small. Indeed, on this second point, the method of proof is sufficiently flexible that if one is content with worse bounds, then one can ask for much stronger conclusions. Later in the paper we shall see that this can be useful.

Given a bipartite graph G with vertex sets X and Y, let us say that a subset B ⊂ X is (ϵ, γ, η)-regular for G with parameter α if properties (i) and (ii) of Corollary 4.2 hold. The next result is a rather simple strengthening of Corollary 4.2, where the result is not a single (ϵ, γ, η)-regular set, but a partition of X into such sets. We shall use the word “density” in two senses: when it refers to a subset X′ of X then it means |X′|/|X| and when it refers to an induced bipartite subgraph G(X′, Y′) of G then it means the number of edges between X′ and Y′ divided by |X′||Y′|.

Theorem 4.3. Let δ, θ, ϵ and η be positive constants less than 1, suppose that ϵ < δ, and let G be a bipartite graph with vertex sets X and Y. Then there is a partition X = B_{0} ∪ B_{1} ∪ … ∪ B_{r} with the following properties.

(i) For each i ⩾ 1 the set B_{i} has density at least (ϵγ)^{8η^{−2} log(δ^{−1})^{2}}θ.

(ii) For each i ⩾ 1 the set B_{i} is (ϵ, γ, η)-regular for G.

(iii) For each i ⩾ 1 the graph G(B_{i}, Y) has density at least 2δ^{1/2}.

(iv) For every subset E ⊂ B_{0} of density at least θ, the graph G(E, Y) has density less than 2δ^{1/2}.

Proof. If we cannot just set X = B_{0} then there must be a subset E ⊂ X of density at least θ such that the density of the induced subgraph G(E, Y) is at least 2δ^{1/2}. Let us apply Corollary 4.2 to this subgraph. We know that 𝔼_{x,x′∈E}δ_{1}(x, x′) = 𝔼_{y}δ_{E}(y)^{2} ⩾ (𝔼_{y}δ_{E}(y))^{2} ⩾ 4δ, so if (x, x′) is a random pair chosen from E, then the probability that δ_{1}(x, x′) ⩾ 2δ is at least 2δ, and therefore the probability that δ_{1}(x, x′) ⩾ δ(1 + η)^{1/2} is at least ϵ. Corollary 4.2 therefore gives us a set B_{1} of density at least (ϵγ)^{8η^{−2} log(δ^{−1})^{2}}θ that is (ϵ, γ, η)-regular for G.

We now repeat. If we cannot set B_{0} = X \B_{1}, then there must be a subset E ⊂ X \B_{1} of density at least θ such that the density of the induced subgraph G(E, Y) is at least 2δ^{1/2}. This gives us a set B_{2} of density at least (ϵγ)^{8η^{−2} log(δ^{−1})^{2}}θ that is (ϵ, γ, η)-regular for G.

If we continue this iteration for as long as we can, then eventually we will find that the set X \ (B_{1} ∪ … ∪ B_{r}) has no subset E of density θ such that the graph G(E, Y) has density at least 2δ^{1/2}. We then set B_{0} = X \ (B_{1} ∪ … ∪ B_{r}) and the result is proved. □

The above result can be thought of as a “weak regularity lemma”, and it may help if we compare it with existing regularity lemmas. The most famous of these is Szemerédi’s regularity lemma, which starts with a parameter ϵ and provides a partition of the vertices of a graph into sets X_{1}, …, X_{k}, with k depending on ϵ only, in such a way that for at least (1 − ϵ)k^{2} pairs (X_{i}, X_{j}) the induced bipartite subgraph G(X_{i}, X_{j}) is ϵ-quasirandom. Although this is an extremely useful result, it has the drawback that the dependence of k on ϵ is very poor (and an example in [G1] shows that this is necessary).

Because of this, there are good reasons for trying to find alternative statements that are weak enough to give rise to better bounds, but still strong enough for applications. This turns out to be possible in some situations and tantalizingly difficult in others. One of the most useful weak regularity lemmas is due to Frieze and Kannan, and one way of describing how it relates to Szemerédi’s lemma is as follows. A quasirandom bipartite graph of density p is a bipartite graph that is close in the U_{2}-norm to the constant function p. Suppose that X_{1}, …, X_{k} is the partition arising in Szemerédi’s regularity lemma, and suppose that we define an averaging projection P G(x, y) of G by setting P G(x, y) to be the density of the bipartite graph G(X_{i}, X_{j}) such that x ∈ X_{i} and y ∈ X_{j}. Then Szemerédi’s lemma says that G is well-approximated by P G in the U_{2}-norm on almost all pairs (X_{i}, X_{j}). The lemma of Frieze and Kannan provides a partition that gives rise to a more global notion of approximation: this time we cannot say anything about the U_{2}-norm of G − P G if we restrict to a pair (X_{i}, X_{j}) but we can at least say that ∥G − P G∥_{U_{2}} is small. That is, G is quasirandomly approximated by P G in a global sense, but not necessarily if you restrict to the pairs (X_{i}, X_{j}).

What we have proved, though this will not become fully clear until after the next few results, is an “intermediate regularity lemma”, where G is well-approximated by P G on sets of the form X_{i} × Y. (This is a statement about bipartite graphs, though we shall obtain graph statements as well.) To summarize, for Szemerédi one can look at pairs of small sets, for Frieze and Kannan one can look at pairs of large sets, and here one can look at pairs of sets where one is small and the other large.

Theorem 4.3 provides us with a collection of graphs G(B_{i}, Y) that are individually well-behaved. However, although they are edge disjoint, they all share a vertex set Y, and the next two lemmas can be used to show that they interact in an interesting way. Roughly speaking, we shall show that if δ_{1}(x, x′) is approximately constant over pairs (x, x′) from B_{i}^{2} and also over pairs from B_{j}^{2}, then it is approximately constant over pairs from B_{i} × B_{j}. One can make this assertion precise in different ways, according to whether one uses the stronger property (iii) or the weaker property (v) of Theorem 3.12 as the initial assumption. The next lemma uses property (iii) and the one after it uses property (v). In each case, the conclusion resembles the premise in an obvious way.

We shall state our results in terms of two sets X and X′. Variables such as x, x_{1} and x_{2} will always be assumed to range over X, while variables such as x′, x′_{1} and x′_{2} will range over X′. Given two functions f : X × Y → ℂ and f′ : X′ × Y → ℂ, we shall write δ_{2}(y) for 𝔼_{x}f(x, y) and δ′_{2}(y) for 𝔼_{x′}f′(x′, y). The meaning of δ_{1} will depend in an obvious way on the variables inside it: for example, δ_{1}(x, x′) = 𝔼_{y}f(x, y)\overline{f′(x′, y)}.

Lemma 4.4. Let X, X′ and Y be finite sets, let f : X × Y → ℂ and let f′ : X′ × Y → ℂ. Let 0 < c ⩽ 2^{−24}, and suppose that 𝔼_{x_{1},x_{2}} |δ_{1}(x_{1}, x_{2}) − ∥δ_{2}∥_{2}^{2}|^{2} ⩽ c∥f∥_{U_{2}}^{4}

and that 𝔼_{x′_{1},x′_{2}} |δ_{1}(x′_{1}, x′_{2}) − ∥δ′_{2}∥_{2}^{2}|^{2} ⩽ c∥f′∥_{U_{2}}^{4}. Then 𝔼_{x,x′} |δ_{1}(x, x′) − ⟨δ_{1}, δ_{2}⟩|^{2} ⩽ 16c^{1/16}∥f∥_{U_{2}}^{2}∥f′∥_{U_{2}}^{2}.

Proof. By Theorem 3.12, we know that there is a constant c_{2}, with a power-type dependence on c, such that ∥f − 1 ⊗ δ_{2}∥_{U_{2}}^{4} ⩽ c_{2}∥f∥_{U_{2}}^{4} and ∥f′ − 1 ⊗ δ′_{2}∥_{U_{2}}^{4} ⩽ c_{2}∥f′∥_{U_{2}}^{4}. We also know that

δ_{1}(x, x′) − ⟨δ_{1}, δ_{2}⟩ = 𝔼_{y}(f(x, y)\overline{f′(x′, y)} − δ_{2}(y)\overline{δ′_{2}(y)})
= 𝔼_{y}(f(x, y) − δ_{2}(y))\overline{f′(x′, y)} + 𝔼_{y}δ_{2}(y)(\overline{f′(x′, y)} − \overline{δ′_{2}(y)})
= 𝔼_{y}g(x, y)\overline{f′(x, y)} + 𝔼_{y}δ_{2}(y)\overline{g′(x, y)} ,

where we have set g = f − 1 ⊗ δ_{2} and g′ = f′ − 1 ⊗ δ′_{2}. By Minkowski’s inequality, we may therefore deduce that (𝔼_{x,x′} |δ_{1}(x, x′) − ⟨δ_{1}, δ_{2}⟩|^{2})^{1/2} is at most

(𝔼_{x,x′} |𝔼_{y}g(x, y)\overline{f′(x′, y)}|^{2})^{1/2} + (𝔼_{x,x′} |𝔼_{y}δ_{2}(y)\overline{g′(x′, y)}|^{2})^{1/2} .

Let us estimate these two terms separately. First,

𝔼_{x,x′} |𝔼_{y}g(x, y)\overline{f′(x′, y)}|^{2}
= 𝔼_{x,x′}𝔼_{y,y′}g(x, y)\overline{g(x, y′)}\overline{f′(x′, y)}f′(x′, y)
= 𝔼_{y,y′}(𝔼_{x}g(x, y)\overline{g(x, y′)})(𝔼_{x′} \overline{f′(x′, y)}f′(x′, y))
⩽ (𝔼_{y,y′} |𝔼_{x}g(x, y)\overline{g(x, y′)}|^{2})^{1/2}(𝔼_{y,y′} |𝔼_{x′} \overline{f′(x′, y)}f′(x′, y)|^{2})^{1/2}
= ∥g∥_{U_{2}}^{2}∥f′∥_{U_{2}}^{2} .

Similarly, the square of the second term is at most ∥1 ⊗ δ_{2}∥_{U_{2}}^{2}∥g′∥_{U_{2}}^{2} = ∥δ_{2}∥_{2}^{2}∥g′∥_{U_{2}}^{2} ⩽ ∥f∥_{U_{2}}^{2}∥g′∥_{U_{2}}^{2}.

It follows that the sum of the two terms is at most 2c_{2}^{1/4}∥f∥_{U_{2}}∥f′∥_{U_{2}}, so we may take c′ = 4c_{2}^{1/2}. Looking carefully at the bounds in Theorem 3.12, one can check that this is at most 16c^{1/16} when c ⩽ 2^{−24}. □

Lemma 4.4 tells us that if the variance of δ_{1} is small when it is restricted to X^{2} and small when it is restricted to X^{′2}, then the variance is small when it is restricted to X × X′. The next lemma uses property (v) of Theorem 3.12 and arrives at a slightly weaker and more global conclusion, which implies in particular that, however you choose subsets A ⊂ X′ and A′ ⊂ X′ that are not too small, the average 𝔼_{x∈A}𝔼_{x′∈A′}δ_{1}(x, x′) will be roughly the same.

Lemma 4.5. Let X, X′ and Y be finite sets, let f : X × Y → ℂ and let f′ : X′ × Y → ℂ. Suppose that 𝔼_{y}|𝔼_{x}f(x, y)v(x)|^{2} ⩽ c∥f∥_{U_{2}}^{2}∥v∥_{2}^{2} whenever 𝔼_{x}v(x) = 0, and 𝔼_{y}|𝔼_{x′}f′(x′, y)v′(x)|^{2} ⩽ c∥f′∥_{U_{2}}^{2}∥v′∥_{2}^{2} whenever 𝔼_{x′}v′(x′) = 0. Then

|𝔼_{x,x′}δ_{1}(x, x′)u(x)u′(x′) − 𝔼_{x,x′}u(x)u′(x′)⟨δ_{2}, δ′_{2}⟩| ⩽ c^{1/2}∥f∥_{U_{2}}∥f′∥_{U_{2}}∥u∥_{2}∥u′∥_{2} .

Proof. Let u : X → ℂ and u′ : X′ → ℂ be arbitrary functions. Let τ = 𝔼_{x}u(x) and τ′ = 𝔼_{x′}u(x′), and let u(x) = τ + v(x) and u′(x′) = τ′ + v′(x′). Let us write F and F′ for the linear maps from X and X′ to Y associated with the functions f and f′. That is, F u(y) = 𝔼_{x}f(x, y)u(x) and F′u′(y) = 𝔼_{x′}f′(x′, y)u′(x′). We shall also write τ and τ′ for the constant functions that take values τ and τ′.

Note first that, for any u : X → ℂ,

∥F u∥_{2}^{2} = 𝔼_{x_{1},x_{2}}δ_{1}(x_{1}, x_{2})u(x_{1})\overline{u(x_{2})} ⩽ (𝔼_{x_{1},x_{2}}δ_{1}(x_{1}, x_{2})^{2})^{1/2}∥u∥_{2}^{2} = ∥f∥_{U_{2}}^{2}∥u∥_{2}^{2} ,

so the norm of F before we restrict it to the space of functions of mean zero is at most ∥f∥_{U_{2}}. (This also follows easily from Lemma 3.4.) Similarly, we have the corresponding result for F′ and f′. It follows that

|⟨F u, F′u′⟩ − ⟨F τ, F′τ′⟩| ⩽ |⟨F v, F′τ′⟩| + |⟨F τ, F′v′⟩|
⩽ ∥F v∥_{2}∥F′τ′∥_{2} + ∥F τ∥_{2}∥F′v′∥_{2}
⩽ c^{1/2}∥f∥_{U_{2}}∥f′∥_{U_{2}}(∥v∥_{2}∥τ′∥_{2} + ∥τ∥_{2}∥v′∥_{2}
⩽ c^{1/2}∥f∥_{U_{2}}∥f′∥_{U_{2}}∥u∥_{2}∥u′∥_{2} .

Now F τ = τδ_{2}, F′τ′ = τ′δ′_{2}, and ⟨F u, F′u′⟩ = 𝔼_{x,x′}δ_{1}(x, x′)u(x)u′(x′), so this implies the result. □

Of particular interest to us is the obvious graph-theoretical consequence of the above facts: if f, f′, u and u′ all take values in {0, 1}, then f and f′ are the adjacency matrices of bipartite graphs G ⊂ X × Y and G′ ⊂ X′ × Y, and u and u′ are characteristic functions of subsets A ⊂ X and A′ ⊂ X′. Then ⟨F u, F′u′⟩ is the number of paths of length 2 from A to A′, and Lemmas 4.4 and 4.5 imply that this is close to |A||A′|⟨δ_{2}, δ′_{2}⟩. That is, the product of G and G′ has roughly the same density ⟨δ_{2}, δ′_{2}⟩ everywhere.

Theorem 4.3 therefore gives us a strong regularity statement for “squares” of graphs, or more accurately for the function δ_{1}(x, x′) (which corresponds to the product of the adjacency matrix of G with its transpose). It tells us that we can partition the vertex set of G into sets B_{0}, B_{1}, …, B_{r} in such a way that there are almost no edges out of B_{0} and such that for every i, j ⩾ 1 there exists α_{ij} such that δ_{1}(x, x′) is approximately α_{ij} for almost every (x, x′) ∈ B_{i} ×B_{j}. This is a significantly stronger statement than can be made about the partition in the weak regularity lemma of Frieze and Kannan, but the bound is of comparable size.

We now make this statement precise, beginning with a technical lemma.

Lemma 4.6. Let 0 < δ < 1 and 0 < c < 1/100, and let ϵ = δ^{2}c/4 and η = c^{1/2}/2. Let G be a bipartite graph of density δ with vertex sets X and Y and suppose that B ⊂ X is (ϵ, ϵ, η)-regular for G, with a parameter α ⩾ δ, and let δ_{B}(y) denote the normalized degree in B of a vertex y ∈ Y. Then

𝔼_{x,x′∈B}|δ_{1}(x, x′) − ∥δ_{B}∥^{2}|^{2} ⩽ c𝔼_{x,x′∈B}δ_{1}(x, x′)^{2} .

Proof. By the last part of the conclusion of Corollary 4.2,

𝔼_{x,x′∈B}|δ_{1}(x, x′) − α|^{2} ⩽ δ^{2}c/2 + α^{2}c/4 ⩽ 3α^{2}c/4 .

It follows that (𝔼_{x,x′∈B}|δ_{1}(x, x′)|^{2})^{1/2} ⩾ α − (3α^{2}c/4)^{1/2} ⩾ α(1 − \sqrt{3c}/2), so we have shown that

𝔼_{x,x′∈B}|δ_{1}(x, x′) − α|^{2} ⩽ \frac{3c}{4(1 − \sqrt{3c}/2)^{2}} 𝔼_{x,x′∈B}δ_{1}(x, x′)^{2} .

It can be checked that this is at most c𝔼_{x,x′∈B}δ_{1}(x, x′)^{2} when c < 1/100. The result follows, since ∥δ_{B_{i}}∥_{2}^{2} is the mean of δ_{1} over B^{2}. □

Theorem 4.7. Let ζ, θ > 0 and let G be a bipartite graph with vertex sets X and Y. Then there is a partition of X into sets B_{0}, B_{1}, …, B_{r}, with r ⩽ θ^{−1} exp(Lζ^{−16}(log(ζ^{−1})^{3}) for some absolute constant L, with the following property. For each i and each y ∈ Y let δ_{B_{i}}(y) be the normalized degree of y in B_{i}. Then

𝔼_{x∈B_{i}}𝔼_{x′∈B_{j}} |δ_{1}(x, x′) − ⟨δ_{B_{i}}, δ_{B_{j}}⟩|^{2} ⩽ ζ

whenever i, j ⩾ 1, and either B_{0} has density less than θ or the same inequality holds for i, j ⩾ 0.

Proof. Let c = 2^{−64}ζ^{16}, δ = ζ^{2}/4, ϵ = γ = δ^{2}c/4 and η = c^{1/2}/2, and let B_{0}, B_{1}, …, B_{r} be the partition arising in Theorem 4.3 for these parameters.

For each i let f_{i} denote the restriction of the characteristic function of G to the set B_{i} ×Y. If i ⩾ 1, then B_{i} is (ϵ, γ, η)-regular for G and has density at least 2δ^{1/2}. Therefore, by Lemma 4.6,

𝔼_{x,x′∈B_{i}}|δ_{1}(x, x′) − ∥δ_{B_{i}}|^{2} ⩽ c𝔼_{x,x′∈B_{i}}δ_{1}(x, x′)^{2} = ∥f_{i}∥_{U_{2}}^{4} .

We now have the conditions of Lemma 4.4 for any pair of sets B_{i} and B_{j} with i, j ⩾ 1. It follows that

𝔼_{x∈B_{i}}𝔼_{x′∈B_{j}}|δ_{1}(x, x′) − ⟨δ_{B_{i}}, δ_{B_{j}}⟩|^{2} ⩽ ζ∥f_{i}∥_{U_{2}}^{2}∥f_{j}∥_{U_{2}}^{2}

for every such pair.

We also know that

𝔼_{x∈B_{0}}𝔼_{x′∈B_{i}}|δ_{1}(x, x′)|^{2} ⩽ ∥f_{0}∥_{U_{2}}^{2}∥f_{i}∥_{U_{2}}^{2} ,

by Lemma 2.2. But either B_{0} has density at most θ, in which case we are done, or the graph G(B_{0}, Y) has density at most 2δ^{1/2}, from which it follows that ∥f_{0}∥_{U_{2}}^{4} ⩽ ∥f_{0}∥_{2}^{4} ⩽ ∥f_{0}∥_{2}^{2}∥f_{0}∥_{∞}^{2} ⩽ 4δ. (The first of these inequalities can be deduced easily from Lemma 2.4, or else it is an easy exercise to prove it directly.) Since the mean of δ_{1}(x, x′) over B_{0} × B_{i} is ⟨δ_{B_{0}}, δ_{B_{i}}⟩, it follows that

𝔼_{x∈B_{0}}𝔼_{x′∈B_{i}}|δ_{1}(x, x′) − ⟨δ_{B_{0}}, δ_{B_{i}}⟩|^{2} ⩽ 2δ^{1/2}∥f_{i}∥_{U_{2}}^{2} ⩽ ζ .

This shows that the partition has the desired properties, and the bounds of Theorem 4.3 can be used to check the upper bound on the size of r. □

Remark. Essentially the same proof gives a non-symmetric version of the result, in which one obtains a strong regularity lemma for general graph products. That is, given a bipartite graph G with vertex sets X and Y, and a bipartite graph G′ with vertex sets X′ and Y, one can find partitions of X and X′ such that for almost every B in the first partition and B′ in the second partition the function δ_{1}(x, x′) (defined to be the density of the intersection of the G-neighbourhood of x with the G′-neighbourhood of x′) is roughly constant over B × B′. In the case X = X′ one can even ask for the two partitions to be the same, by proving a version of Lemma 4.1 that works for more than one graph at the same time. (This one can do, for example, by considering a bipartite graph from X to Y^{2} that joins x to (y, y′) if and only if (x, y) ∈ G and (x, y′) ∈ G′.)

We now prove a strengthening of Lemma 4.4 that allows us to exploit more fully the fact that we can obtain (ϵ, η) regular sets with ϵ much smaller than η. The next lemma shows that if B is (ϵ, η)-regular for a graph G, then all subsets C ⊂ B have images, under the linear map given by the adjacency matrix of the graph G(B, Y), that are approximately proportional to each other, provided that they are not too small—where the lower bound we require on the size tends to zero with ϵ and so can be chosen to be very small. The one after it will show that if B_{i} and B_{j} are (ϵ, η)-regular with a very small ϵ, then δ_{1}(x, x′) is approximately equal to α_{ij} for almost every (x, x′) ∈ C_{i} × C_{j}, when C_{i} and C_{j} are subsets of B_{i} and B_{j} that are not too small—again with a lower bound that can be chosen to be very small.

Lemma 4.8. Let δ, η, ϵ and κ be positive constants such that η ⩽ 1/4, κ ⩽ 1 and ϵκ^{−2} ⩽ δη. Let X and Y be finite sets and let G be a bipartite graph with vertex sets X and Y. Suppose that B ⊂ X is (ϵ, ϵ, η)-regular for G with an α that is at least as big as δ. Let C be a subset of B of size at least κ|B|. For each y ∈ Y, let δ_{B}(y) and δ_{C}(y) be the normalized degrees of y in the induced subgraphs G(B, Y) and G(C, Y), respectively. Then ∥δ_{B} − δ_{C}∥_{2}^{2} ⩽ 8η∥δ_{B}∥_{2}^{2}.

Proof. By assumption, there exists α ⩾ δ such that δ_{1}(b_{1}, b_{2}) lies between α and α(1 + η) for all but at most ϵ|B|^{2} pairs (b_{1}, b_{2}) ∈ B^{2}. Therefore, if |C| = κ|B|, then δ_{1}(b, c) lies between α and α(1 + η) for all but at most ϵκ^{−1}|B||C| pairs (b, c) ∈ B × C. It follows that

⟨δ_{B}, δ_{C}⟩ = 𝔼_{y}δ_{B}(y)δ_{C}(y) = 𝔼_{c∈C}𝔼_{b∈B}δ_{1}(b, c)

lies between α − ϵκ^{−1} and α(1 + η) + ϵκ^{−1}.

Similar arguments show that ∥δ_{B}∥_{2}^{2} lies between α−ϵ and α(1+η)+ϵ and that ∥δ_{C}∥_{2}^{2} lies between α − ϵκ^{−2} and α(1 + η) + ϵκ^{−2}. Since ϵκ^{−2} ⩽ αη, all three of ∥δ_{B}∥_{2}^{2}, ∥δ_{C}∥_{2}^{2} and ⟨δ_{B}, δ_{C}⟩ lie between α(1 − η) and α(1 + 2η). It follows that

∥δ_{B} − δ_{C}∥_{2}^{2} ⩽ 2α(1 + 2η) − 2α(1 − η) = 6αη ⩽ 8η∥δ_{B}∥_{2}^{2} .  □

Lemma 4.9. Let δ, η, ϵ and κ be positive constants such that η ⩽ 1/8, κ ⩽ 1 and ϵκ^{−2} ⩽ δ^{2}η^{2}. Let X and Y be finite sets and let G be a bipartite graph with vertex sets X and Y. Suppose that B and B′ are subsets of X that are both (ϵ, ϵ, η)-regular for G with parameters α and α′, respectively, that are at least as big as δ. Let C and C′ be subsets of B and B′ with sizes at least κ|B| and κ|B′|, respectively. Let f_{B}, f′_{B}, f_{C} and f_{C′} denote the restrictions of the characteristic function of G to the sets B × Y, B′ × Y, C × Y and C′ × Y, respectively, and for each y ∈ Y, let δ_{B}(y), δ_{C}(y), δ_{B′}(y) and δ_{C′}(y) be the normalized degrees of y in the corresponding induced subgraphs. Then there is an absolute constant L such that

𝔼_{x∈C}𝔼_{x′∈C′}|δ_{1}(x, x′) − ⟨δ_{B}, δ_{B′}⟩|^{2} ⩽ Lη^{1/8}∥f_{B}∥_{U_{2}}^{2}∥f_{B′}∥_{U_{2}}^{2} .

Proof. We begin by proving a similar inequality with ⟨δ_{C}, δ_{C′}⟩ instead of ⟨δ_{B}, δ_{B′}⟩. We then deduce from Lemma 4.8 that the two inner products are approximately equal. The basic argument is simple but there are some tedious details involved in passing from an estimate in terms of one quantity to a similar estimate in terms of another that is approximately equal to it.

To prove the inequality with ⟨δ_{C}, δ_{C′}⟩ we use Lemma 4.4. Our assumptions tell us that δ_{1}(x_{1}, x_{2}) lies between α and α(1 + η) for all but at most ϵ|B|^{2} pairs (x_{1}, x_{2}) ∈ B^{2}, and hence for all but at most ϵκ^{−2}|C|^{2} pairs (x_{1}, x_{2}) ∈ C^{2}. Therefore, the variance of δ_{1}(x_{1}, x_{2}) over C^{2} is at most ϵκ^{−2} + η^{2}α^{2}, which is at most 2η^{2}α^{2}. Similarly, the variance of δ_{1}(x′_{1}, x′_{2}) over C^{′2} is at most 2η^{2}α^{2}.

Let us write f_{C} for the restriction of f to C × Y. Then the mean of δ_{1}(x_{1}, x_{2}) over C^{2} is ∥δ_{C}∥_{2}^{2}, while the mean of δ_{1}(x_{1}, x_{2})^{2} is ∥f_{C}∥_{U_{2}}^{4}. Therefore, ∥δ_{C}∥_{2}^{2} ⩽ ∥f_{C}∥_{U_{2}}^{2}. From the proof of Lemma 4.8, we know that ∥δ_{C}∥_{2}^{2} is at least α(1 − η). (There we assumed a different bound for κ, but the assumption was weaker so the conclusion is valid here too.) But (1 − η)^{2} > 1/2, so ∥f_{C}∥_{U_{2}}^{4} ⩾ ∥δ_{C}∥_{2}^{4} ⩾ α^{2}/2. Therefore, our statement about the variance of δ_{1}(x_{1}, x_{2}) over C^{2} implies that

𝔼_{x_{1},x_{2}∈C} |δ_{1}(x_{1}, x_{2}) − ∥δ_{C}∥_{2}^{2}|^{2} ⩽ 4η^{2}∥f_{C}∥_{U_{2}}^{4} .

The same argument shows that

𝔼_{x′_{1},x′_{2}∈C′} |δ_{1}(x′_{1}, x′_{2}) − ∥δ_{C′}∥_{2}^{2}|^{2} ⩽ 4η^{2}∥f_{C′}∥_{U_{2}}^{4} .

We therefore have the hypotheses of Lemma 4.4, with C and C′ replacing X and X′, with f_{C} and f_{C′} replacing f and f′, and with c = 4η^{2}. It follows from that lemma that

𝔼_{x∈C}𝔼_{x′∈C′} |δ_{1}(x, x′) − ⟨δ_{C}, δ_{C′}⟩|^{2} ⩽ Kη^{1/8}∥f_{C}∥_{U_{2}}^{2}∥f_{C′}∥_{U_{2}}^{2}

for some absolute constant K.

It remains to recast this conclusion slightly. By Lemma 4.8 we know that ∥δ_{B} −δ_{C}∥_{2}^{2} ⩽ 8η∥δ_{B}∥_{2}^{2} and ∥δ_{B′} − δ_{C′}∥_{2}^{2} ⩽ 8η∥δ_{B′}∥_{2}^{2}. Therefore,

\begin{aligned}|⟨δ_{B}, δ_{B′}⟩ − ⟨δ_{C}, δ_{C′}⟩| & ⩽ |⟨δ_{B}, δ_{B′} − δ_{C′}⟩| + |⟨δ_{B} − δ_{C}, δ_{C′}⟩| \\ & ⩽ 2(8η)^{1/2}∥δ_{B}∥_{2}∥δ_{B′}∥_{2} . \end{aligned}

Since ⟨δ_{C}, δ_{C′}⟩ is the mean of δ_{1}(x, x′) over C × C′, we have the equality

\begin{aligned}𝔼_{x∈C}𝔼_{x′∈C′} |δ_{1}(x, x′) & − ⟨δ_{B}, δ_{B′}⟩|^{2} \\ & = 𝔼_{x∈C}𝔼_{x′∈C′} |δ_{1}(x, x′) − ⟨δ_{C}, δ_{C′}⟩|^{2} + |⟨δ_{B}, δ_{B′}⟩ − ⟨δ_{C}, δ_{C′}⟩|^{2} , \end{aligned}

which, by the estimates we have obtained, is at most Kη^{1/8}∥f_{C}∥_{U_{2}}^{2}∥f_{C′}∥_{U_{2}}^{2} + 32η∥δ_{B}∥_{2}^{2}∥δ_{B′}∥_{2}^{2}.

Finally, we note that ∥f_{C}∥_{U_{2}}^{4} = 𝔼_{x_{1},x_{2}∈C}δ_{1}(x_{1}, x_{2})^{2} ⩽ ∥δ_{C}∥^{4} + 4η^{2}∥f_{C}∥_{U_{2}}^{4}, by our inequality for the variance earlier. Since η < 1/8, it follows that ∥f_{C}∥_{U_{2}}^{4} ⩽ 2∥δ_{C}∥_{2}^{4}. Again because η < 1/8 we know from the fact that ∥δ_{B} − δ_{C}∥_{2}^{2} ⩽ 8η∥δ_{B}∥_{2}^{2} that ∥δ_{C}∥_{2} ⩽ 2∥δ_{B}∥_{2}. And we also know that ∥δ_{B}∥_{2} ⩽ ∥f_{B}∥_{U_{2}}. Putting this together, we find that ∥f_{C}∥_{U_{2}}^{4} ⩽ 32∥f_{B}∥_{U_{2}}^{4}. Similarly, ∥f_{C′}∥_{U_{2}}^{4} ⩽ 32∥f_{B′}∥_{U_{2}}^{4}. Therefore,

𝔼_{x∈C}𝔼_{x′∈C′} |δ_{1}(x, x′) − ⟨δ_{B}, δ_{B′}⟩|^{2} ⩽ (32η + 32Kη^{1/8})∥f_{B}∥_{U_{2}}^{2}∥f_{B′}∥_{U_{2}}^{2} ,

which proves the lemma. □

§5. An application to additive combinatorics.

Let N be a positive integer, let ℤ_{N} denote the set of integers mod N and let A be a subset of ℤ_{N} of size ⌊N/2⌋. If x ∈ ℤ_{N} is chosen randomly, then the expected size of A ∩ (A + x) is |A|^{2}/N, which is approximately N/4. Must there exist some x such that A ∩ (A + x) has approximately this size?

In general, the answer is obviously no: if N is even, then A could be the set of all even elements of ℤ_{N}, and then A ∩ (A + x) would have size 0 or N/2 for every x. However, there is no such easy counterexample if N is prime, so what happens in that case?

This question has an odd history. I thought of it while working on another problem, then thought I had a solution, and then realized that my solution was incorrect (because a certain error term was larger than a certain main term). But I liked the question, so I put it on a sheet of questions to accompany a course I gave on additive combinatorics. However, it became clear that it was more than just an exercise: none of the students attending the course managed to solve it, and it was some time before a solution was finally obtained, by Green and Konyagin [GK]. The best bound now known is due to Sanders [S], who proved that there is some x such that ||A ∩ (A + x)| − N/4| is at most CN(log N)^{−1/3}.

In this section, we shall give a new proof of this result. We obtain a considerably worse bound, so the interest is in the method rather than the conclusion (though it is not out of the question that one might be able to obtain better bounds by developing this method). The novel feature of the method is that it is “purely combinatorial”, in the sense that it uses no Fourier analysis. That is, all our arguments take place in “physical space”, whereas Fourier analysis was essential to the arguments of Green and Konyagin and of Sanders.

The first step is to prove a variant of Corollary 4.2. As mentioned earlier, it can be useful to strengthen the conclusion of this result, and that is what we shall do now. The extra strength is that the number of pairs for which δ_{1}(x, x′) > α(1 + η) is not just a small fraction of |B|^{2}, but a small fraction that depends on the density of B.

Lemma 5.1. Let G be a bipartite graph with vertex sets X and Y of sizes m and n respectively, let δ, η, ϵ and γ be positive constants less than 1. Suppose that there are at least ϵm^{2} pairs (x, x′) ∈ X^{2} such that δ_{1}(x, x′) ⩾ δ(1 + η)^{1/2}. Then there is a constant α ⩾ δ and a subset B ⊂ X with the following properties.

(i) B has density β ⩾ exp(−T), where T = (8η^{−1} log δ^{−1})^{2η^{−1} log δ^{−1}}(log ϵ^{−1}+log γ^{−1}). In particular, if ϵ and γ are both at least η^{2}δ^{2} and we set t = 4η^{−1} log δ^{−1}, then the density of B is at least exp(−t^{t}).

(ii) B is (ϵβ^{2}, γ, η)-regular with parameter α.

Proof. The argument is very similar to the proof of Corollary 4.2. Let B_{0} = X, let β_{0} = 1 and let Δ_{0} = δ. Since δ_{1}(x, x′) ⩾ Δ_{0}(1 + η)^{1/2} for at least ϵβ_{0}^{2}|B_{0}|^{2} pairs (x, x′) ∈ B_{0}^{2}, Lemma 4.1 gives us a subset B_{1} ⊂ B_{0} of size at least (ϵβ_{0}^{2}γ)^{4η^{−1} log(Δ_{0}^{−1})}|B_{0}| such that δ_{1}(x, x′) ⩾ Δ_{0} for all but at most γ|B_{1}|^{2} pairs (x, x′) ∈ B_{1}^{2}. Let β_{1} be the density of B_{1}.

If we also have δ_{1}(x, x′) ⩽ Δ_{0}(1 + η) for all but at most ϵβ_{1}^{2}|B_{1}|^{2} pairs (x, x′) ∈ B_{1}^{2} then B_{1} has the property we require of our set B. Otherwise, let Δ_{1} = Δ_{0}(1 + η)^{1/2}. We then know that δ_{1}(x, x′) ⩾ Δ_{1}(1 + η)^{1/2} for at least ϵβ_{1}^{2}|B_{1}|^{2} pairs (x, x′) ∈ B_{1}^{2}, which is the assumption we first started with except that B_{0}, β_{0} and Δ_{0} have been replaced by B_{1}, β_{1} and Δ_{1}.

We are therefore in a position to iterate. Again the iteration must stop after at most t = 2 log_{1+η} δ^{−1} ⩽ 2η^{−1} log δ^{−1} steps. However, this time what we can say about the density of the B_{i} is weaker: we know that β_{i} ⩾ (ϵβ_{i−1}^{2}γ)^{4η^{−1} log(δ^{−1})}. Taking logarithms and writing a_{i} = log β_{i}^{−1}, we have a_{0} = 0 and

a_{i} ⩽ 4η^{−1} log δ^{−1}(log ϵ^{−1} + log γ^{−1} + 2a_{i−1}) ,

from which it is an easy exercise to deduce that a_{i} ⩽ (8η^{−1} log δ^{−1})^{i}(log ϵ^{−1} + log γ^{−1}). This implies the lower bound stated for the density of B. □

The next lemma shows that we can pass to a large subset of B with an even stronger property. There are some complicated relationships between the parameters involved, but the point to bear in mind is that in applications we would like κ_{0} to be very small. Since it does not cost too much to make ϵ very small, we can have this, even if γ and η are fixed.

Lemma 5.2. Let δ, ϵ > 0 and let 0 < η ⩽ 1/4 and 0 < γ < η/4. Let G be a bipartite graph with vertex sets X and Y and suppose that B_{0} ⊂ X is (ϵ, γ, η)-regular for G with α ⩾ δ. Let κ_{0} = (ϵ/δη)^{1/2} and suppose that κ_{0} ⩽ η/2. Then B_{0} has a subset B of cardinality at least |B_{0}|/2 such that ∥δ_{C} − δ_{B}∥_{2}^{2} ⩽ 24η∥δ_{B}∥_{2}^{2} for every subset C ⊂ B of size at least κ_{0}|B_{0}|.

Proof. Let B be any subset of B_{0} of size at least |B_{0}|/2, let C ⊂ B be a subset of size κ|B|, with κ ⩾ κ_{0}, let θ = 24η and suppose that ∥δ_{C} − δ_{B}∥_{2}^{2} ⩾ θ∥δ_{B}∥_{2}^{2}.

The main fact on which our calculations will depend is that for any subset D ⊂ B with |D| ⩾ κ_{0}|B_{0}| we have ∥δ_{D}∥_{2}^{2} ⩽ α(1 + 2η) ⩽ (1 + 4η)∥δ_{B}∥_{2}^{2}. To see the first inequality, we use the fact that there are at most ϵ|B_{0}|^{2} pairs (x, x′) ∈ B^{2} such that δ_{1}(x, x′) ⩾ α(1 + η), from which it follows that

∥δ_{D}∥_{2}^{2} = 𝔼_{x,x′∈D}δ_{1}(x, x′) ⩽ κ_{0}^{−2}ϵ + α(1 + η) ⩽ α(1 + 2η) ,

as claimed. As for the second, we know that ∥δ_{B}∥_{2}^{2} ⩾ α(1 − 4γ) ⩾ α(1 − η). Since η ⩽ 1/4, one can check that 1 + 2η ⩽ (1 + 4η)(1 − η).

An annoying technicality is that we have to show independently that κ cannot be greater than 1 − κ_{0}. Let us therefore suppose that C ⊂ B has size κ|B| with κ > 1 − κ_{0} and prove that ∥δ_{C} − δ_{B}∥_{2} < θ∥δ_{B}∥_{2}. We shall use repeatedly the fact that if D is any subset of B (or indeed of X) then |D|δ_{D} is the vector ∑_{x∈D} N_{x}, where N_{x} is the characteristic function of the neighbourhood of x. We shall also use the fact that the vectors N_{x} are positive, so that if D ⊂ E then the norm of |D|δ_{D} is at most the norm of |E|δ_{E}. First, note that

δ_{B} − κδ_{C} = |B|^{−1}(|B|δ_{B} − |C|δ_{C}) = |B|^{−1}|B \ C|δ_{B\C} .

Now let D be a subset of |B| of size between κ_{0}|B_{0}| and 2κ_{0}|B_{0}| that contains B \ C. Let |D| = λ|B|. Then by our observations above, the norm of the right hand side is at most |B|^{−1}|D|∥δ_{D}∥_{2} = λ∥δ_{D}∥_{2}. Because |D| ⩾ κ_{0}|B_{0}|, we know that ∥δ_{D}∥_{2}^{2} ⩽ (1 + 4η)∥d_{B}∥_{2}^{2}. Therefore, we can certainly say that ∥δ_{B} − κδ_{C}∥_{2} ⩽ 2λ^{1/2}∥δ_{B}∥_{2}. We also know (using the fact that ∥δ_{C}∥_{2}^{2} ⩽ (1 + 4η)∥δ_{B}∥_{2}^{2} and that η ⩽ 1/4), that

∥δ_{C} − κδ_{C}∥_{2} = (1 − κ)∥δ_{C}∥_{2} ⩽ 2κ_{0}^{1/2}∥δ_{B}∥_{2} .

Since λ ⩽ 4κ_{0}, it follows from the triangle inequality that ∥δ_{C} − δ_{B}∥_{2} ⩽ 6κ_{0}^{1/2}∥δ_{B}∥_{2}. Since 36κ_{0}^{2} ⩽ θ, this shows what we wanted.

Now δ_{B} = κδ_{C} + (1 − κ)δ_{B\C}. It follows that δ_{B} − δ_{C} = (1 − κ)(δ_{B\C} − δ_{C}), so our assumption implies that ∥δ_{B\C} − δ_{C}∥_{2} > θ∥δ_{B}∥_{2} as well. Let us use these facts to prove that κ ⩽ 1/3. Indeed,

∥δ_{B}∥_{2}^{2} = (1 − κ)^{2}∥δ_{B\C}∥_{2}^{2} + κ^{2}∥δ_{C}∥_{2}^{2} + 2κ(1 − κ)⟨δ_{B\C}, δ_{C}⟩

= (1 − κ)^{2}∥δ_{B\C}∥_{2}^{2} + κ^{2}∥δ_{C}∥_{2}^{2} + κ(1 − κ)(∥δ_{B\C}∥_{2}^{2} + ∥δ_{C}∥_{2}^{2} − ∥δ_{B\C} − δ_{C}∥_{2}^{2})

⩽ α(1 + 2η)((1 − κ)^{2} + κ^{2} + 2κ(1 − κ)) − κ(1 − κ)∥δ_{B\C} − δ_{C}∥_{2}^{2}
⩽ α(1 + 2η) − κ(1 − κ)θ∥δ_{B}∥_{2}^{2} .

If κ > 1/3, then κ(1 − κ) > 1/5, so it follows that ∥δ_{B}∥_{2}^{2} < α(1 + 2η)(1 + θ/5)^{−1}. It can be checked that this is at most (1 − η)α, which contradicts the lower bound we have for ∥δ_{B}∥_{2}^{2}.

Those were just preliminaries, and we now come to the main part of the proof. From the second line of the above calculation we have

∥δ_{B}∥_{2}^{2} = (1 − κ)∥δ_{B\C}∥_{2}^{2} + κ∥δ_{C}∥_{2}^{2} − κ(1 − κ)∥δ_{B\C} − δ_{C}∥_{2}^{2} .

By our assumption, this implies that

(1 + κ(1 − κ)θ)∥δ_{B}∥_{2}^{2} ⩽ (1 − κ)∥δ_{B\C}∥_{2}^{2} + κ∥δ_{C}∥_{2}^{2} .

Now ∥δ_{C}∥_{2}^{2} ⩽ (1 + 2η)(1 − η)^{−1}∥δ_{B}∥_{2}^{2} ⩽ (1 + 4η)∥δ_{B}∥_{2}^{2}, so

(1 + κ(1 − κ)θ − (1 + 4η)κ)∥δ_{B}∥_{2}^{2} ⩽ (1 − κ)∥δ_{B\C}∥_{2}^{2} .

It can be checked that the left hand side is at least (1 − κ)(1 + 16ηκ)∥δ_{B}∥_{2}^{2}, and also that (1 + 16ηκ) ⩾ (1 − κ)^{−8η} when η ⩽ 1/4 and κ < 1/3, so this shows that ∥δ_{B\C}∥_{2}^{2} ⩾ (1 − κ)^{−8η}∥δ_{B}∥_{2}^{2}.

This allows us to do an iteration. We have just shown that if B is any subset of B_{0} of size at least |B_{0}|/2 for which the conclusion does not hold, then we can find κ ⩽ 1/3 and a subset B′ ⊂ B of size (1 − κ)|B| such that ∥δ_{B′}∥_{2}^{2} ⩾ (1 − κ)^{−8η}∥δ_{B}∥_{2}^{2}. Let us therefore choose a maximal sequence B_{0} ⊃ B_{1} ⊃ … ⊃ B_{r} such that |B_{i}| = (1 − κ_{i})|B_{i−1}|, 0 < κ_{i} ⩽ 1/3 and ∥δ_{B_{i}}∥_{2}^{2} ⩾ (1 − κ_{i})^{−8η}∥δ_{B_{i−1}}∥_{2}^{2} for each i.

If we do this, then there cannot be any k such that ∏_{i=1}^{k}(1 − κ_{i}) ⩽ 1/2, since if we choose a minimal such k, then 1/2 ⩽ ∏_{i=1}^{k}(1 − κ_{i}) ⩽ 3/4. The upper bound and the regularity assumption imply that ∥δ_{B_{k}}∥_{2}^{2} ⩽ (1 + 4η)∥δ_{B}∥_{2}^{2}, while we also know that ∥δ_{B_{k}}∥_{2}^{2} ⩾ 2^{8η}∥δ_{B}∥_{2}^{2}. It can be checked that 8 log 2 > 4, from which it follows (by looking at derivatives) that 2^{8η} > 1 + 4η for every η > 0.

This is a contradiction, so we can deduce that ∏_{i=1}^{k}(1 − κ_{i}) ⩽ 1/2. This means that the iteration stops with a set B_{r} of size at least |B_{0}|/2 for which the conclusion does hold, which proves the lemma. □

We need one more preliminary lemma, considerably easier than the previous one.

Lemma 5.3. Let 0 < α, 0 < η ⩽ 1/4, 0 < γ < η/4 and 0 < ϵ ⩽ α^{2}η/4. Let θ = 24η and κ_{0} = 2α^{−1}(ϵ/η)^{1/2}. Let G be a bipartite graph with vertex sets X and Y, and suppose that B ⊂ X is (ϵ, γ, η)-regular for G with parameter α. Let C be a subset of B of cardinality at least κ_{0}|B| and suppose that ∥δ_{C} − δ_{B}∥_{2}^{2} ⩽ θ∥δ_{B}∥_{2}^{2}. Then 𝔼_{x,x′∈C} |δ_{1}(x, x′) − ∥δ_{C}∥_{2}^{2}|^{2} ⩽ 5θ^{1/2}α^{2}.

Proof. Since |C| ⩾ κ_{0}|B|, there are at most κ_{0}^{−2}ϵ|C|^{2} pairs (x, x′) ∈ C^{2} such that δ_{1}(x, x′) ⩾ α(1 + η). Therefore, 𝔼_{x,x′∈C}δ_{1}(x, x′)^{2} ⩽ α^{2}(1 + η)^{2} + κ_{0}^{−2}ϵ ⩽ α^{2}(1 + 3η). We also know that 𝔼_{x,x′∈C}δ_{1}(x, x′) = ∥δ_{C}∥_{2}^{2} ⩾ (1−θ^{1/2})^{2}∥δ_{B}∥_{2}^{2}, by the triangle inequality and our assumption about C. We saw in Lemma 5.2 that ∥δ_{B}∥_{2}^{2} ⩾ α(1 − η), so

𝔼_{x,x′∈C} |δ_{1}(x, x′) − ∥δ_{C}∥_{2}^{2}|^{2} ⩽ α^{2}(1 + 3η − (1 − θ^{1/2})^{4}(1 − η)^{2}) .

It can be checked that this is at most the bound stated. □

We now have the tools in place to prove the main theorem of this section.

Theorem 5.4. Let N be a prime and let A ⊂ ℤ_{N} be a set of cardinality ⌊N/2⌋. Then there exists x such that ||A ∩ (A + x)| − N/4| ⩽ AN(log log N)^{−c}, where A and c > 0 are absolute constants.

Proof. Define a bipartite graph G with vertex sets X = Y = ℤ_{N} by joining x to y if and only if y − x ∈ A. That is, join x ∈ X to all points y of the form x + a. Notice first that if B is a subset of X and μ_{B} is the “characteristic measure” of B—that is, μ_{B}(x) = |B|^{−1} when x ∈ B and 0 otherwise—then δ_{B}(y), which is the proportion of x ∈ B such that y − x ∈ A, is |B|^{−1} ∑_{x∈ℤ_{N}} B(x)A(y − x), so δ_{B} = μ_{B} ∗ A.

Let 0 < η ⩽ 1/4, let 0 < γ ⩽ η/16 and let ϵ = η/1024. Now use Lemma 5.1 to choose B of density β ⩾ exp exp(10η^{−1} log η^{−1}) that is (ϵβ^{2}, γ, η)-regular with some parameter α ⩾ 1/4. Then use Lemma 5.2 to pass to a subset B′ of density β′ ⩾ β/2, which is (16ϵβ^{′2}, 4γ, η)-regular with parameter α (so far this is true for any subset B′ of density β′ ⩾ β/2) and which also has the property that ∥δ_{C} − δ_{B′}∥_{2}^{2} ⩽ 24η∥δ_{B′}∥_{2}^{2} for any subset C ⊂ B′ of size at least (4ϵ/η)^{1/2}β′|B′|.

We now apply this to a special choice of C. The average size of B′ ∩ (B′ − d) over all d ∈ ℤ_{N} is β^{′2}N = β′|B|. Therefore, we can find d ≠ 0 such that C = B′∩(B′−d) has size at least β′|B′|/2, and so, therefore, does C + d = B′ ∩ (B′ + d). But by the triangle inequality and the property we have established for B′, we know that ∥δ_{C} − δ_{C+d}∥_{2}^{2} ⩽ 96η∥δ_{B′}∥_{2}^{2}. Since A has a fixed density we may as well forget the slight extra strength we have and use the fact that ∥δ_{B′}∥_{2}^{2} ⩽ 1. Then, by our earlier remarks, ∥μ_{C} ∗ A − (μ_{C} ∗ A + d)∥_{2}^{2} ⩽ 96η. That is, loosely speaking, the function μ_{C} ∗ A is approximately unchanged (in L_{2}(X)) if you translate it by d.

We now use a discrete intermediate value theorem to find x such that |⟨μ_{C} ∗ A, μ_{C} ∗ A + x⟩ − 1/4| ⩽ 10η^{1/2}. Observe first that the expectation of ⟨μ_{C} ∗ A, μ_{C} ∗ A + x⟩ is ∥μ_{C} ∗A∥_{1}^{2} = s = 1/4+O(N^{−1}). There must exist x ≠ x′ such that ⟨μ_{C} ∗A, μ_{C} ∗A+x⟩ ⩽ s and ⟨μ_{C} ∗ A, μ_{C} ∗ A + x′⟩ ⩾ s. Now write x′ = x + md for some m. (This is where we use the fact that N is prime.) Then there must be some minimal k such that ⟨μ_{C} ∗ A, μ_{C} ∗ A + x + kd⟩ ⩾ s. So either k = 0 in which case we are clearly done, or k ⩾ 1 in which case ⟨μ_{C} ∗A, μ_{C} ∗A+x+(k−1)d⟩ < s. But ∥(μ_{C} ∗A+x+kd)−(μ_{C} ∗A+x+(k−1)d)∥_{2} ⩽ 10η^{1/2}, by the approximate translation-invariance of μ_{C} ∗ A, and ∥μ_{C} ∗ A∥ ⩽ 1, so in the second case we must have ⟨μ_{C} ∗ A, μ_{C} ∗ A + x + kd⟩ ⩽ s + 10η^{1/2}. Let us write z = x + kd.

To complete the proof we shall use the previous lemma and Lemma 4.4. The set B′ satisfies the assumptions of that lemma if we replace ϵ by 16ϵβ^{′2} and γ by 4γ. It therefore tells us that 𝔼_{x,x′∈C} |δ_{1}(x, x′) − ∥δ_{C}∥_{2}^{2}|^{2} ⩽ 5θ^{1/2}α^{2} whenever C has size at least 4(16ϵβ^{′2}/η)^{1/2}|B′| = β′|B′|/2.

This gives us the hypotheses of Lemma 4.4 with X = C, X′ = C + z, and c = 10θ^{1/2}. (Here we are using the fact that ∥f∥_{U_{2}} = ∥f′∥_{U_{2}} ⩾ ∥δ_{C}∥_{2} ⩾ 1/2 + O(N^{−1}.) It follows from that lemma that the variance of the quantity δ_{1}(x, x′) over (x, x′) ∈ C × (C + z) is at most 32θ^{1/32}. The mean is ⟨δ_{C}, δ_{C+z}⟩, which we have shown lies between s and s + 10η^{1/2}. Therefore, there exist x ∈ C and x′ ∈ C + z such that |δ_{1}(x, x′) − s| ⩽ 10η^{1/2} + 6θ^{1/64}.

Since we can choose η, and hence θ, to be as small as we like, this proves the result in a qualitative sense. To obtain the dependence on N, the main constraint is that B′ should have a non-zero difference that occurs at least β′|B′|/2 times. For this it is sufficient if the density β of B is at least N^{−1/3}, say. This forces η to be at least c log log log N/ log log N, and therefore forces 10η^{1/2} + 6θ^{1/64} to be at least c(log log log N/ log log N)^{1/64}. □

§6. Concluding remarks.

In one respect the weak regularity lemma that we obtained in Theorem 4.3 is a little artificial. To see why, let X_{1}, X_{2}, Y_{1} and Y_{2} be disjoint finite sets, all of the same size, and form a bipartite graph G by joining x ∈ X_{i} to y ∈ Y_{j} randomly with probability p_{ij}, where p_{ij} = 1/2 if i = j and 1/4 if i ≠ j.

It is not hard to check that if x and x′ belong to the same X_{i}, then with high probability δ_{1}(x, x′) is approximately 5/32, whereas if they belong to different X_{i} then with high probability δ_{1}(x, x′) is approximately 1/8. In fact, the quantifiers can be reversed: with high probability the graph is such that these are good approximations for all the pairs. It is clear, therefore, that the “natural” partition of X is into the sets X_{1} and X_{2}: this will have all the properties we could possibly want from any regularizing partition of X.

However, if we use the method of proof of Theorem 4.3, we will find ourselves applying Corollary 4.2, which itself uses Lemma 4.1, and when we examine how Lemma 4.1 identifies good subsets of X, we see that it produces sets that are, quite unnecessarily, much smaller than X_{1} and X_{2}. The basic idea behind Lemma 4.1 is to choose random points y_{1}, …, y_{k} in Y and to take the intersection of their neighbourhoods. If we do that in this example, then the proof works for the following rough reason: although the probability of choosing any given x is rather small, the probability that we choose x′ given that we choose x is far larger if x and x′ belong to the same X_{i} than if they belong to different X_{i}.

This correlation effect becomes stronger and stronger as k increases, but so does the probability of choosing any given x, and therefore so does the expected size of the set we eventually pick. In fact, for this graph even the maximum size of the common neighbourhood of k vertices in Y decreases exponentially in k.

We therefore end up choosing very small subsets of X_{1} and X_{2}, and the partition in Theorem 4.3 is (approximately, at any rate) a refinement of the partition {X_{1}, X_{2}} into a large number of much smaller sets, all of which behave in an almost identical way to the X_{i} of which they are (more or less) a subset.

Theorem 4.7, our “GG^{∗} regularity lemma,” addresses this problem to some extent, because it gives us a way of conglomerating the cells of the partition when it is appropriate to do so: if K is a set such that the vectors δ_{B_{i}} with i ∈ K are all close to each other, then all the inner products ⟨δ_{B_{i}}, δ_{B_{j}}⟩ with i, j ∈ K are close to each other. Moreover, they are all close to ∥δ_{B}∥_{2}^{2}, where B = ⋃_{i∈K} B_{i}. Therefore, this union has a regularity property as well.

However, as the above argument demonstrates, in some ways it is more natural to look for a metric on G than a partition, where we use the word “metric” slightly loosely in that we allow d(x, y) to equal 0 even if x ≠ y. (In other words, we should call it a pseudometric, but since what will really interest us is the triangle inequality we have not bothered to do so.) To get a further idea of why this might be, consider the “sphere graph” that has the n-sphere S_{n} as its vertex set, and joins x to y if ⟨x, y⟩ ⩾ 0. Then the size of the intersection of the neighbourhoods of x and y is a decreasing function of their distance, so this distance is quite clearly more natural than any partition of the vertex set, since the latter will necessarily create artificial boundaries.

Another nice way of putting a metric on X is to define d(x, x′) to be the distance in L_{2}(Y) between the unit vectors δ_{B_{i}}/∥δ_{B_{i}}∥_{2} and δ_{B_{j}}/∥δ_{B_{j}}∥_{2}, where x ∈ B_{i} and x′ ∈ B_{j}. This time, if x and x′ are close, all we can say is that δ_{B_{i}} and δ_{B_{j}} are roughly proportional. However, the constant of proportionality is equal to the ratio of the densities of the graphs G(B_{i}, Y) and G(B_{j}, Y), and from that one can show, by means of a proof very similar to that of Theorem 4.7, that if we take a small neighbourhood B in this metric, then the graph G(B, Y) will be approximately of rank 1 in the sense of Corollary 3.8 and Theorem 3.11. We omit the details.

References.

[A] N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), 83-96.

[AM] N. Alon, V. D. Milman, Isoperimetric inequalities for graphs and superconcentrators, J. Combin. Theory Ser. B 38 (1985), 73-88.

[BS] A. Balog, E. Szemerédi, A statistical theorem of set addition, Combinatorical 14 (1994), 263-268.

[CG] F. R. K. Chung, R. L. Graham, Quasi-random graphs with given degree sequences, Random Structures and Algorithms, to appear.

[CGW] F. R. K. Chung, R. L. Graham, R. M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), 345–362.

[G1] W. T. Gowers Lower bounds of tower type for Szemerédi’s uniformity lemma, Geom. Funct. Anal. 7 (1997), 322-337.

[G2] W. T. Gowers, A new proof of Szemerédi’s theorem, Geom. Funct. Anal. 11 (2001), 465-588.

[G3] W. T. Gowers, Quasirandomness, counting and regularity for 3-uniform hypergraphs, Combin. Probab. Comput. 15 (2006), 143-184.

[G4] W. T. Gowers, Quasirandom groups (2006), submitted.

[GK] B. J. Green, S. Konyagin, On the Littlewood problem modulo a prime, Canadian J. Math., to appear.

[S] T. Sanders, The Littlewood-Gowers problem, J. Anal. Math., to appear.

[T] A.G. Thomason, Pseudo-random graphs, Proceedings of Random Graphs, Poznán 1985 (M. Karonski, ed.), Annals of Discrete Mathematics 33, 307–331.