Polymath16, fourth thread: Applying the probabilistic method

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 $\mathrm{CNP}\geq 5$:

Suppose there exists a 4-coloring $c\colon \mathbb{R}^2\rightarrow\{1,2,3,4\}$, and apply a “uniform random” Euclidean isometry to $\mathbb{R}^2$ and permutation to $\{1,2,3,4\}$ to produce a random 4-coloring $\mathbf{c}$ (this can be made rigorous since $S_4\times E(2)$ is amenable). Then for each $X\subseteq\mathbb{R}^2$, we can estimate probabilities of the form $\mathbf{P}(\{\mathbf{c}(x)\}_{x\in X}\in S)$ by considering all proper 4-colorings of $X$. Different $X$ can then produce inconsistent probability estimates, resulting in the desired contradiction.

One may rephrase the existing proofs of $\mathrm{CNP}\geq 5$ 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 $M$ or Exoo and Ismailescu’s $G_{627}$), 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 $p_d:=\mathbf{P}(\mathbf{c}(0)=\mathbf{c}(d))$. Of course, $p_0=1$ and $p_1=0$. A spindling argument gives $p_d\leq1/2$ whenever $d\geq 1/2$. Jannis observed $p_{8/3}=1$ 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 $X\subseteq\mathbb{R}^2$, how efficiently can one identify all of the implied linear inequalities on $\{p_d\}_{d\in\Delta(X)}$, where $\Delta(X)=\{\|x-y\|:x,y\in X\}$?

Question. What are “good” vertex sets $X\subseteq\mathbb{R}^2$ 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 $V\oplus V\oplus H$, 8/3 necessarily receives the name color as 0. This implies $\mathrm{CNP}\geq 5$ 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 $V_A\oplus V_A\oplus V_A$ 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 $r$ from the origin has the property that $\arcsin(\frac{1}{2r})$ is an irrational multiple of $\pi$), then the measurable chromatic number of the plane is at least 6. Presumably, this question can be answered using Jannis’s technique.

Question. Define $Z=\{\omega^a\eta^b\zeta^c:a\in\{0,\ldots,5\},b,c\in\{-2,\ldots,2\}\}$, where

$\omega=\frac{1+i\sqrt{3}}{2},\quad\eta=\frac{\sqrt{33}+i\sqrt{3}}{6},\quad\zeta=\frac{-1+i\sqrt{15}}{4}.$

Does 5/3 receive the same color as 0 in every 5-coloring of $Z\oplus Z\oplus Z$?

These two points are always monochromatic for homomorphic colorings, and if this behavior persists for general colorings, then a spindling argument implies $\mathrm{CNP}\geq6$.

— Homomorphic coloring —

Taking inspiration from de Grey’s $M$, we consider rings of the form $R_k:=\mathbb{Z}[\omega_{t_1},\ldots,\omega_{t_k}]$, where $\omega_t=\exp(i\cdot\arccos(1-\frac{1}{2t}))$ and $\{t_j\}_{j=1}^\infty$ is the sequence of positive Loeschian numbers.

So far, this pursuit has been fruitful: $R_0:=\mathbb{Z}$ is 2-chromatic, $R_1$ is 3-chromatic, and $R_2$ is 4-chromatic (see this). Furthermore, we have a few finite subsets of $R_3$ that are 5-chromatic (see this and that).

Question. Is $R_3$ 5-chromatic?

I expect the answer to this question is “yes” by homomorphic coloring. The first step is to identify the ring $\overline{R}_3$ generated by $R_3 \cap \mathbb{T}$ 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 $R_4$ enjoy a homomorphic 5-coloring?

Presumably, the answer is “no.” To answer this question, one must first identify the ring $\overline{R}_4$, which in turn would identify appropriate generators to allow a computer-assisted proof of $\mathrm{CNP}\geq6$.

122 thoughts on “Polymath16, fourth thread: Applying the probabilistic method”

1. I was looking at ways to squeeze more out of the graphs H and J from Aubrey’s paper. From Figure 1 of that paper we have four essentially different colorings of H, call them top-left, top-right, bottom-left, bottom-right. Aubrey proceeds by first assuming no monochromatic triangles, which excludes top-left and top-right, leading to a manageable number of possible colorings of H, which in turn leads to a reasonable number of colorings of J, enough so that the colors of the six vertices at distance 2 from the central vertex are highly constrained (e.g. at least two of them have to be the same color as the central vertex). This then leads to a contradiction after spindling J (using a variant of the spindle that creates six linking edges rather than just one), and now we can work with the assumption that there is a monochromatic triangle somewhere.

I was wondering if we could proceed instead by excluding top-left and bottom-right from Figure 1, so that we assume that H can only be colored using top-right and bottom-left colorings. This leads to more colorings of J than before I think, however there is a chance that there is still some significant constraining going on. For instance, in this scenario we have the identity $p_2 + p_{\sqrt{3}} = 2/3$ rather than just the inequality $p_2 + p_{\sqrt{3}} \geq 2/3$, because the pairs $(a,b)$ that arise in the proof of Lemma 15 can only be (4,0) or (2,1).

The point of doing this is that instead of concluding that a monochromatic triangle exists, we can either assume that two monochromatic triangles exist in a single H (top-left coloring), or three monochromatic 2-edges exist in a single H (bottom right coloring). Perhaps each of these two patterns can be excluded with a simpler graph than $M$ or $V \oplus V \oplus H$, bringing us perhaps closer to human-verifiability. In other words, the strategy here is to perform a tradeoff, making the “J” step a bit more difficult in the hope that it makes the “M” step easier.

1. Nice, I had missed this argument! In probabilistic language, Hubai’s argument shows that the probability that H is colored either 1tri or axisym is at least 1/10; see Lemma 19 of wiki. Hopefully we can get some more inequalities concerning the probabilities of 1tri, 2tri, centralsym, and axisym.

2. I managed to modify Tamas’s approach in a somewhat complicated fashion to show that in fact the 1tri coloring of H must occur with positive probability; this is Theorem 20 on the wiki. Basically, if 1tri is excluded, so that one only has 2tri, axisym, and centralsym colorings, then the possible colorings of the triangular lattice become quite rigid. It’s convenient to work with the hexagonal lattice dual to the triangular lattice, coloring a dual edge black if the original edge was monochromatic. Then 2tri hexagons correspond to dual hexagons that are all black, axisym hexagons correspond to dual hexagons with two opposing black edges, and centralsym hexagons correspond to dual hexagons with no black edges. It turns out that there are very few ways to piece these dual hexagons together in a compatible fashion – either everything is black (2tri throughout), or nothing is black (centralsym throughout), or there is a triangular lattice of 2tri hexagons connected by chains of axisym hexagons (with everything else centralsym), or there are “stripes” of axisym and centralsym hexagons more or less exactly as in Figure 3 of Aubrey’s paper. In almost all of these scenarios one can run the linking edges argument of Aubrey’s paper (but with the distance 2 replaced by a much larger distance P, basically a factorial of a large natural number) to eventually show that d_P is at least (say) 0.8, contradicting the spindling upper bound of 0.5.

Basically, it seems that 1tri is the hexagon coloring that causes chaotic colorings of the triangular lattice; forbid it, and the colorings “freeze” into a quite rigid and restrictive number of possibilities.

3. I think that instead of the dual edge, you mean that an edge is black if its elongation connects two vertices of the same color, right?

4. Yes, that’s what I meant, sorry.

It now occurs to me that rather than edge-coloring the dual graph, one should just edge color the original graph, with an edge being colored black if it is the short diagonal of a rhombus with monochromatic long diagonal, and white otherwise. Then H2tri vertices have six black edges, centralsym vertices have six white edges, axisym vertices have two black edges opposite each other and four white edges, and H1tri vertices have two white edges at 120 degree angles and 4 black edges. Without H1tri the edge coloring “crystallizes” either into a triangular lattice of black edges, a bunch of black and white “stripes”, or some degenerate cases such as all-black, all-white, or six black rays meeting at a single vertex. Even with H1tri there seems to be some vestige of rigidity, for instance the black edges always form convex polygonal faces. Will keep looking at it.

