Quantum Geometry II :

The Mathematics of Loop Quantum Gravity

Three dimensional quantum gravity
J. Manuel García-Islas [
e-mail<EMAIL_ADDRESS>
Loop quantum gravity is a physical theory which aims at unifying general relativity and quantum mechanics.
It takes general relativity very seriously and modifies it via a  quantisation. General relativity describes gravity
in terms of geometry. Therefore, quantising such theory must be equivalent to quantising geometry and that is
what loop quantum gravity does. This sounds like a mathematical task as well.
This is why in this paper we will present the mathematics of loop quantum gravity. We will
do it from a mathematician point of view. This paper is intended to be an introduction to loop quantum gravity for postgraduate students of physics
and mathematics.
In this work we will restrict ourselves to the three dimensional case.

Key Words: Quantum Gravity, Quantum Geometry.

PACS Number: 04.60, 04.60.Pp

§ INTRODUCTION

It is very well known in physics that
classical physical theories have a quantum version. Classical Mechanics and Quantum Mechanics,
Classical Electrodynamics and Quantum Electrodynamics, Special Relativity and Quantum Field Theory.

The question then is: what is the
quantum version of general relativity?
There is no agreement on the answer to this question.

Loop quantum gravity [1], [2], [3] [4],
is a theory which describes the quantum version of general relativity. Since general relativity is a geometrical theory,
quantising such a theory is equivalent to thinking of quantising classical geometry.[
Mathematically speaking,
quantum geometry may also refer to a subject known as noncommutative geometry [5]. But for us it will refer
to loop quantum gravity which is also a quantum geometry.]
This is what loop quantum gravity does in its own original way.   However, unfortunately mathematicians are not
aware of loop quantum gravity and it may be due to the fact that it is a theory
mostly invented by physicists. The truth is that loop quantum gravity is such a beautiful theory with
very precise, rigorous mathematical background which exploits many different subjects of outstanding

Our intention and our project is to write papers introducing loop quantum gravity to postgraduate students in physics and mathematics. We
write it from the point of view of a mathematician. We hope that more mathematicians get to know
and become interested in loop quantum gravity.

However, the project may also be considered from the loop quantum gravity community itself as
writing about the mathematics of loop quantum gravity.

Loop quantum gravity is a very extensive field of study and there are numerous things to deal with. Our project is to
write about the mathematics of loop quantum gravity and therefore write many works on this subject by dealing with a particular theme
in each work. We have already started this project describing quantum polyhedra in [6].

In this work we will deal with three dimensional quantum gravity which has been extensively studied in the literature and there are also
many things in this particular theme to write about. We concentrate on the essentials. Our presentation of the mathematics
of loop quantum gravity is completely original and described in our own way. In this sense this is an original work and an
original project.

In section 2 and 3 we present the mathematical background which is also useful for many other themes in loop quantum gravity.
In section 4 and 5 we introduce three dimensional loop quantum gravity.

§ TOPOLOGICAL GROUPS AND REPRESENTATIONS

In this section we review some mathematical background related to Lie groups and linear representations which is used in loop quantum gravity.
This section is based on [7], [8].

A topological group $G$, is a group which is also a topological space such that the product and inverse operations are continuous. It is said to be compact
if it is a compact space.

We will only consider compact topological groups.

There exists a unique measure on $G$ with the following properties.

1) $\int_{G} f(g) \ dg = \int_{G} f(g h) \ dg$ for every $h \in G$.

2) $\int_{G} f(g) \ dg = \int_{G} f(h g) \ dg$ for every $h \in G$.

3) $\int_{G} f(g) \ dg = 1$.

The measure $dg$ is called invariant measure or the Haar measure of $G$.[Since we are considering compact Lie groups only, it is known that right invariant measures
are also left invariant and that a normalisation condition such as 3) can be chosen. We will not be concerned with this here.]

A linear representation of $G$ in a Hilbert space $H$ is a group homomorphism $\rho : G \longrightarrow GL(H)$, such that $\rho(g) x$ is a continuous map
for every $x \in H$.

Therefore, we have that for $g$ and $g' \in G$,  $\rho(g g') = \rho(g) \rho(g')$, $\rho(g^{-1}) = \rho(g)^{-1} $ and $\rho(e) = Id_{H}$, where $e$ is the identity
of the group and $Id_{H}$ is the identity map in $H$.

The dimension of $H$ is called the dimension of the representation and a representation will be denoted by the pair $(H, \rho)$.

A linear representation of $G$ in a Hilbert space $H$ is a unitary representation if $\rho(g)$ is a unitary operator for every $g \in G$.
Equivalently, $\rho$ is unitary if $< \rho(g) x , \rho(g) y > = < x , y >$ for every $g \in G$ and every $x, y \in H$.[$< , >$ is the scalar product in H
which we assume to be conjugate linear in the first entry and linear in the second]

If $(e_i)$ is a basis of $H$ we have the matrix coefficients of the representation $(H, \rho)$ given by

\begin{equation}
\rho_{ij}(g) = < e_i , \rho(g) e_j > \nonumber
\end{equation}

An intertwining operator between two unitary representations $(H_1 , \rho_1)$ and $(H_2, \rho_2)$ is a continuos linear map $T: H_1 \longrightarrow H_2$ such that
for every $g \in G$ the following diagram commutes

H_1 [r, "T"][d,  "ρ_1(g)"red]
H_2 [d, "ρ_2(g)" ]

H_1 [r,  "T" red]

The representations $(H_1 , \rho_1)$ and $(H_2, \rho_2)$ are said to be equivalent if there exists a bijective $T: H_1 \longrightarrow H_2$
intertwining operator.

This implies that we have an equivalence class of a representation.

A vector subspace $W \subset H$ is said to be invariant under $(H , \rho)$, if $\forall g \in G$, $\rho(g) W \subset W$.

A representation $(H , \rho)$ is said to be irreducible if $H \neq \{ 0 \}$ and if $\{ 0 \}$ and $H$ are the only
vector subspaces of $H$ which are invariant under $\rho$.

Let $(H_1 , \rho_1)$ and $(H_2 , \rho_2)$ be representations of $G$. The direct sum is the representation $(H_1 \oplus H_2 , \rho_1 \oplus \rho_2)$
so that $\forall g \in G$ and $x_1 \in H_1, x_2 \in H_2$.

\begin{equation}
( \rho_1 \oplus \rho_2)(g)(x_1 , x_2) = (\rho_1(g) x_1 ,  \rho_2(g)x_2)\nonumber
\end{equation}

The matrix representation of a direct sum is given by

\begin{equation*}
\left(
\begin{array}{ccc}
\rho_1(g) & 0   \\
0 & \rho_2(g)
\end{array} \right)
\end{equation*}

Analogously the direct sum of an arbitrary finite number of representations is defined.

Let $(H_1 , \rho_1)$ and $(H_2 , \rho_2)$ be representations of $G$. The tensor product is the representation $(H_1 \otimes H_2 , \rho_1 \otimes \rho_2)$
so that $\forall g \in G$ and $x_1 \in H_1, x_2 \in H_2$.

\begin{equation}
( \rho_1 \otimes \rho_2)(g)(x_1 \otimes x_2) = \rho_1(g) x_1 \otimes  \rho_2(g)x_2 \nonumber
\end{equation}

The matrix representation of a tensor product is given by the Kronecker tensor product of the matrices

\begin{equation*}
\left(
\begin{array}{ccc}
\rho_{11} \rho_2(g) & \cdots & \rho_{1n} \rho_2(g) \\

\vdots & \vdots & \ddots \\
\rho_{n1} \rho_2(g) & \cdots & \rho_{nn} \rho_2(g)
\end{array} \right)
\end{equation*}

A representation $(H , \rho)$ is said to be reducible  if it is the direct sum of irreducible representations
$(W_1 , \rho_1), (W_2 , \rho_2),..., (W_k , \rho_k)$; this is expressed
$( H , \rho)  = ( W_1 \oplus W_2 \oplus \cdots \oplus W_k , \rho_1 \oplus \rho_2 \oplus \cdots \oplus \rho_k )$

or simply

\begin{equation}
( H , \rho) = ( \oplus_{i=1}^{k} W_i , \oplus_{i=1}^{k} \rho_i ) \nonumber
\end{equation}

Every unitary representation $(H, \rho)$ of $G$ is reducible.

If the representation is irreducible, then we are finished. Suppose then that the representation $(H , \rho)$ is unitary and not irreducible; then there
must be an invariant subspace $W \subset H$. Since there is a scalar product we can consider the complement of $W$ in $H$ denoted $W^{\perp}$
such that $H = W \oplus W^{\perp}$. It can be shown that $W^{\perp}$ is also an invariant subspace. By induction the theorem follows.

( Schur ) Let $(H_1 , \rho_1)$ and $(H_2 , \rho_2)$ be unitary irreducible representations of $G$. And let $T: H_1 \longrightarrow H_2$
be an intertwining operator. Then $T = 0$ or $T$ is an isomorphism.

Consider the vector space $\mathbb{C}^{G} =\{ f : G \longrightarrow \mathbb{C} \}$ of complex valued functions on $G$, and define the scalar product

\begin{equation}
< f_1 \mid f_2 >  = \int_{G} \overline{f_1 (g)}  f_2 (g) \ dg \nonumber
\end{equation}

where $dg$ is the Haar measure. By completing this space we obtain the Hilbert space of square integrable functions $L^{2}(G)$.

Let $(H_1 , \rho_1)$ and $(H_2 , \rho_2)$ be irreducible unitary representations of $G$. Let $x_1, y_1 \in H_1$ and $x_2, y_2 \in H_2$. Then

\begin{equation}
< \rho_{x_1 y_1}(g) \mid \rho_{x_2 y_2}(g) > = 0 \nonumber
\end{equation}

if the representations are not equivalent, or

\begin{equation}
< \rho_{x_1 y_1}(g) \mid \rho_{x_2 y_2}(g) > = \frac{1}{n} < x_2 , x_1 > < y_1 , y_2 >\nonumber
\end{equation}

if the representations are equivalent and where $n$ is the dimension of $H_1 \sim H_2$.

In particular, if we have orthonormal basis

\begin{equation}
< \rho_{i j}(g) \mid \rho_{k l}(g)) > = 0 \nonumber
\end{equation}

if the representations are not equivalent, or

\begin{equation}
< \rho_{i j}(g) \mid \rho_{k l}(g) > = \frac{1}{n} \delta_{i k} \delta_{j l}  \nonumber
\end{equation}

if the representations are equivalent, where $\delta_{ij}$ is the Kronecker delta.

The set of equivalence classes of irreducible representations of $G$ is denoted by $\hat{G}$.

Peter - Weyl.
Let $f \in L^{2}(G)$. Then

\begin{equation}
f(g) = \sum_{\alpha \in \bar{G}} \sum_{i , j = 1}^{dim \ \rho^{\alpha}} c_{ij}^{\alpha} \ \rho_{ij}^{\alpha}(g) \nonumber
\end{equation}

where $\alpha$ runs over the different irreducible unitary representations, $\rho_{ij}^{\alpha}$ are the matrix coefficients of the representations in
orthonormal basis.

Therefore, the coefficients are given by

\begin{equation}
c_{ij}^{\alpha} = dim \ \rho^{\alpha} \ \int_{G} \overline{\rho_{i j}^{\alpha}(g)} f(g) \ dg \nonumber
\end{equation}

§.§ SU(2)

In this part, we will summarise some important aspects of the irreducible representations of the group
$G = SU(2)$ which are used in LQG. $SU(2)$ consist of the matrices given by

\begin{equation*}
\left(
\begin{array}{ccc}
a & b   \\
- \overline{b} & \overline{a}
\end{array} \right)
\end{equation*}

where $a, b \in \mathbb{C}$ and $\mid a \mid^2 + \mid b \mid^2 = 1$. It can be easily seen that $SU(2)$ is diffeomorphic to the three dimensional sphere $S^3$.

$SU(2)$ acts on the space of complex valued functions on $\mathbb{C}^2$ as follows: we have that for $g \in SU(2)$, $g^{-1} = {}^{t}_{}\overline{g}$; the action
is given by

\begin{equation}
\rho(g) f = f \circ g^{-1} \nonumber
\end{equation}

so that

\begin{equation}
\rho(g) f(z_1 , z_2)  = f( \overline{a}z_1 - b z_2 , \overline{b}z_1 + az_2) \nonumber
\end{equation}

Now we restrict the space of complex valued functions on $\mathbb{C}^2$ to homogeneous polynomials and denote by $H^j$ the vector space of homogeneous polynomials
of degree $2j$ where $j = \frac{1}{2} \mathbb{N}$. The dimension of $H^j$ is $2j +1$.[This view is common to physicists and we will use it.
Mathematicians are more used to think of the space $H^n$ as the space of complex homogeneous polynomials on $\mathbb{C}^2$ of degree $n =2j, n \in \mathbb{N}$,
which has dimension $n+1$.]

This space has basis given and denoted by

\begin{equation}
f_{m}^{j} (z_1 , z_2) = {z_1}^{j+m} \ {z_2}^{j-m} \nonumber
\end{equation}

where $-j \leq m \leq j$; $m$ is integer if $j$ is integer and half-integer if $j$ is half-integer. When restricted to the space $H^j$ the action $\rho$ gives a representation which we denote by $(H^j ,\rho^j )$.

The Lie algebra $\mathfrak{su}(2)$ of $SU(2)$ is a vector space of dimension three of traceless anti-Hermitian matrices with basis
given by

\begin{equation*}
\xi_1 = \frac{1}{2} \left(
\begin{array}{ccc}
0 & i   \\
i & 0
\end{array} \right) \qquad
\xi_2 = \frac{1}{2} \left(
\begin{array}{ccc}
0 & -1   \\
1 & 0
\end{array} \right) \qquad
\xi_3 = \frac{1}{2} \left(
\begin{array}{ccc}
i & 0   \\
0 & -i
\end{array} \right)
\end{equation*}

which satisfy the commutation relations $[\xi_1 , \xi_2] = \xi_3 , [\xi_2 , \xi_3] = \xi_1 , [\xi_3 , \xi_1] = \xi_2 $.

Physicists in LQG prefer to use the Hermitian matrices given by $J_k = i \xi_k$ for $k=1,2,3$ where the commutation relations are given by
$[J_1 , J_2] = i J_3 , [J_2 , J_3] = i J_1 , [J_3 , J_1] = i J_2 $.

