Hypergraph regularity and the multidimensional Szemerédi theorem

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, Schacht and Skokan.first, but in some sense simpler, so that we could generalize both statements to one that can be proved inductively.Certain similarities are immediately clear, as is the fact that the last expression, if we fix x and x rather than taking the first expectation, involves functions of two variables rather than three, and a fourth power instead of an eighth power.The only small difference is that we now have the function G appearing rather than some arbitrary function supported in G.This we shall have to incorporate into our inductive hypothesis somehow.However, in this small case, we can simply try to repeat the argument, so let us continue with the calculation:Here, we used the fact that f x,x (y, z) is nonzero only if G(x, z) and G(x , z) are both equal to 1, with a similar statement for u x,x (y, t).We then applied the Cauchy-Schwarz inequality together with the fact that G squares to itself.Given that G could be quite sparse, it was important here that we exploited its sparseness to the full: with a lazier use of the Cauchy-Schwarz inequality we would not have obtained the factor in the first bracket, which will in general be small and not something we can afford to forget about.Now let us continue to manipulate the second bracket in the standard way: expanding the inner square, rearranging, and applying Cauchy-Schwarz.This time, in order not to throw away any sparseness information, we will bear in mind that the expectation over y and y below is zero unless all of G(x, y), G(x , y), G(x, y ) and G(x , y ) are equal to 1.