5. It seems that 4-colorings of the hexagonal lattice are essentially equivalent (up to color relabeling) of tilings of the lattice into convex polygons (thus: equilateral triangles, parallelograms, trapezoids, pentagrams, or hexagons) in which every vertex either has degree 6 [2tri case] or degree 4 [1tri case] (and in the latter case, the two non-edges are at 120-degree angles). The axisym and centralsym hexagons then correspond to edges and interior points of the polygons. It seems every such tiling leads to a consistent coloring rule for the lattice, unique up to relabeling of the colors. To get enough rigidity to make a contradiction one has to forbid degree 4 vertices (i.e., forbid 1tri hexagons), as there seem to be plenty of tilings even if all one has are the degree 4 vertices.

2. I also looked a bit at the measurable coloring problem and the Jordan region coloring problem. Let’s suppose for simplicity that we are using a coloring where the color regions are polygonal. At an edge, one could think of a vertex as being colored with both colors of the polygonal faces, since one could (heuristically at least) “jiggle” that vertex to either side without changing the colors of any other vertex of some given finite unit distance graph (though things get more complicated if many of these vertices lie on edges, making it hard to jiggle the graph). Similarly, at a meeting of three polygonal faces one could imagine that vertex as being colored with all three colors of the adjoining faces.

Falconer’s argument for $CNP \geq 5$ in the measurable case basically proceeds by noting that one can without loss of generality fix one point, say the origin, to be an “edge” vertex in that it takes two colors, and then by rotating, any finite or even countable number of other points of interest are interior points that take only one color. In particular, if one considers a Moser spindle with the common vertex at the origin, then the two far vertices of the spindle must take on the two colors of the origin, with the two vertices being colored with different colors. Rotating the spindle and using the fact that the angle of the spindle is an irrational multiple of pi, we can eventually get a contradiction with measurability.

I haven’t looked at the proof of $CNP \geq 6$ in the Jordan case, but I would guess it is something like trying to position a unit equilateral triangle so that one vertex has three colors and another one has two colors.

The Falconer argument is not as compatible with the probabilistic approach as I had first hoped, because of the special role played by the origin. One can still consider a random coloring formed by rotating and reflecting around the origin, but one loses the freedom to translate the coloring around. So for instance a probability like ${\bf P}( {\bf c}(z)={\bf c}(w) )$ depends not only on the length $|z-w|$ as before, but also on the distances $|z|, |w|$ to the origin. But perhaps the non-probabilistic approaches are going to be more effective. For instance, the only 4-coloring of H in which the central vertex has two colors will necessarily have two monochromatic $\sqrt{3}$-triangles, so Aubrey’s proof can jump straight to M and forget about J in this case (of course Falconer’s proof is still simpler in this particular case).

1. As for the Jordan case, Coulson made a relatively short paper using, naively expressed, circles, hexagons and by extension triangles and acute angles to find a contradiction resulting in the 6.

I think using an exclusion zone and it’s properties can help improve these bounds to 7, given certain assumptions for which I have a lot of empirical evidence, but no super solid proof yet.
If we use a generalized exclusion zone such as…
$\mathbb{X}_{G_n}(v) = \bigcup\limits^{}_{(a_1, \ldots ,a_n) \in v}\{ (x_1, \ldots ,x_n) \in \mathbb{R}^n \mid (x_1 - a_1)^2 + \cdots (x_n - a_n)^2 = 1 \}$

…we can create a dual graph of a tesselation by turning every manifold into a node, and every 2 manifolds/nodes that touch each other with their exclusion zones are connected by an edge. Doing this I’m certain the bounds for $\mathbb{R}^2$ will be 8 for triangles/squares, 8 (maybe 7) for pentagons and 7 for hexagons. Higher edge counts per polygon likely result in a rise of colors again.

Assuming that the maximum diameter (1 with intersecting vertice deletion) is the most efficient, and constructing a dual graph with the exclusion zone we find a 8-complete subgraph for triangles, a critical subgraph with chromatic color 8 for squares and a 7-complete subgraph for hexagons.
Triangles and Squares are unscalable in these constructions, similar to the truncated octahedron in $\mathbb{R}^3$.

As for pentagons, my assumption is that any irregularity for tesselations will be bad by definition for coloring, so that alone would rule it out. Having taken a look at possible pentagonal tilings, like [cmm (2*22)] I always end up finding at least 8-complete subgraphs.

I’ve attempted to generalize the relations emerging from this using the euler characteristic and the Brianchon-Euler-Gram theorem, but suffice to say I’ve failed so far. If however such a method could be established with solid proof, generalizing it into higher dimensions should be pretty easy.

Ideally the result would be a generalized function that takes in vertice count and dimensionality and throws out the most efficient possible coloring achievable with the given circumstances. Plotting this function would point towards the best tesselation with a clear dip.

1. ag24ag24 says:

@Bernhard – you mean Woodall, no? – the only major contribution from Coulson that I know was finding the upper bound of 15 on the CN of R^3 (by a method very similar to Radoicic and Toth’s permutohedron approach). If you did indeed mean Coulson, could you please give the reference?

As for your approach, I believe the main thing that needs to be taken into account is the possibility of regions that have diameter 1 in all the directions between a vertex and (part or all of) an opposite edge, rather than just between vertices. For example, the triangular grid needs eight colours, but if all the triangles in one of the orientations are “fattened” into Reuleaux triangles then they still need only four colours but the other (concave) triangles now only need three. Using similar ideas for tilings with pentagons can give an exclusion set of size 16 as against 18 for the hexagonal tiling; it is easily 7-paintable (is this a good term? – it seems like we could benefit from coining something other than “colorable”)but not 6-paintable – I can’t figure out how to add an image here (though it seems to be doable, since Dustin did it once or twice – Dustin?) so I will put it in the dropbox as “pent-tess.png”.

A few months ago I played with this idea quite a bit and found a couple more tilings with an average exclusion set size of 16 that have more than one tile shape. I’m pretty sure I didn’t exhaust the options.

[Image added. To add an image, just include the url on its own line. – M.]

2. @ag24ag24
I meant this paper by Coulson: http://www.austms.org.au/Publ/JAustMS/V77P2/pdf/a83.pdf
Though yeah, it’s not a major contribution to my knowledge, just a different result in that direction.

I see, I haven’t performed quite as much research into such directions but you’re absolutely right, at a glance I only found a 6-complete dual graph in there, and there’s surely a 7-color critical graph in there too, interesting. In this case since we’re using not entirely convex shapes we make a trade off, worse exclusion zone ratio in general but a better dual graph relationship. I’ve been wondering about cases like this for a while but haven’t found them myself (also didn’t look for them yet), and my searches on the internet came up empty, so thanks for bringing that to my attention.

Of course the easiest scenario would be if these patterns can at best result in the same chromatic number as the most efficient tessellation using regular shapes, but I’m not sure how to test or let alone proof that yet. If however these configurations stay persistently viable through higher dimensions, possibly trumping regular tessellations in some dimensions that’ll make things a lot more complicated, likely demanding a way to generalize and calculate possibilities of “reaching around” adjacent manifolds, and how to limit that. It might make the link to sphere packing less pronounced too, though it certainly can’t remove it entirely. I wonder if these convex/concave boundaries can be applied to permutahedra as well, or if their conjectured inherent relation to sphericality has something to say about that… I guess I have some new venues to look at.

May I ask what program you’ve used for these results? I’ve used SketchUp with a mixture of manual calculation and plugins since that’s a program I already had expertise in but it does have its limitations. Also do we know about any such examples in $\mathbb{R}^3$ yet?

