Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs

W. T. Gowers

Abstract. The main results of this paper are regularity and counting lemmas for 3uniform hypergraphs. A combination of these two results gives a new proof of a theorem of Frankl and Rödl, of which Szemerédi’s theorem for arithmetic progressions of length 4 is a notable consequence. Frankl and Rödl also prove regularity and counting lemmas, but the proofs here, and even the statements, are significantly different. Also included in this paper is a proof of Szemerédi’s regularity lemma, some basic facts about quasirandomness for graphs and hypergraphs, and detailed explanations of the motivation for the definitions used.

§1. Introduction.

One of the most important tools in extremal graph theory is Szemerédi’s regularity lemma. Given a graph G with vertex set V, the regularity lemma provides a partition of V into sets V_{1}, …, V_{K}, such that for almost every pair (i, j) the induced bipartite graph G(V_{i}, V_{j}) (that is, the restriction of G to the set of edges xy such that x ∈ V_{i} and y ∈ V_{j}) behaves like a typical random graph of the same density. This result has been such an important tool in graph theory and has so many applications that it is very natural to try to find a generalization that will help with extremal problems for hypergraphs. Indeed, there is an application that, even on its own, provides sufficient motivation for a project of this kind. In 1976, Ruzsa and Szemerédi discovered a simple way to deduce Roth’s theorem (Szemerédi’s theorem for progressions of length 3) from the regularity lemma [RS], and for many years, Vojta Rödl, with several collaborators, has had a very promising programme for obtaining a new proof of the full Szemerédi theorem by generalizing the Ruzsa-Szemerédi argument. In order to do this, one needs not just a regularity lemma but also a so-called “counting lemma”, which says, very roughly, that a sufficiently quasirandom hypergraph will contain small subhypergraphs with approximately the correct frequency. (This way of putting it, though it will do for now, is in fact so rough as to be positively misleading - see §5 for an explanation of why.) In 2002, Frankl and Rödl carried out this programme for 3-uniform hypergraphs, thereby giving a new proof of Szemerédi’s theorem in the case of progressions of length four [FR2]. Ten years earlier, they had proved a regularity lemma for k-uniform hypergraphs [FR1], but obtaining an appropriate counting lemma to go with it was much harder.

The main purpose of this paper is expository: we shall explain the ideas that lie behind a paper of the author [G3], the main advance of which is to establish a counting lemma for k-uniform hypergraphs, but also a regularity lemma that is not quite the same as that of Frankl and Rödl. These two results imply not just Szemerédi’s theorem in full generality, but also, as has already been observed by Solymosi [S2], its multidimensional version. This result had previously been obtained only by Furstenberg’s ergodic theory approach [FK]. To explain how these results are proved, we shall concentrate on the case of 3-uniform hypergraphs, since the generalization to k-uniform hypergraphs, though notationally more complicated, is not different in an essential way. The main results of this paper are therefore not new, but the point is that the definitions and proofs are different from those of Frankl and Rödl and more readily generalized. Thus, the principal novelty of this paper occurs at the technical level. However, since this is an area where it is easy to become overwhelmed by technical difficulties, technical simplifications are of more than merely technical interest. That said, Nagle, Rödl and Schacht have also recently generalized the Frankl-Rödl approach to k-uniform hypergraphs [NRS], in work independent of the work discussed here. In the final section of this paper, we explain what the main difference is between the Frankl-Rödl approach and the one given here.

The methods of this paper have their roots in part of the analytic proof of Szemerédi’s theorem given by the author in [G1,2]. Another purpose of the paper is to explain this connection. We shall occasionally assume a nodding acquaintance with the ideas of [G1] (which are not used here in any formal way, but which shed light on some of our arguments): otherwise this paper is self-contained.

The reader is urged not to be put off by the length of the paper. The main results - counting and regularity lemmas for 3-uniform hypergraphs - are dealt with in §6 and §8 respectively. The rest of the paper consists of discussion, motivating examples and well-known background results in graph theory. Even the sections with the main results contain quite a bit of discussion, rather than being written as densely as possible. If you are looking for a short proof of Szemerédi’s theorem for progressions of length four, then the “true” length of this paper is shorter than that of other papers that establish the same result. Almost all the proofs are straightforward applications of the second-moment method, otherwise known as the Cauchy-Schwarz inequality.

To begin with, here is a brief sketch of a variant of the argument of Ruzsa and Szemerédi that was the starting point for Rödl’s programme. Their first step was to prove the following simple-looking statement about graphs.

Theorem 1.1. For every constant c > 0 there exists a constant a > 0 with the following property. If G is any graph with n vertices that contains at most an^{3} triangles, then it is possible to remove at most cn^{2} edges from G to make it triangle-free.

Sketch Proof. For anybody with experience of the regularity lemma, this is an easy and standard argument (but it was of course a serious achievement of Ruzsa and Szemerédi to notice that this kind of result was both easy and significant). First, apply the regularity lemma to obtain a c/4-regular partition of G into vertex sets V_{1}, …, V_{K} of almost equal size. Remove all edges that belong to pairs (V_{i}, V_{j}) that fail to be c/4-regular or that have density at most c/2. The result is a subgraph G′ of G such that every edge belongs to a pair (V_{i}, V_{j}) that is c/4 regular and has density at least c/2, and the number of edges we have removed from G to achieve this is less than cn^{2}.

It remains to show that G′ is triangle-free. But if xyz is a triangle in G′ then we must have x ∈ V_{i}, y ∈ V_{j} and z ∈ V_{k} with the pairs (V_{i}, V_{j}), (V_{j}, V_{k}) and (V_{i}, V_{k}) all c/4 regular and of density at least c/2. It is not hard to deduce from this that the number of triangles in G is at least c^{3}N^{3}/256K^{3}. Since K depends on c only, the result is proved. □

Remark. In the above argument we are allowing i, j and k to coincide, so strictly speaking the triangles we obtain should have labellings on their vertices. But this affects the bound by a factor of at most 6. It is more common to insist that K is large, so that there are very few edges joining vertices in the same V_{i} and one can afford to remove them.

The bound one gets for the dependence of a on c in Theorem 1.1 is extremely weak, and it is a fascinating problem to find a proof that does not use the regularity lemma and therefore, one hopes, gives a better bound. The reason this would be more than a minor curiosity is that Theorem 1.1 implies Roth’s theorem - that is, Szemerédi’s theorem in the case of progressions of length three. There are several ways to demonstrate this - the way we give here is a small modification of an argument of Solymosi [S1], which is a precursor to the argument mentioned earlier. He was the first to observe that one could obtain the following two-dimensional statement as well.

Corollary 1.2. For every δ > 0 there exists N such that every subset A ⊂ [N]^{2} of size at least δN^{2} contains a triple of the form (x, y), (x + d, y), (x, y + d) with d > 0.

Proof. First, note that an easy argument allows us to replace A by a set B that is symmetric about some point. Briefly, if the point (x, y) is chosen at random then the intersection of A with (x, y)−A has expected size cδ^{2}N^{2} for some absolute constant c > 0, lives inside the grid [−N, N]^{2}, and has the property that B = (x, y) − B. So B is still reasonably dense, and if it contains a subset K then it also contains a translate of −K. So we shall not worry about the condition d > 0. (I am grateful to Ben Green for bringing this trick to my attention.)

Without loss of generality, the original set A is symmetric in this sense. Let X be the set of all vertical lines through [N]^{2}, that is, subsets of the form {(x, y) : x = u} for some u ∈ [N]. Similarly, let Y be the set of all horizontal lines. Define a third set, Z, of diagonal lines, that is, lines of constant x + y. These sets form the vertex sets of a tripartite graph, where a line in one set is joined to a line in another if and only if their intersection belongs to A. For example, the line x = u is joined to the line y = v if and only if (u, v) ∈ A and the line x = u is joined to the line x + y = w if and only if (u, w − u) ∈ A.

Suppose that the resulting graph G contains a triangle of lines x = u, y = v, x+y = w. Then the points (u, v), (u, w − u) and (w − v, v) all lie in A. Setting d = w − u − v, we can rewrite them as (u, v), (u, v + d), (u + d, v), which shows that we are done unless d = 0. When d = 0, we have u + v = w, which corresponds to the degenerate case when the vertices of the triangle in G are three lines that intersect in a single point. Clearly, this can happen in at most |A| = o(N^{3}) ways.

Therefore, if A contains no configuration of the desired kind, then the hypothesis of Theorem 1.1 holds, and we can remove o(N^{2}) edges from G to make it triangle-free. But this is a contradiction, because there are at least δN^{2} degenerate triangles and they are edge-disjoint. □

It is straightforward to deduce Roth’s theorem from the above result. Note that for this deduction we do not mind if the d obtained in Corollary 1.2 is negative.

Corollary 1.3. For every δ > 0 there exists N such that every subset A of {1, 2, …, N} of size at least δN contains an arithmetic progression of length 3.

Proof. Define B ⊂ [N]^{2} to be the set of all (x, y) such that x−y ∈ A. It is straightforward to show that B has density at least η > 0 for some η that depends on δ only. Applying Corollary 1.2 to B we obtain inside it three points (x, y), (x+d, y) and (x, y +d). Then the three numbers x−y −d, x−y, x+d−y belong to A and form an arithmetic progression. □

Rödl’s programme, outlined in [R], was to generalize Theorem 1.1 to hypergraphs, using generalized regularity and counting lemmas to prove it. The various ways of deducing Roth’s theorem from Theorem 1.1 can then be straightforwardly modified to give deductions of the full Szemerédi theorem.

To be more precise about this, let H be a 3-uniform hypergraph. By a simplex in H we mean a collection of four edges of the form {xyz, xyw, xzw, yzw}, that is, a complete subhypergraph on four vertices. If one thinks of the edges of H as (two-dimensional) triangles, then the “edges” of a simplex can be thought of as the faces of a tetrahedron. However one looks at it, this is the natural generalization of the notion of a triangle in a graph. The result of Frankl and Rödl mentioned earlier is the following.

Theorem 1.4. For every constant c > 0 there exists a constant a > 0 with the following property. If H is any 3-uniform hypergraph with n vertices that contains at most an^{4} simplices, then it is possible to remove at most cn^{3} edges from H to make it simplex-free.

As Solymosi demonstrated, it is easy to adapt the proof of Theorem 1.2 and show that Theorem 1.4 has the following consequence.

Theorem 1.5. For every δ > 0 there exists N such that every subset A ⊂ [N]^{3} of size at least δN^{3} contains a quadruple of points of the form

{(x, y, z), (x + d, y, z), (x, y + d, z), (x, y, z + d)}

with d > 0.

Similarly, Szemerédi’s theorem for progressions of length four is an easy consequence of Theorem 1.5.

Thus, once one has appropriate generalizations of the regularity and counting lemmas to hypergraphs, the rest of the argument goes through quite easily. However, as will become clear over the next three sections, even to come up with the right statements is harder than one might at first think. To begin with, however, we shall provide some essential background by discussing several notions of quasirandomness and the relationships between them.

§2. Quasirandom graphs, hypergraphs and subsets of ℤ_{N}: some definitions.

Every known proof of Szemerédi’s theorem involves somewhere a notion of quasirandomness and a two-case argument of the following kind: if a certain structure is quasirandom then it contains several configurations of the kind one is looking for (just as one expects from a random structure), and if it is not then one can exploit the non-quasirandomness and pass to the next stage of an iteration. In this section we review certain notions of quasirandomness and point out connections between them (some of which are well known).

The first is the definition of a quasirandom graph, which was introduced by Chung, Graham and Wilson [CGW]. (A similar notion was discovered independently by Thomason [T].) There are in fact several different definitions, and the main purpose of their paper was to show that they are all equivalent. Here we restrict attention to bipartite graphs and focus on just two of the definitions. (Chung and Graham state their results in the case p = 1/2 only but the generalization to arbitrary p is not hard.) A proof of a slightly modified result will be given in the next section.

Theorem 2.1. Let G be a bipartite graph with vertex sets X and Y. Let |X| = M and |Y | = N and suppose that G has pMN edges. Then the following properties of G are equivalent.

(i) The number of labelled 4-cycles in G that start in X (that is, quadruples (x_{1}, x_{2}, y_{1}, y_{2}) ∈ X^{2} × Y^{2} such that x_{1}y_{1}, x_{1}y_{2}, x_{2}y_{1} and x_{2}y_{2} are all edges of G) is at most p^{4}M^{2}N^{2} + c_{1}M^{2}N^{2}.

(ii) If X′ and Y′ are any two subsets of X and Y respectively, then the number of edges from X′ to Y′ differs from p|X||Y | by at most c_{2}MN.

A graph that satisfies property (i) is often called α-quasirandom. For the time being, we shall adopt this definition, though in the next section we shall choose a different, equivalent definition that is more convenient.

Chung and Graham [CG2] went on to define a notion of quasirandomness for subsets of ℤ_{N}. Again, they gave the definition in the form of a theorem that asserted the equivalence of various randomness properties, and once again we shall focus on just two of these and consider the case of an arbitary “probability” p rather than just p = 1/2. By a mod-N progression we mean a set of the form (a, a + d, …, a + (m − 1)d), where addition is in the group ℤ_{N}.

Theorem 2.2. Let A be a subset of ℤ_{N} of size pN. Then the following properties of A are equivalent.

(i) The number of quadruples (a, b, c, d) ∈ A^{4} such that a + b = c + d is at most p^{4}N^{4} + o(N^{4}).

(ii) If X is any mod-N progression then |A ∩ X| = p|X| + o(N).

Chung and Graham also pointed out that there is a close connection between quasirandom subsets of ℤ_{N} and quasirandom graphs. To see this, let A be a subset of ℤ_{N} and define a bipartite graph G with vertex sets X = Y = ℤ_{N} by letting (x, y) ∈ X × Y be an edge if and only if x + y ∈ A. Then, given a 4-cycles (x_{1}, x_{2}, y_{1}, y_{2}) of the kind counted in property (ii) of Theorem 2.1, we know that x_{1} + y_{1}, x_{1} + y_{2}, x_{2} + y_{1} and x_{2} + y_{2} all belong to A, and moreover that

(x_{1} + y_{1}) + (x_{2} + y_{2}) = (x_{1} + y_{2}) + (x_{2} + y_{1}) ,

from which it is easy to see that there is an N-to-one correspondence between the 4cycles from Theorem 2.1 (i) and the quadruples from Theorem 2.2 (i). Thus, the set A is quasirandom if and only if the corresponding graph G is quasirandom.

Why are quasirandom sets useful for Szemerédi’s theorem? Briefly, the reason is that a quasirandom set A of density p must contain approximately the same number of arithmetic progressions of length 3 as a typical random set of that density, while if it fails to be quasirandom, then property (ii) of Theorem 2.2 tells us that there are well-structured subsets of ℤ_{N} inside which A has density substantially different from p (and hence, by an averaging argument, sometimes substantially larger). This makes possible an iteration argument of the kind mentioned at the beginning of this section.

In all known proofs of Szemerédi’s theorem, the difficulty increases sharply when the length of the progression increases from 3 to 4. In the analytic approach of [G1,2], the reason for this difficulty is that the quasirandomness of Theorem 2.2 is not a sensitive enough property to detect that a set has too many or too few arithmetic progressions of length 4 (compared with a random set of the same density). The idea of [G1] is to define a stronger property, known there as quadratic uniformity, which is sensitive to progressions of length 4. However, because it is a stronger property, it is much harder to say anything about sets that fail to be quadratically uniform - a point to which we shall return.

The main purpose of this section, however, is to show how the notion of quadratic uniformity leads naturally to a definition, also due to Chung and Graham [CG1] (but arrived at in a different way), of quasirandomness for 3-uniform hypergraphs. First, then, here is the definition of a quadratically uniform subset of ℤ_{N}.

Definition 2.3. Let α > 0. A subset A ⊂ ℤ_{N} of size pN is α-quadratically uniform if A^{8} contains at most (p^{4} + α)N^{4} octuples of the form

(x, x + a, x + b, x + c, x + a + b, x + a + c, x + b + c, x + a + b + c) .

Since quadruples (a, b, c, d) with a + b = c + d are in one-to-one correspondence with quadruples of the form (x, x + a, x + b, x + a + b), this definition is a natural generalization of property (i) of Theorem 2.2.

In order to define quasirandomness for 3-uniform hypergraphs, we shall “complete the square”, by finding a property that stands in relation to quadratic uniformity as quasirandomness for graphs does to quasirandomness for subsets of ℤ_{N}. To establish that connection we started with a set A and defined the bipartite graph G to consist of all pairs (x, y) such that x + y ∈ A. Now we would like to find an associated 3-uniform hypergraph, and it seems sensible to try the tripartite hypergraph H with vertex sets X = Y = Z = ℤ_{N}, with the triple (x, y, z) forming an edge of H if and only if x + y + z ∈ A.

