Hypergraph Regularity and the multidimensional Szemerédi Theorem.

W. T. Gowers

Abstract. We prove analogues for hypergraphs of Szemerédi’s regularity lemma and the associated counting lemma for graphs. As an application, we give the first combinatorial proof of the multidimensional Szemerédi theorem of Furstenberg and Katznelson, and the first proof that provides an explicit bound. Similar results with the same consequences have been obtained independently by Nagle, Rödl and Schacht.

§1. Introduction.

Szemerédi’s theorem states that, for every real number δ > 0 and every positive integer k, there exists a positive integer N such that every subset A of the set {1, 2, …, N} of size at least δN contains an arithmetic progression of length k. There are now three substantially different proofs of the theorem, Szemerédi’s original combinatorial argument [Sz1], an ergodic-theory proof due to Furstenberg (see for example [FKO]) and a proof by the author using Fourier analysis [G1]. Interestingly, there has for some years been a highly promising programme for yet another proof of the theorem, pioneered by Vojta Rödl (see for example [R]), developing an argument of Ruzsa and Szemerédi [RS] that proves the result for progressions of length three. Let us briefly sketch their argument.

The first step is the famous regularity lemma of Szemerédi [Sz2]. If G is a graph and A and B are sets of vertices in V, then let e(A, B) stand for the number of pairs (x, y) ∈ A × B such that xy is an edge of G. Then the density d(A, B) of the pair (A, B) is e(A, B)/|A||B|. The pair is ϵ-regular if |d(A′, B′) − d(A, B)| ⩽ ϵ for all subsets A′ ⊂ A and B′ ⊂ B such that |A′| ⩾ ϵ|A| and |B′| ⩾ ϵ|B|. The basic idea is that a pair is regular with density d if it resembles a random graph with edge-probability d. Very roughly, the regularity lemma asserts that every graph can be decomposed into a few pieces, almost all of which are random-like. The precise statement is as follows.

Theorem 1.1. Let ϵ > 0. Then there exists a positive integer K such that, given any graph G, the vertices can be partitioned into at most K sets V_{i}, with sizes differing by at most 1, such that all but at most ϵK^{2} of the pairs (V_{i}, V_{j}) are ϵ-regular.

A partition is called ϵ-regular if it satisfies the conclusion of Theorem 1.1. The regularity lemma is particularly useful in conjunction with the following further result, known as the counting lemma.

Theorem 1.2. For every α > 0 and every k there exists ϵ > 0 with the following property. Let V_{1}, …, V_{k} be sets of vertices in a graph G, and suppose that for each pair (i, j) the pair (V_{i}, V_{j}) is ϵ-regular with density d_{ij}. Let H be a graph with vertex set (x_{1}, …, x_{k}) and let v_{i} ∈ V_{i} be chosen uniformly at random, the choices being independent. Then the probability that v_{i}v_{j} is an edge of G if and only if x_{i}x_{j} is an edge of H differs from ∏_{x_{i}x_{j}∈H} d_{ij} ∏_{x_{i}x_{j} ∉H}(1 − d_{ij}) by at most α.

Roughly, this result tells us that the k-partite graph induced by the sets V_{1}, …, V_{k} contains the right number of labelled copies of the graph H. Let us briefly see why this result is true when H is a triangle. Suppose that U, V, W are three sets of vertices and the pairs (U, V), (V, W) and (W, U) are ϵ-regular with densities ζ, η and θ respectively. Then a typical vertex of U has about ζ|V | neighbours in V and θ|W | neighbours in W. By the regularity of the pair (V, W), these two neighbourhoods span about η(ζ|V |)(θ|W |) edges in G, creating that many triangles. Summing over all vertices of U we obtain the result.

The next step in the chain of reasoning is the following innocent-looking statement about graphs with few triangles. Some of the details of the proof will be sketched rather than given in full.

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

Proof. This theorem is a simple consequence of the regularity lemma. Indeed, let ϵ = ϵ(a) > 0 be sufficiently small and let V_{1}, …, V_{K} be an ϵ-regular partition of the vertices of G. If there are fewer than a|V_{i}||V_{j}|/100 edges between V_{i} and V_{j}, then remove all those edges, and also remove all edges from V_{i} to V_{j} if (V_{i}, V_{j}) is not an ϵ-regular pair. Since the partition is ϵ-regular, we have removed fewer than an^{2} edges, and the resulting graph must either be triangle-free or contain several triangles. To see why this is, suppose that (x, y, z) is a triangle in G (after the edges have been removed), and suppose that (x, y, z) ∈ V_{i} × V_{j} × V_{k}. Then by our construction the pair (V_{i}, V_{j}) must be regular and must span many edges (because we did not remove the edge (x, y)) and similarly for the pairs (V_{j}, V_{k}) and (V_{i}, V_{k}). But then, by the counting lemma for triangles, the sets V_{i}, V_{j} and V_{k} span at least a^{3}|V_{i}||V_{j}||V_{k}|/10^{6} triangles. Each V_{i} has cardinality at least n/2K, where K depends on ϵ only (which itself depends on a only). This proves that the result is true provided that c ⩽ a^{3}/10^{6}K^{3}. □

Ruzsa and Szemerédi [RS] observed that Theorem 1.3 implies Szemerédi’s theorem for progressions of length 3. More recently, Solymosi noticed [S1,2] that it also implied the following two-dimensional generalization. (Actually, neither of these statements is quite accurate. There are several closely related graph-theoretic results that have these consequences and can be proved using the regularity lemma, of which Theorem 1.3 is one. Ruzsa and Szemerédi and Solymosi did not use Theorem 1.3 itself but their arguments are not importantly different.)

Corollary 1.4. 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. As it happens, the resulting improvement to the theorem is something of a side issue, since the positivity of d does not tend to be used in applications. See for instance Corollary 1.5 below. See also the remark at the beginning of the proof of Theorem 10.3.)

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

Corollary 1.5. 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+2y ∈ 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 + 2y, x + d + 2y and x + 2(y + d) belong to A and form an arithmetic progression. □

And now the programme for proving Szemerédi’s theorem in general starts to become clear. Suppose, for example, that one would like to prove it for progressions of length 4. After a little thought, one sees that the direction in which one should generalize Theorem 1.3 is the one that takes graphs to 3-uniform hypergraphs, that is, set-systems consisting of subsets of size 3 of a set X. If H is a 3-uniform hypergraph, then a simplex in H is a set of 4 vertices x, y, z and w of H (that is, elements of the set X) such that the four triples xyz, xyw, xzw and yzw all belong to H. The following theorem of Frankl and Rödl is a direct generalization of Theorem 1.3, but its proof is much harder.

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

As observed by Solymosi, it is straightforward to generalize the proof of Theorem 1.4 and show that Theorem 1.6 has the following consequence.

Theorem 1.7. 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.7 (and once again one does not need the positivity of d).

It may look as though this section contains enough hints to enable any sufficiently diligent mathematician to complete a proof of the entire theorem. Indeed, here is a sketch for the 3-uniform case. First, one proves the appropriate 3-graph analogue of Szemerédi’s regularity lemma. Then, given a hypergraph H, one applies this lemma. Next, one removes all sparse triples and all triples that fail to be regular. If the resulting hypergraph contains a simplex, then any three of the four sets in which its vertices lie must form a dense regular triple, and therefore (by regularity) the hypergraph contains many simplices, contradicting the original assumption.

The trouble with the above paragraph is that it leaves unspecified what it means for a triple to be regular. It turns out to be surprisingly hard to come up with an appropriate definition, where “appropriate” means that it must satisfy two conditions. First, it should be weak enough that for a regularity lemma to hold: that is, one should always be able to divide a hypergraph up into regular pieces. Second, it should be strong enough to yield the conclusion that four sets of vertices, any three of which form a dense regular triple, should span many simplices. The definition that Frankl and Rödl used for this purpose is complicated and it proved very hard to generalize. In [G2] we gave a different proof which is in some ways more natural. The purpose of this paper is to generalize the results of [G2] from 3-uniform hypergraphs to k-uniform hypergraphs for arbitrary k, thereby proving the full multidimensional version of Szemerédi’s theorem (Theorem 10.3 below), which was first proved by Furstenberg and Katznelson [FK]. This is the first proof of the multidimensional Szemerédi theorem that is not based on Furstenberg’s ergodic-theoretic approach, and also the first proof that gives an explicit bound. The bound, however, is very weak - giving an Ackermann-type dependence on the initial parameters.

Although this paper is self-contained, we recommend reading [G2] first. The case k = 3 contains nearly all the essential ideas, and they are easier to understand when definitions and proofs can be given directly. Here, because we are dealing with a general k, many of the definitions have to be presented inductively. The resulting proofs can be neater, but they may appear less motivated if one has not examined smaller special cases. The bulk of [G2] consists of background material and general discussion (such as, for example, a complete proof of the regularity lemma for graphs and a detailed explanation of how the ideas relate to those of the analytic approach to Szemerédi’s theorem in [G1]). Rather than repeat all that motivating material, we refer the reader to that paper for it.

The main results of this paper have been obtained independently by Nagle, Rödl and Schacht. They too prove hypergraph generalizations of the regularity and counting lemmas that imply Theorem 10.3 and Szemerédi’s theorem. However, they formulate their generalizations differently and there are substantial differences between their proof and ours. Broadly speaking, they take the proof of Frankl and Rödl as their starting point, whereas we start with the arguments of [G2]. At the end of [G2] we explain in more detail what the main difference is between the two approaches.

§2. Some basic definitions.

2.1. Hypergraphs and chains.

An r-partite hypergraph is a sequence X_{1}, …, X_{r} of disjoint sets, together with a collection H of subsets A of X_{1} ∪ … ∪ X_{r} with the property that |A ∩ X_{i}| ⩽ 1 for every i. The sets X_{i} are called vertex sets and their elements are vertices. The elements of H are called edges, or sometimes hyperedges if there is a danger of confusing them with edges in the graph-theoretic sense. A hypergraph is k-uniform if all its edges have size k. (Thus, a 2-uniform hypergraph is a graph.)

An r-partite hypergraph H is called an r-partite chain if it has the additional property that B is an edge of H whenever A is an edge of H and B ⊂ A. Thus, an r-partite chain is a particular kind of combinatorial simplicial complex, or down-set. Our use of the word “chain” is non-standard (in particular, it should not be confused with the notion of a chain complex in algebraic topology). We use it because it is quicker to write than “simplicial complex”.

If the largest size of any edge of H is k, then we shall sometimes say that H is a k-chain.

2.2. Homomorphisms and r-partite functions.

Let E_{1}, …, E_{r} and X_{1}, …, X_{r} be two sequences of disjoint finite sets. If ϕ is a map from E_{1} ∪ … ∪ E_{r} to X_{1} ∪ … ∪ X_{r} such that ϕ(E_{i}) ⊂ X_{i} for every i, we shall say that ϕ is an r-partite function.

Let J be an r-partite chain with vertex sets E_{1}, …, E_{r} and let H be an r-partite chain with vertex sets X_{1}, …, X_{r}. Let ϕ be an r-partite function from the vertices of J to the vertices of H. We shall say that ϕ is a homomorphism from J to H if ϕ(A) ∈ H whenever A ∈ J. We shall write Hom(J , H) for the set of all homomorphisms from J to H.

2.3. A-functions and J -functions.

Let Φ be the set of all r-partite maps from E_{1} ∪…∪E_{r} to X_{1} ∪…∪X_{r}. We shall also consider some special classes of functions defined on Φ. If A is a subset of E_{1} ∪…∪E_{r} such that |A ∩ E_{i}| ⩽ 1 for every i, then a function f : Φ → [−1, 1] will be called an A-function if the value of f(ϕ) depends only on the image ϕ(A). If J is an r-partite chain with vertex sets E_{1}, …, E_{r}, then a J -function is a function f : Φ → [−1, 1] that can be written as a product f = ∏_{A∈J} f^{A}, where each f^{A} is an A-function.

The definition of A-functions and J -functions is introduced in order to deal with situations where we have a function of several variables that can be written as a product of other functions each of which depends on only some of those variables. Let us clarify this with a small example. Suppose that we have three sets X_{1}, X_{2} and X_{3} and a function f : X_{1}^{2} × X_{2} × X_{3} → [−1, 1] of the form

f(x_{1}, x′_{1}, x_{2}, x_{3}) = f_{1}(x_{1}, x_{2})f_{2}(x_{1}, x_{3})f_{3}(x′_{1}, x_{2})f_{4}(x′_{1}, x_{3}) .

Let E_{1} = {1, 1′}, E_{2} = {2} and E_{3} = {3}. There is an obvious one-to-one correspondence between quadruples (x_{1}, x′_{1}, x_{2}, x_{3}) and tripartite maps from E_{1} ∪ E_{2} ∪ E_{3}: given such a sequence one associates with it the map ϕ that takes 1 to x_{1}, 1′ to x′_{1}, 2 to x_{2} and 3 to x_{3}. Therefore, we can if we wish change to a more opaque notation and write

f(ϕ) = f_{1}(ϕ)f_{2}(ϕ)f_{3}(ϕ)f_{4}(ϕ) .

Now f_{2}(ϕ) = f_{2}(ϕ(1), ϕ(3)) = f_{2}(ϕ({1, 3})), so f_{2} is a {1, 3}-function. Similar remarks can be made about f_{1}, f_{3} and f_{4}. It follows that f is a J -function if we take J to be the chain consisting of the sets {1, 2}, {1, 3}, {1′, 2} and {1′, 3} and all their subsets. The fact that the subsets are not mentioned in the formula does not matter, since if C is one of these subsets we can take the function that is identically 1 as our C-function.

An important and more general example is the following. As above, let J be an r-partite chain with vertex sets E_{1}, …, E_{r} and let H be an r-partite chain with vertex sets X_{1}, …, X_{r}. For each ϕ in Φ and each A ∈ J let H^{A}(ϕ) equal 1 if ϕ(A) ∈ H and 0 otherwise. Let H(ϕ) = ∏_{A∈J} H^{A}(ϕ). Then H(ϕ) equals 1 if ϕ ∈ Hom(J , H) and 0 otherwise. In other words, the characteristic function of Hom(J , H) is a J -function. We stress that H(ϕ) depends on J; however, it is convenient to suppress this dependence in the notation. Our counting lemma will count homomorphisms from small chains J to large quasirandom chains H, so we can regard our main aim as being to estimate the sum of H(ϕ) over all ϕ ∈ Φ. However, in order to do so we need to consider more general J -functions.

The J -functions we consider will be supported in a chain H in the following sense. Let us say that an A-function f^{A} is supported in H if f^{A}(ϕ) is zero whenever ϕ(A) fails to be an edge of H. Equivalently, f^{A} is supported in H if f^{A} = f^{A}H^{A}, where H^{A} is as defined above. Then we shall say that f is a J -function on H if it can be written as a product ∏_{A∈J} f^{A}, where each f^{A} is an A-function supported in H. If f is a J -function on H, then f(ϕ) = 0 whenever ϕ does not belong to Hom(J , H). That is, f(ϕ) = f(ϕ)H(ϕ). Notice that the product of any J function with the function H will be a J -function on H.

2.4. The index of a set, and relative density in a chain.

Let H be an r-partite chain with vertex sets X_{1}, …, X_{r}. Given a set E ∈ H, define its index i(E) to be the set of all i such that E ∩ X_{i} is non-empty. (Recall that E ∩ X_{i} is a singleton for each such i.) For any set A in any r-partite chain, let H(A) be the collection of all sets E ∈ H of index equal to that of A. If A has cardinality k, then let H_{∗}(A) be the collection of all sets D of index i(A) such that C ∈ H whenever C ⊂ D and C has cardinality k − 1. (Since H is a chain, it follows from this that all proper subsets of D belong to H.) Clearly H(A) ⊂ H_{∗}(A). The relative density of H(A) in H is defined to be |H(A)|/|H_{∗}(A)|. We will denote it by δ_{A}.

The relative density δ_{A} can be interpreted probabilistically: it is the conditional probability that a randomly chosen set D ⊂ X_{1} ∪ … ∪ X_{r} of index i(A) belongs to H (and hence to H(A)), given that all its proper subsets belong to H.

