Polymath Wiki - User contributions [en]

DHJ(k) implies multidimensional DHJ(k)

2009-03-16T07:50:29Z

82.152.251.19: /* A weak multidimensional DHJ(k) implies DHJ(k) */ Corrected typo

==Introduction==

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

==The proof==

Let <math>\mathcal{A}</math> be a [[density]]-<math>\delta</math> subset of <math>[k]^n</math> and let M be large enough so that every subset of <math>[k]^M</math> of density at least <math>\theta</math> contains a [[combinatorial line]]. Now split <math>[k]^n</math> up into <math>[k]^M\times[k]^{n-M}.</math> For a proportion at least <math>\delta/2</math> of the points y in <math>[k]^{n-M}</math> the set of <math>x\in[k]^M</math> such that <math>(x,y)\in\mathcal{A}</math> has density at least <math>\delta/2.</math> Therefore, by DHJ(k) (with <math>\theta=\delta/2</math>) we have a combinatorial line. Since there are fewer than <math>(k+1)^M</math> combinatorial lines to choose from, by the pigeonhole principle we can find a combinatorial line <math>L\subset[k]^M</math> and a set <math>\mathcal{A}_1</math> of density <math>\delta/2(k+1)^M</math> in <math>[k]^{n-M}</math> such that <math>(x,y)\in\mathcal{A}</math> whenever <math>x\in L</math> and <math>y\in\mathcal{A}_1.</math> And now by induction we can find an (m-1)-dimensional subspace in <math>\mathcal{A}_1</math> 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 <math> [k]^n</math> contains a d-dimensional subspace.”

We should show that the statement above implies DHJ(k). As before, write <math> [k]^n</math> as <math> [k]^r\times[k]^s </math> , where s is much bigger than r. For each <math> y\in [k]^s</math> , define <math> \mathcal{A}_y</math> to be <math> \{x\in[k]^r:(x,y)\in\mathcal{A}\}</math> . Let Y denote the set of <math> y\in [k]^s</math> such that <math>\mathcal{A}_y</math> is empty. Suppose that <math> \mathcal{A} </math> is large, line-free, and its density is <math> \delta =\Delta-\epsilon</math> where <math> \Delta</math> is the limit of density of line-free sets and <math> \epsilon < (1-c)\Delta</math> . We can also suppose that no <math> \mathcal{A}_y</math> has density much larger than <math> \Delta</math> 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, <math> Z=[k]^s-Y</math>, such that any element is a tail of some elements of <math> \mathcal{A}</math> . For every <math> y \in Z</math> choose an <math> x\in [k]^r:(x,y)\in\mathcal{A}</math> . This x will be the colour of y. It gives a <math> [k]^r</math> colouring on Z. By the initial condition Z contains arbitrary large subspaces, so by HJ(k) we get a line in <math> \mathcal{A}</math> .

Abstract regularity lemma

2009-03-14T08:43:23Z

82.152.251.19:

Suppose we have a finite probability space <math>X = (X, \mu)</math> such that every point in X occurs with positive probability. Given a <math>\sigma</math>-algebra (i.e. finite partition) <math>{\mathcal B}</math> of this space, and a function <math>f: X \to {\Bbb R}</math>, define the ''conditional expectation'' <math>{\Bbb E}(f|{\mathcal B})</math> to be the function from X to <math>{\Bbb R}</math> whose value at any point x is the average of f on the cell of <math>{\mathcal B}</math> that contains x.

We say that a finite partition of X has ''complexity'' M if it is generated by M or fewer sets, which implies that it has at most <math>2^M</math> cells. If one partition <math>{\mathcal B}</math> is coarser than another <math>{\mathcal B}'</math>, we write <math>{\mathcal B} \leq {\mathcal B}'</math>. Given two partitions <math>{\mathcal B}, {\mathcal B}'</math>, let <math>{\mathcal B} \vee {\mathcal B}'</math> denote the common refinement.

'''Abstract regularity lemma''' Let X be a finite probability space, and for each i=0,1,2, let <math>{\mathcal B}_i^0 \subset {\mathcal B}_i^1 \subset \ldots</math> be an increasing sequence of partitions, and let <math>f_i: X \to [0,1]</math> be a function. Let <math>\varepsilon > 0</math>, and let <math>F: {\Bbb R}^+ \to {\Bbb R}^+</math> be a function. Then there exists integers <math>M \leq M' \leq O_{\varepsilon,F}(1)</math>, and partitions <math>{\mathcal A}_i^{coarse} \leq {\mathcal A}_i^{fine}</math> for i=0,1,2 with the following properties for all {i,j,k}={0,1,2}:

# (Coarse partition is low complexity) <math>{\mathcal A}_i^{coarse} \leq {\mathcal B}_i^M</math>, and <math>{\mathcal A}_i^{coarse}</math> has complexity M.
# (Fine partition is medium complexity) <math>{\mathcal A}_i^{fine} \leq {\mathcal B}_i^{M'}</math>, and <math>{\mathcal A}_i^{fine}</math> has complexity M'.
# (Coarse and fine approximations are close) <math>\| {\Bbb E}(f_i | {\mathcal A}_j^{fine} \vee {\mathcal A}_k^{fine} ) -
{\Bbb E}(f_i | {\mathcal A}_j^{coarse} \vee {\mathcal A}_k^{coarse} ) \|_{L^2(X)} \leq \varepsilon</math>.
# (Fine approximation is extremely high quality) For any <math> E_j \in {\mathcal B}_j^{M'+1}</math>, <math>E_k \in {\mathcal B}_k^{M'+1}</math>, we have <math>| {\Bbb E} (f_i - {\Bbb E}(f_i| {\mathcal A}_j^{fine} \vee {\mathcal A}_k^{fine} )) 1_{E_j} 1_{E_k} | \leq 1/F(M)</math>.

'''Proof''': Run the following algorithm:

# Initialise m=1, and set <math>{\mathcal A}_i^m</math> to be trivial for i=0,1,2.
# Find the {i,j,k}={0,1,2} and <math>E^m_j \in {\mathcal B}_j^{m+1}</math>, E^m_k \in {\mathcal B}_k^{m+1}</math> that maximises the quantity <math>| {\Bbb E} (f_i - {\Bbb E}(f_i| {\mathcal A}_j^m \vee {\mathcal A}_k^m )) 1_{E_j^m} 1_{E_k^m} |</math>. Define <math>E_i^m</math> to be the empty set.
# For each i=0,1,2, define <math>{\mathcal A}_i^{m+1}</math> to be the partition generated by <math>{\mathcal A}_i^m</math> and <math>E_i^m</math>.
# Increment m to m+1, and return to Step 2.

This gives increasing sequences of partitions <math>{\mathcal A}_i^m</math> for i=0,1,2 and <math>m=1,2,\ldots</math>. Define the energy

<math>E_m := \sum_{\{i,j,k\}=\{0,1,2\}} \| {\Bbb E}(f_i | {\mathcal A}_j^m \wedge {\mathcal A}_k^m ) \|_{L^2(X)}^2</math>.

This energy lies between 0 and 3!, and by Pythagoras' theorem, it is non-decreasing in m. Thus by the finite convergence principle, we can find <math>M = O_{F,\varepsilon}(1)</math> such that

:<math>E_{M + F(M)^2 + 1} \leq E_M + \varepsilon^2</math>.

By the pigeonhole principle, one can then find <math>M \leq M' \leq M+F(M)^2</math> such that

:<math>E_{M'+1} \leq E_{M'} + 1/F(M)^2</math>.