In order to generalize Definition 2.3, we now want to find a structure in H that corresponds to octuples of the given kind. It is natural to think of these octuples as labelling vertices of a cube (as they would if a, b and c denoted three orthogonal vectors of the same length). It is also natural to think of the edges of a 3-uniform hypergraph as triangles. Is there a configuration of triangles naturally associated with a cube?

Indeed there is: the dual of a cube is an octahedron and an octahedron is made of triangles. This suggests that we should regard a quadruple (x, x + a, x + b, x + a + b) in ℤ_{N} as a kind of square, and a 4-cycle (x_{1}, x_{2}, y_{1}, y_{2}) in a bipartite graph as its dual, which happens, confusingly, to look like a square as well. (This dual square gives rise to the square (x_{1} + y_{1}, x_{1} + y_{2}, x_{2} + y_{1}, x_{2} + y_{2}) in ℤ_{N}.) The points x_{i} and y_{i} of the 4-cycle are vertices, so the vertices of the square in ℤ_{N} correspond to (1-dimensional) faces, and the value attached to a face is the sum of the values at the vertices. This gives us a construction that generalizes easily to all dimensions.

The above remarks provide the justification for the following construction. Given a subset A ⊂ ℤ_{N}, define a tripartite 3-uniform hypergraph H with vertex sets X = Y = Z = ℤ_{N} to be the set of all triples (x, y, z) such that x + y + z ∈ A. Define an octahedron in this (or any other) hypergraph to be a set of eight 3-edges of the form {(x_{i}, y_{j}, z_{k}) : i, j, k ∈ {1, 2}}, where x_{1}, x_{2} ∈ X, y_{1}, y_{2} ∈ Y, z_{1}, z_{2} ∈ Z. Equivalently, an octahedron is a complete tripartite subhypergraph with two vertices from each vertex set of H.

It is now reasonable to guess that a good definition of quasirandomness for 3-uniform hypergraphs is the following.

Definition 2.4. Let H be a tripartite 3-uniform hypergraph with vertex sets X, Y and Z of size L, M and N respectively and suppose that H has pLMN edges. Then H is α-quasirandom if it contains at most (p^{8} + α)L^{2}M^{2}N^{2} octahedra.

This suggestion can be motivated further (to do so one attempts to generalize arguments about graphs and sees what one needs) but for now it is perhaps enough simply to say that the guess turns out to be correct, and to point out that the number of octahedra must be at least p^{8}L^{2}M^{2}N^{2}. (This last observation follows easily from the Cauchy-Schwarz inequality, as will become clear later in this paper.)

A first sign that the definition is a good one is that the eight numbers x_{i} + y_{j} + z_{k} do form a cube, in the sense discussed earlier. It follows that a subset A of ℤ_{N} gives rise to an α-quasirandom 3-graph H if and only if A is α-quadratically uniform.

As it happens, there is a different definition (Definition 4.3 below) that is even better. However, it is equivalent apart from the precise value of α, and the advantage is a technical one, so for the purposes of the discussion in this section we shall stick with the more obvious Definition 2.4.

Theorem 2.1 stated that two quasirandomness properties of graphs are equivalent. We have just generalized the second of these properties. What about the first? It is here that hypergraph quasirandomness springs a surprise. The property that most obviously generalizes property (ii) of Theorem 2.1 is the following, which we shall call vertex-uniformity.

Definition 2.5. Let H be a 3-uniform hypergraph with vertex sets X, Y and Z of sizes L, M and N respectively and suppose that H has pLMN edges. Then H is β-vertex-uniform if, for any choice of subsets X′ ⊂ X, Y′ ⊂ Y and Z′ ⊂ Z, the number of triples (x, y, z) ∈ X′ × Y′ × Z′ that belong to H differs from p|X′||Y′||Z′| by at most βLMN.

In the next section we shall see that an α-quasirandom 3-graph is β-vertex-uniform for some β depending on α only, but the reverse is not true. In §4 we shall give two examples that demonstrate the failure of this implication. We end this section with one last definition, of a property that generalizes property (ii) of Theorem 2.1 in a less naive way. This property will turn out to be equivalent to quasirandomness - another result to be proved in the next section.

Definition 2.6. Let H be a 3-uniform hypergraph with vertex sets X, Y and Z of sizes L, M and N respectively and suppose that H has pLMN edges. Then H is γ-edge-uniform if for every t ∈ [0, 1] and every tripartite graph G with vertex sets X, Y and Z and tLMN triangles, the number of triangles in G that belong to H differs from ptLMN by at most γLMN.

Here, of course, a triangle in G is said to belong to H if its vertices form a triple that belongs to H.

Why is this a generalization of property (ii)? Well, that property says of a bipartite graph that it doesn’t significantly correlate with graphs that are induced by sets of vertices (that is, complete bipartite graphs on subsets of the vertex sets). Edge-uniformity says of a 3-uniform hypergraph that it doesn’t correlate with 3-uniform hypergraphs that are induced by sets of edges (as opposed to hyperedges).

Although in this paper we are concentrating on 3-uniform hypergraphs, it should be clear how the definitions of this section are generalized. A k-partite k-uniform hypergraph H of density p with vertex sets X_{i} of size N_{i} is quasirandom if it contains at most (p^{2^{k}} + c)(N_{1} … N_{k})^{2} k-dimensional octahedra and c is small; this turns out to be equivalent to the assertion that H is ((k − 1)-edge)-uniform, in the sense that H does not significantly correlate with any k-uniform hypergraph induced from a (k−1)-uniform hypergraph. Using this kind of language, one could say that a quasirandom graph is a 2-uniform hypergraph that is (1-edge)-uniform. The right generalization of the pair (2, 1) is not (k, 1) as one might at first suppose, but (k, k − 1). Thus, Definition 2.6 is more useful to us than Definition 2.5.

§3. Quasirandom functions and a counting lemma.

Let G be a tripartite graph with vertex sets X, Y and Z, of sizes L, M and N respectively, and write G(X, Y), G(Y, Z) and G(X, Z) for the three bipartite parts of G. Suppose that these parts are quasirandom with probabilities p, q and r respectively. How many triangles does G contain?

If we use genuinely random graphs as our guide, we should expect the answer to be about pqrLMN, and indeed it is easy to use property (ii) of Theorem 2.1 to prove that this is approximately right: a typical vertex in X has about pM neighbours in Y and rN neighbours in Z; these two neighbourhoods are linked by about q(pM)(rN) edges; summing over all x ∈ X we obtain the desired estimate.

The argument just sketched can be generalized quite easily from triangles to copies of any small graph, and this generalization is what we shall refer to as the counting lemma for graphs. The first aim of this section will be to give it a different and less transparent proof. Why should we wish to do something so apparently perverse? Because the alternative proof has a number of advantages: first, it is closely modelled on the analytic arguments of [G1] and related arguments from Furstenberg’s ergodic-theory proof of Szemerédi’s theorem (see for example [FKO]); more importantly, this analytic approach is much easier to generalize, an advantage that is very noticeable even for “the first non-trivial case”, that of 3-uniform hypergraphs. Thus, the reader who is prepared to make the small effort needed to understand the proof of Theorem 3.5 below will understand the basic structure of the longer arguments of §4 and §6, and also that of [G3]: the main lemmas and arguments there all have their prototypes here.

An important technicality in the analytic approach to these arguments is to think of sets as {0, 1}-valued functions and to generalize set-theoretic arguments to functions taking values in more general sets such as [0, 1], [−1, 1], ℝ_{+}, ℝ, {z ∈ ℂ : |z| ⩽ 1} or ℂ. We shall do that now, proving results about [−1, 1]-valued functions and only occasionally pausing to deduce results about graphs and hypergraphs. Our first result is a version of Theorem 2.1 for functions. It is not quite a direct generalization of Theorem 2.1 because the conclusion is generalized to functions as well as the hypothesis. However, as we shall see, if G is regular then it is easy to deduce Theorem 2.1 from it. We shall not bother with the irregular case, because we shall base our later arguments on Theorem 3.1 and not use Theorem 2.1.

Theorem 3.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.

Proof. We shall begin with a very simple argument that shows that (ii) implies (i). Let us assume that (i) is false, or in other words that

∑_{x,x′∈X} ∑_{y,y′∈Y} f(x, y)f(x′, y)f(x, y′)f(x′, y′) > c_{1}M^{2}N^{2} .

Now choose x′ ∈ X and y′ ∈ Y randomly and independently and fix them. Then the average of the sum ∑_{x,y} f(x, y)f(x′, y)f(x, y′)f(x′, y′) is greater than c_{1}MN, so the sum itself is greater than c_{1}MN for at least one choice of x′ and y′. But then (ii) is false if we set c_{2} = c_{1}, u(x) = f(x, y′) and v(y) = f(x′, y)f(x′, y′). (What is important here is that fixing x′ and y′ turns all the terms except for f(x, y) into constants or functions of one variable.)

The reverse implication uses the Cauchy-Schwarz inequality several times. It is this technique that, when suitably generalized, lies at the heart of the proof of the counting lemma for hypergraphs. (To be more precise, what we keep using is not the Cauchy-Schwarz inequality directly, but the inequality (∑_{i=1}^{N} a_{i})^{2} ⩽ N ∑_{i=1}^{N} a_{i}^{2}, which follows from it.) In the expressions that follow, sums involving x and x′ are over X and sums involving y and y′ are over Y.

|∑_{x,y} f(x, y)u(x)v(y)|^{4} = ((∑_{x} ∑_{y} f(x, y)u(x)v(y))^{2})^{2}

⩽ (M ∑_{x}(∑_{y} f(x, y)u(x)v(y))^{2})^{2}

⩽ (M ∑_{x}(∑_{y} f(x, y)v(y))^{2})^{2}

= M^{2}(∑_{x} ∑_{y,y′} f(x, y)f(x, y′)v(y)v(y′))^{2}

⩽ M^{2}N^{2} ∑_{y,y′}(∑_{x} f(x, y)f(x, y′)v(y)v(y′))^{2}

⩽ M^{2}N^{2} ∑_{y,y′}(∑_{x} f(x, y)f(x, y′))^{2}

= M^{2}N^{2} ∑_{x,x′} ∑_{y,y′} f(x, y)f(x, y′)f(x′, y)f(x′, y′)

These calculations show that if (i) is true then (ii) is true for c_{2} = c_{1}^{1/4}.

It is obvious that (ii) implies (iii), since one can take u and v to be the characteristic functions of X′ and Y′ respectively, so it remains to prove that (iii) implies (ii).

Suppose, then, that (ii) is false and we have functions u : X → [−1, 1] and v : Y → [−1, 1] such that |∑_{x,y} f(x, y)u(x)v(y)| ⩾ c_{2}MN. We can write u = u_{+} − u_{−} with u_{+} and u_{−} disjointly supported and taking values in [0, 1], and similarly we can write v = v_{+} −v_{−}. It follows that there are [0, 1]-valued functions s and t such that |∑_{x,y} f(x, y)s(x)t(y)| ⩾ c_{1}MN/4. Now let X_{1} and Y_{1} be random subsets of X and Y respectively, with their elements chosen independently with probabilities given by the functions s and t. Then the expectation of ∑_{x∈X_{1}} ∑_{y∈Y_{1}} f(x, y) is ∑_{x,y} f(x, y)s(x)t(y), so there must exist a choice of X_{1} and Y_{1} such that |∑_{x∈X_{1}} ∑_{y∈Y_{1}} f(x, y)| is at least c_{1}MN/4. If this sum is positive, then we are done. Otherwise, let X_{2} = X \ X_{1} and Y_{2} = Y \ Y_{1}, and for i, j ∈ {1, 2} let S_{ij} = ∑_{x∈X_{i}} ∑_{y∈Y_{j}} f(x, y). Then S_{11}+S_{12}+S_{21}+S_{22} = 0 from which it follows that either there exists a pair (i, j) ≠ (1, 1) such that S_{ij} ⩾ c_{1}MN/12. Whatever happens, we have found a pair of sets X′ ⊂ X and Y′ ⊂ Y such that |∑_{x∈X′} ∑_{y∈Y′} f(x, y)| > c_{2}MN/12, contradicting (iii) when c_{3} ⩽ c_{2}/12. □

Theorem 3.1 motivates the following definition.

Definition 3.2. Let X and Y be sets of size M and N. A function f is α-quasirandom if ∑_{x,x′∈X} ∑_{y,y′∈Y} f(x, y)f(x′, y)f(x, y′)f(x′, y′) ⩽ αM^{2}N^{2}.

If G is a bipartite graph with vertex sets X and Y, let us write G(x, y) for the function that is 1 if xy is an edge of G and 0 otherwise. Suppose that |X| = M, |Y | = N and every vertex in X has degree pN, and set f(x, y) = G(x, y) − p. Then it is easy to verify that

\begin{matrix}∑_{x,x′,y,y′} G(x, y)G(x, y′) & G(x′, y)G(x′, y′) \\ = ∑_{x,x′,y,y′} f(x, y)f(x, y′)f(x′, y)f(x′, y′) + p^{4}M^{2}N^{2} . \end{matrix}

It follows that G is α-quasirandom, in the sense of §2, if and only if f is α-quasirandom. From now on we shall adopt this as our definition of quasirandomness even in the nonregular case.

Definition 3.3. Let G be a bipartite graph with vertex sets X and Y of size M and N and suppose that G has pMN edges. Then G is α-quasirandom if the function f(x, y) = G(x, y) − p is α-quasirandom.

Notice also that, with this definition of f,

∑_{x∈X′} ∑_{y∈Y′} G(x, y) = ∑_{x∈X′} ∑_{y∈Y′} f(x, y) + p|X′||Y′| ,

so property (iii) of Theorem 3.1 and property (ii) of Theorem 2.1 are trivially equivalent. We have therefore proved Theorem 2.1 in the case of regular graphs.

Now let us state and prove a counting lemma for graphs. We begin with the special case of triangles in order to demonstrate the argument without getting tied up with notation. It is also the case of most immediate interest.

Lemma 3.4. Let G be a tripartite graph with vertex sets X, Y and Z, of sizes L, M and N respectively. Suppose that the bipartite graphs G(X, Y), G(Y, Z) and G(X, Z) are α-quasirandom with densities p, q and r respectively. Then the number of triangles in G differs from pqrLMN by at most 4α^{1/4}LMN.

Proof. Let the variables x, y and z always stand for elements of X, Y and Z respectively, so that we do not keep needing to specify this. Define a function f : X × Y → [−1, 1] by f(x, y) = G(x, y) − p, and similarly let g(y, z) = G(y, z) − q and h(x, z) = G(x, z) − r. In terms of this notation, the number of triangles in G is given by the sum

∑_{x,y,z}(p + f(x, y))(q + g(y, z))(r + h(x, z)) .

This sum splits naturally into eight parts, and the idea of the proof is that if α is small then only the main term pqrLMN makes a significant contribution to it. To see this, let us consider any one of the four terms that involves f(x, y) rather than p. It will have the form ∑_{x,y,z} f(x, y)u(y, z)v(x, z), where u is either q or g and v is either r or h.

If we now fix z, we obtain an expression of the form ∑_{x,y} f(x, y)u(y)v(z). The deduction of property (ii) from property (i) in Theorem 3.1 tells us that this is at most α^{1/4}LM, which gives us that ∑_{x,y,z} f(x, y)u(y, z)v(x, z) is at most α^{1/4}LMN. There are seven terms other than the main one, of this kind, three of which are easily seen to be zero, so the result follows. □

The general counting lemma is proved in essentially the same way. We shall state it in an equivalent form, as a “probability lemma”. Notice that the probability in the conclusion of the lemma is what one would expect in the case of random graphs. The conclusion of the lemma therefore says that there are about as many copies of H in G as one would expect.

Theorem 3.5. Let G be an m-partite graph with vertex sets X_{1}, …, X_{m} and write N_{i} for the size of X_{i}. Suppose that for each pair (i, j) the induced bipartite graph G(X_{i}, X_{j}) is α-quasirandom with density p_{ij}. Let H be any graph with vertex set {1, 2, …, m} and let (x_{1}, …, x_{m}) be a random element of X_{1} ×…×X_{m}. Then the probability that the function i ↦ x_{i} is an isomorphic embedding of H into G differs from ∏_{ij∈E(H)} p_{ij} ∏_{ij∉E(H)}(1−p_{ij}) by at most 2^{\binom{m}{2}}α^{1/4}. The probability that x_{i}x_{j} is an edge of G whenever ij is an edge of H (but not necessarily conversely) differs from ∏_{ij∈E(H)} p_{ij} by at most 2^{|E(H)|}α^{1/4}.

Proof. This time, let x_{i} always stand for an element of X_{i}. Let f_{ij}(x, y) = G(x, y) − p_{ij} for each pair (i, j). Then the probability in question is

(N_{1} … N_{m})^{−1} ∑_{x_{1},...,x_{m}} ∏_{ij∈E(H)}(p_{ij} + f_{ij}(x_{i}, x_{j})) ∏_{ij∉E(H)}(1 − p_{ij} − f_{ij}(x_{i}, x_{j})) .