Moreover, we consider the matrices $J_3 , J_+ = J_1 + i J_2 , J_- = J_1 - i J_2$ which have commutation relations
$[J_+ , J_-] = 2 J_3 , [J_3 , J_+] =  J_+ , [J_3 , J_-] = - J_- $.
It is known that the differentials $D$ of the representations $\rho^j$ are representations of the Lie algebra and therefore
give rise to operators $( D \rho^j ) J_3 ,  (D \rho^j ) J_+ ,  (D \rho^j ) J_-$
that act on the space $H^j$ as follows[The differential of the representation $(E, \rho)$ of a Lie Group $G$ gives a Lie Algebra representation.
Studying Lie Algebra representations is equivalent to studying the representations of the Lie Group. See [7] for details.]; rename the basis $f_{m}^{j} $ of $H^j$ with notation used in physics

\begin{equation}
\mid j , m > = \frac{1}{\sqrt{(j-m)! (j+m)!}}f_{m}^{j}  \nonumber
\end{equation}

\begin{align}
&( D \rho^j ) J_3 \ \mid j , m > = m \ \mid j , m >  \nonumber \\
&( D \rho^j ) J_+ \ \mid j , m > = \sqrt{(j-m) (j+m +1)} \ \mid j , m +1 > \nonumber  \\
& ( D \rho^j ) J_- \ \mid j , m > =  \sqrt{(j+m) (j-m +1)} \ \mid j , m -1 > \nonumber
\end{align}

It is a well known proven fact that each representation $(H^j , \rho^j)$ of $SU(2)$ is unitary and irreducible with the fact that the basis
$ \mid j , m >$ is orthonormal.

The tensor product of representations is used thoroughly in LQG. The tensor product of two irreducible representations is reducible and therefore
is the direct sum of irreducible representations which for $SU(2)$ is known as the Clebsch-Gordan decomposition

\begin{equation}
( H^{j_1} \otimes H^{j_2}, \rho^{j_1} \otimes \rho^{j_2} )  = ( H^{\mid j_2 -j_1 \mid} \oplus H^{\mid j_2 -j_1 \mid +1} \oplus \cdots \oplus
H^{j_1 + j_2} , \rho^{\mid j_2 -j_1 \mid} \oplus \cdots \oplus \rho^{j_1 + j_2} ) \nonumber
\end{equation}

This decomposition of the tensor product of two unitary irreducible representations implies that we can consider
two orthonormal basis, one given by

\begin{equation}
\mid j_1 , m_1 > \otimes \mid j_2 , m_2 > \qquad \text{where} \qquad - j_1 \leq m_1 \leq j_1, \qquad - j_2 \leq m_2 \leq j_2 \nonumber
\end{equation}

And the second one given by

\begin{equation}
\mid J , M >   \qquad \text{where} \qquad \mid j_1 - j_2 \mid \leq J \leq j_1+ j_2 \qquad \text{and} \qquad - J \leq M \leq J \nonumber
\end{equation}

Since the tensor product and the direct sum decomposition are isomorphic spaces
we can change basis and write down one of the basis vectors as a linear combination of the others

\begin{equation}
\mid J , M >  = \sum_{m_1 , m_2} C(J , M , j_1 , m_1 , j_2 , m_2) \ \mid j_1 , m_1 > \otimes \mid j_2 , m_2 > \nonumber
\end{equation}

where the coefficients $C(J , M , j_1 , m_1 , j_2 , m_2)$ are known as Clebsch-Gordan coefficients.
It is more common in physics to use Wigner notation of these coefficients because of the symmetries which are easier to visualise. Let

\begin{equation*}
\left(
\begin{array}{ccc}
j_1 & j_2 & J   \\
m_1 & m_2 & - M
\end{array} \right) = \frac{(-1)^{j_1 - j_2 + M}}{\sqrt{2J+1}} \ C(J , M , j_1 , m_1 , j_2 , m_2)
\end{equation*}

Then we can write the change of basis formula as

\begin{equation*}
\mid J , M >  = \sum_{m_1 , m_2} (-1)^{j_2 - j_1 - M} \sqrt{2J+1}
\left(
\begin{array}{ccc}
j_1 & j_2 & J   \\
m_1 & m_2 & - M
\end{array} \right) \
\mid j_1 , m_1 > \otimes \mid j_2 , m_2 > \nonumber
\end{equation*}

It is also useful to write down the change of basis the other way around. This is given by

\begin{equation*}
\mid j_1 , m_1 > \otimes \mid j_2 , m_2 >
= \sum_{J , M} (-1)^{j_2 - j_1 - M} \sqrt{2J+1}
\left(
\begin{array}{ccc}
j_1 & j_2 & J   \\
m_1 & m_2 & - M
\end{array} \right) \
\mid J , M >  \nonumber
\end{equation*}

The symmetry properties of the Wigner symbol are can be found in the literature.

§ GRAPHS AND TRIANGULATIONS

This section is based on [9].

A point configuration in Euclidean space $\mathbb{R}^n$ is a finite collection of points $\Pi = \{ p_1, p_2, ....p_k \}$

A convex hull of $\Pi$ is the intersection of all convex sets which contain the points of $\Pi$. It is denoted by $\text{conv}(\Pi)$.

A d-simplex is the convex hull of $d+1$ affinely independent points in $\mathbb{R}^n$. We must have $n \geq d$.

A j-face of a d-simplex is the convex hull of $j+1$ of its vertices.

A triangulation of a point configuration $\Pi \in \mathbb{R}^n$ is a collection of n-simplices all of whose vertices are points of $\Pi$ such that
the union of all these simpleces equals $\text{conv}(\Pi)$ and any pair of these simpleces intersects in a common face.

It is allowed that the intersection of these pair of simpleces is empty.

A graph is a pair $\Gamma = (V, E)$ of sets, such that $E \subset [V]^2$.

$E \subset [V]^2$ means that the elements of $E$ are two-element subsets of $V$. Is is always assumed that $V \cap E = \emptyset$.
The elements of $V$ will be called vertices and the elements of $E$ will be called edges.

The vertex set of the graph $\Gamma$, will be denoted as $V(\Gamma)$ and its vertex set by $E(\Gamma)$.

The number of vertices of the graph $\Gamma$ is its order and is denoted $\mid \Gamma \mid$.

A vertex is incident to edge $e$ if $v \in e$. It is also said that $e$ is an edge at $v$.
The two vertices incident to edge $e$ are called its endvertices.

The set of all edges at a vertex $v$ is denoted by $E(v)$.

The number of edges $E(v)$ at vertex $v$ is called the degree of vertex $v$ and it is denoted by $d_{\Gamma}(v)$ or simply by $d(v)$.

Given a triangulation of a point configuration $\Pi \in \mathbb{R}^n$ we associate a graph called
the dual graph; this graph is drawn as follows:  draw a node for each n-simplex and an
edge when two n-simpleces intersect in a (n-1)-face.

Consider a triangulation of a point configuration in $\mathbb{R}^3$ and its dual graph. The dual graph is called a 2-complex in LQG. Observe that the
dual graph associated to the boundary simplicial triangulation is given by a trivalent graph $\Gamma=(V , E)$.

§ THREE DIMENSIONAL LQG

We now start with the three dimensional study of quantum gravity as it is understood in LQG. This section is our main section and we
try to be as mathematical as possible as in our previous sections. This section is entirely inspired on [2].
A mathematical description of loop quantum gravity can be found in [10], and reference [3] is a very advanced
book on loop quantum gravity which is very mathematical. A very nice and useful introduction to the subject which uses more physical notation
is [11].

§.§ Spin Networks

In LQG there is a Hilbert space which is interpreted as the quantum space of states.
Consider a trivalent directed graph $\Gamma = (V, E)$  with $\mid V \mid$ number of vertices  and $\mid E \mid$ number of edges.
The Hilbert space of three dimensional LQG is a subspace of the Hilbert space $L^2(SU(2)) \times L^2(SU(2)) \cdots \times L^2(SU(2))$ of $\mid E \mid$ products
which we denote by $L^2(SU(2)^{\mid E \mid})$. This subspace is called the invariant space and it is the Hilbert space of the theory. This
space is given as follows.

Consider a function $c: E \rightarrow \widehat{SU(2)}$ which goes from the set of edges to the
set of equivalence classes of irreducible representations of $SU(2)$ with the following properties. This function $c$ is called
labelling function.

So for each directed edge $e$ we have $c(e) = ( H^{j} , \rho^{j} )$. Denote the matrix coefficients of this representation by

\begin{equation}
\rho_{mn}^{j} (g) = \ < e_m , \rho^{j}(g) e_n > \nonumber
\end{equation}

We can think of this in a graphical way, where the directed edge is labelled $j$ and its vertices are labelled $m$ and $n$ and the edge is directed
from vertex labelled $n$ to vertex labelled $m$.

For each vertex $v$ we have three directed edges $e_1, e_2, e_3$ incident to $v$ and suppose that
$c(e_1) = ( H^{j_1} , \rho^{j_1} )$ and $c(e_2)= ( H^{j_2} , \rho^{j_2} )$ and $c(e_3)= ( H^{j_3} , \rho^{j_3} )$.

Assign to the vertex $v$ the Wigner coefficients [The Wigner coefficient $\widetilde{C}(j_1 , m_1 , j_2 , m_2 , j_3 , m_3)$
in a graphical way is thought as a trivalent vertex with its edges directed outwards and labelled $j_1, j_2, j_3$. If we had
$\widetilde{C}(j_1 , m_1 , j_2 , m_2 , j_3 ,  - m_3)$  then it is thought as a trivalent vertex with
two of its edges directed outwards labelled $j_1, j_2$ and one inwards labelled $j_3$ Analogously if any of the indices $m_i$ changes sign.]

\begin{equation*}
v \mapsto \left(
\begin{array}{ccc}
j_1 & j_2 & j_3   \\
m_1 & m_2 & m_3
\end{array} \right) : = \widetilde{C}(j_1 , m_1 , j_2 , m_2 , j_3 , m_3)
\end{equation*}

This is equivalent to assigning to the vertex $v$ an intertwining operator given by $T : \mathbb{C} \longrightarrow H^{j_1}  \otimes H^{j_2} \otimes H^{j_3} $.
Although the notation of the Wigner coefficients is the $2 \times 3$ matrix, we will use the $\widetilde{C}(j_1 , m_1 , j_2 , m_2 , j_3 , m_3)$ notation
of our own.

Now we are ready to present an element of the invariant Hilbert space of three dimensional LQG.

By the Peter-Weyl theorem if $f \in L^2(SU(2)^{\mid E \mid})$ it must be of the form

\begin{equation}
f(g_1 , g_2 , \cdots g_{\mid E \mid}) = \sum_{j_1 \cdots j_{\mid E \mid}} \sum_{m , n = 1}^{dim \ \rho^{j}}
c_{m_1 m_2 \cdots m_{\mid E \mid} n_1 n_2 \cdots n_{\mid E \mid}}^{j_1 j_2 \cdots j_{\mid E \mid}} \
\rho_{m_1 n_1}^{j_1}(g_1) \cdots \rho_{m_{\mid E \mid} n_{\mid E \mid}}^{j_{\mid E \mid}}(g_{\mid E \mid}) \nonumber
\end{equation}

According to [2], the invariant Hilbert space is spanned by the functions $\Psi \in L^2(SU(2)^{\mid E \mid})$ given by
[Recall that we have considered a trivalent graph $\Gamma = (V, E)$  with $\mid V \mid$ number of vertices  and $\mid E \mid$ number of edges.]

Ψ(g_1 , g_2 , ⋯g_|E |) =     ∑_m_1 m_2 ⋯n_|E |-1 n_|E |     C_1(j_1, m_1, j_2 , m_2 , j_3 , m_3)  ×⋯×

C_|V |( j_|E |-2 ,  n_|E |-2 ,  j_|E |-1 ,  n_|E |-1 ,  j_|E | ,  n_|E | ) ×

ρ_m_1 n_1^j_1(g_1) ⋯⋯ρ_m_|E | n_|E |^j_|E |(g_|E |)
These functions are known as the quantum state functions. Therefore the invariant Hilbert space is given by linear combinations of these functions.
This space is called Quantum Space.

Let us show with examples how these generator functions $\Psi$ are given.

§.§.§ Example

The theta graph

The theta graph $\Theta = (V, E)$ has two vertices $v_1, v_2$ and three edges $e_1, e_2 , e_3$. If $c(e_1) = ( H^{j_1} , \rho^{j_1} )$,
$c(e_2) = ( H^{j_2} , \rho^{j_2} )$ then recall that $j_3$ must be chosen between $\{  \mid j_2 - j_1\mid , \mid j_2 - j_1\mid +1 , \cdots j_1 + j_2 \ \}$.
In this case the state function is given by

Ψ(g_1 , g_2 , g_3) =     ∑_m_1 m_2 m_3   ∑_n_1 n_2 n_3     C(j_1, m_1, j_2 , m_2 , j_3 , m_3)  C(j_1, - n_1, j_2 , - n_2 , j_3 , - n_3)

ρ_m_1 n_1^j_1(g_1)  ρ_m_2 n_2^j_2(g_2)  ρ_m_3 n_3^j_3(g_3)
where the sum takes the values $- j_1 \leq m_1 \leq j_1$, $- j_1 \leq n_1 \leq j_1$, $- j_2 \leq m_2 \leq j_2$, $- j_2 \leq n_2 \leq j_2$,
$- j_3 \leq m_3 \leq j_3$, $- j_3 \leq n_3 \leq j_3$.

§ STATE SUM MODEL

As we have discussed it is equivalent to think of a triangulation of a point configuration or to think of the dual graph. Let $M$ be a triangulation
of a point configuration in $\mathbb{R}^3$. Let $\partial M = \Sigma$ be its boundary.[This boundary may have one component or may be composed of different
components.] Observe that the boundary is a two dimensional triangulation in the sense that it is composed of 0-simplices, 1-simplices and 2-simplices.

A colouring of $M$ is a map $c: E(M) \rightarrow \widehat{SU(2)}$, where $E(M)$ is the set of 1-simplices of $M$ and $\widehat{SU(2)}$ is the set
of equivalent irreducible representations of $SU(2)$.

Such colouring $c$ is called admissible if for each 2-simplex there is an intertwining operator $T : H_1 \otimes H_2 \otimes H_3 \rightarrow \mathbb{C}$.

Consider now the tensor product of three irreducible representations of $SU(2)$,  $( H^{j_{12}} \otimes H^{j_{23}} \otimes H^{j_{34}}, \rho^{j_{12}} \otimes \rho^{j_{23}} \otimes \rho^{j_{34}})$.
We know from section 2.1 that the tensor product of two irreducible representations decomposes in a direct sum of irreducible ones.
Therefore, now have two possible homomorphisms