Notational remark. It may help the reader to remember the definitions in this section if we explicitly point out that most of the time we are adopting the following conventions. The symbols J and K are used for chains of fixed size that are embedded into a chain H of size tending to infinity. From these we sometimes form other chains: for instance, J_{1} will be a chain of fixed size derived from a chain J, and H_{x,x′} will be a chain of size tending to infinity derived from a chain H. The letter H will tend to be reserved for set systems connected with H where the sets all have the same index. The same goes for functions derived from H. For example, we write H(ϕ) because we use the full chain H to define the function, whereas we write H^{A}(ϕ) because for that we just use sets of index i(A), and hence of size |A|. Similarly, we write H_{∗}(A) because all sets in H_{∗}(A) have index i(A). 2.5. Oct(f) for an A-function f.

We are building up to a definition of quasirandomness for H(A). An important ingredient of the definition is a weighted count of combinatorial octahedra, which generalizes the following idea. If f is a function of three variables x, y and z that range over sets X, Y and Z, respectively, then we define a quantity Oct(f) to be the sum over all x, x′ ∈ X, y, y′ ∈ Y and z, z′ ∈ Z of

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′) .

Similarly, if f is a function of k variables x_{1}, …, x_{k}, with each x_{i} taken from a set X_{i}, then

Oct(f) = ∑_{x_{1}^{0},x_{1}^{1}∈X_{1}} … ∑_{x_{k}^{0},x_{k}^{1}∈X_{k}} ∏_{ϵ∈{0,1}^{k}} f(x_{1}^{ϵ_{1}}, …, x_{k}^{ϵ_{k}}) .

Now let us express this definition in the language of A-functions. As before, let J and H be r-partite chains with vertex sets E_{1}, …, E_{r} and X_{1}, …, X_{r}, let Φ be the set of all r-partite maps from E_{1} ∪ … ∪ E_{r} to X_{1} ∪ … ∪ X_{r} and let A ∈ J. We can think of an A-function as a function defined on the product of those X_{i} for which i ∈ i(A). However, we can also think of it as a function f defined on Φ such that f(ϕ) depends only on ϕ(A). To define Oct(f) in these terms, we construct a set system B as follows. For each i ∈ i(A) let U_{i} be a set of cardinality 2, let U be the union of the U_{i} and let B consist of the 2^{k} sets B ⊂ U such that |B ∩ U_{i}| = 1 for every i. Let Ω be the set of all maps ω from U to ⋃ X_{i} such that ω(U_{i}) ⊂ X_{i} for every i ∈ i(A). For each ω ∈ Ω define f^{B}(ω) to be the value of f(ϕ) for any map ϕ ∈ Φ such that ϕ(A) = ω(B). (This is well-defined, since f is an A-function.) Then define

Oct(f) = ∑_{ω∈Ω} ∏_{B∈B} f^{B}(ω) .

A moment’s thought will show that this definition agrees with the earlier one (which, for simplicity, dealt with the case A = {1, 2, …, k}).

2.6. Octahedral quasirandomness.

We come now to the most important definition of this section. Let f be an A-function, and suppose that it is supported in H_{∗}(A), in the sense that f(ϕ) = 0 whenever ϕ(A) ∉ H_{∗}(A). Equivalently, suppose that whenever f(ϕ) ≠ 0 we have f(C) ∈ H for every proper subset C ⊂ A. Loosely speaking, we shall say that f is octahedrally quasirandom relative to H if Oct(f) is significantly smaller than one might expect.

To turn this idea into a precise definition, we need to decide what we expect. Let B be the set system defined in the previous subsection. If B ∈ B, then f^{B}(ω) is defined to be the value of f(ϕ) for any ϕ with ϕ(A) = ω(B). If f^{B}(ω) ≠ 0, then f(ϕ) ≠ 0 so ϕ(A) ∈ H_{∗}(A), by assumption, and hence ω(B) ∈ H_{∗}(A). Therefore, a necessary condition for ∏_{B∈B} f^{B}(ω) to be non-zero is that ω(D) ∈ H for every D that is a proper subset of some B ∈ B. Let K be the chain consisting of all such sets. Then, since |f^{B}(ω)| ⩽ 1 for every B and every ω, a trivial upper bound for Oct(f) is

∑_{ω∈Ω} ∏_{D∈K} H^{D}(ω) ,

which we shall call Oct(H_{∗}(A)), since it counts the number of (labelled, possibly degenerate) combinatorial k-dimensional octahedra in H_{∗}(A).

We could if we wanted declare Oct(f) to be small if it is small compared with Oct(H_{∗}(A)). Instead, however, since we shall be working exclusively with quasirandom chains, it is more convenient to work out how many octahedra we expect H_{∗}(A) to have, given the various relative densities, and use that quantity for comparison.

This is easily done if we recall the interpretation of relative densities as conditional probabilities. Suppose that we choose ω randomly from Ω, and also that H behaves in a random way. Then the probability that H^{D}(ω) = 1 given that H^{C}(ω) = 1 for every C ⊊ D is the probability that ω(D) ∈ H given that ω(C) ∈ H for every C ⊊ D, which is δ_{D}. Because H behaves randomly, we expect all these conditional probabilities to be independent, so we expect that the ∑_{ω∈Ω} ∏_{D∈K} H^{D}(ω) will be approximately |Ω| ∏_{D∈K} δ_{D}. Accordingly, we shall say that f is η-octahedrally quasirandom if

Oct(f) ⩽ η|Ω| ∏_{D∈K} δ_{D} .

Since octahedral quasirandomness is the only form of quasirandomness that we use in this paper, we shall often omit the word “octahedrally” from this definition.

It is not necessary to do so, but one can rewrite the right-hand side more explicitly. For each proper subset C ⊊ A, there are 2^{|C|} sets D ∈ K with the same index as C. (We can think of these as |C|-dimensional faces of the octahedron with index i(C).) Moreove, writing N_{i} for the cardinality of X_{i}, we have that |Ω| = ∏_{i∈A} N_{i}^{2}. Therefore,

η|Ω| ∏_{D∈K} δ_{D} = η ∏_{C⊊A} δ_{C}^{2^{|C|}} ∏_{i∈A} N_{i}^{2} .

The main use of the definition of quasirandomness for A-functions is to give us a precise way of saying what it means for a k-partite k-uniform hypergraph to “sit quasirandomly inside a k-partite (k − 1)-chain”. Let A and H be as above. The k-uniform hypergraph we would like to discuss is H(A). Associated with this hypergraph is its “characteristic function” H^{A} and its relative density δ_{A}. The (k − 1)-chain is the set of all edges of H with index some proper subset of A. Define an A-function f^{A} by setting f^{A}(ϕ) to equal H^{A}(ϕ) − δ_{A} if ϕ(A) ∈ H_{∗}(A) and zero otherwise. An important fact about f^{A} is that its average is zero. To see this, note that

|Φ|^{−1} ∑_{ϕ(A)∈H_{∗}(A)} H^{A}(ϕ) = |Φ|^{−1} ∑_{ϕ∈Φ} H^{A}(ϕ) ,

which is the probability that ϕ(A) ∈ H for a randomly chosen r-partite map ϕ. Meanwhile,

|Φ|^{−1} ∑_{ϕ(A)∈H_{∗}(A)} δ_{A}

is the probability that ϕ(A) ∈ H_{∗}(A) multiplied by the conditional probability that ϕ(A) ∈ H(A) given that ϕ(A) ∈ H_{∗}(A), which is the same thing.

We shall say that H(A) is η-octahedrally quasirandom, or just η-quasirandom, relative to H, if the function f^{A} is η-quasirandom according to the definition given earlier. The counting lemma, which we shall prove in §5, will show that if H is an r-partite chain and all its different parts of the form H(A) are quasirandom in this sense, then H behaves like a random chain with the same relative densities.

§3. A technical lemma for r-partite chains.

The main task of this section is to prove the following lemma. We have used the word “technical” to describe it, but it is the engine that drives all our later arguments. The statement is somewhat complicated because it has had to be artificially strengthened so that it is amenable to an inductive proof. Lemma 3.1. Let J_{0} be an r-partite chain with vertex sets E_{1}, …, E_{r} and let A_{0} ∈ J_{0}. Let H be an r-partite chain with vertex sets X_{1}, …, X_{r}, and let Φ be the set of r-partite maps ϕ from E_{1} ∪ … ∪ E_{r} to X_{1} ∪ … ∪ X_{r}. Let G : Φ → [−1, 1] be a J_{0}-function on H, and suppose that G can be written ∏_{A∈J_{0}} g^{A}, where each g^{A} is an A-function supported in H and g^{A} = H^{A} whenever A_{0} ⊂ A. Let f be an A_{0}-function supported in H and let F = fG. Let J be any subchain of J_{0} that contains A_{0}. Then there exists an r-partite k-chain K with vertex sets F_{1}, …, F_{r}, satisfying the following properties.

(i) K depends on J only.

(ii) There is a homomorphism γ from K to J such that for every set A ∈ J there

are exactly 2^{k} sets C ∈ K with γ(C) = A. (iii) For each i ∈ i(A_{0}) there is a subset U_{i} of F_{i} of cardinality 2, and every set

C ⊂ ⋃_{i∈A_{0}} U_{i} such that |C ∩ U_{i}| ⩽ 1 for each i ∈ A_{0} belongs to K. (iv) Let B be the set of B ⊂ ⋃_{i∈A_{0}} U_{i} such that |B ∩ U_{i}| = 1 for every i ∈ A_{0} and let Ω be the set of all r-partite maps from F_{1} ∪ … ∪ F_{r} to X_{1} ∪ … ∪ X_{r}. Then we have the inequality

(∑_{ϕ∈Φ} F (ϕ))^{2^{k}} ⩽ ∑_{ω∈Ω} ∏_{C∈K} H^{C}(ω) ∏_{B∈B} f^{B}(ω) ,

where f^{B}(ω) is defined to be the value of f(ϕ) for any map ϕ ∈ Φ such that ϕ(A_{0}) = ω(B).

Before we give the proof of Lemma 3.1, here are a few remarks about it. The most important of the properties of K is the inequality in (iv). The left-hand side of this inequality can be interpreted as follows. First, rewrite it as

∑_{ϕ_{1},...,ϕ_{2^{k}} ∈Φ} F (ϕ_{1}) … F (ϕ_{2^{k}}) ,

and write F (ϕ_{1}, …, ϕ_{2^{k}}) for F (ϕ_{1}) … F (ϕ_{2^{k}}). Now a sequence of 2^{k} functions ϕ_{1}, …, ϕ_{2^{k}} in Φ can be thought of as a single r-partite function with range X_{1} ∪ … ∪ X_{r} and domain a suitable set built out of 2^{k} copies of E_{1} ∪ … ∪ E_{r}. Moreover, if in each of these copies we put a copy of J_{0} and call the resulting chain L, then F (ϕ_{1}, …, ϕ_{2^{k}}) is the product of an L-function with the function f(ϕ_{1}(A_{0})) … f(ϕ_{2^{k}}(A_{0})). Thus, if J = J_{0} then the main thing we have done in getting from the left-hand side to the right-hand side is to replace L by a chain K which also has 2^{k} sets for each set in J_{0}, but which allows us to put together all the copies of A_{0} so that they form the faces of a k-octahedron. If J is a proper subset of J_{0} then we have also passed to a subchain.

The reason for this rather curious passage to a subset J of the original chain J_{0} is that we shall apply the lemma in the case where J is the set of all edges of J_{0} of size at most k − 1. However, the proof of the lemma is by induction on k and we cannot afford to restrict to sets of size at most k − 2 in the inductive hypothesis.

A third remark is that Lemma 3.1 follows from a certain special case, which is easier (for notational reasons) to prove. We state this implication as a separate lemma.

Lemma 3.2. Lemma 3.1 is true in general if it is true whenever the vertex sets of J are singletons.

Proof. Let all the notation be as in the statement of Lemma 3.1. Our task is to exhibit a chain K with the required properties. Let m = |E_{1}| + … + |E_{r}| and define new chains J_{0}^{∗} and J^{∗} to consist of the same vertices and edges as J_{0} and J, respectively, but with the vertex set E_{1} ∪ … ∪ E_{r} partitioned into m singletons instead of into the r sets E_{1}, …, E_{r}. Next, build an m-partite chain H^{∗} out of H as follows. The vertex sets are all sets of the form {a} × X_{i}, where a is an element of E_{i}. Let π be the projection that takes a vertex (a, x) of H^{∗} to the vertex x of H. Then Y is an edge of H^{∗} if πY is an edge of H and the restriction of π to Y is an injection. (This second condition says that if x ≠ y then (a, x) and (a, y) cannot both belong to the same edge Y of H^{∗}.)

To each r-partite map ϕ ∈ Φ we can associate an m-partite map ϕ^{∗} : E_{1} ∪ … ∪ E_{r} → ⋃_{i=1}^{r} E_{i} × X_{i} by setting ϕ^{∗}(a) = (a, ϕ(a)). Let Φ^{∗} be the set of such m-partite maps. Obviously, the map ϕ ↦ ϕ^{∗} is a one-to-one correspondence between Φ and Φ^{∗}: indeed, the map ϕ^{∗} ↦ π ∘ ϕ^{∗} is its inverse. More importantly, ϕ(A) ∈ H if and only if ϕ^{∗}(A) ∈ H^{∗}. This follows from the fact that ϕ(A) = πϕ^{∗}(A), since πϕ^{∗}(A) ∈ H if and only if ϕ^{∗}(A) ∈ H^{∗} by the definition of H^{∗} (and the fact that π restricted to ϕ^{∗}(A) is clearly an injection).

Another useful fact is that if f : Φ → [−1, 1] then f ∘ γ : Φ^{∗} → [−1, 1], and f is an A-function supported in H if and only if f ∘ π is an A-function supported in H^{∗}. Let us quickly check this. Suppose that f(ϕ) depends only on ϕ(A) and let ϕ^{∗}(A) = ψ^{∗}(A). Then ϕ(A) = ψ(A) (applying γ to both sides), so f(ϕ) = f(ψ) and hence f ∘ π(ϕ^{∗}) = f ∘ π(ψ^{∗})). This shows that f ∘ π depends only on ϕ^{∗}(A). Conversely, if f ∘ π depends only on ϕ^{∗}(A) and ϕ(A) = ψ(A) then ϕ^{∗}(A) = ψ^{∗}(A) (as can easily be seen from the definition of ϕ^{∗} and ψ^{∗}), from which it follows that f ∘ π(ϕ^{∗}) = f ∘ π(ψ^{∗}) and hence that f(ϕ) = f(ψ). Now suppose that f is an A-function supported in H and that f ∘π(ϕ^{∗}) ≠ 0. Then πϕ^{∗}(A) ∈ H, which implies that ϕ^{∗}(A) ∈ H^{∗}. Hence, f ∘ π is supported in H^{∗}. Conversely, if f ∘ π is an A-function supported in H^{∗} and f(ϕ) ≠ 0 then f ∘ π(ϕ^{∗}) ≠ 0, so ϕ^{∗}(A) ∈ H^{∗}, and hence ϕ(A) = πϕ^{∗}(A) ∈ H. This implies that ϕ(A) ∈ H, and hence that ϕ is supported in H.

Having established these simple facts, let us apply Lemma 3.1 to the chains J_{0}^{∗}, J^{∗} and H^{∗} and to the function G^{∗} = ∏_{A∈J^{∗}} g^{A} ∘ π. The remarks above show that the hypotheses of the lemma are satisfied, so it provides us with an m-partite chain K^{∗} with vertex sets V_{1}, …, V_{m}, all of which have size 2^{k}. Let γ be the 2^{k}-to-one map given to us by property (ii). We can create from K^{∗} an r-partite chain K by simply combining these vertex sets into larger ones: for each i ⩽ r we let F_{i} be the union of all V_{j} such that γ(V_{j}) ⊂ E_{i}. (To put this less formally: each V_{j} consists of 2^{k} copies of a vertex of J, and we combine the V_{j} according to the sets E_{i} in which the corresponding vertices of J lie.)

