After a hiatus of several months, I’ve made an effort to advance the writing of the second Polymath1 paper, entitled “Density Hales-Jewett and Moser numbers“. This is in part due to a request from the Szemeredi 60th 70th birthday conference proceedings (which solicited the paper) to move the submission date up from April to February. (Also, the recent launch of Polymath5 on Tim Gowers blog reminds me that I should get this older project out of the way.)
The current draft of the paper is here, with source files here. I have been trimming the paper, in particular replacing some of the auxiliary or incomplete material in the paper with references to pages on the polymath wiki instead. Nevertheless this is still a large paper, at 51 pages. It is now focused primarily on the computation of the Density Hales-Jewett numbers 
There are a number of minor issues remaining with the paper:
- A picture of a Fujimura set for the introduction would be nice.
- In the proof of Theorem 1.3 (asymptotic lower bound for DHJ numbers), it is asserted without proof that the circulant matrix with first row 1,2,…,k-1 is nonsingular. One can prove this claim by computing the Fourier coefficients
for all t, but is there a slicker way to see this (e.g. by citing a reference?).
- Reference [15] (which is Komlos’s lower bound on the Moser numbers) is missing a volume number. The reference is currently given as
J. Komlos, solution to problem P.170 by Leo Moser, Canad. Math.. Bull. vol ??? (1972), 312-313, 1970.
Finally, the text probably needs to be proofread one or two more times before it is ready to go, hopefully by early February. There is still also one last opportunity to propose non-trivial restructuring of the paper (in particular, if there are other ways to trim the size of the paper, this may be worth looking into).
What's new 
38 comments
Comments feed for this article
16 January, 2010 at 12:23 am
Qiaochu Yuan
2. The algebra of circulant matrices of order
is isomorphic to ![\mathbb{C}[x]/(x^n - 1)](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BC%7D%5Bx%5D%2F%28x%5En+-+1%29&bg=ffffff&fg=545454&s=0&c=20201002)
, where 
is the cyclic permutation matrix of order 
. In this algebra, it’s clear that 
, so the circulant matrix you’re looking at is invertible.
16 January, 2010 at 12:55 am
Kevin Costello
Another way of approaching (2) is to look at the vectors
, where 
denotes the 
row of 
and 
equals 
.
Each such vector is of the form
, so a hypothetical vector in the nullspace would have to have all of its entries equal, which can immediately be rejected by considering the first row.
18 January, 2010 at 8:49 pm
obryant
With a proof this sweet, it would be wrong to omit it.
There’s a nice formula for the determinant of the circulant here:
http://mathworld.wolfram.com/CirculantDeterminant.html
16 January, 2010 at 3:32 am
Jitse Niesen
Theorem 3 of Daryl Geller, Irwin Kra, Sorin Popescu and Santiago Simanca, “On circulant matrices”, http://www.math.sunysb.edu/~sorin/eprints/circulant.pdf, states that a circulant matrix whose first row is an increasing sequence of nonnegative numbers, is nonsingular.
16 January, 2010 at 9:21 am
jozsef
” This is in part due to a request from the Szemeredi 60th birthday conference proceedings ”
I agree that Endre looks younger than 60, however this conference will celebrate his 70th birthday :)
[Oops! Corrected, thanks. I hope Endre won’t be offended – T.]
16 January, 2010 at 11:50 am
Density Hales-Jewett and Moser numbers « Euclidean Ramsey Theory
[…] Density Hales-Jewett and Moser numbers By kristalcantwell The deadline for this paper has changed. The deadline has been moved from February to April. See the following post. […]
16 January, 2010 at 12:21 pm
Kristal Cantwell
I looked at the Canadian Mathematic bulletin site here:
http://www.cms.math.ca/cmb/
It said that the volume number of 1972 is 15.
16 January, 2010 at 12:53 pm
Mathematics, Science, and Blogs « Combinatorics and more
[…] (October 09 ) The paper with the DHJ proof is now uploaded. (January 2010) A draft of a second paper devoted to the study of DHJ and Moser numbers can be found here. […]
17 January, 2010 at 12:52 am
Matemáticos colaboram num projecto aberto de investigação conjunta através do blogue do Professor Timothy Gowers « problemas | teoremas
[…] and Moser numbers”, em versão pdf é este. A este respeito, o Professor Terence Tao escreveu no seu […]
17 January, 2010 at 2:13 pm
Kristal Cantwell
I have been going through the paper and at page 20 it gives the following url: http://abel.math.umu.se/klasm/Data/HJ/ as a reference. I have tried this address and it gave me a 404 page. So there may be problems with this url.
18 January, 2010 at 12:59 am
Klas Markström
Kristal, as you have written it there is a missing tilde, or ~, before klasm in the address. If you add that it works.
18 January, 2010 at 7:04 pm
Kristal Cantwell
I looked at it again and I think what happen is that the missing symbol is in the paper but it is missing in the font and so I am getting a space. So at least my software is missing a font and leaving it out.
18 January, 2010 at 9:00 pm
obryant
Theorem 1.3 is not mentioned in the abstract.
18 January, 2010 at 9:02 pm
obryant
The comment in Theorem 1.4 stating that the sequence is now in the OEIS should be before the theorem.
BTW, the “corrections” I’m posting are just my opinion, so please accept or ignore them as you find appropriate.
18 January, 2010 at 9:06 pm
obryant
page 5: change “it gives a lower bound of $c’_{6,3}=344$” to “it gives a lower bound of $c’_{6,3} \geq 344$”
18 January, 2010 at 9:09 pm
obryant
Footnote on page 5: change “no all equilateral” to “no equilateral”
18 January, 2010 at 9:12 pm
obryant
If somebody emails me a good Fujimura set, I can make the picture (I made the other pics in the introduction, so the style would be the same).
19 January, 2010 at 11:39 am
Kristal Cantwell
I think the following article in the polymath wiki has some examples of Fujimura sets http://michaelnielsen.org/polymath1/index.php?title=Fujimura%27s_problem possibly one of them might work.
18 January, 2010 at 9:57 pm
obryant
On page 10, in the proof of Theorem 1.3, in the last line of text, we have “applying (2.1)”, but it is actually using something more general than (2.1). Can fix by changing (2.1), or by changing the reference to “applying the obvious generalization of (2.1) to arbitrary $k$”.
Also in this proof, change “simplices $\Delta_{n,k}$” to “simplices in $\Delta_{n,k}$”.
Also in this proof, we use the notation $n/k + \vec{s}$ to mean the vector, all of whose components are Floor[n/k], plus the vector s. (notation used again two lines later.) Is this standard usage? I recommend changing the period at the end of the definition of B to a comma, and then continuing, “where \vec{c} is the $k-1$ dimensional vector, all of whose entries are $\lfloor n/k \rfloor$.” Two lines later, change “c” to “M\vec{c}$.
18 January, 2010 at 9:59 pm
obryant
Is the proof of Theorem 1.3 the only place we use “\vec” to denote elements of
?
19 January, 2010 at 6:45 pm
Terence Tao
Thanks for all the corrections! I’ve uploaded a revised version at
Click to access polymath1.pdf
The only outstanding issue now that I know of is the image of the Fujimura set (though of course more proofreading is very welcome).
20 January, 2010 at 10:44 am
Kristal Cantwell
I now see the tilde in the web address. I was looking at volume numbers in the bibliography and they don’t seem to be standardized. Some are boldfaced some are not, some are proceeded by the word volume or vol. So possibly one way could be chosen to write all the volume numbers.
21 January, 2010 at 12:56 am
obryant
The new abstract has “We also some”, which should perhaps be “we also prove some”.
The last equation of the abstract should be $2k>2^\ell$.
23 January, 2010 at 12:00 am
Terence Tao
A new version of the paper, incorporating all the latest changes and also some nice new figures by Kevin:
Click to access polymath2.pdf
It’s looking close to ready now…
23 January, 2010 at 8:34 am
Terence Tao
Oops, I forgot to make the bibliography consistent as Kristal suggested. Here is a version with a better biblio:
Click to access polymath3.pdf
23 January, 2010 at 9:07 am
Christian
Here are some further suggestions on references/bibliography:
1) On preprints/arxiv preprints:
consistently with arxiv number/link or consistently not.
[23] has the number, most others not.
2) On books: with place of publication. (This is an old tradition).
3) Abbreviation of Journals consistently, according to MathScinet
e.g. Canad. Math. Bull. is abbreviated several entries are not abbreviated.
some detailed comments below.
[2] arxiv, see above
[3] place of publication: Cambridge
[7] Bull. not Bull,
[13] tilde ~ before sorin missing (same latex problem as before)
[14] arxiv see above
[20] arxiv see above
[25] add hyphen between pages, I think, 332-344,
[27] add place of publication: Heidelberg
[28] year in brackets
25 January, 2010 at 7:48 pm
Terence Tao
I’ve made the changes to the bibliography at
Click to access polymath4.pdf
To ensure that this process terminates, I’ll arbitrarily set Feb 1 as the self-imposed deadline for submission, and then submit to the Szemeredi conference proceedings and to the arXiv.
28 January, 2010 at 10:14 am
Christian
Suggestion for section 4:
After a major part of the section was written, the results had been improved and put in front of the remainder of the section. The remaining part was kept since those constructions still give some insight.
In any case the following sentences could be adjusted:
1) formula 4.2 closer to the beginning of the section.
2) page 22, 2nd paragraph, 2nd sentence (In this section…) is
obsolete now.
3) page 23, last paragraph, comment that this construction gives the
best value C is not true any longer.
I am now looking forward to the Szemeredi Festsschrift!
Many thanks to Terry for his great supervision of the project, and to all others who contributed!
28 January, 2010 at 2:47 pm
misha
LYM (e.g. on page 6) and LMY (e.g. on page 5) are used interchangeably.
m
28 January, 2010 at 6:30 pm
Terence Tao
A new version of the draft:
Click to access polymath5.pdf
It includes a second picture of a Fujimura set by Jason Dyer, and incorporates the preceding corrections.
28 January, 2010 at 6:41 pm
Anonymous
I think the following (on the bottom of page 9) is missing a punctuation mark:
… to the following Fujimura set construction It is convenient to write …
28 January, 2010 at 7:04 pm
misha
Sorry, the abstract is referring to LYM inequality, the body to LMY.
m
31 January, 2010 at 9:30 am
Terence Tao
One of the participants pointed out to me by email that there is one last reference question which it may be good to resolve before submitting, namely to track down the reference of Fujimura in which he introduces (essentially) the concept of what we call a Fujimura set. Right now all we have is a web URL,
http://www.puzzles.com/PuzzlePlayground/CoinsAndTriangles/CoinsAndTriangles.htm
but apparently in one of Martin Gardner’s columns “Eccentric Chess and Other Problems”, from 1979, he attributes the puzzle to a “recent book” of Fujimura. The one germane publication we know of of Fujimura is “the Tokyo puzzles”, but this puzzle does not appear to be in that book. We’ve had good luck with using the polymath community to settle other reference questions of this sort, so I’m tossing this out here in the hope that it works again…
31 January, 2010 at 10:38 am
Jason Dyer
Just as a quick clarification, the article is in the book Mathematical Circus, so the original Scientific American article might be back a year or two.
The Tokyo Puzzles was from 1978 so it’s the most likely candidate, but it doesn’t seem to be in there. It is possible I am simply blind, but I checked through quite a few times. I’m guessing (since Gardiner was editor of The Tokyo Puzzles) he learned of the new puzzle simply through side personal correspondence, meaning likely the original book is only available in Japanese.
If someone has contact information for Martin Gardiner himself, he might be able to resolve this.
31 January, 2010 at 12:09 pm
Klas Markström
The weekand has given me time to do a bit of proof reading too.
On page 2 we have the sentence: “The proof of [2] also used ergodic theory, but the proof in [23] was combinatorial and gave e ffective bounds for cn;k in the limit n -> 1.” Should this sentence be in past tense? It sound a bit strange to me, but english is not my first language.
Page 9. “An integer program2 was run…” Strictly speaking one doesn’t run an integer program, after all it is a set of linear inequalities and an objective function. Maybe “An integer program was solved” instead?
Page 9. The same paragraph which contains the previous sentence ends with a “:” and the next paragraph is just a single line which should probably be merged into the same paragraph.
Section 3. It could possibly be helpful to divide this section into subsections for difference values of n.
Page 19. Again “An integer program was run”
Page 19. Same paragraph. Here the reference to the list of optimizers is done as an URL but on page 9 this was done as ref [17]. I think it is better to be consistent and use [17].
Reference 17 I wouldn’t mind getting some umlauts to have an ö instead on an o in my name :) They are even separate letters in the Swedish alphabet.
1 February, 2010 at 6:34 am
Michael
Klas, in that reference, you list values up to n=20, but your link to the actual Fujimura sets only goes up to 10. Do you still have the Fujimura sets up to 20?
1 February, 2010 at 6:53 am
Klas Markström
Michael,
The files with Fujimura sets which I have posted are only for values of n for which I have all such sets. I can put some partial files with example sets for larger n there as well, but i might have to generate some of them anew.
3 February, 2010 at 7:08 am
Michael
I think it would be good to have an example of each n, if it is easy to regenerate.