Outline of second paper

From Polymath Wiki
Jump to: navigation, search

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.



(A draft proposal - please edit)

For any [math]n \geq 0[/math] and [math]k \geq 1[/math], the density Hales-Jewett number [math]c_{n,k}[/math] is defined as the size of the largest subset of the cube [math][k]^n := \{1,\ldots,k\}^n[/math] which contains no combinatorial line; similarly, the Moser number [math]c'_{n,k}[/math] is the largest subset of the cube [math][k]^n[/math] which contains no geometric line. A deep theorem of Furstenberg and Katznelson [cite] shows that [math]c_{n,k} = o(k^n)[/math] as [math]n \to \infty[/math] (which implies a similar claim for [math]c'_{n,k}[/math]; this is already non-trivial for [math]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]c_{n,k}[/math] and [math]c'_{n,k}[/math] for small [math]n,k[/math]. For instance the sequence [math]c_{n,3}[/math] for [math]n=0,\ldots,6[/math] is [math]1,2,6,18,52,150,450[/math], while the sequence [math]c'_{n,3}[/math] for [math]n=0,\ldots,6[/math] is [math]1,2,6,16,43,124,353[/math]. We also establish some results for higher [math]k[/math], showing for instance that an analogue of the LYM inequality (which relates to the [math]k=2[/math] case) does not hold for higher [math]k[/math].



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]c_{n,3}[/math]
  • Computation of several values of [math]c'_{n,3}[/math]
  • Asymptotic lower bounds for [math]c_{n,k}[/math]
  • Genetic algorithm lower bounds
  • Some bounds for [math]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
  • Kakeya problem for [math]Z_3^n[/math]

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]c_{n,k} \gt C k^{n - \alpha(k)\sqrt[\ell]{\log n}+\beta(k) \log \log n}[/math]

Discussion of genetic algorithm

Low-dimensional density Hales-Jewett numbers

Very small n

[math]n=0,1,2[/math] are trivial. But the six-point examples will get mentioned a lot.

For [math]n=3[/math], one needs to classify the 17-point and 18-point examples.


One needs to classify the 50-point, 51-point, and 52-point examples.


This is the big section, showing there are no 151-point examples.


Easy corollary of n=5 theory

Higher k DHJ numbers

Exact computations of [math]c_{2,k}, c_{3,k}[/math]

Connection between Moser[math](n,2k)[/math] and DHJ[math](n,k)[/math]


Failure of hyper-optimistic conjecture

Lower bounds for Moser

Using Gamma sets to get lower bounds

Adding extra points from degenerate triangles

Higher k; 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


The above are the master copies of the LaTeX files. Below are various compiled versions of the source: