Polymath Wiki - User contributions [en]

Coloring Hales-Jewett theorem

2009-06-24T07:21:23Z

130.239.119.161: Undo revision 1751 by 212.92.229.205 (Talk)

==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 (see [http://www.math.ucsd.edu/~etressle/hj32.pdf this paper]):

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

== Improved bounds on HJ(3,3) ==

We can show that <math>HJ(3,3) > 7</math> by exhibiting a 3-colouring of <math>[3]^7</math> with no monochromatic lines.

We start with the set formed by removing (0,1,6), (1,0,6), (0,5,2), (5,0,2) , (1,5,1), (5,1,1),(1,6,0), (6,1,0) from D_7.
Note that none of (0,1,6), (1,0,6), (0,5,2), (5,0,2) , (1,5,1), (5,1,1),(1,6,0), (6,1,0)contains a point whose coordinate sum is divisible by three we give it color 1
where (a,b,c) is shorthand for the slice Γ_a,b,c.
It is combinatorial line free from the n=7 section of the upper and lower bounds wiki at
http://michaelnielsen.org/polymath1/index.php?title=Upper_and_lower_bounds#n.3D7

then we divide the remaining points into all points whose coordinate sum is not equal to 0 mod 9 and
all points of (0,1,6), (1,0,6), (0,5,2), (5,0,2) , (1,5,1), (5,1,1),(1,6,0), (6,1,0)whose coordinate sum is equal to 1 mod 3 We give these color 2

then we take all points of (0,1,6), (1,0,6), (0,5,2), (5,0,2) , (1,5,1), (5,1,1),(1,6,0), (6,1,0)whose coordinate sum equal to 2 mod 3 and those points
whose sum is equal to 0 mod 9. We give these color 3.

Then with this coloring there are nor monochromatic lines. If there are any monochromatic
Lines with number of moving coordinates not divisible by three in color 2 they must contain point whose coordinate sum is equal to 2 mod three
But there are no such points with color 2. If there are any monochromatic lines whose coordinate sum is divisible by three
Than they must contain points whose coordinate sum is 0 mod 9 but there are no such points with color 2. So there
Are no monochromatic combinatorial lines with color 2.

If there are any monochromatic
Lines with number of moving coordinates not divisible by three in color 3 they must contain point whose coordinate sum is equal to 1 mod three
But there are no such points with color 3. If there are any monochromatic lines whose coordinate sum is divisible by three
Than they must contain points whose coordinate sum is not 0 mod 9 but there are no such points with color 3.

As already noted color 1 is combinatorial line free and we are done.

== Improved bounds on HJ(3,r) ==

HJ(3,3) is greater than 13

We take the slices of the thirteen dimensional hypercube
of side three in the following way:
We start with the Van der Warden number W(3,3) from Ramsey Theory
By Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer
second edition.

W(3,3)=27 which gives us a three coloring free of monochromatic
progressions of length 3 of the numbers on through 27

We give the slice (a,b,c) the color associated
with a + 2b +1 in the above coloring then the maximum value is 27
We add one because the coloring in W(3,3) starts with one
and we have zero values in our slices.

Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
triangle and a monochromatic upward triangle would lead to
an arithmetic progression of length three but we have forbidden such a progression by our choice of coloring so we are done.
This is an improvement in the old value of HJ(3,3) is my value of 7 above before that there was a computer generated value of 6 in this paper http://www.math.ucsd.edu/~etressle/hj32.pdf.

HJ(3,4) is greater than 37

We color the slices of the 37 dimensional hypercube
of side three in the following way:
We start with the Van der Warden number W(3,4) from Ramsey Theory
by Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer.
We have an exact value:
W(3,4) = 76 from Ramsey Theory
by Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer.
Which is associated with a four coloring of the
numbers one through 76
which is free of monochromatic arithmetic progressions of
length three.

We give the slice (a,b,c) the color associated
with a + 2b + 1 in the above coloring then the maximum value is 75 so we can color each slice
We add one because the coloring in W(3,4) starts with one
and we have zero values in our slices.
Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
triangle and a monochromatic upward triangle would lead to
an arithmetic progression of length three but we have forbidden such a progression by our choice of coloring so we are done.

HJ(3,5) is greater than 84

We have from
http://www.st.ewi.tudelft.nl/sat/waerden.php
W(3,5) is greater than 170 which is associated with a
five coloring of the points from 1 to 170 free of arithmetic progressions of lenght
three from this we get a coloring of slices by giving the slice (a,b,c)
the color in the above coloring associated with a+2b+1
then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward triangle
which would lead to an arithmetic progression of length three but
we have forbidden such a progression by our choice of coloring so we are done.
This leads to improvements in the existing bounds for c_n in the spreadsheet for
values 82-84 as the density must be greater than 1/r=1/5 for n less than or equal
to 84.

HJ(3,6) is greater than 103

We have from
http://www.st.ewi.tudelft.nl/sat/waerden.php
W(3,6) is greater than 207 which is associated with a
six coloring of the points from 1 to 207 free of arithmetic progressions of length.
three from this we get a coloring of slices by giving the slice (a,b,c)
the color in the above coloring associated with a+2b+1
then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward triangle
which would lead to an arithmetic progression of length three but
we have forbidden such a progression by our choice of coloring so we are done.
Again this leads to improvements in the existing bounds for c_n for 82 to 98 again
as the density must be greater than 1/r=1/6 for n less than or equal
to 103 and the table stops at 98.

HJ(3,r) is greater than r^{clnr}/2-1

We have from
from Ramsey Theory
by Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer,second edition page 103.
W(3,r) is greater than r^{clnr} which is associated with a
t coloring of the points from 1 to r^{clnr} free of arithmetic progressions of length.
three from this we get a coloring of slices by giving the slice (a,b,c)
the color in the above coloring associated with a+2b+1
then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward triangle
which would lead to an arithmetic progression of length three but
we have forbidden such a progression by our choice of coloring so we are done.

== Improved bounds on HJ(4,r) ==

HJ(4,2) is greater than 11

We start with the Van der Warden number W(4,2) from Ramsey Theory
by Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer for which
we have an exact value:
W(4,2)=35 with this is associated a two coloring of the
numbers one through 35 with no monochromatic progression
of length four.

We give the slices (a,b,c,d) of the 11th dimensional
hypercube of side 4 the color associated
with a + 2b + 3c + 1 then the maximum value is 34
so our coloring is well defined.
We add one because the coloring in W(4,2) starts with one
and we have zero values in our slices.
Then we will not have a monochromatic combinatorial line
because we will have no monochromatic upward tetrahedrons
because they would lead to an arithmetic progression of length four which we
have forbidden in our choice of coloring.

HJ(4,3) is greater than 97

We start with W(4,3) is greater than 292
from http://www.st.ewi.tudelft.nl/sat/waerden.php
We let the dimension be 97 then give the slices
the color associated with a+2b+3c+1 in the three coloring
of 292 which has no monochromatic arithmetic progression
of length four. Then since a monochromatic combinatorial line would
lead to a monochromatic upward tetrahedron which would lead to an
arithmetic progression of length four which we have forbidden we are done.

HJ(4,4) is greater than 349

We start with W(4,4) is greater than 1048
from http://www.st.ewi.tudelft.nl/sat/waerden.php
We let the dimension be 349 then give the slices
the color associated with a+2b+3c+1 in the three coloring
of 1048 which has no monochromatic arithmetic progression
of length four. Then since a monochromatic combinatorial line would
lead to a monochromatic upward tetrahedron which would lead to an
arithmetic progression of length four which we have forbidden we are done.

HJ(4,5) is greater than 751

We start with W(4,5) is greater than 2254
from http://www.st.ewi.tudelft.nl/sat/waerden.php
We let the dimension be 751 then give the slices
the color associated with a+2b+3c+1 in the three coloring
of 2254 which has no monochromatic arithmetic progression
of length four. Then since a monochromatic combinatorial line would
lead to a monochromatic upward tetrahedron which would lead to an
arithmetic progression which we have forbidden we are done.

HJ(4,6) is greater than 3259

We start with W(4,6) is greater than 9778
from http://www.st.ewi.tudelft.nl/sat/waerden.php
We let the dimension be 3259 then give the slices
the color associated with a+2b+3c+1 in the three coloring
of 9778 which has no monochromatic arithmetic progression
of length four. Then since a monochromatic combinatorial line would
lead to a monochromatic upward tetrahedron which would lead to an
arithmetic progression which we have forbidden we are done.

== Improved bounds on HJ(5,r) ==

HJ(5,2) is greater than 59

We color the slices of the 59 dimensional hypercube
of side five in the following way:
We start with the Van der Warden number W(5,2) for which
we have an exact value:
W(5,2) =178
from Ramsey Theory
by Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer
this is associated with a two coloring of the numbers from
1 to 178 with no arithmetic progression of length 5
We give the slice (a,b,c,d,e) the color associated
with a + 2b + 3c+4d+1 then the maximum value is 178
so the coloring is well defined.
We add one because the coloring in W(5,2) starts with one
and we have zero values in our slices.
Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
simplex of dimension four whose vertices are (a+r,b,c,d,e), (a,b+r,c,d,e) etc. and a monochromatic upward simplex of dimension four would lead to
an arithmetic progression of length five but we have forbidden such a progression by our choice of coloring so we are done.

HJ(5,3) is greater than 302

We color the slices of the 302 dimensional hypercube
of side five in the following way:
We start with the Van der Warden number W(5,3) for which
we have
W(5,3) is greater than 1209 see
http://www.st.ewi.tudelft.nl/sat/waerden.php associated with a two coloring of the numbers from
1 to 1209 with no arithmetic progression of length 5
We give the slice (a,b,c,d,e) the color associated
with a + 2b + 3c + 4d + 1 then the maximum value is 1209
so the coloring is well defined.
We add one because the coloring in W(5,3) starts with one
and we have zero values in our slices.
Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
simplex of dimension four whose vertices are (a+r,b,c,d,e), (a,b+r,c,d,e) etc. and a monochromatic upward simplex of dimension four would lead to
an arithmetic progression of length five but we have forbidden such a progression by our choice of coloring so we are done.

HJ(5,4) is greater than 2609

We color the slices of the 2609 dimensional hypercube
of side five in the following way:
We start with the Van der Warden number W(5,4) for which
we have
W(5,4) is greater than 10437 see
http://www.st.ewi.tudelft.nl/sat/waerden.php associated with a three coloring of the numbers from 1 to 1209 with no arithmetic progression of length 5
We give the slice (a,b,c,d,e) the color associated
with a + 2b + 3c + 4d + 1 then the maximum value is 2609
so the coloring is well defined.
Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
simplex of dimension four and a monochromatic upward simplex of dimension four would lead to
an arithmetic progression of length five but we have forbidden such a progression by our choice of coloring so we are done.

HJ(5,5) is greater than 6011

We color the slices of the 6011 dimensional hypercube
of side five in the following way:
We start with the Van der Warden number W(5,5) for which
we have W(5,5) is greater than 24045 see
http://www.st.ewi.tudelft.nl/sat/waerden.php associated with a three coloring of the numbers from 1 to 24045 with no arithmetic progression of length 5
We give the slice (a,b,c,d,e) the color associated
with a + 2b + 3c + 4d + 1
Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
simplex of dimension four and a monochromatic upward simplex of dimension four would lead to
an arithmetic progression of length five but we have forbidden such a progression by our choice of coloring so we are done.

HJ(5,6) is greater than 14173

We color the slices of the 14173 dimensional hypercube
of side five in the following way:
We start with the Van der Warden number W(5,6) for which
we have W(5,6) is greater than 56693 see
http://www.st.ewi.tudelft.nl/sat/waerden.php associated with a three coloring of the numbers from 1 to 56693 with no arithmetic progression of length 5
We give the slice (a,b,c,d,e) the color associated
with a + 2b + 3c + 4d + 1
Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
simplex of dimension four and a monochromatic upward simplex of dimension four would lead to
an arithmetic progression of length five but we have forbidden such a progression by our choice of coloring so we are done.

== Improved bounds on HJ(6,r) ==

HJ(6,2) is greater than 226

We color the slices of the 226 dimensional hypercube
of side six in the following way:
We start with the Van der Warden number W(6,2) for which
we have an exact value from http://www.st.ewi.tudelft.nl/sat/waerden.php:
W(6,2) =1131
this is associated with a two coloring of the numbers from
1 to 1131 with no arithmetic progression of length 6.

We give the slice (a,b,c,d,e,f) the color associated
with a + 2b + 3c + 4d +5e + 1 then the maximum value is 1131
so the coloring is well defined.
We add one because the coloring in W(6,2) starts with one
and we have zero values in our slices.

Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
simplex of dimension five whose vertices are (a+r,b,c,d,e,f), (a,b+r,c,d,e,f) etc. and a monochromatic upward simplex of dimension five would lead to
an arithmetic progression of length six but we have forbidden such a progression by our choice of coloring so we are done.

HJ(6,3) is greater than 1777

We color the slices of the 1777 dimensional hypercube
of side six in the following way:
We start with the Van der Warden number W(6,3) for which
we have from http://www.st.ewi.tudelft.nl/sat/waerden.php:
W(6,3) is greater than 8886
this is associated with a three coloring of the numbers from
1 to 8886 with no arithmetic progression of length 6.

We give the slice (a,b,c,d,e,f) the color associated
with a + 2b + 3c + 4d +5e + 1.

Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
simplex of dimension five and a monochromatic upward simplex of dimension five would lead to
an arithmetic progression of length six but we have forbidden such a progression by our choice of coloring so we are done.

HJ(6,4) is greater than 18061

We color the slices of the 18061 dimensional hypercube
of side six in the following way:
We start with the Van der Warden number W(6,3) for which
we have from http://www.st.ewi.tudelft.nl/sat/waerden.php:
W(6,3)is greater than 90306.

We give the slice (a,b,c,d,e,f) the color associated
with a + 2b + 3c + 4d +5e + 1.

Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
simplex of dimension five and a monochromatic upward simplex of dimension five would lead to
an arithmetic progression of length six but we have forbidden such a progression by our choice of coloring so we are done.

HJ(6,5) is greater than 49391

We start with the Van der Warden number W(6,5) for which
we have from http://www.st.ewi.tudelft.nl/sat/waerden.php:
W(6,5)is greater than 246956.

We give the slice (a,b,c,d,e,f) the color associated
with a + 2b + 3c + 4d +5e + 1.

Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
simplex of dimension five and a monochromatic upward simplex of dimension five would lead to
an arithmetic progression of length six but we have forbidden such a progression by our choice of coloring so we are done.

HJ(6,6) is greater than 120097

We start with the Van der Warden number W(6,6) for which
we have from http://www.st.ewi.tudelft.nl/sat/waerden.php:
W(6,6)is greater than 600486.

We give the slice (a,b,c,d,e,f) the color associated
with a + 2b + 3c + 4d +5e + 1.

Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
simplex of dimension five and a monochromatic upward simplex of dimension five would lead to
an arithmetic progression of length six but we have forbidden such a progression by our choice of coloring so we are done.

== Improved bounds on HJ(7,r) ==

HJ(7,2) is greater than 617

We color the slices of the 617 dimensional hypercube
of side seven in the following way:
We start with the Van der Warden number W(7,2) for which
we have from http://www.st.ewi.tudelft.nl/sat/waerden.php:
W(7,2)is greater than 3703
this is associated with a two coloring of the numbers from
1 to 3703 with no arithmetic progression of length 7.

We give the slice (a,b,c,d,e,f,g) the color associated
with a + 2b + 3c + 4d +5e + 6f+ 1 then the maximum value is 3703
so the coloring is well defined.
We add one because the coloring in W(7,2) starts with one
and we have zero values in our slices.

Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
simplex of dimension six whose vertices are (a+r,b,c,d,e,f,g), (a,b+r,c,d,e,f,g) etc. and a monochromatic upward simplex of dimension six would lead to
an arithmetic progression of length seven but we have forbidden such a progression by our choice of coloring so we are done.

HJ(7,3) is greater than 7309

We start with the Van der Warden number W(7,3) for which
we have from http://www.st.ewi.tudelft.nl/sat/waerden.php:
W(7,3) is greater than 43855
this is associated with a two coloring of the numbers from
1 to 43855 with no arithmetic progression of length 7.

We give the slice (a,b,c,d,e,f,g) the color associated
with a + 2b + 3c + 4d +5e + 6f+ 1.

Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
simplex of dimension six (a+r,b,c,d,e,f,g) (a,b+r,c,d,e,f,g) etc. and a monochromatic upward simplex of dimension six would lead to
an arithmetic progression of length seven but we have forbidden such a progression by our choice of coloring so we are done.

HJ(7,4) is greater than 64661

We start with the Van der Warden number W(7,4) for which
we have from http://www.st.ewi.tudelft.nl/sat/waerden.php:
W(7,4) is greater than 387967
this is associated with a two coloring of the numbers from
1 to 43855 with no arithmetic progression of length 7.

We give the slice (a,b,c,d,e,f,g) the color associated
with a + 2b + 3c + 4d +5e + 6f+ 1.

Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
simplex of dimension six (a+r,b,c,d,e,f,g) (a,b+r,c,d,e,f,g) etc. and a monochromatic upward simplex of dimension six would lead to
an arithmetic progression of length seven but we have forbidden such a progression by our choice of coloring so we are done.

== Improved bounds on HJ(8,r) ==

HJ(8,2) is greater than 1069

We color the slices of the 1069 dimensional hypercube
of side eight in the following way:
We start with the Van der Warden number W(8,2) for which
we have from http://www.st.ewi.tudelft.nl/sat/waerden.php:
W(8,2) is greater than 7484
this is associated with a two coloring of the numbers from
1 to 7484 with no arithmetic progression of length 8.

We give the slice (a,b,c,d,e,f,g,h) the color associated
with a + 2b + 3c + 4d +5e + 6f + 7g + 1.
We add one because the coloring in W(8,2) starts with one
and we have zero values in our slices.

Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
simplex of dimension seven whose vertices are (a+r,b,c,d,e,f,g,h) (a,b+r,c,d,e,f,g,h) etc. and a monochromatic upward simplex of dimension seven would lead to
an arithmetic progression of length eight but we have forbidden such a progression by our choice of coloring so we are done.

HJ(8,3) is greater than 34057

We color the slices of the 34057 dimensional hypercube
of side eight in the following way:
We start with the Van der Warden number W(8,3) for which
we have from http://www.st.ewi.tudelft.nl/sat/waerden.php:
W(8,3) is greater than 238400
this is associated with a three coloring of the numbers from
1 to 238400 with no arithmetic progression of length 8.

We give the slice (a,b,c,d,e,f,g,h) the color associated
with a + 2b + 3c + 4d +5e + 6f + 7g + 1.
We add one because the coloring in W(8,3) starts with one
and we have zero values in our slices.

Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
simplex of dimension seven whose vertices are (a+r,b,c,d,e,f,g,h), (a,b+r,c,d,e,f,g,h) etc. and a monochromatic upward simplex of dimension seven would lead to
an arithmetic progression of length eight but we have forbidden such a progression by our choice of coloring so we are done.

== Improved bounds on HJ(9,r) ==

HJ(9,2) is greater than 3389

We color the slices of the 3389 dimensional hypercube
of side 9 in the following way:
We start with the Van der Warden number W(9,2) for which
we have from http://www.st.ewi.tudelft.nl/sat/waerden.php:
W(9,2) is greater than 27113
this is associated with a two coloring of the numbers from
1 to 27113 with no arithmetic progression of length 9.

We give the slice (a,b,c,d,e,f,g,h,i) the color associated
with a + 2b + 3c + 4d +5e + 6f + 7g + 8h + 1.
We add one because the coloring in W(9,2) starts with one
and we have zero values in our slices.

Then we will not have a monochromatic combinatorial line
because it would correspond to a monochromatic upward
simplex of dimension eight whose vertices are (a+r,b,c,d,e,f,g,h.i), (a,b+r,c,d,e,f,g,h,i) etc. and a monochromatic upward simplex of dimension eight would lead to
an arithmetic progression of length nine but we have forbidden such a progression by our choice of coloring so we are done.

== Improved bounds on HJ(n,r) ==

HJ(n,r) is greater than ((r^n/ern(1+o(1)))/n-1) -2

We start with the bound W(n,r) is greater than r^n/erk(1+o(1))
which is from the website

http://mathworld.wolfram.com/vanderWaerdenNumber.html

which gives the reference
Heule, M. J. H. “Improving the Odds: New Lower Bounds for Van der Waerden Numbers.” March 4, 2008. http://www.st.ewi.tudelft.nl/sat/slides/waerden.pdf.

Set the dimension equal to ((r^n/ern(1+o(1)))/n-1) -2

then we take that coloring and give it to give a point the color associated with a +2b+.. continued n-1 times
we can do tbis because the dimension is ((r^n/ern(1+o(1)))/n-1) -2
There is no n-1 dimensional upward simplex as then we would
have a monochromatic arithmetic progression which we have forbidden but since we have no monochromatic upward n-1 dimensional simplex we will have no combinatorial lines and so we are done.

Talk:Main Page

2009-06-24T07:20:58Z

130.239.119.161: Undo revision 1735 by 93.80.175.110 (Talk)

Metacomment: it would be cool to have a polymath logo to replace "set $wgLogo to the URL path...".

Talk:Main Page

2009-06-24T07:20:34Z

130.239.119.161: Undo revision 1750 by 78.106.184.160 (Talk)

Metacomment: it would be cool to have a polymath logo to replace "set $wgLogo to the URL path...".

== Protection key ==

http://key-key.sqweebs.com/key-west-florida.html <a href=" http://key-key.sqweebs.com/key-west-florida.html ">key west florida</a> http://key-key.sqweebs.com/hl-cd-key.html <a href=" http://key-key.sqweebs.com/hl-cd-key.html ">hl cd key</a> http://protection.sqweebs.com/wood-stove-wall-protection.html <a href=" http://protection.sqweebs.com/wood-stove-wall-protection.html ">wood stove wall protection</a> http://key-key.sqweebs.com/half-life-valid-cd-key.html <a href=" http://key-key.sqweebs.com/half-life-valid-cd-key.html ">half life valid cd key</a> http://key-key.sqweebs.com/key-west-hotels.html <a href=" http://key-key.sqweebs.com/key-west-hotels.html ">key west hotels</a> http://key-key.sqweebs.com/aneta-keys.html <a href=" http://key-key.sqweebs.com/aneta-keys.html ">aneta keys</a> http://protection.sqweebs.com/texas-motorist-protection-act.html <a href=" http://protection.sqweebs.com/texas-motorist-protection-act.html ">texas motorist protection act</a> http://key-key.sqweebs.com/index12.html <a href=" http://key-key.sqweebs.com/index12.html ">map key symbols</a> http://protection.sqweebs.com/remote-trojan-protection.html <a href=" http://protection.sqweebs.com/remote-trojan-protection.html ">remote trojan protection</a> http://key-key.sqweebs.com/recover-my-files-229-key-generator.html <a href=" http://key-key.sqweebs.com/recover-my-files-229-key-generator.html ">recover my files 2.29 key generator</a> http://protection.sqweebs.com/cats-protection-league.html <a href=" http://protection.sqweebs.com/cats-protection-league.html ">cats protection league</a> http://key-key.sqweebs.com/key-west-fl.html <a href=" http://key-key.sqweebs.com/key-west-fl.html ">key west, fl</a> http://key-key.sqweebs.com/index4.html <a href=" http://key-key.sqweebs.com/index4.html ">half life cd key generator</a> http://protection.sqweebs.com/identity-protection.html <a href=" http://protection.sqweebs.com/identity-protection.html ">identity protection</a> http://key-key.sqweebs.com/game-cd-key-finders.html <a href=" http://key-key.sqweebs.com/game-cd-key-finders.html ">game cd key finders</a> http://protection.sqweebs.com/marine-life-protection.html <a href=" http://protection.sqweebs.com/marine-life-protection.html ">marine life protection</a> http://key-key.sqweebs.com/index13.html <a href=" http://key-key.sqweebs.com/index13.html ">map key symbols</a> http://key-key.sqweebs.com/finding-wep-key.html <a href=" http://key-key.sqweebs.com/finding-wep-key.html ">finding wep key</a> http://protection.sqweebs.com/free-microsoft-virus-protection.html <a href=" http://protection.sqweebs.com/free-microsoft-virus-protection.html ">free microsoft virus protection</a> http://key-key.sqweebs.com/working-hl-key.html <a href=" http://key-key.sqweebs.com/working-hl-key.html ">working hl key</a> http://key-key.sqweebs.com/index9.html <a href=" http://key-key.sqweebs.com/index9.html ">key sat</a> http://protection.sqweebs.com/sun-protection-hats.html <a href=" http://protection.sqweebs.com/sun-protection-hats.html ">sun protection hats</a> http://protection.sqweebs.com/construction-protection-chicago-remodeling.html <a href=" http://protection.sqweebs.com/construction-protection-chicago-remodeling.html ">construction protection chicago remodeling</a> http://key-key.sqweebs.com/alicia-keys-bikini-photo.html <a href=" http://key-key.sqweebs.com/alicia-keys-bikini-photo.html ">alicia keys bikini photo</a> http://key-key.sqweebs.com/siesta-key.html <a href=" http://key-key.sqweebs.com/siesta-key.html ">siesta key</a> http://protection.sqweebs.com/bypass-dvd-copyright-protection.html <a href=" http://protection.sqweebs.com/bypass-dvd-copyright-protection.html ">bypass dvd copyright protection</a> http://protection.sqweebs.com/radiation-protection.html <a href=" http://protection.sqweebs.com/radiation-protection.html ">radiation protection</a> http://key-key.sqweebs.com/london-keys.html <a href=" http://key-key.sqweebs.com/london-keys.html ">london keys</a> http://protection.sqweebs.com/environmental-protection-agency.html <a href=" http://protection.sqweebs.com/environmental-protection-agency.html ">environmental protection agency</a> http://key-key.sqweebs.com/keys-to-a-healthy-lifestyle.html <a href=" http://key-key.sqweebs.com/keys-to-a-healthy-lifestyle.html ">keys to a healthy lifestyle</a>
It`s really great!

Talk:Line

2009-06-23T07:09:06Z

130.239.119.161: Removing all content from page

Corners theorem

2009-06-23T07:08:37Z

130.239.119.161: Undo revision 1736 by 12.24.98.34 (Talk)

'''Corners theorem''': (<math>{\Bbb Z}/N{\Bbb Z}</math> version) If N is sufficiently large depending on <math>\delta</math>, then any <math>\delta</math>-dense subset of <math>{}[N]^2</math> must contain a "corner" (x,y), (x+r,y), (x,y+r) with <math>r > 0</math>.

'''Corners theorem''': (<math>({\Bbb Z}/3{\Bbb Z})^n</math> version) If n is sufficiently large depending on <math>\delta</math>, then any <math>\delta</math>-dense subset of <math>{}(({\Bbb Z}/3{\Bbb Z})^n)^2</math> must contain a "corner" (x,y), (x+r,y), (x,y+r) with <math>r \neq 0</math>.

This result was first proven by [[Ajtai-Szemerédi's proof of the corners theorem|Ajtai and Szemerédi]]. A simpler proof, based on the [[triangle removal lemma]], was obtained by Solymosi. The corners theorem implies [[Roth's theorem]] and is in turn implied by the [[IP-Szemerédi theorem]], which in turn follows from [[DHJ(3)]].

One consequence of the corners theorem is that any subset of the triangular grid

:<math>\Delta_n = \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c=n\}</math>

of density at least <math>\delta</math> will contain an equilateral triangle <math>(a+r,b,c),(a,b+r,c),(a,b,c+r)</math> with <math>r>0</math>, if n is sufficiently large depending on <math>\delta</math>.

A [[DHJ(1,3)|special case of the corners theorem]] is of interest in connection with [[DJH(1,3)]].

Talk:Main Page

2009-06-17T08:05:21Z

130.239.119.161: Undo revision 1689 by 93.80.199.215 (Talk)

Metacomment: it would be cool to have a polymath logo to replace "set $wgLogo to the URL path...".

Talk:Main Page

2009-06-09T07:02:58Z

130.239.119.161: Undo revision 1602 by 89.178.120.134 (Talk)

Metacomment: it would be cool to have a polymath logo to replace "set $wgLogo to the URL path...".

Obstructions to uniformity

2009-06-05T08:02:17Z

130.239.119.161: Undo revision 1557 by 93.190.138.249 (Talk)

Suppose that we have a definition of [[quasirandomness]] for subsets of some structure. As stated in the quasirandomness article, a definition of quasirandomness is not very useful unless one has some understanding of sets that are ''not'' quasirandom. Let S be a structure (such as a complete graph, <math>[3]^n,</math> a finite Abelian group, or <math>[n]^2</math>) and let A be a subset of S of density <math>\delta</math>. Let f be <math>1-\delta</math> on A and <math>-\delta</math> on the complement of A. Then the average of f is zero. Typically, one would like to show that if A, or equivalently f, is not quasirandom then there is some "structured subset" <math>S'\subset S</math> such that <math>\mathbb{E}_{x\in S'}f(x)\geq c</math> for some positive constant c that depends on <math>\delta</math> only. Better still, one would like a converse: that any function that has positive expectation on a substructure must fail to be quasirandom. If we can do this, then we say that we have a complete set of obstructions to uniformity. ("Uniformity" is sometimes used as a synonym for "quasirandomness".)

More generally, we can look not for structured sets but structured ''functions''. In this case we would like to find a set G of functions such that for every non-quasirandom function f there exists g in G such that <math>\mathbb{E}_{x\in S}f(x)g(x)\geq c,</math> and such that if there exists such a g then f is not quasirandom.

==Examples==

====Graphs====

If f is a non-quasirandom function defined on the edges of the complete graph <math>K_n,</math> then there are sets X and Y of vertices of linear size such that <math>\mathbb{E}_{(x,y)\in X\times Y}f(x,y)\geq c,</math> where c is a positive constant that depends on the degree of non-quasirandomness of f. Conversely, if such vertex sets exist, then f is not quasirandom.

====Functions defined on <math>\mathbb{Z}_N</math>====

If f is a non-quasirandom function defined on <math>\mathbb{Z}_N,</math> then there exists an integer r such that <math>\mathbb{E}_{x\in\Z_N}f(x)exp(2\pi irx/N)\geq c,</math> where again c is a positive constant that depends on the degree of non-quasirandomness of f. Again, the converse holds as well. Thus, in this case the trigonometric functions form a complete set of obstructions to quasirandomness.

==The relevance to the density Hales-Jewett theorem==

It is possible to think about obstructions to uniformity even in the absence of a precisely formulated definition of quasirandomness. For example, in the case of the density Hales-Jewett theorem, we know that we want quasirandom sets to contain roughly the expected number of combinatorial lines. Therefore, we can temporarily (and unsatisfactorily) ''define'' a quasirandom set to be one that contains roughly the expected number of combinatorial lines and try to classify "extreme examples" of sets that do not contain roughly the expected number. These extreme examples will typically be highly structured sets: for instance, the set of all sequences x such that <math>x_1=1</math> is easily shown to have more combinatorial lines than a random set of density 1/3, but it is also a highly structured subset of <math>[3]^n.</math> If these examples appear to belong to a limited number of types, we can then hypothesize that ''every'' set with the wrong number of combinatorial lines correlates with one of these extreme examples. It is these extreme examples that one calls obstructions to uniformity.

Once we have formulated a conjecture of this type, we would hope to prove it in two stages as follows.

*Every quasirandom set contains roughly as many combinatorial lines as a random set of the same density. Therefore, a set with the wrong number of combinatorial lines is not quasirandom.

*Every non-quasirandom set is noticeably correlated with an obstruction to uniformity.

==Possible candidates==

The obstructions to uniformity appear to be hard to describe if one uses the uniform measure on <math>[3]^n,</math> even if one localizes to a few slices. However, if one uses [[equal-slices measure]], then all known obstructions are sets of the following form. (The next couple of paragraphs are lifted from [http://michaelnielsen.org/polymath1/index.php?title=DHJ%283%29&section=4 the discussion of DHJ(1,3)].)

Let <math>\mathcal{U},\mathcal{V}</math> and <math>\mathcal{W}</math> be collections of subsets of <math>[n].</math> Define <math>\mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W})</math> to be the set of all triples <math>(U,V,W),</math> where <math>U,V,W</math> are disjoint, and <math>U\in\mathcal{U},V\in\mathcal{V},W\in\mathcal{W}.</math> These triples are in an obvious one-to-one correspondence with elements of <math>[3]^n.</math>

Call <math>\mathcal{A}</math> a ''set of complexity 1'' if it is of the form <math>\mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W})</math>. For instance, a [[slice]] <math>\Gamma_{a,b,c}</math> is of complexity 1, as is a union of slices of the form <math>\bigcup\{\Gamma_{a,b,c}:(a,b,c)\in A\times B\times C, a+b+c=n\}</math>

It is conceivable, though certainly not proved, that every set that does not contain roughly the expected number of combinatorial lines, given its density (where everything is with respect to equal-slices measure) correlates significantly with a set of complexity 1. In the opposite direction, sets of complexity 1 do give a large source of examples of sets with the wrong number of combinatorial lines.

DJH(1,3)

2009-05-29T09:50:12Z

130.239.119.161: Removing all content from page

Talk:Main Page

2009-05-25T11:23:46Z

130.239.119.161:

Metacomment: it would be cool to have a polymath logo to replace "set $wgLogo to the URL path...".

Talk:Main Page

2009-05-25T11:23:32Z

130.239.119.161:

Metacomment: it would be cool to have a polymath logo to replace "set $wgLogo to the URL path...". [[User:Rainjacket|Rainjacket]]