\begin{equation}
F_1 = H^{j_{14}} \longrightarrow ( H^{j_{12}} \otimes H^{j_{23}} ) \otimes H^{j_{34}} \nonumber
\end{equation}

\begin{equation}
F_2 = H^{j_{14}} \longrightarrow H^{j_{12}} \otimes ( H^{j_{23}}  \otimes H^{j_{34}} )  \nonumber
\end{equation}

\begin{equation}
H^{j_{12}} \otimes H^{j_{23}} =  \bigoplus_{j_{13}} H^{j_{13}} \nonumber
\end{equation}

where $j_{13}$ runs from $\mid j_{23} - j_{12} \mid$ to $j_{23} + j_{12}$. We also have that

\begin{equation}
H^{j_{23}} \otimes H^{j_{34}} =  \bigoplus_{j_{24}} H^{j_{24}} \nonumber
\end{equation}

where $j_{24}$ runs from $\mid j_{34} - j_{23} \mid$ to $j_{34} + j_{23}$.

The coefficients which appear in the change of basis in the diagram

H^j_14 [r, "F_2"][d,  "Id"red]
H^j_12 ⊗( H^j_23 ⊗H^j_34 )  [d, "" ]

H^j_14  [r,  "F_1" red]
( H^j_12 ⊗H^j_23 ) ⊗H^j_34

are called the 6j-symbols and are denoted by

\begin{equation*}
\left \{
\begin{array}{ccc}
j_{12} & j_{23} & j_{13}   \\
j_{34} & j_{14} & j_{24}
\end{array} \right \}
\end{equation*}

Explicitly the $6j$-symbols are given by

j_1     j_2     j_3

j_4     j_5     j_6
} =
∑_m_1, ..... , m_6  (-1)^∑_i=1^6 (j_i - m_i)
C(j_1, - m_1, j_2 , - m_2 , j_3 , - m_3)
C(j_1, m_1, j_5 , - m_5 , j_6 , m_6)

×C(j_4, m_4, j_2 , m_2 , j_6 , - m_6)  C(j_3, m_3, j_4 , - m_4 , j_5 , m_5)
The $6j$-symbol has the following symmetries

j_1     j_2     j_3

j_4     j_5     j_6
} =

j_2     j_1     j_3

j_5     j_4     j_6
}  =

j_3     j_2     j_1

j_6     j_5     j_4
}    =

j_4     j_2     j_6

j_1     j_5     j_3

Let $M$ be a triangulation
of a point configuration in $\mathbb{R}^3$ and $\partial M = \Sigma$ be its boundary. Let $E^{\circ} = \{ E(M) \in M^{\circ}\}$ be the interior edges of $M$.
The state sum is defined by

\begin{equation}
Z_M [ \Sigma] = \sum_{c} \ \prod_{E^{\circ}} (-1)^{2j} (2j+1) \ \prod_{\triangle} (-1)^{\sum_{i=1}^{6} j_{i}}  \
\left \{
\begin{array}{ccc}
j_{1} & j_{2} & j_{3}   \\
j_{4} & j_{5} & j_{6}
\end{array}      \right \}     \nonumber
\end{equation}

where the sum is over all functions $c: E^{\circ} \rightarrow \widehat{SU(2)}$ of admissible colourings
of the interior 1-simplices $E^{\circ}$, and $\triangle$ is the set of 3-simplices of $M$.

The state sum $Z_M[\Sigma]$ is a function of the colouring of the boundary $\Sigma$ of $M$
The colouring of the boundary is fixed
since the state sum is only over the colouring of the interior 1-simplices. And if our triangulation configuration $M$ has no boundary
then $Z_M [\Sigma] \in \mathbb{C}$.

It is known that this state sum is interpreted geometrically
as a sum over metrics on the interior of a manifold which match the fixed boundary metric. Moreover,
for most triangulations this state sum diverges and therefore regularisation of the sum is needed.
We will not be concerned with the metric problem here but in a future work. Neither will we be concerned with
the regularisation issue in this work as it is a different topic which has been extensively studied, see for example
[12], [13]. These subjects will be treated in a different one.

Physically the state sum is a Feynman path integral of general relativity. In this case of three dimensional Euclidean general relativity. This state sum is known as the Ponzano-Regge model
[14] and its connection to loop quantum gravity was pointed out in [15].
We will deal with the regularisation and the mathematics of this state sum in another work and will describe its properties.

§ DISCUSSION

We have introduced a well known state sum of three dimensional loop quantum gravity. The model is a quantisation of three dimensional Euclidean general relativity without
cosmological constant. Originally this model came from a discretisation of a Feynman path integral of three dimensional general relativity. But now, in the
loop quantum gravity this discrete model is not something we impose for simplicity problems but it is a real consequence of the theory.
Space is really quantised.

This three dimensional model is one of the simplest models of loop quantum gravity since it is a toy model in the physical sense. Moreover, we have introduced mathematical background
which is thoroughly used in many topics of loop quantum gravity.

We have described the model in a mathematical way as much as formal as we could. Our purpose is to introduce loop quantum gravity
to mathematicians or it could also be thought as a project in which we are introducing an approach to the field of loop quantum gravity
from a mathematical side; from the point of view of a mathematician.

We hope that the present work, article [6], and future writings from a mathematical point of view inspire mathematics and physics students as well as researchers in the field
to approach the subject of loop quantum gravity in a more rigorous mathematical way.

[1] Carlo Rovelli, Quantum Gravity, Cambridge Monographs on Mathematical Physics, Cambridge
University Press, 2004

[2] Carlo Rovelli, Francesca Vidotto, Covariant Loop Quantum Gravity: An Elementary
Introduction to Quantum Gravity and Spin Foam Theory, Cambridge University Press,

[3] Thomas Thiemann, Modern Canonical Quantum General Relativity, Cambridge Monographs on
Mathematical Physics, Cambridge
University Press, 2007

[4] Rodolfo Gambini, Jorge Pullin, A First Course in Loop Quantum Gravity, Oxford University Press,

[5] Alain Connes, Noncommutative Geometry, Academic Press, 1994

[6] J.Manuel García-Islas, Quantum Geometry I :
Basics of Loop Quantum Gravity .
The Quantum Polyhedra. Rev. Mex. Fis 65 (2019) 7-11

[7] Yvette Kosmann-Schwarzbach, Groups and Symmetries: From Finite Groups to Lie Groups, Universitext, Springer, 2010

[8] Brian C.Hall, Lie Groups, Lie Algebras and Representations: An Elementary Introduction,
Springer, Graduate Texts in Mathematics, 2015

[9] Jesús A. De Loera, Jörg Rambau, Francisco Santos, Triangulations : Structures for Algorithms and Applications,
Volume 25, Springer, 2010

[10] John Baez, An Introduction to Spin Foam Models of Quantum Gravity and BF Theory,
Lect. Notes Phys. 543, 25-94, 2000  arXiv:gr-qc/9905087

[11] Pierre Martin-Dussaud, A Primer of Group Theory for Loop Quantum Gravity and Spin-foams, arXiv:1902.08439 [math-ph]

[12] V. Turaev, O. Viro, State sum invariants of 3-manifolds and quantum6j-symbols, Topology 31 No.4,  865-902, 1992

[13] John W. Barrett, Ileana Naish-Guzman, The Ponzano-Regge model, Class.Quant.Grav. 26, 155014, 2009
arXiv:0803.3319 [gr-qc]

[14] Ponzano, G. Regge, Tulio, Semiclassical limit of Racah Coefficients, Spectroscopy and Group Theoretical Methods in Physics,
North-Holland, 1-58, 1968

[15] Carlo Rovelli, The basis of the Ponzano-Regge-Turaev-Viro-Ooguri model is the loop representation basis, Phys Rev D 48,
2702-2707, 1993. arXiv:math.ph:9304164v1


# Subshifts and colorings on ascending HNN-extensions of finitely generated
abelian groups

Eduardo Silva<EMAIL_ADDRESS>
###### Abstract.

For an ascending HNN-extension $G*_{\psi}$ of a finitely generated abelian
group $G$, we study how a synchronization between the geometry of the group
and weak periodicity of a configuration in $\mathcal{A}^{G*_{\psi}}$ forces
global constraints on it, as well as in subshifts containing it. A particular
case are Baumslag-Solitar groups $\mathrm{BS}(1,N)$, $N\geq 2$, for which our
results imply that a $\mathrm{BS}(1,N)$-SFT which contains a configuration
with period $a^{N^{\ell}}$, $\ell\geq 0$, must contain a strongly periodic
configuration with monochromatic $\mathbb{Z}$-sections. Then we study proper
$n$-colorings, $n\geq 3$, of the (right) Cayley graph of $\mathrm{BS}(1,N)$,
estimating the entropy of the associated subshift together with its mixing
properties. We prove that $\mathrm{BS}(1,N)$ admits a frozen $n$-coloring if
and only if $n=3$. We finally suggest generalizations of the latter results to
$n$-colorings of ascending HNN-extensions of finitely generated abelian
groups.

###### Key words and phrases:

symbolic dynamics, ascending HNN-extension, groups, Baumslag-Solitar,
subshifts of finite type, Cayley graphs, weak periodicity, frozen colorings,
topological entropy

##  1\. Introduction

The main object studied by symbolic dynamics on finitely generated groups are
$G$-subshifts, that is, closed subsets of the product space $\mathcal{A}^{G}$,
for $\mathcal{A}$ a finite discrete alphabet and $G$ a finitely generated
group, which are invariant under the action $\sigma$ of $G$ in
$\mathcal{A}^{G}$, called the shift and defined by

$\sigma_{g}(x)_{h}=x_{g^{-1}h}\text{ for }x\in\mathcal{A}^{G},\ g,h\in G.$

An important family of subshifts are subshifts of finite type (SFT), which are
those that can be described completely by a finite set of forbidden patterns.

Throughout the last decades there has been interest in the cases
$G=\mathbb{Z}^{d}$, $d\geq 2$, where a more complex structure arises in
comparison with the one-dimensional case $G=\mathbb{Z}$: questions which have
been long answered in the case $d=1$ become significantly more difficult for
$d\geq 2$, sometimes changing its veracity, or remaining as open problems to
this day. An example of this contrast is the so called Domino problem, which
asks whether, given a finite set of forbidden patterns, the corresponding SFT
is empty or not. For $d=1$ this problem is decidable, meanwhile for $d\geq 2$
it is undecidable.

In recent years interest has grown in studying symbolic dynamics on other
finitely generated groups, obtaining results in a general context as well as
in more particular settings, such as free groups or Baumslag-Solitar groups.

Given $m,n\in\mathbb{Z}\backslash\\{0\\}$, we define the corresponding
Baumslag-Solitar group as given by its standard presentation

$\mathrm{BS}(m,n)\coloneqq\langle a,b\mid ba^{m}b^{-1}=a^{n}\rangle.$

These groups were first introduced (though their origin might be older) in
[BS62] by G. Baumslag and D. Solitar, in order to provide an example of a non-
Hopfian group with two generators and one relator, namely, one which is
isomorphic to one of its (proper) quotient groups. Since then these groups
have gained attention in the fields of combinatorial group theory and
geometric group theory as examples and counterexamples of different properties
[Har03, Mes72], and more recently in the field of symbolic dynamics [AK13,
CFKP16, EM20].

The subfamily of Baumslag-Solitar groups $\mathrm{BS}(1,N)$, $N\geq 2$, is of
particular interest, since it exhibits nice properties in contrast with the
rest of Baumslag-Solitar groups. This subfamily actually comprises all the
cases for which the Baumslag-Solitar group is solvable, and hence amenable,
while still being non-abelian (the case $N=1$ gives
$\mathrm{BS}(1,1)\cong\mathbb{Z}^{2}$). In particular, this allows us to find
a Følner sequence which permits us to define a notion of topological entropy
for $\mathrm{BS}(1,N)$-subshifts. Actually, the above holds in a more general
framework: ascending HNN-extensions of finitely generated groups, which will
be our object of study throughout this paper.

In section 2 we introduce the basic concepts and notation used throughout this
work. We define the basic objects of symbolic dynamics and different notions
of periodicity, show how Baumslag-Solitar groups arise as HNN-extensions of
$\mathbb{Z}$ and explain the advantages of restricting ourselves to the case
of ascending HNN-extensions $G*_{\psi}$ of a finitely generated abelian group
$G$. Finally we describe the structure of the Cayley graph of $G*_{\psi}$,
which is formed by copies of $G$, which we call $G$-sections, connected
between them by the stable letter associated to the HNN-extension.

In section 3 we show how the geometry of $G*_{\psi}$ forces some rigidity for
configurations in the full $G*_{\psi}$-shift which exhibit weak periodicity in
the direction of a particular subgroup. Alternatively, how a synchronization
between the stabilizer of a configuration and the map defining the HNN-
extension forces rigidity in the global structure of the point. We show that a
periodicity of $\psi^{\ell}(H)$, for $H\leqslant G$ and $\ell\geq 0$, forces
sufficiently high $G$-sections to be $p$-periodic (Theorem 3.1). Moreover, we
show how having such a configuration affects a $G*_{\psi}$-subshift which
contains it (Theorem 3.3).

######  Theorem 1.1.

Let $x\in\mathcal{A}^{G*_{\psi}}$ and suppose there exists a subgroup
$H\leqslant G$ with $\psi(H)\leqslant H$ and $\ell\geq 0$ such that
$\psi^{\ell}(H)\leqslant\mathrm{Stab}(x)$. Then

  1. (1)

all $G$-sections of level greater or equal than $\ell$ are $H$-periodic,

  2. (2)

if $X$ is a $G*_{\psi}$-subshift which contains the configuration $x$, then
there exists $y\in X$ for which all $G$-sections are $H$-periodic, and

  3. (3)

if $X$ is further assumed to be an SFT and $H=G$, then $y$ can be chosen to be
strongly periodic.

In particular for the Baumslag-Solitar group $\mathrm{BS}(1,N)$, $N\geq 2$,
Theorem 1.1 implies that any configuration
$x\in\mathcal{A}^{\mathrm{BS}(1,N)}$ such that $\sigma_{a^{pN^{\ell}}}(x)=x$
has sufficiently high $p$-periodic $\mathbb{Z}$-sections. Moreover, any
$\mathrm{BS}(1,N)$-subshift $X$ containing such a configuration contains one
in which all $\mathbb{Z}$-sections are $p$-periodic, and if $X$ is an SFT and
$p=1$, then it contains a strongly periodic configuration with monochromatic
$\mathbb{Z}$-sections.

Given a group $G$ generated by a finite subset $S\subseteq G$ it is
interesting to study the dynamical properties of proper colorings (in the
sense used commonly in graph theory) of its Cayley graph. We define for $n\geq
2$ the graph-coloring subshift (GCS)

