This is a continuation of the preceding two threads here on the polymath1 project, which are now full. We are closing on on the computation of the sixth Moser number – the size of the largest subset of the six-dimensional cube 
Besides this, the nominal purpose of this thread is to coordinate the writing of the second paper of the project. In addition to incorporating whatever results we get from the six-dimensional Moser problem, a lot of work still has to be done on other sections of the paper, notably the higher k component and the component on Fujimura’s problem, as well as the appendices.
24 comments
Comments feed for this article
9 July, 2009 at 9:15 am
Terence Tao
It looks like Michael and Kristal have shown that a (5,12,12,4,1) slice cannot intersect a (6,12,18,4,0) slice in either a (2,6,6,0) pattern or a (4,3,3,1) pattern. If so, then this shows that (5,12,12,4,1) slices do not occur. (Proof: if such a slice does occur, then by the preceding analysis (see my 8 July 11:18 am comment), it must contain a 3D slice which is either (1,6,3,0) or (3,3,0,1). But every 3D slice must be adjacent to a slice of (6,12,18,4,0), which is either (2,6,6,0) or (4,3,3,1). These two adjacent 3D slices must span a (5,12,12,4,1) 4D slice (as they cannot span a (6,12,18,4,0) or (5,12,18,4,0)), and so we have a (5,12,12,4,1) slice intersecting a (6,12,18,4,0) slice.)
Assuming everything is correct so far, the remaining scenario left to eliminate for 354-point 6D Moser sets is:
* All 4D slices are either (6,12,18,4,0) or (5,12,18,4,0). Each family of four parallel slices contains two of each type.
* All 3D slices are either (2,6,6,0), (4,3,3,1), (1,6,6,0), or (3,3,3,1). The (6,12,18,4,0) slices split as (2,6,6,0)+(4,3,3,1); the (5,12,18,4,0) slices split as (1,6,6,0)+(4,3,3,1) or (2,6,6,0)+(3,3,3,1).
As in the wiki, we can assign each (6,12,18,4,0) a _type_ based on what “d” points they have; one can also assign a type to (5,12,18,4,0) slices similarly. We know that opposing d points (e.g. 111222 and 113222) cannot both lie in the set, or both be absent from the set (see Kristal’s 3 July 6:02 pm comment). Because of this, two adjacent 4D slices (e.g. 11**** and 13****) must have opposite types, and hence any two diagonally opposite 4D slices (e.g. 11**** and 33****) must have the same type. On the wiki it is shown that two diagonally opposite (6,12,18,4,0) slices with the same type cannot occur (they eliminate far too many points in the center slice), so we conclude that 11**** and 33**** cannot both be (6,12,18,4,0). Similarly for 13**** and 31****; meanwhile, these four slices must somehow accommodate two (6,12,18,4,0)’s and two (5,12,18,4,0)’s. Thus:
* Given two diagonally opposite 4D slices, one of them must be (6,12,18,4,0) and the other (5,12,18,4,0), and they must be of the same type. (e.g. if the 11**** slice contains 111222, then the 33**** slice must contain 33122).
This is quite a bit of progress… hopefully with a few more observations we should be able to eliminate the last remaining cases, either by hand or by computer search.
Incidentally, the above facts pin down the statistics of a 6D 354 Moser set precisely, to be (22, 72, 180, 80, 0, 0, 0). I don’t see how to gain any additional mileage out of this that we can’t already see from the 3D and 4D slice information, though.
9 July, 2009 at 12:23 pm
Kristal Cantwell
If the c and the d points are the same for (6,12,18,4,0)
and (5,12,18,4,0) sets which I think is true and these are the only sets left then can’t the following argument
from the wiki:
“Note: in the 353-point example given above, the 11**** slices are good (and of type 1111), the 13**** slices have statistics (5,12,18,4,0) and consist of the type 3333 slice with the point 133333 removed, and the 33**** slices have statistics (6,8,12,8,0), with the slice consisting of the 6 a-points formed by permuting 1133, the 8 b-points formed by permuting 1112 and 3332, the 12 c-points formed by permuting 1122 and 3322, and all 8 d-points.
We now show that it is impossible to have a 356-point set, i.e. one in which all corner slices are good. From the above discussion, we see that if the 111*** slice contains its center 111222, then the 113*** slice does not, and vice versa. Tthus the d points of the form ***222 consist either of those strings with an even number of 1s, or those with an odd number of 1s.
Let’s say it’s the former, thus the set contains 111222, 133222, and permutations of the first three coordinates, but omits 113222, 333222 and permutations of the first three coordinates. Meanwhile, we see that the (24,72,180,80,0,0,0) set saturates the inequality 4c+3d \leq 960, which is only possible if every line connecting two “c” points to a “d” point meets exactly two elements in the set. Since the “d” points 113222, 333222 are omitted, we conclude that the “c” points 113122, 113322, 333122, 333322 must lie in the set, and similarly for permutations of the first three and last three coordinates. But this gives at least 15 of the 16 “c” points ending in 22; by symmetry this leads to 225 c-points in all, which is far too many. ”
be adapted to get rid of the remaining 354 point cases?
9 July, 2009 at 2:27 pm
Terence Tao
Hmm, I think you’re right! Then it looks like we have in fact shown that
.
I’ve put the argument on the wiki. The wiki proof is not the most efficient proof – this is a consequence of it evolving from the
argument, followed by the 
argument, then 
argument, and then finally the 
argument, but I’ll put a more coherent argument in the LaTeX writeup, which will also provide an opportunity to double-check various steps (and in particular to identify exactly what parts of the argument require computer verification).
Michael, did anything special have to be done to do your computer searches of the various 4D slices, or was brute force sufficient?
9 July, 2009 at 8:19 pm
Michael Peake
I accidentally answered your question in the previous thread instead of this one.
9 July, 2009 at 10:55 pm
Terence Tao
I’ve made a new version of the paper at
http://terrytao.wordpress.com/files/2009/07/polymath.pdf
It has the
proof, except for a few things that were proven by computer and which we will have to describe in a bit more detail.
As the paper was getting a bit long, I decided to omit some of the human proofs of things that we can do by computer, instead referring the reader to the relevant wiki page for details.
I think we’re pretty much done on the Moser number side of things: the bounds
we have are just too far apart to have any realistic hope of narrowing the gap in any reasonable amount of time. The big things left to do are to put in the higher k stuff, the Fujimura stuff, whatever we have on the coloring HJ problem, and then once all the material is there, to figure out how to keep the paper reasonable in size and focus (perhaps by moving some content to the wiki as necessary).
10 July, 2009 at 11:10 am
Kristal Cantwell
The main improvement we have in coloring is related to the connection between Moser(n, 2k) and DHJ(n,k). We can get a similar connection to coloring numbers Let HJ(k, r) be the coloring number for a cube of side k and r colors(here we are looking for a combinatorial line and M(k,r) be the coloring number for a cube of side k and r colors. then we get a connection between the two that allows an improvement in the M(k,r) and also the use of Van der Warden numbers in constructing the M(k,r). Previously the methond used in getting the M(k,r) was looking at sets free of quadratic sequences instead of arithmetic sequences. We also have HJ(k,r) numbers that appear to be new but are constructed by a known method. I am thinking of just referring to the wiki for this.
I have a question if we are given a density and a length k and we want an n that at that density that must have a k-length arithmetic progression what does that function look like for k = 1 through 6? Because I think the the other paper combined with some of the results here might make those numbers lie within primitive recursive bounds.
10 July, 2009 at 7:18 pm
Kristal Cantwell
It looks like it might be possible to narrow the gap between the upper and lower bounds of c_7′ the Maple calculations seem to have been done before it was known that the larges c_6′ set was 353 and it looks like the example appears to have g=2 now it looks like if g=2 and we can get one side slice equal to 337 and the center slice will have another g point if not both side slices are of size 337 and we get the total number of points less than 1041. Because of the above I doubt the 1041 bound is realized and it might be relatively easier to improve. Are there 353 point Moser sets in six dimensions with 5 2’s? On the other hand if we are going to submit the paper in April we will probably not get c_7′ by then and even if we did we would run into space problems. I think the 1041 bound might be quickly improved though.
Also in my last post k=1 and 2 are trivial and I think we cannot get an improvement for 3 for this question:
“if we are given a density and a length k and we want an n that at that density that must have a k-length arithmetic progression what does that function look like for k less than 6?”
And now that I think about it I am less optimistic about the cases 4,5 and 6. Although I have no idea what the existing numbers are so it is possible there could be an improvement.
10 July, 2009 at 8:57 pm
Terence Tao
Dear Kristal,
I added in the
bound to the Maple calculations (it’s the line “X6 := {op(X6), A6+16*g 0, but at best this will just send g to zero, thus lowering the 1041 upper bound by at most two, which is still a fair way from 1017.) Also, we are getting further and further away from the last case we understand completely, namely the 4D case where we have the complete Pareto-optimal list, and the capability to classify sets of a given statistic, so I would imagine the 7D case would be quite a deal harder than the 6D case, unfortunately.
Regarding your question about arithmetic progressions, I think this is basically equivalent to getting the best possible bounds for Szemeredi’s theorem, see
http://en.wikipedia.org/wiki/Szemer%C3%A9di%27s_theorem
The number n you are looking for is basically
.
11 July, 2009 at 9:07 am
Kristal Cantwell
I added the counterexample to the HOC for all even numbers great than 4 to the following section of the paper
http://michaelnielsen.org/polymath1/index.php?title=Higherk.tex
11 July, 2009 at 1:38 pm
Frank
Dr. Tao,
cud u plz say something about how to ‘create’ a new theory? I find it is sad when I have to follow other’s step, and make small modifications.
Thank you.
Frank
20 July, 2009 at 4:56 am
Michael Peake
I think I have found a problem in the writeup of the 353 proof, in Moser.tex
In lemma \ref{f6}, proving that f(A)=0, it is assumed [3]^6 has 30 edge slices. I think it has 60 edge slices, which would affect the proof of this lemma in several places.
20 July, 2009 at 5:22 am
Terence Tao
Hmm, this is a problem. I think this means that the argument as it stands eliminates all values of f(A) greater than 2, but additional arguments are needed for f(A)=1 and f(A)=2.
In principle one can deconstruct the Maple calculations to extract a proof of f(A)=0, but of course a more transparent, human-verifiable proof would be desirable.
25 July, 2009 at 3:18 pm
Terence Tao
I’ve patched the problem Michael pointed out, at the cost of making the argument rather ad hoc and complicated, and also needing some linear programming analysis of the 4D Pareto optimals, and also recompiled the paper. Thanks to Mike and Klas for fleshing out the other sections of the paper, though still a fair bit of polishing is needed. The latest version is at
http://terrytao.wordpress.com/files/2009/07/polymath1.pdf
26 July, 2009 at 12:43 pm
Kristal Cantwell
I have just added more to the colouring section of the paper. I also added a couple of items to the bibliography of the main paper since I had to cite them. I didn’t know about the problem to the c_6′ proof until after it had been solved. I am glad there was a way to get around the problem.
27 July, 2009 at 10:49 am
Kristal Cantwell
I think I can find lower bounds to a couple more coloring problems. They involve the cube when viewed as a torus. This allows more lines. I think these lines are sets of n points with fixed coordinates and if we are looking at a k-cube k types of moving coordinates they move up by one but can start at any of the k-values. Let us refer to these as n=T(k,r) is the smallest integer to force a monochromatic line. If we allow lines to move sown as well as up we have 2n types of lines and we can define n=D(k,r). By using arguments similar to the arguments relating colorings without combinatorial lines and coloring without geometric lines. I can get lower bounds of roughly 2^n/3 and 2^n/6 for these number if the number of colors is two. Two colors is important because it related to the drawing postions in two player games. These two toric variants are interesting because their hypergraph has a property that makes a variant of the two player game easy to analyze.
27 July, 2009 at 2:06 pm
Kristal Cantwell
With regard to my above post I am not able to prove this result.
27 July, 2009 at 6:57 pm
Michael Peake
Just a remark on the symmetry group in the Moser problem, mentioned in the introduction. The coordinates
naturally pair up into 
and so on. When 
, these pairs can be swapped around, which increases the symmetry group by a factor 
. Each pair can be flipped, which gives an extra factor 
. (The symmetry of flipping every pair is the same as flipping every coordinate dimension, so it is already included in 
.)
27 July, 2009 at 8:18 pm
Terence Tao
Huh, that’s somewhat strange symmetry (it doesn’t have a geometric interpretation, despite the fact that the lines are geometric), but I guess you’re right. So for instance, for k=4, one could swap all 1s with 4s in a Moser set while keeping 2s and 3s unchanged, or instead swap 1s with 2s and 3s with 4s, boosting the group of symmetries by an order of 4. Every little bit helps, I suppose…
5 November, 2009 at 11:31 pm
Kevin O'Bryant
This is slightly off-topic, but does anyone know of explicit computations of
, the maximum size of a subset of 
that does not have 
terms in AP?
I recall seeing
somewhere, but I can’t find it now.
6 November, 2009 at 4:52 pm
Terence Tao
That sounds somewhat large to me, given that the Fourier-analytic upper bounds are quite lossy, and the Behrend examples are also not very strong at this scale, and there are too many combinations for a brute force approach. Perhaps it was van der Waerden numbers instead?
7 November, 2009 at 5:09 pm
Kevin O'Bryant
The preprint I found was definitely concerning
, and it was reporting the outcome of a large parallel computation. The number 200 is from my memory, and could well have been “almost 200”.
While 200 is too small for the good stuff, some elementary arguments are still powerful. The original 1930s Erdos-Turan paper uses the bound
, for example, and the greedy algorithm to compute 
(by hand!).
8 November, 2009 at 1:23 am
Klas Markström
You might be thinking of this set of results.
http://www.st.ewi.tudelft.nl/sat/waerden.php
n=200 sounds much larger than anything I can recall having seen so if there really is such a result the methods behind it would be very interesting to see.
7 November, 2009 at 10:04 am
Kristal Cantwell
I can look for the van der Warden for 5 colors and length note it is greater than 170 from the table here:
http://en.wikipedia.org/wiki/Van_der_Waerden_number
Then divide by 5 and get a set of 34 points out of the 200 without an arithmetic progression of length 3 so the maximum must be 34 or more.
5 December, 2009 at 7:43 pm
Kevin O'Bryant
According to this site (http://www.math.uni.wroc.pl/~jwr/non-ave.htm), Rodolfo Niborski has proved that
. The witness is
1 2 5 7 11 16 18 19 24 26 38 39 42 44 48 53 55 56 61 63 112 127 128 133 135 136 140 146 148 149 151 155 172 173 178 179 181 187 188 192 194
with the optimality coming by exhaustive search.