It is clear that K depends only on J. To establish property (ii), all we have to do is check that γ takes elements of F_{i} to elements of E_{i}, which it does since that is how we defined the F_{i}. The rest of (ii) is obvious since the only difference between K and K^{∗} is in the partition we have put on the vertex set, and similarly for J and J^{∗}.

Next, let i ∈ i(A_{0}). Let a be the unique element of A_{0} ∩ E_{i}. Then {a} is a vertex set of J^{∗}, and (iii) gives us a subset U_{a} of V_{a} of cardinality 2, which we can rename U_{i}, since it is also a subset of F_{i} of cardinality 2. Property (iii) now follows easily for K - again since we are talking about precisely the same sets as we were for K^{∗}.

Finally, let B be defined as in property (iv), and note that it is the same collection of sets, whether we are talking about K or K^{∗}. Lemma 3.1 for J_{0}^{∗}, J^{∗} and H^{∗} gives us the inequality

( ∑_{ϕ^{∗}∈Φ^{∗}} F (ϕ^{∗}))^{2^{k}} ⩽ ∑_{ω^{∗}∈Ω^{∗}} ∏_{C∈K^{∗}}(H^{∗})^{C}(ω^{∗}) ∏_{B∈B} f^{B}(ω^{∗}) ,

where Φ^{∗} and Ω^{∗} have obvious meanings and F (ϕ^{∗}) and f^{B}(ω^{∗}) are defined to be F (ϕ) and f^{B}(ω) for the corresponding functions ϕ ∈ Φ and ω ∈ Ω. We also have (H^{∗})^{C}(ω^{∗}) = H(γ(ω^{∗}(C))) = H(ω(C)) = H^{C}(ω). Therefore, this inequality is precisely what we want, and Lemma 3.1 is established for J_{0}, J and H. □

The proof of Lemma 3.1 is a good example of an argument that is simple to carry out in small cases (some examples are given in [G2]) and routine to generalize, but not easy to present in its general form without to some extent hiding its simplicity. Essentially, it consists of a large number of applications of the Cauchy-Schwarz inequality together with a few rearrangments of sums. However, to prove it in general, one must use induction, and as we have seen the inductive hypothesis turns out to be quite complicated.

Quite a lot of the main argument consists in little more than translating statements from one notation to another. To make the proof more comprehesible, we shall start with a preparatory lemma that will allow us to do this translation quickly and efficiently.

Suppose that J_{0} and H are r-partite chains with vertex sets E_{1}, …, E_{r} and X_{1}, …, X_{r}, respectively, and suppose also that E_{1} has only one element, e. Let J_{1} be the (r − 1)-partite chain consisting of all sets A ⊂ E_{2} ∪ … ∪ E_{r} that belong to J_{0}, and suppose that J_{0} satisfies the following condition.

(*) If A and B are any two sets in J_{1} with the same index then {e} ∪ A ∈ J_{0} if and

only if {e} ∪ B ∈ J_{0}. Given any element x ∈ X_{1} and any (r − 1)-partite map ϕ′ from E_{2} ∪ … ∪ E_{r} to

X_{2} ∪ … ∪ X_{r}, let (x, ϕ′) denote the r-partite map from E_{1} ∪ … ∪ E_{r} to X_{1} ∪ … ∪ X_{r} that takes e to x and a to ϕ′(a) if a ≠ e. Given two elements x, x′ ∈ X_{1}, we shall be interested to know under what circumstances both (x, ϕ′) and (x′, ϕ′) are homomorphisms. To be precise, we shall construct an (r − 1)-partite chain H_{x,x′} with vertex sets X_{2}, …, X_{r} such that (x, ϕ′) and (x′, ϕ′) are both homomorphisms from J_{0} to H if and only if ϕ′ is a homomorphism from J_{1} to H_{x,x′}.

Let Φ be the set of all r-partite maps from E_{1} ∪ … ∪ E_{r} to X_{1} ∪ … ∪ X_{r} and let Φ′ be the set of all (r − 1)-partite maps from E_{2} ∪ … ∪ E_{r} to X_{2} ∪ … ∪ X_{r}. Given a function f : Φ → [−1, 1] and two elements x, x′ ∈ X_{1}, define a function f_{x,x′} : Φ′ → [−1, 1] by f_{x,x′}(ϕ′) = f(x, ϕ′)f(x′, ϕ′). Another useful property of the chain H_{x,x′} shows that, under suitable conditions, f_{x,x′} relates to H_{x,x′} much as f relates to H.

For convenience, we shall write e ∪ A instead of {e} ∪ A, and similarly with other unions involving singletons. If A ∈ J_{1} then (H_{x,x′})^{A} will have the obvious meaning: if ϕ′ ∈ Φ′ then (H_{x,x′})^{A}(ϕ′) = 1 if ϕ′(A) ∈ H_{x,x′} and 0 otherwise. Lemma 3.3. Let J_{0} and H be r-partite chains with vertex sets E_{1} ∪ … ∪ E_{r} and X_{1} ∪ … ∪ X_{r}. Suppose that E_{1} is a singleton {e} and that J_{0} satisfies condition (∗) above. Then for each pair x, x′ of elements of X_{1} there exists an (r − 1)-partite chain H_{x,x′} with vertex sets X_{2}, …, X_{r}, with the following properties.

(i) A function ϕ′ ∈ Φ′ is a homomorphism from J_{1} to H_{x,x′} if and only if both (x, ϕ′) and (x′, ϕ′) are homomorphisms from J_{0} to H. (ii) If A ∈ J_{1} and e ∪ A ∈ J, then (H^{e∪A})_{x,x′} = (H_{x,x′})^{A}. (iii) If A ∈ J_{1} and f is an (e∪A)-function supported in H, then f_{x,x′} is an A-function

supported in H_{x,x′}. Proof. Define H_{x,x′} to be the (r − 1)-partite chain with vertex sets X_{2}, …, X_{r} consisting of all sets Y that satisfy the following conditions. First, Y ∈ H. Secondly, for every Z ⊂ Y, if e ∪ A ∈ J_{0} for some A ∈ J_{1} with i(A) = i(Z), then x ∪ Z ∈ H and x′ ∪ Z ∈ H. (We have to talk about subsets of Y in order to ensure that H_{x,x′} is a chain and not just a set system.) Let us prove the three properties.

(i) Suppose that ϕ′ ∈ Φ′ and that (x, ϕ′) and (x′, ϕ′) both belong to Hom(J_{0}, H). Let A ∈ J_{1}. Then A ∈ J_{0} and (x, ϕ′)(A) = ϕ′(A), so ϕ′(A) ∈ H. Let Z ⊂ ϕ′(A) and suppose that the index of Z is C. If e ∪ C ∈ J_{0}, then (x, ϕ′)(e ∪ C) and (x′, ϕ′)(e ∪ C) belong to H. That is, x ∪ ϕ′(C) and x′ ∪ ϕ′(C) belong to H. But ϕ′(C) = Z, so x ∪ Z and x′ ∪ Z belong to H. We have proved the conditions necessary for ϕ′(A) to belong to H_{x,x′}. This shows that ϕ′ ∈ Hom(J_{1}, H_{x,x′}).

Conversely, suppose that ϕ′ ∈ Hom(J_{1}, H_{x,x′}) and let A ∈ J. If e ∉ A, then (x, ϕ′)(A) = (x′, ϕ′)(A) = ϕ′(A), which belongs to H_{x,x′} by our hypothesis on ϕ′, and hence to H, since H_{x,x′} ⊂ H. If A = e ∪ B then (x, ϕ′)(A) = x ∪ ϕ′(B). But B ∈ J_{1} so ϕ′(B) ∈ H_{x,x′}, which implies, since e ∪ B ∈ J_{0}, that x ∪ ϕ′(B) ∈ H. Similarly, x′ ∪ ϕ′(B) ∈ H. This shows that (x, ϕ′) and (x′, ϕ′) both belong to Hom(J_{0}, H).

(ii) Because e∪A ∈ J_{0}, we have that ϕ′(A) ∈ H_{x,x′} if and only if x∪ϕ′(A) and x′∪ϕ′(A) belong to H. But x ∪ ϕ′(A) ∈ H if and only if H^{e∪A}(x, ϕ′) = 1 and x′ ∪ ϕ′(A) ∈ H if and only if H^{e∪A}(x′, ϕ′) = 1. It follows that

(H_{x,x′})^{A}(ϕ′) = H^{e∪A}(x, ϕ′)H^{e∪A}(x′, ϕ′) = (H^{e∪A})_{x,x′}(ϕ′) .

(iii) If f is an (e ∪ A)-function supported in H, then f = fH^{e∪A}, as we remarked in subsection 2.3. But then f_{x,x′} = f_{x,x′}(H^{e∪A})_{x,x′}, which equals f_{x,x′}(H_{x,x′})^{A}, by part (ii) of this lemma. This proves (by the same remark but the reverse implication) that f_{x,x′} is an A-function supported in H_{x,x′}. □

Notation. We shall use the customary notation [k] for the set {1, 2, …, k} and [2, k] for the set {2, 3, …, k}.

Proof of Lemma 3.1. We prove this result by induction on k. By Lemma 3.2 it is enough to prove it in the case where the vertex sets E_{i} of J_{0} are singletons. However, we may, and will, assume the general case as our inductive hypothesis. It will also simplify our notation slightly and involve no loss of generality if we assume that each E_{i} is the singleton {i} and that A_{0} = [k]. In order to make the structure of the proof a bit clearer, we shall divide it into steps.

Step 1. Splitting up the sum and applying the Cauchy-Schwarz inequality to obtain an expression to which the inductive hypothesis can be applied.

As earlier, let J_{1} be the set of all A ∈ J_{0} such that 1 ∉ A. We shall also let J_{2} be the subset of J_{1} consisting of those A ∈ J_{1} for which 1 ∪ A ∈ J_{0}. Then J_{0} = J_{1} ∪ {1 ∪ A : A ∈ J_{2}}. Recall that Φ′ is the set of (r − 1)-partite maps from [2, r] to X_{2} ∪ … ∪ X_{r} and note that there is a one-to-one correspondence between Φ and X_{1} × Φ′, as is implicit in the notation (x, ϕ′) introduced before Lemma 3.3, which we shall use again here. Therefore,

\begin{aligned}(∑_{ϕ∈Φ} F (ϕ))^{2^{k}} & = (∑_{ϕ∈Φ} f(ϕ) ∏_{A∈J_{0}} g^{A}(ϕ))^{2^{k}} \\ & = ( ∑_{ϕ′∈Φ′} ∑_{x∈X_{1}} f(x, ϕ′) ∏_{A∈J_{1}} g^{A}(ϕ′) ∏_{A∈J_{2}} g^{1∪A}(x, ϕ′))^{2^{k}} . \end{aligned}

Strictly speaking we should write g^{A}(x, ϕ′) in the first product, but since this quantity does not depend on x when 1 ∉ A, we use the abbreviation g^{A}(ϕ′).

Now, the inner sum is zero unless ϕ′ ∈ Hom(J_{1}, H), since if A ∈ J_{1} and ϕ′(A) ∉ H then g^{A}(ϕ′) = 0. Therefore, setting M = | Hom(J_{1}, H)|, the Cauchy-Schwarz inequality implies that the last line is at most

(M ∑_{ϕ′∈Φ′}( ∑_{x∈X_{1}} f(x, ϕ′) ∏_{A∈J_{1}} g^{A}(ϕ′) ∏_{A∈J_{2}} g^{1∪A}(x, ϕ′))^{2})^{2^{k−1}} .

Since the functions g^{A} with A ∈ J_{1} have no dependence on x, we will increase this last expression if we remove any such g^{A} from the product, or if we replace it by the larger function H^{A}. Therefore, we can set J_{3} = J_{1} ∩ J and say that this last expression is at most

\begin{matrix}(M ∑_{ϕ′}(∑_{x} f(x, ϕ′) ∏_{A∈J_{3}} H^{A}(ϕ′) ∏_{A∈J_{2}} g^{1∪A}(x, ϕ′))^{2})^{2^{k−1}} \\ = M^{2^{k−1}}(∑_{x,x′} ∑_{ϕ′} f_{x,x′}(ϕ′) ∏_{A∈J_{3}} H^{A}(ϕ′) ∏_{A∈J_{2}}(g^{1∪A})_{x,x′}(ϕ′))^{2^{k−1}} . \end{matrix}

By Hölder’s inequality, this is at most

M^{2^{k−1}}|X_{1}|^{2^{k}−2} ∑_{x,x′}(∑_{ϕ′} f_{x,x′}(ϕ′) ∏_{A∈J_{3}} H^{A}(ϕ′) ∏_{A∈J_{2}}(g^{1∪A})_{x,x′}(ϕ′))^{2^{k−1}} .

Step 2. Rewriting the bracketed part of the last expression in terms of the chain H_{x,x′} in order to show that it satisfies the conditions for the inductive hypothesis to be applicable.

The function f is a [k]-function supported in H and [2, k] ∈ J_{1}. Hence, by Lemma 3.3, f_{x,x′} is a [2, k]-function supported in H_{x,x′}. Lemma 3.3 also tells us, for each A ∈ J_{1}, that g^{1∪A} is an A-function supported in H_{x,x′}. Here we are using the fact that J_{0} and J satisfy the condition (∗), for the trivial reason that there is at most one set of any given index. (It is for this purpose that we bothered with Lemma 3.2.)

The functions H^{A} must be treated slightly differently. If A ∈ J_{3}, then H^{A} is certainly an A-function supported in H, but it need not be supported in H_{x,x′}. However, if A ∈ J_{3} and H^{A}(ϕ′) ≠ 0, then ϕ′(A) ∈ H \ H_{x,x′}, so there exists C ⊂ A such that 1 ∪ C ∈ J_{0} and either x ∪ ϕ′(C) ∉ H or x′ ∪ ϕ′(C) ∉ H, which implies that C ∈ J_{2} and (g^{1∪C})_{x,x′}(ϕ′) = 0. Therefore, we make no difference to the product if we replace each H^{A}(ϕ′) in the first product by (H_{x,x′})^{A}(ϕ′).

Note also that if A ∈ J_{2} and [2, k] ⊂ A, then [k] ⊂ 1 ∪ A, so by hypothesis g^{1∪A} = H^{1∪A}. But then, by Lemma 3.3 again, (g^{1∪A})_{x,x′} = (H^{1∪A})_{x,x′} = (H_{x,x′})^{A}.

These observations show that we can rewrite the last line above as

M^{2^{k−1}}|X_{1}|^{2^{k}−2} ∑_{x,x′}(∑_{ϕ′} f_{x,x′}(ϕ′) ∏_{A∈J_{2}∪J_{3}} u_{x,x′}^{A}(ϕ′))^{2^{k−1}} ,

where each function u_{x,x′}^{A} is an A-function (that depends on x and x′) supported in H_{x,x′}, and it equals (H_{x,x′})^{A} when [2, k] ⊂ A. Moreover, f_{x,x′} is a [2, k]-function supported in H_{x,x′} and ∏_{A∈J_{2}∪J_{3}} u_{x,x′}^{A} is a (J_{2} ∪ J_{3})-function on H_{x,x′}.

Step 3. Applying the inductive hypothesis.

We have just shown that the conditions for Lemma 3.1 are satisfied, with r, J_{0}, A_{0}, H and g^{A} replaced by r−1, J_{2} ∪J_{3}, [2, k], H_{x,x′} and u_{x,x′}^{A}, respectively. Now let J_{4} = J_{2} ∩J. Then J_{4} ∪ J_{3} is a subchain of J_{2} ∪ J_{3} and [2, k] ∈ J_{4} ∪ J_{3}, so we can apply the inductive hypothesis with J_{4} ∪ J_{3} playing the part of J. It provides us with an (r − 1)-partite chain K_{1} and a homomorphism γ′ from K_{1} to J_{4} ∪ J_{3} such that for each A ∈ J_{4} ∪ J_{3} there are exactly 2^{k−1} sets C ∈ K_{1} with γ′(C) = A. Let V_{2}, …, V_{r} be the vertex sets of K_{1}. Then we are also provided with sets U_{2}, …, U_{k} such that U_{i} ⊂ V_{i} and |U_{i}| = 2 for each i, and such that every subset of U_{2} ∪ … ∪ U_{k} that intersects each U_{i} at most once belongs to K_{1}. Letting B_{1} be the set of all such sets that intersect each U_{i} exactly once and letting Ω′ be the set of all (r − 1)-partite maps from V_{2} ∪ … ∪ V_{r} to X_{2} ∪ … ∪ X_{r}, we are also given the inequality