$\mathcal{C}_{n}\coloneqq\left\\{x\in\\{0,\ldots,n-1\\}^{G}\mid\text{ for all
}g\in G,s\in S:\ x_{g}\neq x_{gs}\right\\},$

that is, each configuration $x\in\mathcal{C}_{n}$ describes a proper
$n$-coloring of the Cayley graph $\Gamma(G,S)$ of $G$ with respect to the
generator $S$.

Proper $n$-colorings of $G=\mathbb{Z}^{2}$, or more generally
$G=\mathbb{Z}^{d}$ for $d\geq 2$, have been studied recently [ABC+19, PS18,
RS20]. In particular, in [ABC+19] the authors study mixing properties for
colorings of $\mathbb{Z}^{d}$, $d\geq 2$, introducing the notion of a frozen
$n$-coloring of $\mathbb{Z}^{d}$ as an n-coloring which cannot be modified on
a finite subset to create a different coloring, and prove that
$\mathbb{Z}^{d}$ admits frozen $n$-colorings if and only if $2\leq n\leq d+1$.

In section 4 we consider the GCS $\mathcal{C}_{n}$ in $\mathrm{BS}(1,N)$ and,
among other results regarding extensibility of patterns and mixing properties,
we show explicit constructions of frozen $3$-colorings in $\mathrm{BS}(1,N)$
(Theorem 4.7), and then prove the lack of frozen $n$-colorings for every
$n\geq 4$ (Theorem 4.9).

######  Theorem 1.2.

For $n\geq 3$, the GCS
$\mathcal{C}_{n}\subseteq\\{0,\ldots,n-1\\}^{\mathrm{BS}(1,N)}$ contains a
frozen coloring if and only if $n=3$.

Another question of interest for $n$-colorings of a group $G$ is to estimate
in how many different ways one can (properly) color a finite set, that is, the
amount of patterns of $\mathcal{C}_{n}$ with a fixed (finite) support. The
answer to this question, in turn, allows us to give estimates for the
topological entropy of $\mathcal{C}_{n}$. This is a rather difficult question
even when restricting the attention to $\mathbb{Z}^{2}$ and in general there
are no closed formulas for any of these numbers, except for some exceptions as
is the case of topological entropy of $3$-colorings of $\mathbb{Z}^{2}$, known
to be $\frac{3}{2}\log\frac{4}{3}$ [Lie67].

The last results of this section provide bounds for the topological entropy of
the GCS $\mathcal{C}_{n}$ in $\mathrm{BS}(1,N)$ (Theorem 4.10), as well as
showing that the topological entropy of $\mathcal{C}_{3}$ is positive (Theorem
4.11).

######  Theorem 1.3.

For $n\geq 3$, the GCS
$\mathcal{C}_{n}\subseteq\\{0,\ldots,n-1\\}^{\mathrm{BS}(1,N)}$ satisfies

$\log(n-2)\leq h_{\mathrm{top}}(\mathcal{C}_{n})\leq\log(n-1).$

We also have that $h_{\mathrm{top}}(\mathcal{C}_{3})>0$. In fact, we further
have that

  1. (1)

if $N$ is odd then $h_{\mathrm{top}}(\mathcal{C}_{3})\geq\frac{1}{2}\log 2$,
and

  2. (2)

if $N$ is even then
$h_{\mathrm{top}}(\mathcal{C}_{3})\geq\frac{1}{2(2N+1)}\log 2$.

Finally in Section 5 we make some comments and questions about possible
generalizations of the above results to the case of $n$-colorings of general
ascending HNN-extensions of finitely generated abelian groups.

##  2\. Preliminaries

###  2.1. Symbolic dynamics on finitely generated groups

Let $G$ be a finitely generated group and $\mathcal{A}$ be a finite (discrete)
set. Given $F\subseteq G$ finite, we call and element $p\in\mathcal{A}^{F}$ a
pattern, $F$ its support, and use the notation $\mathrm{supp}(p)\coloneqq F$.
Given patterns $p,q$, we say that $p$ is a subpattern of $q$, denoted
$p\sqsubseteq q$, if there exists $g\in G$ such that
$p=q|_{g\cdot\mathrm{supp}(p)}$. An element $x\in\mathcal{A}^{G}$ is called a
configuration or coloring, and we use the notation $x_{g}\coloneqq x(g)$,
$g\in G$. The set $\mathcal{A}^{G}$ can be endowed with the product topology,
which is metrizable, compact and has a base given by the cylinders, that is,
sets of the form

$[p]=\\{x\in\mathcal{A}^{G}\mid x|_{\mathrm{supp}(p)}=p\\},\ p\text{ a
pattern}.$

The topological space $\mathcal{A}^{G}$ together with the left $G$-action by
homeomorphisms

$\displaystyle\sigma:G$
$\displaystyle\to\mathrm{Homeo}(\mathcal{A}^{G},\mathcal{A}^{G})$
$\displaystyle g$ $\displaystyle\mapsto\sigma_{g},$

where for every $x\in\mathcal{A}^{G}$, $g,h\in G$:

$\sigma_{g}(x)_{h}=x_{g^{-1}h},$

is called the full $G$-shift and $\sigma$ is called the shift map. Associated
to this action, we define for a configuration $x\in\mathcal{A}^{G}$ its orbit

$\mathrm{Orb}(x)\coloneqq\\{\sigma_{g}(x)\mid g\in G\\},$

and its stabilizer

$\mathrm{Stab}(x)\coloneqq\\{g\in G\mid\sigma_{g}(x)=x\\}.$

The latter of these sets is in fact a subgroup of $G$, and we have the
relation $|\mathrm{Orb}(x)|=|G:\mathrm{Stab}(x)|$. A configuration
$x\in\mathcal{A}^{G}$ is said to be weakly periodic if $\mathrm{Stab}(x)$
contains an infinite cyclic group, and strongly periodic if
$|\mathrm{Orb}(x)|<\infty$.

A subset $X\subseteq\mathcal{A}^{G}$ is called a $G$-subshift if it is closed
and $\sigma$-invariant, that is, for every $g\in G$: $\sigma_{g}(X)=X$.
Equivalently, $X$ is a $G$-subshift if there exists a family $\mathcal{F}$ of
(forbidden) patterns such that

$X=\\{x\in\mathcal{A}^{G}\mid\text{ for every }F\subseteq G\text{ finite:
}x|_{F}\notin\mathcal{F}\\}.$

If such a family can be chosen to be finite we say that $X$ is a $G$-subshift
of finite type (SFT).

Given a $G$-subshift $X\subseteq\mathcal{A}^{G}$ described by a family
$\mathcal{F}$ of (forbidden) patterns, we say that a pattern $p$ is locally
admissible if $p$ does not contain elements of $\mathcal{F}$ a subpatterns,
and globally admissible if there exists an $x\in X$ such that
$x|_{\mathrm{supp}(p)}=p$.

In the case where $G$ is amenable, we can define the topological entropy of a
$G$-subshift $X$ as

$h_{\mathrm{top}}(X)\coloneqq\lim_{n\to\infty}\frac{\log|\mathcal{L}_{F_{n}}(X)|}{|F_{n}|},$

where $\\{F_{n}\\}_{n\in\mathbb{N}}$ is a Følner sequence and
$\mathcal{L}_{F_{n}}(X)=\\{x|_{F_{n}}\mid x\in X\\}$. This limit always exists
and it does not depend on the Følner sequence chosen [KL16, Theorem 4.38].
Intuitively, the topological entropy of a $G$-subshift $X$ represents the rate
of exponential growth at which the amount of patterns with support $F_{n}$ we
see in the elements of $X$ increases as these sets become more and more
invariant.

###  2.2. HNN-extensions and Baumslag-Solitar groups

Consider a group $G$ and two isomorphic subgroups $H,K\leq G$. The HNN-
extension111The letters “HNN” stands for Higman, Neumann and Neumann, who
introduced this kind of extension in [HNN49]. $G*_{\psi}$ defined below is
intuitively a form of constructing a group which contains a copy of $G$, on
which $H$ and $K$ are conjugate subgroups.

######  Definition 2.1.

Consider a group $G$ with a presentation $\langle S\left|\right.R\rangle$ and
two isomorphic subgroups $H,K\leq G$, with $\psi:K\to H$ an isomorphism. We
define the HNN-extension of $G$ with respect to $\psi$ by the presentation

$G*_{\psi}\coloneqq\langle
S\cup\\{t\\}\left|\right.R\cup\\{tkt^{-1}=\psi(k):k\in K\\}\rangle.$

We will say that $G$ is the base group, and that $H$ and $K$ are the subgroups
conjugated in $G*_{\psi}$. We also call the generator $t$ the stable letter.

Thanks to the relations of $G*_{\psi}$, for every $k\in K$ and $h\in H$ we
have that $tk=\psi(k)t$ and $\psi^{-1}(h)t^{-1}=t^{-1}h$, which allows us to
choose in which order the elements of $G$ appear with respect to $t$ or
$t^{-1}$. By using this property, we can find a rather simple normal form for
the HNN-extension $G*_{\psi}$, as the next proposition shows.

######  Proposition 2.1 (Britton’s Lemma [LS77, Theorem IV.2.1]).

Let $G$ be a group, $H,K\leq G$ and $\psi:K\to H$ an isomorphism. Choose
classes of representatives $T_{H}$ and $T_{K}$ of the right cosets for $H$ and
$K$ in $G$, respectively, such that $T_{H}$ and $T_{K}$ both contain the
identity element $e_{G}$. Then the HNN-extension $G*_{\psi}$ has a normal form
given by the set of words of the form
$g_{0}t^{\varepsilon_{1}}g_{1}t^{\varepsilon_{2}}\ldots
t^{\varepsilon_{n}}g_{n}$ for $n\geq 0$, $g_{0}\in G$ and
$\varepsilon_{i}\in\\{+1,-1\\}$ for $i=1,\ldots,n$, such that

  1. (1)

$\varepsilon_{i}=1$ implies $g_{i}\in T_{K}$,

  2. (2)

$\varepsilon_{i}=-1$ implies $g_{i}\in T_{H}$ and

  3. (3)

there is no subword of the form $t^{\varepsilon}e_{G}t^{-\varepsilon}$, for
$\varepsilon\in\\{+1,-1\\}$.

An important example of HNN-extensions are Baumslag-Solitar groups: given non-
zero integers $m,n\in\mathbb{Z}\backslash\\{0\\}$ we define the group

$\mathrm{BS}(m,n)=\langle a,b\left|\right.ba^{m}b^{-1}=a^{n}\rangle,$

which is an HNN-extension of $\mathbb{Z}$ via the isomorphism $\psi:\langle
a^{m}\rangle\to\langle a^{n}\rangle$ defined by $\psi(a^{m})=a^{n}$. When
$|m|=1$, these groups form part of a special class of HNN-extensions:

######  Definition 2.2.

Given a group $G$ and a monomorphism $\psi:G\to G$, we say that $G*_{\psi}$ is
an ascending HNN-extension.

Throughout the rest of this work we center our attention in ascending HNN-
extensions $G*_{\psi}$ having a finitely generated abelian base group $G$, on
which the monomorphism $\psi$ is not trivial. The main example for our results
are the Baumslag-Solitar groups $\mathrm{BS}(1,N)$ for $N\geq 2$.

Restricting ourselves to this subfamily of HNN-extensions has many advantages:
we have useful commuting relations between the elements of the group, a
simpler normal form (in contrast to the general one given by Britton’s lemma)
and a simpler understanding of the geometric structure Cayley graph of the
group, all of which we describe in further detail below.

First we establish the following lemma, which summarizes some of the
consequences induced by the defining relations used in the standard
presentation of $G*_{\psi}$. Its elementary proof is by induction and is
omitted.

######  Lemma 2.2.

Under the above hypotheses and the presentation of $G*_{\psi}$ from Definition
2.1, for $g\in G$ and $j\geq 0$ we have $t^{j}g=\psi^{j}(g)t^{j},$ where
$\psi^{j}$ denotes the composition of $\psi$ with itself $j$ times.

######  Proposition 2.3.

Let $G$ be a finitely generated abelian group, $\psi:G\to G$ a monomorphism.
The ascending HNN-extension $G*_{\psi}$ has a normal form given by words of
the form $t^{-j}gt^{i}$, where $i,j\geq 0$, $g\in G$, and $g\in\psi(G)$ is
possible only if $i=0$ or $j=0$.

###### Proof.

Using the normal form for HNN-extensions described in Proposition 2.1 with
$T_{K}=\\{e_{G}\\}$ and $T_{H}$ a set of representatives of $\psi(G)$, we
distinguish three types of words.

  1. 1.

The first type are words of the form $gt^{i}$, $g\in G$, $i\geq 0$. This is
already a word of the form described in the proposition.

  2. 2.

The second type are words of the form $g_{0}t^{-1}g_{1}\cdots t^{-1}g_{n},$
where $g_{0}\in G,\ g_{1},\ldots,g_{n}\in T_{H}.$ We will prove that we can
arrive at a word of the form described in the proposition by induction.
Moreover, we will show that there exists $\tilde{g}\in G$ such that

$g_{0}t^{-1}g_{1}\cdots t^{-1}g_{n}=t^{-n}\psi(\tilde{g})g_{n}.$

If $n=1$, then $g_{0}t^{-1}g_{1}=t^{-1}\psi(g_{0})g_{1}$.

In the general case, for $n\geq 2$, the induction hypothesis gives us the
existence if $\tilde{g}\in G$ such that

$g_{0}t^{-1}g_{1}\cdots t^{-1}g_{n-1}=t^{-(n-1)}\psi(\tilde{g})g_{n-1}.$

Then

$\displaystyle g_{0}t^{-1}g_{1}\cdots t^{-1}g_{n-1}t^{-1}g_{n}$
$\displaystyle=t^{-(n-1)}\psi(\tilde{g})g_{n-1}t^{-1}g_{n}$
$\displaystyle=t^{-(n-1)}\psi(\tilde{g})t^{-1}\psi(g_{n-1})g_{n}$
$\displaystyle=t^{-n}\psi(\psi(\tilde{g})g_{n-1})g_{n},$

finishing the induction.

  3. 3.

Finally, the third possible type of words are of the form
$g_{0}t^{-1}g_{1}\cdots t^{-1}g_{n}t^{j},\text{ where}\ g_{0}\in G,\
g_{1},\ldots,g_{n}\in T_{H},\ j\geq 1.$ As in the previous case, it is
possible to prove that there exists $\tilde{g}\in G$ such that

