Probabilistic formulation of Hadwiger-Nelson problem

Suppose for sake of contradiction that we have a 4-coloring [math]\displaystyle{ c: {\bf C} \to \{1,2,3,4\} }[/math] of the complex plane with no unit edges monochromatic, thus

[math]\displaystyle{ c(z) \neq c(w) \hbox{ whenever } |z-w| = 1. \quad (1) }[/math]

We can create further such colorings by composing [math]\displaystyle{ c }[/math] on the left with a permutation [math]\displaystyle{ \sigma \in S_4 }[/math] on the left, and with the (inverse of) a Euclidean isometry [math]\displaystyle{ T \in E(2) }[/math] on the right, thus creating a new coloring [math]\displaystyle{ \sigma \circ c \circ T^{-1}: {\bf C} \to \{1,2,3,4\} }[/math] of the complex plane with the same property. This is an action of the solvable group [math]\displaystyle{ S_4 \times E(2) }[/math].

It is a fact that all solvable groups (viewed as discrete groups) are amenable, so in particular [math]\displaystyle{ S_4 \times E(2) }[/math] is amenable. This means that there is a finitely additive probability measure [math]\displaystyle{ \mu }[/math] on [math]\displaystyle{ S_4 \times E(2) }[/math] (with all subsets of this group measurable), which is left-invariant: [math]\displaystyle{ \mu(gE) = \mu(E) }[/math] for all [math]\displaystyle{ g \in S_4 \times E(2) }[/math] and [math]\displaystyle{ E \subset S_4 \times E(2) }[/math]. This gives [math]\displaystyle{ S_4 \times E(2) }[/math] the structure of a finitely additive probability space. We can then define a random coloring [math]\displaystyle{ {\mathbf c}: {\bf C} \to \{1,2,3,4\} }[/math] by defining [math]\displaystyle{ {\mathbf c} := {\mathbf \sigma} \circ c \circ {\mathbf T}^{-1} }[/math], where [math]\displaystyle{ ({\mathbf \sigma},{\mathbf T}) }[/math] is the element of the sample space [math]\displaystyle{ S_4 \times E(2) }[/math]. Thus for any complex number [math]\displaystyle{ z }[/math], the random color [math]\displaystyle{ {\mathbf c}(z) }[/math] is a random variable taking values in [math]\displaystyle{ \{1,2,3,4\} }[/math]. The left-invariance of the measure implies that for any [math]\displaystyle{ (\sigma,T) \in S_4 \times E(2) }[/math], the coloring [math]\displaystyle{ \sigma \circ {\mathbf c} \circ T^{-1} }[/math] has the same law as [math]\displaystyle{ {\mathbf c} }[/math]. This gives the color permutation invariance

[math]\displaystyle{ {\bf P}( {\mathbf c}(z_1) = c_1, \dots, {\mathbf c}(z_k) = c_k ) = {\bf P}( {\mathbf c}(z_1) = \sigma(c_1), \dots, {\mathbf c}(z_k) = \sigma(c_k) )\quad (2) }[/math]

for any [math]\displaystyle{ z_1,\dots,z_k \in {\bf C} }[/math], [math]\displaystyle{ c_1,\dots,c_k \in \{1,2,3,4\} }[/math], and [math]\displaystyle{ \sigma \in S_4 }[/math], and the Euclidean isometry invariance

