Outline of second paper
Here is a proposed outline of the second paper, which will focus on the new bounds on DHJ(3) and Moser numbers, and related quantities.
Metadata
- Author: D.H.J. Polymath
- Address: http://michaelnielsen.org/polymath1/index.php (Do we need a more stable address?)
- Email: ???
- Title: Density Hales-Jewett and Moser numbers in low dimensions.
- AMS Subject classification: ???
Abstract
(A draft proposal - please edit)
For any [math]\displaystyle{ n \geq 0 }[/math] and [math]\displaystyle{ k \geq 1 }[/math], the density Hales-Jewett number [math]\displaystyle{ c_{n,k} }[/math] is defined as the size of the largest subset of the cube [math]\displaystyle{ [k]^n := \{1,\ldots,k\}^n }[/math] which contains no combinatorial line; similarly, the Moser number [math]\displaystyle{ c'_{n,k} }[/math] is the largest subset of the cube [math]\displaystyle{ [k]^n }[/math] which contains no geometric line. A deep theorem of Furstenberg and Katznelson [cite] shows that [math]\displaystyle{ c_{n,k} = o(k^n) }[/math] as [math]\displaystyle{ n \to \infty }[/math] (which implies a similar claim for [math]\displaystyle{ c'_{n,k} }[/math]; this is already non-trivial for [math]\displaystyle{ k=3 }[/math]. Several new proofs of this result have also been recently established [cite Polymath], [cite Austin].
Using both human and computer-assisted arguments, we compute several values of [math]\displaystyle{ c_{n,k} }[/math] and [math]\displaystyle{ c'_{n,k} }[/math] for small [math]\displaystyle{ n,k }[/math]. For instance the sequence [math]\displaystyle{ c_{n,3} }[/math] for [math]\displaystyle{ n=0,\ldots,6 }[/math] is [math]\displaystyle{ 1,2,6,18,52,150,450 }[/math], while the sequence [math]\displaystyle{ c'_{n,3} }[/math] for [math]\displaystyle{ n=0,\ldots,5 }[/math] is [math]\displaystyle{ 1,2,6,16,43,124 }[/math]. We also establish some results for higher [math]\displaystyle{ k }[/math], showing for instance that an analogue of the LYM inequality (which relates to the [math]\displaystyle{ k=2 }[/math] case) does not hold for higher [math]\displaystyle{ k }[/math].
Sections
Introduction
Basic definitions. Definitions and notational conventions include
- [k] = {1, 2, ..., k}
- Subsets of [k]^n are called A
- definition of combinatorial line, geometric line
- Hales-Jewett numbers, Moser numbers
History of and motivation for the problem:
- Sperner's theorem
- Density Hales-Jewett theorem, including new proofs
- Review literature on Moser problem
New results
- Computation of several values of [math]\displaystyle{ c_{n,3} }[/math]
- Computation of several values of [math]\displaystyle{ c'_{n,3} }[/math]
- Asymptotic lower bounds for [math]\displaystyle{ c_{n,3} }[/math]
- Genetic algorithm lower bounds
- Some bounds for [math]\displaystyle{ c_{n,k} }[/math] for low n and large k
- Connection between Moser(2k) and DHJ(k)
- Hyper-optimistic conjecture, and its failure
- New bounds for colouring Hales-Jewett numbers
Lower bounds for density Hales-Jewett
Fujimura implies DHJ lower bounds; some selected numerics (e.g. lower bounds up to 10 dimensions, plus a few dimensions afterwards).
The precise asymptotic bound of [math]\displaystyle{ c_n \gt C 3^{n - 4\sqrt{\log 2}\sqrt{\log n}+\frac 12 \log \log n} }[/math]
Discussion of genetic algorithm
Low-dimensional density Hales-Jewett numbers
Very small n
[math]\displaystyle{ n=0,1,2 }[/math] are trivial.
For [math]\displaystyle{ n=3 }[/math], one needs to classify the 17-point and 18-point examples.
n=4
One needs to classify the 52-point, 53-point, and 54-point examples.
n=5
This is the big section, showing there are no 151-point examples.
n=6
Easy corollary of n=5 theory
Higher k DHJ numbers
Exact computations of [math]\displaystyle{ c_{2,k}, c_{3,k} }[/math]
Numerics
Failure of hyper-optimistic conjecture
Lower bounds for Moser
Using sphere packing to get lower bounds
Implications between Moser and DHJ
Moser in low dimensions
There is some general slicing lemma that needs to be proved here that allows inequalities for low-dim Moser to imply inequalities for higher dim.
For n=0,1,2 the theory is trivial.
For n=3 we need the classification of Pareto optimal configurations etc. So far this is only done by computer brute force search; we may have to find a human version.
n=4 theory: include both computer results and human results
n=5: we have a proof using the n=4 computer data; we should keep looking for a purely human proof.
n=6: we can give the partial results we have.
Fujimura's problem
Coloring DHJ
Files
The above are the master copies of the LaTeX files. Below are various compiled versions of the source:
