DHJ(k) implies multidimensional DHJ(k)

From Polymath1Wiki

Introduction

This is a result that will be needed if the proof of DHJ(3) is correct and we want to push it through for DHJ(k).

The proof

Let be a density-δ subset of [k]ⁿ and let M be large enough so that every subset of [k]^M of density at least θ contains a combinatorial line. Now split [k]ⁿ up into For a proportion at least δ / 2 of the points y in [k]^{n − M} the set of such that has density at least δ / 2. Therefore, by DHJ(k) (with θ = δ / 2) we have a combinatorial line. Since there are fewer than (k + 1)^M combinatorial lines to choose from, by the pigeonhole principle we can find a combinatorial line and a set of density δ / 2(k + 1)^M in [k]^{n − M} such that whenever and And now by induction we can find an (m-1)-dimensional subspace in and we're done.

A weak multidimensional DHJ(k) implies DHJ(k)

It is also true that a weak multidimensional DHJ(k) implies DHJ(k). We will show that the following statement is equivalent to DHJ(k):

“There is a constant, c < 1 that for every d there is an n that any c-dense subset of [k]ⁿ contains a d-dimensional subspace.”

We should show that the statement above implies DHJ(k). As before, write [k]ⁿ as , where s is much bigger than r. For each , define to be . Let Y denote the set of such that is empty. Suppose that is large, line-free, and its density is δ = Δ − ε where Δ is the limit of density of line-free sets and ε < (1 − c)Δ . We can also suppose that no has density much larger than Δ as that would guarantee a combinatorial line. But then the density of Y is at most 1-c, so there is a c-dense set, Z = [k]^s − Y, such that any element is a tail of some elements of . For every choose an . This x will be the colour of y. It gives a [k]^r colouring on Z. By the initial condition Z contains arbitrary large subspaces, so by HJ(k) we get a line in .