The Number of Configurations in the Full Shift with a Given Least Period

Abstract

For any group G and any set A, consider the shift action of G on the full shift $A^G$. A configuration $x \in A^G$ has least period $H \le G$ if the stabiliser of x is precisely H. Among other things, the number of such configurations is interesting as it provides an upper bound for the size of the corresponding $\mathrm {Aut}(A^G)$-orbit. In this paper, we show that if G is finitely generated and H is of finite index, then the number of configurations in $A^G$ with least period H may be computed by using the Möbius function of the lattice of subgroups of finite index in G. Moreover, when H is a normal subgroup, we classify all situations such that the number of G-orbits with least period H is at most 10.

1 Introduction

Let G be a group and let A be a set. Consider the set $A^G$ of all functions from G to A equipped with the shift action of G, defined by

$$\begin{aligned} (g \cdot x) (h) := x(g^{-1}h), \end{aligned}$$

for all $g, h \in G$ and $x \in A^G$. Although we shall not focus on this, the set $A^G$ is usually seen as a topological space with the product topology of the discrete topology on A.

The G-space $A^G$ is a fundamental object in areas such as symbolic dynamics and the theory of cellular automata (e.g. see [4, 10]). Following [4], we call the elements of $A^G$ configurations. For any $x \in A^G$, the stabiliser $G_x$ of x and the G-orbit Gx of x are defined as follows:

$$\begin{aligned} G_x := \{ g \in G : g \cdot x = x \} \quad \text { and } \quad Gx := \{ g \cdot x \in A^G : g \in G \}. \end{aligned}$$

For a subgroup H of G, a configuration $x \in A^G$ has period H, or is H-periodic, if $h \cdot x = x$ for all $h \in H$, or, equivalently, if $H \le G_x$. Denote by $\mathrm {Fix}(H)$ the subset of $A^G$ consisting of all H-periodic configurations. It is known (see [4, Proposition 1.3.3]) that $\mathrm {Fix}(H)$ is in bijection with $A^{H{\setminus } G}$, where $H{\setminus } G = \{ Hg :g \in G \}$ is the set of rights cosets of H in G. Hence, it follows that $\vert \mathrm {Fix}(H) \vert = \vert A \vert ^{[G:H]}$, where $[G:H] := \vert H{\setminus } G \vert$ is the index of H in G. In particular, the configurations whose period is the trivial subgroup of G are known as aperiodic points, and have been used in [6] as powerful tools to study the dynamics in $A^G$ and its subshifts, or subflows (i.e. closed G-equivariant subsets of $A^G$).

We say that $x \in A^G$ has least period, or fundamental period, H if $G_x = H$ (c.f. [10, Definition 1.1.3.]). In this paper, we are interested in the number $\psi _H(G;A)$ of configurations with least period H:

$$\begin{aligned} \psi _H(G;A) := \vert \{ x \in A^G : G_x = H \} \vert . \end{aligned}$$

If $x,y \in A^G$ satisfy that $y=g\cdot x$, then $G_y = g G_x g^{-1}$; hence, it is sometimes convenient to consider the G-invariant set $\{ x \in A^G : [G_x] = [H] \}$, where $[H] := \{gHg^{-1} : g \in G \}$ is the conjugacy class of H, and its cardinality

$$\begin{aligned} \psi _{[H]}(G;A) := \vert \{ x \in A^G : [G_x] = [H] \} \vert . \end{aligned}$$

As $\psi _{H}(G;A) = \psi _{gHg^{-1}}(G;A)$ for all $g \in G$, we have

$$\begin{aligned} \psi _{[H]}(G;A) = \vert [H] \vert \; \psi _H(G;A). \end{aligned}$$

Finally, we also consider the number of G-orbits whose stabiliser is conjugate to H:

$$\begin{aligned} \alpha _{[H]}(G;A) := \vert \{ Gx : [G_x] = [H] \} \vert . \end{aligned}$$