Once again, we have a sum that splits up into several terms. The main term is ∏_{ij∈E(H)} p_{ij} ∏_{ij∉E(H)}(1 − p_{ij}) and it remains to show that all other terms are small. But any other term must choose f_{ij}(x_{i}, x_{j}) from at least one bracket, and since only one bracket involves both x_{i} and x_{j}, if we fix all the other x_{k} we obtain an expression of the form ∑_{x_{i},x_{j}} f_{ij}(x_{i}, x_{j})u(x_{i})v(x_{j}), with u and v taking values in the interval [−1, 1]. It follows from the α-quasirandomness of f_{ij} and Theorem 3.1 that this is at most α^{1/4}N_{i}N_{j}. Summing over the other m − 2 variables and multiplying by (N_{1} … N_{m})^{−1} we find that each term apart from the main one has size at most α^{1/4}. Since there are 2^{\binom{m}{2}} terms, the result follows (and could be improved slightly since some of the terms are zero).

The proof of the second assertion is similar, but slightly simpler. □

§4. A counting lemma for quasirandom 3-graphs.

The virtue of the arguments in §3 is that they generalize easily. Our first demonstration of this takes the form of very similar proofs of corresponding results for quasirandom 3-uniform hypergraphs. As in §3, we begin with a result about functions that serves as a definition of quasirandomness. The statement is very similar to that of Theorem 3.1, and the proofs of the implications are also very similar to the corresponding proofs in Theorem 3.1. Properties (i) and (iii) below are functional versions of Definitions 2.4 and 2.6 respectively.

During part of the proof, we shall make use of a non-standard but very convenient “product convention”. If g is any function of k variables x_{1}, …, x_{k}, then g_{x,x′}(x_{2}, …, x_{k}) will be shorthand for g_{x}(x_{2}, …, x_{k})g_{x′}(x_{2}, …, x_{k}). What’s more, we shall iterate this, writing g_{x,x′,y,y′} for (g_{x,x′})_{y,y′} and so on. For instance, if g is a function of three variables, then

g_{x,x′,y,y′}(z) = g(x, y, z)g(x′, y, z)g(x, y′, z)g(x′, y′, z) .

If we iterate k times, then the resulting function is a function of no variables, that is, a constant. To be precise, g_{x_{1},x′_{1},...,x_{k},x′_{k}} is the number ∏_{ϵ∈{0,1}} g(u_{1}(ϵ), …, u_{k}(ϵ)), where u_{i}(ϵ) = x_{i} if ϵ_{i} = 0 and u_{i}(ϵ) = x′_{i} if ϵ_{i} = 1.

Theorem 4.1. Let X, Y and Z be sets of sizes L, M and N and let f : X×Y ×Z → [−1, 1]. Then the following statements are equivalent.

(i) ∑_{x_{0},x_{1}∈X} ∑_{y_{0},y_{1}∈Y} ∑_{z_{0},z_{1}∈Z} ∏_{(i,j,k)∈{0,1}^{3}} f(x_{i}, y_{j}, z_{k}) ⩽ c_{1}L^{2}M^{2}N^{2}.

(ii) For any three functions u : X × Y → [−1, 1], v : Y × Z → [−1, 1] and w : X × Z → [−1, 1] we have the inequality |∑_{x,y,z} f(x, y, z)u(x, y)v(y, z)w(x, z)| ⩽ c_{2}LMN.

(iii) For any tripartite graph G with vertex sets X, Y and Z, the sum of f(x, y, z) over all triangles xyz of G is at most c_{3}LMN in magnitude. Proof. Assume that (i) is false, so that

∑_{x_{0},x_{1}∈X} ∑_{y_{0},y_{1}∈Y} ∑_{z_{0},z_{1}∈Z} ∏_{(i,j,k)∈{0,1}^{3}} f(x_{i}, y_{j}, z_{k}) > c_{1}L^{2}M^{2}N^{2} .

Choose x_{1}, y_{1} and z_{1} randomly and independently and fix them. Then the average of the sum

∑_{x_{0},y_{0},z_{0}} ∏_{(i,j,k)∈{0,1}^{3}} f(x_{i}, y_{j}, z_{k})

is greater than c_{1}LMN, so the sum itself is greater than c_{1}LMN for at least one choice of x_{1}, y_{1} and z_{1}. But then (ii) is false if we set c_{2} = c_{1}, u(x, y) = f(x, y, z_{1}), v(y, z) = f(x_{1}, y, z)f(x_{1}, y_{1}, z) and w(x, z) = f(x, y_{1}, z)f(x, y_{1}, z_{1})f(x_{1}, y_{1}, z)f(x_{1}, y_{1}, z_{1}).

Again, the details do not matter here: the point is that if we write x, y and z for x_{0}, y_{0} and z_{0}, then f(x, y, z) is the only term in the product that depends on all of x, y and z, so fixing x_{1}, y_{1} and z_{1} results in an expression of the form ∑_{x,y,z} f(x, y, z)u(x, y)v(y, z)w(x, z).

Now let us prove the reverse inequality by making repeated use of the Cauchy-Schwarz inequality. This is where we shall use the notation introduced before the statement of the theorem.

( ∑_{x,y,z}f(x, y, z)u(x, y)v(y, z)w(x, z))^{8}

⩽ (MN ∑_{y,z}(∑_{x} f(x, y, z)u(x, y)v(y, z)w(x, z))^{2})^{4}

⩽ M^{4}N^{4}(∑_{y,z}(∑_{x} f(x, y, z)u(x, y)w(x, z))^{2})^{4}

= M^{4}N^{4}(∑_{x,x′} ∑_{y,z} f(x, y, z)f(x′, y, z)u(x, y)u(x′, y)w(x, z)w(x′, z))^{4}

= M^{4}N^{4}(∑_{x,x′} ∑_{y,z} f_{x,x′}(y, z)u_{x,x′}(y)w_{x,x′}(z))^{4}

⩽ M^{4}N^{4}L^{6} ∑_{x,x′}(∑_{y,z} f_{x,x′}(y, z)u_{x,x′}(y)w_{x,x′}(z))^{4} .

We now perform on the inner sum the steps from the corresponding part of the proof of Theorem 3.1. The last expression is at most

M^{4}N^{4}L^{6} ∑_{x,x′}(∑_{z}(∑_{y} f_{x,x′}(y, z)u_{x,x′}(y)w_{x,x′}(z))^{2})^{2}

⩽ M^{4}N^{4}L^{6} ∑_{x,x′}(N ∑_{z}(∑_{y} f_{x,x′}(y, z)u_{x,x′}(y))^{2})^{2}

= M^{4}N^{6}L^{6} ∑_{x,x′}(∑_{y,y′} ∑_{z} f_{x,x′}(y, z)f_{x,x′}(y′, z)u_{x,x′}(y)u_{x,x′}(y′))^{2}

= M^{4}N^{6}L^{6} ∑_{x,x′}(∑_{y,y′} ∑_{z} f_{x,x′,y,y′}(z)u_{x,x′,y,y′})^{2}

⩽ M^{4}N^{6}L^{6} ∑_{x,x′} M^{2} ∑_{y,y′}(∑_{z} f_{x,x′,y,y′}(z)u_{x,x′,y,y′})^{2}

⩽ M^{6}N^{6}L^{6} ∑_{x,x′} ∑_{y,y′}(∑_{z} f_{x,x′,y,y′}(z))^{2}

= M^{6}N^{6}L^{6} ∑_{x,x′} ∑_{y,y′} ∑_{z,z′} f_{x,x′,y,y′,z,z′} .

This is another way of writing

M^{6}N^{6}L^{6} ∑_{x_{0},x_{1}∈X} ∑_{y_{0},y_{1}∈Y} ∑_{z_{0},z_{1}∈Z} ∏_{(i,j,k)∈{0,1}^{3}} f(x_{i}, y_{j}, z_{k}) .

It follows that if (i) is true then (ii) is true with c_{2} = c_{1}^{1/8}.

It is obvious that (ii) implies (iii), since one can take u, v and w to be the characteristic functions of the bipartite graphs G(X, Y), G(Y, Z) and G(X, Z). It therefore remains to prove that (iii) implies (ii).

Suppose, then, that (ii) is false and we have functions u : X ×Y → [−1, 1], v : Y ×Z → [−1, 1] and w : X × Z → [−1, 1] such that

| ∑_{x,y,z} f(x, y, z)u(x, y)v(y, z)w(x, z)| > c_{2}LMN .

One can write u as u_{+} − u_{−} with u_{+} and u_{−} disjointly supported and taking values in [0, 1], and one can do the same for v and w. It follows that there are functions a, b and c taking values in [0, 1] such that

| ∑_{x,y,z} f(x, y, z)a(x, y)b(y, z)c(x, z)| > c_{2}LMN/8 .

Now let A_{1}, B_{1} and C_{1} be random subsets of X × Y, Y × Z and X × Z, their elements chosen randomly and independently with probabilities given by the functions a, b and c. Writing A_{1}, B_{1} and C_{1} for the characteristic functions of the sets as well, we have that the expectation of

| ∑_{x,y,z} f(x, y, z)A_{1}(x, y)B_{1}(y, z)C_{1}(x, z)|

is at least c_{2}LMN/8. Choose A_{1}, B_{1} and C_{1} such that the absolute value of the sum is at least this big and let the complements of A_{1}, B_{1} and C_{1} be A_{2}, B_{2} and C_{2}. Write S_{ijk} for the sum ∑_{x,y,z} f(x, y, z)A_{i}(x, y)B_{j}(y, z)C_{k}(x, z). Since f sums to zero, we know that the S_{ijk} add up to zero. Since S_{111} has absolute value at least c_{2}LMN/8, it follows that at least one S_{ijk} exceeds c_{2}LMN/56. If we let G be the tripartite graph with edge sets A_{i}, B_{j} and C_{k}, then we have disproved (iii) for any c_{3} ⩽ c_{2}/56. □

It is now very natural to make the following pair of definitions.

Definition 4.2. Let X, Y and Z be sets of sizes L, M and N. A function f : X × Y × Z is α-quasirandom if

∑_{x_{0},x_{1}∈X} ∑_{y_{0},y_{1}∈Y} ∑_{z_{0},z_{1}∈Z} ∏_{(i,j,k)∈{0,1}^{3}} f(x_{i}, y_{j}, z_{k}) ⩽ αL^{2}M^{2}N^{2} .

Definition 4.3. Let H be a tripartite 3-uniform hypergraph with vertex sets X, Y and Z of sizes L, M and N. Let the number of edges of H be pLMN and let f(x, y, z) = H(x, y, z) − p. Then H is α-quasirandom if f is α-quasirandom.

As we commented earlier, this definition is not identical to Definition 2.4, but it is equivalent (give or take the precise value of α) and it is the one we shall use. The advantage it has is that it is easier to use when proving a counting lemma. Note that if H fails to be quasirandom in this sense, then we have the easy deduction that f fails property (ii) of Theorem 4.1, which in turn shows easily that H is not α-edge uniform (in the sense of Definition 2.6).

We come now to a counting lemma for quasirandom 3-uniform hypergraphs. For simplicity, we prove it only in one special case, that of simplices (these were defined just before the statement of Theorem 1.4), but it is an easy exercise to generalize this case to a full counting lemma, just as we generalized Lemma 3.4 to Theorem 3.5.

Lemma 4.4. Let H be a quadripartite 3-uniform hypergraph with vertex sets X, Y, Z and W, of sizes L, M and N and P respectively. Suppose that the induced subhypergraphs H(X, Y, Z), H(X, Y, W), H(X, Z, W) and H(Y, Z, W) are α-quasirandom with densities p, q, r and s respectively. Then the number of simplices in H differs from pqrsLMNP by at most 15α^{1/8}LMNP.

Proof. Let the variables x, y, z and w stand for elements of X, Y, Z and W. Let the letter H stand for the characteristic function of the hypergraph H as well as the hypergraph itself. Define functions f, g, h and k (with obvious domains) by f(x, y, z) = H(x, y, z) − p, g(x, y, w) = H(x, y, w) − q, h(x, z, w) = H(x, z, w) − r and k(y, z, w) = H(y, z, w) − s. Then the number of simplices in H is

∑_{x,y,z,w}(p + f(x, y, z))(q + g(x, y, w))(r + h(x, z, w))(s + k(y, z, w)) .

The main term in this sum is pqrsLMNP. We shall now show that all other terms are significantly smaller. Consider, for example, any term that chooses f(x, y, z) rather than p from the first bracket. For each fixed w this results in a sum of the form ∑_{x,y,z} f(x, y, z)t(x, y)u(y, z)v(z, x), with t, u and v taking values in the interval [−1, 1]. Therefore, by Theorem 4.1 (and the bound obtained in the proof), the entire sum comes to at most α^{1/8}LMNP. The same argument works for g, h and k, and that is enough to show that all terms apart from the main term have modulus at most α^{1/8}LMNP, which proves the result. □

§5. Why quasirandom 3-graphs are not enough.

To prove Roth’s theorem (that is, Szemerédi’s theorem for progressions of length 3), one uses a combination of Szemerédi’s regularity lemma and Lemma 3.4. The reader who has followed the paper so far may be disappointed to learn that Lemma 4.4 is not very useful when it comes to generalizing that argument. However, any effort spent on understanding it will pay dividends later, since the result that is useful is a further generalization, proved by a similar technique, and the steps of that result will make much more sense if they are compared with the steps in the proofs of Theorem 4.1 and Lemma 4.4.

What, then, is inadequate about quasirandomness of 3-uniform hypergraphs? The answer is not that the property is too weak - as Lemma 4.4 demonstrates - but rather that it is too strong. In other words, we are delighted if we are lucky enough to be presented with a quasirandom hypergraph, but in general it is too much to hope for. If we wish to generalize the proof for graphs, triangles and progressions of length 3, then we shall need two components: a regularity lemma and an associated counting lemma. The regularity lemma will tell us that we can divide any 3-uniform hypergraph H into random-like pieces (whatever this turns out to mean, it should somehow be analogous to the statement of the usual regularity lemma for graphs) and the counting lemma will allow us to use this information to approximate the number of simplices in H. One might think that “randomlike pieces” should simply be quasirandom sub-hypergraphs, but any sensible statement along these lines turns out to be false.

Here is a simple example of a tripartite 3-uniform hypergraph that has no large quasirandom subhypergraph, and which therefore cannot be decomposed into a small number of them. Let X, Y and Z be three sets of size N and let G be a random tripartite graph with vertex sets X, Y and Z. Let H be the hypergraph consisting of all triangles in G, that is, all triples (x, y, z) such that xy, yz and xz are edges of G. Then the density of H is 1/8, but the number of octahedra in H is about 2^{−12}N^{6} (because an octahedron, considered as a graph, has 12 edges) rather than 8^{−8}N^{6} as it should have if H is quasirandom.

Now, given any large subsets X′ ⊂ X, Y′ ⊂ Y and Z′ ⊂ Z, the graphs G(X′, Y′), G(Y′, Z′) and G(X′, Z′) are (with high probability) quasirandom, and therefore the same reasoning shows that the induced subhypergraph H(X′, Y′, Z′) still fails to be quasirandom.

Indeed, the situation is even worse, as it is not just induced subhypergraphs that fail to be quasirandom. Let H′ be any subhypergraph of H and let the density of H′ be p. Since H′ is a subhypergraph of H,

∑_{x,y,z} H′(x, y, z)G(x, y)G(y, z)G(x, z) = pN^{3} .

If we set f(x, y, z) = H′(x, y, z) − p, then we can deduce that

∑_{x,y,z} f(x, y, z)G(x, y)G(y, z)G(x, z) = pN^{3} − pN^{3}/8 ,

which is a clear violation of property (iii) of Theorem 4.1. This argument remains valid even if one starts by restricting to large subsets X′, Y′ and Z′ of X, Y and Z.

This looks like bad news, and in a way it is, because it makes life more complicated, but it is not as bad as all that. To see why not, just look back at the discussion of the example above. Although the hypergraph H was not quasirandom, we had absolutely no difficulty calculating roughly how many octahedra it should have, and the reason was that we were able to use the quasirandomness of the graphs G(X, Y), G(Y, Z) and G(Z, X). More generally, suppose we construct a hypergraph H as follows. First, we take random graphs G(X, Y), G(Y, Z) and G(Z, X) with densities p, q and r and let G be the tripartite graph formed by their union. Next, we define H_{0} to be the hypergraph consisting of all triangles of G. Finally, we let H be a random subhypergraph of H_{0}, choosing each edge of H_{0} with probability s and making all choices independently.

How many octahedra do we expect H to contain? Well, if we choose x_{0}, x_{1} ∈ X, y_{0}, y_{1} ∈ Y and z_{0}, z_{1} ∈ Z at random, then the probability that a pair x_{i}y_{j} belongs to G is p, and these probabilities are more or less independent, so the probability that all four pairs belong to G is almost exactly p^{4}. Similar statements hold for the y_{i}z_{j} and the x_{i}z_{j}, so the probability that all the 2-edges of the octahedron belong to G is almost exactly (pqr)^{4}. If this happens, then there are eight 3-edges, or faces, each of which has a probability s of lying in H. We therefore expect the number of octahedra in H to be about (pqr)^{4}s^{8}(|X||Y ||Z|)^{2}.

