## A minimal periodic coloring theorem, part 2

As mentioned previously, for $n=4$ the situation regarding minimal periodic colorings of $A_{n-1}$ is more complicated. The assignment

$\sigma_{12} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{smallmatrix} \right), \quad \sigma_{13} \equiv \left( \begin{smallmatrix}1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \end{smallmatrix} \right), \quad \sigma_{14} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \end{smallmatrix} \right)$

works and produces the essentially unique periodic cyclic coloring of $A_3.$ This name reflects the fact that the induced $\Gamma_\sigma$ is isomorphic to the cyclic group $\mathbb{Z}_4.$

The cyclic coloring of $A_3$. For comparison with a later figure, take 0 to be the vertex at the top of this figure.

There are also essentially three inequivalent periodic 4-colorings with $\Gamma_\sigma \cong \mathbb{Z}_2^2$ obtained in this way, corresponding to

$\sigma_{12} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{smallmatrix} \right), \quad \sigma_{13} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \end{smallmatrix} \right), \quad \sigma_{14} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{smallmatrix} \right);$

or

$\sigma_{12} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{smallmatrix} \right), \quad \sigma_{13} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1 \end{smallmatrix} \right), \quad \sigma_{14} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{smallmatrix} \right);$

or

$\sigma_{12} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{smallmatrix} \right), \quad \sigma_{13} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{smallmatrix} \right), \quad \sigma_{14} \equiv \left( \begin{smallmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{smallmatrix} \right),$

respectively.

The $\mathbb{Z}_2^2$ coloring of $A_3$ corresponding to $\sigma_{12} \equiv \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{smallmatrix} \right), \quad \sigma_{13} \equiv \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \end{smallmatrix} \right),$ and $\sigma_{14} \equiv \left(\begin{smallmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{smallmatrix} \right).$

For larger values of $n$ it is impractical to catalog the coherent color shift groups in silico via brute force: either a reasonably sophisticated algorithm or some (presumably nontrivial representation-theoretic) calculation in papyro is wanted. Nevertheless, it is easy to see that a cyclic coloring of $A_{n-1}$ exists for all $n$ (and hence that for $n$ prime the cyclic coloring is the only periodic $n$-coloring): simply let

$s := \left(\begin{smallmatrix} 1 & 2 & \cdots & n-1 & n \\ 2 & 3 & \cdots & n & 1 \end{smallmatrix} \right).$

The cyclic coloring is obtained by setting $\sigma_{1k} := s^{k-1}.$

Color quotients and the cyclic color space

For $k \ge n$ we may consider a $k$-coloring $\kappa$ of $A_{n-1}$ and the attendant color quotient $A_{n-1}/\sim$, where $x \sim y \iff \kappa(x) = \kappa(y)$. The color projection map $\Pi : A_{n-1} \rightarrow A_{n-1}/\sim$ is defined in the obvious way, and we may identify $\Pi$ and $\kappa$ with only a slight abuse of notation. In particular, if $\kappa$ is the cyclic coloring, the resulting color quotient is called the cyclic color space and denoted $\mathbb{A}_{n-1}.$

Consider a càdlàg random walk $\xi_t$ on $A_{n-1}$, for $t \ge t_0 \equiv 0$, and write $\kappa_t := \Pi \circ \xi_t \equiv \kappa \circ \xi_t$ for the projected walk on $\mathbb{A}_{n-1}.$ Let $t_\ell$ denote the $\ell$th jump time of $\xi_t$ (and hence also $\kappa_t$), and in a further abuse of notation write $\kappa_\ell := \kappa(\xi_{t_\ell}).$ Let $j_\ell,k_\ell$ be defined via $\xi_{t_\ell} - \xi_{t_{\ell-1}} = -e_{j_\ell} + e_{k_\ell}.$ Now the color shift from $\kappa_\ell$ to $\kappa_{\ell+1}$ is

$\sigma_{\kappa_\ell \kappa_{\ell+1}} = \sigma_{\kappa_\ell 1} \sigma_{1 \kappa_{\ell+1}} = s^{1-\kappa_\ell}s^{\kappa_{\ell+1}-1} = s^{\kappa_{\ell+1}-\kappa_\ell}.$

Without loss of generality, let $\kappa_0 = 1$ and $\kappa(\xi_0-e_1+e_k) = k$. Define

$\rho_n(m) := (m-1) \!\!\!\!\! \mod n + 1.$

Note that $s^\ell : j \mapsto s^\ell \cdot j \equiv \rho_n(j + \ell)$, where $\cdot$ indicates the cyclic color shift action. Now

$\kappa(\xi_0-e_j+e_k) = \kappa([\xi_0-e_1+e_k]-e_j+e_1) \equiv \sigma_{j1} \cdot k$

$= \sigma_{1j}^{-1} \cdot k = s^{-j+1} \cdot k = \rho_n(k-j+1).$

Therefore $\kappa_1 = \rho_n(1+ k_1 - j_1)$, and we have that the color shift from $\kappa_0$ to $\kappa_1$ is

$\sigma_{\kappa_0 \kappa_1} = s^{\kappa_1-\kappa_0} = s^{\rho_n(k_1 - j_1 + 1)-1} = s^{(k_1 - j_1) \!\!\!\!\! \mod n} = s^{k_1 - j_1}.$

We proceed along similar lines to compute $\kappa_{\ell+1}$ from $\kappa_\ell,$ $j_\ell,$ and $k_\ell:$

$\boxed{\kappa_{\ell+1} = \sigma_{j_\ell k_\ell} \cdot \kappa_\ell = s^{k_\ell - j_\ell} \cdot \kappa_\ell = \rho_n(k_\ell - j_\ell + \kappa_\ell).}$

This equation illustrates the ease and utility of projecting random walks from $A_{n-1}$ to $\mathbb{A}_{n-1}.$ It is also straightforward to show that for $a \in \mathbb{Z}^n$ the assignment

$\kappa \left( \sum_{m=1}^n a_m(-e_1 + e_m) \right) = \left( \sum_{m=1}^n a_m (m-1) \right) \!\!\!\!\! \mod n + 1$

produces the cyclic coloring.

In a followup post I’ll sketch how to identify the coherent color shift groups of low order and hint at some of the ways in which this construction might be applied.

### 2 Responses to A minimal periodic coloring theorem, part 2

1. [...] minimal periodic coloring theorem, part 3 Last time I gave nontrivial examples of periodic colorings of and demonstrated that the cyclic coloring of [...]

• Carley says:

Hooray for new traditions. I was srisruped to learn you all hadn’t put up a tree before. We almost didn’t this year last year’s tree dropped so many needles and I wasn’t sure I could handle that again. We went with a different tree variety this year, and it’s been much better so far.