3. ag24ag24 says:

I used PowerPoint to draw the figure; I found it with pen and paper and a bunch of staring at the sky from my hot tub 🙂 Dustin, thanks for adding the image. I’ve tried to explore the idea in R^3 but I haven’t yet found anything interesting. Thanks for the Coulson paper.

4. Heh powerpoint? That indeed seems even more tedious than SketchUp. I’d love to know a program that can properly work with exclusion zones but have no idea how to go about doing that, or if SAGE might be able to.

So about establishing general lower bounds, to my knowledge we know absolutely no way of proving the necessity of using polygons/polytopes/manifolds yet, so doing that is based on assumptions, right?

In my opinion there’s at least two possible ways to achieve that, which I had mentioned in my paper linked in one of my earlier clumsier posts, but that’s already down again for revisioning.

We take a specific perspective on the space, that is all 2 points for which there exists a continuous mapping through the same color are part of the same set, preferably manifold.

Assume $\mathbb{R}^2$ can be efficiently colored with 0-manifolds, discrete spaces, then there has to be a way to color the plane without generating measurable same-color paths as described above, lest that would be a 1-manifold. That is we need a neighborhood around this point without color 1, and since we’re not working with a discrete topology on the general space that neighborhood would have to have a diameter greater than 0. Hoping I got that right.
Then we have a measurable set with an excluded color around our inital vertex, so we place another vertex inside of this neighborhood, for which we have to repeat the same steps. I think we can’t just define the neighborhood as an infinitesimal so we can define our second neighborhood as a strict subset/interior of the first. Now we have a measurable set that excludes two colors. Rinse and repeat to get nested neighborhoods, and the conclusion would be to use an infinite amount of colors or escalate to 1-manifolds.
And once we consider 1-manifolds the same process repeats. Also this process should in general work in $\mathbb{R}^n$ until we reach n-dimensional objects.
(Except $\mathbb{R}^1$ since the connected graph spaces there are discrete, not 1-dimensional)

On the other hand if we consider the exclusion zone of a single vertex then we always find that $\mathbb{X}(v)$ is (n-1)-dimensional and $\mathbb{X}^2(v)$ is n-dimensional, and in all cases we get very clear measures. Now we need to somehow fill $\mathbb{X}(v)$ with colors, and a finite amount at that, so wouldn’t that alone demand a measurable coloring? Dividing the measure of $\mathbb{X}(v)$ by an integer, our number of colors, would still leave a clearly defined measure. Further we need to have exclusion zones overlap one another to some degree for an efficient coloring, and if we take a single color set and put it in $\mathbb{X}(v)$ then we find that the exclusion generated by that color in $\mathbb{X}^2(v)$ is smaller the tighter the color is clustered and larger the finer it is dispersed, again pointing towards not just measurable sets in general put tightly packed manifolds.

It looks to me like any sort of regular graph defined on a euclidean space such that the entire graph is also connected and fills the space will end up demanding a coloring with elements homeomorphic to its containing space.

Thoughts on this, am I making some naive mistake here?

3. “Does $R_4$ enjoy a homomorphic 5-coloring?”

$\omega_{t_4} = \omega_7 = \frac{13+3i\sqrt{3}}{14}$

The only thing this adds into the ring $\overline{R}_4$, that was not already there in $\overline{R}_3$ is the extra factor of 7 in the denominator. In other words $\overline{R}_4 = \overline{R}_3[\frac{1}{7}]$

If $\overline{R}_3$ has a homomorphic 5-colouring then so does $\overline{R}_4$. You just have to multiply by the inverse of 7 mod 5 each time you divide by 7. However, this would eliminate homomorphic 7-colourings and homomorphic 6-colourings are already ruled out for $\overline{R}_3$ because it contains $\frac{1}{6}$

In general if a ring contains the fraction $\frac{1}{k}$ then it does not have a homomorphic k-colouring. Why? because if a number $z$ is in the ring then so is the number $\frac{z}{k}$ but $z = k \cdot \frac{z}{k}$ so in a homomorphic k-colouring every point would have to be assigned the colour 0.

These things are trivial when you see how they work but not so obvious at first thought. If we want to eliminate 5-colourings we would need to add a generator like $\omega_{25}$

1. Does $\omega_7$ add any additional members of unit modulus to the ring?

1. Very good question. It might do. I know how to answer that and will let you know shortly.

First, the members of unit modulus in $\overline{R}_3$ are $\omega^a \eta^b \zeta^c \alpha^d, a,b,c,d \in \mathbb{Z}$ where the first three generators are as in the post and $\alpha = \frac{3 + i\sqrt{55}}{8}$ My proof of this is not 100% watertight because it relies on factorisation in some quadratic rings that are not unique factorisation domains, but I think the result is still correct.

2. I found some extra generators for elements of unit modulus in $\overline{R}_4$ i.e. $\frac{1+4i\sqrt{3}}{7}$ and $\frac{17+3i\sqrt{55}}{28}$

So to correct what I said, these could eliminate homomorphic 5-colourings in $\overline{R}_4$

3. It might be worth adding that $\omega_7$ rotates $\omega + 2$ to $2\omega + 1$. These are already joined by an edge but of course the rotated edges are new elements of unit length.

4. I would be happy to add some of this to the Wiki.

4. Nazgand says:

I just noticed the wiki says H gives a lower bound of 1/6 for ${\bf P}( \mathbf{c}(0) = \mathbf{c}(2) )$, yet a coloring of H exists with all 2-edges bichromatic. Am I missing something, is this bound incorrect, or is the bound given by a graph other than H?

1. Nazgand says:

The method I used to find the conditional probabilities of H is counting the minimum and maximum number of cases for each colouring as was done in Lemma 12’s pentagon method.

2. Yeah, this bound comes not just from H, but from combining the bounds from H from the bound coming from the $\sqrt{3}, \sqrt{3}, 1$ isosceles triangle. The point is that while it is possible for H to have all 2-edges bichromatic, this is only possible when at least 2/3 of the $\sqrt{3}$-edges are monochromatic. On the other hand, the isosceles triangle shows that at most 1/2 of those latter edges are monochromatic. Hence there have to be some monochromatic 2-edges.

5. Rosenfeld asked for the chromatic number of planar points where edges correspond to odd integer distances.

It is interesting if current graphs constructed so far can lead to non 5-colorable odd-distance graphs. For such graphs we can declare the unit distace as representing an odd integer k (which can be one) and add the additional edges for all other distances which are odd integers.

6. Nazgand says:

Lemma 17 is questionable, as it seems to ignore conditional probabilities.
Starting with $0={\bf P}( {\mathbf c}(b) = {\mathbf c}(d) \land {\mathbf c}(0) = {\mathbf c}(d) \mid {\mathbf c}(0) \neq {\mathbf c}(b) )$

I did not find anything more useful than the simplification
${\bf P}( {\mathbf c}(b) \neq {\mathbf c}(d) \land {\mathbf c}(0) = {\mathbf c}(d) \mid {\mathbf c}(0) \neq {\mathbf c}(b) )={\bf P}( {\mathbf c}(0) = {\mathbf c}(d) \mid {\mathbf c}(0) \neq {\mathbf c}(b) )$

What justifies ignoring conditional probabilities?

1. Take $x,y,z\in\mathbb{C}$ that form the vertices of an $(a,b,c)$-triangle. Then Lemma 17 follows from the union bound:

$\mathbf{P}(\mathbf{c}(0)\neq\mathbf{c}(c))$
$=\mathbf{P}(\mathbf{c}(z)\neq\mathbf{c}(x))$
$\leq \mathbf{P}(\mathbf{c}(x)\neq\mathbf{c}(y)\vee \mathbf{c}(y)\neq\mathbf{c}(z))$
$\leq \mathbf{P}(\mathbf{c}(x)\neq\mathbf{c}(y))+\mathbf{P}(\mathbf{c}(y)\neq\mathbf{c}(z))$
$=\mathbf{P}(\mathbf{c}(0)\neq\mathbf{c}(a))+\mathbf{P}(\mathbf{c}(0)\neq\mathbf{c}(b))$