It is clear from that calculation that quasirandom hypergraphs are not the only ones for which it ought to be possible to prove a counting lemma. That is, one ought to be able to relax the assumptions of Lemma 4.4 so that the induced subhypergraphs are not necessarily quasirandom, but are built rather like the hypergraph considered in the last paragraph. It is a lemma of this kind that we shall state and prove in the next section.

This will deal with the difficulty that we have just discussed. If we have proved a counting lemma for a wider class of hypergraphs than just the quasirandom ones, then it is enough, when proving a regularity lemma, to show that a hypergraph can be decomposed into subgraphs from this wider class. And this assertion is weak enough to be true, which is of course a huge advantage.

The situation we have just encountered occurs in other parts of mathematics - indeed, something like it seems to happen for almost any class of mathematical objects that do not have too rigid a structure but are well-endowed with subobjects. In such a situation, it is very useful to find, for any object X in the class, a subobject Y ⊂ X that is in some way “stable”, in the sense that any further subobject Z ⊂ Y does not differ interestingly from Y. To do this one must first identify the stable objects and then prove that every object contains a stable subobject. Here the structure we have been talking about is an approximate one (it is not hard to define a notion of approximate isomorphism to make it precise).

More exact instances are usually called canonical Ramsey theorems, of which the most famous example concerns arbitrary colourings of the edges of the complete graph on ℕ. Here, one cannot expect to find a monochromatic infinite clique, but one can find an infinite set X such that the restriction of the colouring to the clique X^{(2)} has one of four simple forms. Write all edges as xy with x < y and write xy ∼ zw if xy and zw have the same colour. Then one of the following four statements is true for all pairs xy, zw of edges with x, y, z, w ∈ X: (i) xy ∼ zw if and only if x = z and y = w; (ii) xy ∼ zw if and only if x = z; (iii) xy ∼ zw if and only if y = w; (iv) xy ∼ zw. It is easy to check that if one of these statements holds for X then it holds for all subsets Y ⊂ X, so X (together with its colouring) is stable.

A second class of examples arises in Banach space theory. There are several theorems in the subject that allow one to pass from a Banach space X, perhaps with some extra properties, to a subspace Y that is in some way easier to handle. And in many cases, the property that Y has is a stability property, in the sense that all its subspaces are in some important way similar to the space itself.

Before we embark on the main results of this paper, here is a second hypergraph example to consider. It is not completely obvious that the first one matters, since it is not derived from a subset of ℤ_{N} in the way shown after Definition 2.3. Perhaps hypergraphs that come from sets have some extra property that makes them decomposable into quasirandom pieces.

It turns out that they don’t. Rather than show precisely this, we shall briefly discuss a similar result for functions, because it is much easier technically. It is derived in a simple way from an example that plays a similar role in the analytic proof of Szemerédi’s theorem [G1].

Let N be an odd positive integer and let ω = e^{2πi/N}. Define a function f : ℤ_{N}^{3} → ℂ by f(x, y, z) = ω^{(x+y+z)^{2}}. This can be decomposed as ω^{(x+y)^{2}}ω^{(y+z)^{2}}ω^{(x+z)^{2}}ω^{−x^{2}}ω^{−y^{2}}ω^{−z^{2}}, or alternatively as g(x, y)g(y, z)g(x, z), where g(x, y) = ω^{2^{−1}(x^{2}+y^{2})+2xy}. It is a straightforward exercise to deduce from the fact that the function ω^{x^{2}} has very small Fourier coefficients that g is a quasirandom function. So once again, we have a function of three variables that is a product of three quasirandom functions of two variables and therefore not quasirandom itself, even after restriction to any large set.

§6. A counting lemma for two-dimensional quasirandom simplicial complexes.

What the previous section shows is that we should consider objects that are slightly more complicated than 3-uniform hypergraphs. We need to look instead at 3-uniform hypergraphs that are obtained as subhypergraphs H of the set of all triangles in some tripartite graph G, paying attention to both H and G. Let us write Δ(G) for the set of triangles of G. Then one of these objects can be defined more formally as an ordered pair (G, H) such that H ⊂ Δ(G). It should be considered as quasirandom if the three bipartite parts of the graph G are quasirandom and H in some way “sits quasirandomly” inside Δ(G). Our first task is to make this idea precise. Once we have done that, we shall prove another sequence of results, again following the scheme of §3 and §4.

A slightly better way to think of our objects (G, H) is as two-dimensional simplicial complexes: that is, as collections Σ of sets of size at most 3 with the property that if A ∈ Σ and B ⊂ A then B ∈ Σ. Of course, to do this we need to take not just a graph and a hypergraph, but also a set of vertices (and, to be strictly correct, the empty set). What makes this a better way to think about it is partly that it is more natural when one comes to generalize to k-uniform hypergraphs, and partly that the regularity lemma we shall eventually prove involves restricting vertex sets. Despite all this, it will be simpler to stick to pairs (G, H) for now and bear in mind that our results will later be applied to pairs with restricted vertex sets. Let us make a formal definition.

Definition 6.1. An r-partite chain is a pair (G, H), where G is an r-partite graph, H is an r-partite hypergraph with the same vertex sets as G, and H ⊂ Δ(G).

Suppose, then, that we have a chain (G, H). We know what it means for the bipartite parts of G to be quasirandom, but must now say what it means for H to sit quasirandomly inside Δ(G). As before, we shall define this in terms of functions. For convenience, let us make another definition.

Definition 6.2. Let X, Y and Z be three sets and let f : X × Y × Z → ℝ be a function. Then oct(f) is defined to be f_{x,x′,y,y′,z,z′}, which equals the sum

∑ f(x, y, z)f(x, y, z′)f(x, y′, z)f(x, y′, z′)f(x′, y, z)f(x′, y, z′)f(x′, y′, z)f(x′, y′, z′)

taken over all x, x′ ∈ X, y, y′ ∈ Y and z, z′ ∈ Z.

Recall that the notation f_{x,x′,y,y′,z,z′} was introduced before the statement of Theorem 4.1. We shall use it again when proving Theorem 6.5 below.

If f is the characteristic function of a hypergraph H then oct(f) is the number of octahedra in H. We shall write oct(H) for this quantity. With this notation it is easy to express precisely what it means for H to sit quasirandomly in G.

Definition 6.3. Let G be a tripartite graph with vertex sets X, Y and Z of sizes L, M and N, and let f : X × Y × Z → [−1, 1] be a function such that f is supported in Δ(G).

Let the densities of G(X, Y), G(Y, Z) and G(X, Z) be p, q and r respectively. Then f is α-quasirandom relative to G if oct(f) ⩽ α(pqr)^{4}(LMN)^{2}. Now let H be a tripartite 3-uniform hypergraph with vertex sets X, Y and Z and suppose that H ⊂ Δ(G) and |H| = γ|Δ(G)|. Let f(x, y, z) = H(x, y, z) − γ for (x, y, z) ∈ Δ(G) and 0 otherwise. Then H is α-quasirandom relative to G if f is α-quasirandom relative to G.

It might be more natural to say that f is α-quasirandom relative to G if oct(f) ⩽ α oct(G). If G is quasirandom, then this is roughly what the definition does say, and we shall apply the definition only to quasirandom graphs, where the formulation we have given turns out to be slightly more convenient for technical reasons.

These definitions are very similar to those of §4, but now everything takes place inside Δ(G). What we shall show is that if the bipartite parts of G are sufficiently quasirandom, then relative quasirandomness has consequences that are also similar to those of §4, though for reasons that will be explained more fully later, some of them are a bit more complicated.

The main result of this section is a counting lemma for simplices in quadripartite chains. The reader who follows the proof will see that it can be generalized easily to a counting lemma for arbitrary subchains. However, the case of simplices is easier to present, and is enough for the application to arithmetic progressions of length four.

Before we prove this counting lemma, we need to prepare for it with a technical lemma (Lemma 6.6 below), which itself needs small amount of preparation.

Definition 6.4. Let G and H be k-partite graphs with vertex sets X = X_{1} ∪ … ∪ X_{k} and A = A_{1} ∪ … ∪ A_{k} respectively. A homomorphism from H to G is a map ϕ : A → X such that ϕ(A_{i}) ⊂ X_{i} for each i and such that ϕ(v)ϕ(w) is an edge of G whenever vw is an edge of H.

Note that in the above definition we say nothing about what happens if vw is not an edge of H. Nor do we insist that ϕ is an injection.

Let G be a quadripartite graph with vertex sets X, Y, Z and W of sizes L, M, N and P respectively. Let H be another quadripartite graph, with vertex sets A, B, C and D of sizes q, r, s and t, and let a, a′ ∈ A, b, b′ ∈ B and c, c′ ∈ C be six vertices and suppose that the set {a, a′, b, b′, c, c′} is independent. For any x, x′ ∈ X, y, y′ ∈ Y and z, z′ ∈ Z let h(x, x′, y, y′, z, z′) be the number of homomorphisms ϕ from H to G such that ϕ(a) = x, ϕ(a′) = x′, ϕ(b) = y, ϕ(b′) = y′, ϕ(c) = z and ϕ(c′) = z′. Lemma 6.6 will tell us that if G is α-quasirandom for a sufficiently small α, then the function h is approximately constant. This is a simple application of the counting lemma for graphs (Theorem 3.5) and the second-moment method.

Before we embark on the lemma, let us think about the constant we expect to obtain. For each pair i, j let the density of the graph G(X_{i}, X_{j}) be δ_{ij}. Given any edge e of H, let us set δ(e) to be the δ_{ij} for which A_{i} and A_{j} are the vertex sets containing the two vertices joined by e. The number of ways of choosing a function ϕ that respects the partitions of G and H is L^{q}M^{r}N^{s}P^{t}. If we fix the images of a, a′, b, b′, c, c′ then the number of possible extensions is L^{q−2}M^{r−2}N^{s−2}P^{t}. Given an edge e of H, it joins A_{i} to A_{j} for some 1 ⩽ i < j ⩽ 4. The probability that ϕ(e) is an edge of G is the density δ_{ij} of the bipartite subgraph G(X_{i}, X_{j}). If G behaves like a random graph, then the probability that ϕ is a homomorphism will be roughly the product, δ, of all these individual edge-probabilities. We shall call this the expected H-density of G. (The assumption that {a, a′, b, b′, c, c′} is an independent set means that we do not have to worry about whether there are edges joining vertices in the set {x, x′, y, y′, z, z′}.) We expect the approximately constant value of h to be about δL^{q−2}M^{r−2}N^{s−2}P^{t}.

We shall be using second moments, so for convenience here first is an easy technical lemma that encapsulates what we need for the main lemma.

Lemma 6.5. Let α, δ ∈ [0, 1], let R be a real number and let a_{1}, …, a_{n} be real numbers such that ∑_{i=1}^{n} a_{i} ⩾ (δ − α)Rn and ∑_{i=1}^{n} a_{i}^{2} ⩽ (δ^{2} + α)R^{2}n. Then |a_{i} − δR| ⩽ Rα^{1/4} for all but at most 3n\sqrt{α} values of i.

Proof. Using our hypotheses, we find that

∑_{i=1}^{n}(a_{i} − δR)^{2} = ∑_{i=1}^{n} a_{i}^{2} − 2R ∑_{i=1}^{n} a_{i}δ + nδ^{2}R^{2}
⩽ R^{2}n(δ^{2} + α − 2δ(δ − α) + δ^{2})
= R^{2}nα(1 + 2δ) ⩽ 3R^{2}nα .

The result follows immediately. □

The statement that follows will look somewhat peculiar: we are giving the particular case that happens to arise later of a more general statement which, though more natural, is perhaps harder to digest. Some readers may wish to jump to Lemma 6.7 and then come back to this point of the paper when the motivation for it has become clear.

Lemma 6.6. Let G, H and δ be as in the remarks preceding Lemma 6.5. Let 0 < ϵ ⩽ 1, let α > 0 be such that 2^{m}α^{1/16} ⩽ ϵδ/3 and suppose that G is α-quasirandom. Let m be the number of edges of H and let δ be the expected H-density of G. Then the number of sextuples (x, x′, y, y′, z, z′) for which h(x, x′, y, y′, z, z′) differs from δL^{q−2}M^{r−2}N^{s−2}P^{t} by more than ϵδL^{q−2}M^{r−2}N^{s−2}P^{t} is at most ϵδL^{2}M^{2}N^{2}.

Proof. First, we estimate ∑_{x,x′,y,y′,z,z′} h(x, x′, y, y′, z, z′). This is the number of homomorphisms ϕ from H to G, which, by Theorem 3.5, is at least (δ − 2^{m}α^{1/4})L^{q}M^{r}N^{s}P^{t}.

Next, we estimate ∑_{x,x′,y,y′,z,z′} h(x, x′, y, y′, z, z′)^{2}. For this we can use the counting lemma again, but first we must define an auxiliary graph J. For each vertex v of H apart from a, a′, b, b′, c and c′, let v_{1} be a copy of v. Let γ be a function defined on the vertex set V of H that takes the vertices a, a′, b, b′, c and c′ to themselves and takes any other vertex v to its copy v_{1}. The vertex set of J is V ∪ γ(V) and the edges of J are the edges of H together with all pairs γ(u)γ(v) such that uv is an edge of H. It is easy to see that ∑_{x,x′,y,y′,z,z′} h(x, x′, y, y′, z, z′)^{2} is the number of homomorphisms from J to G, which is of course why we defined J. Since every edge of H has been doubled up in J, the product of the edge-probabilities of J is δ^{2}, so Theorem 3.5 tells us that the number of homomorphisms from J to G is at most (δ^{2} + 2^{2m}α^{1/4})L^{2q−2}M^{2r−2}N^{2s−2}P^{t}.

Let us now apply the previous lemma, with n = L^{2}M^{2}N^{2}, R = L^{q−2}M^{r−2}N^{s−2}P^{t}, δ as it is and α replaced by 2^{2m}α^{1/4}. Then the hypotheses of the lemma are satisfied and it tells us that the number of sextuples (x, x′, y, y′, z, z′) for which h(x, x′, y, y′, z, z′) differs from δL^{q−2}M^{r−2}N^{s−2}P^{t} by more than 2^{m/2}α^{1/16}L^{q−2}M^{r−2}N^{s−2}P^{t} is at most 3.2^{m}α^{1/8}L^{2}M^{2}N^{2}. Our upper bound on α then implies the result. □

A few words of explanation are needed before the next lemma, to draw attention to how it differs from the implication of (ii) from (i) in Theorem 4.1. As in that proof we have a sum and we wish to show that it is small, subject to a quasirandomness assumption about the function f. As in that proof we shall use the Cauchy-Schwarz inequality several times, and the manipulations will be very similar. However, this time the functions we look at are supported in the set of triangles of a quasirandom quadripartite graph G, and the bound we obtain is stronger because it depends on the densities of the six bipartite parts of G. The significance of this is that the theorem says something even when the quasirandomness parameter η below is much larger than any of these densities. This extra strength is very significant when G is sparse, as it will be if it is one of the graphs given to us by the hypergraph regularity lemma proved later. To obtain the extra strength, we shall be very careful to use the full strength of the Cauchy-Schwarz inequality whenever we apply it: if the number of i such that a_{i} ≠ 0 is m, then we shall bound (∑_{i=1}^{n} a_{i}) above by m ∑_{i=1}^{n} a_{i}^{2} rather than by n ∑_{i=1}^{n} a_{i}^{2}.

We shall use the following notation. The graph G will have vertex sets X, Y, Z and W, but we shall also think of them as X_{1}, X_{2}, X_{3} and X_{4} respectively. (Sometimes one notation is easier to handle, sometimes the other.) The density of G_{ij} will again be denoted δ_{ij}. We shall write h_{i} for |X_{i}|, h_{ij} for |G(X_{i}, X_{j})| and h_{ijk} for the number of triangles in G(X_{i}, X_{j}) ∪ G(X_{j}, X_{k}) ∪ G(X_{i}, X_{k}). If x, x′ ∈ X_{1} and i > 1 then we shall also write h_{i}(x, x′) for the number of vertices in X_{i} that are joined to both x and x′. Similarly, if 1 < i < j then we shall write h_{ij}(x, x′) for the set of all edges yz in G(X_{i}, X_{j}) such that y and z are both joined to both of x and x′. Similarly, if x, x′ ∈ X_{1}, y, y′ ∈ X_{2} and i > 2, then we shall write h_{i}(x, x′, y, y) for the number of z ∈ X_{i} that are joined to all of x, x′, y and y′. It is numbers such as these that will appear when we make our more efficient uses of the Cauchy-Schwarz inequality.