(∑_{ϕ′} f_{x,x′}(ϕ′) ∏_{A∈J_{2}∪J_{3}} u_{x,x′}^{A}(ϕ′))^{2^{k−1}} ⩽ ∑_{ω′∈Ω′} ∏_{C′∈K′}(H_{x,x′})^{C′}(ω′) ∏_{B′∈B_{1}}(f_{x,x′})^{B′}(ω′) .

And now, putting together all the inequalities we have shown so far, we have that

(∑_{ϕ∈Φ} F (ϕ))^{2^{k}} ⩽ M^{2^{k−1}}|X_{1}|^{2^{k}−2} ∑_{x,x′} ∑_{ω′∈Ω′} ∏_{C′∈K_{1}}(H_{x,x′})^{C′}(ω′) ∏_{B′∈B_{1}}(f_{x,x′})^{B′}(ω′) .

Step 4. Rewriting the right-hand side of the above inequality in terms of H rather than H_{x,x′}.

The product ∏_{C′∈K_{1}}(H_{x,x′})^{C′}(ω′) is the characteristic function of the event that ω′ is a homomorphism from K_{1} to H_{x,x′}. Let K_{0} be the r-partite chain with vertex sets {1}, V_{2}, V_{3}, …, V_{r} consisting of all sets A ∈ K_{1} together with all sets of the form 1 ∪ A such that A ∈ K_{1} and γ′(A) ∈ J_{4}. (Recall that this is the case if 1 ∪ γ′(A) ∈ J.) Then K_{1} is the collection of all sets A ∈ K_{0} that are subsets of V_{2} ∪ … ∪ V_{r}, so it is built out of K_{0} just as J_{1} is built out of J_{0}. Furthermore, K_{0} satisfies condition (∗): if A, B ∈ K_{1}, i(A) = i(B) and 1 ∪ A ∈ K_{0}, then γ′(A) = γ′(B) and γ′(A) ∈ J_{4}, so γ′(B) ∈ J_{4}, so 1 ∪ B ∈ K_{0}. Therefore, by Lemma 3.3, ω′ ∈ Hom(K_{1}, H_{x,x′}) if and only if both (x, ω′) and (x′, ω′) belong to Hom(K_{0}, H).

Now we define an r-partite chain K_{2} with vertex sets {1, 1′}, V_{2}, …, V_{r}. The edges of K_{2} are all sets A ∈ K_{1} together with all sets of the form 1∪A or 1′∪A such that γ′(A) ∈ J_{4}. For each ω′ ∈ Ω′ let (x, x′, ω′) denote the r-partite map that takes 1 to x, 1′ to x′ and a to ω′(a) for all a ∈ V_{2} ∪ … ∪ V_{r}. Clearly (x, ω′) and (x′, ω) belong to Hom(K_{0}, H) if and only if (x, x′, ω′) ∈ Hom(K_{2}, H). We have therefore shown that

∏_{C′∈K_{1}}(H_{x,x′})^{C′}(ω′) = ∏_{C∈K_{2}} H^{C}(x, x′, ω′)

for every x, x′ ∈ X_{1} and every ω′ ∈ Ω′.

As for (f_{x,x′})^{B′}(ω′), it equals the value of f_{x,x′}(ϕ′) for any ϕ′ ∈ Φ′ such that ϕ′([2, k]) = ω′(B′). But if ϕ′ has this property then (x, ϕ′)([k]) = (x, x′, ω′)(1 ∪ B′) and (x′, ϕ′)([k]) = (x, x′, ω′)(1′ ∪ B′). It follows that

(f_{x,x′})^{B′}(ω′) = f_{x,x′}(ϕ′) = f(x, ϕ′)f(x′, ϕ′) = f^{1∪B′}(x, x′, ω′)f^{1′∪B′}(x, x′, ω′) .

Let U_{1} = {1, 1′} and let B be the set of all sets of the form 1 ∪ B′ or 1′ ∪ B′ with B′ ∈ B′. Let Ω_{2} be the set of all r-partite maps from U_{1} ∪ V_{2} ∪ … ∪ V_{r} to X_{1} ∪ … ∪ X_{r} and note that these are precisely the maps of the form (x, x′, ω′) with ω′ ∈ Ω′. It follows that the right-hand side of the last inequality can be written

M^{2^{k−1}}|X_{1}|^{2^{k}−2} ∑_{ω∈Ω_{2}} ∏_{C∈K_{2}} H^{C}(ω) ∏_{B∈B} f^{B}(ω) .

Step 5. Reinterpreting the inequality we have just proved, in order to demonstrate that it proves the lemma.

It remains to define a suitable chain K and rewrite the expression we have just obtained in terms of K in such a way that it has the form stated in the lemma. Then we must check that K has the properties claimed. What enables us to do this is the fact that M^{2^{k−1}} and |X_{1}|^{2^{k}−2} both count homomorphisms from suitable chains into H. (Recall that M = | Hom(J_{1}, H)|.)

Define a chain K as follows. Let W_{1} be a set of size 2^{k} − 2 and for 2 ⩽ i ⩽ r let W_{i} be a set of size 2^{k−1}. Let the vertex sets of K be F_{1}, …, F_{r}, where F_{1} = U_{1} ∪ W_{1} and F_{i} = V_{i} ∪ W_{i} for i ⩾ 2. Let K_{3} be the set of all singletons {a} with a ∈ W_{1}. Let K_{4} be a union of 2^{k−1} disjoint copies of J_{1} living inside W_{2} ∪ … ∪ W_{r}. (More formally, let Z_{1}, …, Z_{2^{k−1}} be disjoint sets such that |E_{i} ∩ Z_{j}| = 1 for every 2 ⩽ i ⩽ r and 1 ⩽ j ⩽ 2^{k−1}. Then for each Z_{j} let ζ_{j} be the unique (r − 1)-partite map from [2, k] to Z_{j} and let K_{4} consist of all sets of the form ζ_{j}(A) with A ∈ J_{1}.)

We now let K = K_{2} ∪ K_{3} ∪ K_{4} and let Ω be the set of all r-partite maps ω from F_{1} ∪ … ∪ F_{r} to X_{1} ∪ … ∪ F_{r}. Such a map is a homomorphism if and only if its restrictions to W_{1} and to W_{2}∪…∪W_{r} are homomorphisms from K_{3} to H and from K_{4} to H respectively. It follows easily that

M^{2^{k−1}}|X_{1}|^{2^{k}−2} ∑_{ω∈Ω_{2}} ∏_{C∈K_{2}} H^{C}(ω) ∏_{B∈B} f^{B}(ω) = ∑_{ω∈Ω} ∏_{C∈K} H^{C}(ω) ∏_{B∈B} f^{B}(ω) .

Step 6. Checking that K has the properties claimed.

It remains to prove that for each non-empty set A ∈ J there are exactly 2^{k} sets in K of index A, and that these sets are all the non-empty sets in K. (It is clear that K depends only on J.) So let A ∈ J. If 1 ∉ A then there are 2^{k−1} copies of A in K_{4} and no copies of A in K_{3}. We also have that A ∈ J_{1} ∩ J = J_{3}, so, as we showed earlier, there are 2^{k−1} sets C in K_{1} such that γ′(C) = A. Each of these sets belongs to K_{2}. If 1 ∈ A then let B = A \ {1}. If B is non-empty then again there are 2^{k−1} sets C in K′ such that γ′(C) = B. Since 1 ∪ B ∈ J, we have B ∈ J_{4}, so for each such C the sets {1} ∪ C and {1′} ∪ C belong to K_{2}. Therefore, K_{2} contains 2^{k} sets with index A. Neither K_{3} nor K_{4} contains any sets with index A. If B is empty then A = {1} and there are two sets C in K_{2} of index A, namely {1} and {1′}. Together with the singletons {a} ∈ K_{3} this again makes 2^{k} sets in K. □

§5. A counting lemma for quasirandom chains.

In this section we shall prove that a sufficiently quasirandom r-partite chain H behaves like a random chain in the following respect: if J is a fixed chain (we imagine that H is varying and its size is tending to infinity), then the number of r-partite maps from the vertices of J to the vertices of H that are homomorphisms is roughly what would be expected if H had been chosen randomly.

The main result of the section is in fact a generalization of the counting lemma itself. We state the more general form because it lends itself more easily to an inductive proof, and is in fact a useful statement in its own right. A few preliminary words about the result may make the formal statement easier to take in.

Let F and f be as defined in the statement of Lemma 3.1. The main idea behind the counting lemma, and the justification for the definition of octahedral quasirandomness, is that if Oct(f) is small and H behaves like a random chain then ∑_{ϕ∈Φ} F (ϕ) is also small. One can give a heuristic argument for this using the inequality from part (iv) of Lemma 3.1 as follows. Let K_{1} be the chain of all subsets of all sets B ∈ B. Then ∏_{B∈B} f^{B}(ω) is non-zero only if H^{C}(ω) = 1 for every C ∈ K_{1}. Therefore, we can rewrite the right-hand side of the inequality as

∑_{ω∈Ω} ∏_{C∈K\K_{1}} H^{C}(ω) ∏_{B∈B} f^{B}(ω) .

We would expect that if ω is chosen randomly then the probability that ∏_{C∈K\K_{1}} H^{C}(ω) = 1 given that ∏_{B∈B} f^{B}(ω) ≠ 0 is around ∏_{C∈K\K_{1}} δ_{C}. Furthermore, since no set in K \ K_{1} is contained in any set in K_{1}, we expect this probability to be more or less independent of the value of ∏_{B∈B} f^{B}(ω). In other words, we expect that

∑_{ω∈Ω} ∏_{C∈K\K_{1}} H^{C}(ω) ∏_{B∈B} f^{B}(ω) ≈ ∏_{C∈K\K_{1}} δ_{C} ∑_{ω∈Ω} ∏_{B∈B} f^{B}(ω) .  (∗)

We count Oct(f) as small if ∑_{ω∈Ω} ∏_{B∈B} f^{B}(ω) is small compared with |Ω| ∏_{C∈K_{1}} δ_{C}.

Putting these two estimates together shows that (∑_{ϕ∈Φ} F (ϕ))^{2^{k}} is small compared with |Ω| ∏_{C∈K} δ_{C}. Since for each set in J the chain K contains 2^{k} sets of the same index, this is equal to (|Φ| ∏_{A∈J} δ_{A})^{2^{k}}. If H is sufficiently quasirandom, then |Φ| ∏_{A∈J} δ_{A} will be roughly the size of Hom(J , H), so it is appropriate to claim that ∑_{ϕ∈Φ} F (ϕ) is small.

In order to make the above ideas rigorous we must somehow take each function H^{C}(ω) on the left-hand side of (∗) and replace it by the constant function δ_{C}. We do this by exploiting the quasirandomness of H^{C}. Roughly speaking, that tells us that the difference between H^{C} and δ_{C} is octahedrally quasirandom relative to the chain, so we can try to use Lemma 3.1 to prove that replacing H^{C} by δ_{C} will not make much difference. This seems to raise exactly the same difficulties that we are already trying to solve, but if we are careful we can assume that in this instance they have been dealt with by induction.

Theorem 5.1, then, is a general result that allows us, under appropriate circumstances, to take expressions involving functions H^{A} and replace some of them by constant functions δ_{A}. The proof is a more detailed version of the argument just sketched. In order for the proof to work, certain relationships must hold between the relative densities and the quasirandomness parameters. So that we do not have to keep repeating these, and so that the statements of our results are not too cumbersome, let us formulate a definition first.

Suppose that J and H are r-partite chains. For each A ∈ J, let the relative density of H(A) in H be δ_{A} and suppose that H(A) is relatively η_{A}-quasirandom. For each s let δ_{⩾s} be the product of the relative densities δ_{A} over all A ∈ J of size at least s. Let 0 < ϵ < 1 and define a pair of sequences η_{2}, …, η_{k} and ϵ_{2}, …, ϵ_{k} inductively, by setting ϵ_{k} = ϵ and for each s ⩽ k setting η_{s} = \frac{1}{2}(ϵ_{s}δ_{⩾s})^{2^{s}} and ϵ_{s−1} = η_{s}|J |^{−1} ∏_{t=s}^{k} 2^{−t}. We shall say that the chain H is (ϵ, J , k)-quasirandom if η_{A} ⩽ η_{s} for each s ⩽ k and each set A of size s. For much of the argument that follows, it is not necessary to remember the details of this definition: basically, H is (ϵ, J , k)-quasirandom if the various parts of H are sufficiently quasirandom to make the proof of our counting lemma work. Notice one feature of the definition: that if H is (ϵ, J , k)-quasirandom and ϵ_{2}, …, ϵ_{k} are as defined above, then H is (ϵ_{s}, J , s)-quasirandom for each s between 2 and k.

Theorem 5.1. Let J_{0} and H be r-partite chains with vertex sets E_{1} ∪ … ∪ E_{r} and X_{1} ∪ … ∪ X_{r}, respectively. Let J_{1} be a subchain of J_{0} and let G = ∏_{A∈J_{0}} g^{A} be a J_{0}-function on H such that each g^{A} is an A-function supported in H and g^{A} = H^{A} whenever A ∈ J_{0} \ J_{1}. Let k be the size of the largest set in J_{0} \ J_{1} and suppose that H is (ϵ, J_{0}, k)-quasirandom. Then

|∑_{ϕ∈Φ} ∏_{A∈J_{0}} g^{A}(ϕ) − ∏_{A∈J_{0}\J_{1}} δ_{A} ∑_{ϕ∈Φ} ∏_{A∈J_{1}} g^{A}(ϕ)| ⩽ ϵ|J_{0} \ J_{1}||Φ| ∏_{A∈J_{0}} δ_{A} .

Proof. Our argument will be by a double induction. The outer induction will be on k and the inner one will be on the number |J_{0} \ J_{1}|. If J_{1} = J_{0} then the result is trivial. Otherwise, let Φ be the set of r-partite maps from E_{1} ∪ … ∪ E_{r} to X_{1} ∪ … ∪ X_{r} and let A_{0} be a set of size k in J_{0} \ J_{1}. For each ϕ ∈ Φ let f(ϕ) = H^{A_{0}}(ϕ) − δ_{A_{0}} ∏_{A⊊A_{0}} H^{A}(ϕ). Then let F (ϕ) = f(ϕ)G(ϕ). (This is a quick way of defining the function that has the same formula as G except that g^{A_{0}}, which equals H^{A_{0}}, is replaced by f. It works because f = fg^{A_{0}}.) Then the conditions of Lemma 3.1 are satisfied for J_{0}, H, A_{0} and F: since A_{0} is a maximal element of J_{0} \ J_{1} and J_{1} is a chain, A_{0} = A whenever A_{0} ⊂ A, so g^{A} = H^{A}; the other conditions are obvious.

Now let J be the set of all edges of J_{0} of cardinality less than k. Let K be the chain provided for us by Lemma 3.1, so that, in the notation of that lemma, we have the inequality

(∑_{ϕ∈Φ} F (ϕ))^{2^{k}} ⩽ ∑_{ω∈Ω} ∏_{C∈K} H^{C}(ω) ∏_{B∈B} f^{B}(ω) .

Letting K_{1} be the subchain of K consisting of all subsets of sets in B, we can rewrite this as

\begin{aligned}(∑_{ϕ∈Φ} F (ϕ))^{2^{k}} & ⩽ ∑_{ω∈Ω} ∏_{C∈K\K_{1}} H^{C}(ω) ∏_{B∈B} f^{B}(ω) ∏_{C∈K_{1}\B} H^{C}(ω) \\ & = ∑_{ω∈Ω} ∏_{C∈K\K_{1}} H^{C}(ω) ∏_{B∈B} f^{B}(ω) , \end{aligned}