If we then set <math>{\mathcal A}_i^{coarse} := {\mathcal A}_i^M</math> and <math>{\mathcal A}_i^{fine} := {\mathcal A}_i^{M'}</math> for i=0,1,2, the claims are then verified by a number of applications of Pythagoras and Cauchy-Schwarz (the computations are essentially the same as those in my [[http://front.math.ucdavis.edu/math.CO/0504472 regularity lemma paper]]). <math>\Box</math>

Coloring Hales-Jewett theorem

2009-03-13T14:57:17Z

82.152.251.19: Modified introduction slightly (Gowers -- forgot to login).

==Introduction==

The Hales-Jewett theorem states that for every k and every r there exists an n such that if you colour the elements of <math>[k]^n</math> with r colours, then there must be a [[combinatorial line]] with all its points of the same colour.

This is a consequence of the [[Density Hales-Jewett theorem]], since there must be a set of density at least <math>r^{-1}</math> of elements of <math>[k]^n</math> all of whose elements have the same colour. It also follows from the [[Graham-Rothschild theorem]].

By iterating the Hales-Jewett theorem, one can also show that one of the color classes contains an m-dimensional [[combinatorial subspace]], if n is sufficiently large depending on k, r and m.

There are two combinatorial proofs of the Hales-Jewett theorem: the original one by Hales and Jewett, and a second proof by Shelah. They are given below.

There is an infinitary generalisation of this theorem known as the [[Carlson-Simpson theorem]].

Here is the [http://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem Wikipedia entry on this theorem].

For a fixed r and k, the least n needed for the Hales-Jewett theorem to apply is denoted HJ(k,r). The following bounds are known:

: <math>HJ(3,1) = 1</math>
: <math>HJ(3,2) = 4</math>
: <math>HJ(3,3) > 6</math>

==The original proof of the Hales-Jewett theorem==

The first proof of the Hales-Jewett theorem was an abstraction of the argument used to prove van der Waerden's theorem. It goes like this. As above, let us write HJ(k,r) for the smallest n such that for every r-colouring of <math>[k]^n</math> there is a monochromatic combinatorial line. We shall attempt to bound HJ(k,r) in terms of the function <math>s\mapsto HJ(k-1,s),</math> which we may assume by induction to take finite values for every s.

Let <math>t_1,t_2,\dots,t_r</math> be a rapidly increasing sequence of integers, to be chosen later, let <math>n=t_1+\dots+t_r</math> and consider an r-colouring of <math>[k]^n=[k]^{t_1}\times\dots\times[k]^{t_r}.</math> Now define an induced <math>k^{n-t_r}</math>-colouring on <math>[k]^{t_r}</math> by colouring each x according to the function that takes <math>w\in[k]^{n-t_r}</math> to the colour of <math>(w,x).</math> By induction, we can find a monochromatic combinatorial line <math>L_r</math> in <math>[k]^{t_r}</math> such that all the points in that line have the same (induced) colour, with the possible exception of the point where the value of the variable coordinates is k. For this we need <math>t_r\geq HJ(k-1,k^{n-t_r}).</math>

Now pass to the subspace <math>[k]^{n-t_r}\times L_r,</math> and note that the only way a sequence in this space can depend on its final coordinate is through whether that final coordinate takes the value k or not. Inside this subspace, run precisely the same argument, but this time with <math>[k]^{t_{r-1}}</math> taking over the role of <math>[k]^{t_r}.</math> There is a choice here about what "precisely the same argument" means. It can either mean that we treat <math>[k]^{n-t_r}\times L_r</math> as <math>([k]^{n-t_r-t_{r-1}}\times L_r)\times[k]^{t_{r-1}}</math> and talk about the original colouring, or it can mean that we restrict attention to the set <math>[k]^{n-t_r}=[k]^{t_1}\times\dots\times[k]^{t_{r-1}}</math> and talk about the colouring where the colour of w is the colour of (w,x) for the points <math>x\in L_r</math> with variable coordinate not equal to k. The usual argument goes via the second option, but for the sake of comparison with Shelah's proof it is nicer to go for the first (so what we are presenting here is not quite identical to the proof of Hales and Jewett).

After the second stage of the iteration, for which we require that
<math>t_{r-1}\geq HJ(k-1,k^{n-t_r-t_{r-1}+1}),</math> we have a line <math>L_{r-1}</math> such that the colour of a point in <math>[k]^{t_1}\times\dots\times[k]^{t_{r-2}}\times L_{r-1}\times L_r</math> does not depend on which point you choose in <math>L_{r-1}\times L_r,</math> except if you change a non-k to a k or a k to a non-k.

Continuing this process, one ends up with a subspace <math>L_1\times\dots\times L_r</math> such that the colour of a point depends only on which of its coordinates are equal to k. This reduces the problem to HJ(2,r), which follows trivially from the pigeonhole principle. To spell it out, consider the points <math>(k-1,k-1,\dots,k-1),</math> <math>(k,k-1,k-1,\dots,k-1),</math> <math>(k,k,k-1,\dots,k-1),\dots(k,k,k,\dots,k).</math> There are r+1 of these points, so two of them have the same colour. Those two are the top two points of a combinatorial line, all the rest of which must have the same colour as well.

==Shelah's proof of the Hales-Jewett theorem==

This is very unfair to Shelah, but I am trying to present what he did as an almost trivial exercise in "turning an induction upside-down". The above proof used HJ(k-1) to create a subspace that we can treat as <math>[2]^r,</math> because the colouring in that subspace depends only on which coordinates are k and which are not k. Now let us try to use HJ(2) to create a subspace that we can treat as <math>[k-1]^m,</math> for some appropriate m, since in the subspace we shall ensure that the colouring is insensitive to changes between k-1 and k. To emphasize how easy this is, I shall paste the above paragraphs into this section and make the necessary adjustments.

Let <math>t_1,t_2,\dots,t_m</math> be a rapidly increasing sequence of integers, to be chosen later (including m), let <math>n=t_1+\dots+t_m</math> and consider an r-colouring of <math>[k]^n=[k]^{t_1}\times\dots\times[k]^{t_m}.</math> Now define an induced <math>k^{n-t_m}</math>-colouring on <math>[k]^{t_m}</math> by colouring each x according to the function that takes <math>w\in[k]^{n-t_m}</math> to the colour of <math>(w,x).</math> By HJ(2) (a trivial application of the pigeonhole principle, as we saw above), we can find a monochromatic combinatorial line <math>L_r</math> in <math>[k]^{t_m}</math> such that the first two points in that line have the same (induced) colour. For this we need <math>t_r\geq HJ(2,k^{n-t_m})=k^{n-t_m}.</math>

Now pass to the subspace <math>[k]^{n-t_m}\times L_m,</math> and note that if you change the final coordinate of a sequence in this space from a 1 to a 2, or vice versa, then it does not change the colour of the sequence. Inside this subspace, run precisely the same argument, but this time with <math>[k]^{t_{m-1}}</math> taking over the role of <math>[k]^{t_m}</math> and <math>L_m</math> taking over the role of <math>[k]^{t_{m-1}}.</math>

After the second stage of the iteration, for which we require that <math>t_{m-1}\geq HJ(2,k^{n-t_r-t_{m-1}+1})=k^{n-t_m-t_{m-1}}+1,</math> we have a line <math>L_{m-1}</math> such that the colour of a point in <math>[k]^{t_1}\times\dots\times[k]^{t_{m-2}}\times L_{m-1}\times L_m</math> does not change if you change any of the coordinates in <math>L_{m-1}\times L_m,</math> from a 1 to a 2 or vice versa.

Continuing this process, one ends up with a subspace <math>L_1\times\dots\times L_m</math> such that the colour of a point does not change if you change a coordinate from a 1 to a 2 or vice versa. This reduces the problem to HJ(k-1), so we can take m to be HJ(k-1,r) and we are done. To spell it out, consider the set of all points in <math>L_1\times\dots\times L_m</math> that have no variable coordinate equal to 1. Inside this set, we can find, by HJ(k-1,m), a combinatorial line such that all points in the line with variable coordinate not equal to 1 have the same colour. But by the way the subspace is chosen, we still have the same colour if we change the variable coordinate to a 1.

Coloring Hales-Jewett theorem

2009-03-13T14:51:51Z

82.152.251.19: Added Shelah proof (Gowers -- forgot to log in)

'''Coloring Hales-Jewett theorem''' (k=3): If n is sufficiently large depending on c, and <math>[3]^n</math> is partitioned into c color classes, then one of the color classes contains a [[combinatorial line]].

This is a consequence of the [[Density Hales-Jewett theorem]], and also of the [[Graham-Rothschild theorem]].

Iterating the Hales-Jewett theorem, we also see that one of the color classes contains an m-dimensional [[combinatorial subspace]], if n is sufficiently large depending on c and m.

There are two combinatorial proofs of this theorem: the original one by Hales and Jewett, and a second proof by Shelah.

There is an infinitary generalisation of this theorem known as the [[Carlson-Simpson theorem]].

Here is the [http://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem Wikipedia entry on this theorem].

For a fixed c, the least n needed for the Hales-Jewett theorem to apply is denoted HJ(3,c). The following bounds are known:

: <math>HJ(3,1) = 1</math>
: <math>HJ(3,2) = 4</math>
: <math>HJ(3,3) > 6</math>

==The original proof of the Hales-Jewett theorem==

The first proof of the Hales-Jewett theorem was an abstraction of the argument used to prove van der Waerden's theorem. It goes like this. Let us write
HJ(k,r) for the smallest n such that for every r-colouring of <math>[k]^n</math> there is a monochromatic combinatorial line. We shall attempt to bound HJ(k,r) in terms of the function <math>s\mapsto HJ(k-1,s),</math> which we may assume by induction to take finite values for every s.

Let <math>t_1,t_2,\dots,t_r</math> be a rapidly increasing sequence of integers, to be chosen later, let <math>n=t_1+\dots+t_r</math> and consider an r-colouring of <math>[k]^n=[k]^{t_1}\times\dots\times[k]^{t_r}.</math> Now define an induced <math>k^{n-t_r}</math>-colouring on <math>[k]^{t_r}</math> by colouring each x according to the function that takes <math>w\in[k]^{n-t_r}</math> to the colour of <math>(w,x).</math> By induction, we can find a monochromatic combinatorial line <math>L_r</math> in <math>[k]^{t_r}</math> such that all the points in that line have the same (induced) colour, with the possible exception of the point where the value of the variable coordinates is k. For this we need <math>t_r\geq HJ(k-1,k^{n-t_r}).</math>

Now pass to the subspace <math>[k]^{n-t_r}\times L_r,</math> and note that the only way a sequence in this space can depend on its final coordinate is through whether that final coordinate takes the value k or not. Inside this subspace, run precisely the same argument, but this time with <math>[k]^{t_{r-1}}</math> taking over the role of <math>[k]^{t_r}.</math> There is a choice here about what "precisely the same argument" means. It can either mean that we treat <math>[k]^{n-t_r}\times L_r</math> as <math>([k]^{n-t_r-t_{r-1}}\times L_r)\times[k]^{t_{r-1}}</math> and talk about the original colouring, or it can mean that we restrict attention to the set <math>[k]^{n-t_r}=[k]^{t_1}\times\dots\times[k]^{t_{r-1}}</math> and talk about the colouring where the colour of w is the colour of (w,x) for the points <math>x\in L_r</math> with variable coordinate not equal to k. The usual argument goes via the second option, but for the sake of comparison with Shelah's proof it is nicer to go for the first (so what we are presenting here is not quite identical to the proof of Hales and Jewett).

After the second stage of the iteration, for which we require that
<math>t_{r-1}\geq HJ(k-1,k^{n-t_r-t_{r-1}+1}),</math> we have a line <math>L_{r-1}</math> such that the colour of a point in <math>[k]^{t_1}\times\dots\times[k]^{t_{r-2}}\times L_{r-1}\times L_r</math> does not depend on which point you choose in <math>L_{r-1}\times L_r,</math> except if you change a non-k to a k or a k to a non-k.

Continuing this process, one ends up with a subspace <math>L_1\times\dots\times L_r</math> such that the colour of a point depends only on which of its coordinates are equal to k. This reduces the problem to HJ(2,r), which follows trivially from the pigeonhole principle. To spell it out, consider the points <math>(k-1,k-1,\dots,k-1),</math> <math>(k,k-1,k-1,\dots,k-1),</math> <math>(k,k,k-1,\dots,k-1),\dots(k,k,k,\dots,k).</math> There are r+1 of these points, so two of them have the same colour. Those two are the top two points of a combinatorial line, all the rest of which must have the same colour as well.

==Shelah's proof of the Hales-Jewett theorem==

This is very unfair to Shelah, but I am trying to present what he did as an almost trivial exercise in "turning an induction upside-down". The above proof used HJ(k-1) to create a subspace that we can treat as <math>[2]^r,</math> because the colouring in that subspace depends only on which coordinates are k and which are not k. Now let us try to use HJ(2) to create a subspace that we can treat as <math>[k-1]^m,</math> for some appropriate m, since in the subspace we shall ensure that the colouring is insensitive to changes between k-1 and k. To emphasize how easy this is, I shall paste the above paragraphs into this section and make the necessary adjustments.

Let <math>t_1,t_2,\dots,t_m</math> be a rapidly increasing sequence of integers, to be chosen later (including m), let <math>n=t_1+\dots+t_m</math> and consider an r-colouring of <math>[k]^n=[k]^{t_1}\times\dots\times[k]^{t_m}.</math> Now define an induced <math>k^{n-t_m}</math>-colouring on <math>[k]^{t_m}</math> by colouring each x according to the function that takes <math>w\in[k]^{n-t_m}</math> to the colour of <math>(w,x).</math> By HJ(2) (a trivial application of the pigeonhole principle, as we saw above), we can find a monochromatic combinatorial line <math>L_r</math> in <math>[k]^{t_m}</math> such that the first two points in that line have the same (induced) colour. For this we need <math>t_r\geq HJ(2,k^{n-t_m})=k^{n-t_m}.</math>

Now pass to the subspace <math>[k]^{n-t_m}\times L_m,</math> and note that if you change the final coordinate of a sequence in this space from a 1 to a 2, or vice versa, then it does not change the colour of the sequence. Inside this subspace, run precisely the same argument, but this time with <math>[k]^{t_{m-1}}</math> taking over the role of <math>[k]^{t_m}</math> and <math>L_m</math> taking over the role of <math>[k]^{t_{m-1}}.</math>

After the second stage of the iteration, for which we require that <math>t_{m-1}\geq HJ(2,k^{n-t_r-t_{m-1}+1})=k^{n-t_m-t_{m-1}}+1,</math> we have a line <math>L_{m-1}</math> such that the colour of a point in <math>[k]^{t_1}\times\dots\times[k]^{t_{m-2}}\times L_{m-1}\times L_m</math> does not change if you change any of the coordinates in <math>L_{m-1}\times L_m,</math> from a 1 to a 2 or vice versa.

Continuing this process, one ends up with a subspace <math>L_1\times\dots\times L_m</math> such that the colour of a point does not change if you change a coordinate from a 1 to a 2 or vice versa. This reduces the problem to HJ(k-1), so we can take m to be HJ(k-1,r) and we are done. To spell it out, consider the set of all points in <math>L_1\times\dots\times L_m</math> that have no variable coordinate equal to 1. Inside this set, we can find, by HJ(k-1,m), a combinatorial line such that all points in the line with variable coordinate not equal to 1 have the same colour. But by the way the subspace is chosen, we still have the same colour if we change the variable coordinate to a 1.

Coloring Hales-Jewett theorem

2009-03-13T12:47:28Z

82.152.251.19: Created article (Gowers -- forgot to log in).

Line free sets correlate locally with dense sets of complexity k-2

2009-03-12T21:47:19Z

82.152.251.19: /* Introduction */

==Introduction==

The aim of this page is to generalize the proof that [[Line-free_sets_correlate_locally_with_complexity-1_sets|line-free subsets of <math>[3]^n</math> correlate locally with sets of complexity 1]] to an analogous statement for line-free subsets of <math>[k]^n.</math>

Until this sentence is removed, there is no guarantee that this aim will be achieved, but what follows seems to be a plausible sketch.

==Notation and definitions==

The actual result to be proved is more precise than the result given in the title of the page. To explain it we need a certain amount of terminology. Given <math>j\leq k</math> and a sequence <math>x\in[k]^n,</math> let <math>U_j(x)</math> denote the set <math>\{i\in[n]:x_i=j\}.</math> We call this the ''j-set'' of x. More generally, if <math>E\subset[k],</math> let <math>U_E(x)</math> denote the sequence <math>(U_j(x):j\in E).</math> We call this the ''E-sequence'' of x. For example, if n=10, k=4, <math>x=3442411123</math> and <math>E=\{2,3\}</math> then the E-sequence of x is <math>(\{4,9\},\{1,10\}).</math> It can sometimes be nicer to avoid set-theoretic brackets and instead to say things like that the 24-sequence of x is <math>(49,235).</math>

An ''E-set'' is a set <math>\mathcal{A}\subset[k]^n</math> such that whether or not x belongs to <math>\mathcal{A}</math> depends only on the E-sequence of x. In other words, to define an E-set one chooses a collection <math>\mathcal{U}_E</math> of sequences of the form <math>(U_i:i\in E),</math> where the <math>U_i</math> are disjoint subsets of [n], and one takes the set of all x such that <math>(U_i(x):i\in E)\in\mathcal{U}_E.</math> More generally, an <math>(E_1,\dots,E_r)</math>-''set'' is an intersection of <math>E_h</math>-sets as h runs from 1 to r.

Of particular interest to us will be the sequence
<math>(E_1,\dots,E_{k-1}),</math> where <math>E_j=[k-1]\setminus j.</math> What is an <math>(E_1,\dots,E_{k-1})</math>set? It is a set where membership depends on k-1 conditions, and the jth condition on a sequence x depends just on the sets <math>U_i(x)</math> with <math>i\leq k-1</math> and <math>i\ne j.</math>

Since it provides a useful illustrative example, let us describe the class of sets that will arise in the proof. Suppose we have a set <math>\mathcal{B}\subset[k-1]^n.</math> We can use <math>\mathcal{B}</math> to define a set <math>\mathcal{C}\subset[k]^n</math> as follows. A sequence x belongs to <math>\mathcal{C}</math> if and only if for each j < k the following holds: if change all the k's of x into j's, the resulting sequence is in <math>\mathcal{B}.</math>

To see that this is an <math>(E_1,\dots,E_{k-1})</math>-set, it is enough to show that the set <math>\mathcal{C}_j</math> of all x such that changing ks to js puts you in <math>\mathcal{B}</math> is an <math>E_j</math>-set. And indeed, whether or not x belongs to that set does depend only on the i-sets <math>U_i(x)</math> with <math>i\leq k-1</math> and <math>i\ne j,</math> since once you know those you have determined the sequence obtained from x when you rewrite the ks as js.

<math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math>

==Proof of the main result, with a gap still left to fill==

To write this section, I lifted [[Line-free_sets_correlate_locally_with_complexity-1_sets#Proof|a section from the equivalent proof for DHJ(3)]] and made such changes as were necessary. One result did not go through straightforwardly and now needs to be thought about. (It is pretty clear that it can be done -- it will just need a bit of work.)

Let us assume for now that the equal-slices density of <math>\mathcal{A}</math> in <math>[k]^n</math> is at least <math>\delta</math>, and that the equal-slices density of <math>\mathcal{A} \cap [k-1]^n</math> in <math>[k-1]^n</math> is at least <math>\theta</math>. As discussed in the sections below, we can reduce to this case by passing to subspaces. Let us write <math>\mathcal{B}</math> for <math>\mathcal{A}\cap[k-1]^n,</math> and let <math>\mathcal{C}</math> be the set defined in terms of <math>\mathcal{B}</math> in the previous section.

We shall now deduce from the fact that <math>\mathcal{A}</math> contains no combinatorial line that it is disjoint from <math>\mathcal{C}.</math> Indeed, this is pretty well trivial. Given any sequence x, let <math>\rho_j(x)</math> be the sequence obtained by changing all the ks in x to js. Then the set <math>\{\rho_1(x),\dots,\rho_{k-1}(x),x\}</math> is a combinatorial line (with wildcard set <math>U_k(x)</math>). Therefore, not all its points belong to <math>\mathcal{A}</math> which implies that either <math>x\notin\mathcal{A}</math> or <math>x\notin\mathcal{C}.</math>

We will now show that <math>\mathcal{C}</math> is dense in equal-slices measure on <math>[k]^n</math>.

Hmm ... this is less obvious. Hopefully one can use the understanding of the [[equal-slices distribution for DHJ(k)]].

For now let me just say what happens if this is true. If <math>\mathcal{C}=\mathcal{C}_1\cap\dots\cap\mathcal{C}_{k-1}</math> has density at least <math>\eta,</math> then consider all the <math>2^{k-1}-1</math> sets of the form <math>\mathcal{D}_1\cap\dots\cap\mathcal{D}_{k-1},</math> where each <math>\mathcal{D}_i</math> is either <math>\mathcal{C}_i</math> or its complement, and not every <math>\mathcal{D}_i</math> equals <math>\mathcal{C}_i.</math> Then there must be some i such that the measure <math>\mu(\mathcal{A}\cap\mathcal{D}_i)</math> is at least <math>\delta\mu(\mathcal{D}_i)+\eta/(2^{k-1}-1).</math> This gives us a density increase of at least <math>\eta/2^{k-1}</math> on a set of density at least <math>\eta/2^{k-1}.</math>

We should be able to move from this relative density-increment under equal-slices to a nearly as good one under uniform by appropriately generalizing the results in the [[passing between measures]] section ("relative density version").

==DHJ(k) implies equal-slices Varnavides-DHJ(k)==

This section is intended to fill the main gap in the section above. We would like to deduce from DHJ(k) that if <math>\mathcal{B}</math> is an equal-slices dense subset of <math>[k]^n,</math> then with positive probability an equal-slices random combinatorial line is contained in <math>\mathcal{A}.</math>

To prove this it is enough to do the following. Let the density of <math>\mathcal{B}</math> be <math>\theta,</math> let <math>\zeta</math> be some positive constant that depends on <math>\theta</math> only, and let M be large enough that every subset of <math>[k]^M</math> of density at least <math>\zeta</math> contains a combinatorial line. We would now like to find a positive linear combination <math>\nu</math> of characteristic functions of M-dimensional subspaces of <math>[k]^n</math> with the following properties.

*<math>\nu</math> is a probability measure: that is, it sums to 1.

*If <math>\mathcal{B}</math> is any subset of <math>[k]^n</math> with equal-slices density <math>\theta>0,</math> then <math>\nu(\mathcal{B})\geq\eta=\eta(\theta)>0.</math>

*Let <math>\mathcal{L}</math> be a set of combinatorial lines. Define the <math>\nu</math>-density of <math>\mathcal{L}</math> to be the probability that a random line L belongs to <math>\mathcal{L}</math> if you choose it by first picking a <math>\nu</math>-random subspace and then picking a random line (uniformly) from that subspace. (See below for the definition of <math>\nu</math>-random subspace.) Then if the <math>\nu</math>-density of <math>\mathcal{L}</math> is at least <math>c,</math> then the equal-slices density of <math>\mathcal{L}</math> is at least <math>c'(c).</math>

Let us see why these three properties are enough. Let the M-dimensional subspaces of
<math>[k]^n</math> be enumerated as <math>S_1,\dots,S_N,</math> and let <math>\sigma_i</math> be the uniform probability measure on <math>S_i.</math> Then we are looking for a convex combination <math>\nu=\sum_{i=1}^N\lambda_i\sigma_i</math> of the measures <math>\sigma_i.</math> Given such a <math>\nu,</math> we define a <math>\nu</math>-''random subspace'' to be what you get when you choose <math>S_i</math> with probability <math>\lambda_i.</math>

Suppose we have found <math>\nu</math> with the three properties above, and let
<math>\mathcal{B}</math> be a set of equal-slices density <math>\theta.</math> Then by hypothesis we have that <math>\nu(\mathcal{B})\geq\eta.</math> This implies that if <math>S_i</math> is a <math>\nu</math>-random subspace, then the probability that <math>\sigma_i(\mathcal{B})\geq\eta/2</math> is at least <math>\eta/2.</math> If we have taken <math>\zeta</math> to be <math>\eta/2,</math> then each subspaces <math>S_i</math> for which <math>\sigma_i(\mathcal{B})\geq\eta/2</math> contains a combinatorial line in <math>\mathcal{B}.</math> Since an M-dimensional subspace contains <math>(k+1)^M</math> combinatorial lines, this implies that the <math>\nu</math>-density of the set of all combinatorial lines in <math>\mathcal{B}</math> is at least <math>\eta/2(k+1)^M.</math> Hence, by the third property, the equal-slices density of this set of lines is at least <math>c(\theta,k,M)>0.</math>

It remains to define an appropriate measure <math>\nu.</math> I think probably a fairly obvious equal-slices measure on M-dimensional subspaces will do the trick, but will have to wait to check this.

Here is a preliminary attempt to do the check. This will be tidied up at some point if it works. Let us define a random M-dimensional subspace S by randomly choosing numbers <math>a_1+\dots+a_M=n</math> and then randomly partitioning <math>[n]</math> into wildcard sets <math>Z_1,\dots,Z_M</math> with <math>|Z_i|=a_i.</math> Then <math>\nu</math> is the measure you get by choosing a random subspace in this way and then choosing a random point in that subspace.

Now <math>\nu</math> is nothing like the equal-slices density, since a typical point will have roughly equal numbers of each coordinate value. However, the probability that we deviate from this average is small as a function of M rather than as a function of n, so the second property looks fine.

A similar argument appears to deal with the third property. It may be a bore to make it rigorous, but I definitely believe it.

<math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math>

Line free sets correlate locally with dense sets of complexity k-2

2009-03-10T23:39:08Z

82.152.251.19: /* DHJ(k) implies equal-slices Varnavides-DHJ(k) */

==Introduction==

The aim of this page is to generalize the proof that [[Line-free_sets_correlate_locally_with_complexity-1_sets|line-free subsets of <math>[3]^n</math> correlate locally with sets of complexity 1]] to an analogous statement for line-free subsets of <math>[k]^n.</math>

Until this sentence is removed, there is no guarantee that this aim will be achieved, or even that a plausible sketch will result.

==Notation and definitions==

The actual result to be proved is more precise than the result given in the title of the page. To explain it we need a certain amount of terminology. Given <math>j\leq k</math> and a sequence <math>x\in[k]^n,</math> let <math>U_j(x)</math> denote the set <math>\{i\in[n]:x_i=j\}.</math> We call this the ''j-set'' of x. More generally, if <math>E\subset[k],</math> let <math>U_E(x)</math> denote the sequence <math>(U_j(x):j\in E).</math> We call this the ''E-sequence'' of x. For example, if n=10, k=4, <math>x=3442411123</math> and <math>E=\{2,3\}</math> then the E-sequence of x is <math>(\{4,9\},\{1,10\}).</math> It can sometimes be nicer to avoid set-theoretic brackets and instead to say things like that the 24-sequence of x is <math>(49,235).</math>

An ''E-set'' is a set <math>\mathcal{A}\subset[k]^n</math> such that whether or not x belongs to <math>\mathcal{A}</math> depends only on the E-sequence of x. In other words, to define an E-set one chooses a collection <math>\mathcal{U}_E</math> of sequences of the form <math>(U_i:i\in E),</math> where the <math>U_i</math> are disjoint subsets of [n], and one takes the set of all x such that <math>(U_i(x):i\in E)\in\mathcal{U}_E.</math> More generally, an <math>(E_1,\dots,E_r)</math>-''set'' is an intersection of <math>E_h</math>-sets as h runs from 1 to r.

Of particular interest to us will be the sequence
<math>(E_1,\dots,E_{k-1}),</math> where <math>E_j=[k-1]\setminus j.</math> What is an <math>(E_1,\dots,E_{k-1})</math>set? It is a set where membership depends on k-1 conditions, and the jth condition on a sequence x depends just on the sets <math>U_i(x)</math> with <math>i\leq k-1</math> and <math>i\ne j.</math>

Since it provides a useful illustrative example, let us describe the class of sets that will arise in the proof. Suppose we have a set <math>\mathcal{B}\subset[k-1]^n.</math> We can use <math>\mathcal{B}</math> to define a set <math>\mathcal{C}\subset[k]^n</math> as follows. A sequence x belongs to <math>\mathcal{C}</math> if and only if whenever you change all the ks of x into js, for some j<k, you end up with a sequence in <math>\mathcal{B}.</math>

To see that this is an <math>(E_1,\dots,E_{k-1})</math>-set, it is enough to show that the set <math>\mathcal{C}_j</math> of all x such that changing ks to js is an <math>E_j</math>-set. And indeed, whether or not x belongs to that set does depend only on the i-sets <math>U_i(x)</math> with <math>i\leq k-1</math> and <math>i\ne j,</math> since once you know those you have determined the sequence obtained from x when you rewrite the ks as js.

<math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math>

==Proof of the main result, with a gap still left to fill==

To write this section, I lifted [[Line-free_sets_correlate_locally_with_complexity-1_sets#Proof|a section from the equivalent proof for DHJ(3)]] and made such changes as were necessary. One result did not go through straightforwardly and now needs to be thought about. (It is pretty clear that it can be done -- it will just need a bit of work.)

Let us assume for now that the equal-slices density of <math>\mathcal{A}</math> in <math>[k]^n</math> is at least <math>\delta</math>, and that the equal-slices density of <math>\mathcal{A} \cap [k-1]^n</math> in <math>[k-1]^n</math> is at least <math>\theta</math>. As discussed in the sections below, we can reduce to this case by passing to subspaces. Let us write <math>\mathcal{B}</math> for <math>\mathcal{A}\cap[k-1]^n,</math> and let <math>\mathcal{C}</math> be the set defined in terms of <math>\mathcal{B}</math> in the previous section.

We shall now deduce from the fact that <math>\mathcal{A}</math> contains no combinatorial line that it is disjoint from <math>\mathcal{C}.</math> Indeed, this is pretty well trivial. Given any sequence x, let <math>\rho_j(x)</math> be the sequence obtained by changing all the ks in x to js. Then the set <math>\{\rho_1(x),\dots,\rho_{k-1}(x),x\}</math> is a combinatorial line (with wildcard set <math>U_k(x)</math>). Therefore, not all its points belong to <math>\mathcal{A}</math> which implies that either <math>x\notin\mathcal{A}</math> or <math>x\notin\mathcal{C}.</math>

We will now show that <math>\mathcal{C}</math> is dense in equal-slices measure on <math>[k]^n</math>.

Hmm ... this is less obvious. Hopefully one can use the understanding of the [[equal-slices distribution for DHJ(k)]].

For now let me just say what happens if this is true. If <math>\mathcal{C}=\mathcal{C}_1\cap\dots\cap\mathcal{C}_{k-1}</math> has density at least <math>\eta,</math> then consider all the <math>2^{k-1}-1</math> sets of the form <math>\mathcal{D}_1\cap\dots\cap\mathcal{D}_{k-1},</math> where each <math>\mathcal{D}_i</math> is either <math>\mathcal{C}_i</math> or its complement, and not every <math>\mathcal{D}_i</math> equals <math>\mathcal{C}_i.</math> Then there must be some i such that the measure <math>\mu(\mathcal{A}\cap\mathcal{D}_i)</math> is at least <math>\delta\mu(\mathcal{D}_i)+\eta/(2^{k-1}-1).</math> This gives us a density increase of at least <math>\eta/2^{k-1}</math> on a set of density at least <math>\eta/2^{k-1}.</math>

We should be able to move from this relative density-increment under equal-slices to a nearly as good one under uniform by appropriately generalizing the results in the [[passing between measures]] section ("relative density version").

==DHJ(k) implies equal-slices Varnavides-DHJ(k)==

This section is intended to fill the main gap in the section above. We would like to deduce from DHJ(k) that if <math>\mathcal{B}</math> is an equal-slices dense subset of <math>[k]^n,</math> then with positive probability an equal-slices random combinatorial line is contained in <math>\mathcal{A}.</math>

To prove this it is enough to do the following. Let the density of <math>\mathcal{B}</math> be <math>\theta,</math> let <math>\zeta</math> be some positive constant that depends on <math>\theta</math> only, and let M be large enough that every subset of <math>[M]^k</math> of density at least
<math>\zeta</math> contains a combinatorial line. We would now like to find a positive linear combination <math>\nu</math> of characteristic functions of M-dimensional subspaces of <math>[k]^n</math> with the following properties.

*<math>\nu</math> is a probability measure: that is, it sums to 1.

*If <math>\mathcal{B}</math> is any subset of <math>[k]^n</math> with equal-slices density <math>\theta>0,</math> then <math>\nu(\mathcal{B})\geq\eta=\eta(\theta)>0.</math>

*Let <math>\mathcal{L}</math> be a set of combinatorial lines. Define the <math>\nu</math>-density of <math>\mathcal{L}</math> to be the probability that a random line L belongs to <math>\mathcal{L}</math> if you choose it by first picking a <math>\nu</math>-random subspace and then picking a random line (uniformly) from that subspace. (See below for the definition of <math>\nu</math>-random subspace.) Then if the <math>\nu</math>-density of <math>\mathcal{L}</math> is at least <math>c,</math> then the equal-slices density of <math>\mathcal{L}</math> is at least <math>c'(c).</math>

Let us see why these three properties are enough. Let the M-dimensional subspaces of
<math>[k]^n</math> be enumerated as <math>S_1,\dots,S_N,</math> and let <math>\sigma_i</math> be the uniform probability measure on <math>S_i.</math> Then we are looking for a convex combination <math>\nu=\sum_{i=1}^N\lambda_i\sigma_i</math> of the measures <math>\sigma_i.</math> Given such a <math>\nu,</math> we define a <math>\nu</math>-''random subspace'' to be what you get when you choose <math>S_i</math> with probability <math>\lambda_i.</math>

Suppose we have found <math>\nu</math> with the three properties above, and let
<math>\mathcal{B}</math> be a set of equal-slices density <math>\theta.</math> Then by hypothesis we have that <math>\nu(\mathcal{B})\geq\eta.</math> This implies that if <math>S_i</math> is a <math>\nu</math>-random subspace, then the probability that <math>\sigma_i(\mathcal{B})\geq\eta/2</math> is at least <math>\eta/2.</math> If we have taken <math>\zeta</math> to be <math>\eta/2,</math> then each subspaces <math>S_i</math> for which <math>\sigma_i(\mathcal{B})\geq\eta/2</math> contains a combinatorial line in <math>\mathcal{B}.</math> Since an M-dimensional subspace contains <math>(k+1)^M</math> combinatorial lines, this implies that the <math>\nu</math>-density of the set of all combinatorial lines in <math>\mathcal{B}</math> is at least <math>\eta/2(k+1)^M.</math> Hence, by the third property, the equal-slices density of this set of lines is at least <math>c(\theta,k,M)>0.</math>

It remains to define an appropriate measure <math>\nu.</math> I think probably a fairly obvious equal-slices measure on M-dimensional subspaces will do the trick, but will have to wait to check this.

<math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math>

An outline of a density-increment argument

2009-03-05T14:32:39Z

82.152.251.19: Began section. About to log in.

==Introduction==

One of the proof strategies we have considered seriously is [[Density_increment_method|the density-increment method]]. The idea here is to prove that if <math>\mathcal{A}</math> is a subset of <math>[3]^n</math> of [[density]] <math>\delta</math> with no [[combinatorial line]] then there is a [[combinatorial subspace]] S of dimension tending to infinity with n such that the density of <math>\mathcal{A}</math> inside S is larger than <math>\delta</math> by an amount that depends on <math>\delta</math> only. If we can prove such a result, then we can drop down to S and repeat the argument. If the initial dimension n is large enough, then we push the density up to 1 before we run out of dimensions, and thereby obtain a contradiction.

==Notation and definitions==

Let x be an element of <math>[3]^n.</math> Write <math>U(x),V(x)</math> and <math>W(x)</math> for the sets of i such that <math>x_i=1,2</math> and 3, respectively. These are called the ''1-set'', the ''2-set'' and the ''3-set'' of x. The map <math>x\mapsto(U(x),V(x),W(x))</math> is a one-to-one correspondence between <math>[3]^n</math> and the set of all triples <math>(U,V,W)</math> of sets that partition <math>[n].</math> We shall use the notation x and also the notation <math>(U,V,W)</math> and will pass rapidly between them.

Let <math>\mathcal{U}</math> and <math>\mathcal{V}</math> be collections of subsets of <math>[n].</math> We shall write <math>\mathcal{U}\otimes\mathcal{V}</math> for the collection of all sequences <math>x</math> such that <math>U(x)\in\mathcal{U}</math> and <math>V(x)\in\mathcal{V}.</math> A set of the form <math>\mathcal{U}\otimes\mathcal{V}</math> will be called a ''12-set''.

In general, if X is a finite set and A and B are subsets of X, we define ''the density of'' A ''in'' B to be <math>|A\cap B|/|B|.</math>

==A very broad overview of the argument==

One of the main features of the argument is that it is ''local'' in character. In other words, it does not try to understand fully the [[obstructions to uniformity]] that cause a set to fail to have the expected number of combinatorial lines. Instead, we are content to find non-quasirandom behaviour inside small subspaces of <math>[3]^n.</math> This happens right from the start. A conjecture that one might hope to be true is that if a set <math>\mathcal{A}</math> is line-free, then there is a dense 12-set <math>\mathcal{U}\otimes\mathcal{V}</math> such that the density of <math>\mathcal{A}</math> inside <math>\mathcal{U}\otimes\mathcal{V}</math> is a bit larger than the density of <math>\mathcal{A}</math> in <math>[3]^n.</math> However, this is not in fact our first step. Instead, we argue that this kind of correlation happens when one restricts to an appropriate subspace. This part of the argument is [[Line-free_sets_correlate_locally_with_complexity-1_sets|given in some detail on a different page]], (where what we are calling 12-sets are called special sets of complexity 1).

Once we have correlation with a 12-set (even if we have had to pass to a subspace to get it) it is natural to try to prove that a 12-set can be partitioned into combinatorial subspaces, since then by averaging we could show that <math>\mathcal{A}</math> correlated with one of those subspaces, and we would be done. An argument similar to [[Sperner's_theorem|the proof of the multidimensional Sperner theorem]] can be used to prove that a dense 12-set contains many combinatorial subspaces. However, it is not at all obvious that one can partition the 12-set into such subspaces (even if small errors are allowed).

However, a different principle comes to the rescue. It is the observation that there are ''two'' kinds of density increment that will be good enough for us. One is a density increment on a subspace, as we already know. The other is a density increment on a 12-set (obtained after passing to a subspace if necessary). Let us spell this out in more detail. Suppose that <math>\mathcal{A}</math> is a line-free set of density <math>\delta</math> and we want to obtain a contradiction. We know two things. First, we can find a 12-subset of a subspace in which <math>\mathcal{A}</math> has increased density <math>\delta+\eta</math>, and secondly, if we can ever prove that there is increased density <math>\delta+\eta/2</math> (say) on a subspace then we are done. However, we can add a third principle, which is that if we can find a 12-subset of a subspace on which the density goes up from <math>\delta+\eta</math> then we are again done. Why? Because we are in the same position as we were in before, but with a slightly higher density, so we can iterate.

Just to be explicit about this, let us briefly describe how the iteration would go. We start with a line-free set <math>\mathcal{A}</math> of density <math>\delta</math> and hope ultimately to obtain a contradiction. To do this, we adopt as a more immediate aim to find a subspace S inside which <math>\mathcal{A}</math> has density at least <math>\delta+\eta(\delta)/2.</math> As a first step, we find a 12-subset of a subspace, inside which <math>\mathcal{A}</math> has density at least <math>\delta+\eta.</math> We now focus our attention on the subproblem of trying to use this to obtain a subspace inside which <math>\mathcal{A}</math> has density at least <math>\delta+\eta/2.</math> But here again we can use the same sort of idea. We do not have to find such a subspace directly: instead, we could prove that if no such subspace exists (so the density of <math>\mathcal{A}</math> inside all subspaces is at most <math>\delta+\eta/2,)</math> then we can find a 12-subset of some further subspace, inside which <math>\mathcal{A}</math> has density at least <math>\delta+\eta+\theta(\delta).</math> And then we can try again to find a subspace where the density is at least <math>\delta+\eta/2.</math> Repeating this argument leads to an iteration within the main iteration, which will eventually terminate with a density increase on a subspace (since the density within a 12-set cannot exceed 1). And then we have completed another step of the main iteration, so we are done.

==A brief description of the main steps of the argument==

'''Step 1.''' Suppose that <math>\mathcal{A}</math> has [[equal-slices_measure|equal-slices density]] <math>\delta.</math> Then we can pass to a <math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math>