[math]\displaystyle{ {\bf P}( {\mathbf c}(z_1) = c_1, \dots, {\mathbf c}(z_k) = c_k ) = {\bf P}( {\mathbf c}(T(z_1)) = c_1, \dots, {\mathbf c}(T(z_k)) = c_k. \quad (3) }[/math]

(In probabilistic language, this means that the random coloring is a stationary process with respect to the action of [math]\displaystyle{ S_4 \times E(2) }[/math]. The extraction of a stationary process from a deterministic object is an example of the Furstenberg correspondence principle.)

Bounds on [math]\displaystyle{ p_d }[/math] for 4-colourings

A class of correlations that is of particular interest is that of vertex pairs at some distance [math]\displaystyle{ d }[/math]. Accordingly, define

[math]\displaystyle{ p_d := {\bf P}( \mathbf{c}(0) = \mathbf{c}(d) ). }[/math]

distance	Lower bound	Lower-bounding graph/method	Upper bound	Upper-bounding graph	Notes
[math]\displaystyle{ \geq 1/2 }[/math]			1/2	Spindle
[math]\displaystyle{ \geq \frac{2}{\sqrt{15}} }[/math]			[math]\displaystyle{ \frac{1}{2} - \frac{1}{62} }[/math]	Proposition 36
[math]\displaystyle{ d\geq 1/n, n\gt 1 }[/math]			[math]\displaystyle{ 1-\frac{1}{n} }[/math]	(n+1)-gon with one edge length 1 and the rest d, Lemma 34
[math]\displaystyle{ d\geq 1/(n \sqrt{3}), n\gt 1 }[/math]			[math]\displaystyle{ (3n-2)/3n }[/math]	(n+1)-gon with one edge length [math]\displaystyle{ 1/\sqrt{3} }[/math] and the rest d, Lemma 34	Not better than the above on intervals [math]\displaystyle{ \left(\frac{1}{7},\frac{1}{4\sqrt{3}}\right),\left(\frac{1}{4},\frac{1}{2\sqrt{3}}\right) }[/math]
1	0	Unit edge	0	Unit edge
[math]\displaystyle{ \frac{1}{\sqrt{3}} }[/math]	1/28	Unit diamond plus centres of triangles, together with H, Corollary 16	1/3	Unit triangle plus its centre
2	1/4	[math]\displaystyle{ G_{21} }[/math]	[math]\displaystyle{ \frac{1}{2} - \frac{1}{62} }[/math]	Proposition 36	Lower bound computer verified
[math]\displaystyle{ {\sqrt{3}} }[/math]	1/4	H, Corollary 16	[math]\displaystyle{ \frac{1}{2} - \frac{1}{62} }[/math]	Proposition 36
[math]\displaystyle{ {\frac{\sqrt{5}+1}{2}} }[/math]	1/5	regular pentagon with unit side length	2/5	regular pentagon with unit side length
[math]\displaystyle{ {\frac{\sqrt{5}-1}{2}} }[/math]	1/5	regular pentagon with [math]\displaystyle{ {\frac{\sqrt{5}-1}{2}} }[/math] side length	2/5	regular pentagon with [math]\displaystyle{ {\frac{\sqrt{5}-1}{2}} }[/math] side length
[math]\displaystyle{ {\sqrt{11/3}} }[/math]	1/118	[math]\displaystyle{ G_{40} }[/math]	[math]\displaystyle{ \frac{1}{2} - \frac{1}{62} }[/math]	Proposition 36	computer-verified
8/3	1	[math]\displaystyle{ V \oplus V \oplus H }[/math]	[math]\displaystyle{ \frac{1}{2} - \frac{1}{62} }[/math]	Proposition 36	computer-verified; leads to contradiction
[math]\displaystyle{ \frac{\sqrt{6} \pm \sqrt{2}}{2} }[/math]	1/6	An arrangement of five vertices; Lemma 2	[math]\displaystyle{ \frac{1}{2} - \frac{1}{62} }[/math]	Proposition 36
[math]\displaystyle{ \sqrt{2} }[/math]	1/14	A graph of 13 vertices	[math]\displaystyle{ \frac{1}{2} - \frac{1}{62} }[/math]	Proposition 36
[math]\displaystyle{ \frac{1}{2} \sqrt{3^{1/4} \cdot 2 \sqrt{2} + 2 \sqrt{3} + 2} }[/math]	1/28	A graph of 13 vertices; Lemma 2	[math]\displaystyle{ \frac{1}{2} - \frac{1}{62} }[/math]	Proposition 36
[math]\displaystyle{ \sqrt{3/2 + \sqrt{33}/6} }[/math]	1/196	A graph of 9 vertices; Corollary 16	[math]\displaystyle{ \frac{1}{2} - \frac{1}{62} }[/math]	Proposition 36
[math]\displaystyle{ \sqrt{5/3} }[/math]	1/756	A graph of 33 vertices; Corollary 16	[math]\displaystyle{ \frac{1}{2} - \frac{1}{62} }[/math]	Proposition 36
[math]\displaystyle{ 2/\sqrt{3} }[/math]	1/177	A graph of 103 vertices	[math]\displaystyle{ \frac{1}{2} - \frac{1}{62} }[/math]	Proposition 36	Computer-verified
[math]\displaystyle{ \frac{\sqrt{33} \pm 1}{2\sqrt{3}} }[/math]	1/2	[math]\displaystyle{ G_{420} }[/math]	[math]\displaystyle{ \frac{1}{2} - \frac{1}{62} }[/math]	Proposition 36	Computer-verified

Bounds on [math]\displaystyle{ {\bf P}( \mathbf{c}(0) = \mathbf{c}(d_1) \mid \mathbf{c}(0) \neq \mathbf{c}(d_0) ) }[/math] for 4-colourings

[math]\displaystyle{ d_1 }[/math]	[math]\displaystyle{ d_0 }[/math]	Lower bound	Lower-bounding graph	Upper bound	Upper-bounding graph	Notes
[math]\displaystyle{ 1+(-1)^{1/3} }[/math]	[math]\displaystyle{ 2 }[/math]	1/2	H			Equals [math]\displaystyle{ p_{\sqrt 3}/(1-p_2) }[/math]
[math]\displaystyle{ 1+(-1)^{1/3} }[/math]	[math]\displaystyle{ 1+(-1)^{-1/3} }[/math]			1/2	H

Proofs of bounds

One can compute some correlations of the coloring exactly:

Lemma 1

Let [math]\displaystyle{ z,w \in {\bf C} }[/math] with [math]\displaystyle{ |z-w|=1 }[/math]. Then

[math]\displaystyle{ {\bf P}( \mathbf{c}(z) = c ) = \frac{1}{4}\quad (4) }[/math]

for all [math]\displaystyle{ c=1,\dots,4 }[/math],

[math]\displaystyle{ {\bf P}( \mathbf{c}(z) = \mathbf{c}(w) ) = 0\quad (5), }[/math]

and

[math]\displaystyle{ {\bf P}( \mathbf{c}(z) = c; \mathbf{c}(w) = c' ) = \frac{1}{12} \quad (6) }[/math]

for any distinct [math]\displaystyle{ c,c' \in \{1,2,3,4\} }[/math]. If [math]\displaystyle{ u }[/math] is at a unit distance from both z and w, then

[math]\displaystyle{ {\bf P}( \mathbf{c}(z) = c; \mathbf{c}(w) = c'; \mathbf{c}(u) = c'' ) = \frac{1}{24} \quad (6') }[/math]

Proof By color invariance (2), the four probabilities in (4) are equal and sum to 1, giving (4). The claim (5) is immediate from (1). From (5) and color invariance, the 12 probabilities in (6) are equal and sum to 1, giving (6). The same argument gives (6').[math]\displaystyle{ \Box }[/math]

Lemma 2

(Spindle argument) Let [math]\displaystyle{ |d| \geq 1/2 }[/math]. Then

[math]\displaystyle{ p_d \leq \frac{1}{2} \quad (7). }[/math]

Proof We can find an angle [math]\displaystyle{ \theta }[/math] with [math]\displaystyle{ |de^{i\theta}-d|=1 }[/math], then [math]\displaystyle{ \mathbf{c}(de^{i\theta}) \neq \mathbf{c}(d) }[/math] almost surely. This means that at least one of the events [math]\displaystyle{ \mathbf{c}(0) = \mathbf{c}(d) }[/math], [math]\displaystyle{ \mathbf{c}(0) = \mathbf{c}(d e^{i\theta}) }[/math] occurs with probability at most 1/2. The claim now follows from isometry invariance (3). [math]\displaystyle{ \Box }[/math]

Lemma 3

(Using the K graph) We have

[math]\displaystyle{ 52 {\bf P}( \mathbf{c}(1) = \mathbf{c}(e^{2\pi i/3}) = \mathbf{c}(e^{4\pi i/3}) ) + {\bf P}( \mathbf{c}(-z) = \mathbf{c}(z) \hbox{ for } z = 2, 2e^{2\pi i/3}, 2e^{4\pi i/3} ) \geq 1 \quad (8). }[/math]

Proof Consider the 61-vertex graph [math]\displaystyle{ K }[/math] from de Grey's paper. It has 26 (isometric) copies of H, and thus 52 copies of the triangle [math]\displaystyle{ (1, e^{2\pi i/3}, e^{4\pi i/3}) }[/math]. With probability at least [math]\displaystyle{ 1 - 52 {\bf P}( \mathbf{c}(1) = \mathbf{c}(e^{2\pi i/3}) = \mathbf{c}(e^{4\pi i/3}) ) }[/math], none of these triangles are monochromatic. By the argument in that paper, this implies that the three linking diagonals [math]\displaystyle{ (-2, +2) }[/math], [math]\displaystyle{ (-2 e^{2\pi i/3}, 2e^{2\pi i/3}) }[/math], [math]\displaystyle{ (-2 e^{4\pi i/3}, e^{-4\pi i/3}) }[/math] are monochromatic. This gives the claim. [math]\displaystyle{ \Box }[/math]

Corollary 4

(Existence of monochromatic [math]\displaystyle{ \sqrt{3} }[/math]-triangles) We have [math]\displaystyle{ {\bf P}( \mathbf{c}(1) = \mathbf{c}(e^{2\pi i/3}) = \mathbf{c}(e^{4\pi i/3}) ) \geq \frac{1}{104} }[/math].

Proof The probability [math]\displaystyle{ {\bf P}( \mathbf{c}(-z) = \mathbf{c}(z) \hbox{ for } z = 2, 2e^{2\pi i/3}, 2e^{4\pi i/3} ) }[/math] is at most [math]\displaystyle{ {\bf P}( \mathbf{c}(-2) = \mathbf{c}(2)) = p_4 }[/math], which by Lemma 2 is at most 1/2. The claim now follows from Lemma 3. [math]\displaystyle{ \Box }[/math]

Computer-verified Claim 5

(Using the graph M) One has [math]\displaystyle{ {\bf P}( \mathbf{c}(1) = \mathbf{c}(e^{2\pi i/3}) = \mathbf{c}(e^{4\pi i/3}) ) = 0 }[/math] (Note this contradicts Corollary 4).

Proof This simply reflects the fact that there is no 4-coloring of the 1345-vertex graph M from de Grey's paper with its central copy of H containing a monochromatic triangle. One can use other graphs for this purpose, such as the 278-vertex graph [math]\displaystyle{ M_1 }[/math] or [math]\displaystyle{ V \oplus V \oplus H }[/math]. [math]\displaystyle{ \Box }[/math]

Computer-verified Claim 6

(Using the graph [math]\displaystyle{ V \oplus V \oplus H }[/math]) One has [math]\displaystyle{ p_{8/3} = 1 }[/math] (note this contradicts Lemma 2).

Proof This reflects the fact that every 4-coloring of [math]\displaystyle{ V \oplus V \oplus H }[/math] must assign the same color to 0 and 8/3. There is also a 745-vertex subgraph of [math]\displaystyle{ V \oplus V \oplus H }[/math] with the same property. [math]\displaystyle{ \Box }[/math]

Lemma 7

(Using [math]\displaystyle{ G_{40} }[/math]) We have

[math]\displaystyle{ 59 p_{\sqrt{11/3}} + p_{8/3} \geq 1 }[/math].

Proof This reflects the fact that every 4-coloring of the 40-vertex graph [math]\displaystyle{ G_{40} }[/math] from Exoo-Ismaolescu in which none of the 59 pairs of vertices at distance [math]\displaystyle{ \sqrt{11/3} }[/math] apart, will assign the same color to 0 and 8/3. (This is presumably human-verifiable.) [math]\displaystyle{ \Box }[/math]

Corollary 8

One has

[math]\displaystyle{ p_{\sqrt{11/3}} \geq \frac{1}{118} }[/math].

Proof Combine Lemma 7 and Lemma 2. [math]\displaystyle{ \Box }[/math]

Lemma 9

(Using [math]\displaystyle{ G_{49} }[/math]) One has

[math]\displaystyle{ 18 {\bf P}( \mathbf{c}(1/3) = \mathbf{c}(e^{2\pi i/3}/3) = \mathbf{c}(e^{4\pi i/3}/3) ) \geq p_{\sqrt{11/3}} . }[/math]

Proof This reflects the fact that every 4-coloring of the 49-vertex graph [math]\displaystyle{ G_{49} }[/math] from Exoo-Ismaolescu in which 0 and [math]\displaystyle{ \sqrt{11/3} }[/math] have the same color, at least one of the 18 copies of [math]\displaystyle{ (1/3, e^{2\pi i/3}/3, e^{4\pi i/3}/3) }[/math] is monochromatic. This is potentially human-verifiable. [math]\displaystyle{ \Box }[/math]

Corollary 10

(Existence of monochromatic [math]\displaystyle{ 1/\sqrt{3} }[/math]-triangles) One has [math]\displaystyle{ {\bf P}( \mathbf{c}(1/3) = \mathbf{c}(e^{2\pi i/3}/3) = \mathbf{c}(e^{4\pi i/3}/3) ) \geq \frac{1}{2124}. }[/math]

Proof Combine Corollary 8 and Lemma 9. [math]\displaystyle{ \Box }[/math]

Computer-verified claim 11

One has [math]\displaystyle{ {\bf P}( \mathbf{c}(1/3) = \mathbf{c}(e^{2\pi i/3}/3) = \mathbf{c}(e^{4\pi i/3}/3) ) = 0 }[/math]. (This contradicts Corollary 10).

Proof This reflects the fact that the 627-vertex graph [math]\displaystyle{ G_{627} }[/math] from Exoo-Ismaolescu does not have any 4-colorings with [math]\displaystyle{ 1/3, e^{2\pi i/3}/3, e^{4\pi i/3}/3 }[/math] monochromatic. [math]\displaystyle{ \Box }[/math]

Lemma 12

For certain special distances d, one can improve the bound in Lemma 2:

If [math]\displaystyle{ k \geq 1 }[/math] is a natural number, [math]\displaystyle{ j\in\mathbb{Z} }[/math], [math]\displaystyle{ \gcd(j,2k+1)=1 }[/math], and [math]\displaystyle{ r = \frac{1}{2} \csc\left(\frac{j\pi}{2k+1}\right) }[/math] then

[math]\displaystyle{ p_r \leq \frac{k}{2k+1}, }[/math]

thus for instance

[math]\displaystyle{ p_{\frac{1}{\sqrt{3}}} \leq \frac{1}{3}. }[/math]

Proof Observe that the regular 2k+1-polygon [math]\displaystyle{ r, re^{2\pi i/(2k+1)}, r e^{4\pi i/(2k+1)}, \dots, r^{4k\pi i/(k+1)} }[/math] has unit side lengths. By the pigeonhole principle, we conclude that at most k of these vertices can have the same color as the origin, and the claim follows. [math]\displaystyle{ \Box }[/math]

On the other hand, for [math]\displaystyle{ k=2,j=1 }[/math] we also know from the regular pentagon of unit sidelength that

[math]\displaystyle{ \frac{1}{5} \leq p_{\frac{\sqrt{5}+1}{2}} \leq \frac{2}{5} \quad (9) }[/math]

since any 4-coloring of that pentagon has either one or two monochromatic diagonals.

Similarly, for [math]\displaystyle{ k=2,j=2 }[/math] we also know from the regular pentagon of [math]\displaystyle{ \frac{\sqrt{5}-1}{2} }[/math] sidelength that

[math]\displaystyle{ \frac{1}{5} \leq p_{\frac{\sqrt{5}-1}{2}} \leq \frac{2}{5} }[/math]

since any 4-coloring of that pentagon has either one or two monochromatic edges. More generally, if [math]\displaystyle{ a,b,c,d,e }[/math] are the diagonal lengths of a pentagon with unit sides, then

[math]\displaystyle{ 1 \leq p_a + p_b + p_c + p_d + p_e \leq 2. }[/math]

Lemma 13

We have

[math]\displaystyle{ 7 p_{\frac{1}{\sqrt{3}}} \geq p_{\sqrt{3}} }[/math].

Proof Consider the unit rhombus [math]\displaystyle{ 0, 1, e^{i\pi/3}, e^{-i\pi/3} }[/math] together with the centers [math]\displaystyle{ e^{i\pi/6}/\sqrt{3}, e^{-i\pi/6}/\sqrt{3} }[/math]. With probability [math]\displaystyle{ p_{\sqrt{3}} }[/math], the two far vertices [math]\displaystyle{ e^{i\pi/3}, e^{-i\pi/3} }[/math] are the same color, and then 0,1 will be two other colors. This forces either one of the centers [math]\displaystyle{ e^{i\pi/6}/\sqrt{3} }[/math] of a triangle to have a common color with one of the vertices of that triangle, or the two centers must have the same color. Thus in any event one of the seven edges of distance [math]\displaystyle{ 1/\sqrt{3} }[/math] is monochromatic, giving the claim. [math]\displaystyle{ \Box }[/math]

Corollary 14

We have [math]\displaystyle{ p_{\frac{1}{\sqrt{3}}} \geq \frac{1}{728} }[/math].

This slightly improves upon the lower bound of 1/2124 coming from Corollary 10.

Proof Combine Corollary 4 and Lemma 13. [math]\displaystyle{ \Box }[/math]

Lemma 15

One has

[math]\displaystyle{ p_{\sqrt{3}} + p_2 \geq \frac{2}{3} }[/math] and [math]\displaystyle{ 2 p_{\sqrt{3}} + p_2 \geq 1 }[/math].

Proof As noted in de Grey's paper, there are essentially four 4-colorings of H. H has six edges of length [math]\displaystyle{ \sqrt{3} }[/math] and three of length [math]\displaystyle{ 2 }[/math]. If we let a denote the number of monochromatic [math]\displaystyle{ \sqrt{3} }[/math] edges and b the number of monochromatic [math]\displaystyle{ 2 }[/math]-edges, we see from inspection of all four colorings that [math]\displaystyle{ (a,b) }[/math] is either [math]\displaystyle{ (6, 0), (4,0), (2, 1) }[/math], or [math]\displaystyle{ (0,3) }[/math]. In particular, one always has [math]\displaystyle{ \frac{a}{6} + \frac{b}{3} \geq \frac{2}{3} }[/math] and [math]\displaystyle{ 2\frac{a}{6} + \frac{b}{3} \geq 1 }[/math]. Taking expectations, we obtain the claim. [math]\displaystyle{ \Box }[/math]

Corollary 16

We have [math]\displaystyle{ p_2 \geq \frac{1}{6} }[/math], [math]\displaystyle{ p_{\sqrt{3}} \geq \frac{1}{4} }[/math] and [math]\displaystyle{ p_{\frac{1}{\sqrt{3}}} \geq \frac{1}{28} }[/math].

Proof Combine Lemma 2, Lemma 15, and Lemma 13. [math]\displaystyle{ \Box }[/math]

Lemma 17

If [math]\displaystyle{ a,b,c \gt 0 }[/math] are the lengths of a triangle, then [math]\displaystyle{ p_a + p_b \leq 1 + p_c }[/math].

Proof Consider a triangle of side lengths a,b,c. If the c side is not monochromatic, then at least one of the other two sides must fail to be monochromatic also, thus

[math]\displaystyle{ {\bf P}(\mathbf{c}(0) \neq \mathbf{c}(a)) + {\bf P}(\mathbf{c}(0) \neq \mathbf{c}(b)) \geq {\bf P}(\mathbf{c}(0) \neq \mathbf{c}(c)) }[/math]

and the claim follows. [math]\displaystyle{ \Box }[/math]

Note that Lemma 2 follows from the a=b, c=1 case of this lemma. Iterating this lemma starting with Lemma 2 we can also obtain slightly nontrivial upper bounds on [math]\displaystyle{ p_a }[/math] for small values of a, e.g. [math]\displaystyle{ p_a \leq 1 - 2^{-k} }[/math] when [math]\displaystyle{ a \geq 2^{-k}, k\in\mathbb{Z}^+ }[/math].

Further, we can generalise the a=b case to one in which the triangle is replaced by a (k+1)-gon of which one edge is 1 and the others are all equal, leading to the stronger result [math]\displaystyle{ p_a \leq 1 - 1/k }[/math] when [math]\displaystyle{ a \geq 1/k, k\in\mathbb{Z}^+ \land k\gt 1 }[/math]. Further strengthening is achieved by using [math]\displaystyle{ 1/\sqrt{3} }[/math] as the long edge, given Lemma 12.

Lemma 18

Whenever [math]\displaystyle{ d\gt 0 }[/math], one has the inequalities

[math]\displaystyle{ |p_{\phi d} - p_d| \leq \frac{2}{5}, p_{\phi d} + p_d \geq \frac{1}{5}, 2p_d - p_{\phi d} \leq 1, 2 p_{\phi d} - p_d \leq 1 }[/math]

where [math]\displaystyle{ \phi := \frac{1+\sqrt{5}}{2} }[/math] is the golden ratio. Also we have

[math]\displaystyle{ p_{d/\sqrt{3}} \leq \frac{1}{3} + p_d, \frac{1}{2} + \frac{1}{2} p_d. }[/math]

Note that this generalises (9), as well as a special case of Lemma 12.

Proof Consider the regular pentagon with sidelength [math]\displaystyle{ d }[/math], so it also has 5 diagonals of length [math]\displaystyle{ \phi d }[/math]. Let [math]\displaystyle{ a \in \{0,1,2,3,4,5\} }[/math] denote the number of monochromatic edges and let [math]\displaystyle{ b \in \{0,1,2,3,4,5\} }[/math] denote the number of monochromatic diagonals. Observe:

• [math]\displaystyle{ a,b }[/math] cannot both be zero (pigeonhole principle).
• [math]\displaystyle{ a }[/math] cannot be 4. Similarly, [math]\displaystyle{ b }[/math] cannot be 4.
• If [math]\displaystyle{ a=5 }[/math], then [math]\displaystyle{ b=5 }[/math], and conversely.
• If [math]\displaystyle{ a=0 }[/math], then [math]\displaystyle{ b=1,2 }[/math]; similarly, if [math]\displaystyle{ b=0 }[/math], then [math]\displaystyle{ a=1,2 }[/math].

From this we observe the inequalities

[math]\displaystyle{ |\frac{a}{5}-\frac{b}{5}| \leq \frac{2}{5}; \frac{a}{5} + \frac{b}{5} \geq \frac{1}{5}; 2 \frac{a}{5} - \frac{b}{5} \leq 1; 2\frac{b}{5} - \frac{a}{5} \leq 1 }[/math]

and on taking expectations we obtain the first claim. Similarly, if one considers the colorings of an equilateral triangle of sidelength [math]\displaystyle{ d }[/math] together with its center, and counts the numbers [math]\displaystyle{ a,b \in \{0,1,2,3\} }[/math] of monochromatic edges of length [math]\displaystyle{ d }[/math] and [math]\displaystyle{ d/\sqrt{3} }[/math] respectively, one observes that one always has [math]\displaystyle{ \frac{b}{3} \leq \frac{1}{3} + \frac{2}{3} \frac{a}{3}, \frac{1}{2} + \frac{1}{2} \frac{a}{3} }[/math], and on taking expectations one obtains the claim.[math]\displaystyle{ \Box }[/math]

The hexagon [math]\displaystyle{ H }[/math] has essentially four distinct colorings: the coloring [math]\displaystyle{ \hbox{2tri} }[/math] with two triangles, the coloring [math]\displaystyle{ \hbox{1tri} }[/math] with one triangle, the coloring [math]\displaystyle{ \hbox{axisym} }[/math] that is symmetric around an axis, and the coloring [math]\displaystyle{ \hbox{centralsym} }[/math] that is symmetric around the central point. This gives four probabilities [math]\displaystyle{ p_{H = 2tri}, p_{H = 1tri}, p_{H = axisym}, p_{H = centralsym} }[/math] that sum to 1. By counting the number of monochromatic edges of length [math]\displaystyle{ \sqrt{3}, 2 }[/math] respectively, one also obtains the identities

[math]\displaystyle{ p_{\sqrt{3}} = p_{H = 2tri} + \frac{2}{3} p_{H = 1tri} + \frac{1}{3} p_{H = axisym}; \quad p_2 = \frac{1}{3} p_{H=axisym} + p_{H=centralsym} }[/math]

which reproves Lemma 15. Also

[math]\displaystyle{ {\bf P}( \mathbf{c}(0) = \mathbf{c}(e^{2\pi i/3}) = \mathbf{c}(e^{4\pi i/3}) ) = p_{H = 2tri} + \frac{1}{2} p_{H=1tri}. }[/math]

Any 4-coloring of L contains at least one triangle within one of its 52 copies of H, thus

[math]\displaystyle{ p_{H = 2tri} + \frac{1}{2} p_{H=1tri} \geq \frac{1}{52} }[/math]

which reproves Corollary 4.

Lemma 19

(Hubai) One has [math]\displaystyle{ p_{H = 1tri} + p_{H = axisym} \geq \frac{1}{10} }[/math].

Proof Consider five copies of H centred at 0,1,2,3,4. With probability at least [math]\displaystyle{ 1 - 5( p_{H = 1tri} + p_{H = axisym} ) }[/math], none of these copies of H are colored 1tri or axisym, and so must be colored 2tri or centralsym. One can check then that if one of the copies is colored 2tri, then so is any adjacent copy; thus all five copies are colored 2tri, or all five are colored centralsym. In either case we see that -1 and 5 are colored the same color. Comparing with Lemma 2 then gives the claim. [math]\displaystyle{ \Box }[/math]

Theorem 20

One has [math]\displaystyle{ p_{H = 1tri} \gt 0 }[/math].

Proof Suppose for contradiction that [math]\displaystyle{ p_{H = 1tri} = 0 }[/math]. One can then run a version of the de Bruijn-Erdos argument to obtain a coloring in which 1tri hexagons are completely nonexistent (since there are arbitrarily large finite colorings with this property). Consider the triangular lattice [math]\displaystyle{ {\bf Z}[e^{\pi i/3}] }[/math]. We 2-color the edges of this lattice by coloring an edge black if it is the short diagonal of a unit rhombus with monochromatic long diagonal, and white otherwise. The four colorings of hexagons lead to four possible colorings at each vertex:

• If H is colored 2tri, then all six edges to the centre of H are black.
• If H is colored 1tri, then two edges to the centre of H at 120 degree angles are white, the other four are black.
• If H is colored axisym, then two opposing edges of the centre of H are black, the other four are white.
• If H is colored centralsym, then all six edges to the centre of H are black.

In particular, as we are assuming no 1tri hexagons, the faces cut out by the black edges have angles 60 degrees, and thus must be equilateral triangles, sectors of angle 60, half-planes, or the entire plane. If there is at least one equilateral triangle, then the rest of the black edges must form an equilateral lattice with that triangle sidelength. This leads to only a small number of possible hexagon colorings in the lattice:

1. Case 1: All edges white.
2. Case 2: All edges black.
3. Case 3.k: For some natural number [math]\displaystyle{ k \geq 2 }[/math], the length k edges joining adjacent vertices in some coset of [math]\displaystyle{ k \cdot {\mathbf Z}[ e^{\pi i/3} ] }[/math] are all black, and the remaining edges are white.
4. Case 4: Each horizontal row consists either entirely of black edges, or entirely of white edges.
5. Case 5: Each northwest row consists either entirely of black edges, or entirely of white edges.
6. Case 6: Each northeast row consists either entirely of black edges, or entirely of white edges.
7. Case 7: Six rays of black edges meeting at a common vertex; all other edges white.

Technically, Case 1 is contained in Cases 4,5,6 as written above, but this will not be an issue. One can view Case 7 as a limiting case [math]\displaystyle{ k=\infty }[/math] of Case 3.k; Case 2 is similarly the opposite limiting case [math]\displaystyle{ k=1 }[/math].

In the first case, the coloring is periodic with periods [math]\displaystyle{ 2, 2 e^{\pi i/3} }[/math]. In the second case, it is periodic with periods [math]\displaystyle{ 3, 3 e^{\pi i/3} }[/math]. In the third case, it is periodic with periods [math]\displaystyle{ 3k, 3k e^{\pi i/3} }[/math]. Also note that for each k, one can check if Case 3.k holds by inspecting the coloring at a finite number of vertices. Thus the event that Case 3.k holds is "measurable" in the sense that a meaningful probability can be assigned. (But Cases 1,2,4,5,6 are not measurable events, they require an infinite number of points to be inspected, and the probability measure we are using is only finitely additive rather than infinitely additive.) In Case 4, the coloring is periodic with period 2; also, every coset of [math]\displaystyle{ 2 \cdot {\bf Z}[e^{\pi i/3}] }[/math] is 2-colored. Similarly for Case 5 and 6 (where the periods are [math]\displaystyle{ 2 e^{2\pi i/3} }[/math] and [math]\displaystyle{ 2 e^{4\pi i/3} }[/math] respectively.)

Let [math]\displaystyle{ \alpha_k }[/math] be the probability that Case 3.k holds for the given value of [math]\displaystyle{ k }[/math]. Then [math]\displaystyle{ \sum_{k=2}^K \alpha_k \leq 1 }[/math] for any k, hence [math]\displaystyle{ \sum_{k=2}^\infty \alpha_k \leq 1 }[/math]. In particular, we can find [math]\displaystyle{ K_1 }[/math] such that [math]\displaystyle{ \sum_{k={K_1}}^\infty \alpha_k \leq 0.1 }[/math] (say). Let [math]\displaystyle{ P }[/math] be six times the least common multiple of [math]\displaystyle{ 1,2,\dots,K_1 }[/math]. Then the coloring is P- and [math]\displaystyle{ P e^{\pi i/3} }[/math]-periodic for Case 1, Case 2, and all Case 3.k with [math]\displaystyle{ k \leq K_1 }[/math]. On the other hand, if [math]\displaystyle{ K_2 }[/math] is sufficiently large depending on [math]\displaystyle{ P }[/math], and Case 3.k holds for some [math]\displaystyle{ k \geq K_2 }[/math], then almost all of the hexagons are colored centralsym, which makes the coloring "almost [math]\displaystyle{ P, P e^{\pi i/3} }[/math]-periodic" in the sense that

[math]\displaystyle{ {\bf c}(z+P e^{\pi i j/3}) = {\bf c}(z) \hbox{ for } j=0,1,2,3,4,5 }[/math]

will hold for at least [math]\displaystyle{ 0.9 }[/math] of the lattice points [math]\displaystyle{ z \in {\bf Z}[e^{\pi i/3}] }[/math] with [math]\displaystyle{ |z| \leq K_2 }[/math]. Similarly for Case 7 (which is sort of a [math]\displaystyle{ k=\infty }[/math] limiting case of Case 3.k.) Thus, with the probability [math]\displaystyle{ \geq 1 - \sum_{k=K_1}^{K_2} \alpha_k \geq 0.9 }[/math], the coloring of the seven vertices [math]\displaystyle{ {\bf c}(0), {\bf c}(P e^{\pi ij/3}, j=1,\dots,6 }[/math] is (up to rotation and recoloring) one of the three patterns of the central and linking vertices in Figure 3 of Aubrey's paper, namely

• [math]\displaystyle{ {\bf c}(0) = {\bf c}(P) = {\bf c}(P e^{\pi i/3}) = {\bf c}(P e^{2\pi i/3}) = {\bf c}(P e^{3\pi i/3}) = {\bf c}(P e^{4\pi i/3}) = {\bf c}(P e^{5\pi i/3}) }[/math];
• [math]\displaystyle{ {\bf c}(0) = {\bf c}(P') = {\bf c}(P' e^{3\pi i/3}) }[/math]; [math]\displaystyle{ {\bf c}(P' e^{\pi i/3}) = {\bf c}(P' e^{2\pi i/3}) = {\bf c}(P' e^{4\pi i/3}) = {\bf c}(P' e^{5\pi i/3}) }[/math] for some [math]\displaystyle{ P' = P e^{\pi i j/3} }[/math], [math]\displaystyle{ j=1,\dots,6 }[/math];
• [math]\displaystyle{ {\bf c}(0) = {\bf c}(P') = {\bf c}(P' e^{\pi i/3}) = {\bf c}(P' e^{2\pi i/3}) = {\bf c}(P' e^{3\pi i/3}) }[/math]; [math]\displaystyle{ {\bf c}(P' e^{4\pi i/3}) = {\bf c}(P' e^{5\pi i/3}) }[/math] for some [math]\displaystyle{ P' = P e^{\pi i j/3} }[/math], [math]\displaystyle{ j=1,\dots,6 }[/math].

Using the spindling argument from Aubrey's paper, we conclude that the third possibility must in fact hold with probability at least 0.8; on the other hand, from Lemma 2 this scenario can only occur with probability at most 1/2, giving the required contradiction. [math]\displaystyle{ \Box }[/math]

One should be able to refine this argument to show that [math]\displaystyle{ p_{H = 1tri} \gt c }[/math] for an absolute constant [math]\displaystyle{ c\gt 0 }[/math].

Lemma 21

Providing a tighter bound for Lemma 17 with a more thorough proof: If [math]\displaystyle{ a,b,c \gt 0 }[/math] are the lengths of a triangle, then [math]\displaystyle{ {\bf P}\left(\mathbf{c}(a)\neq \mathbf{c}(0)\neq \mathbf{c}\left(b\exp\left(i\arccos\left(\frac{a^b+b^2-c^2}{2ab}\right)\right)\right) \right) + p_a + p_b \leq 1 + p_c }[/math].

Proof Consider a triangle of side lengths [math]\displaystyle{ a,b,c }[/math]. Let [math]\displaystyle{ \left|z_2\right|=b,\left|a-z_2\right|=c }[/math]. If the c side is not monochromatic, then at least one of the other two sides must fail to be monochromatic also: [math]\displaystyle{ \mathbf{c}(a)\neq\mathbf{c}(z_2)\Rightarrow[\mathbf{c}(a)\neq\mathbf{c}(0)\lor\mathbf{c}(0)\neq\mathbf{c}(z_2)] }[/math]. [math]\displaystyle{ [A\Rightarrow B]\Rightarrow {\bf P}(A)\leq{\bf P}(B) }[/math] thus

[math]\displaystyle{ {\bf P}(\mathbf{c}(a)\neq\mathbf{c}(0)\lor\mathbf{c}(0)\neq\mathbf{c}(z_2)) \geq {\bf P}(\mathbf{c}(a) \neq \mathbf{c}(z_2)) = 1-p_c }[/math]

[math]\displaystyle{ {\bf P}(A\lor B) +{\bf P}(A\land B)={\bf P}(A)+{\bf P}(B) }[/math], so

[math]\displaystyle{ {\bf P}(\mathbf{c}(a)\neq\mathbf{c}(0)\lor\mathbf{c}(0)\neq\mathbf{c}(z_2)) = {\bf P}(\mathbf{c}(a)\neq\mathbf{c}(0)) + {\bf P}(\mathbf{c}(0)\neq\mathbf{c}(z_2)) - {\bf P}(\mathbf{c}(a)\neq\mathbf{c}(0)\neq\mathbf{c}(z_2)) }[/math]

[math]\displaystyle{ {\bf P}(\mathbf{c}(a)\neq\mathbf{c}(0)\lor\mathbf{c}(0)\neq\mathbf{c}(z_2)) = 2 - p_a - p_b - {\bf P}(\mathbf{c}(a)\neq\mathbf{c}(0)\neq\mathbf{c}(z_2)) }[/math]

[math]\displaystyle{ 1-p_c \leq 2 - p_a - p_b - {\bf P}(\mathbf{c}(a)\neq\mathbf{c}(0)\neq\mathbf{c}(z_2)) }[/math]

Using the law of cosines: [math]\displaystyle{ z_2=b\exp\left(i\arccos\left(\frac{a^b+b^2-c^2}{2ab}\right)\right) }[/math]

[math]\displaystyle{ {\bf P}\left(\mathbf{c}(a)\neq \mathbf{c}(0)\neq \mathbf{c}\left(b\exp\left(i\arccos\left(\frac{a^b+b^2-c^2}{2ab}\right)\right)\right) \right) + p_a + p_b \leq 1 + p_c }[/math] [math]\displaystyle{ \Box }[/math]

Lemma 22

One has [math]\displaystyle{ 3 p_{1/\sqrt{3}} \geq {\bf P}( \mathbf{c}(1) = \mathbf{c}(e^{2\pi i/3}) = \mathbf{c}(e^{4\pi i/3}) ) }[/math].

Proof Let [math]\displaystyle{ z }[/math] be a complex number of magnitude [math]\displaystyle{ 1/\sqrt{3} }[/math] that is a unit distance from 1. If [math]\displaystyle{ \mathbf{c}(1) = \mathbf{c}(e^{2\pi i/3}) = \mathbf{c}(e^{4\pi i/3}) = c }[/math] (say), then [math]\displaystyle{ 0, z, e^{2\pi i/3} z, e^{4\pi i/3} z }[/math] cannot be colored with [math]\displaystyle{ c }[/math]; also, [math]\displaystyle{ z, e^{2\pi i/3} z, e^{4\pi i/3} z }[/math] are the vertices of a unit equilateral triangle and thus must take on three different colors. By the pigeonhole principle, one of [math]\displaystyle{ 0, z, e^{2\pi i/3} z, e^{4\pi i/3} z }[/math] must then take the same color as the origin, and the claim follows. [math]\displaystyle{ \Box }[/math]

Lemma 23

One has [math]\displaystyle{ 4 p_{(\sqrt{6} \pm \sqrt{2})/2} + p_{\sqrt{2}} \geq 1 }[/math]. In particular, by Lemma 2, [math]\displaystyle{ p_{(\sqrt{6}+\sqrt{2})/2} \geq 1/8 }[/math].

Proof [ExIs2018b] We just prove the claim for the + sign (the - sign can then be obtained after applying the Galois conjugacy that maps [math]\displaystyle{ \sqrt{3} }[/math] to [math]\displaystyle{ -\sqrt{3} }[/math], leaving [math]\displaystyle{ \sqrt{2} }[/math] unchanged). Set [math]\displaystyle{ d := \frac{\sqrt{6}+\sqrt{2}}{2} }[/math], and consider the five vertices

[math]\displaystyle{ 0, e^{5\pi i/4}, e^{5\pi i/4} + d, e^{5\pi i/4} + e^{\pi i/3} d, e^{5\pi i/4} + (e^{\pi i/3}-i)d. }[/math]

One can check that of the ten edges determined by these five vertices, five have unit length, four have length d, and the remaining distance (from 0 to [math]\displaystyle{ e^{5\pi i/4}+d }[/math]) has distance [math]\displaystyle{ \sqrt{2} }[/math]. Since [math]\displaystyle{ \mathbf{c} }[/math] must make one of the latter five edges monochromatic, the claim follows. [math]\displaystyle{ \Box }[/math]

Lemma 24

One has [math]\displaystyle{ p_{\sqrt{2}} \geq \frac{1}{14} }[/math].

Proof In page 7 of [ExIs2018b], a non-4-colorable graph of 13 vertices with 20 unit distance edges and 14 edges of length [math]\displaystyle{ \sqrt{2} }[/math] is constructed. The coloring [math]\displaystyle{ \mathbf{c} }[/math] must make one of the 14 latter edges monochromatic, and the claim follows. [math]\displaystyle{ \Box }[/math]

Lemma 25

Let [math]\displaystyle{ d = \frac{1}{2} \sqrt{3^{1/4} \cdot 2 \sqrt{2} + 2 \sqrt{3} + 2} }[/math] and [math]\displaystyle{ e = \frac{3^{1/4} \sqrt{2} + \sqrt{3} - 1}{2} }[/math]. Then one has [math]\displaystyle{ 14 p_d + p_e \geq 1 }[/math]. In particular, by Lemma 2, [math]\displaystyle{ p_d \geq 1/28 }[/math].

Proof In page 9 of [ExIs2018b], a non-4-colorable graph of 13 vertices with 19 unit edges, 14 edges of length d, and one edge of length e is constructed. The coloring [math]\displaystyle{ \mathbf{c} }[/math] must make one of the 15 latter edges monochromatic, and the claim follows. [math]\displaystyle{ \Box }[/math]

Lemma 26

Let [math]\displaystyle{ d = \sqrt{3/2 + \sqrt{33}/6} }[/math]. Then [math]\displaystyle{ 7 p_d \geq p_{1/\sqrt{3}} }[/math]. In particular, by Corollary 16, [math]\displaystyle{ p_d \geq \frac{1}{196} }[/math].

Proof In page 11 of [ExIs2018b], a graph of nine vertices consisting of 12 unit edges and 7 edges of length d is constructed with the property that any 4-coloring of this graph cannot have two specific vertices A,B (which are distance [math]\displaystyle{ 1/\sqrt{3} }[/math] apart) monochromatic. Thus, [math]\displaystyle{ \mathbf{c} }[/math] can only make the AB edge monochromatic if one of the seven length d edges is monochromatic. The claim follows. [math]\displaystyle{ \Box }[/math]

Lemma 27

One has [math]\displaystyle{ 27 p_{\sqrt{5/3}} \geq p_{1/\sqrt{3}} }[/math]. In particular, by Corollary 16, [math]\displaystyle{ p_{\sqrt{5/3}} \geq \frac{1}{756} }[/math].

Proof In page 13 of [ExIs2018], a graph of 33 vertices with some unit edges and 27 edges of length [math]\displaystyle{ \sqrt{5/3} }[/math] is contructed with the property that any 4-coloring of this graph cannot have two specific vertices A,B (which are distance [math]\displaystyle{ 1/\sqrt{3} }[/math] apart) monochromatic. Now repeat the proof of Lemma 26. [math]\displaystyle{ \Box }[/math]

Computer-verified claim 28

One has [math]\displaystyle{ p_{2/\sqrt{3}} \geq \frac{1}{177} }[/math].

Proof In page 15 of [ExIs2018], a 5-chromatic graph of 103 vertices, 312 unit edges, and 177 edges of length [math]\displaystyle{ 2/\sqrt{3} }[/math] is constructed. [math]\displaystyle{ \mathbf{c} }[/math] must make one of the latter edges monochromatic, giving the claim. [math]\displaystyle{ \Box }[/math]

Lemma 29

One has [math]\displaystyle{ p_{(\sqrt{6} \pm \sqrt{2})/2} \geq 1/6 }[/math] (this improves the bound in Lemma 23).

Proof Use graphs 505 and 507 from [S2004] and the spindle bound. [math]\displaystyle{ \Box }[/math]

Lemma 30

For [math]\displaystyle{ m \gt n }[/math] and an [math]\displaystyle{ n }[/math]-coloring of the complex plane, [math]\displaystyle{ \sum_{k=1}^m\sum_{j=k+1}^m{\bf P}\left(\mathbf{c}(z_k) = \mathbf{c}(z_j) \right) \geq 1 }[/math].

Proof [math]\displaystyle{ n }[/math] colors and [math]\displaystyle{ m }[/math] points necessitates at least 2 having equal color. I.e.

[math]\displaystyle{ {\bf P}\left(\bigvee_{k=0}^n \bigvee_{j=k+1}^n\ \mathbf{c}(z_k) = \mathbf{c}(z_j)\right) = 1 }[/math]

The lemma then follows immediately from the fact:

[math]\displaystyle{ {\bf P}\left(\bigcup_{k} E_k\right) \leq \sum_{k} {\bf P}\left(E_k\right) \,\Box }[/math]

Corollary 31

Let [math]\displaystyle{ \lvert z_k\rvert=1 }[/math]. Then for [math]\displaystyle{ m \geq n }[/math] and an [math]\displaystyle{ n }[/math]-coloring of the complex plane, [math]\displaystyle{ \sum_{k=1}^m\sum_{j=k+1}^m{\bf P}\left(\mathbf{c}(z_k) = \mathbf{c}(z_j) \right) \geq 1 }[/math].

Proof Use lemma 30 on the set [math]\displaystyle{ \left\{z_k \bigg\vert 1\leq k\leq m \land k\in\mathbb{Z}\right\}\cup\{0\} }[/math]. Simplify using [math]\displaystyle{ {\bf P}\left(\mathbf{c}(z_k) = \mathbf{c}(0) \right)=0 }[/math]. [math]\displaystyle{ \Box }[/math]

Lemma 32

For [math]\displaystyle{ x\in\mathbb{R} }[/math] and an [math]\displaystyle{ n }[/math]-coloring of the plane, [math]\displaystyle{ \sum_{k=1}^{n-1}\left(n-k\right){\bf P}\left(\mathbf{c}\left(0\right) = \mathbf{c}\left( 2\sin\left(\frac{kx}{2}\right) \right) \right) \geq 1 }[/math].

Proof Use corollary 31 on the set [math]\displaystyle{ \left\{e^{ikx} \bigg\vert 0\leq k \lt n \land k\in\mathbb{Z}\right\} }[/math]. and simplify by grouping lengths. [math]\displaystyle{ \Box }[/math]

Corollary 33

Interesting(easy to simplify results of) values for [math]\displaystyle{ x }[/math] in Lemma 32 are in [math]\displaystyle{ \left\{x \bigg\vert \sin\left(\frac{kx}{2}\right)=1 \land 1\leq k \lt n \land k\in\mathbb{Z}\right\} }[/math]. For 4-colorings, this gives

[math]\displaystyle{ 2p_{\sqrt 3}+p_2 \geq 1 }[/math]

[math]\displaystyle{ 3p_{(\sqrt 3-1)/\sqrt 2}+p_{\sqrt 2} \geq 1 }[/math]

[math]\displaystyle{ 3p_{2\sin(\pi/18)}+2p_{2\sin(\pi/9)} \geq 1 }[/math]

Lemma 34

Generalizing the note of Lemma 17, [math]\displaystyle{ \lvert d_1\rvert= d_1 \gt \lvert d_0\rvert= d_0\Rightarrow (1-p_{d_1})\leq \left\lceil\frac{d_1}{d_0}\right\rceil(1-p_{d_0}) }[/math]

Proof let [math]\displaystyle{ \lvert z_{j+1} -z_j\rvert=d_0 \gt 0, \lvert z_{j+n} -z_0\rvert=d_1\gt 0 }[/math].

Base case, [math]\displaystyle{ n=2 }[/math], by Lemma 17 using the [math]\displaystyle{ \left(z_n-z_0,z_n-z_{n-1},z_{n-1}-z_0\right) }[/math] triangle:

[math]\displaystyle{ 2d_0\geq d_1\Rightarrow 2p_{d_0}\leq 1+p_{d_1} }[/math]

The inductive step is Lemma 17 using the [math]\displaystyle{ \left(z_n-z_0,z_n-z_{n-1},z_{n-1}-z_0\right) }[/math] triangle. After induction:

[math]\displaystyle{ [n\geq 2\land nd_0\geq d_1]\Rightarrow np_{d_0}\leq n-1+p_{d_1} }[/math]

Substitute [math]\displaystyle{ n=\left\lceil\frac{d_1}{d_0}\right\rceil }[/math], simplify, rearrange:

[math]\displaystyle{ d_1 \gt d_0\Rightarrow (1-p_{d_1})\leq \left\lceil\frac{d_1}{d_0}\right\rceil(1-p_{d_0}) }[/math]

[math]\displaystyle{ \Box }[/math]

Proposition 35

If [math]\displaystyle{ d \gt 1/\sqrt{2} }[/math] obeys the inequalities

[math]\displaystyle{ \sin( 2 \mathrm{arcsin} \frac{1}{2d} ) \geq \frac{1}{4d} }[/math]

and

[math]\displaystyle{ \cos( 2 \mathrm{arcsin} \frac{1}{2d} ) \geq \frac{1}{4d} }[/math]

then

[math]\displaystyle{ p_d \leq \frac{1}{2} - \frac{1}{188}. }[/math]

(One can check that the conditions are obeyed precisely when [math]\displaystyle{ d \geq \frac{\sqrt{33}-1}{8} = 0.84307\dots }[/math].)

Proof Write [math]\displaystyle{ p_d = \frac{1}{2}-\delta }[/math]. Let [math]\displaystyle{ ABC }[/math] be any isosceles triangle of sidelengths [math]\displaystyle{ |AB|=|AC|=d, |BC|=1 }[/math]; this subtends an acute angle of [math]\displaystyle{ 2\mathrm{arcsin} \frac{1}{2d} }[/math] at A. Then AB and AC are each individually monochromatic with probability [math]\displaystyle{ \frac{1}{2}-\delta }[/math], but cannot both be monochromatic. Thus, the probability that [math]\displaystyle{ AB }[/math], [math]\displaystyle{ AC }[/math] are both not monochromatic is at most [math]\displaystyle{ 2\delta }[/math].

Now let [math]\displaystyle{ ABCD }[/math] be a quadrilateral with [math]\displaystyle{ |AB|=|AC|=|AD|=d, |BC|=|CD|=1 }[/math], so [math]\displaystyle{ \angle BAD = 4 \mathrm{arcsin} \frac{1}{2d} }[/math]. If [math]\displaystyle{ AB }[/math] is monochromatic, then [math]\displaystyle{ AC }[/math] is not monochromatic, and thus by the previous paragraph [math]\displaystyle{ AD }[/math] is monochromatic outside of an event of probability at most [math]\displaystyle{ 2\delta }[/math]. Since [math]\displaystyle{ AB }[/math] is monochromatic with probability [math]\displaystyle{ \frac{1}{2}-\delta }[/math], we conclude that the triangle [math]\displaystyle{ ABD }[/math] is monochromatic with probability at least [math]\displaystyle{ \frac{1}{2}-3\delta }[/math].

Now let [math]\displaystyle{ BADE }[/math] be a rhombus with sidelengths d and [math]\displaystyle{ \angle BAD = 4 \mathrm{arcsin} \frac{1}{2d} }[/math]. By the hypotheses, the diagonals BD, AE of this rhombus have length at least 1/2, and hence are monochromatic with probability at most 1/2 by Lemma 2. As above, ABD and BDE are each monochromatic with probability at least [math]\displaystyle{ \frac{1}{2}-3\delta }[/math]. As BD is monochromatic with probability at most [math]\displaystyle{ 1/2 }[/math], we conclude that BADE is monochormatic with probability at least [math]\displaystyle{ \frac{1}{2}-6\delta }[/math].

Now let [math]\displaystyle{ EDFG }[/math] be another rhombus congruent to [math]\displaystyle{ BADE }[/math]. As BD, AE have length at least 1/2, at least one of the long diagonals BF, AG have length at least 1/2 (the diagonal opposite an obtuse or right-angled triangle will work). Let's say BF has length at least 1/2. As BADE and EDFG are both monochromatic with probability at least [math]\displaystyle{ \frac{1}{2}-6\delta }[/math], and the common edge DE is monochromatic with probability [math]\displaystyle{ \frac{1}{2}-\delta }[/math], we conclude that the entire configuration ABDEFG is monochromatic with probability at least [math]\displaystyle{ \frac{1}{2}-11\delta }[/math]. In particular the pentagon ABDEF is monochromatic with at least this probability. However, in this pentagon, the five edges BA, AD, DE, EB, EF are monochromatic with probability at most [math]\displaystyle{ \frac{1}{2}-\delta }[/math], and the other five edges are monochromatic with probability at most [math]\displaystyle{ \frac{1}{2} }[/math] by Lemma 2. Thus the probability that at least one of the edges of this pentagon is monochromatic is at most [math]\displaystyle{ (\frac{1}{2}-11\delta) + 5 \times 10\delta + 5 \times 11\delta = \frac{1}{2}+94\delta }[/math]. On the other hand, by the pigeonhole principle, this probability is 1. The claim follows. [math]\displaystyle{ \Box }[/math]

Proposition 36

If [math]\displaystyle{ d \ge \frac{2}{\sqrt{15}} = 0.5163\dots }[/math], then

[math]\displaystyle{ p_d \leq \frac{1}{2} - \frac{1}{62}. }[/math]

Proof Write [math]\displaystyle{ p_d = \frac{1}{2}-\delta }[/math]. Let [math]\displaystyle{ ABC }[/math] be any isosceles triangle of sidelengths [math]\displaystyle{ |AB|=|AC|=d, |BC|=1 }[/math]; this subtends an acute angle of [math]\displaystyle{ 2\mathrm{arcsin} \frac{1}{2d} }[/math] at A. Then AB and AC are each individually monochromatic with probability [math]\displaystyle{ \frac{1}{2}-\delta }[/math], but cannot both be monochromatic. Thus, the probability that [math]\displaystyle{ AB }[/math], [math]\displaystyle{ AC }[/math] are both not monochromatic is at most [math]\displaystyle{ 2\delta }[/math].

Now let [math]\displaystyle{ ABCD }[/math] be a quadrilateral with [math]\displaystyle{ |AB|=|AC|=|AD|=d, |BC|=|CD|=1 }[/math], so [math]\displaystyle{ \angle BAD = 4 \mathrm{arcsin} \frac{1}{2d} }[/math]. A simple calculation shows that if [math]\displaystyle{ d \ge \frac{2}{\sqrt{15}} }[/math], then [math]\displaystyle{ |BD| \ge \frac{1}{2} }[/math]. If [math]\displaystyle{ AB }[/math] is monochromatic, then [math]\displaystyle{ AC }[/math] is not monochromatic, and thus by the previous paragraph [math]\displaystyle{ AD }[/math] is monochromatic outside of an event of probability at most [math]\displaystyle{ 2\delta }[/math]. By inclusion-exclusion, we conclude that outside of the event that [math]\displaystyle{ AB }[/math] is monochromatic, the probability that [math]\displaystyle{ AD }[/math] is monochromatic is at most [math]\displaystyle{ 2\delta }[/math].

Now let [math]\displaystyle{ ADE }[/math] the [math]\displaystyle{ 180^\circ }[/math] rotation of [math]\displaystyle{ ADB }[/math] around the midpoint of [math]\displaystyle{ AD }[/math], and let [math]\displaystyle{ FDE }[/math] be the [math]\displaystyle{ 180^\circ }[/math] rotation of [math]\displaystyle{ ADE }[/math] around the midpoint of [math]\displaystyle{ DE }[/math]. By the hypotheses, the line segments [math]\displaystyle{ AE, BD, BE, BF, DF }[/math] all have length at least 1/2. Let [math]\displaystyle{ {\mathcal E} }[/math] be the event that at least one of [math]\displaystyle{ AB, AD, DE, EF }[/math] is monochromatic. By the previous paragraph, this event occurs with probability at most [math]\displaystyle{ \frac{1}{2}-\delta+2\delta+2\delta+2\delta = \frac{1}{2}+5\delta }[/math].

By previous considerations, [math]\displaystyle{ ABD }[/math] is monochromatic with probability at least [math]\displaystyle{ \frac{1}{2}-3\delta }[/math], and this event lies in [math]\displaystyle{ {\mathcal E} }[/math]. On the other hand, [math]\displaystyle{ BD }[/math] is monochromatic with probability at most 1/2 by Lemma 2. We conclude that outside of [math]\displaystyle{ {\mathcal E} }[/math], [math]\displaystyle{ BD }[/math] is only monochromatic with probability at most [math]\displaystyle{ 3\delta }[/math]. A similar argument (replacing [math]\displaystyle{ ABD }[/math] by [math]\displaystyle{ DAE }[/math] or [math]\displaystyle{ EDF }[/math]) shows that outside of [math]\displaystyle{ {\mathcal E} }[/math], [math]\displaystyle{ AE }[/math] is monochromatic with probability at most [math]\displaystyle{ 3\delta }[/math], and similarly for [math]\displaystyle{ DF }[/math]. Now we consider [math]\displaystyle{ EB }[/math]. By previous considerations, the probability that [math]\displaystyle{ ABDE }[/math] is monochromatic is at least [math]\displaystyle{ \frac{1}{2}-5\delta }[/math], and this event lies inside [math]\displaystyle{ {\mathcal E} }[/math]. Thus, outside of [math]\displaystyle{ {\mathcal E} }[/math], the probability that [math]\displaystyle{ EB }[/math] is monochromatic is at most [math]\displaystyle{ 5\delta }[/math]; similarly for [math]\displaystyle{ AF }[/math]. Finally, the probability that [math]\displaystyle{ BF }[/math] is monochromatic outside of [math]\displaystyle{ {\mathcal E} }[/math] is at most [math]\displaystyle{ 7\delta }[/math]. We conclude that outside of an event of probability

[math]\displaystyle{ \frac{1}{2}+5\delta + 3\delta+3\delta+3\delta+5\delta+5\delta+7\delta = \frac{1}{2} + 31\delta, }[/math]

none of the ten edges connecting [math]\displaystyle{ A,B,D,E,F }[/math] are monochromatic. But by the pigeonhole principle, this cannot occur in a 4-coloring, hence [math]\displaystyle{ \frac{1}{2} + 31 \delta \geq 1 }[/math], and the claim follows. [math]\displaystyle{ \Box }[/math]

Note: it may be possible to sharpen this bound by an iterative argument, by feeding the bounds obtained by this argument back into the place in the proof where Lemma 2 is currently invoked.

Note 2: If we obtain [math]\displaystyle{ F }[/math] by reflecting [math]\displaystyle{ B }[/math] to [math]\displaystyle{ AD }[/math], then we win [math]\displaystyle{ 2\delta }[/math] in the last step. But to invoke Lemma 2, we need (among other things) that [math]\displaystyle{ EF }[/math] is at least 1/2 - this is true if [math]\displaystyle{ d }[/math] is large enough.

Lemma 37

One has [math]\displaystyle{ \sup_{0 \lt d \lt 2} p_d \geq 1/3 }[/math].

Proof For a large integer [math]\displaystyle{ n }[/math], consider the points [math]\displaystyle{ e^{2\pi i j/n} }[/math] with [math]\displaystyle{ j=1,\dots,n }[/math]. Any unit distance coloring will color these points in at most colors, hence divides the n points into three color classes of some size [math]\displaystyle{ n_1,n_2,n_3 }[/math]. The number of monochromatic pairs is then

[math]\displaystyle{ \frac{n_1(n_1-1)}{2} + \frac{n_2(n_2-1)}{2} + \frac{n_3(n_3-1)}{2} = \frac{1}{2} (n_1^2+n_2^2+n_3^2) + O(n) \geq \frac{1}{6} n^2 + O(n) }[/math]

by Cauchy-Schwarz. Thus at least [math]\displaystyle{ 1/3-O(1/n) }[/math] of the pairs are monochromatic. Taking expectations and using the pigeonhole principle, we conclude that one of the distances has a probability at least [math]\displaystyle{ 1/3 -O(1/n) }[/math] of being monochromatic, giving the claim. [math]\displaystyle{ \Box\lt math\gt == Simplification rules for triplets of points in the complex plane == Deduced from the rule \lt math\gt {\bf P}(A\land B)+{\bf P}(A\land \lnot B)={\bf P}(A) }[/math].

[math]\displaystyle{ {\bf P}( {\mathbf c}(z_0) = {\mathbf c}(z_1) = {\mathbf c}(z_2) ) + {\bf P}( {\mathbf c}(z_0) = {\mathbf c}(z_1) \neq {\mathbf c}(z_2) ) = {\bf P}( {\mathbf c}(z_0) = {\mathbf c}(z_1) ) }[/math]

[math]\displaystyle{ {\bf P}( {\mathbf c}(z_0) \neq {\mathbf c}(z_1) \neq {\mathbf c}(z_2) ) + {\bf P}( {\mathbf c}(z_0) \neq {\mathbf c}(z_1) = {\mathbf c}(z_2) ) = {\bf P}( {\mathbf c}(z_0) \neq {\mathbf c}(z_1) ) }[/math]

[math]\displaystyle{ {\bf P}( {\mathbf c}(z_0) = {\mathbf c}(z_1) = {\mathbf c}(z_2) ) - {\bf P}( {\mathbf c}(z_0) \neq {\mathbf c}(z_1) \neq {\mathbf c}(z_2) ) = {\bf P}( {\mathbf c}(z_0) = {\mathbf c}(z_1) ) - {\bf P}( {\mathbf c}(z_1) \neq {\mathbf c}(z_2) ) }[/math]

[math]\displaystyle{ {\bf P}( {\mathbf c}(z_0) \neq {\mathbf c}(z_1) \neq {\mathbf c}(z_2) \neq {\mathbf c}(z_0) ) + {\bf P}( {\mathbf c}(z_1) \neq {\mathbf c}(z_2) = {\mathbf c}(z_0) ) = {\bf P}( {\mathbf c}(z_0) \neq {\mathbf c}(z_1) \neq {\mathbf c}(z_2) ) }[/math]

Proofs of bounds for conditional probabilities

The trivial case, valid where [math]\displaystyle{ \left|d\right|\neq 1 }[/math]:

[math]\displaystyle{ x\in\mathbb{R}\Rightarrow{\bf P}( {\mathbf c}(0) = {\mathbf c}(d+e^{ix}) \mid {\mathbf c}(0) = {\mathbf c}(d) )=0 }[/math]

Trivial plus Baye's Theorem, valid where [math]\displaystyle{ d\neq 0 }[/math]:

[math]\displaystyle{ x\in\mathbb{R}\Rightarrow{\bf P}( {\mathbf c}(0) = {\mathbf c}(d+e^{ix}) \mid {\mathbf c}(0) \neq {\mathbf c}(d) )=\frac{{\bf P}( {\mathbf c}(0) = {\mathbf c}(d+e^{ix}) )}{1-{\bf P}( {\mathbf c}(0) = {\mathbf c}(d) )}\leq 1 }[/math]

Rearrange:

[math]\displaystyle{ {\bf P}( {\mathbf c}(0) = {\mathbf c}(d+e^{ix}) )+{\bf P}( {\mathbf c}(0) = {\mathbf c}(d) )\leq 1 }[/math]

Spindle method: for [math]\displaystyle{ \left|d\right|=d\geq 1/2 }[/math] and [math]\displaystyle{ \theta=2\text{arcsin}\left(\frac{1}{2d}\right) }[/math]:

[math]\displaystyle{ {\bf P}( {\mathbf c}(0) = {\mathbf c}(d+e^{i\theta}) \mid {\mathbf c}(0) \neq {\mathbf c}(d) ) = \frac{1}{1-{\bf P}( {\mathbf c}(0) = {\mathbf c}(d) )} - 1\leq 1 }[/math]

which is another way to see [math]\displaystyle{ \left|d\right|=d\geq 1/2\Rightarrow{\bf P}( {\mathbf c}(0) = {\mathbf c}(d) )\leq 1/2 }[/math].

Further questions

• For [math]\displaystyle{ n,m\geq CNP }[/math], what consistent relationships exist between [math]\displaystyle{ {\bf P}\left(\mathbf{c}(0)=\mathbf{c}(d)\bigg\vert n\text{ colors}\right) }[/math] and [math]\displaystyle{ {\bf P}\left(\mathbf{c}(0)=\mathbf{c}(d)\bigg\vert m\text{ colors}\right) }[/math]? How can these relationships be used to sharpen arguments of the probabilistic formulation?