This is the fourth “research” thread of the Polymath16 project to make progress on the Hadwiger–Nelson problem, continuing this post. This project is a follow-up to Aubrey de Grey’s breakthrough result that the chromatic number of the plane is at least 5. Discussion of the project of a non-research nature should continue in the Polymath proposal page. We will summarize progress on the Polymath wiki page.
What follows is a summary of some of the main directions of this project:
— Lower bounds from the probabilistic method —
Terry Tao suggested a new approach that might lead to a human proof of :
Suppose there exists a 4-coloring , and apply a “uniform random” Euclidean isometry to and permutation to to produce a random 4-coloring (this can be made rigorous since is amenable). Then for each , we can estimate probabilities of the form by considering all proper 4-colorings of . Different can then produce inconsistent probability estimates, resulting in the desired contradiction.
One may rephrase the existing proofs of in this probabilistic language (see the wiki). Each of these proofs finds a contradiction by demonstrating that a certain probability equals exactly 0. Doing so requires a large vertex set (e.g., de Grey’s or Exoo and Ismailescu’s ), thereby insisting on computer assistance. However, it suffices to show that the probability in question is small, meaning we might get away with a smaller (human-analyzable?) vertex set.
This line of inquiry has focused on estimating probabilities of the form . Of course, and . A spindling argument gives whenever . Jannis observed by computer assistance, contradicting this upper bound, and so in principle, it suffices to consider probabilities of this form. Many more bounds are derived in the wiki.
Question. Given , how efficiently can one identify all of the implied linear inequalities on , where ?
Question. What are “good” vertex sets to compute inequalities from?
By combining answers to these questions, we can build up a rich database of probability estimates that will hopefully lead to a contradiction from small vertex sets.
— Computational lower bounds —
As mentioned above, Jannis found that for every 4-coloring of , 8/3 necessarily receives the name color as 0. This implies by a spindling argument. We would like to replicate this approach to obtain new lower bounds.
Question. Consider all proper 5-colorings of Tamás’s in which the neighborhood of the origin avoids colors 1 and 2. Is there any vertex (other than the origin) that is colored either 1 or 2 in all such colorings?
If such a vertex exists (and the vertex’s distance from the origin has the property that is an irrational multiple of ), then the measurable chromatic number of the plane is at least 6. Presumably, this question can be answered using Jannis’s technique.
Philip asked a related question in the previous thread:
Question. Define , where
Does 5/3 receive the same color as 0 in every 5-coloring of ?
These two points are always monochromatic for homomorphic colorings, and if this behavior persists for general colorings, then a spindling argument implies .
— Homomorphic coloring —
Question. Is 5-chromatic?
I expect the answer to this question is “yes” by homomorphic coloring. The first step is to identify the ring generated by and its multiplicative inverses. This step will also help us to identify appropriate generators for Minkowski sums, enabling additional computational observations (à la Jannis).
Question. Does enjoy a homomorphic 5-coloring?
Presumably, the answer is “no.” To answer this question, one must first identify the ring , which in turn would identify appropriate generators to allow a computer-assisted proof of .