since whenever f_{B}(ω) ≠ 0 we have H^{C}(ω) = 1 for every C ⊂ B.

But the largest set in K \ K_{1} has size less than k, and for each s ⩽ k − 1 we have ϵ_{s−1} ⩽ η_{s}|J_{0}|^{−1} ∏_{t=s}^{k} 2^{−t} ⩽ η_{s}|K|^{−1} ∏_{t=s}^{k−1} 2^{−t}, since |K| ⩽ 2^{k}|J_{0}|. This tells us that H is (ϵ_{k−1}, K, k−1)-quasirandom, which puts us in a position to apply our inductive hypothesis. This tells us that

|∑_{ω∈Ω} ∏_{C∈K\K_{1}} H^{C}(ω) ∏_{B∈B} f^{B}(ω) − ∏_{C∈K\K_{1}} δ_{C} ∑_{ω∈Ω} ∏_{B∈B} f^{B}(ω)| ⩽ ϵ_{k−1}|K \ K_{1}||Ω| ∏_{C∈K} δ_{C} .

It does not quite tell us this directly, since B is not a chain, but it does so if in addition we use the equality ∏_{B∈B} f^{B}(ω) = ∏_{B∈B} f^{B}(ω) ∏_{C∈K_{1}\B} H^{C}, which we observed earlier.

By hypothesis,

∑_{ω∈Ω} ∏_{B∈B} f^{B}(ω) ⩽ η_{k}|Ω| ∏_{B∈K_{1}} δ_{B} ,

from which it follows that

∏_{C∈K\K_{1}} δ_{C} ∑_{ω∈Ω} ∏_{B∈B} f^{B}(ω) ⩽ η_{k}|Ω| ∏_{C∈K} δ_{C} ,

and therefore that

|∑_{ω∈Ω} ∏_{C∈K\K_{1}} H^{C}(ω) ∏_{B∈B} f^{B}(ω)| ⩽ (ϵ_{k−1}|K \ K_{1}| + η_{k})|Ω| ∏_{C∈K} δ_{C} .

Since to each set A ∈ J we associate 2^{k} sets C ∈ K with the same index, this is equal to (ϵ_{k−1}|K \ K_{1}| + η_{k})(|Φ| ∏_{A∈J} δ_{A})^{2^{k}}. But |K \ K_{1}| < 2^{k}|J_{0}| and so, by our assumptions about ϵ_{k−1} and η_{k}, we may conclude that

|∑_{ϕ∈Φ} F (ϕ)| ⩽ (ϵ_{k−1}|K \ K_{1}| + η_{k})^{1/2^{k}}|Φ| ∏_{A∈J} δ_{A} ⩽ (2η_{k})^{1/2^{k}}|Φ| ∏_{A∈J} δ_{A} .

Since (2η_{k})^{1/2^{k}} ⩽ ϵ_{k}δ_{⩾k}, this is at most ϵ_{k}|Φ| ∏_{A∈J_{0}} δ_{A}.

But

∑_{ϕ∈Φ} F (ϕ) = ∑_{ϕ∈Φ} ∏_{A∈J_{0}} g^{A}(ϕ) − δ_{A_{0}} ∑_{ϕ∈Φ} ∏_{A∈J_{0},A≠A_{0}} g^{A}(ϕ) .

By our second induction (on |J_{0} \ J_{1}|) we have that

\begin{aligned}|∑_{ϕ∈Φ} ∏_{A∈J_{0},A≠A_{0}} g^{A}(ϕ) − ∏_{A∈J_{0}\J_{1},A≠A_{0}} δ_{A} ∑_{ϕ∈Φ} & ∏_{A∈J_{1}} g^{A}(ϕ)| \\ & ⩽ ϵ_{k}(|J_{0} \ J_{1}| − 1)|Φ| ∏_{A∈J_{0},A≠A_{0}} δ_{A} , \end{aligned}

which implies that

|δ_{A_{0}} ∑_{ϕ∈Φ} ∏_{A∈J_{0},A≠A_{0}} g^{A}(ϕ) − ∏_{A∈J_{0}\J_{1}} δ_{A} ∑_{ϕ∈Φ} ∏_{A∈J_{1}} g^{A}(ϕ)| ⩽ ϵ(|J_{0} \ J_{1}| − 1)|Φ| ∏_{A∈J_{0}} δ_{A} .

Hence, by the triangle inequality,

|∑_{ϕ∈Φ} ∏_{A∈J_{0}} g^{A}(ϕ) − ∏_{A∈J_{0}\J_{1}} δ_{A} ∑_{ϕ∈Φ} ∏_{A∈J_{1}} g^{A}(ϕ)| ⩽ ϵ_{k}|J_{0} \ J_{1}||Φ| ∏_{A∈J_{0}} δ_{A}

and the proof is complete. □

In the case where J_{0} = J and J_{1} = ∅, the function g^{A} in the statement of Theorem 5.1 is equal to H^{A}, for every A ∈ J. Then we have ∑_{ϕ∈Φ} ∏_{A∈J_{0}} g^{A}(ϕ) = | Hom(J , H)|. To complete the section, let us state this case of Theorem 5.1 separately. This is our “counting lemma” for quasirandom chains.

Corollary 5.2. Let J and H be r-partite chains with vertex sets E_{1} ∪ … ∪ E_{r} and X_{1} ∪ … ∪ X_{r}, respectively. Let k be the size of the largest set in J and suppose that H is (ϵ, J , k)-quasirandom. Then

|| Hom(J , H)| − |Φ| ∏_{A∈J} δ_{A}| ⩽ ϵ|J ||Φ| ∏_{A∈J} δ_{A} .  □

§6. Local increases in mean-square density.

All known proofs of Szemerédi’s theorem use (explicitly or implicitly) an approach of the following kind. Given a dense set that fails to be quasirandom in some appropriate sense, one can identify imbalances in the set that allow one to divide it into pieces that “improve” in some way, on average at least, on the set itself. One then iterates this argument until one reaches sets that are quasirandom. At that point one uses some kind of counting lemma to prove that they contain an arithmetic progression of length k.

This proof is no exception. We have defined a notion of quasirandomness and proved a counting lemma for it. Now we must see what happens when some parts of a chain are not relatively quasirandom. We shall end up proving a regularity lemma, which says, roughly speaking, that any dense chain can be divided up into a bounded number of pieces, almost all of which are quasirandom. This generalizes Szemerédi’s regularity lemma for graphs (which formed part of his proof of his theorem on arithmetic progressions).

Given a dense graph G and a positive real number ϵ, Szemerédi’s regularity lemma asserts that the vertices of G can be partitioned into K classes of roughly equal size, with K bounded above by a function of ϵ only, in such a way that, proportionately speaking, at least 1−ϵ of the bipartite graphs spanned by two of these classes are ϵ-quasirandom. (One can insist that K is much bigger than ϵ^{−1}, so it is not necessary to worry about the case where the two classes are equal. Or it can be neater to say that two equal classes form a “regular pair” if they span a quasirandom graph.)

Very roughly, the proof is as follows. Suppose you have a graph G and a partition of its vertex set. Then either this partition will do or there are many pairs of cells from the partition that give rise to induced bipartite subgraphs of G that are not ϵ-quasirandom. If X and Y are two disjoint sets of vertices, write G(X, Y) for the corresponding induced bipartite subgraph of G. Suppose that X and Y are two cells of the partition, for which G(X, Y) is not ϵ-quasirandom. Then it is not hard to show that there are large subsets X(0) ⊂ X and Y (0) ⊂ Y for which the density of G(X(0), Y (0)) is substantially different from that of G(X, Y). Letting X(1) = X \ X(0) and Y (1) = Y \ Y (0), we have obtained partitions of X and Y into two sets each, in such a way that the densities of the graphs G(X(i), Y (j)) are not almost all approximately the same as that of G(X, Y). One can then define an appropriately weighted average of the squares of these four densities and show that this average is greater than the square of the density of G(X, Y). Let us call this stage one of the argument, the stage where we identify a “local” increase in mean-square density.

It remains to turn these local increases into a global increase. This, which we shall call stage two, is quite simple. Denote the cells of the partition by X_{1}, …, X_{k}. For each pair (X_{i}, X_{j}) that fails to be ϵ-regular, use the above argument to partition X_{i} into two sets X_{ij}(0) and X_{ij}(1), and to partition X_{j} into two sets X_{ji}(0) and X_{ji}(1). Then for each i find a partition of X_{i} that refines all the partitions {X_{ij}(0), X_{ij}(1)}. The result is a partition into m ⩽ k.2^{k} sets Y_{1}, …, Y_{m} that refines the partition {X_{1}, …, X_{k}}. It can be shown that the average of the squares of the densities G(Y_{i}, Y_{j}), again, with appropriate weights, is significantly greater than it was for the partition {X_{1}, …, X_{k}}. Therefore, if one iterates the procedure, the iteration must terminate after a number of steps that can be bounded in terms of ϵ. It can terminate only if almost all the graphs G(X_{i}, X_{j}) are quasirandom, so the result is proved.

We have given this sketch since our generalized regularity lemma will be proved in a similar way. There are two main differences. First, it is an unfortunate fact of life that, when one is dealing with k-chains rather than graphs, simple arguments have to be expressed in terminology that can obscure their simplicity. For example, even defining the appropriate notion of a “partition” of a chain is somewhat complicated. Thus, stage two of our argument, although it is an “obvious” generalization of stage two of the proof of the usual regularity lemma, is noticeably more complicated to write down.

A more fundamental difference, however, is that our stage one is not completely straightforward, and here the difference is mathematical rather than merely notational. For an explanation of why it should be harder, see the beginning of §8, and also §10, of [G2]. (It is not, however, substantially harder for general k than it is for k = 3, the case dealt with in that paper.) This local stage will occupy us for the rest of this section.

To begin with, let us say what we mean by the mean-square density of a function with respect to a partition. Let U be a set of size n, let f : U → ℝ and let B_{1}, …, B_{r} be sets that form a partition of U. Then the mean-square density of f with respect to the partition {B_{1}, …, B_{r}} is

∑_{i=1}^{r} \frac{|B_{i}|}{n}(|B_{i}|^{−1} ∑_{x∈B_{i}} f(x))^{2} .

If we write β_{i} for |B_{i}|/n (which it is helpful to think of as the probability that a random x ∈ U is an element of B_{i}) and δ_{i} for |B_{i}|^{−1} ∑_{x∈B_{i}} f(x) (that is, the expectation, or “density”, of f in B_{i}) then this sum is ∑_{i=1}^{r} β_{i}δ_{i}^{2}, the average of the squared densities δ_{i}^{2}, with a natural system of weights β_{i}.

The following two simple lemmas are lifted straight out of [G2]. The first is our main tool, while the second is more of a technical trick that will be used in the main result of this section, Lemma 6.3.

Lemma 6.1. Let U be a set of size m 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}/m∥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 m times the mean-square density of f (by definition), so the lemma follows. □

Lemma 6.2. Let m and n be positive integers, let 0 < δ < 1 and let r be an integer greater than or equal to δ^{−1}. Let v_{1}, …, v_{n} be vectors in ℓ_{2}^{m} such that ∥v_{i}∥^{2} ⩽ m for each i and such that ∥∑ v_{i}∥_{2}^{2} ⩽ δn^{2}m. 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}m.

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 δm. If i = j, then ⟨w_{i}, w_{j}⟩ is at most m, again by hypothesis. Therefore, the expectation we are trying to bound is at most (δr(r − 1) + r)m. Since δr ⩾ 1, this is at most 2δr^{2}m, as claimed. □

Before we state the main result of this section, we need two definitions. The first is of a chain D that we shall call a double octahedron. We use this name for conciseness even though it is slightly misleading: in fact, D is the (k − 1)-skeleton of a chain formed from two k-dimensional octahedra by identifying a face from one with the corresponding face from the other. To put this more formally, take the vertex set of D to be the set [k] × {0, 1, 2}. For each i between 1 and k let V_{i} be the set {i} × {0, 1, 2} and for j = 0, 1, 2 let B_{j} be the set [k] × {j}. The edges of D are all sets B of cardinality at most k − 1 such that |B ∩ V_{i}| ⩽ 1 for every i and at least one of B ∩ B_{1} and B ∩ B_{2} is empty. (The two octahedra in question are O_{1} and O_{2}, where O_{j} consists of all sets B ⊂ B_{0} ∪ B_{j} such that |B ∩ V_{i}| ⩽ 1 for every i.)

Notice that if A ⊂ [k] is a set of size at most k − 1 then the number of edges in D of index A is 2^{|A|+1} − 1, since there are 2^{|A|} edges from each octahedron and one, namely A × {0}, which is common to both.

For the second definition, suppose we have a k-partite (k −1)-chain H with vertex sets X_{1}, …, X_{k}. Recall from §2 that H_{∗}([k]) is the collection of all sets A such that |A∩X_{i}| = 1 for every i and such that every proper subset of A belongs to H. For this second condition to hold it is enough for C to be an edge of H whenever C ⊂ A and |C| = k − 1. Let H be the k-partite (k − 1)-uniform hypergraph consisting of all edges of H of size k − 1. For 1 ⩽ i ⩽ k let H_{i} be the (k − 1)-partite subhypergraph of H consisting of all edges of H that have empty intersection with X_{i}. We shall call the hypergraphs H_{i} the parts of H.

Each set A ∈ H_{∗}([k]) has k subsets of size k − 1. Each part H_{i} of H contains exactly one of these subsets, namely A \ X_{i}.

Suppose that each H_{i} is partitioned into subhypergraphs H_{i1}, …, H_{ir_{i}}. These partitions give rise to an equivalence relation ∼ on H_{∗}([k]): we say that A ∼ A′ if, for each i ⩽ k, the sets A \ X_{i} and A′ \ X_{i} belong to the same cell H_{ij} of the partition of H_{i}. The corresponding partition will be called the induced partition of H_{∗}([k]).

Lemma 6.3. Let H be a k-partite (k − 1)-chain with vertex sets X_{1}, …, X_{k}, let D be the double octahedron, let δ = ∏_{A∈D} δ_{A} and let r ⩾ δ^{−1} be a positive integer. Suppose that ϵ ⩽ |D|^{−1}, that H is (ϵ, D, k − 1)-quasirandom and that f : H_{∗}([k]) → [−1, 1] is a function that is not η-quasirandom relative to H. Let H be the set of all edges of H of size k − 1 and let H_{1}, …, H_{k} be the k parts of H. Then there are partitions of the H_{i} into at most 3^{r} sets each such that the mean-square density of f with respect to the induced partition of H_{∗}([k]) is at least η^{2}/8.

We shall prove Lemma 6.3 in stages, by means of some intermediate lemmas. But to begin with, let us examine our main hypothesis, that f is not η-quasirandom relative to H. For each i ⩽ k let U_{i} = {i} × {0, 1} (so U_{i} consists of the “first two” of the three elements of V_{i}). As in §2, let B be the k-partite k-uniform hypergraph consisting of all sets B ⊂ U_{1} ∪ … ∪ U_{k} such that |B ∩ U_{i}| = 1 for every i, let K be the chain of all sets C that are proper subsets of some B ∈ B and let Ω be the set of all k-partite maps from U_{1} ∪ … ∪ U_{k} to X_{1} ∪ … ∪ X_{k}. Then to say that f is not η-quasirandom relative to H is to say that

Oct(f) = ∑_{ω∈Ω} ∏_{B∈B} f^{B}(ω) > η|Ω| ∏_{A∈K} δ_{A} ,

where by f^{B}(ω) we mean f(ω(B)) if ω(B) ∈ H_{∗}([k]) and 0 otherwise.

Let B_{0} and B_{1} be as defined earlier, so that U_{1} ∪ … ∪ U_{k} = B_{0} ∪ B_{1}. Let Φ and Ψ be the set of all k-partite maps from B_{0} and B_{1}, respectively, to X_{1} ∪ … ∪ X_{k}. There is an obvious one-to-one correspondence between Ω and Φ × Ψ: given any ω ∈ Ω, associate with it the pair (ϕ, ψ) where ϕ and ψ are the restrictions of ω to B_{0} and B_{1}. This procedure is invertible: given a pair (ϕ, ψ), define an r-partite map ω by setting ω(x) = ϕ(x) if x ∈ B_{0} and ω(x) = ψ(x) if x ∈ B_{1}. From now on we shall identify Ω with Φ × Ψ and freely pass from one to the other.

Let us split the product ∏_{B∈B} f^{B}(ω) into two parts. We shall write F (ω) for f^{B_{0}}(ω) and G(ω) for ∏_{B∈B,B≠B_{0}} f^{B}(ω). Now if ω = (ϕ, ψ) then F (ω) does not depend on ψ (since it depends only on ω(B_{0}) = ϕ(B_{0})). To emphasize this, we shall write G(ϕ, ψ) for G(ω) and F (ϕ) for F (ω). Our hypothesis now becomes

∑_{ϕ∈Φ} ∑_{ψ∈Ψ} F (ϕ)G(ϕ, ψ) > η|Φ||Ψ| ∏_{A∈K} δ_{A} .

Let us see why this is useful. First, note that there is another obvious one-to-one correspondence, this time between Φ and X_{1} × … × X_{k}. It associates with a map ϕ ∈ Φ the k-tuple (ϕ(1, 0), …, ϕ(k, 0)), and the inverse associates with a k-tuple (x_{1}, …, x_{k}) ∈ ∏_{i=1}^{k} X_{i} the map ϕ : B_{0} → X_{1} ∪ … ∪ X_{k} that takes (i, 0) to x_{i} for each i ⩽ k. Therefore, the function F is basically another way of thinking about f. The inequality above can be regarded as saying that, for an average ψ ∈ Ψ, F has a certain correlation with the function G_{ψ} : ϕ ↦ G(ϕ, ψ). This is significant, because the functions G_{ψ} have a special form, as the next lemma shows.

Lemma 6.4. Each function G_{ψ} : Φ → [−1, 1] can be written as a product of A-functions over sets A ⊂ B_{0} of size k − 1.

Proof. By definition, G_{ψ}(ϕ) = ∏_{B∈B,B≠B_{0}} f^{B}(ϕ, ψ). Now f^{B}(ϕ, ψ) depends on (ϕ, ψ)(B) = ϕ(B ∩ B_{0}) ∪ ψ(B ∩ B_{1}) only. Therefore, if ψ is fixed, f^{B}(ϕ, ψ) depends on ϕ(B ∩ B_{0}) only. Thus, the function ϕ ↦ f^{B}(ϕ, ψ) is a (B ∩ B_{0})-function defined on Φ. Since B ≠ B_{0}, |B ∩ B_{0}| ⩽ k − 1. This proves that G_{ψ} is a product of A-functions over sets A of size at most k − 1. However, if B ⊂ A, then the product of a B-function with an A-function is still an A-function. From this simple observation it now follows that G_{ψ} is a product of A-functions over sets A of size equal to k − 1. □

Our next task is to construct some new functions E_{ψ} out of the G_{ψ} that have very similar properties but take values 0, 1 and −1 only.

Lemma 6.5. There exist functions E_{ψ} : Φ → {−1, 0, 1}, one for each ψ ∈ Ψ, with the following properties. First, E_{ψ}(ϕ) is non-zero only if (ϕ, ψ) ∈ Hom(K, H). Second, each E_{ψ} can be written as a product of {−1, 0, 1}-valued A-functions over subsets A ⊂ B_{0} of size k − 1. Third,

∑_{ϕ∈Φ} ∑_{ψ∈Ψ} F (ϕ)E_{ψ}(ϕ) > η|Φ||Ψ| ∏_{A∈K} δ_{A} .

Proof. Let us fix ψ ∈ Ψ and consider the function G = G_{ψ}. By Lemma 6.4 we can write it as a product of A-functions, where each A in the product is a subset of B_{0} of size k − 1. There are k such sets, namely A_{1}, …, A_{k}, where for each i we set A_{i} = B_{0} \ {(i, 0)}. So we can write G(ϕ) = ∏_{i=1}^{k} g_{i}(ϕ) with g_{i} an A_{i}-function for each i.

Now define an A_{i}-function u_{i} : Φ → {−1, 0, 1} randomly in the following natural way. Say that two maps ϕ and ϕ′ are equivalent if ϕ(A_{i}) = ϕ′(A_{i}) and choose one map from each equivalence class. Let ϕ be one of these representatives. If g_{i}(ϕ) ⩾ 0 then let u_{i}(ϕ) equal 1 with probability g_{i}(ϕ) and 0 with probability 1 − g_{i}(ϕ). If g_{i}(ϕ) < 0 then let u_{i}(ϕ) equal -1 with probability −g_{i}(ϕ) and 0 with probability 1 + g_{i}(ϕ). Then the expectation of u_{i}(ϕ) is g_{i}(ϕ). If ϕ′ is equivalent to ϕ then let u_{i}(ϕ′) = u_{i}(ϕ).

Do the same for each equivalence class and make all the random choices independently. Finally, for each ϕ ∈ Φ let E_{ψ}(ϕ) = ∏_{i=1}^{k} u_{i}(ϕ).

Now E_{ψ}(ϕ) can be non-zero only if u_{i}(ϕ) ≠ 0 for every i, and this is the case (with probability 1) only if g_{i}(ϕ) ≠ 0 for every i, and hence only if G(ϕ) ≠ 0. We defined G(ϕ) to be G_{ψ}(ϕ) = ∏_{B∈B,B≠B_{0}} f^{B}(ϕ, ψ). But f^{B}(ϕ, ψ) = 0 unless (ϕ, ψ)(B) ∈ H_{∗}([k]), and this is true only if (ϕ, ψ)(C) ∈ H for every proper subset C of B. Therefore this product is non-zero only if (ϕ, ψ) is a homomorphism from K to H.

Since the choices of the different functions u_{i} were made independently and the expectation of u_{i}(ϕ) is g_{i}(ϕ), the expectation of u_{1}(ϕ) … u_{k}(ϕ) is g_{1}(ϕ) … g_{k}(ϕ) = G_{ψ}(ϕ). Therefore, by linearity of expectation, the expectation of ∑_{ϕ} ∑_{ψ} F (ϕ)E_{ψ}(ϕ) is ∑_{ϕ} ∑_{ψ} F (ϕ)G_{ψ}(ϕ), which we have assumed to be at least η|Φ||Ψ| ∏_{A∈K} δ_{A}. It follows that we can choose functions E_{ψ} with the desired properties. □

Lemma 6.6. For each ψ ∈ Ψ let E_{ψ} be the function constructed in Lemma 6.5, and let D be the double octahedron chain introduced before the statement of Lemma 6.3. Then

∑_{ϕ∈Φ}( ∑_{ψ∈Ψ} E_{ψ}(ϕ))^{2} ⩽ 2|Φ||Ψ|^{2} ∏_{A∈D} δ_{A} .

Proof. The left-hand side of the inequality we wish to prove can be rewritten

∑_{ϕ∈Φ} ∑_{ψ_{1},ψ_{2}∈Ψ} E_{ψ_{1}}(ϕ)E_{ψ_{2}}(ϕ) .

By Lemma 6.5, E_{ψ_{1}}(ϕ)E_{ψ_{2}}(ϕ) is non-zero if and only if (ϕ, ψ_{1}) and (ϕ, ψ_{2}) belong to Hom(K, H). Therefore, this sum is at most the number of triples (ϕ, ψ_{1}, ψ_{2}) such that (ϕ, ψ_{1}) and (ϕ, ψ_{2}) belong to Hom(K, H).

In order to estimate how many such triples there are, we shall apply the counting lemma to the chain D. Every edge of D is a subset of either B_{0} ∪ B_{1} or B_{0} ∪ B_{2}. Let K_{1} be the set of all edges of the first kind and let K_{2} be the set of all edges of the second kind. Both K_{1} and K_{2} are chains and they intersect in a chain that consists of all proper subsets of B_{0}. Moreover, K_{1} is essentially the same chain as K (formally, it has different vertex sets but the edges are the same). As for K_{2}, it is isomorphic to K in the following sense. Let γ be the bijection from B_{0} ∪ B_{1} to B_{0} ∪ B_{2} that takes (i, 0) to (i, 0) and (i, 2) to (i, 1). Then A is an edge of K_{2} if and only if γ(A) is an edge of K.

Let Θ be the set of all k-partite functions from V_{1} ∪ … ∪ V_{k} (the vertex set of D) to X_{1} ∪ … ∪ X_{k}. There is a one-to-one correspondence between Θ and Φ × Ψ × Ψ taking θ ∈ Θ to (ϕ, ψ_{1}, ψ_{2} ∘ γ), where ϕ, ψ_{1} and ψ_{2} are the restrictions of θ to B_{0}, B_{1} and B_{2}, respectively. Since D = K_{1} ∪ K_{2}, a map θ ∈ Θ belongs to Hom(D, H) if and only if (ϕ, ψ_{1}) belongs to Hom(K_{1}, H) and (ϕ, ψ_{2}) belongs to Hom(K_{2}, H). But this is true if and only if (ϕ, ψ_{1}) and (ϕ, ψ_{2} ∘ γ) belong to Hom(K, H). (Note that ψ_{2} ∘ γ here is the ψ_{2} in the sum that we are estimating.)

What this shows is that the number of triples we wish to count is equal to the cardinality of Hom(D, H). Since we are assuming that H is (ϵ, D, k − 1)-quasirandom and that ϵ ⩽ |D|^{−1}, the counting lemma (Corollary 5.2) implies that this is at most 2|Θ| ∏_{A∈D} δ_{A} = 2|Φ||Ψ|^{2} ∏_{A∈D} δ_{A}, which proves the lemma. □

Our next task is to show that we can make a small selection of the functions E_{ψ} and keep properties similar to those proved in the last two lemmas. The selection will be done in the obvious way: randomly.

Lemma 6.7. Let δ = 2 ∏_{A∈D} δ_{A}, let β = ∏_{A∈K} δ_{A} and let r ⩾ δ^{−1} be a positive integer. Then there exist functions E_{1}, …, E_{r} from Φ to {−1, 0, 1} with the following three properties.

(i) Each function E_{i} is a product of {−1, 0, 1}-valued A-functions over subsets A ⊂ B_{0} of size k − 1.

(ii) For each i and each ϕ ∈ Φ, E_{i}(ϕ) is non-zero only if ϕ(B_{0}) ∈ H.

(iii) ∑_{i=1}^{r} ∑_{ϕ∈Φ} F (ϕ)E_{i}(ϕ) ⩾ (η/2)βr|Φ|.
(iv) ∑_{ϕ∈Φ}(∑_{i=1}^{r} E_{i}(ϕ))^{2} ⩽ (4rδ/ηβ) ∑_{i=1}^{r} ∑_{ϕ∈Φ} F (ϕ)E_{i}(ϕ).

Proof. For each i let E_{i} be one of the functions E_{ψ}, where ψ is chosen uniformly at random from Ψ. Let the choices be independent (so, in particular, the E_{i} are not necessarily distinct, though they probably will be). Then it follows from Lemma 6.5 that property (i) holds, and also that the expectation of ∑_{i=1}^{r} ∑_{ϕ∈Φ} F (ϕ)E_{i}(ϕ) is at least ηβr|Φ|.

We now want to estimate the expectation of ∑_{ϕ∈Φ}(∑_{i=1}^{r} E_{i}(ϕ))^{2}, and for this we shall use Lemma 6.2, the technical lemma from the beginning of the section. Set n = |Ψ| = |Φ| and let the vectors v_{1}, …, v_{n} be the functions E_{ψ}, which we regard as elements of ℓ_{2}(Φ). Lemma 6.6 tells us that ∥∑_{i=1}^{n} v_{i}∥_{2}^{2} ⩽ δn^{3}. Therefore, Lemma 6.2 tells us that the expectation of ∥∑_{i=1}^{r} E_{i}∥_{2}^{2}, which is the same as the expectation of ∑_{ϕ∈Φ}(∑_{i=1}^{r} E_{i}(ϕ))^{2}, is at most 2δr^{2}n = 2δr^{2}|Φ|.

It follows that the expectation of

4rδ ∑_{i=1}^{r} ∑_{ϕ∈Φ} F (ϕ)E_{i}(ϕ) − ηβ ∑_{ϕ∈Φ}(∑_{i=1}^{r} E_{i}(ϕ))^{2}

is at least 4ηβδr^{2}|Φ| − 2ηβδr^{2}|Φ| = 2ηβδr^{2}|Φ|. It follows that there must be some choice of the functions E_{1}, …, E_{r} such that the inequalities (iii) and (iv) are satisfied.

Since each E_{i} is one of the functions E_{ψ}, Lemma 6.5 implies that E_{i}(ϕ) is non-zero only if (ϕ, ψ) ∈ Hom(K, H) for some ψ ∈ Ψ. But a necessary condition for this is that ϕ(B_{0}) ∈ H, so property (ii) is true as well. □

Proof of Lemma 6.3. For each i let us write E_{i} as a product ∏_{j=1}^{k} E_{ij}, where E_{ij} is a {−1, 0, 1}-valued A_{i}-function. (As in the proof of Lemma 6.5, A_{i} is the set B_{0} \ {(i, 0)}.)

For each j ⩽ k we can partition the part H_{j} of H into at most 3^{r} sets, such that on each of these sets the function E_{ij} is constant for every i ⩽ r. Let Z_{1}, …, Z_{N} be the corresponding induced partition of H_{∗}([k]). Then every function E_{i} is constant on every cell Z_{j}, from which it follows that the function g(ϕ) = ∑_{i=1}^{r} E_{i}(ϕ) is constant on every cell Z_{j}.

We are now in a position to apply Lemma 6.1. Property (ii) of Lemma 6.7 tells us that ⟨F, g⟩ ⩾ (η/2)βr|Φ|, and property (iii) tells us that ⟨F, g⟩/∥g∥_{2}^{2} ⩾ ηβ/4rδ. Let U be the set of all ϕ ∈ Φ such that ϕ(B_{0}) ∈ H_{∗}([k]). The map ϕ ↦ ϕ(B_{0}) is a bijection between U and H_{∗}([k]), so we can regard Z_{1}, …, Z_{N} as a partition of U.

Lemma 6.7 and these estimates tell us that the mean-square density of F with respect to this partition is at least

\frac{(η/2)βr|Φ|}{|U|} · \frac{ηβ}{4rδ} = \frac{η^{2}β^{2}|Φ|}{8δ|U|} .

We also know that |U| = |Φ| ∏_{A⊊B_{0}} δ_{A}. Recall that every set A ⊂ B_{0} is the index of precisely 2^{|A|+1}−1 sets in D and 2^{|A|} sets in K. It follows that β^{2} = δ ∏_{A⊊B_{0}} δ_{A}. Therefore, the mean-square density of F with respect to the partition Z_{1}, …, Z_{N} is at least η^{2}/8. Since F (ϕ) = f(ϕ(B_{0})), this statement is equivalent to the statement of Lemma 6.3. □

Corollary 6.8. Let H be a k-partite (k − 1)-chain with vertex sets X_{1}, …, X_{k}, let D be the double octahedron, let δ = ∏_{A∈D} δ_{A} and let r ⩾ δ^{−1} be a positive integer. Suppose that ϵ ⩽ |D|^{−1} and that H is (ϵ, D, k − 1)-quasirandom. Let H^{k} be a k-partite k-uniform hypergraph with vertex sets X_{1}, …, X_{k}, let the density of H^{k} relative to H (that is, the quantity |H^{k}|/|H_{∗}([k])) be δ_{[k]} and suppose that H^{k} is not η-quasirandom relative to H. Let H be the set of all edges of H of size k−1 and let H_{1}, …, H_{k} be the k parts of H. Then there are partitions of the H_{i} into at most 3^{r} sets each such that the mean-square density of (the characteristic function of) H^{k} with respect to the induced partition of H_{∗}([k]) is at least δ_{[k]}^{2} + η^{2}/8.

Proof. Let f : H_{∗}([k]) → [−1, 1] be the function H^{k} − δ_{[k]}. Then the statement that H^{k} is not η-quasirandom relative to H is, by definition, the statement that f is not ηquasirandom relative to H. Therefore, by Lemma 6.3, we can find partitions of the required kind for which the mean-square density of f with respect to the induced partition of H_{∗}([k]) is at least η^{2}/8.

Let Z_{1}, …, Z_{N} be the induced partition of H_{∗}([k]) and for each (x_{1}, …, x_{k}) ∈ Z_{i} let G(x_{1}, …, x_{k}) = |H^{k} ∩ Z_{i}|/|Z_{i}|. Then the mean of G is the same as the mean of H^{k}, namely δ_{[k]}. The variance of G is the mean-square density of f. The result follows. □

§7. The statement of a regularity lemma for r-partite chains.

Corollary 6.8 is stage one of the proof of our regularity lemma. In this short section we will introduce some definitions and state the lemma. The proof (or rather, stage two of the proof) will be given in §9.

Broadly speaking, the lemma says that we can take a k-uniform hypergraph H, regard it as a chain (by adding all subsets of edges of H) and decompose that chain into subchains almost all of which are quasirandom. This is a useful thing to do, because Corollary 5.2 gives us a good understanding of quasirandom chains. Thus, the regularity lemma and counting lemma combine to allow us to decompose any (dense) k-uniform hypergraph into pieces that we can control. In the final section of the paper we shall exploit this by proving a generalization of Theorems 1.3 and 1.6 to k-uniform hypergraphs, which implies the multidimensional Szemerédi theorem.

Our principal aim will be to understand a certain (k+1)-partite k-uniform hypergraph. However, for the purposes of formulating a suitable inductive hypothesis it is helpful to prove a result that is more general in two ways. First of all, we shall look at r-partite k-uniform hypergraphs. Secondly, rather than looking at single hypergraphs we shall look at partitions. To be precise, let X_{1}, …, X_{r} be a sequence of finite sets. Given any subset A ⊂ [r], A = {i_{1}, …, i_{s}}, let K(A) be the complete s-uniform hypergraph on the sets X_{i_{1}}, …, X_{i_{s}}, that is, the hypergraph consisting of all subsets of X_{1} ∪ … ∪ X_{r} of index A. (It is part of the definition of “index” that such a set should intersect each X_{i} in at most a singleton.) For each s ⩽ r, the complete s-uniform hypergraph K_{s} = K_{s}(X_{1}, …, X_{r}) on the sets X_{1}, …, X_{r} is the union of the hypergraphs K(A) over all sets A ⊂ [r] of size s. Finally, the complete k-chain on X_{1}, …, X_{r}, denoted K_{k}(X_{1}, …, X_{r}), is the union of all K(A) such that A has cardinality at most k: that is, it consists of all subsets of X_{1}∪…∪X_{r} of size at most k that intersect each X_{i} at most once.

To form an arbitrary r-partite s-uniform hypergraph H with vertex sets X_{1}, …, X_{r}, one can choose, for each A ⊂ [r] of size s, a subset H(A) ⊂ K(A) and let H be the union of these hypergraphs H(A). If we want to, we can regard each H(A) as a partition of K(A) into the two sets H(A) and K(A) \ H(A). Our regularity lemma will be concerned with more general partitions, but it will imply a result for hypergraphs as an easy corollary.

Suppose now that for every subset A ⊂ [r] of size at most k we have a partition of the hypergraph K(A). If B and B′ are two edges of this hypergraph (that is, if they are two sets of index A), let us write B ∼_{A} B′ if B and B′ lie in the same cell of the partition, and say that B and B′ are A-equivalent.

One can use these equivalence relations to define finer ones as follows. Given two sets B, B′ of index A and given any subset C ⊂ A, there are unique subsets D ⊂ B and D′ ⊂ B of index C. Let us say that B and B′ are C-equivalent if D and D′ are. Then let us say that B and B′ are strongly equivalent if they are C-equivalent for every subset C ⊂ A.

Given this system of equivalence relations, we can define a collection of chains as follows. For every r-tuple x = (x_{1}, …, x_{r}) ∈ X_{1} × … × X_{r} and every set A of size at most k, let x(A) be the set {x_{i} : i ∈ A} and let H(A, x) be the hypergraph consisting of all sets B that are strongly equivalent to x(A).

Lemma 7.1. The union H = H(x) of the hypergraphs H(A, x) over all sets A of size at most k is an r-partite k-chain.

Proof. Let B ∈ H(A, x) and let D ⊂ B. Let C be the index of D. Since B is strongly equivalent to x(A), D is strongly equivalent to x(C). Therefore D ∈ H(C, x) and the lemma is proved. □

Lemma 7.2. Let x = (x_{1}, …, x_{r}) and y = (y_{1}, …, y_{r}) belong to the set X_{1} × … × X_{r} and let H(x) and H(y) be the two chains constructed as above. Then for every set A ⊂ [r] of size at most k, the hypergraphs H(A, x) and H(A, y) are either equal or disjoint.

Proof. Suppose that B is a set of index A and that B ∈ H(A, x) ∩ H(A, y). Then B is strongly equivalent to both x(A) and y(A), so these two sets are strongly equivalent to each other. It follows that H(A, x) = H(A, y). □

Let us call two r-partite k-chains H and H′ with the same vertex sets X_{1}, …, X_{r} compatible if, for every subset A ⊂ [r] of size at most k, the hypergraphs H(A) and H′(A) are either equal or disjoint. By a chain decomposition of the complete r-partite k-chain K_{k}(X_{1}, …, X_{r}) we mean a set {H_{1}, …, H_{N}} of chains with the following two properties:

(i) for every i and j the chains H_{i} and H_{j} are compatible; (ii) for every sequence (x_{1}, …, x_{r}) ∈ X_{1} × … × X_{r} there is precisely one chain from the set {H_{1}, …, H_{N}} that contains every subset of {x_{1}, …, x_{r}} of size at most k.

Note that a chain decomposition is not a partition of K_{k}(X_{1}, …, X_{r}). There is no interesting way to partition K_{k}(X_{1}, …, X_{r}) into subchains, as a moment’s thought will reveal. Lemmas 7.1 and 7.2 shows that the chains H(x) form a chain decomposition of K_{k}(X_{1}, …, X_{r}). (It may be that H(x) = H(y), but this does not contradict (ii) because we have carefully defined a chain decomposition to be a set of chains rather than a sequence of chains.)

We are now ready to state our regularity lemma.

Theorem 7.3. Let J be an r-partite k-chain with vertex sets E_{1}, …, E_{r} and let 0 < ϵ ⩽ |J |^{−1}. Let X_{1}, …, X_{r} be a sequence of finite sets and for each subset A ⊂ [r] of size at most k let P(A) be a partition of the hypergraph K(A) into n_{A} sets. Then there are refinements Q(A) of the partitions P(A) leading to a chain decomposition of K_{k}(X_{1}, …, X_{r}) with the following property: if x = (x_{1}, …, x_{r}) is a randomly chosen element of X_{1} × … × X_{r} then the probability that the chain H(x) is (ϵ, J , k)-quasirandom is at least 1 − ϵ. Moreover, Q(A) = P(A) when |A| = k, and for general A the number of sets m_{A} in the partition Q(A) depends only on ϵ, J, k and the numbers n_{C}.

Before we start on the proof, let us comment on how we shall actually use Theorem 7.3. We will be presented with an r-partite k-uniform hypergraph H with vertex sets X_{1}, …, X_{r}. All the \binom{r}{k} k-partite parts H(A) of H will have density at least a certain fixed δ > 0. We shall then apply Theorem 7.3 to the partitions P(A) defined as follows. If |A| = k then P(A) will be {H(A), K(A) \ H(A)}. If |A| < k then it will be the trivial partition {K(A)}. In this case, the result will tell us that we can find partitions Q(A) such that almost all edges of H lie in quasirandom chains from the decomposition determined by the partitions Q(A).

§8. Basic facts about partitions and mean-square density.

In order to prove a regularity lemma for systems of partitions, we need to generalize the notion of mean-square density as follows. Let P = {X_{1}, …, X_{r}} and Q = {Y_{1}, …, Y_{s}} be two partitions of a finite set U. Then the mean-square density of P with respect to Q is the quantity

∑_{i=1}^{r} ∑_{j=1}^{s} \frac{|Y_{j}|}{|U|} (\frac{|X_{i} ∩ Y_{j}|}{|Y_{j}|})^{2} ,

that is, the sum of all the mean-square densities of the sets X_{i} (that is, the mean-square densities of their characteristic functions, as defined in §6) with respect to Q.

Since the numbers |X_{i} ∩ Y_{j}|/|Y_{j}| are non-negative and sum to 1, we have the simple upper bound

∑_{i=1}^{r} ∑_{j=1}^{s} \frac{|Y_{j}|}{|U|} (\frac{|X_{i} ∩ Y_{j}|}{|Y_{j}|})^{2} ⩽ ∑_{j=1}^{s} \frac{|Y_{j}|}{|U|} = 1

for this quantity. An alternative way of seeing this, which will be helpful later, is to notice that each u ∈ U is contained in a unique X_{i} and a unique Y_{j}, and the mean-square density of P with respect to Q is the expected value of |X_{i} ∩ Y_{j}|/|Y_{j}|.

Lemma 8.1. Let P = {X_{1}, …, X_{r}} and Q = {Y_{1}, …, Y_{s}} be two partitions of a finite set U, and let Q′ be a refinement of Q. Then the mean-square density of P with respect to Q′ is at least as great as the mean-square density of P with respect to Q.

Proof. Let the sets that make up Q′ be called Y_{jk}, where Y_{j} = ⋃_{k} Y_{jk}. For each j and k define γ_{j} and γ_{jk} by |Y_{j}| = γ_{j}|U| and |Y_{jk}| = γ_{jk}|U|. For each i, j and k let d_{ij} = |X_{i} ∩ Y_{j}|/|Y_{j}| and let d_{ijk} = |X_{i} ∩ Y_{jk}|/|Y_{jk}|. Then

∑_{k} d_{ijk}|Y_{jk}| = ∑_{k} |X_{i} ∩ Y_{jk}| = |X_{i} ∩ Y_{j}| = d_{ij}|Y_{j}| ,

from which it follows that ∑_{k} γ_{jk}d_{ijk} = γ_{j}d_{ij} for every i and j.

The mean-square density of P with respect to Q is ∑_{i} ∑_{j} γ_{j}d_{ij}^{2}, which is therefore equal to

\begin{aligned}∑_{i} ∑_{j} γ_{j}^{−1}(∑_{k} γ_{jk}d_{ijk})^{2} & = ∑_{i} ∑_{j}(∑_{k} γ_{j}^{−1/2}γ_{jk}d_{ijk})^{2} \\ & ⩽ ∑_{i} ∑_{j}(∑_{k} γ_{j}^{−1}γ_{jk})^{2}(∑_{k} γ_{jk}d_{ijk}^{2}) , \end{aligned}

by the Cauchy-Schwarz inequality. Since ∑_{k} γ_{j}^{−1}γ_{jk} = 1 for every j, this equals ∑_{i} ∑_{j} ∑_{k} γ_{jk}d_{ijk}^{2}, which is the mean-square density of P with respect to Q′. □

The next lemma is a simple, but somewhat irritating, technicality.

Lemma 8.2. Let ϵ > 0, let X_{1}, …, X_{r} be a sequence of finite sets, let K(X_{1}, …, X_{r}) be the complete r-partite k-chain with vertex sets X_{1}, …, X_{r} and for each A of size at most k let P(A) be a partition of K(A) into n_{A} sets. For each x = (x_{1}, …, x_{r}) ∈ X_{1} × … × X_{r} and each A of size at most k let δ_{A,x} be the relative density of the hypergraph H(A, x) in the chain H(x) (defined in the previous section). Then if (x_{1}, …, x_{r}) is chosen randomly from X_{1} × … × X_{r} and A ⊂ [r] has size at most k, the probability that δ_{A,x} < ϵn_{A}^{−1} is at most ϵ.

Proof. Let B and B′ be two sets of index A. Let us call them weakly equivalent, and write B ∼_{∗} B′, if B is C-equivalent to B′ for every proper subset C. Then B is strongly equivalent to B′ if and only if B ∼_{∗} B′ and B ∼_{A} B′.

The relative density δ_{A,x} is simply the probability that a set B of index A is strongly equivalent to x(A) given that it is weakly equivalent to A. Since K(A) is partitioned into n_{A} sets, the number of strong equivalence classes in each weak equivalence class is at most n_{A}. Therefore, for any weak equivalence class T, the probability that x(A) lies in a strong equivalence class of size less than ϵn_{A}^{−1}|T | given that it lies in T is at most ϵ. If x(A) lies in a strong equivalence class of size at least ϵn_{A}^{−1}|T |, then the probability that B is in the same strong equivalence class given that B is in T is at least ϵn_{A}^{−1}, which implies that δ_{A,x} ⩾ ϵn_{A}^{−1}.

Therefore, for every T the conditional probability that δ_{A,x} < ϵn_{A}^{−1} given that x(A) ∈ T is less than ϵ. The result follows. □

We now have all the ingredients needed to prove our regularity lemma.

§9. The proof of Theorem 7.3.

It will be convenient for the proof if J contains the double octahedron D. Since the result for J follows from the result for J ∪ D, we are free to assume that this is the case.

Let us describe an inductive procedure for producing better and better systems of partitions. Then we shall prove that the procedure terminates.

Suppose, then, that for all subsets A ⊂ [r] of size at most k we have a partition P(A) of the hypergraph K(A) into t_{A} sets. (For ease of notation, we are using the letter P, but these partitions are not the initial partitions in the statement of the theorem.) Suppose, moreover, that if x = (x_{1}, …, x_{r}) is chosen randomly from X_{1} × … × X_{r}, then there is a probability of at least ϵ that the chain H(x) fails to be (ϵ, J , k)-quasirandom.

Let γ be defined by 2γ ∑_{i=1}^{k} \binom{r}{i} = ϵ. By Lemma 8.2, the probability that there exists a subset A ⊂ [r] of size at most k such that δ_{A} < γt_{A}^{−1} is at most γ ∑_{i=1}^{k} \binom{r}{i} = ϵ/2. Therefore, with probability at least ϵ/2, the chain H(x) fails to be (ϵ, J , k)-quasirandom but for each A the relative density δ_{A,x} is at least γt_{A}^{−1}.

In order to continue with the argument, we must use the detailed definition of “(ϵ, J , k)-quasirandom” that immediately precedes Theorem 5.1. Let η_{2}, …, η_{s} and ϵ_{2}, …, ϵ_{k} be the sequences that appear in that definition, and note that η_{s} depends only on ϵ and the densities δ_{A,x} with |A| ⩾ s. Since δ_{A,x} ⩾ γt_{A}^{−1} for every A, it follows that η_{s} is bounded below by a function of ϵ and all those t_{A} for which |A| ⩾ s.

If H(x) fails to be (ϵ, J , k)-quasirandom, there must be a minimal s such that it fails to be (ϵ_{s}, J , s)-quasirandom, and for that s there must be a set A of size s such that H(A, x) is not η_{s}-quasirandom relative to H(x), while H(x) is (ϵ_{s−1}, J , s − 1)-quasirandom. Since there are at most ∑_{i=1}^{k} \binom{r}{i} possibilities for this set A we may deduce from the previous paragraph that there exists a set A of size s ⩽ k such that, with probability at least γ, the chain H(x) is (ϵ_{s−1}, J , s − 1)-quasirandom but H(A, x) is not η_{s}-quasirandom relative to H(x).

Let us call x irregular if H(x) has these two properties. Given an irregular x, let H_{−}(A, x) be the s-partite (s − 1)-chain consisting of all strong equivalence classes H(C, x) with C ⊊ A. We can now apply Corollary 6.8 to the chain H_{−}(A, x) and to the suniform hypergraph H(A, x). (Thus, the k of Corollary 6.8 is equal to s here.) Since ϵ_{s−1} ⩽ ϵ ⩽ |J |^{−1}, the conditions hold for the corollary to be applicable. The hypergraphs H_{1}, …, H_{k} in the statement of Corollary 6.8 are, in this context, the hypergraphs H(A′, x), where A′ ranges over all subsets of A of size s − 1.