By the Orbit-Stabiliser Theorem [14, Theorem 7.2.1], all G-orbits inside $\{ x \in A^G : [G_x] = [H]\}$ have size [G : H]; therefore, we have

$$\begin{aligned} \alpha _{[H]}(G;A) \; [G:H] = \psi _{[H]}(G;A). \end{aligned}$$

Besides being interesting for their own right, the above numbers have connections with the structure of the automorphism group of $A^G$. Recall that a map $\tau : A^G \rightarrow A^G$ is G-equivariant if $\tau (g \cdot x) = g \cdot \tau (x)$, for all $g \in G$, $x \in A^G$. Let $\mathrm {Aut}(A^G)$ the group of all G-equivariant homeomorphisms of $A^G$. By the Curtis–Heldund Theorem [4, Theorem 1.8.1], $\mathrm {Aut}(A^G)$ is the same as the group of invertible cellular automata of $A^G$. It follows by G-equivariance that for every $\tau \in \mathrm {Aut}(A^G)$, $x \in A^G$, we have $G_{x} = G_{\tau (x)}$. Thus, $\psi _{G_x}(G;A)$ is an upper bound for the cardinality of the $\mathrm {Aut}(A^G)$-orbit of x. Moreover, if the group G is finite, the structure of $\mathrm {Aut}(A^G)$ was described in [3, Theorem 3] as

$$\begin{aligned} \mathrm {Aut}(A^G) \cong \prod _{i=1}^{r} ( (N_G(H_i)/H_i) \wr \mathrm {Sym}_{\alpha _i}), \end{aligned}$$

(1.1)

where $[H_1], \dots , [H_r]$ is the list of all different conjugacy classes of subgroups of G, and $\alpha _i = \alpha _{[H_i]}(G;A)$, as defined above. Hence, the structure of $\mathrm {Aut}(A^G)$ completely depends on the quotient groups $N_G(H_i)/H_i$, which may be easily calculated by knowing the group G, and the integers $\alpha _{[H_i]}(G;A)$, which depend on $\psi _H(G;A)$. Finally, in [1, 2], the sets of points of a given least period were a fundamental tool in the study of automorphism groups of shifts of finite type, which include the group $\mathrm {Aut}(A^{{\mathbb {Z}}})$.

As $\psi _H(G;A)$ is finite if and only if [G : H] is finite (see Lemma 2.1 below), we shall focus on finite index subgroups of G. In the first part of this paper, we prove that, when G is finitely generated, the poset L(G) of finite index subgroups of G is a locally finite lattice, so we use Möbius inversion to show that

$$\begin{aligned} \psi _H(G;A) = \sum _{H \le K \le G} \mu (H,K) \vert A \vert ^{[G:K]}, \end{aligned}$$

(1.2)

where $\mu$ is the Möbius function of L(G). In the second part of this paper, we note that if H is a normal subgroup, then $\psi _H(G;A) = \psi _1(G/H;A)$ and $\alpha _{[H]}(G;A) = \alpha _{[1]}(G/H;A)$. Hence, by computing the Möbius function of the subgroup lattice of all finite groups of size up to 7, we classify under which situations we have $\alpha _{[H]}(G;A) \le 10$.

Our work generalises previous results known in the literature. When $G = {\mathbb {Z}}_n$ is a cyclic group and $H=1$ is the trivial subgroup, $\alpha _{[1]}({\mathbb {Z}}_n;A)$ is equivalent to the number of aperiodic necklaces of length n, and equation (1.2) gives the so-called Moreau’s necklace-counting function [12]. Moreover, $\alpha _{[1]}({\mathbb {Z}}_n;A)$ is also equivalent to the number of Lyndon words of length n [11, Sect. 5.1] . For a finite group G, this equation may be derived using the result of [9, Sect. 4]. However, as far as we know, Eq. (1.2) had not been derived when G is an arbitrary finitely generated group.

2 Periodic Configurations when G is Finitely Generated