Lemma 6.7. Let G be as just described, and let f : X ×Y ×Z → [−1, 1], g : X ×Y ×W → [−1, 1], h : X × Z × W → [−1, 1] and k : Y × Z × W → [−1, 1] be functions that are non-zero only at triples that form triangles in G. Suppose that G is α-quasirandom and that f is η-quasirandom relative to the tripartite graph G(X, Y, Z). Suppose also that 2^{36}α^{1/16} ⩽ η(δ_{12}δ_{23}δ_{13}δ_{14}δ_{24}δ_{34})^{8}/6. Then

| ∑_{x,y,z,w} f(x, y, z)g(x, y, w)h(x, z, w)k(y, z, w)| ⩽ (2η)^{1/8}δ_{12}δ_{23}δ_{13}δ_{14}δ_{24}δ_{34}LMNP .

Proof. We begin with several applications of the Cauchy-Schwarz inequality, of a similar kind to ones that we have seen already.

( ∑_{x,y,z,w} f(x, y, z)g(x, y, w)h(x, z, w)k(y, z, w))^{8}

⩽ (h_{234} ∑_{y,z,w}(∑_{x} f(x, y, z)g(x, y, w)h(x, z, w)k(y, z, w))^{2})^{4}

⩽ (h_{234} ∑_{y,z,w}(∑_{x} f(x, y, z)g(x, y, w)h(x, z, w))^{2})^{4}

= h_{234}^{4}(∑_{x,x′} ∑_{y,z,w} f_{x,x′}(y, z)g_{x,x′}(y, w)h_{x,x′}(z, w))^{4}

⩽ h_{234}^{4}h_{1}^{6} ∑_{x,x′}( ∑_{y,z,w} f_{x,x′}(y, z)g_{x,x′}(y, w)h_{x,x′}(z, w))^{4}

⩽ h_{234}^{4}h_{1}^{6} ∑_{x,x′}(h_{34}(x, x′) ∑_{z,w}(∑_{y} f_{x,x′}(y, z)g_{x,x′}(y, w)h_{x,x′}(z, w))^{2})^{2}

⩽ h_{234}^{4}h_{1}^{6} ∑_{x,x′}(h_{34}(x, x′) ∑_{z,w} G(z, w)(∑_{y} f_{x,x′}(y, z)g_{x,x′}(y, w))^{2})^{2}

= h_{234}^{4}h_{1}^{6} ∑_{x,x′} h_{34}(x, x′)^{2}(∑_{y,y′} ∑_{z,w} f_{x,x′,y,y′}(z)g_{x,x′,y,y′}(w)G(z, w))^{2}

⩽ h_{234}^{4}h_{1}^{6} ∑_{x,x′} h_{34}(x, x′)^{2}h_{2}(x, x′)^{2} ∑_{y,y′}(∑_{z,w} f_{x,x′,y,y′}(z)g_{x,x′,y,y′}(w)G(z, w))^{2}

⩽ h_{234}^{4}h_{1}^{6} ∑_{x,x′} h_{34}(x, x′)^{2}h_{2}(x, x′)^{2} ∑_{y,y′} h_{4}(x, x′, y, y′)

∑_{w}(∑_{z} f_{x,x′,y,y′}(z)g_{x,x′,y,y′}(w)G(z, w))^{2}

⩽ h_{234}^{4}h_{1}^{6} ∑_{x,x′} h_{34}(x, x′)^{2}h_{2}(x, x′)^{2} ∑_{y,y′} h_{4}(x, x′, y, y′)

∑_{w}(∑_{z} f_{x,x′,y,y′}(z)G_{x,x′}G_{y,y′}(w)G(z, w))^{2}

= h_{234}^{4}h_{1}^{6} ∑_{x,x′} h_{34}(x, x′)^{2}h_{2}(x, x′)^{2} ∑_{y,y′} h_{4}(x, x′, y, y′)

∑_{z,z′} f_{x,x′,y,y′,z,z′} ∑_{w} G_{x,x′}G_{y,y′}G_{z,z′}(w)

= h_{234}^{4}h_{1}^{6} ∑_{x,x′} h_{34}(x, x′)^{2}h_{2}(x, x′)^{2} ∑_{y,y′} h_{4}(x, x′, y, y′) ∑_{z,z′} f_{x,x′,y,y′,z,z′}h_{4}(x, x′, y, y′, z, z′)

The main idea of the proof has now been given. The rest of the argument consists in showing that the h-terms are all approximately constant and calculating what the result would be if they were constant. For this we use the lemma about graphs proved earlier.

The final line above can be written as

∑_{x,x′,y,y′,z,z′} h(x, x′, y, y′, z, z′)f_{x,x′,y,y′,z,z′} = ⟨h, F ⟩ ,

where F (x, x′, y, y′, z, z′) = f_{x,x′,y,y′,z,z′} and

h(x, x′, y, y′, z, z′) = h_{234}^{4}h_{1}^{6}h_{34}(x, x′)^{2}h_{2}(x, x′)^{2}h_{4}(x, x′, y, y′)h_{4}(x, x′, y, y′, z, z′) .

This last quantity is the number of homomorphisms from a certain quadripartite graph H to G, given that a particular six of its vertices (none of which are joined to each other) map to x, x′, y, y′, z and z′. To see this, note first that it is true of each individual term in the product. For example, to understand the term h_{34}(x, x′)^{2} in this way, take the graph J with vertex set {a, a′, b, b′, c, c′, d, e} and edges ad, ae, a′d, a′e and de. The number of homomorphisms ϕ from J to G such that ϕ(a) = x, ϕ(a′) = x′, ϕ(b) = y, ϕ(b′) = y′, ϕ(c) = z, ϕ(c′) = z′, ϕ(d) ∈ Z and ϕ(e) ∈ W is the number of pairs (z, w) ∈ Z × W such that z is joined to w and both z and w are joined to both x and x′, which is the definition of h_{34}(x, x′). To obtain the product, one takes disjoint copies of all the graphs J constructed in this way and identifies the vertices a, a′, b, b′, c and c′ from each one. (That is, the a in one graph is the same as the a in another, and so on.)

Let the vertex set of H be A ∪ B ∪ C ∪ D, and let us look at the sizes of A, B, C and D. The set A contains a and a′, and receives an additional six (isolated) vertices from the term h_{1}^{6}. B contains b and b′, and receives in addition four vertices from h_{234}^{4} and two from h_{2}(x, x′). C contains c and c′ and receives four vertices from h_{234}^{4} and two from h_{34}(x, x′)^{2}. Finally, D receives four vertices from h_{234}^{4}, two from h_{34}(x, x′) and one each from h_{4}(x, x′, y, y′) and h_{4}(x, x′, y, y′, z, z′).

In a similar way one can work out how many edges there are between each pair from A, B, C and D. For example, the number of edges between B and D is 4+2+2 = 8, since h_{234}^{4} contributes four, h_{4}(x, x′, y, y′) contributes two and h_{4}(x, x′, y, y′, z, z′) contributes two. As another example, the number of edges between A and C is 4, all coming from h_{34}(x, x′)^{2}. It turns out that there are eight edges between any pair of sets that includes D and four between any other pair.

We wish to apply Lemma 6.6. It follows from the simple calculations we have just made that the expected H-density of G is

δ = (δ_{12}δ_{23}δ_{13})^{4}(δ_{14}δ_{24}δ_{34})^{8} .

We also have q = r = s = t = 8 and m = 36. Let ϵ = η(δ_{12}δ_{23}δ_{13})^{4}/2 and call a sextuple (x, x′, y, y′, z, z′) bad if |h(x, x′, y, y′, z, z′) − δL^{6}M^{6}N^{6}P^{8}| > ϵδL^{6}M^{6}N^{6}P^{8}, and good otherwise.

By Lemma 6.6, the number of bad sextuples is at most ϵδL^{2}M^{2}N^{2}, and a trivial upper bound for each h(x, x′, y, y′, z, z′) is L^{6}M^{6}N^{6}P^{8}. Therefore, if we let h′ be a new function that equals h for every good sextuple and takes the value δL^{6}M^{6}N^{6}P^{8} otherwise, then ∥h − h′∥_{1} ⩽ ϵδ(LMNP)^{8}. Writing d for the constant function δL^{6}M^{6}N^{6}P^{8}, we also have that ∥h′ − d∥_{∞} ⩽ ϵδL^{6}M^{6}N^{6}P^{8}. As for F, we know that ∥F ∥_{1} is at most the number of octahedra in the graph G(X, Y, Z). By Theorem 3.5, this is at most 2(δ_{12}δ_{23}δ_{13})^{4}(LMN)^{2}. Finally, we are assuming also the bound ∥F ∥_{∞} ⩽ 1. Putting all these facts together, we find that

|⟨h, F ⟩ − ⟨d, F ⟩| ⩽ |⟨h − h′, F ⟩| + |⟨h′ − d, F ⟩|
⩽ ∥h − h′∥_{1}∥F ∥_{∞} + ∥h′ − d∥_{∞}∥F ∥_{1}
⩽ ϵδ(LMNP)^{8} + ϵδ(LMNP)^{8}
= η(δ_{12}δ_{23}δ_{13}δ_{14}δ_{24}δ_{34}LMNP)^{8} .

But the the relative quasirandomness assumption on f tells us that

⟨d, F ⟩ = δL^{6}M^{6}N^{6}P^{8} oct(f)
⩽ ηδ(δ_{12}δ_{23}δ_{13})^{4}(LMNP)^{8}
= η(δ_{12}δ_{23}δ_{13}δ_{14}δ_{24}δ_{34}LMNP)^{8} .

The result follows. □

We are now ready to prove a generalization of Lemma 4.4 from quasirandom hypergraphs to quasirandom chains. Notice the dependence of parameters in the statement. The graph G is α-quasirandom and the hypergraph H is relatively η-quasirandom. Both α and η need to be small for the conclusion to hold and be useful, but whereas the condition on α depends on η, the density of G and the relative density of H, the smallness of η depends only on the last of these. In particular, as we have already mentioned, η can be much larger than the density of G. This is critically important, since it is all that can be guaranteed by the regularity lemma later.

Theorem 6.8. Let X, Y, Z and W be sets of size L, M, N and P respectively. Let G be a quadripartite graph with vertex sets X, Y, Z and W and suppose that the six bipartite parts of G are α-quasirandom. Write δ_{12} for the density of the graph G(X, Y), and similarly for the other parts, and suppose that all these graphs are α-quasirandom. Let H_{123} be a tripartite hypergraph with vertex sets X, Y and Z that is η-quasirandom relative to Δ(G(X, Y, Z)) and similarly for H_{124}, H_{134} and H_{234}. For each triple ijk Let the relative density of H_{ijk} be δ_{ijk}. Let H be the union of the hypergraphs H_{ijk}. Suppose that α satisfies the condition 2^{36}α^{1/16} ⩽ η(δ_{12}δ_{23}δ_{13}δ_{14}δ_{24}δ_{34})^{8}/6. Then the number of simplices in H differs from δ_{12}δ_{23}δ_{13}δ_{14}δ_{24}δ_{34}δ_{123}δ_{124}δ_{134}δ_{234}LMNP by at most 8η^{1/8}δ_{12}δ_{23}δ_{13}δ_{14}δ_{24}δ_{34}LMNP.

Proof. We wish to estimate the sum

∑_{x,y,z,w} H(x, y, z)H(x, y, w)H(x, z, w)H(y, z, w) .

For each triple 1 ⩽ i < j < k ⩽ 4 let d_{ijk}(x, y, z) = δ_{ijk}G(x, y)G(y, z)G(x, z). Then

∑_{x,y,z,w} d_{123}(x, y, z)d_{124}(x, y, w)d_{134}(x, z, w)d_{234}(y, z, w)

is δ_{123}δ_{124}δ_{134}δ_{234} times the number of simplices in G. Since G is α-quasirandom, Theorem 3.5 tells us that the number of simplices in G is δ_{12}δ_{23}δ_{13}δ_{14}δ_{24}δ_{34}LMNP, to within an error of at most 64α^{1/4}LMNP, which is certainly at most η^{1/8}LMNP.

If we let f(x, y, z) = H(x, y, z) − d_{123}(x, y, z), then our hypothesis implies that f is η-quasirandom relative to G. If we take the sum we wish to estimate and change H(x, y, z) into d_{123}(x, y, z), then the difference we make to the sum is

| ∑_{x,y,z,w} f(x, y, z)H(x, y, w)H(x, z, w)H(y, z, w)| .

By Lemma 6.7, this is at most (2η)^{1/8}δ_{12}δ_{23}δ_{13}δ_{14}δ_{24}δ_{34}LMNP. By a similar argument we can replace H(x, y, w) by d_{124}(x, y, w), again making a difference of at most (2η)^{1/8}δ_{12}δ_{23}δ_{13}δ_{14}δ_{24}δ_{34}LMNP. Repeating this process twice more, we find that

\begin{matrix}| ∑_{x,y,z,w} H(x, y, z) & H(x, y, w)H(x, z, w)H(y, z, w) \\ − ∑_{x,y,z,w} d_{123}(x, y, z)d_{124}(x, y, w)d_{134}(x, z, w)d_{234}(y, z, w)| \end{matrix}

is at most 4(2η)^{1/8}δ_{12}δ_{23}δ_{13}δ_{14}δ_{24}δ_{34}LMNP. Combining this with the estimate of the previous paragraph, we obtain the desired result. □

We have now finished the hardest part of the proof, by identifying a class of stable hypergraphs and proving a counting lemma for them. It remains to prove a regularity lemma, which says, roughly speaking, that every dense 3-uniform hypergraph can be decomposed into stable subhypergraphs.

§7. A proof of Szemerédi’s regularity lemma.

The statement of Szemerédi’s regularity lemma given in the introduction is not quite standard, but it can be proved more cleanly and is better suited for generalizing to hypergraphs. To demonstrate the first of these assertions, to keep this paper self-contained and to illuminate the proof of hypergraph regularity, we shall now prove it in full.

Let G be a bipartite graph with vertex sets X and Y of sizes M and N respectively. Let X_{1} ∪ … ∪ X_{m} and Y_{1} ∪ … ∪ Y_{n} be partitions of X and Y, with |X_{i}| = α_{i}M and Y_{j} = β_{j}N. Write d(X_{i}, Y_{j}) for the density of the induced subgraph G(X_{i}, Y_{j}), that is, |X_{i}|^{−1}|Y_{j}|^{−1} times the number of edges from X_{i} to Y_{j}. The mean-square density of G with respect to the partitions is defined to be ∑_{i,j} α_{i}β_{j}d(X_{i}, Y_{j})^{2}. Sometimes, when G is clear from the context, we shall call this the mean-square density of the partitions. This concept can also be viewed probabilistically. Choose a random x ∈ X and y ∈ Y. Then x belongs to some X_{i} and y to some Y_{j} and the mean-square density is the expectation of the square of the density d(X_{i}, Y_{j}).

Our first steps are very simple - all they say is that certain projections on certain Hilbert spaces have norm at most 1. However, let us quickly establish them in our particular context.

Lemma 7.1. Let U be a finite set and let f : U → ℝ be a function with mean d. Let U = U_{1} ∪ … ∪ U_{s} with |U_{i}| = γ_{i}|U|, and let d_{i} be the mean of f restricted to U_{i}. Then d^{2} ⩽ ∑_{i=1}^{r} γ_{i}d_{i}^{2}.

Proof. By the Cauchy-Schwarz inequality,

(∑_{i=1}^{r} γ_{i}d_{i})^{2} ⩽ (∑_{i=1}^{r} γ_{i})(∑_{i=1}^{r} γ_{i}d_{i}^{2}) .

The left-hand side is d^{2} and the first bracket on the right-hand side is 1, so the result is proved. □

Lemma 7.2. Let U, f and U_{1}, …, U_{r} be as in Lemma 7.1. Suppose that each U_{i} is partitioned further into sets U_{ij}, let |U_{ij}| = γ_{ij}|U| and let d_{ij} be the mean of f restricted to U_{ij}. Then ∑_{i} γ_{i}d_{i}^{2} ⩽ ∑_{ij} γ_{ij}d_{ij}^{2}.

Proof. By Lemma 7.1, we have for each i the inequality

d_{i}^{2} ⩽ ∑_{j} \frac{γ_{ij}}{γ_{i}} d_{ij}^{2} .

Multiplying both sides by γ_{i} and summing over i gives the result. □

Corollary 7.3. Let G be a bipartite graph of density d with vertex sets X and Y of sizes M and N respectively. Let X_{1} ∪ … ∪ X_{m} and Y_{1} ∪ … ∪ Y_{n} be partitions of X and Y. Let each X_{i} be partitioned further into sets X_{ik} and each Y_{j} into sets Y_{jl}. Then the mean-square density of G with respect to the partitions {X_{ik}} and {Y_{jl}} is at least the mean-square density of G with respect to the partitions {X_{i}} and {Y_{j}}.