$g_{0}t^{-1}g_{1}\cdots t^{-1}g_{n}t^{j}=t^{-n}\psi(\tilde{g})g_{n}t^{j}.$

Note that as $j\geq 1$, the third condition from Proposition 2.1 ensures that
$g_{n}\neq e_{G}$ (since otherwise the considered word would contain a subword
of the form $t^{-1}e_{G}t$), and hence $\psi(\tilde{g})g_{n}\notin\psi(G)$.

∎

An ascending HNN-extension $G*_{\psi}$ whose base group $G$ is a finitely
generated abelian group is amenable. We exhibit an explicit Følner sequence in
the case of Baumslag-Solitar groups, which will be useful in the study of
graph-coloring subshifts below. In particular, we will use this sequence to
compute topological entropy in $\mathrm{BS}(1,N)$-subshifts.

######  Proposition 2.4.

Consider the Baumslag-Solitar group $\mathrm{BS}(1,N)$, $N\geq 2$. Define for
$m\geq 1$ the rectangle of height $m$

$R_{m}\coloneqq\\{a^{k}b^{i}\mid 0\leq k<N^{m},\ 0\leq
i<m\\}\subseteq\mathrm{BS}(1,N).$

Then $\\{R_{m}\\}_{m\geq 1}$ forms a Følner sequence in $\mathrm{BS}(1,N)$.

###  2.3. The Cayley graph

To finish this section let us take a look at the structure of the Cayley graph
of ascending HNN-extensions of finitely generated abelian groups, in
particular that of $\mathrm{BS}(1,N)$, $N\geq 2$.

Recall that given a group $G$ together with a finite generating set
$S\subseteq G$, the (right) Cayley graph of $G$ with respect to $S$ is the
labeled directed graph $\Gamma(G,S)=(V_{\Gamma},E_{\Gamma},\lambda_{\Gamma})$
where

  1. (1)

the set of vertices is $V_{\Gamma}=G$,

  2. (2)

the set of edges is $E_{\Gamma}=\\{(g,gs)\in G\times G\mid s\in S\\}$, and

  3. (3)

the labeling function $\lambda_{\Gamma}:E_{\Gamma}\to V_{\Gamma}$ satisfies
$\lambda_{\Gamma}(g,gs)=s$, for $g\in G$, $s\in S$.

A section of the Cayley graph of $\mathrm{BS}(1,N)$ with respect to the
generating set $S=\\{a,b\\}$ is shown in Figure 1, where we see that its
structure is that of rows (along the edges labeled by the $a$-generator) being
arranged (in a sideways view) as an N-ary tree. Seen from the front, each row
has below it (i.e. in the $b^{-1}$-direction) a unique $\mathbb{Z}$-section,
and above it (i.e. in the $b$-direction) $N$ new $\mathbb{Z}$-sections. More
formally, defining $A\coloneqq\\{a^{k}\mid k\in\mathbb{Z}\\}$, a set of the
form $gA$ for $g\in\mathrm{BS}(1,N)$ will be called an $\mathbf{a}$-row of the
Cayley graph of $\mathrm{BS}(1,N)$, meanwhile a set of the form
$\displaystyle\bigcup_{n=1}^{\infty}gb^{-n}A\cup\bigcup_{n=0}^{\infty}\left(g\prod_{s=1}^{n}(a^{i_{s}}b)A\right)$
for $g\in\mathrm{BS}(1,N)$ and a sequence
$\\{i_{s}\\}_{s=1}^{\infty}\in\\{0,\ldots,N-1\\}^{\mathbb{N}}$ will be called
a sheet of the Cayley graph of $\mathrm{BS}(1,N)$. An example of the latter is
illustrated in Figure 2.

In the drawings of the Cayley graph of $\mathrm{BS}(1,N)$ made in the next
sections we will omit the label as well as the direction of the edges from the
drawing, as they are not relevant for the context they are used in.

The case of the Cayley graph of an ascending HNN-extension $G*_{\psi}$ of a
finitely generated abelian group is similar to the one described above: it is
composed of copies of the Cayley graph of $G$ connected through the stable
letter $t$, in such a way that each one of them has above it $|G:\psi(G)|$
copies of itself. We call these copies of $G$ the $G$-sections of the Cayley
graph.

We finish this section by making the following definition, which enables us to
enunciate the results of the next section in a clearer way.

######  Definition 2.3.

For $h\in G$ we define the $G$-section containing $h$ as

$\Gamma_{h}\coloneqq\\{hg\mid g\in G\\}.$

Using the normal form from Proposition 2.3 we can write $h=t^{-j}gt^{i}$, for
$i,j\geq 0$, $g\in G$. In this case we say that $\Gamma_{h}$ is a $G$-section
of level $i-j$. Note that thanks to the uniqueness of the normal form, the
value $i-j$ is well defined for $h$.

Figure 1. A section of the Cayley graph of $BS(1,2)$.
$\vdots$$\vdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\vdots$$\vdots$$\vdots$
Figure 2. A section of a sheet of the Cayley graph of $BS(1,2)$. Horizontal
edges are labeled with “$a$”, while vertical edges are labeled with “$b$”.

##  3\. Periodicity constraints

Consider $G$ a finitely generated abelian group and $G*_{\psi}$ an ascending
HNN-extension. This section focuses on studying how (weakly) periodic
configurations on $\mathcal{A}^{G*_{\psi}}$ exhibit some rigidity when their
stabilizer and the structure of the Cayley graph of the group synchronize in
some sense. In particular, we will study $G$-periodic configurations and
obtain results regarding the structure of their $G$-sections.

######  Proposition 3.1.

Suppose there exists $x\in\mathcal{A}^{G*_{\psi}}$, $H\leqslant G$ with
$\psi(H)\leqslant H$ and $\ell\geq 0$ such that
$\psi^{\ell}(H)\leqslant\mathrm{Stab}(x)$. Then all $G$-sections of level
greater or equal than $\ell$ are $H$-periodic.

In the case $H=G$, $x$ assigns the same symbol to all $G$-sections of the same
level sharing a common $G$-section of level greater or equal than $\ell$.

###### Proof.

Consider $x\in\mathcal{A}^{G*_{\psi}}$ as above, so that

$\sigma_{\psi^{\ell}(h)}(x)=x,\ \text{for all }h\in H.$ (1)

It suffices to prove that for any $i,j\geq 0$, $g\in G$ and $h\in H$ we have
that

$x_{t^{-j}gt^{i+j+\ell}h}=x_{t^{-j}gt^{i+j+\ell}}.$ (2)

In effect, note that using Lemma 2.2 and commutativity of $G$ we have that

$\displaystyle t^{-j}gt^{i+j+\ell}h$
$\displaystyle=t^{-j}g\psi^{i+j+\ell}(h)t^{i+j+\ell}$
$\displaystyle=t^{-j}\psi^{i+j+\ell}(h)gt^{i+j+\ell}$
$\displaystyle=\psi^{i+\ell}(h)t^{-j}gt^{i+j+\ell}$
$\displaystyle=\psi^{\ell}(\psi^{i}(h))t^{-j}gt^{i+j+\ell}.$

As $\psi^{i}(h)\in H$ thanks to the hypothesis, Equation (2) follows from
Equation (1).

For the second part of the proposition, it suffices to prove that for any
$i,j,h\geq 0$ and $g,\tilde{g}\in G$ we have

$x_{t^{-j}gt^{i+j+\ell+h}}=x_{t^{-j}ht^{i+j+\ell}\tilde{g}t^{h}}.$

Again using commutativity of $G$ and Lemma 2.2 we have

$\displaystyle t^{-j}gt^{i+j+\ell}t^{h}$
$\displaystyle=t^{-j}g\psi^{i+j+\ell}(\tilde{g})t^{i+j+\ell+h}$
$\displaystyle=t^{-j}\psi^{i+j+\ell}(\tilde{g})gt^{i+j+\ell+h}$
$\displaystyle=\psi^{i+\ell}(\tilde{g})t^{-j}gt^{i+j+\ell+h},$

and the statement follows from $x$ being $\psi^{\ell}(G)$-periodic. ∎

######  Corollary 3.2.

Let $x\in\mathcal{A}^{G*_{\psi}}$ be a strongly periodic configuration, and
suppose there exist $H\leqslant G$ with $\psi(H)\leqslant H$ and $\ell\geq 0$
such that $\psi^{\ell}(H)\leqslant\mathrm{Stab}(x)$. Then all $G$-sections of
$x$ are $H$-periodic.

###### Proof.

Since $x$ is strongly periodic, it has a finite orbit under the action of
$G*_{\psi}$, so in particular the set $\\{\sigma_{t^{-q}}(x):q\geq 1\\}$ is
finite. Hence there exists a sequence of increasing positive integers
$\\{q_{n}\\}_{n\geq 1}$ such that for every $n\geq 1$

$\sigma_{t^{-q_{1}}}(x)=\sigma_{t^{-q_{n}}}(x),$

or equivalently

$\sigma_{t^{q_{1}-q_{n}}}(x)=x.$

By taking $n$ sufficiently large, $b^{q_{n}-q_{1}}g$ will form part of a
$G$-section of level greater or equal than $\ell$. Then using Proposition 3.1
we see that for $g\in G$ and $h\in H$:

$\displaystyle x_{g}$ $\displaystyle=(\sigma_{t^{q_{1}-q_{n}}}(x))_{g}$
$\displaystyle=x_{t^{q_{n}-q_{1}}g}$ $\displaystyle=x_{t^{q_{n}-q_{1}}gh}$
$\displaystyle=\sigma_{t^{q_{1}-q_{n}}}(x)_{gh}$ $\displaystyle=x_{gh}.$

Hence every $G$-section in $x$ is $H$-periodic. ∎

The behavior observed in the previous theorems is not only related to the
configurations appearing on the hypotheses, but also to $G*_{\psi}$-subshifts
which contain them. In the following theorem we see how for a
$G*_{\psi}$-subshift $X$, having such a weakly periodic configuration as above
implies having one with a global structure of $H$-periodic $G$-sections, as
well as the existence of strongly periodic configurations with this property
for SFTs in the case $H=G$.

######  Theorem 3.3.

Let $x\in\mathcal{A}^{G*_{\psi}}$ be a strongly periodic configuration, and
suppose there exist $H\leqslant G$ with $\psi(H)\leqslant H$ and $\ell\geq 0$
such that $\psi^{\ell}(H)\leqslant\mathrm{Stab}(x)$. Then there exists a
configuration $y\in X$ such that all its $G$-sections are $H$-periodic. In
particular if $H=G$ and $X$ is an SFT, then $X$ contains a strongly periodic
configuration for which each of its $G$-sections is monochromatic, that is,
$x$ assigns the same symbol to all of their elements, and $G$-sections of the
same level share the same symbol.

###### Proof.

Thanks to Proposition 3.1 we have that all $G$-sections at a level greater or
equal than $\ell$ in $x$ are $H$-periodic. We define for each $n\geq 1$ the
configuration $x^{n}\coloneqq\sigma_{t^{-n}}(x)\in X$ and choose $y\in X$ to
be a limit point of the sequence $\\{x^{n}\\}_{n\in\mathbb{N}}$, which exists
by compactness of $X$.

As each $G$-section at a sufficiently high level of $x$ is $G$-periodic, the
construction of the sequence $\\{x^{n}\\}_{n\in\mathbb{N}}$ immediately shows
that $y$ satisfies the required properties.

Now suppose that $H=G$ and that $X$ is an SFT. As periodicity is preserved
through a conjugacy map, we may suppose without loss of generality that $X$ is
nearest neighbors SFT. Considering the configuration $y\in X$ from above, by
our extra hypothesis of $H=G$ all $G$-sections of $y$ are monochromatic (since
they are $G$-periodic), and $G$-sections of the same level are equal.

Using the pigeonhole principle, there must exist a $G$-section of some level
$i$ and $h\geq 1$ such that itself together with all $G$-sections of level
$i+h$ having the former as a common base share the same symbol. Using the fact
that $X$ is a nearest neighbors SFT, we can glue copies of these sections to
cover the Cayley graph of $G$ and obtain a strongly periodic configuration
$z\in X$.

∎

######  Remark.

Having all $G$-sections monochromatic is not by itself a sufficient condition
for a configuration $x\in\mathcal{A}^{G*_{\psi}}$ to be strongly periodic. For
example, in the case $G*_{\psi}=\mathrm{BS}(1,N)$ we can construct an example
of such a configuration by considering a non-periodic sequence
$z\in\mathcal{A}^{\mathbb{Z}}$ and define $x\in
x\in\mathcal{A}^{\mathrm{BS}(1,N)}$ to consist of monochromatic
$\mathbb{Z}$-sections whose symbols are defined according to the sequence $z$.
Figure 3 shows a sideways view of the Cayley graph of $\mathrm{BS}(1,N)$,
where each symbol in this figure represents the symbol of the entire
$\mathbb{Z}$-section at that level in $x$.

$z_{-2}$$z_{-1}$$z_{0}$$z_{1}$$z_{2}$$\vdots$$z_{2}$$\vdots$$z_{1}$$z_{2}$$\vdots$$z_{2}$$\vdots$$z_{0}$$z_{1}$$z_{2}$$\vdots$$z_{2}$$\vdots$$z_{1}$$z_{2}$$\vdots$$z_{2}$$\vdots$$\vdots$
Figure 3. Illustration of a configuration in a sideways view of the Cayley
graph of $\mathrm{BS}(1,N)$, having all $\mathbb{Z}$-sections monochromatic
but not being strongly periodic.

##  4\. Graph-coloring subshifts

Given a group $G$ generated by a finite subset $S\subseteq G$, we define for
$n\geq 2$ the graph-coloring subshift (GCS)

$\mathcal{C}_{n}\coloneqq\left\\{x\in\\{0,\ldots,n-1\\}^{G}\mid\text{ for all
}g\in G,s\in S:\ x_{g}\neq x_{gs}\right\\}.$

That is, each configuration $x\in\mathcal{C}_{n}$ describes a proper
$n$-coloring of the Cayley graph $\Gamma(G,S)$ of $G$ with respect to the
generating set $S$. In what follows we consider the GCS in $n\geq 2$ colors
for $\mathrm{BS}(1,N)$ generated by the standard set $S=\\{a,b\\}$.

In this section we study some dynamical properties of graph-coloring subshifts
on $\mathrm{BS}(1,N)$, namely mixing conditions and estimates of their
entropy, among others. We restrict ourselves to the case of Baumslag-Solitar
groups rather than working in the general setting of ascending HNN-extensions
of finitely generated abelian groups, since the linear structure of the base
group allows for rather simple constructions and results.

