Probabilistic formulation of Hadwiger-Nelson problem

Suppose 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 {\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]

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].

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). [math]\displaystyle{ \Box }[/math]

C}</math>