Proof. Let U be the set X × Y and let f be the characteristic function of G. Then the result follows from Lemma 7.2 if we take as our cruder partition of U all sets of the form X_{i} × Y_{j} and as our finer one all sets of the form X_{ik} × Y_{jl}, since the quantities compared in that lemma are the mean-square densities of G with respect to the two sets of partitions. □

Lemma 7.4. Let G be a bipartite graph of density d with vertex sets X and Y of sizes M and N, and suppose that G fails to be ϵ-quasirandom. Then there are partitions X = X_{1} ∪ X_{2} and Y = Y_{1} ∪ Y_{2} of the vertex sets that have mean-square density at least d^{2} + ϵ^{2}/16.

Proof. Let f(x, y) = G(x, y)−d. The proof of Theorem 3.1 provides us with subsets X_{1} ⊂ X and Y_{1} ⊂ Y such that |∑_{x∈X_{1}} ∑_{y∈Y_{1}} f(x, y)| ⩾ ϵMN/4. Let us write ϕ(X_{i}, Y_{j}) for the “density” of f when restricted to X_{i} × Y_{j}, that is, for |X_{i}|^{−1}|Y_{j}|^{−1} ∑_{x∈X_{i}} ∑_{y∈Y_{j}} f(x, y). Then the mean-square density of the partitions is

∑_{i,j=1}^{2} α_{i}β_{j}(d + ϕ(X_{i}, Y_{j}))^{2} = ∑_{i,j=1}^{2} α_{i}β_{j}(d^{2} + 2dϕ(X_{i}, Y_{j}) + ϕ(X_{i}, Y_{j})^{2}) .

The first term adds up to d^{2}. The second adds up to zero, since the average of f is zero. The third adds up to at least α_{1}β_{1}(α_{1}M)^{−2}(β_{1}N)^{−2}(ϵMN/4)^{2}, which is at least ϵ^{2}/16. □

Lemma 7.5. Let G be a bipartite graph with vertex sets X and Y of sizes M and N respectively. Let X_{1} ∪…∪X_{m} and Y_{1} ∪…∪Y_{n} be partitions of X and Y, with |X_{i}| = α_{i}M and Y_{j} = β_{j}N. Suppose that the mean-square density of these partitions is d^{2}. Let B be the set of all pairs (i, j) such that the subgraph G(X_{i}, Y_{j}) fails to be ϵ-quasirandom, and suppose that ∑_{(i,j)∈B} α_{i}β_{j} > ϵ. Then one can find partitions X_{i} = X_{i1} ∪ … ∪ X_{is} and Y_{j} = Y_{j1} ∪ … ∪ Y_{jt} such that the refined partitions {X_{ik}} and {Y_{jl}} have mean-square density at least d^{2} + ϵ^{3}/16. Moreover, s and t are uniformly bounded above by 2^{n} and 2^{m} respectively.

Proof. For every pair (X_{i}, Y_{j}) that fails to be ϵ-quasirandom Lemma 7.4 provides us with partitions X_{i} = X_{i1}^{(j)} ∪ X_{i2}^{(j)} and Y_{j} = Y_{j1}^{(i)} ∪ Y_{j2}^{(i)} of mean-square density at least d(X_{i}, Y_{j})^{2} + ϵ^{2}/16. For each i let X_{i} = X_{i1} ∪ … ∪ X_{is} be a partition with s ⩽ 2^{n} that simultaneously refines all the partitions X_{i1}^{(j)} ∪ X_{i2}^{(j)}, and for each j let Y_{j} = Y_{j1} ∪ … ∪ Y_{jt} be a partition with t ⩽ 2^{m} that simultaneously refines all the partitions Y_{j} = Y_{j1}^{(i)} ∪ Y_{j2}^{(i)}.

For each (i, j) ∈ B, Lemma 7.3 implies that the mean-square density of G with respect to the partitions X_{i1} ∪ … ∪ X_{is} and Y_{j1} ∪ … ∪ Y_{jt} is at least d(X_{i}, Y_{j})^{2} + ϵ^{2}/16. For every other (i, j), Lemma 7.3 implies that it is at least d(X_{i}, Y_{j})^{2}. Multiplying by α_{i}β_{j} and summing over all i, j tells us that the mean-square density of the partitions {X_{ik}} and {Y_{jl}} is at least

∑_{(i,j)∉B} α_{i}β_{j}d(X_{i}, Y_{j})^{2} + ∑_{(i,j)∈B} α_{i}β_{j}(d(X_{i}, X_{j})^{2} + ϵ^{2}/16) ,

which is at least d^{2} + ϵ^{3}/16, by our hypothesis on the size of B. □

The next result is our non-standard statement of Szemerédi’s regularity lemma.

Theorem 7.6. Let ϵ > 0 and let G be any bipartite graph with vertex sets X and Y. Then there are partitions X = X_{1} ∪ … ∪ X_{m} and Y = Y_{1} ∪ … ∪ Y_{n} with m and n bounded above by functions of ϵ, with the following property. Let B be the set of all pairs (i, j) such that the subgraph G(X_{i}, Y_{j}) fails to be ϵ-quasirandom. Then ∑_{(i,j)∈B} α_{i}β_{j} ⩽ ϵ. Equivalently, the probability that a random pair (x, y) ∈ X × Y belongs to an X_{i} × Y_{j} for which G(X_{i}, Y_{j}) fails to be ϵ-quasirandom is at most ϵ.

Proof. If G itself is ϵ-quasirandom then we are done. Otherwise, let d be the density of G. Then Lemma 7.4 gives us partitions X = X_{1} ∪ X_{2} and Y = Y_{1} ∪ Y_{2} of mean-square density at least d^{2} + ϵ^{3}/16. In general, given any pair of partitions X = X_{1} ∪ … ∪ X_{m} and Y = Y_{1} ∪ … ∪ Y_{n}, either ∑_{(i,j)∈B} α_{i}β_{j} ⩽ ϵ and we are done (where B is defined as in the statement of the theorem) or we can find refinements for which the mean-square density is greater by at least ϵ^{3}/16. This allows us to construct a sequence of partitions of ever-increasing mean-square density, each refining the one before. Since mean-square density is bounded above by 1, this sequence must terminate in at most 16ϵ^{−3} steps, and it terminates at a pair of partitions that satisfy the conclusion of the theorem. By the bound in Lemma 7.5, the number of sets in these partitions is bounded above by a function of ϵ only. (This function is given by a tower of 2s of height proportional to ϵ^{−3}.) □

To end this section, we prove a (known and easy) generalization of Szemerédi’s regularity lemma, which we shall need later.

Lemma 7.7. Let X and Y be sets and let G_{1}, …, G_{r} be bipartite graphs that form a partition of the edges of the complete bipartite graph K(X, Y). Let X_{1}, …, X_{m} and Y_{1}, …, Y_{n} be partitions of X and Y respectively and suppose that the sum of the meansquare densities of all the graphs G_{u} with respect to these partitions is D. Choose an element (x, y) of the set X × Y uniformly at random, and suppose that with probability at least ϵ it lies in some X_{i} × Y_{j} for which not all the graphs G_{u}(X_{i} × Y_{j}) are ϵ-quasirandom. Then one can find partitions X_{i} = X_{i1} ∪ … ∪ X_{is_{i}} and Y_{j} = Y_{j1} ∪ … ∪ Y_{jt_{j}} such that the sum of the mean-square densities of the G_{u} with respect to the refined partitions {X_{ik}} and {Y_{jl}} is at least D + ϵ^{3}/16. Moreover, all the s_{i} are bounded above by 2^{n} and all the t_{j} are bounded above by 2^{m}.

Proof. This is very similar to the proof of Lemma 7.5 so we shall be brisk. Let (i, j) be a pair such that some graph G_{u}(X_{i} × Y_{j}), of density d, say, fails to be ϵ-quasirandom. Then by Lemma 7.4 we can find partitions of X_{i} and Y_{j} into two sets each in such a way that the mean-square density of G_{u}(X_{i} × Y_{j}) with respect to these partition is at least d^{2} + ϵ^{2}/16, and that will be true of any refinements of them, by Corollary 7.3.

Now let us find such partitions for every pair (i, j) for which a suitable u exists. Then each set X_{i} has been partitioned into two in at most n ways and each Y_{j} has been partitioned into two in at most m ways. Let X_{i} = X_{i1} ∪ … ∪ X_{is_{i}} and Y_{j} = Y_{j1} ∪ … ∪ Y_{jt_{j}} be common refinements of these partitions, into at most 2^{n} sets and 2^{m} sets respectively.

For each pair (i, j) for which there was a non-ϵ-quasirandom graph G_{u}(X_{i}, X_{j}) of density d the mean-square density of G_{u}(X_{i}, X_{j}) with respect to the partitions X_{i} = X_{i1} ∪…∪X_{is_{i}} and Y_{j} = Y_{j1} ∪…∪Y_{jt_{j}} is at least d^{2} +ϵ^{2}/3. Since a random pair (x, y) has a probability of at least ϵ of belonging to X_{i} ×X_{j} for such a pair (i, j), a calculation similar to that of Lemma 7.5 shows that the sum of the mean-square densities of all the graphs G_{u} with respect to the partitions {X_{ik}} and {Y_{jl}} is at least D + ϵ^{3}/16, as claimed. □

Theorem 7.8. Let ϵ > 0, let X_{1}, …, X_{k} be finite sets. For each i let X′_{i1}, …, X′_{im_{i}} be a partition of X_{i}, and for each i, j let G_{ij}(1), …, G_{ij}(r_{ij}) be bipartite graphs that form a partition of the complete bipartite graph K(X_{i}, X_{j}). Then for each i one can find a partition X_{i1}, …, X_{in_{i}} of X_{i} that refines the partition X′_{i1}, …, X′_{im_{i}}, and this can be done in such a way that, for every i and j, if a random pair (x, y) is chosen from X_{i} × X_{j}, then with probability at least 1 − ϵ it lies in some set X_{is} × X_{jt} for which all the r_{ij} induced subgraphs G_{ij}(u)(X_{is}, X_{jt}) are ϵ-quasirandom. Moreover, all the n_{i} are bounded above by a function that depends on ϵ, the m_{i} and the r_{ij} only.

Proof. Suppose that we have partitions X_{i1}, …, X_{in_{i}} of each X_{i}, and suppose that for these partitions the conclusion of the theorem is false. Then there exist i and j such that at least ϵ|X_{i}||X_{j}| of the pairs (x, y) ∈ X_{i} × X_{j} lie in sets X_{is} × X_{jt} for which at least one of the graphs G_{ij}(u)(X_{is}, X_{jt}) is not ϵ-quasirandom. By Lemma 7.7 we can refine the partitions X_{i1}, …, X_{in_{i}} and X_{j1}, …, X_{jn_{j}} in such a way that the sum of the mean-square densities of the graphs G_{ij}(u) with respect to the refined partitions is greater by at least ϵ^{3}/16 than it was for the original ones. Moreover, the numbers of sets in the new partitions are bounded above by an exponential function of the numbers in the old ones.

Since the sum of the mean-square densities of the graphs G_{ij}(u) (over all i, j and u) cannot exceed ∑_{i<j} r_{ij}, this procedure must terminate after at most 16ϵ^{−3} ∑_{i<j} r_{ij} steps. At that point we have a partition with the desired properties. If we start the iteration with the partitions given in the first place, then we end up proving the theorem. □

§8. Regularity for 3-uniform hypergraphs.

As ever, the picture for hypergraphs is more complicated. One of the reasons for this we have already met - we shall split our hypergraphs into “stable” subhypergraphs (see the discussion at the end of §5) rather than quasirandom ones, and this forces us to discuss chains (G, H) as well as hypergraphs. We shall find ourselves partitioning not just the vertex sets of H (and G) but also the edge sets of the graphs G, so the statements we prove are rather more elaborate.

A more technical complication, but nevertheless a fundamental one, arises out of the fact that we must consider chains (G, H) for which G is very sparse. This makes it hard to generalize Lemma 7.4 adequately. To see why, let G be an α-quasirandom tripartite graph of density p with vertex sets X, Y and Z, and suppose that p is very small. Let H ⊂ Δ(G) be a hypergraph that fails to be η-quasirandom relative to Δ(G). If α is small enough, then an averaging argument similar to that of Theorem 4.1 allows us to find sets X′ ⊂ X, Y′ ⊂ Y and Z′ ⊂ Z such that the restriction of H to X′ × Y′ × Z′ is of significantly greater density than H itself. (This statement is true both relative to G and, since G is quasirandom, in absolute terms.) Unfortunately, the sets X′, Y′ and Z′ that this argument gives are contained in certain neighbourhoods of vertices of G, and therefore their sizes depend not just on η but on p as well. Therefore, any increase in mean-square density that we can hope to get from the dense hypergraph H(X′, Y′, Z′) will also depend on p.

This matters a lot, because as the iteration proceeds in the hypergraph regularity lemma, we are forced to consider a sequence of graphs G_{i} with rapidly decreasing densities p_{i}, so if the increase in mean-square density at stage i depends on p_{i}, there is no guarantee that the iteration will come to an end.

The solution to this problem is to squeeze a bit more out of the proof of Theorem 4.1. Instead of choosing just one triple (X′, Y′, Z′), we shall choose several, and prove that they are sufficiently spread out to provide us with an increase in mean-square density that is strong enough to use.

The statement of the hypergraph regularity lemma is somewhat complicated, so we shall postpone it until after we have made the above remarks precise in Lemma 8.4 below. At that point, the formulation of the regularity lemma will be better motivated and the rest of the proof quite easy.

To begin with, here is a simple and general criterion that we can use when we are trying to establish that a partition gives us an increase in mean-square density.

Lemma 8.1. Let U be a set of size n and let f and g be functions from U to the interval [−1, 1]. Let B_{1}, …, B_{r} be a partition of U and suppose that g is constant on each B_{i}. Then the mean-square density of f with respect to the partition B_{1}, …, B_{r} is at least ⟨f, g⟩^{2}/n∥g∥_{2}^{2}.

Proof. For each j Let a_{j} be the value taken by g on the set B_{j}. Then, by the Cauchy-Schwarz inequality,

⟨f, g⟩ = ∑_{j} a_{j} ∑_{x∈B_{j}} f(x)

⩽ (∑_{j} |B_{j}|a_{j}^{2})^{1/2}(∑_{j} |B_{j}|^{−1} ∑_{x∈B_{j}} f(x))^{1/2}

= ∥g∥_{2}(∑_{j} |B_{j}|(|B_{j}|^{−1} ∑_{x∈B_{j}} f(x))^{2})^{1/2} .

But ∑_{j} |B_{j}|(|B_{j}|^{−1} ∑_{x∈B_{j}} f(x))^{2} is n times the mean-square density of f (by definition), so the lemma follows. □

So that it does not clutter up the proof of Lemma 8.4, here is a second very simple technical lemma.

Lemma 8.2. Let 0 < δ < 1 and let r be an integer greater than or equal to δ^{−1}. Let v_{1}, …, v_{n} be vectors in ℓ_{2}^{n} such that ∥v_{i}∥^{2} ⩽ n for each i and such that ∥∑ v_{i}∥_{2}^{2} ⩽ δn^{3}. Let r vectors w_{1}, …, w_{r} be chosen uniformly and independently from the v_{i}. (To be precise, for each w_{j} an index i is chosen randomly between 1 and n and w_{j} is set equal to v_{i}.) Then the expectation of ∥∑ w_{j}∥_{2}^{2} is at most 2δr^{2}n.

Proof. The expectation of ∥∑ w_{j}∥_{2}^{2} is the expectation of ∑_{i,j}⟨w_{i}, w_{j}⟩. If i ≠ j then the expectation of ⟨w_{i}, w_{j}⟩ is n^{−2} ∥∑ v_{i}∥_{2}^{2} which, by hypothesis, is at most δn. If i = j, then ⟨w_{i}, w_{j}⟩ is at most n, again by hypothesis. Therefore, the expectation we are trying to bound is at most (δr(r − 1) + r)n. Since δr ⩾ 1, this is at most 2δr^{2}n, as claimed. □

Definition 8.3. Let G be a tripartite graph with vertex sets X, Y and Z and let the bipartite graphs G(X, Y), G(Y, Z) and G(X, Z) be partitioned into subgraphs G_{i}(X, Y), G_{j}(Y, Z) and G_{k}(X, Z) respectively. For each triangle (x, y, z) ∈ Δ(G), define its index to be the triple (i, j, k) such that xy ∈ G_{i}(X, Y), yz ∈ G_{j}(Y, Z) and xz ∈ G_{k}(X, Z). The induced partition of Δ(G) is the partition of the triples of Δ(G) according to their index. If f : X × Y × Z → [−1, 1], then the mean-square density of f relative to the partitions (G_{i}(X, Y)), (G_{j}(Y, Z)) and (G_{k}(X, Z)) is defined to be the mean-square density of f relative to the induced partition of Δ(G).

Note that a typical cell of the induced partition is of the form

Δ(G_{i}(X, Y) ∪ G_{j}(Y, Z) ∪ G_{k}(X, Z)) .