1. Nazgand says:

Thanks for your insight. I figured it out, and tightened the inequality of Lemma 17. I still view what you said as non-rigorous because the line segments (0,a), (0,b), (0,c) do not form a triangle.

[Good point. I edited my comment for clarity. – M.]

7. This is a proposal of a way to prove that we can start with a similar assumption in case of non-measurable colorings, as for measurable ones. More precisely, suppose that we have an (embedded) unit-distance graph $G$ with a special vertex $v_0$ that doesn’t admit a $4$-coloring if $v_0$ has two colors, i.e., none of its neighbors can be red or blue. I want to argue that in this case the chromatic number of the plane is $>4$.

Denote the neighbors of $v_0$ by $\Gamma_0$. Consider the $|\Gamma_0|$ unit circles $\mathcal C$ that are centered on the points $\Gamma_0$ (these all go through $v_0$). I would like to show that for any good (i.e., without a monochromatic unit-distance) $4$-coloring of the plane there is an isometric copy of $\mathcal C$ such that the common points of the circle is, say red, and there is another color, say blue, that is present on all the circles. If we could find such a configuration, then we could just shift $G$ appropriately so that the vertices $\Gamma_0$ are mapped to the centers of the circles.

It might be easier to first prove the respective statement for lines. So this would go as follows:

Prove that for any $m$ directions $\alpha_1,\ldots, \alpha_m$ and any good $4$-coloring of the plane there is a point $p$ and an angle $\varphi$ such that the lines of direction $\alpha_1+ \varphi,\ldots, \alpha_m+ \varphi$ through $p$ share a color that is different from the color of $p$.

At the moment I can only prove this statement for $m=2$ (which would give the respective statement if $deg(v_0)$ in $G$ is $2$, but this clearly won’t help).

8. Here is how to construct a homomorphic 5-colouring for both the rings $\overline{R}_3$ and $\overline{R}_4$

This is building on ideas from David Speyer for $\overline{R}_2$ here

Elements of the rings $\overline{R}_3$ and $\overline{R}_4$ are of the form

$z = \frac{a + bi\sqrt{3} + c\sqrt{5} + di\sqrt{11} + ei\sqrt{15} + f\sqrt{33} + gi\sqrt{55} + h\sqrt{165}}{N}$ where $a,b,c,d,e,f,g,h \in \mathbb{Z}$ and $N = 2^x 3^y 7^z , x,y,z \ge 0 \in \mathbb{Z}$.

For $\overline{R}_3$ the only restriction is $z = 0$. There are no congruence relations to worry about as there were for $\overline{R}_2$.

Expanding out the equation $|z|^2 = 1$ gives four integer equations for elements of unit modulus

$ac + 33fh + 3be + 11dg = 0$
$af + bd + 5ch + 5eg = 0$
$ah + cf + bg + de = 0$
$a^2 + 3b^2 + 5c^2 + 11d^2 + 15e^2 + 33f^2 + 55g^2 + 165h^2 = N^2$

Map the elements of $\overline{R}_4$ to $(A,B,D,F) \in \mathbb{Z}_5^4$ using $A = aN^{-1} \mod 5, B = bN^{-1} \mod 5, D = dN^{-1} \mod 5, F = fN^{-1} \mod 5$

This is a group homomorphism from the additive group of the ring $\overline{R}_4$.

The elements of $\overline{R}_4$ of unit modulus map to a subset of $\mathbb{Z}_5^4$ The elements of this subset can be found by reducing the above equations for the elements of unit modulus modulo 5 giving

$AF + BD = 0$ and $A^2 = 3B^2 + 11D^2 + 33 F^2 = 1$

These can be solved either using a factorisation or by simply testing all 625 cases. I got 24 solutions (call them units). A graph on $\mathbb{Z}_5^4$ can now be constructed such that any two elements are linked if they differ by one of these units. It is a graph of 625 vertices and 15,000 edges. Any k-colouring of this graph would provide a k-colouring of $\overline{R}_4$ which is periodic with a period of 5 in each variable $a,b,d,f$ for fixed $N$, and it would be independent of $c,e,f,h$. 5-colourings which are homomorphisms can be found in the form $pA + qB + rC + sD$ by testing all possible integers mod 5 $p,q,r,s$ to find a set such that none of the 24 units are mapped to zero.

I have checked this and found 384 homomorphic 5-colourings.

Similar methods can be used to look for non-homomorphic 5-colourings with any periodicities that are not multiples of 2,3 or 7. The finite graphs formed by these projections have lots of symmetries generated by multiplication by the units and translations. I wonder if the probabilistic methods can be applied directly to these.

1. Interesting! So $R_3$ is indeed 5-chromatic, but we need another way to build up to a 6-chromatic ring. Here’s a proposal:

Given a k-chromatric ring $\mathcal{R}$, find $x\in\mathcal{R}$ such that for every k-coloring $c$ of $\mathcal{R}$, $c(x)$ is determined by $c(0)$. Then $\mathcal{R}[\omega_{\|x\|^2}]$ is at least (k+1)-chromatic by a spindling argument. This procedure produces the sequence

$\mathbb{Z},\qquad\mathbb{Z}[\omega_1],\qquad\mathbb{Z}[\omega_1,\omega_3],\qquad\mathbb{Z}[\omega_1,\omega_3,\omega_{64/9}].$

(This last ring, call it $R_H$, is due to Jannis Harder.) This begs two questions:

Question. What is $R_H\cap\mathbb{T}$?

Question. Is $R_H$ homomorphically 5-colorable?

In particular, an answer to the first question will give us generators to computationally hunt for the next $x\in R_H$.

1. I agree with that general approach.

This ring $R_H$ can certainly be given the same treatment. It has square roots of -247 instead of 5. This means the group it will project to will be the full $\mathbb{Z}_5^8$ which is bigger but still tractable. From the limited experience we have so far I would be surprised if it does not have lots of homomorphic 5-colourings.

I think to progress it will be necessary to construct some examples of non-homomorphic colourings. David Speyer was able to do this for 4-colourings of $\overline{R}_2$ If all colourings were homomorphic the point 4/3 would be the same colour as zero. A non-homomorphic colouring with a period of 8 ruled this out, but we know from the SAT solvers that the point 8/3 is the same colour.

This leaves us with the expectation that homomorphic colourings will give false positives that need to be ruled out with non-homomorphic colourings. We might look at a periodicity that is a multiple of 5 e.g. 25. The space is too big to search by any kind of brute force search, so the question is whether Speyer’s construction can be generalised and scaled up.

It is possible that bigger rings will be needed to get the desired result. Perhaps it is necessary to throw in both $\omega_4$ and $\omega_{64/9}$.

The next problem is that even if we find two points that appear to have the same colour in all the colourings we can construct, it will be well beyond any SAT solver to prove it, but that will be a problem for later.

2. My coloring wasn’t non-homomorphic, it was just periodic with larger period than expected. I found a 4-coloring of R which was periodic modulo 8R, rather than 4R.
The analogous idea here would be to try to color $\overline{R}_3$ modulo the ideal generated by 25, or perhaps by $5 \sqrt{5}$.

3. Oh, you are using homomorphic to mean a linear map, not merely a periodic coloring. Which makes perfect sense. Sorry!

4. I am going to add some info about the algebraic formulations into the wiki. It might be a good opportunity to clarify the algebraic terminology. It may be better to call the colouring linear if it is a homomorphism of the additive group only. There seem to be also interest in colourings formed by using a ring homomorphism onto a finite ring and then colouring the finite ring.

9. Marijn Heule says:

I found a new record that is substantially smaller compared to the prior ones and it consists of only 633 vertices and 3166 edges. It is a subgraph of two copies of the Minkowski sum of $V \oplus V \oplus V$ with $V$ referring to the one from de Grey’s paper. The copies share the center vertex and are rotated in such a way that the points at distance 2 from the center become connected. The resulting graph is quite interesting and I am writing it up in a paper. I plan to get out by next weekend.

1. Interesting indeed, that’s a big jump. It looks much more symmetrical as well.

2. ag24ag24 says:

Congratulations Marijn!

3. Michael Ruxton says:

I see many red, green, blue, yellow vertices, only one white vertex. Is that correct?

1. I think the point is to illustrate that the graph is 5-vertex-critical. The central vertex is not special: For every vertex v, there should be a 5-coloring such that v is the only vertex colored white.

4. K says:

Cool! But why do you write it up yourself, and not as part of the DHJ Polymath project? I is apparent that you participated here. I thought the purpose is to commonly participate and then commonly, as polymath, write up the results.

1. Michael says:

But he is the only one to reduce the number of points; and no-one else contributed to his arm of the project.

5. Per Terry’s question below, how much smaller can you make the graph if you assume the origin is colored with *two* colors?

10. BTW, what is the minimum average degree (or ratio between edges and vertices) we have for a non 4-colorable unit distance graph?

(I realize now there are two variants: minimum average degree for a non-4-colorable unit-distance graph and minimum average degree for a non-4 colorable subgraph of a unit distance graph.)

11. ag24ag24 says:

I’m wondering whether we should be paying more attention to regular pentagons and related graphs. They seem to have various attractive properties to an even greater extent than hexagons. In particular:

– phi and 1/phi have the smallest probabilistic range we’ve found so far, smaller even than that for $1/\sqrt 3$

– spindling at distance phi is at an angle that is a rational fraction of 2pi (specifically, pi/5)

– scaling introduces unusually few new lengths, on account of the well-known phi-1/phi = phi^2-phi = 1

I’m therefore suspecting that the ring-theoretic approach being taken by Philip and others (which I’m afraid is way above my pay grade) could yield better results in this context. Does that sound plausible?

I’m guessing that 2 cos(pi/10) = $\sqrt{\phi+2}$ also becomes a useful distance to include in such analyses. Calling that number psi, we can start by creating an 8-vertex graph at two pentagons sharing a diagonal, whose 28 distances then consist of ten at 1, nine at phi, four at phi-1, two at psi and one at psi/phi, plus two at the only slightly messier $\sqrt{\phi+3}$. Moving up, the 21-vertex graph consisting of two concentric decagons, one with unit edge and one with unit radius, and their centre (see Figure 15.5 of Soifer’s book, but please let’s not denote it by “H” as he did!) has 210 distances, all of which are one of 1/phi, 1, psi/phi, phi, psi, 2, phi+1, psi*phi, 2*phi, $\sqrt{\phi+3}$ or $\sqrt{2 \phi+3}$. Adding another pentagon that is a factor of phi larger still has mighty few distinct distances.

12. Zachary Chroman says:

Any set of 5 points with only 3 distinct distances can get a probabilistic bound as an embedding of K5. I think there are only finitely many of these, but it’s a pretty large number–has any attempt been made to classify all of them? That might expand our table of probabilities.

More generally, is anything known about graphs we can make from three distinct distances?

1. ag24ag24 says:

Wow, what a cool paper! I don’t think it adds any more cases to Dan and Geoffrey’s list of distances that prohibit 4-colouring when combined with 1, though I had to check pretty carefully. However, I think it does provide some new lower bounds for our probabilistic table, resulting from new graphs that use exactly one of one length and a small number of a second length – e.g. their graph 505 gives $(\sqrt 3 - 1)/\sqrt 2$ >= 1/6 and 507 does the same for $(\sqrt 3 + 1)/\sqrt 2$.

2. Zachary Chroman says:

One potentially helpful lemma here: if ABCDE is an equilateral pentagon (potentially self-intersecting) with diagonals of length v,w,x,y,z, then $1 \leq f(v)+f(w)+f(x)+f(y)+f(z) \leq 2$, where f(x) is the probability that 0 and (0,x) have the same color.

13. I’ve been looking at the second part of Falconer’s argument and I wonder how hard it would be to make it work also for non-measurable colorings. So suppose that the origin is colored with two colors (say 1 and 2) while every other point is colored with just one color (1,2,3 or 4). How hard is it to find a unit distance graph?

Notice that all points of the unit circle around the origin are colored with 3 or 4. This implies that all points of the circle of radius $\sqrt 3$ around the origin are colored with 1 or 2. But since points at unit distance from each other on this circle are colored 1 and 2, this implies of two further circles centered at the origin (one inside the one with radius $\sqrt 3$ and one outside of it) that they are colored with 3 and 4 etc. It seems to me that we get a dense system of concentric circles both from the ones that are colored with 1 and 2, and from the ones that are colored with 3 and 4.

1. I like this question! Surely we can use fewer than 633 vertices if we already know that (say) the origin is colored with one of two colors. This would give for instance a human proof that in a 4-coloring of the plane, the color of any point is determined by the color of all the other points.

Call a radius r “bichromatic” if the circle of radius r uses only 2 colors. As you say, once the origin is colored in two colors, the radii 1 and $\sqrt{3}$ are bichromatic, and more generally if $r$ is bichromatic then so is $\sqrt{r^2-\frac{1}{4}} \pm \frac{\sqrt{3}}{2}$ (assuming that $r \geq 1$). This does presumably give a dense system of bichromatic radii. Furthermore it seems that in each bichromatic circle, each color class is a rotation of the other, and in two nearby bichromatic circles using the same two colors, the color classes in one bichromatic circle are rotations (and dilations) of that in the other. I don’t see how to actually draw a contradiction from this.

An even simpler problem would be prove that there is no 4-coloring in which _every_ radius is bichromatic. We can do it with 633 vertices; surely we can do it in fewer!

1. ag24ag24 says:

@Terry: I like it too, but I must be misunderstanding your closing question. Surely $1/\sqrt 3$ cannot be bichromatic, and neither can any radius which is that of the circumcircle of a regular (2n+1)-gon? Please tell me what I’m misunderstanding.

2. For instance, the 278-vertex graph $M_1$ would already suffice, as it cannot have a monochromatic $\sqrt{3}$-triangle in a specific location.

3. Oh, good point, that latter question is too degenerate. The original question of preventing the origin being bichromatic is still nontrivial though, I think 🙂

4. I was hoping to find an odd cycle with unit lengths either in the union of the 1-2-colored circles, or in the union of the 3-4-colored circles. Can someone good with computers check this? If we find such a short cycle, it might be also a good idea to use its directions/distances to find small 5-chromatic distance graphs.

5. ag24ag24 says:

@domotorp: Yeah, I was thinking the same – I’ve just looked for a simpler version, namely radii that fall into sets of both parities as defined by Terry’s recurrence relation (where the unit circle is indexed 1, $\sqrt 3$ is indexed 2 etc), and I’m not finding any. (I do, however, suggest that we adopt the convention of colouring the origin 2 and 4, rather than 3 and 4, so as to let us use the word “parity” unambiguously!) A next step would be to extend Terry’s recurrence relation to identify radii by triangulating from points at unit distance that lie on circles of the same parity whose radii differ by =1 ? Wouldn’t r >= 1/2 suffice (taking absolute values at the end, of course) and give otherwise-overlooked radii?

6. Yes, indeed, this gives even more radii!

7. ag24ag24 says:

That was supposed to say “differ by at most 1” of course. I am being daunted by the algebra entailed in determining what these new radii are…

8. I think what you mean is that if we have two radii of the same parity, $r_1$ and $r_2$ such that $|r_1-r_2|\leq 1$, then we can find a unit distance by picking one point from one circle, and another from the other circle. We can extend this unit segment into (two) unit triangles, and rotating around the origin thus creates (typically) two new radii.