######  Proposition 4.1.

If $N$ is odd $\mathcal{C}_{2}\neq\varnothing$, and if $N$ is even then
$\mathcal{C}_{2}=\varnothing$ meanwhile $\mathcal{C}_{3}\neq\varnothing$. In
particular, independent of the parity of $N$, for every $n\geq 3$ we have
$\mathcal{C}_{n}\neq\varnothing$.

###### Proof.

Let us see first that if $N$ is even then $\mathcal{C}_{2}=\varnothing$. To
see this suppose we have $x\in\mathcal{C}_{2}$ and without loss of generality
let us suppose that $x_{e_{\mathrm{BS}(1,N)}}=0$. Then by the coloring rules
we must have $x_{a^{N}}=0$, and $x_{b}=x_{a^{N}b}=1$, but this cannot be since
$x_{a^{N}b}=x_{ba}$, so the neighboring vertices $b$ and $ba$ have the same
color and this contradicts the GCS’s definition.

Now let us show that if $N$ is odd then $\mathcal{C}_{2}\neq\varnothing$.
Moreover, we will show that in fact $|\mathcal{C}_{2}|=2$. To create a point
$x\in\mathcal{C}_{2}$ let us impose that $x_{e_{\mathrm{BS}(1,N)}}=0$, and
define for every $g\in\mathrm{BS}(1,N)$ expressed in its normal form
$g=b^{-j}a^{k}b^{i}$ with $i,j\geq 0$ and $k\in\mathbb{Z}$: $x_{g}=i+j+k\mod
2$. We check that this provides a consistent coloring of the Cayley graph: for
$g$ as above and a generator $s\in\\{a,b\\}$, the normal form of $gs$ is given
by

$ga=b^{-j}a^{k+N^{i}}b^{i},$

if $s=a$ and

$gb=b^{-j}a^{k}b^{i+1},$

if $s=b$. Then $x_{ga}=i+j+k+N^{i}\mod 2$ and $x_{gb}=i+1+j+k\mod 2$, and as
$N$ is odd we see that $x_{ga}\neq x_{g}$ and $x_{gb}\neq x_{g}$. With this,
neighboring elements in the graph have different colors and hence $x$ forms a
valid configuration in $\mathcal{C}_{2}$. Also note that this point is
completely determined by our choice of $x_{e_{\mathrm{BS}(1,N)}}=0.$ If we had
chosen instead $x_{e_{\mathrm{BS}(1,N)}}=1$, we would have obtained the same
configuration as above, but with $0$’s and $1$’s interchanged, thus we
conclude that $|\mathcal{C}_{2}|=2$.

Let us see now that for $N$ even we have $\mathcal{C}_{3}\neq\varnothing$. For
this notice first that if we have an $\mathbb{Z}$-section
$\Gamma_{g}\coloneqq\\{ga^{k}:k\in\mathbb{Z}\\},g\in G$ colored consistently
with the coloring rules using two colors, i.e. the two colors strictly
alternate along $\Gamma_{g}$, then we can color each row directly above it
respecting the coloring rules: as $\Gamma_{g}$ is colored with two colors and
$N$ is even, then every row directly above it only sees one color through its
edges connecting it to $\Gamma_{g}$, so if we choose the two remaining colors
we can color this new row consistently. On the other hand note that if
$\Gamma_{g}$ is colored consistently, we can also color the row exactly below
it: as $\Gamma_{g}$ is colored with two colors we can color the vertices below
it with the remaining color in $\\{0,1,2\\}$, and as $N$ is even we can choose
any other color and fill the gaps consistently between the already colored
vertices on this new row, alternating those two colors.

With the two previous facts it is easy to see that one can construct
inductively a point in $\mathcal{C}_{3}$. Hence
$\mathcal{C}_{3}\neq\varnothing$.

The final statement of the proposition follows from the fact that if $n>3$,
then $\mathcal{C}_{n}$ contains a copy of $\mathcal{C}_{n-1}$ by simply
considering colorings with a smaller palette of colors. ∎

###  4.1. Extensibility of patterns

In the case of $2$-colorings of $\mathrm{BS}(1,N)$ the subshift
$\mathcal{C}_{2}$ is finite (it is either empty or has two configurations, if
$N$ is even or odd, respectively) so the configurations appearing in it are
somewhat rigid and admit very few different ways of coloring the Cayley graph.
This leads us to ask how many ways to color are there in the case of $n\geq
3$, and with it be able to estimate topological entropy
$h_{\mathrm{top}}(\mathcal{C}_{n})$.

In order to do this, we will first tackle the question of extending colorings
of a finite subset of the Cayley graph to bigger patterns containing it. In
the language of symbolic dynamics this question is the same as asking if in
$\mathcal{C}_{n}$ locally admissible patterns are globally admissible, or
under which conditions on the pattern we can ensure this. A first result in
this direction answers the question affirmatively, subject to having a minimum
of available colors.

######  Proposition 4.2.

For $n\geq 5$, every locally admissible pattern $p$ of $\mathcal{C}_{n}$ is
globally admissible.

###### Proof.

This follows from the fact that for a finite graph, its chromatic number is
less than its maximum degree. Since every finite subgraph of the Cayley graph
of $\mathrm{BS}(1,N)$ has maximum degree at most $4$, then the considered
pattern can be extended to any finite graph containing it by choosing for each
vertex a color that none of its neighbors has, and thus preserving the
coloring rules. This process can then be iterated indefinitely to finally
obtain a configuration $x\in\mathcal{C}_{n}$ such that
$x|_{\mathrm{supp}(p)}=p$.

More formally, given a locally admissible pattern $p$ with support $S$ we
define a point $x^{0}\in\\{0,\ldots,n-1\\}^{\mathrm{BS}(1,N)}$ such that
$x^{0}|_{S}=p$. We define $S_{1}$ to be $S$ together with all vertices that
are adjacent to it, and define $x^{1}\in\\{0,\ldots,n-1\\}^{\mathrm{BS}(1,N)}$
such that $x^{1}|_{S}=x^{0}|_{S}$ and the rest of the vertices of $S_{1}$ are
colored respecting the coloring rules as said above, that is, using the fact
that each vertex $S_{1}\backslash S$ has at most $4$ neighbors already
colored, so there is always an available color. Inductively, for $j\geq 1$, to
define $x^{j+1}$ we define $S_{j+1}$ to be $S_{j}$ together with all vertices
that are adjacent to it, and define
$x^{j+1}\in\\{0,\ldots,n-1\\}^{\mathrm{BS}(1,N)}$ such that
$x^{j+1}|_{S_{j}}=x^{j}|_{S_{j}}$ and the rest of the vertices of $S_{j+1}$
are colored as said above. By compactness we find a limit point $\overline{x}$
of $\\{x^{j}\\}_{j\geq 0}$, and by how we constructed this sequence we see
that each vertex is properly colored and so $\overline{x}\in\mathcal{C}_{n}$.
∎

######  Remark.

The previous proposition does not hold for $n\in\\{3,4\\}$. For example the
locally admissible pattern in $\mathrm{BS}(1,2)$ in Figure 4 cannot be
realized within a point $x\in\mathcal{C}_{4}$ since no color can be assigned
to the vertex with an interrogation sign, while respecting the coloring rules.

$?$$3$$0$$1$$2$$1$$0$$3$$2$$3$$0$$1$$3$$2$$0$ Figure 4. Locally admissible
pattern for $\mathcal{C}_{4}$ which cannot be extended to a global
configuration.

The previous remark showed a locally admissible pattern that could not be
extended to form a valid configuration of the group, and the main property of
this example is that although the support of the chosen pattern can be taken
to be a connected subgraph of the Cayley graph, it has a “gap” which allows us
to surround a position in such a way that the pattern could not be extended. A
way of avoiding these pathological cases is to require the supports of the
patterns to have some sort of convexity.

######  Lemma 4.3.

For every $n\geq 3$ every $n$-coloring of the rectangle $R_{m}$ can be
extended to a proper $n$-coloring of the rectangle $R_{m+1}$.

###### Proof.

For every $k\in\\{0,\ldots,m\\}$ we define

$H_{k}\coloneqq\left(R_{m+1}\backslash R_{m}\right)\cap\\{a^{i}b^{k}\mid i\geq
0\\},$

which represents the elements of $R_{m+1}$ of height $k$, outside of the
rectangle $R_{m}$. Note that by definition we have

$R_{m+1}=R_{m}\cup\bigcup_{k=0}^{m}H_{k}.$

Then we can extend the pattern $p$ on $R_{m}$ by successive colorings
(respecting the condition of being a proper coloring) coloring first $H_{0}$,
then $H_{1}$, and so until we color $H_{m}$. In each step of this process each
vertex has at most $2$ neighbors already colored, so having at least $3$
available colors is enough for this process to be carried out. ∎

By using the same ideas present in the proof of the previous lemma we obtain
the following proposition. Indeed, one can inductively color the rows of the
Cayley graph one by one, so that each vertex has at most two colored neighbors
at the moment it must choose its color.

######  Proposition 4.4.

For $n\geq 3$ every locally admissible pattern for $\mathcal{C}_{n}$ with
support a rectangle is globally admissible.

###  4.2. Mixing and frozen colorings

Thanks to Proposition 4.2 we know that for $n\geq 5$ we can extend every
admissible pattern to a proper coloring of the Cayley graph of
$\mathrm{BS}(1,N)$, from which we obtain the following mixing property for
$\mathcal{C}_{n}$.

######  Definition 4.1.

We say that a subshift $X\subseteq\mathcal{A}^{G}$ is strongly irreducible if
there exists $F\subseteq G$ finite such that for every globally admissible
patterns $p,q$ in $X$ with $\mathrm{supp}(p)\cap\mathrm{supp}(q)\cdot
F=\varnothing$: $[p]\cap[q]\neq\varnothing$.

######  Theorem 4.5.

Let $n\geq 5$ and consider two non-adjacent finite subsets
$F_{1},F_{2}\subseteq\mathrm{BS}(1,N)$, that is, such that

$\left(F_{1}\cdot\\{e_{\mathrm{BS}(1,N)},a,a^{-1},a,b^{-1}\\}\right)\cap
F_{2}=\varnothing.$

Then for every choice of (locally) admissible patterns
$p_{i}\in\\{0,\ldots,n-1\\}^{F_{i}},i=1,2,$ there exists $x\in\mathcal{C}_{n}$
such that $x|_{F_{1}}=p_{1}$ and $x|_{F_{2}}=p_{2}$. With this we have that
for $n\geq 5$ the GCS $\mathcal{C}_{n}$ is strongly irreducible.

###### Proof.

The above condition on $F_{1}$ and $F_{2}$ means that these two sets are
disjoint, and separated by at least one vertex in the Cayley graph of
$\mathrm{BS}(1,N)$.

Consider two locally admissible patterns
$p_{i}\in\\{0,\ldots,n-1\\}^{F_{i}},i=1,2$. Then we can define a new pattern
$p\in\\{0,\ldots,n-1\\}^{F_{1}\cup F_{2}}$ such that $p(f)=p_{i}(f)$ for $f\in
F_{i},i=1,2$ consistently, since $F_{1}\cap F_{2}=\varnothing.$ This pattern
is also locally admissible thanks to the distance existing between $F_{1}$ and
$F_{2}$, as between every vertex of $F_{1}$ and every vertex of $F_{2}$ there
is at least one uncolored vertex. Then, according to Proposition 4.2, this
pattern is globally admissible and hence there exists $x\in\mathcal{C}_{n}$
such that $x|_{F_{1}\cup F_{2}}=p$. This $x$ satisfies $x|_{F_{1}}=p_{1}$ and
$x|_{F_{2}}=p_{2}$ and so we have found the desired point. ∎

The previous proposition tells us that for $n\geq 5$ the subshift
$\mathcal{C}_{n}$ has a strong mixing property. On the other side, we can see
that $\mathcal{C}_{2}$ has no type of mixing behavior: this
$\mathrm{BS}(1,N)$-subshift is either empty if $N$ is even, or if $N$ is odd
then there is no way to assign the same color to two elements of the group
$g,h\in\mathrm{BS}(1,N)$ such that $g^{-1}h\in\left\\{a^{2m+1}\mid
m\in\mathbb{Z}\right\\}$, which forbids the gluing of patterns at arbitrarily
large distances. This contrast between $\mathcal{C}_{2}$ and $\mathcal{C}_{n}$
for $n\geq 5$ raises the question of what kind of mixing behaviors does
$\mathcal{C}_{3}$ and $\mathcal{C}_{4}$ have. To study this we will use a
similar approach as that of [ABC+19], by introducing the concept of a frozen
coloring.

######  Definition 4.2.

Let $n\geq 3$. A configuration $x\in\mathcal{C}_{n}$ is called a frozen
coloring if for every $y\in\mathcal{C}_{n}$ such that there exists a non-empty
finite subset $F\subseteq\mathrm{BS}(1,N)$ with $x|_{F^{c}}=y|_{F^{c}}$, then
$x=y$. That is, no coloring of $\mathrm{BS}(1,N)$ other than $x$ can coincide
with it outside of a finite set.

Frozen colorings are configurations in which the neighboring vertices of every
finite subset of the Cayley graph determine unequivocally how this subset must
be colored, in order to obtain a proper coloring. This behavior is the reason
frozen colorings are closely related to the (lack of) mixing properties of the
GCS, as the next proposition shows.

######  Proposition 4.6.

If $\mathcal{C}_{n}$ has a frozen coloring, then it is not strongly
irreducible.

###### Proof.

Looking for a contradiction, suppose that $\mathcal{C}_{n}$ is strongly
irreducible and $x\in\mathcal{C}_{n}$ is a frozen coloring.

Consider any other configuration $y\in\mathcal{C}_{n}$ such that
$y_{e_{\mathrm{BS}(1,N)}}\neq x_{e_{\mathrm{BS}(1,N)}}$. As $\mathcal{C}_{n}$
is strongly irreducible, there exists $F\subseteq G$ finite such that for any
two patterns $p,q\in\mathcal{L}(\mathcal{C}_{n})$ with
$\mathrm{supp}(p)\cap\mathrm{supp}(q)\cdot F=\varnothing$ we have
$[p]\cap[q]\neq\varnothing$. Considering the patterns
$y|_{e_{\mathrm{BS}(1,N)}}$ and $x|_{\partial B_{M}}$, where $\partial
B_{M}\coloneqq\\{g\in\mathrm{BS}(1,N):|g|=M\\}$, for $M$ sufficiently large we
have $\partial B_{M}\cap F=\varnothing$. Then there must exist a coloring
$z\in\mathcal{C}_{n}$ such that
$z_{e_{\mathrm{BS}(1,N)}}=y_{e_{\mathrm{BS}(1,N)}}\neq
x_{e_{\mathrm{BS}(1,N)}}$, and $z|_{\partial B_{M}}=x|_{\partial B_{M}}$.
Moreover, we can assume that $z|_{B_{M-1}^{c}}=x|_{B_{M-1}^{c}}$, where
$B_{M-1}\coloneqq\\{g\in\mathrm{BS}(1,N):|g|\leq M-1\\}$, since $z$ and $x$
coincide on $\partial B_{M}$ and hence re-coloring $z$ as $x$ outside of this
ball gives us a proper coloring.

With this we have found a configuration $z\in\mathcal{C}_{n}$ which coincides
with $x$ outside of a finite set but is different from $x$ inside it, so we
have a contradiction with the fact that $x$ is a frozen coloring. Hence we
conclude that a strongly irreducible subshift $\mathcal{C}_{n}$ cannot have a
frozen coloring. ∎

We already know by Theorem 4.5 that the GCS $\mathcal{C}_{n}$ for $n\geq 5$ is
strongly irreducible, and hence by the above proposition it cannot have a
frozen coloring. On the other hand, as the case $n=3$ is the first non-finite
subshift of the GCS’s $\mathcal{C}_{n}$ for $N\geq 2$, it is reasonable to
conjecture that its properties must still be somewhat rigid. The next
proposition confirms this by showing that $\mathcal{C}_{3}$ possesses a frozen
coloring, and with it exhibits the lack of a strong mixing behavior of the GCS
with three colors.

######  Theorem 4.7.

The GCS $\mathcal{C}_{3}\subseteq\\{0,1,2\\}^{\mathrm{BS}(1,N)}$ admits a
frozen coloring, and hence is not strongly irreducible.

###### Proof.

The proof will be divided in three cases, depending on the value of $N\
(\mathrm{mod}\ 3)$. For each one of these cases we will construct explicitly
the claimed frozen coloring.

Let us suppose first that $N=1\ (\mathrm{mod}\ 3)$, and with it for every
$i\geq 0$ we have $N^{i}=1\ (\mathrm{mod}\ 3)$. Let us define the
configuration $x\in\\{0,1,2\\}^{\mathrm{BS}(1,N)}$ such that for
$g=b^{-j}a^{k}b^{i}\in\mathrm{BS}(1,N)$ written in its normal form:

$x_{g}\coloneqq 2(i-j)+k\ (\mathrm{mod}\ 3).$

$\vdots$$\vdots$$\vdots$$\cdots$$\cdots$012012012012012012012012 Figure 5.
Construction of a frozen $3$-coloring for $N=1\ (\mathrm{mod}\ 3)$.

Note that $gb=b^{-j}a^{k}b^{i+1}$ and
$ga=b^{-j}a^{k}b^{i}a=b^{-j}a^{k+N^{i}}b^{i}$. With this, remembering that
$N^{i}=1\ (\mathrm{mod}\ 3)$ we have

$\displaystyle x_{gb}$ $\displaystyle=x_{g}+2\ (\mathrm{mod}\ 3),\text{ and}$
$\displaystyle x_{ga}$ $\displaystyle=x_{g}+N^{i}\ (\mathrm{mod}\ 3)=x_{g}+1\
(\mathrm{mod}\ 3).$

Therefore $x_{gb}\neq x_{g}$ and $x_{ga}\neq x_{g}$, and so
$x\in\mathcal{C}_{3}$ defines a proper coloring. Let us see that $x$ defines a
frozen coloring: looking for a contradiction let us suppose
$y\in\mathcal{C}_{3}$ is such that there exists a finite subset
$F\subseteq\mathrm{BS}(1,N)$ with $y|_{F^{c}}=x|_{F^{c}}$ and for every $f\in
F:\ x_{f}\neq y_{f}$. By using the fact that $F$ is finite, and shifting both
configurations if necessary, we may assume that

$F\subseteq\\{g\in\mathrm{BS}(1,N)\mid g=a^{k}b^{i},\text{ for some
}k\in\mathbb{Z},i\geq 0\\}.$

Geometrically, this means that $g$ is in the “upper” section of the Cayley
graph of $\mathrm{BS}(1,N)$, that is, in a sheet having as a base the subgroup
$\langle a\rangle$. Now consider $g$ in $F$ which maximizes the value of $i+k$
in its normal form. In other words,

$g\coloneqq\mathrm{argmax}\\{i+k\mid g=a^{k}b^{i}\in F,\ k\in\mathbb{Z},i\geq
0\\}.$

Then $y_{gb}=x_{gb}=x_{g}+2\ (\mathrm{mod}\ 3)$, and $y_{ga}=x_{ga}=x_{g}+1\
(\mathrm{mod}\ 3)$, and so as $y$ defines a proper coloring we must have
$y_{g}=x_{g}$, but this gives a contradiction since as $g\in F$ we should have
$y_{g}\neq x_{g}$.

Now let us see the case $N=2\ (\mathrm{mod}\ 3)$. Note that now we have that
for $i\geq 0$:

$N^{i}=\left\\{\begin{aligned} &1\ (\mathrm{mod}\ 3)\text{ if }i\text{ is
even},\\\ &2\ (\mathrm{mod}\ 3)\text{ if }i\text{ is
odd.}\end{aligned}\right.$

Define a configuration $x\in\\{0,1,2\\}^{\mathrm{BS}(1,N)}$ such that for
$g=b^{-j}a^{k}b^{i}\in\mathrm{BS}(1,N)$ written in its normal form:

$x_{g}\coloneqq i-j+k\ (\mathrm{mod}\ 3).$

$\vdots$$\vdots$$\vdots$$\cdots$$\cdots$0120120120120120110210210220120 Figure
6. Construction of a frozen $3$-coloring for $N=2\ (\mathrm{mod}\ 3)$.

Then as before we have

$\displaystyle x_{gb}$ $\displaystyle=x_{g}+1\ (\mathrm{mod}\ 3),\text{ and}$
$\displaystyle x_{ga}$ $\displaystyle=x_{g}+N^{i}\ (\mathrm{mod}\ 3),$

and so $x_{gb}\neq x_{g}$ and $x_{ga}\neq x_{g}$ (since $N^{i}$ can be either
$1$ or $2$). With this we have that $x\in\mathcal{C}_{3}$ defines a proper
coloring, so it only remains to prove that $x$ defines a frozen coloring.
Looking for a contradiction, suppose there exists $y\in\mathcal{C}_{3}$ and a
finite set $F\subseteq\mathrm{BS}(1,N)$ such that $x|_{F^{c}}=y|_{F^{c}}$ and
for every $f\in F:x_{f}\neq y_{f}$. Again, by shifting both configurations if
necessary, we may assume that $F\subseteq\\{g\in\mathrm{BS}(1,N)\mid
g=a^{k}b^{i},\text{ for some }k\in\mathbb{Z},i\geq 0\\}$. Define
$i_{max}\coloneqq\max\\{i\geq 0\mid a^{k}b^{i}\in F,\text{ for some
}k\in\mathbb{Z}\\}$ and $B_{max}\coloneqq\\{g=a^{k}b^{i}\in F\mid
i=i_{max}\\}$.

If $i_{max}$ is even, let us take $g=a^{k}b^{i}\in B_{max}$ which minimizes
the value of $k$. Then as $i_{max}$ is even we have $N^{i_{max}}=1$ and with
it $y_{gb}=x_{gb}=x_{g}+1\ (\mathrm{mod}\ 3)$, and
$y_{ga^{-1}}=x_{ga^{-1}}=x_{g}-N^{i_{max}}=x_{g}+2\ (\mathrm{mod}\ 3)$. But
then we must have $y_{g}=x_{g}$ and this gives a contradiction since $g\in F$
and therefore $x_{g}\neq y_{g}$.

Now if $i_{max}$ is odd, let us consider the element $g=a^{k}b^{i}\in B_{max}$
which maximizes the value of $k$. Then as $i_{max}$ is odd we have
$N^{i_{max}}=2$ and with it $y_{gb}=x_{gb}=x_{g}+1\ (\mathrm{mod}\ 3)$, and
$y_{ga}=x_{ga}=x_{g}+N^{i_{max}}=x_{g}+2\ (\mathrm{mod}\ 3)$. But then we must
have $y_{g}=x_{g}$ and this gives a contradiction since $g\in F$ and therefore
$x_{g}\neq y_{g}$, proving that $x$ defines a frozen coloring.

Finally suppose that $N=0\ (\mathrm{mod}\ 3)$. The method used on the previous
two cases to find a frozen coloring on $\mathcal{C}_{3}$ was to construct a
configuration using a function $f(j,k,i)$ of the coefficients of the normal
form of every element of the group, which $\mod\ 3$ had period $3$ on the
variable $k$. This cannot be done in the case $N\in 3\mathbb{Z}$ since here
the configuration constructed would satisfy $x=\sigma_{a^{3}}(x)$ and hence
$x=\sigma_{a^{N}}(x)$ (since $N\in 3\mathbb{Z}$). But then by Proposition 3.1
the coloring $x$ would have to have monochromatic rows appearing on it, which
contradicts the fact that $x\in\mathcal{C}_{3}$ defines a proper coloring.
Nonetheless, using a similar but different kind of function we can define a
configuration $x\in\\{0,1,2\\}^{\mathrm{BS}(1,N)}$ such that for
$g=b^{-j}a^{k}b^{i}\in\mathrm{BS}(1,N)$ written in its normal form:

$x_{g}\coloneqq(k\ (\mathrm{mod}\ 2))+2(i-j)\ (\mathrm{mod}\ 3).$

$\vdots$$\vdots$$\vdots$$\cdots$$\cdots$01010101010101010102020202121 Figure
7. Construction of a frozen $3$-coloring for $N=0\ (\mathrm{mod}\ 3)$.

We see that since $N^{i}$ is odd for every $i\geq 0$ we have:

$\displaystyle x_{gb}$ $\displaystyle=x_{g}+2\ (\mathrm{mod}\ 3),\text{ and}$
$\displaystyle x_{ga}$ $\displaystyle=(k+N^{i}\ (\mathrm{mod}\ 2))+2(i-j)\
(\mathrm{mod}\ 3)=x_{g}+1\ (\mathrm{mod}\ 3),$

from which $x\in\mathcal{C}_{3}$ defines a proper coloring, and we can proceed
as we did previously in the case $N^{i}=1\ (\mathrm{mod}\ 3)$. That is, to
prove that $x$ defines a frozen coloring we suppose $y\in\mathcal{C}_{3}$ is
such that there exists a finite subset $F\subseteq\mathrm{BS}(1,N)$ with
$y|_{F^{c}}=x|_{F^{c}}$ and for every $f\in F:\ x_{f}\neq y_{f}$. By shifting
both configurations if necessary, we may assume that
$F\subseteq\\{g\in\mathrm{BS}(1,N)\mid g=a^{k}b^{i},\text{ for some
}k\in\mathbb{Z},i\geq 0\\}$. Now let us consider $g$ in $F$ which maximizes
the value of $i+k$ in its normal form. Then $y_{gb}=x_{gb}=x_{g}+2\
(\mathrm{mod}\ 3)$, and $y_{ga}=x_{ga}=x_{g}+1\ (\mathrm{mod}\ 3)$, and so as
$y$ defines a proper coloring we must have $y_{g}=x_{g}$, but this gives a
contradiction since as $g\in F$ we should have $y_{g}\neq x_{g}$. Hence we see
that $x$ a frozen coloring.

To finish the proof we simply use the previous proposition to see that
$\mathcal{C}_{3}$ cannot be strongly irreducible, as we have constructed a
frozen coloring in it. ∎

This last theorem together with the previous comments settle the existence of
frozen colorings for $n=3$ and $n\geq 5$. To tackle the case of four colors,
and in the process give an alternative proof of the lack of frozen colorings
for $n\geq 5$, we will use a proposition from [ABC+19] used in that paper to
prove the lack of frozen $n$-colorings in $\mathbb{Z}^{d}$ for $n\geq d+2$.

######  Proposition 4.8 ([ABC+19, Proposition 2.2]).

For a graph $\Gamma$ let us define its edge-isoperimetric constant by

$i_{e}(\Gamma)\coloneqq\inf_{F\subseteq\Gamma\text{
finite}}\frac{|E(F,\Gamma\backslash F)|}{|F|},$

where $E(F,\Gamma\backslash F)$ are the edges of $\Gamma$ connecting vertices
from $F$ to $\Gamma\backslash F$. Denote by $\Delta$ the maximum degree of
$\Gamma$. Then for every $n>\frac{1}{2}\Delta+\frac{1}{2}i_{e}(\Gamma)+1$
there do not exist frozen $n$-colorings of $\Gamma$.

######  Theorem 4.9.

For $n\geq 4$ the GCS $\mathcal{C}_{n}$ does not admit a frozen coloring.

###### Proof.

Denoting by $\Gamma$ the Cayley graph of $\mathrm{BS}(1,N)$ its maximum degree
is $\Delta=4$, and if we prove that $i_{e}(\Gamma)=0$ we will have that, using
proposition 4.8, for $n>\frac{1}{2}\cdot 4+\frac{1}{2}\cdot 0+1=3$ this graph
does not admit frozen $n$-colorings, proving the statement.

Let us see that $i_{e}(\Gamma)=0$. Consider for every $k\geq 1:\
\gamma_{k}\coloneqq E(R_{k},\Gamma\backslash R_{k})$. We see that
$\gamma_{1}=2N+2$, and that for every $k\geq 2$:

$\gamma_{k}=N^{k}+2+N(\gamma_{k-1}-N^{k-1})=2+N\gamma_{k-1},$

by using the fact that the $N$ sheets arising from the base of the rectangle
$R_{k}$ are copies of the rectangle $R_{k-1}$. With this we have that

$\gamma_{k+1}-\gamma_{k}=N(\gamma_{k}-\gamma_{k-1}),\
\gamma_{2}-\gamma_{1}=2N^{2},$

and so $\gamma_{k}-\gamma_{k-1}=2N^{k}$, for every $k\geq 2$. Now summing this
equality from $k=2$ to $k=m$ we see that

$\displaystyle\gamma_{m}-(2N+2)=\gamma_{m}-\gamma_{1}=\sum_{k=2}^{m}\gamma_{k}-\gamma_{k-1}$
$\displaystyle=2\sum_{k=2}^{m}N^{k}$
$\displaystyle=2\frac{N^{m+1}-N^{2}}{N-1},$

and hence $\gamma_{m}=2\frac{N^{m+1}-1}{N-1}$. From this calculation we can
estimate the edge-isoperimetric constant:

$i_{e}(\Gamma)\leq\liminf_{m\to\infty}\frac{|E(R_{m},\Gamma\backslash
R_{m}|)}{|R_{m}|}=\liminf_{m\to\infty}\frac{\gamma_{m}}{|R_{m}|}=\liminf_{m\to\infty}\frac{2}{mN^{m}}\frac{N^{m+1}-1}{N-1}=0,$

and so $i_{e}(\Gamma)=0$ as we had claimed at the beginning of the proof. ∎

###  4.3. Topological entropy

We finish this section by focusing our attention on the topological entropy of
the GCS $\mathcal{C}_{n}$. By estimating in how many different ways a pattern
defined on a rectangle can be extended to a bigger one, we obtain the
following bounds.

######  Theorem 4.10.

For $n\geq 3$, we have the following estimate for the topological entropy of
the GCS $\mathcal{C}_{n}$:

$\log(n-2)\leq h_{\mathrm{top}}(\mathcal{C}_{n})\leq\log(n-1).$

###### Proof.

Let us see that $h_{\mathrm{top}}(\mathcal{C}_{n})\leq\log(n-1)$: a coloring
of the rectangle $R_{m}$ may be extended to a coloring of the rectangle
$R_{m+1}$ by coloring the remaining vertices having on each one at most $n-1$
options. With this

$\displaystyle|\mathcal{L}_{R_{m+1}}(\mathcal{C}_{n})|\leq|\mathcal{L}_{R_{m}}(\mathcal{C}_{n})|(n-1)^{|R_{m+1}\backslash
R_{m}|}.$

A simple calculation shows that $|R_{m+1}\backslash R_{m}|=N^{m}(mN+N-m)$.
With this:

$\displaystyle\frac{1}{|R_{m+1}|}\log|\mathcal{L}_{R_{m+1}}(\mathcal{C}_{n})|$
$\displaystyle=\frac{1}{(m+1)N^{m+1}}\log|\mathcal{L}_{R_{m+1}}(\mathcal{C}_{n})|$
$\displaystyle\leq\frac{1}{(m+1)N^{m+1}}\log|\mathcal{L}_{R_{m}}(\mathcal{C}_{n})|+\frac{N^{m}(mN+N-m)}{(m+1)N^{m+1}}\log(n-1)$
$\displaystyle=\frac{1}{N}\frac{m}{m+1}\frac{1}{mN^{m}}\log|\mathcal{L}_{R_{m}}(\mathcal{C}_{n})|+\frac{mN+N-m}{m+1}\frac{1}{N}\log(n-1)$
$\displaystyle=\frac{1}{N}\frac{m}{m+1}\frac{1}{|R_{m}|}\log|\mathcal{L}_{R_{m}}(\mathcal{C}_{n})|+\frac{m(N-1)+N}{m+1}\frac{1}{N}\log(n-1).$

Taking the limit $m\to\infty$ we arrive at

$\displaystyle h_{\mathrm{top}}(\mathcal{C}_{n})$
$\displaystyle=\lim_{m\to\infty}\frac{1}{|R_{m+1}|}\log|\mathcal{L}_{R_{m+1}}(\mathcal{C}_{n})|$
$\displaystyle\leq\lim_{m\to\infty}\frac{1}{N}\frac{m}{m+1}\frac{1}{|R_{m}|}\log|\mathcal{L}_{R_{m}}(\mathcal{C}_{n})|+\lim_{m\to\infty}\frac{m(N-1)+N}{m+1}\frac{1}{N}\log(n-1)$
$\displaystyle=\frac{1}{N}h_{\mathrm{top}}(\mathcal{C}_{n})+\frac{N-1}{N}\log(n-1),$

from where

$h_{\mathrm{top}}(\mathcal{C}_{n})\leq\log(n-1).$

Now let us see that $h_{\mathrm{top}}(\mathcal{C}_{n})\geq\log(n-2)$: the
rectangle $R_{m}$ can be colored starting from the upper levels to the lower
levels, ensuring at least $n-2$ color options at each element, since in this
way each vertex of the Cayley graph has at most two neighbors already colored.
Then this coloring can be extended to the whole graph by using Proposition 4.4
and hence forming a globally admissible configuration for $\mathcal{C}_{n}$.
From this we arrive at

$\displaystyle|\mathcal{L}_{R_{m}}(\mathcal{C}_{n})|\geq(n-2)^{|R_{m}|},$

and so $h_{\mathrm{top}}(\mathcal{C}_{n})\geq\log(n-2)$. ∎

In particular, the lower bound from the previous proposition shows us that
$h_{\mathrm{top}}(\mathcal{C}_{n})>0$ for every $n\geq 4$, but gives us no new
information for the case of three colors $\mathcal{C}_{3}$, since by
definition $h_{\mathrm{top}}(\mathcal{C}_{3})\geq 0$. In the next proposition
we show that indeed $h_{\mathrm{top}}(\mathcal{C}_{3})>0$, dividing the proof
in two cases depending on the parity of $N$. If $N$ is odd we can exploit the
fact that the Cayley graph of $\mathrm{BS}(1,N)$ is bipartite (we know this
since we have already constructed a $2$-coloring of it in Proposition 4.1, or
equivalently observing that it has no odd cycles) to give a straightforward
proof, while in the case of even $N$ we give a more delicate construction to
arrive at the same result.

######  Theorem 4.11.

The GCS $\mathcal{C}_{3}\subseteq\\{0,1,2\\}^{\mathrm{BS}(1,N)}$ has positive
topological entropy.

###### Proof.

Let us start with the case of odd $N$. Here the Cayley graph of
$\mathrm{BS}(1,N)$ is bipartite and hence so is every rectangle $R_{m}$, for
$m\geq 1$. Consider a partition of $R_{m}$ into two sets $A$ and $B$, meaning
that all edges of the graph are composed of a vertex in $A$ and a vertex in
$B$. Then one of them, which we take to be $A$ without loss of generality,
must have cardinality at least $\frac{1}{2}|R_{m}|$. Then we can create proper
colorings of $R_{m}$ by coloring the vertices of $B$ with one color and have
the freedom to choose between two colors for every vertex of $A$, and then
extend this pattern on $R_{m}$ to the rest of the group as was said earlier.

With the above we can estimate a lower bound for the number of proper
colorings of $R_{m}$ by

$|\mathcal{L}_{R_{m}}(\mathcal{C}_{3})|\geq 2^{|A|}\geq
2^{\frac{1}{2}|R_{m}|}.$

Then taking logarithm and dividing by $|R_{m}|$ we arrive at

$\frac{1}{|R_{m}|}\log|\mathcal{L}_{R_{m}}(\mathcal{C}_{3})|\geq\frac{1}{2}\log(2),$

to finally take limit as $m\to\infty$ and obtain

$h_{\mathrm{top}}(\mathcal{C}_{3})\geq\frac{1}{2}\log(2)>0,$

which is what we wanted.

Now consider the case of even $N$. For $m\geq 1$ we define a pattern
$p\in\mathcal{A}^{R_{2m}}$, where some of the vertices of this rectangle will
have the freedom of being assigned the symbol $1$ or $2$, in either case
remaining a proper $3$-coloring of $R_{2m}$.

First let us define

$p|_{[e_{\mathrm{BS}(1,N)},a^{N^{2m}-1}]}=\left(0(12)^{2N}\right)^{\infty}|_{[0,N^{2m}-1]},$

and for $i\in\\{0,\ldots,N^{2m}-1\\}$, $j\in\\{0,\ldots,m-1\\}$ define

$p_{a^{i}b^{2j}}=p_{a^{i}}.$

That is, the symbols we see in the $\mathbb{Z}$-sections at even level of
$R_{2m}$ are copies of the sequence found in the base of the rectangle. Now we
proceed to define the pattern $p$ at the $\mathbb{Z}$-sections of odd level.
Define for
$i\in\left\\{0,\ldots,\left\lfloor\frac{N^{2m}}{2N+1}\right\rfloor-1\right\\}$,
$k\in\\{0,\ldots,2N\\}$, $j\in\\{0,\ldots,m-1\\}$ and any choice of
$\alpha_{i,j,k}\in\\{0,1\\}$:

$p_{a^{(2N+1)i+k}b^{2j+1}}=\left\\{\begin{aligned} &\alpha_{i,j,k}\text{ if
}k=0,\\\ &0\text{ if }k=N\text{ or }k=N+1,\\\ &2\text{ if }k\text{ is even and
}k\neq N,\\\ &1\text{ if }k\text{ is odd and }k\neq N+1.\\\
\end{aligned}\right.$

With the above we are assigning to each $\mathbb{Z}$-section at odd level of
$R_{m}$ (a subword of) the sequence $\left(\alpha_{i,j,k}\ 0\
(12)^{2N-2}\right)^{\infty}$, where every choice of
$\alpha(i,j,k)\in\\{1,2\\}$ gives rise to a different pattern.

$\vdots$$\vdots$$\vdots$$\cdots$$\cdots$01212012120121201?0210?02102121 Figure
8. Nodes with the symbol “?” have freedom of choosing between a symbol “1” or
“2”, since all their neighbors have “0”s in them.

The above shows that

$|\mathcal{L}_{R_{2m}}(\mathcal{C}_{3})|\geq
2^{m\left\lfloor\frac{N^{2m}}{2N+1}\right\rfloor},$

and hence

$\displaystyle\frac{1}{|R_{2m}|}\log|\mathcal{L}_{R_{2m}}(\mathcal{C}_{3})|$
$\displaystyle\geq\frac{m\left\lfloor\frac{N^{2m}}{2N+1}\right\rfloor}{2mN^{2m}}\log(2)$
$\displaystyle\geq\frac{\frac{N^{2m}}{2N+1}-1}{2N^{2m}}\log(2).$

Finally, taking limit as $m\to\infty$ we obtain

$h_{\mathrm{top}}(\mathcal{C}_{3})\geq\frac{1}{2(2N+1)}\log(2)>0.$

∎

##  5\. Further questions and possible generalizations

It is interesting to think about how the properties from Section 4 for graph-
coloring subshifts in $\mathrm{BS}(1,N)$ generalize to the more fundamental
context of ascending HNN-extensions $G*_{\psi}$ of finitely generated abelian
groups. The answers will now probably be separated in two cases depending on
the nature of the group $G$, with respect to whether it is bipartite or not.
Results will also depend on the value of $|G:\psi(G)|$, since this number will
play a role in the length of the new cycles that arise in the Cayley graph of
$G*_{\psi}$, in contrast with those found in $G$.

The method used to find the topological entropy bounds for GCS in
$\mathrm{BS}(1,N)$ was counting patterns using rectangles, and thus should be
able to be replicated to some extent for $G*_{\psi}$, using the natural
generalizations of rectangles to this group.

######  Problem.

How do the topological entropy related results from Theorem 1.3 generalize to
GCS in $G*_{\psi}$?

With respect to frozen colorings, Proposition 4.8 was fundamental for proving
the absence of such configurations for $n\geq 4$ and it will play the same
role in the case of ascending HNN-extensions $G*_{\psi}$ of a finitely
generated abelian group, by using the generalization of rectangles to these
groups. On the other hand, the existence of frozen $3$-colorings shown in
Theorem 4.7 was somehow involved and it does not generalize immediately to the
case of $G*_{\psi}$.

######  Problem.

Find explicit constructions of frozen $3$-colorings on $G*_{\psi}$.

A final remark is that most of the results obtained in Section 4 depend only
on the number of colors $n$, and not on the parameter $N$ of
$\mathrm{BS}(1,N)$. More generally, we ask the following.

######  Problem.

Consider a finitely generated abelian group $G$, two different (non-trivial)
monomorphisms $\psi,\psi^{\prime}:G\to G$, and the corresponding ascending
HNN-extensions $G*_{\psi}$ and $G*_{\psi^{\prime}}$. For $n\geq 3$, what are
the dynamical differences between the corresponding GCS associated to
$G*_{\psi}$ and $G*_{\psi^{\prime}}$? In particular, do they have equal
topological entropy?

Acknowledgements. I would like to thank my Master’s advisor Michael Schraudner
for his continuous support, and Nathalie Aubrun for her helpful comments and
ideas. This work was developed as part of a Master’s degree thesis at
Universidad de Chile, partially supported by CONICYT-PFCHA/Magíster
Nacional/2019 - 22190176.

## References

  * [ABC+19] Noga Alon, Raimundo Briceño, Nishant Chandgotia, Alexander Magazinov, and Yinon Spinka.  Mixing properties of colorings of the $\mathbb{Z}^{d}$ lattice.  arXiv preprint arXiv:1903.11685, 2019.
  * [AK13] Nathalie Aubrun and Jarkko Kari.  Tiling problems on baumslag-solitar groups.  Electronic Proceedings in Theoretical Computer Science, 128:35–46, 2013.
  * [BS62] Gilbert Baumslag and Donald Solitar.  Some two-generator one-relator non-hopfian groups.  Bulletin of the American Mathematical Society, 68(3):199–202, 1962\.
  * [CFKP16] Van Cyr, John Franks, Bryna Kra, and Samuel Petite.  Distortion and the automorphism group of a shift.  arXiv preprint arXiv:1611.05913, 2016.
  * [EM20] Julien Esnay and Etienne Moutot.  Weakly and strongly aperiodic subshifts of finite type on baumslag-solitar groups.  arXiv preprint arXiv:2004.02534, 2020.
  * [Har03] Pierre de La Harpe.  Topics in geometric group theory.  Univ. of Chicago Press, 2003.
  * [HNN49] Graham Higman, B. H. Neumann, and Hanna Neuman.  Embedding theorems for groups.  Journal of the London Mathematical Society, s1-24(4):247–254, 1949\.
  * [KL16] David Kerr and Hanfeng Li.  Ergodic Theory.  Springer International Publishing, 2016.
  * [Lie67] Elliott H. Lieb.  Residual Entropy of Square Ice.  Phys. Rev., 162:162–172, 1967.
  * [LS77] R. C. Lyndon and Paul E. Schupp.  Combinatorial group theory.  Springer, 1977.
  * [Mes72] Stephen Meskin.  Nonresidually finite one-relator groups.  Transactions of the American Mathematical Society, 164:105, 1972\.
  * [PS18] Ron Peled and Yinon Spinka.  Rigidity of proper colorings of $\mathbb{Z}^{d}$.  arXiv preprint arXiv:1808.03597, 2018.
  * [RS20] Gourab Ray and Yinon Spinka.  Proper 3-colorings of $\mathbb{Z}^{2}$ are bernoulli.  arXiv preprint arXiv:2004.00028, 2020.