Lemma 8.4. Let G be a tripartite graph with vertex sets X, Y and Z of sizes L, M and N respectively, let the densities G(X, Y), G(Y, Z) and G(X, Z) be δ_{12}, δ_{23} and δ_{13}, let δ = δ_{12}δ_{23}δ_{13} and suppose that these three graphs are α-quasirandom. Let H be a tripartite 3-uniform hypergraph with the same vertex sets as G, let the relative density |H|/|Δ(G)| of H in G be d, and suppose that H is not η-quasirandom relative to Δ(G). Suppose also that 2^{21}α^{1/4} ⩽ δ^{7}. Then there are partitions G_{1}(X, Y) ∪ … ∪ G_{l}(X, Y) = G(X, Y), G_{1}(Y, Z) ∪ … ∪ G_{m}(Y, Z) = G(Y, Z) and G_{1}(X, Z) ∪ … ∪ G_{n}(X, Z) = G(X, Z), relative to which the mean-square density of H is at least d^{2} + 2^{−10}η^{2}. Moreover, l, m and n are all at most 3^{δ^{−4}}.

Proof. Let f(x, y, z) = H(x, y, z) − d whenever (x, y, z) ∈ Δ(G) and let it be zero otherwise. Then the hypothesis of the lemma is that

∑_{x,x′,y,y′,z,z′} f_{x,x′,y,y′,z,z′} ⩾ ηδ^{4}L^{2}M^{2}N^{2} .

Let U = Δ(G) and for each triple (x, y, z) ∈ U define F_{xyz}(x′, y′, z′) to be f_{x,x′,y,y′,z,z′}/f(x′, y′, z′) and let F (x′, y′, z′) = ∑_{x,y,z} G_{xyz}(x′, y′, z′). With this notation, the hypothesis can be rewritten ⟨f, F ⟩ ⩾ ηδ^{4}(LMN)^{2}.

Let us now build some new functions E_{xyz}. These will have similar properties to the F_{xyz} but will take values 0, 1 and −1 only. A vital property of each function F_{xyz} is that it can be written in the form u(x′, y′)v(y′, z′)w(x′, z′), since of the eight terms in the product f_{x,x′,y,y′,z,z′} the only one that depends on all three of x′, y′ and z′ is f(x′, y′, z′), which is absent from F_{xyz}(x′, y′, z′). Moreover, we can do this with u, v and w taking values in the interval [−1, 1].

Fix a triple (x, y, z) as above, and for each pair (x′, y′) define u′(x, y) randomly according to the following simple rule. If u(x′, y′) is positive then u′(x′, y′) is 1 with probability u(x′, y′) and 0 otherwise. If u(x′, y′) is negative then u′(x′, y′) is -1 with probability |u(x′, y′)| and 0 otherwise. If u(x′, y′) = 0 then u′(x′, y′) = 0 as well. Construct functions v′ and w′ similarly, and let all the random choices that have been made be independent. Finally, let E_{xyz}(x′, y′, z′) = u′(x′, y′)v′(y′, z′)w′(x′, z′), and note that the expectation of E_{xyz}(x′, y′, z′) is F_{xyz}(x′, y′, z′).

Let E be the sum of all the functions E_{xyz}. The expectations of ⟨f, F_{xyz}⟩ and ⟨f, E_{xyz}⟩ are the same, so we can make the random choices in such a way that ⟨f, E⟩ ⩾ ηδ^{4}(LMN)^{2}. The other property we shall use is that E_{xyz}(x′, y′, z′) is non-zero only if x, x′, y, y′, z and z′ are the vertices of an octahedron in the graph G. (This is true despite the fact that we have divided by f(x′, y′, z′): for each pair there is still a triple containing it for which f is required to be non-zero.) So that our notation will be reasonably concise, Let us set G_{x,x′,y,y′,z,z′} to be 1 if x, x′, y, y′, z and z′ are the vertices of an octahedron and 0 otherwise. (Strictly speaking, it would be more accurate to write Δ(G)_{x,x′,y,y′,z,z′}.)

Our next aim is to obtain an upper bound for ∥E∥_{2}^{2}. To start with, we have

∥E∥_{2}^{2} = ∑_{x′,y′,z′}( ∑_{x,y,z} E_{xyz}(x′, y′, z′))^{2}

⩽ ∑_{x′,y′,z′}( ∑_{x,y,z} G_{x,x′,y,y′,z,z′})^{2}

= ∑_{x′,y′,z′} ∑_{x_{1},y_{1},z_{1},x_{2},y_{2},z_{2}} G_{x_{1},x′,y_{1},y′,z_{1},z′}G_{x_{2},x′,y_{2},y′,z_{2},z′}

This counts the number of 9-tuples (x′, y′, z′, x_{1}, y_{1}, z_{1}, x_{2}, y_{2}, z_{2}) such that the sextuples (x′, x_{1}, y′, y_{1}, z′, z_{1}) and (x′, x_{2}, y′, y_{2}, z′, z_{2}) both form octahedra in G. That is, it counts the number of copies in G of a certain graph with nine vertices and seven edges between each pair of vertex sets (four for each octahedron but intersecting in one). By Theorem 3.5 and our upper bound for α, there are at most 2δ^{7}(LMN)^{3} of these.

We are not yet in a position to apply Lemma 8.1: E is the sum of |U| functions E_{xyz} and we are unlikely to find a partition into just a few sets on which it is constant. The next stage of the argument is to make a random selection of a small number of E_{xyz} in such a way that their sum preserves the good properties of E. Let r ⩾ δ^{−4}, choose E_{1}, …, E_{r} randomly from the E_{xyz} and let D = ∑_{i=1}^{r} E_{i}. Since the expectation of ⟨f, E_{i}⟩ is |U|^{−1}⟨f, E⟩ and we know that ⟨f, E⟩ ⩾ ηδ^{4}(LMN)^{2}, the expectation of ⟨f, D⟩ is at least ηδ^{4}r|U|^{−1}(LMN)^{2}. By Theorem 3.5 and our upper bound for α, we know that |U| lies between δLMN/2 and 2δLMN, so this is at least ηrδ^{2}|U|/4.

We shall now apply Lemma 8.2, with n = |U|, to the functions E_{xyz}. We have shown that ∥E∥_{2}^{2} ⩽ 2δ^{7}(LMN)^{3}, which is at most 16δ^{4}|U|^{3}. Moreover, each E_{xyz} is supported in U and takes values in [−1, 1], so ∥E_{xyz}∥_{2}^{2} is at most |U|. Therefore, Lemma 8.2 implies that the expectation of ∥D∥_{2}^{2} is at most 32δ^{4}r^{2}|U|. Therefore, the expectation of 256δ^{2}r⟨f, D⟩ − ηδ∥D∥_{2}^{2} is at least 64ηδ^{4}r^{2}|U|. From this it follows that we can choose D in such a way that ⟨f, D⟩ ⩾ ηδ^{2}r|U|/4 and ∥D∥_{2}^{2} ⩽ 256δ^{2}r⟨f, D⟩η^{−1}. For such a D, we have

\frac{⟨f, D⟩}{∥D∥_{2}^{2}} ⩾ \frac{⟨f, D⟩}{256δ^{2}rη^{−1}} ⩾ \frac{ηδ^{2}r|U|}{2^{10}δ^{2}rη^{−1}} = \frac{η^{2}|U|}{2^{10}} .

We finish the proof by applying Lemma 8.1 to a suitable partition of U = Δ(G). Each of the r functions E_{xyz} that we added up to make D is of the form u′(x′, y′)v′(y′, z′)w′(x′, z′), where u′, v′ and w′ take values in the set {−1, 0, 1}. We can partition the bipartite graph G(X, Y) into at most 3^{r} subgraphs G_{i}(X, Y) such that every u′ is constant on each G_{i}(X, Y). In a similar way we can partition G(Y, Z) into subgraphs G_{j}(Y, Z) and G(X, Z) into subgraphs G_{k}(X, Z). For each triangle (x, y, z) ∈ Δ(G), define its index to be the triple (i, j, k) such that xy ∈ G_{i}(X, Y), yz ∈ G_{j}(Y, Z) and xz ∈ G_{k}(X, Z). Then partition Δ(G) into triples according to their index. This partition has at most 3^{3r} cells, each of the form Δ(G_{i}(X, Y) ∪ G_{j}(Y, Z) ∪ G_{k}(X, Z)).

The function D is constant on each cell, so Lemma 8.1 and our estimate for ⟨f, D⟩/∥D∥_{2}^{2} imply that the mean-square density of f with respect to this partition is at least 2^{−10}η^{2}. It follows that the mean-square density of H is at least d^{2} +2^{−10}η^{2}, which proves the lemma. □

Now let us prepare for the statement of our regularity lemma for 3-uniform hypergraphs. As with the counting lemma, we will keep things simple by restricting to the case of quadripartite hypergraphs, but the result can easily be generalized. The idea will be to take a quadripartite 3-uniform hypergraph H and “decompose it into quasirandom chains”. Before we say exactly what this means, let us try to motivate the slightly technical definition we shall give in a moment of a quasirandom chain.

What we ultimately want from a chain is that it should satisfy the conditions for Theorem 6.8, the counting lemma for chains that we proved earlier. There we had a quadripartite graph G with vertex sets of sizes L, M, N and P and a quadripartite 3uniform hypergraph H ⊂ Δ(G). Writing δ for the product of the densities of the six bipartite parts of G, the assumptions of the theorem were that each tripartite part of H was η-quasirandom relative to G, each bipartite part of G was α-quasirandom and 2^{36}α^{1/16} ⩽ ηδ^{8}/6. Writing γ for the product of the relative densities of the four tripartite parts of H, the conclusion was that the number of simplices in H differed from γδLMNP by at most 8η^{1/8}δLMNP. We therefore consider this to be a small error if η^{1/8} is small compared with γ.

Definition 8.5. Let ψ(η, δ) be a polynomial in η and δ that vanishes when either η or δ is zero. A quadripartite chain (G, H) with δ defined as above is (η, ψ)-quasirandom if all six parts of G are ψ(η, δ)-quasirandom and all four parts of H are η-quasirandom relative to G.

Later we shall use this definition in the case where ψ(η, δ) = (2^{−40}ηδ^{8})^{16}. Then, if α = ψ(η, δ) it will satisfy the condition 2^{36}α^{1/16} ⩽ ηδ^{8}/6 discussed above.

In Szemerédi’s regularity lemma one decomposes a graph into quasirandom pieces using partitions of its vertex sets. As we have already mentioned, the decompositions we shall consider of hypergraphs are more complicated, so let us say precisely what they are. We shall use the following notation for this purpose and throughout the rest of the paper. If G is a quadripartite graph, X and Y are two of its vertex sets and X′ ⊂ X and Y′ ⊂ Y, then G(X′, Y′) stands for the induced bipartite subgraph of G with vertex sets X′ and Y′. Similarly, if H is a quadripartite 3-uniform hypergraph and X′, Y′ and Z′ are subsets of three of its vertex sets then H(X′, Y′, Z′) stands for the induced tripartite subhypergraph with vertex sets X′, Y′ and Z′. The complete k-partite graph with vertex sets X_{1}, …, X_{k} will be denoted K(X_{1}, …, X_{k}).

Definition 8.6. Let X_{1}, X_{2}, X_{3} and X_{4} be four sets. A decomposition of the complete quadripartite graph K(X_{1}, X_{2}, X_{3}, X_{4}) consists of the following:

(a) for each vertex set X_{i} a partition into subsets X_{i1}, …, X_{in_{i}};

(b) for each bipartite graph K(X_{i}, X_{j}) a partition into subgraphs G_{ij}(1), …, G_{ij}(m_{ij}).

Such a decomposition provides us with a collection of tripartite graphs. A typical one of these graphs has vertex sets of the form X_{ir}, X_{js} and X_{kt}, and an edge set of the form

G_{ij}(u)(X_{ir}, X_{js}) ∪ G_{jk}(v)(X_{js}, X_{kt}) ∪ G_{ik}(w)(X_{ir}, X_{kt}) .

If H is a quadripartite 3-uniform hypergraph with vertex sets X_{1}, X_{2}, X_{3} and X_{4}, then the decomposition also provides us with a collection of tripartite hypergraphs. A typical one of these has vertex sets as above and edge set H ∩ Δ(G), where G is one of the tripartite graphs of the form the collection just defined. The pair (G, H) will then be a chain.

Definition 8.7. Let H be a quadripartite 3-uniform hypergraph with vertex sets X_{1}, …, X_{4} and suppose that we have a decomposition of K(X_{1}, X_{2}, X_{3}, X_{4}). Then the associated chain decomposition of H is the set of all chains formed in the way explained above.

Every triple (x, y, z) ∈ (X_{i}, X_{j}, X_{k}) belongs to exactly one of the tripartite graphs defined above, and hence we can associate with it exactly one of the chains. Hence, to each (x, y, z, w) we can associate four chains, one for each triple.

Definition 8.8. Let H be as above. Then H(X_{i}, X_{j}, X_{k}) is (ϵ, η, ψ)-quasirandom if for all but ϵ|X_{i}||X_{j}||X_{k}| of its edges (x, y, z) the associated tripartite chain is (η, ψ)-quasirandom. H itself is (ϵ, η, ψ)-quasirandom if all its four parts are.

Just before we prove the regularity lemma, here is a generalization of Corollary 7.3 that we will need in the proof.

Lemma 8.9. Let G be a tripartite graph with vertex sets X, Y and Z, let H be a tripartite 3-uniform hypergraph with the same vertex sets, and let d be the relative density |H ∩ Δ(G)|/|Δ(G)| of H in Δ(G). Let E_{1} ∪ … ∪ E_{l}, F_{1} ∪ … ∪ F_{m} and G_{1} ∪ … ∪ G_{n} be partitions of G(X, Y), G(Y, Z) and G(X, Z) respectively. Let each E_{i}, F_{j} and G_{k} be partitioned further into sets E_{ir}, F_{js} and G_{kt}. Then the mean-square density of H relative to the partitions {E_{ir}}, {F_{js}} and {G_{kt}} is at least as big as the mean-square density of H relative to {E_{i}}, {F_{j}} and {G_{k}}.

Proof. Like Corollary 7.3, this result is an immediate consequence of Lemma 7.2. This time, let U = Δ(G) and let f be the characteristic function of H. The partition of U induced by the partitions {E_{ir}}, {F_{js}} and {G_{kt}} is a refinement of the partition induced by the partitions {E_{i}}, {F_{j}} and {G_{k}}, and again the quantities compared in Lemma 7.2 are the mean-square densities we wish to compare here. □

We are now ready for the main result of this section.

Theorem 8.10. Let H be a quadripartite hypergraph with vertex sets X, Y, Z and W, and let ϵ, η > 0. Let the densities of H(X, Y, Z), H(X, Y, W), H(X, Z, W) and H(Y, Z, W) be δ_{123}, δ_{124}, δ_{134} and δ_{234} respectively . Then there is a decomposition of the complete quadripartite graph K(X, Y, Z, W) such that the associated chain decomposition of H is (ϵ, η, ψ)-quasirandom. Moreover, the number of bipartite graphs in the decomposition is bounded above by a number that depends only on ϵ and η, while the number of sets in the partitions of X, Y, Z and W is bounded above by a function of ϵ, η, ψ and the densities δ_{123}, δ_{124}, δ_{134} and δ_{234}.

Proof. Suppose that we have a decomposition of the vertices and edges of K(X, Y, Z, W), with each vertex set partitioned into at most n sets and each complete bipartite graph formed from two of the vertex sets partitioned into at most m bipartite subgraphs.

Let α = ψ(η, ϵ/48m). By Theorem 7.8 we can refine the partitions of X, Y, Z and W so that if a random quadruple (x, y, z, w) is chosen from X × Y × Z × W, then, with probability at least 1 − α, xy lies in a product X_{i} × Y_{j} of cells such that all the induced subgraphs G(X_{i}, Y_{j}), where G is a graph from the decomposition of K(X, Y), are α-quasirandom, and similarly for the other five pairs from (x, y, z, w). Suppose that we have passed to such a refinement. Then each vertex set is now partitioned into at most N sets, where N depends on ϵ, m and n only.

We do not want to consider chains that are too sparse, so let us show that these do not occur very often. To any quadruple (x, y, z, w) ∈ X ×Y ×Z ×W there is an associated quadripartite chain. Let its vertex sets be A_{1}, A_{2}, A_{3} and A_{4} and let its edge-sets be G_{ij} for 1 ⩽ i < j ⩽ 4. Here, A_{4} is the cell that contains w from the partition of W, G_{23} is the bipartite graph from the decomposition that contains the edge yz, and so on. The graphs G_{ij} form the edges of the quadripartite chain. The hyperedges come from the union of the four tripartite hypergraphs

H ∩ Δ(G_{ij}(A_{i}, A_{j}) ∪ G_{jk}(A_{j}, A_{k}) ∪ G_{ik}(A_{i}, A_{k})) ,

where 1 ⩽ i < j < k ⩽ 4.

