Now that the quarter is nearing an end, I’m returning to the half of the polymath1 project hosted here, which focussed on computing density Hales-Jewett numbers and related quantities. The purpose of this thread is to try to organise the task of actually writing up the results that we already have; as this is a metathread, I don’t think we need to number the comments as in the research threads.
To start the ball rolling, I have put up a proposed outline of the paper on the wiki. At present, everything in there is negotiable: title, abstract, introduction, and choice and ordering of sections. I suppose we could start by trying to get some consensus as to what should or should not go into this paper, how to organise it, what notational conventions to use, whether the paper is too big or too small, and so forth. Once there is some reasonable consensus, I will try creating some TeX files for the individual sections (much as is already being done with the first polymath1 paper) and get different contributors working on different sections (presumably we will be able to coordinate all this through this thread). This, like everything else in the polymath1 project, will be an experiment, with the rules made up as we go along; presumably once we get started it will become clearer what kind of collaborative writing frameworks work well, and which ones do not.
What's new 
110 comments
Comments feed for this article
13 June, 2009 at 10:38 am
Terence Tao
Hmm. The only way that a 6D set can have statistic (24,72,180,80,0,0,0) is if every 1***** slice has statistics (6,12,18,4,0) (which is an extremal for 4D), and similarly for permutations. If we can classify the (6,12,18,4,0) sets in [3]^4 we may be able to kill off the 356 case. The scanning program can in principle do this but perhaps an integer program would be the most direct way to go here?
13 June, 2009 at 10:46 am
Terence Tao
Ack, there is a problem with the brute force search :-(… (6,12,18,4,0) is reported as feasible, but it is not compatible with the 3D inequalities. Time to debug…
13 June, 2009 at 12:39 pm
Terence Tao
False alarm! (6,12,18,4,0) is indeed feasible (an explicit example has slices 261660105, 356516660,432356261 in octal; it seems that there are not many other solutions than this one and its symmetric permutations, though I was not able to establish this rigorously). My application of the 3D inequalities in the preceding comment was incorrect. So, barring any further bugs, we’re still in a good position, in that we have a proof of
and a fairly precise description of when 
can occur; if we can pin down the (6,12,18,4,0) Moser sets precisely, we might be able to finish off 356 completely.
13 June, 2009 at 4:57 pm
Kristal Cantwell
If the slice is 4D from a 6D set shouldn’t the number of fixed coordinates be two instead of one. I am assuming that what happens here is that is that if we fix any two coordinates of the (24,72,180,80,0,0,0) and set each of them equal to 1 or 3 the resulting slice will have statistics (6,12,18,4,0).
13 June, 2009 at 8:11 pm
Terence Tao
Yes, you’re right, I meant the 11**** slices (and symmetries thereof).
Actually I have a short proof of
. Define the score of a 4D set to be 4a+6b+10c+20d+60e. Double counting shows that (if f=g=0, which we may assume) the size of a 6D set is the average of the scores of its 4D side slices (such as 11****). But thanks to the 4D extremals, the largest score is 356, attained at exactly one place, namely (6,12,18,4,0), see https://spreadsheets.google.com/ccc?key=rD2Oc_wyheVOcmCyd-Drdgw&hl=en . This also shows that the only way 356 is attainable is if all 11**** slices have statistics (6,12,18,4,0) as mentioned earlier, and if the entire set has statistics (24,72,180,80,0,0,0).
With a bit more effort I can get
. Consider the 112*** slices (and symmetries thereof). Double counting shows that these slices must have statistics (3,9,3,0) on the average. But all 3D slices must obey the inequalities 
and 
(see https://spreadsheets.google.com/ccc?key=p5T0SktZY9DuKZ2DyzO9EOg&hl=en ), and so all 112*** slices must obey these inequalities with equality; also, d must be zero. We conclude that the 112*** slices have statistics (3,9,3,0), (2,6,6,0), or (4,12,0,0). The latter two possibilities are inconsistent with the 11**** slices having statistics (6,12,18,4,0) (since all but at most two of the “d” points in the 11**** slice lie in 112***). So all 112*** slices have statistics (3,9,3,0). Since 11**** has statistics (6,12,18,4,0), this implies that exactly one of 111222 and 113222 lie in the set. More generally, we see that given any two adjacent “d” points in ![[3]^6](https://s0.wp.com/latex.php?latex=%5B3%5D%5E6&bg=ffffff&fg=545454&s=0&c=20201002)
, exactly one of them lies in the set; thus the d points 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, but omits 113222, 333222 and permutations. Meanwhile, we see that the (24,72,180,80,0,0,0) set saturates the inequality
, 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. But this is too many c points (225 points, whereas we are only supposed to have 180), a contradiction.
There may be a chance to push these arguments further; the fact that (6,18,24,4,0) is the only extremiser for the score (by quite a margin) is quite encouraging.
14 June, 2009 at 12:43 am
Michael Peake
I can see why, in xxx222, either every d point has an odd number of 1s, or an even number of 1s. But xx2x22 may also have an odd number of 1s, or an even number of 1s. Could a choice of ‘odd’ and ‘even’ for the twenty classes of d points be made so that fewer c points are needed?
14 June, 2009 at 1:02 am
Terence Tao
Hmm, true, but the argument can be easily fixed. For xxx222, the argument in my previous comment shows that the set has at least 15 “c” points of the form xxxx22 (regardless of whether the xxx222 points come from odds or evens). Permuting this fact, we still get 225 “c” points in all.
I played a little bit with the score 4a+6b+10c+20d+60e. As I said before, the maximal score is 356, attained at (6,18,24,0,0). The next highest score among all feasible statistics is 352, attained in three ways, by (6,8,12,8,0), (5,12,12,4,1), and (5,18,24,0,0). Since there must be a way to slice into 11xxxx, 13xxxx, 31xxxx, 33xxxx (or a permutation thereof) such that the average score is greater than or equal to the cardinality, we see that for a 355 set, one way of slicing must consist of three (6,18,24,0,0) slices plus one of the three other slices mentioned above (in particular, this shows that a=24 or a=23). To proceed further it seems of interest to classify the (6,18,24,0,0) slices properly. It would also be interesting to see what the slices of Kareem’s example are.
14 June, 2009 at 1:22 am
DHJ: Still writing the second paper « What’s new
[…] June, 2009 in math.CO | Tags: polymath1 | by Terence Tao This is a continuation of the previous thread here in the polymath1 project, which is now full. Ostensibly, the purpose of this thread is to […]
14 June, 2009 at 1:24 am
Terence Tao
It’s a little awkward to move the thread while it is still so active, but I have decided to stick with tradition and move on to the next thread, at
9 July, 2009 at 8:28 am
DHJ: Writing the second paper III. « What’s new
[…] July, 2009 in math.CO | Tags: polymath1 | by Terence Tao This is a continuation of the preceding two threads here on the polymath1 project, which are now full. We are closing on on the […]