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
$$ \begin{align*}\sigma_g(x)_h=x_{g^{-1}h}\quad\text{for }x\in\mathcal{A}^G,\ g,h\in G.\end{align*} $$
An important type of subshift is the subshift of finite type (SFT), which can be described completely by a finite set of forbidden patterns.
Throughout the last decades, there has been interest shown in the cases
$G=\mathbb {Z}^d$
,
$d\ge 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\ge 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\ge 2$
, it is undecidable.
In recent years, interest has grown in studying the 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
$$ \begin{align*}\mathrm{BS}(m,n):= \langle a,b \mid ba^mb^{-1}=a^n \rangle. \end{align*} $$
These groups were first introduced (though their origin might be older) in [Reference Baumslag and Solitar3] by Baumslag and Solitar, 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 [Reference de La Harpe6, Reference Meskin13], and more recently in the field of symbolic dynamics [Reference Aubrun and Kari2, Reference Cyr, Franks, Kra and Petite5, Reference Esnay and Moutot7].
The subfamily of Baumslag–Solitar groups
$\mathrm {BS}(1,N)$
,
$N\ge 2$
, is of particular interest, since it exhibits interesting properties in contrast to the rest of the 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 §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 by the stable letter associated with the HNN-extension.
In §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 \ge 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 \ge 0$
such that
$\psi ^{\ell }(H)\leqslant \mathrm {Stab}(x)$
. Then:
-
(1) all G-sections of level greater or equal than
$\ell $
are H-periodic; -
(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) 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\ge 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\ge 2$
the graph-coloring subshift (GCS)
$$ \begin{align*}\mathcal{C}_{n}:=\{x\in \{0,\ldots,n-1\}^G\mid \text{ for all } g\in G, s\in S: \ x_{g}\neq x_{gs} \}, \end{align*} $$
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\ge 2$
, have been studied recently [Reference Alon, Briceño, Chandgotia, Magazinov and Spinka1, Reference Peled and Spinka14, Reference Ray and Spinka15]. In particular, in [Reference Alon, Briceño, Chandgotia, Magazinov and Spinka1], the authors study mixing properties for colorings of
$\mathbb {Z}^d$
,
$d\ge 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\le n\le d+1$
.
In §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.10), and then prove the lack of frozen n-colorings for every
$n\ge 4$
(Theorem 4.12).
Theorem 1.2. For
$n\ge 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
$\tfrac 32\log \tfrac 43$
[Reference Lieb10].
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.13), as well as showing that the topological entropy of
$\mathcal {C}_3$
is positive (Theorem 4.14).
Theorem 1.3. For
$n\ge 3$
, the GCS
$\mathcal {C}_n\subseteq \{0,\ldots ,n-1\}^{\mathrm {BS}(1,N)}$
satisfies
$$ \begin{align*} \log(n-2)\le h_{\mathrm{top}}(\mathcal{C}_n)\le\log(n-1). \end{align*} $$
We also have that
$h_{\mathrm {top}}(\mathcal {C}_3)>0$
. In fact, we further have that:
-
(1) if N is odd, then
$h_{\mathrm {top}}(\mathcal {C}_3)\ge \tfrac 12\log 2$
; and -
(2) if N is even, then
$h_{\mathrm {top}}(\mathcal {C}_3)\ge ({1}/{2(N^2+1)})\log 2$
.
Finally in §5, we make some comments and raise 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):= 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:= 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
$$ \begin{align*}[p]=\{x\in \mathcal{A}^G\mid x|_{\mathrm{supp}(p)}=p \}, \quad p\text{ a pattern}. \end{align*} $$
The topological space
$\mathcal {A}^G$
together with the left G-action by homeomorphisms
$$ \begin{align*} \sigma:G&\to \mathrm{Homeo}(\mathcal{A}^G,\mathcal{A}^G)\\ g&\mapsto \sigma_g, \end{align*} $$
where for every
$x\in \mathcal {A}^G$
,
$g,h\in G$
:
$$ \begin{align*}\sigma_g(x)_h=x_{g^{-1}h} \end{align*} $$
is called the full G-shift and
$\sigma $
is called the shift map. Associated with this action, we define for a configuration
$x\in \mathcal {A}^G$
its orbit
$$ \begin{align*}\mathrm{Orb}(x):=\{\sigma_g(x)\mid g\in G \},\end{align*} $$
and its stabilizer
$$ \begin{align*}\mathrm{Stab}(x):= \{g\in G\mid \sigma_g(x)=x \}.\end{align*} $$
The latter of these sets is in fact a subgroup of G, and we have the following 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)$
is not the trivial subgroup
$\{e_G\}$
, 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
$$ \begin{align*}X=\{x\in \mathcal{A}^G\mid \text{ for every finite subset }F\subseteq G:\ \sigma_g(x)|_{F}\notin \mathcal{F}, \text{ for every }g\in G \}. \end{align*} $$
If such a family can be chosen to be finite, we say that X is a G-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}$
as subpatterns, and globally admissible if there exists an
$x\in X$
such that
$x|_{\mathrm {supp}(p)}=p$
.
We say that a countable group G is amenable if there exists a sequence of finite subsets
$F_n\subseteq G$
,
$n\in \mathbb {N}$
, such that for any
$g\in G$
:
$$ \begin{align*}\lim_{n\to \infty}\frac{|gF_n\triangle F_n|}{|F_n|}=0. \end{align*} $$
We say that
$\{F_n\}_{n\in \mathbb {N}}$
is a Følner sequence in G. For our purposes, amenability will be important because it will allow us to generalize the notion we have for topological entropy of
$\mathbb {Z}$
-subshifts to more general groups. See [Reference Löh11, Ch. 9] and [Reference Ceccherini-Silberstein and Coornaert4, Ch. 4] for further details about amenability.
In the case where G is amenable, we fix a Følner sequence
$\{F_n\}_{n\in \mathbb {N}}$
and we define the topological entropy of a G-subshift X as
$$ \begin{align*}h_{\mathrm{top}}(X):= \lim_{n\to \infty}\frac{\log|\mathcal{L}_{F_n}(X)|}{|F_n|}, \end{align*} $$
where
$\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 [Reference Kerr and Li9, 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\le G$
. The HNN-extensionFootnote †
$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| R\rangle $
and two isomorphic subgroups
$H,K\le G$
, with
$\psi :K\to H$
an isomorphism. We define the HNN-extension of G with respect to
$\psi $
by the presentation
$$ \begin{align*} G*_{\psi}:= \langle S\cup\{t\} | R\cup \{t k t^{-1}=\psi(k): k\in K \} \rangle. \end{align*} $$
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.2. (Britton’s lemma [Reference Lyndon and Schupp12, Theorem IV.2.1])
Let G be a group,
$H,K\le 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_0t^{\varepsilon _1}g_1t^{\varepsilon _2}\ldots t^{\varepsilon _n}g_n$
for
$n\ge 0$
,
$g_0\in G$
, and
$\varepsilon _i\in \{+1,-1\}$
for
$i=1,\ldots ,n$
, such that:
-
(1)
$\varepsilon _i=1 $
implies
$g_i\in T_K$
; -
(2)
$\varepsilon _i=-1$
implies
$g_i\in T_H$
: and -
(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
$$ \begin{align*}\mathrm{BS}(m,n)=\langle a,b | ba^mb^{-1}=a^n\rangle,\end{align*} $$
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.3. 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 on ascending HNN-extensions
$G*_{\psi }$
having a finitely generated abelian base group G, on which the monomorphism
$\psi $
is not surjective. That is, the image
$\psi (G)$
is a proper subgroup of G. The main example for our results are the Baumslag–Solitar groups
$\mathrm {BS}(1,N)$
for
$N\ge 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 of the 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.4. Under the above hypotheses and the presentation of
$G*_{\psi }$
from Definition 2.1, for
$g\in G$
and
$j\ge 0$
we have
$ t^jg=\psi ^j(g)t^j,$
where
$\psi ^j$
denotes the composition of
$\psi $
with itself j times.
Proposition 2.5. 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\ge 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.2 with
$T_K=\{e_{G}\}$
and
$T_H$
a set of representatives of
$\psi (G)$
, we distinguish three types of words.
(1) The first type is words of the form
$gt^i$
,
$g\in G$
,
$i\ge 0$
. This is already a word of the form described in the proposition.
(2) The second type is words of the form
$ g_0t^{-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
$$ \begin{align*} g_0t^{-1}g_1\cdots t^{-1}g_n=t^{-n}\psi(\tilde{g})g_n. \end{align*} $$
If
$n=1$
, then
$g_0t^{-1}g_1=t^{-1}\psi (g_0)g_1$
.
In the general case, for
$n\ge 2$
, the induction hypothesis gives us the existence if
$\tilde {g}\in G$
such that
$$ \begin{align*} g_0t^{-1}g_1\cdots t^{-1}g_{n-1}=t^{-(n-1)}\psi(\tilde{g})g_{n-1}. \end{align*} $$
Then
$$ \begin{align*} g_0t^{-1}g_1\cdots t^{-1}g_{n-1}t^{-1}g_n&=t^{-(n-1)}\psi(\tilde{g})g_{n-1}t^{-1}g_n\\ &=t^{-(n-1)}\psi(\tilde{g})t^{-1}\psi(g_{n-1})g_n\\ &=t^{-n}\psi(\psi(\tilde{g})g_{n-1})g_n, \end{align*} $$
finishing the induction.
(3) Finally, the third possible type of words are of the form
$ g_0t^{-1}g_1\cdots t^{-1}g_nt^{j}, \text { where}\ g_0\in G, \ g_1,\ldots ,g_n\in T_H, \ j\ge 1. $
As in the previous case, it is possible to prove that there exists
$\tilde {g}\in G$
such that
$$ \begin{align*} g_0t^{-1}g_1\cdots t^{-1}g_nt^{j}=t^{-n}\psi(\tilde{g})g_nt^j. \end{align*} $$
Note that as
$j\ge 1$
, the third condition from Proposition 2.2 ensures that
$g_n\neq e_G$
(since otherwise the considered word would contain a subword of the form
$t^{-1}e_Gt$
), and so
$\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.6. Consider the Baumslag–Solitar group
$\mathrm {BS}(1,N)$
,
$N\ge 2$
. Define for
$m\ge 1$
the rectangle of height m
$$ \begin{align*} R_m:= \{a^kb^i\mid 0\le k<N^m, \ 0\le i<m \}\subseteq \mathrm{BS}(1,N). \end{align*} $$
Then
$\{R_m\}_{m\ge 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\ge 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 },\unicode{x3bb} _{\Gamma })$
where:
-
(1) the set of vertices is
$V_\Gamma =G$
; -
(2) the set of edges is
$E_{\Gamma }=\{(g,gs)\in G\times G\mid s\in S\}$
; and -
(3) the labeling function
$\unicode{x3bb} _{\Gamma }:E_{\Gamma }\to V_{\Gamma }$
satisfies
$\unicode{x3bb} _{\Gamma }(g,gs)=s$
, for
$g\in G$
,
$s\in S$
.
For
$g\in G$
, we denote by
$|g|_S$
the minimum distance between g and the identity in the Cayley graph
$\Gamma (G,S)$
. When the generating set S is fixed and understood from the context, we simply write
$|g|$
. We call
$|\cdot |_S$
the word metric in G associated with 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 (that is, in the
$b^{-1}$
-direction) a unique
$\mathbb {Z}$
-section, and above it (that is, in the b-direction) N new
$\mathbb {Z}$
-sections. More formally, defining
$A:= \{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
$\bigcup _{n=1}^{\infty }gb^{-n}A \cup \bigcup _{n=0}^\infty ( g\prod _{s=1}^{n}(a^{i_s}b)A )$
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.
A section of the Cayley graph of
$BS(1,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’.
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 in which they are used.
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 analogously define the notion of a sheet of the Cayley graph of the HNN-extension
$G*_{\psi }$
.
We finish this section by making the following definitions, which enable us to enunciate the results of the next section in a clearer way.
Definition 2.7. For
$h\in G$
, we define the G-section containing h as
$$ \begin{align*} \Gamma_{h}:= \{hg\mid g\in G \}. \end{align*} $$
Using the normal form from Proposition 2.5 we can write
$h=t^{-j}gt^i$
, for
$i,j\ge 0$
,
$g\in G$
. In this case, we say that
$\Gamma _h$
is a G-section of level
$i-j$
. Note that owing to the uniqueness of the normal form, the value
$i-j$
is well defined for h.
Moreover, note that the G-section containing h is naturally in bijection with G, via the map
$\Gamma _h\to G$
defined by
$hg\mapsto g$
, for
$g\in G$
. Hence the restriction of a configuration
$x\in \mathcal {A}^{G*_{\psi }}$
can be interpreted as a configuration
$\hat {x}\in \mathcal {A}^{G}$
, where
$\hat {x}_{g}:= x_{hg}$
.
Given a subgroup
$H\leqslant G$
and a configuration
$x\in \mathcal {A}^{G*_{\psi }}$
, we say that the G-section
$\Gamma _h$
of x is H-periodic if
$\hat {x}$
is H-periodic as a configuration in
$\mathcal {A}^{G}$
, according to the notation of the previous paragraph. That is, if
$x_{hgg'}=x_{hg}$
, for every
$g\in G$
,
$g'\in H$
.
The next notion allows us to distinguish G-sections of the same level, according to what is the highest level of intersection between sheets containing them.
Definition 2.8. Consider an ascending HNN-extension
$G*_{\psi }$
and a subgroup
$H\leqslant G$
. For
$i,\ell \in \mathbb {Z}$
,
$\ell < i$
, we say that two G-sections
$\Gamma _h, \Gamma _{h'}$
of the same level i share a common G-section of level
$\ell $
if there exists a G-section
$\Gamma _{h''}$
of level
$\ell $
such that
$\Gamma _{h}\subseteq \Gamma _{h''}t^{i-\ell }$
and
$\Gamma _{h'}\subseteq \Gamma _{h''}t^{i-\ell }$
.
Intuitively, this means that starting at the G-section
$\Gamma _{h''}$
, we can reach both G-sections
$\Gamma _{h}$
and
$\Gamma _{h'}$
by only moving in the t direction
$i-\ell $
times.
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 \ge 0$
such that
$\psi ^{\ell }(H)\leqslant \mathrm {Stab}(x)$
. Then all G-sections of x 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
$$ \begin{align} \sigma_{\psi^{\ell}(h)}(x)=x\quad\text{for all }h\in H. \end{align} $$
It suffices to prove that for any
$i,j\ge 0$
,
$g\in G$
, and
$h\in H$
, we have that
$$ \begin{align} x_{t^{-j}gt^{i+j+\ell}h}=x_{t^{-j}gt^{i+j+\ell}}. \end{align} $$
In effect, note that using Lemma 2.4 and commutativity of G, we have that
$$ \begin{align*} t^{-j}gt^{i+j+\ell}h&=t^{-j}g\psi^{i+j+\ell}(h)t^{i+j+\ell} \\ &=t^{-j}\psi^{i+j+\ell}(h)gt^{i+j+\ell} \\ &=\psi^{i+\ell}(h)t^{-j}gt^{i+j+\ell}\\ &=\psi^{\ell}(\psi^i(h))t^{-j}gt^{i+j+\ell}. \end{align*} $$
As
$\psi ^i(h)\in H$
, owing to the hypothesis, equation (3.2) follows from equation (3.1).
For the second part of the proposition, it suffices to prove that for any
$i,j,h\ge 0$
and
$g,\tilde {g}\in G$
, we have
$$ \begin{align*} x_{t^{-j}gt^{i+j+\ell+h}}=x_{t^{-j}gt^{i+j+\ell}\tilde{g}t^h}. \end{align*} $$
Again, using commutativity of G and Lemma 2.4, we have
$$ \begin{align*} t^{-j}gt^{i+j+\ell}\tilde{g}t^h&=t^{-j}g\psi^{i+j+\ell}(\tilde{g})t^{i+j+\ell+h}\\ &=t^{-j}\psi^{i+j+\ell}(\tilde{g})gt^{i+j+\ell+h}\\ &=\psi^{i+\ell}(\tilde{g})t^{-j}gt^{i+j+\ell+h}, \end{align*} $$
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 \ge 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\ge 1 \}$
is finite. Hence, there exists a sequence of increasing positive integers
$\{q_n\}_{n\ge 1}$
such that for every
$n\ge 1$
,
$$ \begin{align*} \sigma_{t^{-q_1}}(x)=\sigma_{t^{-q_n}}(x), \end{align*} $$
or equivalently,
$$ \begin{align*} \sigma_{t^{q_1-q_n}}(x)=x. \end{align*} $$
Fix
$g\in G*_{\psi }$
, and note that by considering sufficiently large n, the element
$t^{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 any
$h\in H$
:
$$ \begin{align*} x_{g}&=(\sigma_{t^{q_1-q_n}}(x))_{g}\\ &=x_{t^{q_n-q_1}g}\\ &=x_{t^{q_n-q_1}gh}\\ &=\sigma_{t^{q_1-q_n}}(x)_{gh}\\ &=x_{gh}. \end{align*} $$
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 }}$
, and suppose there exist
$H\leqslant G$
with
$\psi (H)\leqslant H$
and
$\ell \ge 0$
such that
$\psi ^{\ell }(H)\leqslant \mathrm {Stab}(x)$
. Suppose X is a
$G*_{\psi }$
-subshift containing the configuration 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, it assigns the same symbol to all of their elements, and G-sections of the same level share the same symbol.
Proof Owing to Proposition 3.1, we have that all G-sections at a level greater than or equal to
$\ell $
in x are H-periodic. We define for each
$n\ge 1$
the configuration
$x^n:= \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 a nearest neighbor 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\ge 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 neighbor 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 3.4. 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.
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\ge 2$
the graph-coloring subshift (GCS)
$$ \begin{align*}\mathcal{C}_{n}:=\{x\in \{0,\ldots,n-1\}^G\mid\text{for all } g\in G, s\in S: \ x_{g}\neq x_{gs} \}. \end{align*} $$
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\ge 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\ge 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^Nb}=1$
, but this cannot be since
$x_{a^Nb}=x_{ba}$
, so the neighboring vertices b and
$ba$
have the same color and this contradicts the definition of a GCS.
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^kb^i$
with
$i,j\ge 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
$$ \begin{align*} ga=b^{-j}a^{k+N^i}b^{i}, \end{align*} $$
if
$s=a$
and
$$ \begin{align*} gb=b^{-j}a^{k}b^{i+1}, \end{align*} $$
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 a
$\mathbb {Z}$
-section
$\Gamma _g:= \{ga^k: k\in \mathbb {Z}\}, g\in G$
colored consistently with the coloring rules using two colors, that is 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\ge 3$
, and with it, be able to estimate topological entropy
$h_{\mathrm {top}}(\mathcal {C}_n)$
.
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\ge 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.
Fix a sequence of finite subsets
$\{S_n\}_{n\ge 1}$
of
$\mathrm {BS}(1,N)$
, such that:
-
•
$S_0=S$
; -
•
$S_n\subseteq S_{n+1}$
, for
$n\ge 0$
; and -
•
$\mathrm {BS}(1,N)=\bigcup _{n\ge 0}S_n$
.
Given any locally admissible pattern p with support S, we can consider a sequence of configurations
$\{x^{n}\}_{n\in \mathbb {N}}$
in
$\{0,\ldots ,n-1\}^{\mathrm {BS}(1,N)}$
such that
$x^{n}|_{S_n}$
is a proper coloring of
$S_n$
and
$x^{n}|_{S}=p$
, owing to the above explanation. Now by taking
$x\in \{0,\ldots ,n-1\}^{BS}$
to be an accumulation point of said sequence, we see that by construction, it is a proper coloring in
$\mathcal {C}_n$
which coincides with p in S.
Remark 4.3. 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.
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.4. For every
$n\ge 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
$$ \begin{align*}H_k:= (R_{m+1}\backslash R_{m})\cap \{a^ib^k\mid i\ge 0\},\end{align*} $$
which represents the elements of
$R_{m+1}$
of height k, outside of the rectangle
$R_m$
. Note that by definition, we have
$$ \begin{align*}R_{m+1}=R_m\cup \bigcup_{k=0}^{m}H_k.\end{align*} $$
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 on 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.5. For
$n\ge 3$
, every locally admissible pattern for
$\mathcal {C}_n$
with support, a rectangle is globally admissible.
Proof Suppose that we have a locally admissible pattern p defined on the rectangle
$R_{m}$
. First, note that we can extend this to a proper coloring on the
$0$
level. That is, on the subgroup generated by a. In effect, the elements at
$a^{-1}$
and at
$a^{N^m}$
only have one colored neighbor, so we can assign them a color without introducing forbidden patterns. By the same argument, we can color inductively neighboring vertices until we have a proper coloring of
$R_m\cup \langle a \rangle $
.
Now we can do the same with upper levels: consider rows of level
$1$
which are connected to
$\langle a\rangle $
. The elements neighboring
$R_m$
have at most two colored neighbors, and so we can extend the pattern. Again, proceeding inductively and coloring in order according to their relative distance to
$R_m$
, we see that we can extend the pattern to
$R_m\cup \langle a\rangle \cup \langle a\rangle b$
. Moreover, by repeating the same argument, we can see that it is possible to extend the coloring of
$R_m$
to all first m levels. That is, to the set
$\langle a\rangle \cup \langle a\rangle b \cup \cdots \cup \langle a\rangle b^{m-1}.$
We can further extend this coloring upwards: color upper levels inductively, one level at a time, and coloring neighboring vertices of already colored vertices at each step. In this way, it is possible to guarantee that each vertex will have at most two already colored neighbors. With this, we see that it is possible to extend the coloring to all elements of the form
$a^kb^i$
,
$k\in \mathbb {Z}$
,
$i\ge 0$
.
Finally, we note that the same method works for extending the coloring into the
$b^{-1}$
direction, and into the new sheets that appear when traversing this direction. Again, simply color one level at a time making sure that when coloring one vertex it has at most two already colored neighbors.
4.2 Mixing and frozen colorings
Owing to Proposition 4.2, we know that for
$n\ge 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.6. 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.7. Let
$n\ge 5$
and consider two non-adjacent finite subsets
$F_1,F_2\subseteq \mathrm {BS}(1,N)$
, that is, such that
$$ \begin{align*}( F_1\cdot \{e_{\mathrm{BS}(1,N)},a,a^{-1},b,b^{-1}\})\cap F_2=\varnothing.\end{align*} $$
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\ge 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 so 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\ge 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 \{a^{2m+1}\mid m\in \mathbb {Z} \}$
, which forbids the gluing of patterns at arbitrarily large distances. This contrast between
$\mathcal {C}_2$
and
$\mathcal {C}_n$
for
$n\ge 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 [Reference Alon, Briceño, Chandgotia, Magazinov and Spinka1], by introducing the concept of a frozen coloring.
Definition 4.8. Let
$n\ge 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, 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 remarked in Theorem 4.4 of [Reference Alon, Briceño, Chandgotia, Magazinov and Spinka1] for
$\mathbb {Z}^d$
. In the following proposition, we state and prove the precise result in our context.
Proposition 4.9. If
$\mathcal {C}_n$
has a frozen coloring and
$|\mathcal {C}_n|\ge 2$
, 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 $
. Denote by
$|\cdot |$
the word metric in
$\mathrm {BS}(1,N)$
, as defined in §2.3. Considering the patterns
$y|_{e_{\mathrm {BS}(1,N)}}$
and
$x|_{\partial B_M}$
, where
$\partial B_M:= \{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}:= \{g\in \mathrm {BS}(1,N): |g|\le 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.7 that the GCS
$\mathcal {C}_n$
for
$n\ge 5$
is strongly irreducible, and so 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
$\mathcal {C}_n$
for
$N\ge 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.10. 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, according to the value of
$N\ (\mathrm {mod} \ 3)$
. In each case, we will define explicitly a frozen coloring by defining the value of each element of
$\mathrm {BS}(1,N)$
according to its normal form.
Let us suppose first that
$N=1 \ (\mathrm {mod} \ 3)$
, and with it that for every
$i\ge 0$
, we have
$N^i=1 \ (\mathrm {mod} \ 3)$
. Define the configuration
$x\in \{0,1,2\}^{\mathrm {BS}(1,N)}$
in the following way. For
$g=b^{-j}a^kb^i\in \mathrm {BS}(1,N)$
written in its normal form:
$$ \begin{align*}x_g:= 2(i-j)+k \ (\mathrm{mod} \ 3). \end{align*} $$
This configuration is illustrated in Figure 5 for
$N=4$
.
Construction of a frozen
$3$
-coloring for
$N=1\ (\mathrm {mod} \ 3)$
. Here
$N=4$
.
Note that
$gb=b^{-j}a^kb^{i+1}$
and that
$ga=b^{-j}a^kb^{i}a=b^{-j}a^{k+N^{i}}b^{i}$
. Hence, using the fact that
$N^i=1 \ (\mathrm {mod} \ 3)$
, we see that
$$ \begin{align*} x_{gb}&= x_g+2 \ (\mathrm{mod} \ 3) \text{ and }\\ x_{ga}&=x_{g}+N^{i} \ (\mathrm{mod} \ 3)=x_{g}+1 \ (\mathrm{mod} \ 3). \end{align*} $$
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$
.
Now consider g in F which maximizes the value of
$i+k$
in its normal form. In other words,
$$ \begin{align*}g:= \mathrm{arg\max}\{i+k\mid g=b^{-j}a^kb^i\in F, \ k\in \mathbb{Z}, i,j\ge 0 \}. \end{align*} $$
By definition, we must have that
$gb\notin F$
and that
$ga\notin F$
, since otherwise we would arrive at a contradiction with the maximality of the coordinates of g.
As y and x coincide outside of F, we see that
$y_{gb}=x_{gb}=x_g+2\ (\mathrm {mod} \ 3)$
, and
$y_{ga}=x_{ga}=x_g+1\ (\mathrm {mod} \ 3)$
, Moreover, as y defines a proper coloring we must have
$y_g=x_g$
. This gives a contradiction since as
$g\in F$
, we should have
$y_g\neq x_g$
.
Now suppose that
$N=2\ (\mathrm {mod} \ 3)$
. Note that now we have that, for
$i\ge 0$
,
$$ \begin{align*} N^i=\left\{ \begin{aligned} &1 \ (\mathrm{mod} \ 3) \quad\text{if }i\text{ is even}, \\ &2 \ (\mathrm{mod} \ 3) \quad\text{if }i\text{ is odd.} \end{aligned} \right. \end{align*} $$
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:
$$ \begin{align*} x_g:= i-j+k \ (\mathrm{mod} \ 3). \end{align*} $$
This configuration is illustrated in Figure 6.
Construction of a frozen
$3$
-coloring for
$N=2\ (\mathrm {mod} \ 3)$
. Here
$N=2$
.
Then, similar as before, we have
$$ \begin{align*} x_{gb}&=x_g+1 \ (\mathrm{mod} \ 3), \text{ and} \\ x_{ga}&=x_g+N^i \ (\mathrm{mod} \ 3), \end{align*} $$
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$
. Define
$i_{\mathrm \max }:= \max \{ i\ge 0\mid b^{-j}a^kb^i\in F, \text { for some }k\in \mathbb {Z}, \ j\ge 0 \}$
and
$B_{\mathrm \max }:= \{g=b^{-j}a^kb^{i_{\mathrm \max }}\mid \ g\in F\}$
.
If
$i_{\mathrm \max }$
is even, let us take
$g=b^{-j}a^kb^i\in {B_{\max }}$
which minimizes the value of k. Then as
${i_{\max }}$
is even, we have
$N^{i_{\max }}=1 \ (\mathrm {mod} \ 3)$
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)$
. However, 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_{\mathrm \max }$
is odd, let us consider the element
$g=b^{-j}a^kb^i\in {B_{\max }}$
which maximizes the value of k. Then as
$i_{\mathrm \max }$
is odd, we have
$N^{i_{\mathrm \max }}=2 \ (\mathrm {mod} \ 3)$
and with it,
$y_{gb}=x_{gb}=x_g+1 \ (\mathrm {mod} \ 3)$
and
$y_{ga}=x_{ga}=x_g+N^{i_{\mathrm \max }} = x_g+2 \ (\mathrm {mod} \ 3)$
. However, 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 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}$
). However, 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 still manage to prove the existence of a frozen coloring.
To make the proof more clear, we will start with the case
$N=3$
. 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:
$$ \begin{align*} x_g=(k \ \mathrm{mod}\ 2)+ 2(i-j)\ \mathrm{mod}\ 3. \end{align*} $$
This configuration is illustrated in Figure 7.
Construction of a frozen
$3$
-coloring for
$N=0\ (\mathrm {mod} \ 3)$
. Here
$N=3$
.
Then, using that
$gb=b^{-j}a^kb^{i+1}$
and
$ga=b^{-j}a^{k+3^i}b^{i}$
, we have
$$ \begin{align*} x_{gb}= (k\ \mathrm{mod}\ 2)+2(i+1-j)\ \mathrm{mod}\ 3=x_{g}+2\ \mathrm{mod} \ 3, \text{ and } \end{align*} $$
$$ \begin{align*} x_{ga}&=(k+3^{i}\ \mathrm{mod} \ 2)+ 2(i-j) \ \mathrm{mod}\ 3 \\ &=(k+1\ \mathrm{mod} \ 2)+ 2(i-j) \ \mathrm{mod}\ 3\\ &=\left\{\begin{aligned} x_{g}+1 \ \mathrm{mod}\ 3 &\quad\text{if }k=0\ \mathrm{mod}\ 2, \\ x_{g}+2 \ \mathrm{mod}\ 3 &\quad\text{if }k=1\ \mathrm{mod}\ 2. \end{aligned} \right. \end{align*} $$
Again, in all cases,
$x_{gb}$
and
$x_{ga}$
are different from x, and so
$x\in \mathcal {C}_3$
defines a proper coloring.
Let us now see that x is a frozen coloring. Suppose that there exists
$y\in \mathcal {C}_3$
and
$F\subseteq \mathrm {BS}(1,3)$
finite with
$x|_{F^{c}}=y|_{F^{c}}$
, and such that for any
$f\in F$
:
$x_f\neq y_f$
.
Define
$k_{\mathrm \max }:= \{ k\in \mathbb {Z}\mid \ b^{-j}a^kb^i\in F \}$
. We have two cases. If
$k_{\mathrm \max }=0\ \mathrm {mod} \ 2$
, choose
$g=b^{-j}a^{k_{\mathrm \max }}b^i\in F$
which maximizes the value of i. Then
$gb\notin F$
and
$ga\notin F$
. However, by the definition of x and as y coincides with x outside F, we must have
$$ \begin{align*} y_{gb}=x_{gb}=x_{g}+2\ \mathrm{mod}\ 3, \quad\text{and}\quad y_{ga}=x_{ga}=x_{g}+1\ \mathrm{mod}\ 3. \end{align*} $$
This is a contradiction, since it implies that
$y_g=x_g$
, for
$g\in F$
.
The case
$k_{\mathrm \max }=1\ \mathrm {mod}\ 2$
is similar. Choose
$g=b^{-j}a^{k_{\mathrm \max }}b^{i}\in F$
which minimizes
$(i-j)$
. Then
$ga\not \in F$
and so
$y_{ga}=x_{ga}=x_{g}+2\ \mathrm {mod}\ 3$
. On the other hand, we also have that
$gb\not \in F$
. If
$i\ge 1$
, this implies that
$$ \begin{align*} x_{gb^{-1}}&=(k\ \mathrm{mod}\ 2)+2(i-j-1)\ \mathrm{mod}\ 3\\ &=(k\ \mathrm{mod} 2)+2(i-j)+1\ \mathrm{mod}\ 3\\ &=x_g+1\ \mathrm{mod}\ 3. \end{align*} $$
Finally, if
$i=0$
, then
$$ \begin{align*} x_{gb^{-1}}&=x_{b^{-j-1}}a^{k_{\mathrm\max}\cdot 3}\\ &=(k_{\mathrm\max}\cdot 3 \ \mathrm{mod}\ 2)+2(-j-1)\ \mathrm{mod}\ 3\\ &=x_g+1\ \mathrm{mod}\ 3. \end{align*} $$
In all cases,
$y_{gb^{-1}}=x_{gb^{-1}}=x_{g}+1\ \mathrm {mod} \ 3$
. As we have already seen that
$y_{ga}=x_{g}+2 \mathrm {mod}\ 3$
, this implies that
$y_g=x_g$
, which is a contradiction since
$g\in F$
.
Now we can do the general case, that is, suppose that
$N=0 \ \mathrm {mod} \ 3$
, for
$N \ge 6$
. Define the configuration
$x\in \{0,1,2\}^{\mathrm {BS}(1,N)}$
by assigning to each
$g=b^{-j}a^kb^{i}\in \mathrm {BS}(1,N)$
written in its normal form:
$$ \begin{align*}x_g=(k\ \mathrm{mod}\ (N-1))+ 2(i-j)\ \mathrm{mod}\ 3. \end{align*} $$
Then
$x_{gb}=x_g+2 \ \mathrm {mod} \ 3$
, and
$$ \begin{align*} x_{ga}&=(k+N^i \ \mathrm{mod}\ (N-1))+2(i-j)\ \mathrm{mod}\ 3\\ &=(k+1 \ \mathrm{mod}\ (N-1))+2(i-j)\ \mathrm{mod}\ 3\\ &=\begin{cases} x_g+1 \ \mathrm{mod}\ 3 &\quad\text{if } 0\le k\ \mathrm{mod}\ (N-1) <N-2,\\ x_g-(N-2) \ \mathrm{mod}\ 3 &\quad\text{if } k=N-2 \ \mathrm{mod}\ (N-1). \end{cases} \end{align*} $$
Hence, using that
$N=0\ \mathrm {mod}\ 3$
, we have that
$$ \begin{align*}x_{ga}=\begin{cases} x_g+1 \ \mathrm{mod} \ 3&\text{ if } 0\le k\ \mathrm{mod}\ (N-1) <N-2,\\ x_{g}+2 \ \mathrm{mod} \ 3 &\text{ if }k=N-2 \ \mathrm{mod}\ (N-1). \end{cases} \end{align*} $$
We conclude that
$x\in \mathcal {C}_3$
defines a proper coloring.
Now let us prove that x is a frozen coloring. Suppose there exists
$y\in \mathcal {C}_3$
and a finite subset
$F\subseteq \mathrm {BS}(1,N)$
with
$x|_{F^{c}}=y|_{F^c}$
and such that for every
$f\in F$
:
$x_f\neq y_f$
.
Define
$k_{\mathrm \max }:= \max \{k\in \mathbb {Z}\mid \ b^{-j}a^kb^i\in F \}$
. We have two cases.
First, suppose that
$k_{\mathrm \max } \ \mathrm {mod} (N-1)<N-2$
. Then choose an element
$g=b^{-j}a^kb^i\in F$
which maximizes i, so that
$gb\notin F$
and
$ga\notin F$
. We conclude that
$y_{gb}=x_{gb}=x_g+2 \mathrm {mod}\ 3$
and that
$y_{ga}=x_{ga}=x_g+1\ \mathrm {mod}\ 3$
, which leads to the equality
$x_g=y_g$
. This is a contradiction with the choice of y.
Now suppose that
$k_{\mathrm \max }=N-2\ \mathrm {mod}\ (N-1)$
. Then choose
$g=b^{-j}a^{k_{\mathrm \max }}b^i\in F$
which minimizes the value of
$(i-j)$
. As
$ga\notin F$
, we have that
$y_{ga}=x_{ga}=x_g+2 \mathrm {mod}\ 3$
. On the other hand, by the choice of g, we have that
$gb^{-1}\notin F$
.
If
$i\ge 1$
, then
$gb^{-1}=b^{-j}a^kb^{i-1}$
and so
$$ \begin{align*} y_{gb^{-1}}=x_{gb^{-1}}&=(k\ \mathrm{mod}\ (N-1))+2(i-1-j)\ \mathrm{mod}\ 3\\ &=x_g+1\ \mathrm{mod}\ 3. \end{align*} $$
Meanwhile, if
$i=0$
, then
$gb^{-1}=b^{-j}a^kb^{-1}=b^{-j-1}a^{kN}$
, and so
$$ \begin{align*}y_{gb^{-1}}=x_{gb^{-1}}=(kN \ \mathrm{mod}\ (N-1))+2(-j-1)\ \mathrm{mod}\ 3=x_{g}+1\ \mathrm{mod}\ 3. \end{align*} $$
In both cases, we conclude that
$y_g=x_g$
and this is a contradiction.
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\ge 5$
. To tackle the case of four colors, and in the process give an alternative proof of the lack of frozen colorings for
$n\ge 5$
, we will use a proposition from [Reference Alon, Briceño, Chandgotia, Magazinov and Spinka1] used in that paper to prove the lack of frozen n-colorings in
$\mathbb {Z}^d$
for
$n\ge d+2$
.
Proposition 4.11. [Reference Alon, Briceño, Chandgotia, Magazinov and Spinka1, Proposition 2.2]
For a graph
$\Gamma $
, let us define its edge-isoperimetric constant by
$$ \begin{align*} i_e(\Gamma):= \inf_{F\subseteq \Gamma \text{ finite}}\frac{|E(F,\Gamma\backslash F)|}{|F|}, \end{align*} $$
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>\tfrac 12\Delta +\tfrac 12i_e(\Gamma )+1$
, there do not exist frozen n-colorings of
$\Gamma $
.
Theorem 4.12. For
$n\ge 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.11, for
$n>\tfrac 12\cdot 4+\tfrac 12\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\ge 1: \ \gamma _{k}:= |E(R_k,\Gamma \backslash R_k)|$
. We see that
$\gamma _1=2N+2$
, and that for every
$k\ge 2$
:
$$ \begin{align*} \gamma_k=N^k+2+N(\gamma_{k-1}-N^{k-1})=2+N\gamma_{k-1}, \end{align*} $$
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}$
. By solving this recursion, we arrive at
$\gamma _{m}=2(({N^{m+1}-1})/({N-1}))$
, and with it give an estimate for the edge-isoperimetric constant:
$$ \begin{align*} i_e(\Gamma)\le \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. \end{align*} $$
Hence
$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.13. For
$n\ge 3$
, we have the following estimate for the topological entropy of the GCS
$\mathcal {C}_n$
:
$$ \begin{align*} \log(n-2)\le h_{\mathrm{top}}(\mathcal{C}_n)\le \log(n-1). \end{align*} $$
Proof Let us see that
$h_{\mathrm {top}}(\mathcal {C}_n)\le \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:
$$ \begin{align*} |\mathcal{L}_{R_{m+1}}(\mathcal{C}_n)|\le |\mathcal{L}_{R_m}(\mathcal{C}_{n})|(n-1)^{|R_{m+1}\backslash R_m|}. \end{align*} $$
A simple calculation shows that
$|R_{m+1}\backslash R_{m}|=N^m(mN+N-m)$
. With this:
$$ \begin{align*} \frac{1}{|R_{m+1}|}\log|\mathcal{L}_{R_{m+1}}(\mathcal{C}_n)|&=\frac{1}{(m+1)N^{m+1}}\log|\mathcal{L}_{R_{m+1}}(\mathcal{C}_n)|\\ &\le \frac{1}{(m\kern1pt{+}\kern1pt1)N^{m\kern1pt{+}\kern1pt1}}\log|\mathcal{L}_{R_m}(\mathcal{C}_{n})|\kern1pt{+}\kern1pt\frac{N^m(mN\kern1pt{+}\kern1pt N-m)}{(m\kern1pt{+}\kern1pt1)N^{m\kern1pt{+}\kern1pt1}}\log(n\kern1pt{-}\kern1pt1)\\ &=\frac{1}{N}\frac{m}{m\kern1.5pt{+}\kern1.5pt1}\frac{1}{mN^{m}}\log|\mathcal{L}_{R_m}(\mathcal{C}_{n})|\kern1.5pt{+}\kern1.5pt \frac{mN\kern1.5pt{+}\kern1.5pt N\kern1.5pt{-}\kern1.5pt m}{m\kern1.5pt{+}\kern1.5pt1}\frac{1}{N}\log(n\kern1.5pt{-}\kern1.5pt1)\\ &=\frac{1}{N}\frac{m}{m\kern1.5pt{+}\kern1.5pt1}\frac{1}{|R_m|}\log|\mathcal{L}_{R_m}(\mathcal{C}_{n})|\kern1.5pt{+}\kern1.5pt \frac{m(N\kern1.5pt{-}\kern1.5pt1)\kern1.5pt{+}\kern1.5pt N}{m\kern1.5pt{+}\kern1.5pt 1}\frac{1}{N}\log(n\kern1.5pt{-}\kern1.5pt1). \end{align*} $$
Taking the limit
$m\to \infty $
, we arrive at
$$ \begin{align*} h_{\mathrm{top}}(\mathcal{C}_n)&=\lim_{m\to \infty } \frac{1}{|R_{m+1}|}\log|\mathcal{L}_{R_{m+1}}(\mathcal{C}_n)|\\ &\le \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)\\ &= \frac{1}{N}h_{\mathrm{top}}(\mathcal{C}_n)+\frac{N-1}{N}\log(n-1), \end{align*} $$
from where
$$ \begin{align*}h_{\mathrm{top}}(\mathcal{C}_n)\le \log(n-1).\end{align*} $$
Now let us see that
$h_{\mathrm {top}}(\mathcal {C}_n)\ge \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.5 and so forming a globally admissible configuration for
$\mathcal {C}_n$
. From this, we arrive at
$$ \begin{align*} |\mathcal{L}_{R_m}(\mathcal{C}_{n})|\ge (n-2)^{|R_m|}, \end{align*} $$
and so
$h_{\mathrm {top}}(\mathcal {C}_n)\ge \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\ge 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)\ge 0$
. In the next proposition, we show that indeed
$h_{\mathrm {top}}(\mathcal {C}_3)>0$
, dividing the proof into 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.14. 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 then so is every rectangle
$R_m$
, for
$m\ge 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
$\tfrac 12|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
$$ \begin{align*} |\mathcal{L}_{R_m}(\mathcal{C}_3)|\ge 2^{|A|}\ge 2^{{1}/{2}|R_m|}. \end{align*} $$
Then taking the logarithm and dividing by
$|R_m|$
, we arrive at
$$ \begin{align*} \frac{1}{|R_m|}\log |\mathcal{L}_{R_m}(\mathcal{C}_3)| \ge \frac{1}{2}\log (2), \end{align*} $$
to finally take the limit as
$m\to \infty $
and obtain
$$ \begin{align*} h_{\mathrm{top}}(\mathcal{C}_3)\ge \tfrac{1}{2}\log(2)>0, \end{align*} $$
which is what we wanted.
Now consider the case of even N. For
$m\ge 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
$$ \begin{align*} p|_{[e_{\mathrm{BS}(1,N)},a^{N^{2m}-1}]}=(0(12)^{N^2/2})^{\infty}|_{[0,N^{2m}-1]}. \end{align*} $$
That is, we are putting in the elements
$\{a^{0},a^{1},\ldots ,a^{N^{2m}-1}\}$
an initial segment of the infinite
$(N^2+1)$
-periodic sequence
$(0(12)^{N^2/2})^{\infty }$
. Moreover, we will copy this sequence upwards into even levels: for
$k\in \{0,\ldots ,N^{2m}-1\}$
and
$0\le i<m$
, we define
$$ \begin{align*} p_{a^{k}b^{2i}}=p_{a^k}. \end{align*} $$
Note that
$a^kb^{2i}a=a^{k+N^{2i}}b^{2i}$
and that
$N^{2i}=(N^{2})^i=(-1)^{i}\ \mathrm {mod}(N^2+1)$
. This means that at level
$2i$
, we see either (a shift of) the sequence
$(0(12)^{N^2/2})^{\infty }$
or
$(0(21)^{N^2/2})^{\infty }$
. In particular, up until now, p satisfies the rules for being a proper coloring.
It remains to define p at odd levels. Fix
$0\le i<m$
, and consider the level
$2i+1$
. We will define p at this level so that the value
$p_{a^{(N^2+1)k}b^{2i+1}}$
,
$0\le k<({N^{2m}}/({N^2+1}))$
, can take any value in
$\{1,2\}$
and still define a proper coloring. In other words, the element
$a^{(N^2+1)k}b^{2i+1}$
will have all its neighbors assigned the color
$0$
.
Indeed, define for i and k as above, for
$0\le \ell <N^2+1$
, and for any choice
$\alpha (i,\ell ,k)\in \{1,2\}$
:
$$ \begin{align*} p_{a^{(N^2+1)k+\ell}b^{2i+1}}=\begin{cases} \alpha(i,\ell,k) &\text{ if }\ell=0,\\ 0 \ &\text{ if } \ell=N \text{ or }\ell=N^2+1-N,\\ 1\ &\text{ if } \ell\notin\{N,N^2+1-N\} \text{ and }\ell \text{ is even,}\\ 2\ &\text{ if } \ell\notin\{N,N^2+1-N\} \text{ and }\ell \text{ is odd}. \end{cases} \end{align*} $$
Since
$$ \begin{align*}p_{a^{(N^2+1)k+\ell}b^{2i}}=\begin{cases} 1 &\text{ if }\ell \text{ is odd,}\\ 2 &\text{ if }\ell \text{ is even,}\\ \end{cases}\end{align*} $$
for i, k as above, and for
$0<\ell <N^2+1$
, we see that p defines a proper coloring in
$\mathcal {C}_3$
. This configuration is illustrated in 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
$$ \begin{align*} |\mathcal{L}_{R_{2m}}(\mathcal{C}_3)|\ge 2^{m\lfloor {N^{2m}}/({N^2+1})\rfloor }, \end{align*} $$
and hence
$$ \begin{align*} \frac{1}{|R_{2m}|}\log |\mathcal{L}_{R_{2m}}(\mathcal{C}_3)|&\ge\frac{m\lfloor {N^{2m}}/({N^2+1})\rfloor}{2mN^{2m}}\log(2) \\ &\ge \frac{({N^{2m}}/({N^2+1}))-1}{2N^{2m}}\log(2). \end{align*} $$
Finally, taking limit as
$m\to \infty $
, we obtain
$$ \begin{align*} h_{\mathrm{top}}(\mathcal{C}_3)\ge \frac{1}{2(N^2+1)}\log(2)>0.\\[-42pt] \end{align*} $$
5 Further questions and possible generalizations
It is interesting to think about how the properties from §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 into two cases depending on the nature of the Cayley graph of the group G with respect to the chosen generating set, depending on whether it is bipartite or not. Results will also depend on the value of the index
$|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 5.1. How do the topological entropy related results from Theorem 1.3 generalize to GCS in
$G*_{\psi }$
?
With respect to frozen colorings, Proposition 4.11 was fundamental for proving the absence of such configurations for
$n\ge 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.10 was somehow involved and it does not generalize immediately to the case of
$G*_{\psi }$
.
Problem 5.2. Find explicit constructions of frozen
$3$
-colorings on
$G*_{\psi }$
.
A final remark is that most of the results obtained in §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 5.3. Consider a finitely generated abelian group G, two different (non-trivial, non-surjective) monomorphisms
$\psi , \psi ':G\to G$
, and the corresponding ascending HNN-extensions
$G*_{\psi }$
and
$G*_{\psi '}$
. For
$n\ge 3$
, what are the dynamical differences between the corresponding GCS associated to
$G*_{\psi }$
and
$G*_{\psi '}$
? In particular, do they have equal topological entropy?
Acknowledgments
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.