For the rest of the paper, let A be a set with at least two elements and assume that $\{0,1 \} \subseteq A$. We begin by justifying our claim that $\psi _H(G;A)$ is finite if and only if [G : H] is finite.

Lemma 2.1

Let G be a group and let H be a subgroup of G. Then $\psi _H(G;A)$ is finite if and only if [G : H] is finite.

Proof

If [G : H] is finite, then $\psi _H(G;A)$ is clearly finite, as every configuration with least period H is contained in $\mathrm {Fix}(H)$ and $\vert \mathrm {Fix}(H) \vert = \vert A \vert ^{[G:H]} < \infty$.

Conversely, suppose that [G : H] is infinite. Let $T \subseteq G$ be a transversal for the set of right cosets of H in G, i.e., T contains exactly one element from each right coset of H in G. It is clear that $\vert T \vert = [G:H]$. For each $s \in T$, consider the configuration $x_s \in A^G$ defined by

$$\begin{aligned} x_s(g) = {\left\{ \begin{array}{ll} 1 &{} \text { if } g \in Hs \\ 0 &{} \text { otherwise} \end{array}\right. } ,\end{aligned}$$

for any $g \in G$. Given $h \in H$, then $h \cdot x_s(g) = x_s(h^{-1}g) = x_s(g)$, as $h^{-1}g \in Hs$ if and only if $g \in Hs$. Hence, $H \le G_{x_s}$. On the other hand, if $k \in G_{x_s}$, then $k \cdot x_s = x_s$; in particular we have $(k \cdot x_s)(s) =x_s(k^{-1}s) = x_s(s) = 1$, which implies that $k^{-1}s \in Hs$. Therefore, $k \in H$, which shows that $G_{x_s}=H$. As $\vert T \vert = [G:H]$ is infinite, we have constructed infinitely many different configurations with least period H, which establishes that $\psi _{H}(G;A)$ is infinite. $\square$

We shall recall some basic definitions on posets; for further details see [15, Ch. 3]. Recall that a partially ordered set, or a poset, is a set P equipped with a partial order relation $\le$. Given $s, t \in P$ with $s \le t$, define the closed interval $[s,t] := \{ u \in P : s \le u \le t \}$. We say that P is locally finite if every closed interval of P is finite. A chain of P is a subposet S of P that is totally ordered, i.e. any two elements of S are comparable. For $t \in P$, the principal order ideal generated by t is $\Lambda _t := \{ s \in P : s \le t \}$, and the principal dual order ideal generated by t is $V_t := \{s \in P : s \ge t \}$.

A lattice is a poset L for which every pair of elements $s,t \in L$ has a lest upper bound, denoted by $s \vee t$ and read s join t, and a greatest lower bound, denoted by $s \wedge t$ and read s meet t.

The Möbius function of a locally finite poset P is the map $\mu : P \times P \rightarrow {\mathbb {Z}}$ defined inductively by the following equations:

$$\begin{aligned} \mu (a,a)&= 1, \ \ \forall a \in P, \\ \mu (a,b)&= 0, \ \ \forall a \not \le b, \\ \sum _{a \le c \le b} \mu (a,c)&= 0, \ \ \forall a < b. \end{aligned}$$

The Möbius function is the inverse of the zeta function of a locally finite poset, and it importantly satisfies the so-called Möbius inversion formula (see [15, Sect. 3.7]). In this section we shall use the dual form of the Möbius inversion formula [15, Proposition 3.7.2].

Theorem 2.2

(Möbius inversion formula, dual form). Let P be a poset for which every principal dual order ideal $V_t$ is finite. Consider functions $f,g : P \rightarrow K$, where K is a field. Then

$$\begin{aligned} g(t) = \sum _{s \ge t} f(s), \quad \forall t \in P, \end{aligned}$$

if and only if

$$\begin{aligned} f(t) = \sum _{s \ge t} g(s) \mu (t,s), \quad \forall t \in P. \end{aligned}$$

For any group G, it is standard to consider the poset of all subgroups of G ordered by inclusion. Here, we shall consider the poset L(G) of all subgroups of G of finite index ordered by inclusion. The following is a key observation for this section.

Lemma 2.3

The poset L(G) is a lattice. Furthermore, if G is finitely generated, then for every $H \in L(G)$, the principal dual order ideal $V_H = \{ K \le G : H \le K \}$ is finite, so L(G) is a locally finite lattice.

Proof

We shall show that L(G) is a sublattice of the subgroup lattice of G by showing that it is closed under the join, given by $H \vee J = \langle H \cup J \rangle$, and the meet, given by $H \wedge J = H \cap J$.

Let H and K be subgroups of G such that $H \le K$. It is well-known (see, for instance [14, Theorem 3.1.3]) that the indices of H and K in G satisfy, as cardinal numbers, that

$$\begin{aligned}{}[G:H] = [G:K] [K:H]. \end{aligned}$$

Hence, if [G : H] is finite, then [G : K] must be finite. This implies that for any $H, J \in L(G)$, then $\langle H \cup J \rangle \in L(G)$. On the other hand, it is also well-known (see, for instance [14, Theorem 3.1.6]) that the intersection of subgroups of finite index has finite index, so $H \cap J \in L(G)$, and the first part of the lemma follows.

For the second part, for any $H \in L(G)$ and $K \in V_H$, the index of K in G must be a divisor of [G : H]. The result follows as in a finitely generated group there are only finitely many subgroups of a given finite index (this is a well-known theorem by M. Hall [7]; see also [14, Theorem 4.20]). $\square$

The previous lemma allows us to use the Möbius inversion formula for the poset L(G) when G is finitely generated. Let $\mu$ be the Möbius function of L(G).

Theorem 2.4

Let G be a finitely generated group, let H be a subgroup of G of finite index, and let A be a finite set. Then,

$$\begin{aligned} \psi _H(G;A) = \sum _{H \le K \le G} \mu (H,K) \vert A \vert ^{[G:K]}. \end{aligned}$$

Proof

It follows from the definitions that

$$\begin{aligned} \vert \mathrm {Fix}(H) \vert = \sum _{K \ge H} \psi _K(G;A) . \end{aligned}$$

By Lemma 2.3 this summation is finite and we may use Theorem 2.2, with $g(H) = \vert \mathrm {Fix}(H) \vert$ and $f(K) = \psi _K(G;A)$. Therefore, we obtain

$$\begin{aligned} \psi _H(G;A) = \sum _{K \ge H} \mu (H,K) \vert \mathrm {Fix}(K) \vert . \end{aligned}$$

The result follows as $\vert \mathrm {Fix}(K) \vert = \vert A \vert ^{[G:K]}$ by [4, Proposition 1.3.3]. $\square$

Remark 2.5

Note that, for any $H,J \in L(G)$, the value of $\mu (H,J)$ only depends on the on the interval [H, J]. Hence, $\psi _H(G;A)$ may be calculated by only knowing the subposet [H, G].

Corollary 2.6

With the notation of Theorem 2.4, suppose that the interval from H to G consists of a chain $H = H_0< H_1< \dots < H_k=G$. Then,

$$\begin{aligned} \psi _H(G;A) = \vert A \vert ^{[G:H]} - \vert A \vert ^{[G:H_1]}. \end{aligned}$$

In particular, if H is a maximal subgroup of G, then

$$\begin{aligned} \psi _H(G;A) = \vert A \vert ^{[G:H]} - \vert A \vert . \end{aligned}$$

Proof

By Theorem 2.4,

$$\begin{aligned} \psi _H(G;A) = \sum _{i=0}^k \mu (H,H_i) \vert A \vert ^{[G:H_i]}. \end{aligned}$$

Now, by the definition of the Möbius function,

$$\begin{aligned} \mu (H,H_0)&= 1, \\ \mu (H,H_1)&= -1, \\ \mu (H,H_i)&= 0, \quad \quad \forall i=2,3,\dots , k. \end{aligned}$$

The result follows. $\square$

Corollary 2.7

With the notation of Theorem 2.4,

$$\begin{aligned} \psi _{[H]}(G;A)&= \vert [H] \vert \sum _{H \le K \le G} \mu (H,K) \vert A \vert ^{[G:K]}, \\ \alpha _{[H]}(G;A)&= \frac{\vert [H] \vert }{[G:H]} \sum _{H \le K \le G} \mu (H,K) \vert A \vert ^{[G:K]}. \end{aligned}$$

3 Configurations with Normal Period

In this section, we shall specialise on the case when H is a normal subgroup of G of finite index. In this case, the conjugacy class of H just contains H itself, so

$$\begin{aligned} \psi _H(G;A) = \psi _{[H]}(G;A). \end{aligned}$$

Denote by 1 the trivial subgroup. The following result has been noted in [3, Lemma 6].

Lemma 3.1

Let G be any group and let H be a normal subgroup of G of finite index. Then,

$$\begin{aligned}\psi _H(G;A) = \psi _1(G/H;A) \ \text { and } \ \alpha _{[H]}(G;A) = \alpha _{[1]}(G/H; A). \end{aligned}$$

Proof

By [4, Proposition 1.3.7.], there is a G/H-equivariant bijection between $A^{G/H}$ and $\mathrm {Fix}(H)$. Hence, configurations in $A^{G/H}$ with trivial stabiliser are in bijection with the configurations in $A^G$ with stabiliser equal to H. $\square$

The previous lemma allows to apply the machinery of Möbius functions of subgroup lattices which has been developed for a variety of finite groups (e.g. see [5, 8, 13]).

Recall that the classical Möbius function ${\tilde{\mu }}$ of the poset of natural numbers ${\mathbb {N}}$ ordered by divisibility is given by

$$\begin{aligned} {\tilde{\mu }}(d) = {\left\{ \begin{array}{ll} 0 &{} \text { if }d\text { has a squared prime factor} \\ 1 &{} \text { if }d\text { is square-free with an even number of prime factors} \\ -1 &{} \text { if }d\text { is square-free with an odd number of prime factors}. \end{array}\right. }\end{aligned}$$

Using Lemma 3.1, the following result gives the values of $\psi _H(G;A)$ in some particular cases when H is a normal subgroup of G.

Lemma 3.2

Let G be a finitely generated group, let H be a normal subgroup of G of finite index, and let A be a finite set. Let $n \in {\mathbb {N}}$, and let p and $p^\prime$ be two distinct primes.

• (1) If $G/H \cong {\mathbb {Z}}_n$, then $\psi _{H}(G;A) = \sum _{d \mid n} {\tilde{\mu }}(d) \vert A \vert ^{n/d}$.

• (2) If $G/H \cong {\mathbb {Z}}_{p^k}$, then $\psi _{H}(G;A)= \vert A \vert ^{p^k} - \vert A \vert ^{p^{k-1}}$.

• (3) If $G/H \cong {\mathbb {Z}}_{pp^\prime }$, then $\psi _{H}(G;A)= \vert A \vert ^{pp^\prime } - \vert A \vert ^{p} - \vert A \vert ^{p^\prime }+ \vert A \vert$.

• (4) If $G/H \cong {\mathbb {Z}}_{p} \oplus {\mathbb {Z}}_p$, then $\psi _{H}(G;A) = \vert A \vert ^{p^2} - (p+1)\vert A \vert ^p + p\vert A \vert$.

Proof

Parts (1), (2) and (3) follow as it is well-known that $\mu (1, {\mathbb {Z}}_n) = {\tilde{\mu }}(n)$ (as the subgroup lattice of ${\mathbb {Z}}_n$ is isomorphic to the divisibility lattice of n). For part (4), just observe that the group ${\mathbb {Z}}_{p} \oplus {\mathbb {Z}}_p$ has $\frac{p^2-1}{p-1}=p+1$ subgroups isomorphic to ${\mathbb {Z}}_p$ (as each of the $p^2-1$ nontrivial elements of ${\mathbb {Z}}_{p} \oplus {\mathbb {Z}}_p$ generates a subgroup with $p-1$ nontrivial elements), which account for all its proper nontrivial subgroups. $\square$

In the rest of this section, we shall focus on the exact determination of the small values of $\alpha _{[H]}(G;A)$. The inspiration for this question is [3, Lemma 5], which established, without using the Möbius function, that $\alpha _{[H]}(G;A) = 1$ if and only if $[G:H]=2$ and $\vert A \vert = 2$. In general, the classification of small values of $\alpha _{[H]}(G;A)$ is relevant as it classifies configurations with small $\mathrm {Aut}(A^G)$-orbits, and, when G is finite, it classifies the small degrees of the symmetric groups appearing in the decomposition (1.1) of $\mathrm {Aut}(A^G)$.

For $x \in A^G$, we have $G_x = G$ if and only if x is a constant configuration. As we have precisely $\vert A \vert$ constant configurations in $A^G$, then $\alpha _{[G]}(G;A) = \vert A \vert$. Hence, we shall exclude the case $H=G$ in the following theorem. Moreover, we exclude the degenerate case $\vert A \vert = 1$.

Table 1 Small values for $\alpha _{[H]}(G;A)$ with H normal in G

Theorem 3.3

Let G be a finitely generated group, let H be a proper normal subgroup of G of finite index, and let A a finite set with at least two elements.

• (1) $\alpha _{[H]}(G;A) = 1$ if and only if $\vert A \vert =2$ and $[G:H] = 2$.

• (2) $\alpha _{[H]}(G;A) = 2$ if and only if $\vert A \vert =2$ and $[G:H] = 3$, or $\vert A \vert =2$ and $G/H \cong {\mathbb {Z}}_2 \oplus {\mathbb {Z}}_2$.

• (3) $\alpha _{[H]}(G;A) = 3$ if and only if $\vert A \vert =3$ and $[G:H]=2$, or $\vert A \vert =2$ and $G/H \cong {\mathbb {Z}}_4$.

• (4) $\alpha _{[H]}(G;A) = 6$ if and only if $\vert A \vert =2$ and $[G:H] =5$, or $\vert A \vert =4$ and $[G:H]=2$.

• (5) $\alpha _{[H]}(G;A) = 7$ if and only if $\vert A \vert =2$ and $G/H \cong S_3$.

• (6) $\alpha _{[H]}(G;A) = 8$ if and only if $\vert A \vert =3$ and $[G:H] = 3$.

• (7) $\alpha _{[H]}(G;A) = 9$ if and only if $\vert A \vert =2$ and $G/H \cong {\mathbb {Z}}_6$.

• (8) $\alpha _{[H]} (G;A)= 10$ if and only if $\vert A \vert =5$ and $[G:H]=2$.

• (9) $\alpha _{[H]}(G;A) \ne 4$ and $\alpha _{[H]}(G;A) \ne 5$.

Proof

By [6, Corollary 1.7.2],

$$\begin{aligned} \vert A \vert ^{[G:H]} - \vert A \vert ^{[G:H]-1} \le \alpha _{[1]}(G/H,A) = \alpha _{[H]}(G;A). \end{aligned}$$

(This lower bound has been improved in [3, Theorem 5], but the above is enough for this proof). Hence, we see that $\alpha _{[1]}(G/H,A)$ is a strictly increasing function on both [G : H] and $\vert A \vert$. Table 1 shows all values of $\alpha _{[1]}(G/H,A)$ with $[G:H] \le 7$ and $\vert A \vert \le 5$. Most of these values may be calculated using the formulas of Lemma 3.2; the only exception is the case $G/H \cong S_3$, which may be directly computed using the Möbius function of the subgroup lattice of $S_3$ (see Fig. 1). The result follows by inspection of Table 1. $\square$

Fig. 1

Subgroup lattice of $S_3$