For each C ⊊ A we know that δ_{C,x} ⩾ γt_{C}^{−1}. Therefore, if r is a positive integer that is at least ∏_{C⊊A} γ^{−1}t_{C}, then for each subset A′ ⊂ A of size s − 1 we can find a partition of H(A′, x) into at most 3^{r} subsets, in such a way that the mean-square density of H(A, x) with respect to the induced partition of H_{∗}(A, x) is at least δ_{A,x}^{2} + η_{s}^{2}/8. (Here, H_{∗}(A, x) denotes the hypergraph consisting of all sets Y of index A such that every proper subset of Y belongs to H_{−}(A, x).)

Let H(A, x) be the s-partite s-chain H(A, x)∪H_{−}(A, x). The number of distinct such chains is at most ∏_{C⊂A} t_{C}. For each one such that x is irregular (if H(A, x) = H(A, y) and x is irregular then y is irregular) choose a partition of the hypergraphs H(A′, x) as above. In general, it will often happen that H(A, x) ≠ H(A, y) but H(A′, x) = H(A′, y), so each hypergraph H(A′, x) may be partitioned many times. However, the number of distinct chains H(A, x) is at most T_{A} = ∏_{C⊂A} t_{C}, so we can find a common refinement of all the partitions of H(A′, x) into at most 3^{rT_{A}} sets.

For each A′ ⊂ A of size s − 1 let Q(A′) be the union of all these common refinements, over all the different sets H(A′, x). Then Q(A′) is a partition of K(A′) into at most T_{A′}3^{rT_{A}} sets, and it refines P(A′). For all other sets A, let Q(A) = P(A).

By Lemma 8.1, given any irregular x, the mean-square density of H(A, x) with respect to the partition of H_{∗}(A, x) that is induced by the refined partitions of the hypergraphs H(A′, x) is still at least δ_{A,x}^{2} + η_{s}^{2}/8. As for a regular x, Lemma 8.1 tells us that the mean-square density of H(A, x) with respect to the refined partition of H(x)_{∗}(A) is still at least δ_{A,x}^{2}.

Let σ_{A}(P) be the mean-square density of the partition P(A) with respect to the partition of K(A) into weak equivalence classes coming from the partitions P(C). Let σ_{A}(Q) be the mean-square density of P(A) = Q(A) with respect to the partition of K(A) arising from Q in the same way. By the remark preceding Lemma 8.1, ρ_{A} is the expectation of δ_{A,y} over all sequences y = (y_{1}, …, y_{r}). Let us write this as δ_{A,y}(P) since it depends on the system of partitions P(C). Then we can say that σ_{A} is the expectation of δ_{A,x}(Q).

What we have just shown is that if x is irregular, then 𝔼[δ_{A,y}(Q)|y ∈ H(A, x)] is at least δ_{A,y}(P)^{2} + η_{s}^{2}/8, which equals 𝔼[δ_{A,y}(P)|y ∈ H(A, x)] + η_{s}^{2}/8. If x is regular, then this conditional expectation is at least δ_{A,y}(P)^{2}, or 𝔼[δ_{A,y}(P)|y ∈ H(A, x)]. Since the probability that x is irregular is at least γ, this shows that 𝔼[δ_{A,y}(Q)] ⩾ 𝔼[δ_{A,y}(P)]+γη_{s}^{2}/8. In other words, σ_{A}(Q) ⩾ σ_{A}(P) + γη_{s}^{2}/8.

To summarize: if the conclusion of Theorem 7.3 is not true for the partitions P(C) then there is a set A of size s ⩽ k and a system of refinements Q(C) such that Q(C) = P(C) except when C is a subset of A of size s − 1, such that σ_{A}(Q) ⩾ σ_{A}(P) + γη_{s}^{2}/8. For a general C, we have σ_{C}(Q) ⩾ σ_{C}(P) except if C ⊂ A and |C| = s − 1. This is because if C is any other set, then Q(C) = P(C) and all other partitions have either been refined or stayed the same.

To see that we cannot iterate this process of successive refinement for ever, let us see why we are performing an induction over a complicated well-ordered set. The objects in the set will be functions ζ : [r]^{(⩽k)} → ℕ, where [r]^{(⩽k)} stands for the collection of subsets of [r] of size at most k. Let these be well-ordered as follows. First, let ⩽ be an ordering on [r]^{(⩽k)} such that A ⩽ C whenever |A| ⩾ |C|. (In other words, large sets come first in the ordering.) Then let ζ < ζ′ if there exists a set A ∈ [r]^{(⩽k)} such that ζ(C) = ζ′(C) for every C ⩽ A and ζ(A) < ζ′(A). This is clearly a well-ordering: it is a lexicographical ordering with respect to the ordering ⩽ on [r]^{(⩽k)}.

To each system of partitions P(A) we associate such a function ζ_{P} as follows. Let t_{A} and γ be defined as they were earlier in this proof. For each A ⊂ [r] of size at most k let d_{A} = γt_{A}^{−1}. Then let η_{2}, …, η_{k} be defined as they are in the definition of (ϵ, J , k)- quasirandomness, except that δ_{A} is replaced by d_{A}. (These numbers d_{A} are lower bounds for the densities associated with a typical chain H(x).) Finally, if |A| = s then let ζ_{P}(A) be the smallest integer greater than 8(1 − σ_{A}(P))/γη_{s}^{2}.

The number ζ_{P}(A) is chosen because it is an upper bound for the number of increases of γη_{s}^{2}/8 that it is possible to make to σ_{A}(P). Now when we replaced P by Q above, we had a number s ⩽ k and a set A of size s such that P(C) = Q(C) for every set C that is not a subset of A of size s − 1. In particular, the values of d_{C} for Q are as they were for P for every set C of size s or greater. It follows that η_{s} is the same for Q as it is for P. Since σ_{A}(Q) ⩾ σ_{A}(P) + γη_{s}^{2}/8, we therefore find that ζ_{Q}(A) < ζ_{P}(A). For all C ⩽ A we have ζ_{Q}(C) = ζ_{P}(C), so we have shown that ζ_{Q} < ζ_{P}.

This proves that the iterations come to an end. To complete the proof of Theorem 7.3, we observe that at any given stage of the iteration, if we replace partitions P(A) of size t_{P}(A) by partitions Q(A) of size t_{Q}(A), then each number t_{Q}(C) is bounded above by a monotone increasing function of the t_{P}(A) only. So as the iteration proceeds we have a sequence of pairs of functions (ζ_{P}, t_{P}) such that the ζ_{P} form a decreasing sequence and such that if Q follows P then every ζ_{Q}(C) and t_{Q}(C) is bounded above by a function of (ζ_{P}, t_{P}) that is monotone increasing in each t_{P}(A). Therefore, the values of t_{Q}(C) when Q is the final system of partitions in the sequence are bounded above by a function that depends only on the values of the initial t_{P}. □

§10. Hypergraphs with few simplices.

Now that we have established counting and regularity lemmas we have the tools necessary to prove the generalization of Theorems 1.3 and 1.6 to k-uniform hypergraphs.

Theorem 10.1. Let k be a positive integer. Then for every a > 0 there exists c > 0 with the following property. Let H be a (k + 1)-partite k-uniform hypergraph with vertex sets X_{1}, …, X_{k+1}, and let N_{i} be the size of X_{i}. Suppose that H contains at most c ∏_{i=1}^{k+1} N_{i} simplices. Then for each i ⩽ k + 1 one can remove at most a ∏_{j≠i} N_{j} edges of H from ∏_{j≠i} X_{j} in such a way that after the removals one is left with a hypergraph that is simplexfree.

Proof. For each subset A ⊂ [k + 1] of size at most k, define a partition P(A) of K(A) as follows. If |A| < k then P(A) consists of the single set K(A). If |A| = k then it consists of the sets H(A) and K(A) \ H(A). Now apply Theorem 7.3 to this system of partitions, with J = [k + 1]^{(⩽k)} and ϵ = min{|J |^{−1}/2, a/2}, obtaining for each A ∈ J a partition Q(A) of K(A) into m_{A} sets.

If x = (x_{1}, …, x_{k+1}) ∈ X_{1} × … × X_{k+1} and H(x) is not (ϵ, J , k)-quasirandom, then there must be some A of size s ⩽ k such that H(A, x) is not η_{s}-quasirandom relative to H(x). There must be some i such that i ∉ A and if (y_{1}, …, y_{k+1}) is another sequence such that y_{j} = x_{j} when j ≠ i, then H(A, y) will also not be η_{s}-quasirandom relative to H(y). Therefore, since H(x) is (ϵ, J , k)-quasirandom with probability at least 1 − ϵ, there are at most ϵ ∏_{j≠i} N_{j} elements of ∏_{j≠i} X_{j} that can be extended to sequences x that are not (ϵ, J , k)-quasirandom. Remove from H any such element.

Let γ be defined by γ ∑_{i=1}^{k} \binom{k+1}{i} = a/2. Then Lemma 8.2 tells us that if x = (x_{1}, …, x_{k+1}) is chosen randomly, then with probability at least 1 − a/2, we have δ_{A,x} ⩾ γm_{A}^{−1} for every A ∈ [k + 1]^{(⩽k)}. Again, the event that this happens for a particular A does not depend on the x_{i} with i ∉ A. So for each i there are at most a ∏_{j≠i} N_{j}/2 elements of ∏_{j≠i} X_{j} that can be extended to sequences x for which δ_{A,x} < γm_{A}^{−1} for some A ⊂ [k + 1] with i ∉ A. Once again, remove all such elements from H.

For each i we have removed at most a ∏_{j≠i} N_{j} from H ∩ ∏_{j≠i} X_{j}. It remains to show that in the process we have either removed all simplices from H, or else, for some c > 0 that depends on a only, there were at least c ∏_{j} N_{j} simplices to start with.

Suppose, then, that after the removals there is still a simplex x = (x_{1}, …, x_{k+1}), and consider the chain H(x). Then for every A ⊂ [k + 1] of size k the following statements are true. First, the set x(A) is an element of H (or else x would not be a simplex). Second, the hypergraph H(A, x) is a subset of H (since x(A) ∈ H and the partition into strong equivalence classes resulting from Q refines the partition P). Third, δ_{C,x} ⩾ γm_{C}^{−1} for every C ⊂ A (or else we would have removed x(A) from H). Finally, the chain H(x) is (ϵ, J , k)-quasirandom (or else for some A of size k we would have removed x(A) from H).

We now apply Corollary 5.2, the counting lemma for quasirandom chains. It implies that the number of simplices in the chain H(x), which is the same as the number of homomorphisms from J to H(x), is at least ∏_{j} N_{j} ∏_{A∈J} δ_{A,x}, which is at least ∏_{j} N_{j} ∏_{A∈J} γm_{A}^{−1}. But γ and the m_{A} depend on a and k only, so the result is proved. □

Finally, let us deduce from this a multidimensional Szemerédi theorem. Theorem 10.2. Let δ > 0 and k ∈ ℕ. Then, if N is sufficiently large, every subset A of the k-dimensional grid {1, 2, …, N}^{k} of size at least δN^{k} contains a set of points of the form {a} ∪ {a + de_{i} : 1 ⩽ i ⩽ k}, where e_{1}, …, e_{k} is the standard basis of ℝ^{k} and d is a non-zero integer. Proof. Suppose that A is a subset of {1, 2, …, N}^{k} of size δN^{k}, and that A contains no configuration of the kind claimed. Define a (k + 1)-partite k-graph F_{k} with vertex sets X_{1}, …, X_{k+1} as follows. If j ⩽ k then the elements of X_{j} are hyperplanes of the form P_{j,m} = {(x_{1}, …, x_{k}) : x_{j} = m} for some integer m ∈ {1, 2, …, N}. If j = k + 1 then they are hyperplanes of the form Q_{m} = {(x_{1}, …, x_{k}) : x_{1} + … + x_{k} = m} where m is an integer between k and kN. The edges of F_{k} are sets of k hyperplanes from different sets V_{j} that intersect in a point of A.

If F_{k} contains a simplex with vertices P_{j,m_{j}} and Q_{m}, then the points (m_{1}, …, m_{k}) and (m_{1}, …, m_{k}) + (m − ∑_{i=1}^{k} m_{i})e_{j} all belong to A. This gives us a configuration of the desired kind except in the degenerate case where m = ∑_{i=1}^{k} m_{i}, which is the case where all k + 1 hyperplanes have a common intersection. By our assumption on A, all the simplices in F_{k} are therefore degenerate ones of this kind, which implies that there are at most δN^{k} of them.

Now |X_{i}| = N if i ⩽ k and |X_{k+1}| = kN. We can therefore apply (the contrapositive of) Theorem 10.1 with c = N^{−1}k^{−1}. If N is sufficiently large, then the resulting a is smaller than δ/2k, which implies that we can remove fewer than δN^{k} edges from the hypergraph F_{k} and thereby remove all simplices. However, every edge of a degenerate simplex determines the point of intersection of the k + 1 hyperplanes and hence the simplex itself. It follows that one must remove at least δN^{k} edges to get rid of all simplices. This contradiction proves the theorem. □

The above result is a special case of the multidimensional Szemerédi theorem, but it is in fact equivalent to the whole theorem. This is a well-known observation. We give a (slightly sketchy) proof below. Theorem 10.3. For every δ > 0, every positive integer r and every finite subset X ⊂ ℤ^{r} there is a positive integer N such that every subset A of the grid {1, 2, …, N}^{r} of size at least δN^{r} has a subset of the form a + dX for some positive integer d. Proof. It is clearly enough to prove the result for sets X such that X = −X, so all we actually need to ensure is that d ≠ 0. A simple averaging argument shows that we may also assume that X is not contained in any (r − 1)-dimensional subspace of ℝ^{r}. Let the cardinality of X be k + 1. Let ϕ be an affine map that defines a bijection from the set {0, e_{1}, …, e_{k}} ⊂ ℝ^{k} to X, regarded as a subset of ℝ^{r}. Another simple averaging argument allows us to find a grid {1, 2, …, M}^{k}, where M tends to infinity with N, as well as a point z ∈ ℤ^{r} and a constant η > 0 depending on δ and X only, such that z + ϕ(x) ∈ A for at least ηM^{k} points in {1, 2, …, M}^{k}. Let B be the set of points with this property. Thus, B has density at least η and Theorem 10.2 shows that B contains a set of the form w + c{0, e_{1}, …, e_{k}}. But then z + ϕ(w + c{0, e_{1}, …, e_{k}}) is a set of the form a + dX and is also a subset of A. □

Concluding Remarks.

I am very grateful indeed to Yoshiyasu Ishigami, who read carefully an earlier version of this paper and found an error which, though it did not invalidate the approach, occurred early in the argument and therefore required more than local changes to it. While thinking about how to deal with it, I discovered a way of substantially simplifying the proof of the counting lemma, and in the end it seemed best, even if depressing, to rewrite the whole paper (including the regularity part) from scratch.

Recently, Tao [T] has given another proof of the main result of this paper (Theorem 10.1), and indeed of a slight generalization. He also proves regularity and counting lemmas, by methods more closely related to those of Nagle, Rödl and Schacht, but with some new ideas and a different language that leads to considerably shorter proofs.

References.

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

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

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

[G2] W. T. Gowers, Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs, submitted.

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

[R] V. Rödl, Some developments in Ramsey theory, Proceedings of the International Congress of Mathematicians, Vol. I, II (Kyoto 1990), 1455-1466, Math. Soc. Japan, Tokyo, 1991.

[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.

[Sz1] E. Szemerédi, Integer sets containing no k elements in arithmetic progression, Acta Arith. 27 (1975), 299-345.

[Sz2] E. Szemerédi, Regular partitions of graphs, in Problèmes Combinatoires et Théorie des Graphes, Proc. Colloque Inter. CNRS, (Bermond, Fournier, Las Vergnas, Sotteau, eds.), CNRS Paris, 1978, 399-401.

[T] T. Tao, A variant of the hypergraph removal lemma, preprint.