Suppose we choose (x, y, z, w) at random. Then there are at most m possibilities for each G_{ij}. It follows that if we condition on the set A_{1} × A_{2} × A_{3} × A_{4} in which (x, y, z, w) lies, then for each ij the probability that G_{ij} has density less than ϵ/48m in A_{i} × A_{j} is at most ϵ/48. Therefore, with probability at least 1 − ϵ/8, each G_{ij} has density at least ϵ/48m in A_{i} × A_{j}.

Suppose that the chain decomposition we now have of H is not (ϵ, η, ψ)-quasirandom. Then, without loss of generality, for at least ϵ|X||Y ||Z|/4 edges of H(X, Y, Z) the associated chain is not (η, ψ)-quasirandom. It follows that there are at least ϵ|X||Y ||Z|/8 edges (x, y, z) of H(X, Y, Z) such that the density conditions above are satisfied for the associated chains, and such that either H(X, Y, Z) is not η-quasirandom relative to the associated tripartite graph or the three parts of the tripartite graph are not all α-quasirandom.

However, we have arranged for the second possibility to apply to at most α|X||Y ||Z| triples, so there are at least ϵ|X||Y ||Z|/16 edges such that H(X, Y, Z) is not η-quasirandom relative to the associated tripartite graph.

Whenever this happens we can use Lemma 8.4 to partition the three bipartite parts of the graph in such a way that the mean-square density of H relative to these partitions is greater by at least 2^{−10}η than the square of the density of H relative to the tripartite graph. Moreover, by Lemma 8.9 this property is maintained if we refine these partitions. Hence, we can choose a common refinement of all the partitions of all the bipartite parts of all the graphs, preserving all the mean-square density increases. Since at least ϵ|X||Y ||Z|/16 triples belong to tripartite graphs where such increases have taken place, we find that the mean-square density of H relative to the new decomposition is at least 2^{−14}ϵη greater than it was relative to the old one. The number of bipartite graphs in the new partitions is bounded above by a function of ϵ, η and m only.

This procedure can be iterated. When we refine the partitions of the vertex sets, the mean-square density of H relative to the decomposition does not decrease, so the iteration must eventually come to an end and the theorem is proved. □

Remark. An examination of the above proof shows that the bound for the numbers of cells in the eventual partition is of “wowzer” type. The wowzer function W is defined in two steps as follows. First let the tower function T be defined by T (1) = 2, T (n) = 2^{n−1}. Next, let W (1) = 2 and W (n) = T (W (n − 1)). In general, the hypergraph regularity lemma for k-uniform hypergraphs iterates the bound for (k − 1)-uniform hypergraphs, and thus advances one level in the Ackermann hierarchy. This means that the bounds that it gives for the theorems of van der Waerden and Szemerédi are of Ackermann type. Similar bounds have recently been achieved for Szemerédi’s theorem by Tao, who has produced a discretization of Furstenberg’s ergodic-theory proof. This answered a question that many people had asked, and the insights gained played an important role in his spectacular result with Green that the primes contain arbitrarily long arithmetic progressions.

We finish the section with a corollary that is designed to make the regularity lemma easy and convenient to use. As with our earlier results, the result we give is not the most general possible, but more general versions can be proved with only small adaptations.

Let H be a quadripartite 3-uniform hypergraph with vertex sets X_{1}, X_{2}, X_{3} and X_{4}, and for each i let the size of X_{i} be N_{i}. Suppose that for each i we have a subset A_{i} ⊂ X_{i} of size δ_{i}|X_{i}| and that G is a quadripartite graph with vertex sets A_{1}, A_{2}, A_{3} and A_{4}. For each pair i < j let δ_{ij} be the density |G(A_{i}, A_{j})|/|A_{i}||A_{j}| and for each i < j < k let δ_{ijk} be the relative density of H inside Δ(G(A_{i}, A_{j}) ∪ G(A_{j}, A_{k}) ∪ G(A_{i}, A_{k})). Let us call the product of the densities δ_{i}, δ_{ij} and δ_{ijk} the expected simplex density of H in G.

Corollary 8.11. Let ϵ > 0, let H be a quadripartite graph with vertex sets X_{1}, X_{2}, X_{3} and X_{4}, and for each i let the size of X_{i} be N_{i}. Then for each triple 1 ⩽ i < j < k ⩽ 4 one can remove at most ϵ|H(X_{i}, X_{j}, X_{k})| edges of H(X_{i}, X_{j}, X_{k}), and one can find a decomposition of the complete quadripartite graph K = K(X_{1}, X_{2}, X_{3}, X_{4}), with the following property. Let each X_{i} be partitioned into at most n parts and let the number of bipartite graphs in any of the six parts of K be m. Let H′ equal H after the edges have been removed and let G be any quadripartite graph arising from the decomposition with vertex sets A_{i}. Let σ be the expected simplex density of H′ in G. Then either σ = 0 or σ ⩾ (ϵ/8n)^{4}(ϵ/48m)^{6}(ϵ/8)^{4} and the number of simplices in the hypergraph H′ ∩ Δ(G) differs from σN_{1}N_{2}N_{3}N_{4} by at most ϵσN_{1}N_{2}N_{3}N_{4}.

Proof. Let γ be (ϵ/8)^{3}, let η = (ϵγ/16)^{8} and for any δ > 0 let ψ(η, δ) = 2^{−40}ηδ^{8})^{16}. Using Theorem 8.10, let us take a decomposition of the graph K = K(X_{1}, X_{2}, X_{3}, X_{4}) such that the associated chain decomposition of H is (ϵ/2, η, ψ)-quasirandom, and let m be the maximum number of bipartite graphs in any of the six parts of K. For each i < j < k we shall remove at most ϵ|X_{i}||X_{j}||X_{k}| edges of H, using the conclusion of Theorem 8.10 and simple averaging arguments. The result will be a subhypergraph H′ such that each edge (x_{i}, x_{j}, x_{k}) has several good properties. To describe these properties, let us take an arbitrary such edge, let A_{i} ⊂ X_{i}, A_{j} ⊂ X_{j} and A_{k} ⊂ X_{k} be the vertex sets from the decomposition that contain x_{i}, x_{j} and x_{k} respectively and let G_{ij}, G_{jk} let G_{ik} be the bipartite graphs containing x_{i}x_{j}, x_{j}x_{k} and x_{i}x_{k}. The properties are then as follows.

(i) The densities of A_{i}, A_{j} and A_{k} inside X_{i}, X_{j} and X_{k} are all at least ϵ/24n. (ii) The densities of G_{ij}, G_{jk} and G_{ik} inside K(A_{i}, A_{j}), K(A_{j}, A_{k}) and K(A_{i}, A_{k})

are all at least ϵ/48m. (iii) The relative density of H′ inside the tripartite graph

G = G_{ij}(A_{i}, A_{j}) ∪ G_{jk}(A_{j}, A_{k}) ∪ G_{ik}(A_{i}, A_{k})

is at least ϵ/8. (iv) The chain (G, H′ ∩ Δ(G)) is (ϵ/2, η, ψ)-quasirandom.

Now let us see how we can get these properties.

(i) Since X_{i} is partitioned into at most n sets A_{i}, the number of vertices that belong to an A_{i} of density less than e/24n is at most ϵ|X_{i}|/24. Therefore, the number of triples (x_{i}, x_{j}, x_{k}) in X_{i} × X_{j} × X_{k} such that at least one of A_{i}, A_{j} and A_{k} has density less than ϵ/24n is at most ϵ|X_{i}||X_{j}|X_{k}|/8.

(ii) This is obtained by an argument similar to that for (i). In fact, we gave the argument as part of the proof of Theorem 8.10, which implies that the number of triples (x_{i}, x_{j}, x_{k}) in X_{i} × X_{j} × X_{k} for which this density condition fails is again at most ϵ|X_{i}||X_{j}|X_{k}|/8.

(iii) Since K(X_{i}, X_{j}, X_{k}) is partitioned into sets Δ(G), where G is a tripartite graph of the given form, at most ϵ|X_{i}||X_{j}|X_{k}|/8 edges of H(X_{i}, X_{j}, X_{k}) can live in a Δ(G) where the relative density of H is less than ϵ/8.

(iv) The conclusion of Theorem 8.10 (with ϵ replaced by ϵ/2) and Definition 8.8 together tell us that this is true for all but at most ϵ|X_{i}||X_{j}|X_{k}|/2 edges of H(X_{i}, X_{j}, X_{k}).

It follows that we may remove at most ϵ|X_{i}||X_{j}|X_{k}| from each part H(X_{i}, X_{j}, X_{k}) of H and obtain a hypergraph H′ such that properties (i), (ii), (iii) and (iv) hold for every single edge of H′.

We now apply Theorem 6.8. Let G be any quadripartite graph arising from the decomposition, let its vertex sets be A_{1}, A_{2}, A_{3} and A_{4} and let δ be the product of the densities of its edge sets. If all four hypergraphs of the form Δ(G(A_{i}, A_{j}, A_{k})) contain edges of H′ then the densities of all the G(A_{i}, A_{j}) inside K(A_{i}, A_{j}) are at least ϵ/48m, the relative density of H′ inside each G(A_{i}, A_{j}) ∪ G(A_{j}, A_{k}) ∪ G(A_{i}, A_{k}) is at least ϵ/8 and H′ is (ϵ/2, η, ψ)-quasirandom there. By our choices of η, ψ and the lower bounds for the densities, this means that the conditions for Theorem 6.8 are satisfied and we may conclude that the number of simplices in H ∩ Δ(G) differs from σN_{1}N_{2}N_{3}N_{4} by at most 8η^{1/8}δN_{1}N_{2}N_{3}N_{4}. By our choice of η, this is at most ϵσN_{1}N_{2}N_{3}N_{4}. □

§9. Szemerédi’s theorem for progressions of length 4.

It is now straightforward to generalize the proof of Theorem 1.1 to give a proof of Theorem 1.4. Let us modify the statement a little bit so that it fits better with the statements of the last section.

Theorem 9.1. For every a > 0 there exists c > 0 with the following property. Let H be any quadripartite hypergraph H with vertex sets X_{1}, X_{2}, X_{3} and X_{4} of sizes N_{1}, N_{2}, N_{3} and N_{4} respectively, and suppose that the number of simplices in H is at most cN_{1}N_{2}N_{3}N_{4}. Then it is possible to remove at most aN_{i}N_{j}N_{k} triples from each of the four induced subhypergraphs H(X_{i}, X_{j}, X_{k}) in such a way that the resulting subhypergraph of H is simplex-free.

Proof. Apply Corollary 8.11 with ϵ = a and suppose that the resulting hypergraph H′ contains a simplex with vertices x_{1}, x_{2}, x_{3} and x_{4}. Let G be the associated quadripartite graph coming from the decomposition. Then each tripartite part of G contains an edge of H′, so the expected simplex density σ of H in G is non-zero. Corollary 8.11 tells us that it is therefore at least (1 − a)(a/8n)^{4}(a/48m)^{6}(a/8)^{4}. If c is less than this, then we have obtained a contradiction, which shows that H′ could not after all have contained a simplex. Since the numbers m and n depend on ϵ only, the theorem is proved. □

To conclude, let us deduce Szemerédi’s theorem for progressions of length four. First we prove a tiny weakening of Theorem 1.5. (The difference is that we prove that d ≠ 0 rather than that d > 0. Ben Green’s trick mentioned in the proof of Corollary 1.2 works here as well, but Szemerédi’s theorem does not need the positivity of d.)

Theorem 9.2. For every δ > 0 there exists N such that every subset A ⊂ [N]^{3} of size at least δN^{3} contains a quadruple of points of the form

{(x, y, z), (x + d, y, z), (x, y + d, z), (x, y, z + d)}

with d ≠ 0.

Proof. Define a quadripartite hypergraph with vertex sets X = Y = Z = [N] and W = [3N] as follows. A triple (x, y, z) ∈ X ×Y ×Z belongs to H if and only if (x, y, z) ∈ A. A triple (x, y, w) ∈ X × Y × W belongs to H if and only if (x, y, w − x − y) ∈ A, and similarly for triples (x, z, w) and (y, z, w).

Suppose now that H contains a simplex (x, y, z, w) and let d = w − x − y − z. Then the points (x, y, z), (x, y, z + d), (x, y + d, z) and (x + d, y, z) all belong to A. This proves the theorem unless d is always 0. But in that case, there are at most N^{3} simplices in H: in fact, there are exactly |A| of them. Now we apply Theorem 9.1 with a = δ/20. It gives us a c > 0 such that, if H contains at most cN^{4} simplices, then we can remove at most aN^{3} edges from each part of H and remove all of them. Since our hypergraph contains at most N^{3} simplices, if N^{−1} < c we may apply the theorem. However, the number of simplices with d = 0 is δN^{3}, and no two of these share a face, since a simplex with d = 0 is uniquely determined by any one of its four faces. Therefore, if we remove at most a proportion a of the faces from each of the four parts of H, we end up removing at most 10aN^{3} = δN^{3}/2 simplices, which is not all of them. (The number 10 comes from the fact that |W | = 3N.) That is a contradiction, and the theorem is proved. □

Corollary 9.3. For every δ > 0 there exists N such that every subset A ⊂ [N] of size at least δN contains an arithmetic progression of length four.

Proof. Define a subset B ⊂ [N]^{3} to consist of all triples (x, y, z) such that x+2y+3z ∈ A. It is a straightforward exercise to show that B has density bounded below by a function of δ, so Theorem 9.3 yields the arithmetic progression

x + 2y + 3z, (x + d) + 2y + 3z, x + 2(y + d) + 3z, x + 2y + 3(z + d) .  □

§10. Concluding Remarks.

The technical details in the papers of Rödl and his coauthors are very different from those here and it is possible and instructive to pinpoint where the difference arises. The answer is that the two approaches use different notions of quasirandomness that are equivalent for graphs and dense hypergraphs but not equivalent for the sparse hypergraphs we are forced to consider here.

Briefly, whereas in this paper we have focused on “octahedral quasirandomness”, they concentrate their attention on edge-uniformity (see Definition 2.6). These two definitions are not equivalent for chains (G, H), because, as we noted at the beginning of Section 8, if G is sparse, then the failure of H to be relatively quasirandom does not imply that there is a significant increase in mean-square density.

This presented us with a technical problem (dealt with in Lemma 8.4) that does not arise if one uses edge-uniformity instead: that property is weaker, so its denial has stronger consequences. However, one pays the price for this weakness when proving a counting lemma. (In fact, this is an oversimplification: edge-uniformity does not seem to be enough on its own, but a more complicated variant of it can be used instead, more complicated in a way that is rather similar to the way that Lemma 8.4 is more complicated than Lemma 7.4.) Octahedral quasirandomness appears to be exactly the right concept for proving a counting lemma in an analytic style modelled on arguments that have already been used for proving Szemerédi’s theorem; edge-uniformity is the concept one naturally comes up with if one wishes to model one’s arguments on the usual proof of Szemerédi’s regularity lemma. It is just a pity that one cannot use both!

Thus, even though the two approaches share many features, in that they both prove regularity and counting lemmas for chains, they are also genuinely different: for Rödl and his coauthors the counting lemma is harder than the regularity lemma, whereas for us it is the other way round.

References.

[CG1] F. R. K. Chung and R. L. Graham, Quasi-random hypergraphs, Random Structures Algorithms 1 (1990), 105–124.

[CG2] F.R.K. Chung, R.L. Graham, Quasi-random subsets of ℤ_{n}, J. Comb. Th. A 61 (1992), 64–86.

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

[FKO] H. Furstenberg, Y. Katznelson, D. Ornstein, The ergodic theoretical proof of Szemerédi’s theorem, Bull. Amer. Math. Soc. 7 (1982), 527–552.

[FR1] P. Frankl and V. Rödl, The uniformity lemma for hypergraphs, Graphs Combin. 8 (1992), 309-312.

[FR2] P. Frankl and V. Rödl, Extremal problems on set systems, Random Structures and Algorithms 20 (2002), 131-164.

[FK] H. Furstenberg and Y. Katznelson, An ergodic Szemerédi theorem for commuting transformations, J. Analyse Math. 34 (1978), 275-291.

[G1] W. T. Gowers, A new proof of Szemerédi’s theorem for arithmetic progressions of length four, Geom. Funct. Anal. 8 (1998), 529-551.

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

[G3] W. T. Gowers, Hypergraph regularity and Szemerédi’s theorem, preprint.

[NRS] B. Nagle, V. Rödl and M. Schacht, The counting lemma for regular k-uniform hypergraphs, Random Structures and Algorithms (to appear).

[RS] I. Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, 939-945.

[S1] J. Solymosi, Note on a generalization of Roth’s theorem, Discrete and Computational Geometry, 825-827, Algorithms Combin. 25, Springer, Berlin 2003.

[S2] J. Solymosi, A note on a question of Erdős and Graham, Combin. Probab. Comput. 13 (2004), 263-267.

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

Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cambridge CB3 0WB, UK.