9. ag24ag24 says:

Actually I wrote two totally separate things but WordPress screwed me over because I foolishly used angle brackets to denote inequalities and a whole chunk thereby got deleted. The first thing I wrote was exactly as you interpreted – and that’s the thing where I am not doing well with the algebra to get an expression for the new radii. The second thing I wrote was that Terry’s original recurrence relation, being the special case of this where we take the vertices of same parity from the same circle, surely need not be restricted to radii at most 1, but only to radii at most 1/2 with a concluding taking of absolute value.

10. ag24ag24 says:

Gah… The second thing I wrote was that Terry’s original recurrence relation, being the special case of this where we take the vertices of same parity from the same circle, surely need not be restricted to radii at LEAST 1, but only to radii at least 1/2 with a concluding taking of absolute value.

11. Pace P. Nielsen says:

Here is another source of new radii. Take a circle of radius $r$ centered at the origin, and a point $p$ on that circle. Let $q$ be a point on that circle obtained by moving through an angle $2n\arcsin(1/(2r))$ with $n$ odd. Then if $p$ and $q$ are less than distance 2 from each other, they can be used to create two circles. (For instance, take the circle of radius $\sqrt{3}$, and jump around the circle 11 times, using a straight-line distance of 1, to get a second point to use.)

12. ag24ag24 says:

@Pace – yes – on the face of it this does not seem like a promising way to beat 278 vertices for the required graph, but we might get lucky. An anecdotal point from my early work on this is that I don’t think I ever found a counterpart of M that excludes the “2tri” colouring of H without also excluding the 1tri colouring (this would suffice for current purposes, I believe); however there may very well be one, since I also didn’t actually look for anything like the 278er.

13. Presumably one can work with one of the existing graphs that preclude equilateral triangles, such as the 278-vertex graph, and see, out of all the radii that appear in that graph, which ones are forced to be bichromatic by relations of the above form. In the best case scenario, we will find that a single radius is forced to be bichromatic in both parities simultaneously, which will give a human-verifiable contradiction; a second-best-case scenario is that among all the bichromatic circles of a single parity, there is an odd cycle. Failing that, perhaps there are still enough bichromatic circles that the number of possible ways to 4-color the remaining graph drops to some human-verifiable number. Once one has a human-verifiable, or nearly-human-verifiable contradiction, it should become clear how to prune the graph while still retaining the contradiction.

14. Pace Nielsen says:

@Aubrey: Yeah, you are probably right. Another random thought is that if you prevent equilateral triangles of side length $\sqrt{3}$ from being monochromatic, then the circle of radius 2 around the origin is bichromatic.

By the way, the algebra to find the new radius from two other radii $r_1,r_2$ close enough together, gives the formula $r_3=\sqrt{1+r_1^2+r_2^2 + \sqrt{3(1+r_1-r_2)(1+r_2-r_1)(1+r_1+r_2)(-1+r_1+r_2)}}/\sqrt{2}$, choosing the appropriate signs on the square-roots.

15. @Pace Thanks, this seems correct! Just since we can create two circles, I think that we need $\pm$ before the $\sqrt 3$ part.

14. I want to highlight the following small unit-distance graph:

Starting with the black diamond $\{0, 1, \omega_1, 1 + \omega_1\}$, the green diamond amounts to rotating $1 + \omega_1$ around $0$ by the by now familiar Moser angle $\arccos(5/6)$, or multiplying the diamond by $\omega_3$. The blue diamond similarly amounts to rotating $0$ around $1 + \omega_1$ by the Moser angle. Of course, we use this angle to ensure the two bonus unit-distance edges between the tips of the various diamonds, but notice that the green and blue diamonds are translations of one another, so we gained a total of *four* bonus edges that are not within the three diamonds.

If our goal is to understand what operations lead to a high chromatic number, it seems worthwhile to understand what operations lead to significant “bonus edges”.

This operation led me to the following unit-distance graph on 21 vertices and 49 edges that contains an isomorphic copy of every connected 7-vertex unit-distance graph as a subgraph:

http://www.hansparshall.com/txt/n7superCoordinates.txt

This is much easier to work with than my previously reported list of coordinates.

Here’s a description. Apply the same operation described above applied to the hex $\{0, 1, \omega_1, 1 + \omega_1, \overline{\omega_1}, 1 + \overline{\omega_1}, 2\}$. This leads to a graph on 19 vertices and 45 edges. This is missing a copy of the “truss” $\{0, 1, \omega_1, 1 + \omega_1, 2, 2 + \omega_1, 3\}$, so manually include $\{2 + \omega_1, 3\}$ to arrive at the 21 vertices and 49 edges above.

1. Your 21-vertex graph can be used to prove $p_2\geq1/4$, which is news to us.

To see this, isolate all pairs of distance $\sqrt{3}$ or 2. There are 23 such pairs $e$. Let $c$ denote any proper coloring of the vertices, and consider the matrix $A$ whose $(e,c)$th entry is 1 if $e$ is monochromatic under $c$ and 0 otherwise. After removing duplicate columns, $A$ is 23-by-228. By our probabilistic formulation, there exists a weight vector $w\in\mathbb{R}^{228}$ of nonnegative entries that sum to 1 such that $(Aw)_e=p_d$ when $e$ has distance $d$. As such, letting $\mathbf{1}_d\in\mathbb{R}^{23}$ indicate the pairs of distance $d$, if we take

$c = \min x_2 \quad \text{s.t.} \quad Aw=x_{\sqrt{3}} \mathbf{1}_{\sqrt{3}}+x_2 \mathbf{1}_2, ~ \mathbf{1}^\top w=1, ~ w,x_1,x_2\geq 0,$

then $p_2\geq c$. Boris reports that $c=1/4$. We’re still hunting for a “human” proof of this lower bound to add to the wiki.

(Btw – Boris has used this formulation to verify many of the entries in the wiki’s table, but this is the first time we found an improvement to the table.)

1. ag24ag24 says:

@Dustin, Boris – can any of the 21 vertices be removed and the lower bound of 1/4 preserved? That might be a route to a human demonstration of the bound.

2. Yes, four vertices can be removed:

3

1/2*i*sqrt(3) + 5/2

1/12*(i*sqrt(11) – 1)*(-i*sqrt(3) – 3)

1/12*(-i*sqrt(11) – 5)*(-i*sqrt(3) – 1) + 1/12*(i*sqrt(11) – 1)*(-i*sqrt(3) – 3)

3. ag24ag24 says:

OK, so only the vertices of the three hexagons are needed, not the extra two that Tamas added in order to include all 7-vertex graphs. And then you can also remove two more – which are symmetrically located in the outer two hexagons (right?). Can you post a picture of the 17-vertex graph please?

2. Here’s the relevant 17-vertex graph styled similar to the above:

1. ag24ag24 says:

Many thanks Hans. Shouldn’t there also be a dotted line between the vertex closest to (2,0) and the vertex at (3/2,-sqrt(3)) ? Also – Dustin/Boris, I’m not seeing how there are only 23 pairs at distances 2 or sqrt(3) in the original 21-vertex graph – I count 33, of which 21 remain in the 17-vertex graph. What am I misunderstanding?

2. Aubrey, I’m a little unsure about the exact count (namely whether it was 21, 22, or 23), but that count was meant to be for the 17-vertex graph.

I can check later what exactly it was, but in any case, the process of finding the pairs at the relevant distances and constructing the matrix is fully automated.

3. ag24ag24 says:

Aha, OK that explains it. Thanks! If the number is indeed 23 then there must be two “bonus” pairs at those distances (i.e., between vertices from different hexagons), presuming that Hans deleted the correct vertices – I can’t see them though – Dustin, can you point them out?

4. Boris says:

Aubrey, the number of edges of interesting length for the 17-vertex graph was supposed to be 22. (I had an off-by-one error, and the description was wrong as we knew previously.) The one “missing” sqrt(3) length is between the second right-most (“blue”) vertex and the bottom-most “green” vertex. I think there was another essentially similar such distance also before the graph was shrunk.

For what it’s worth, the two sqrt(3) length distances within the blue hexagon are not needed for the linear program.

5. Nazgand says:

Has anyone looked at the consequences of this graph for arbitrary angles, and thus arbitrary dotted line lengths?

15. Tamás Hubai says:

Apparently there are finitely many ways to 4-colour the ring $R_2$ and all of them have a simple periodic structure.

To see this, consider the sets $V$ and $H$ as in Aubrey’s paper and the set of transformations $\Phi$ = {identity, translation by 1, rotation by $\frac\pi3$, rotation by $\frac12\arccos\frac56$}. For a set S define $\Phi(S)$ as the union of $\varphi(S)$ for all $\varphi\in\Phi$.

We can verify via computer search that the unit distance graph on $\Phi(V\oplus V)\oplus H$ forces $\Phi(V\oplus V)$ to be coloured in one of 9120 ways (380 if we fix the colouring of a triangle). Furthermore, for any $\varphi\in\Phi$ the restrictions of these colourings to $\varphi(V\oplus V)$ are unique. It follows that in any 4-colouring of $R_2$ we colour $V\oplus V$ in one of these ways and by repeatedly using the operations in $\Phi$ we can uniquely extend it to a colouring of $R_2$. Therefore $R_2$ has 9120 colourings.

I’ve spent the last couple of days analysing these colourings. The transformations generated by $\Phi$ act on them as a permutation group with the structure $(C_8\times C_8\times C_8\times C_8)\rtimes(C_6\times C_6)$ where the normal subgroup part of the semidirect product corresponds to translations and the quotient group corresponds to rotations around the origin. In particular:
– translations by 8 keep the colouring identical (which also follows from Jannis’ 8/3 result)
– rotations by $3\arccos\frac56$ also keep the colouring identical

Once we factor by translations, rotations, reflections and permutations of colours there remain 22 essentially different colourings of $R_2$. Restricting them to $R_1$ yields 12 different colourings.

Every such colouring of $R_1$ is periodic by 2 in one direction, in other words it has alternating stripes of two colours each. The only freedom we have is in the shifting of the stripes relative to each other. Conversely, any pattern of stripes that is periodic by 8 extends to a valid colouring of $R_2$. Isometries of the plane reduce them to the 12 patterns shown here: https://htamas.ces.hu/files/cnp/R2tiles.pdf

For a fixed colouring of $R_1$ we have two different ways to extend it to $R_2$. Either we colour the vertices rotated by $k\arccos\frac56$ the same way as those rotated by $k\frac23\pi$ for all $k\in\mathbb{Z}$ or as those rotated by $-k\frac23\pi$ for all $k$. Once we decide between clockwise and counterclockwise rotation, we use the same direction when rotating around any vertex.

1. Silly question. Is the vertex set $V$ actually contained in $R_2$? If I understand all the notational conventions, $R_2$ is the ring generated by $\omega_1 = \exp( i \pi/3 )$ and $\omega_3 = \exp( i \mathrm{arcccos}(5/6) )$, but $V$ is the set $V = \{0\} \cup \{ \omega_1^x \eta^y: x=0,\dots,5; y=0,\dots,4\}$ where $\eta = \omega_3^{1/2} = \exp( \frac{1}{2} \mathrm{arccos}(5/6) )$, but perhaps I misunderstood some of the previous definitions? (Actually I am not sure what the purpose of $\eta$ is; $\eta^2 = \omega_3$ naturally arises as the rotation angle of a Moser spindle, but why would it be worthwhile to also add in $\eta$?

I’m tempted to human-analyse the 4-colorings of $\Phi(V \oplus V) \oplus H$ that have a bichromatic origin, as this should lead to a lot of bichromatic radii (e.g. all of $V$ is bichromatic).

1. $\eta = \frac{\sqrt{33} + i\sqrt{3}}{6}$

So the ring $R_2 = \mathbb{Z}[\omega_1, \omega_3]$ contains $\eta$

2. In general when you spindle through an angle $\theta$ you rotate lines by $\exp{i\theta}$ and then the extra lines you create at the base of the isosceles triangle are at angles generated from $\exp{i\theta/2}$

3. Tamás Hubai says:

This is Dustin’s drawing on why $\omega_3^{1/2}$ is interesting (and why it is indeed in $R_2$):

It seems that $V\oplus H$ is already impossible to 4-colour with a bichromatic origin.

4. ag24ag24 says:

@Tamas: right; see also the middle panel of my Figure 7. Fascinating about V+H – how many bichromatic radii (and vertices at those radii) does it have, and does it have either of the “best-case” properties mentioned by Terry? Please post a picture, so we can stare at it until a human proof jumps out at us 🙂

5. I have been editing a wiki page “Algebraic formulation of Hadwiger-Nelson problem” to keep notes about these algebras. I am still working on it.

6. Thanks, I understand now. What are the unit vectors that appear in $V \oplus H$? Are there any other than those already in $V$? This graph looks small enough and symmetric enough that there ought to be a human proof that the origin cannot be bichromatic.

7. The unit vectors in $R_2$ are all of the form $\omega^a \eta^b, a,b, \in \mathbb{Z}$

8. To be clear, $\omega^a\eta^b\in R_2$ when $a,b\geq0$, whereas negative exponents are allowed in $\overline{R}_2$.

2. Also, if you’ve managed to show (using $R_2$) that all colorings of $R_1$ have a period of magnitude 2, then the situation is basically that of Figure 3 of Aubrey’s paper and one can do two more spindlings (one at angle $\omega_4$), and one at angle $\omega_{16}$) to get a contradiction. The first spindling (using the six linking vertices) shows that vertices at distance 4 are monochromatic, and the second spindling then gives the contradiction.

1. Tamás Hubai says:

Once we know how the colourings of $R_2$ look like, there are many ways to show $\chi(\mathbb{R}^2)\ge5$. For any $z\in R_2$ the origin has the same colour as $8z$, also $z$ has the same colour as $\omega_3^3 z$. A single spindling with any such distance will lead to contradiction. Perhaps I should have noted that in my original comment.

The issue, of course, is that my structural description still relies on computer verification for the proof. But with this knowledge we might be able to find some useful claims about the colourings of $R_2$ that we can prove by hand.

3. Philip Gibbs says:

Tamás you wrote “Once we decide between clockwise and counterclockwise rotation, we use the same direction when rotating around any vertex.” Are you sure this is correct? I find that if I assume this then I can deduce a periodicity of 4 which is wrong.

If I assume a clockwise rotation about odd vertices and an anticlockwise rotation about even vertices, or vice-versa, then I can deduce a periodicity of 8 only.

I conclude this by rotating about one vertex and then rotating back about a different vertex.

1. Tamás Hubai says:

I still believe that rotation by $\omega_3$ is either equivalent to rotation by $\omega_1^2$ for all vertices or to rotation by $\omega_1^{-2}$ for all vertices. Also I was able to deduce periodicity by 8 following your argument but not periodicity by 4. Can you describe your method in more detail?

By the way, my proof of periodicity uses the following sequence of rotations:
$\omega_1^2$ around the origin
$\omega_1^{-2}\omega_3$ around (1, 0)
$\omega_1^{-2}\omega_3^{-1}$ around the origin
$\omega_1^2\omega_3^{-1}$ around (1, 0)
$\omega_3$ around the origin
which is equivalent to a shift by 8/3 and also cancels out if we assume either $\omega_3=\omega_1^2$ or $\omega_3=\omega_1^{-2}$.

2. Philip Gibbs says:

Thank you for checking. I believe you are right, I had some errors.

I think I may be able to construct a slightly more ambitious argument starting just from the fact that each $R_1$ has a period 2 in one direction plus the observation that monochromatic vertices are never separated by an odd number of links in any of the three directions. If I can do it I will put it in the Wiki so it can more easily be corrected.

3. ag24ag24 says:

Guys – let’s movethis to the actve thread. I have a question that I will post there as a seed for that.

16. Good, this confirms that the non-linear colorings with period 8 do exist as found earlier by David Speyer. We now also know that all colorings have period 8.

It would be useful to know whether additional generators can reduce the possibilities to only linear 4-colorings.

17. Tamás Hubai says:

Here is a small graph that cannot be 4-coloured with a bichromatic origin:

The points are on circles with radii 0, $\frac{\sqrt{33}-3}6$, $\frac1{\sqrt3}$, $\sqrt{\frac{9-\sqrt{33}}6}$ and 1. The circle with radius $\frac1{\sqrt3}$ is the circumcircle of a regular triangle with unit sides.

1. So much smaller! Is this computer verified?

1. Tamás Hubai says:

Yes, it is.

2. This graph is so small, that I think it also gives hope to finding something similar in 3-dimensions. There currently the best known lower bound is 6, but if we start from a trichromatic origin, we get trichromatic spheres (with certain radii) around it, and can hopefully reach a contradiction if we assume 6 colors. Why can we suppose that the origin is trichromatic? Well, that depends on the higher dimensional variant of this yet unproved conjecture:
https://mathoverflow.net/questions/299616/bichromatic-pencils

3. ag24ag24 says:

Totally awesome. Please tell us a little about how you found it! Also, of course, let’s hunt for properties shared by all colourings, so as to see what 5-chromatic graphs we can build from this. Are there any forced-mono vertex pairs? Any distances with frequencies that contradict our probabilistic bounds? Etc.

4. I’ve been trying to verify this graph by hand and I’m stuck. If I suppose that the circles of radius $\frac{\sqrt{33} -3}{6}$ and $1$ are red-blue and everything else is green-yellow, I cannot find any odd cycles in any of the components.

1. Pace P. Nielsen says:

I believe the following is a human readable proof of this claim. I’ll use C(x) for the color of point x, using the numbering in the graph above. Throughout we don’t need the origin bicolored (or even included), we just need that the outer circle is bichromatic—call those two colors A,B. Without loss of generality assume C(7)=A.

Case I: C(7)=C(14). This determines the colors of 19, 26, 31, 36, 38, 42, 11, 18, 23, and 30. Now the points 10, 27, and 34 must have colors different from A and B, but they form a 3-cycle which is a contradiction.

Case II: C(7)!=C(14). Without loss of generality suppose C(14)=C(2). The colors on the outer circle are completely determined.

Now, C(8)!=A,B by looking at its connections to 3 and 23. Similarly, C(16)!=A,B by looking at its connections to 30 and 38.

The triangle formed from 8, 16, and 27 shows that C(27) is among A or B. Using the line from 27 to 38, we see that C(27)=C(7).

Repeating this argument, after making a $2\pi/3$ counter-clockwise turn, we get C(10)=C(7), contradicting the fact that 10 and 27 are connected.

2. Marijn Heule says:

My smallest graph for which the center cannot be colored with two colors consists of 24 vertices. Actually I found many of them. The reduction algorithm gets down to 24 in roughly 80% of the cases, but not lower yet. Below an image of a 24 vertex graph. The center is the vertex with the highest degree.

I will try to find a more symmetric one.

3. Here is a slight rearrangement of Pace’s argument. Excluding the origin, the 42-vertex graph of Tamas splits into six hexagons: $H_1 = \{1,2,3,4,5,6\}$, $H_1^+ = \{ 7,11,23,31,19,38\}$, $H_1^- = \{ 14, 18, 26, 30, 36, 42 \}$, $H_{\sqrt{(9-\sqrt{33})/6}}^+ = \{ 8,20,32,39,13,25\}$, $H_{\sqrt{(9-\sqrt{33})/6}}^- = \{ 12,17,24,29,35,41\}$, $H_{1/\sqrt{3}} = \{ 10,15,22,27,34, 37\}$, and $H_{(\sqrt{33}-3)/6} = \{9,16,21,28,33,40\}$, where the subscript denotes the radius of the hexagon. There is a conjugation symmetry that maps the + hexagons to the – hexagons leaving the other vertices unchanged.

Because $H_{1/\sqrt{3}}$ contains an equilateral unit triangle, it cannot be bichromatic (this was already observed earlier by Aubrey).

By hypothesis, $H_1, H_1^+, H_1^-$ are all bichromatic with colors A,B say. If $H_1^+$ and $H_1^-$ are aligned in the sense that $C(7)=C(14)$, this forces $H_{1/\sqrt{3}}$ to be CD-bichromatic, contradicting the previous paragraph. So $C(7) \neq C(14)$. This makes $H_{(\sqrt{33}-3)/6}$ CD-bichromatic instead. Also, by comparing $H_1^-$ and $H_1^+$ with $H_1$, at least one of $H_{\sqrt{(9-\sqrt{33})/6}}^+$ or $H_{\sqrt{(9-\sqrt{33})/6}}^-$ is CD-bichromatic, which on combining with $H_{(\sqrt{33}-3)/6}$ CD-bichromatic forces $H_{1/\sqrt{3}}$ to be AB-bichromatic, and again we contradict the previous paragraph.

It’s rather amazing that one can create so many unit distances between these hexagons. I wonder if this graph can give useful consequences (e.g. on edge probabilities) even if we don’t assume the origin to be bichromatic.

18. Has anyone tested whether any of our 5-chromatic graphs has the property that there is no 5-coloring with a bichromatic origin? This would imply $\mathrm{MCNP}\geq6$.

1. Marijn Heule says:

I have been trying to find such a graph. My best attempt so far is a graph with 5617 vertices for which it was computationally hard to find a 5 coloring with the center vertex being bichromatic. So I am unaware of such a graph.

1. ag24ag24 says:

I think I’m missing something here. How does a graph lacking a k-colouring in which a specified vertex can take either of two colours lead to a non-k-colourable graph? Don’t we additionally need a second specified vertex that is also constrained to be the same colour as the first one, or something equivalent? Apologies if things have just been moving too fast for me!

2. @Aubrey – If you can’t k-color a unit-distance graph with a bichromatic vertex, then you can run part of Falconer’s argument to conclude that the measurable chromatic number is at least k+1. I don’t know how to remove “measurable” from the conclusion.

19. ag24ag24 says:

Ah, of course – thanks Dustin. I expect that Marijn is lookng out for suitable additional properties like this of his computationally hard graphs, that would allow the measurability criterion to be dropped. As for his 24-vertex graph, it’s particularly interesting that there are (I think) six distinct radii, as against only four for Tamas’s 43er. It would be most interesting if we could reduce either of these numbers (24 or 4) further.

20. ag24ag24 says:

I’m attempting to shrink Tamas’s 43er in a human-comprehensible way. We only need one, not both, of the two unit-edge triangles centred on the origin to be bichromatic if the origin is. Thus, I think we can omit vertices 10, 27 and 34, and tbence vertices 8, 13, 24, 29, 32 and 41, thus getting us down to 34 vertices – way short of Marijn’s 24, but comprehensible. Here’s what it looks like:

1. ag24ag24 says:

Hm, OK, I tried to include a link to the image in the dropbox – clicking on it works, but the image is not appearing in the actual post (at least not in my browser). Dustin, I hope you can bothfix it and tell me what I did wrongly – thanks!

[It looks like the link you posted was some sort of “Dropbox preview.” To obtain a Dropbox link, I right-click the file and select “Copy Dropbox Link.” – M.]

1. When I click on it I get a request to login so the problem might be that it is not accessible publicly without an account.

2. Michael Ruxton says:

A lot of symmetry in this graph.