Fact 2.3 [Reference Yu7, Lemma 2.2 and Sections 3.2 and 3.3]

If $L\subseteq \Lambda ^*$ then the following are equivalent:

• • L is regular.

• • L is recognized by some DFA.

• • L is recognized by some NFA.

Proof By F-automaticity there is $r_0>0$ and an $F^{r_0}$ -spanning set $\Sigma _0$ such that $\{\sigma \in \Sigma _0^* : [\sigma ]_{F^{r_0}}\in A\}$ is regular. Now $\Theta := [\Sigma ^{(r_0)}]_{F^r}$ is an $F^{rr_0}$ -spanning set, and by [Reference Bell and Moosa2, Proposition 6.3] we have that $\{\sigma \in \Theta ^* : [\sigma ]_{F^{rr_0}}\in A\}$ is regular. Suppose it is recognized by the automaton $M=(\Theta ,Q,q_0,\Omega ,\delta )$ . Now define a new automaton $M' = (\Sigma ,Q\times \Sigma ^{(<r_0)},(q_0,\epsilon ),\Omega ',\delta ')$ by

$$ \begin{align*} \delta '((q,\sigma ), a) &= \begin{cases} (\delta (q,[\sigma a]_{F^r}),\epsilon ) &{\text{if }} {\lvert{\sigma } \rvert} = r_0-1, \\ (q,\sigma a) &{\text{if }} {\lvert{\sigma}\rvert}<r_0-1, \end{cases} \\ \Omega ' &= \{(q,\sigma ) : \delta (q,[\sigma ]_{F^r}) \in \Omega\}. \end{align*} $$

(Note if ${\lvert \sigma \rvert } <r_0$ that $[\sigma ]_{F^r} = [\sigma 0^{r_0-{\lvert \sigma \rvert }}]_{F^r} \in \Theta $ , so $\delta (q,[\sigma ]_{F^r})$ is defined.) Given $\sigma \in \Sigma ^*$ we can write $\sigma =\sigma _1\cdots \sigma _{n+1}$ where ${\lvert {\sigma _1} \rvert }=\cdots ={\lvert {\sigma _n}\rvert } = r_0$ and ${\lvert {\sigma _{n+1}} \rvert }< r_0$ . Now, $M'$ accepts $\sigma $ if and only if M accepts $[\sigma _1]_{F^r}\cdots [\sigma _{n+1}]_{F^r}$ (where again $[\sigma _{n+1}]_{F^r} = [\sigma _{n+1}0^{r_0-{\lvert {\sigma _{n+1}} \rvert }}]_{F^r}\in \Theta $ ), which is in turn equivalent to $[\sigma ]_{F^r} = [[\sigma _1]_{F^r}\cdots [\sigma _{n+1}]_{F^r}]_{F^{rr_0}}\in A$ . So $M'$ recognizes $\{\sigma \in \Sigma ^*:[\sigma ]_{F^r}\in A\}$ , as desired.

Proof Suppose the F-orbit of $a\in A$ is infinite; so there is $i_a$ such that $F^{i_a}a\notin A$ . Now, for all $n\ge i_a$ we have

$$ \begin{align*}\lambda (F^na) &= \lambda (F^{n-i_a}F^{i_a}a) \ge \lambda (F^{i_a}a) + (n-i_a)C - E\\ &= \lambda (a) + nC - (\underbrace{E+ i_aC + \lambda (a)-\lambda (F^{i_a}a)}_*), \end{align*} $$

and for $n< i_a$ we have

$$ \begin{align*}\lambda (F^na) = \lambda (a) + nC - (\underbrace{nC + \lambda (a) - \lambda (F^na)}_*). \end{align*} $$

Hence taking $E'$ to be the maximum of E and all the quantities marked $*$ , we get that $\lambda (F^na)\ge \lambda (a)+ nC-E'$ so that a is no longer exceptional with respect to this new $E'$ . Iterating this procedure for each $a\in A$ with infinite F-orbit, we eventually produce a new $\widetilde {E}\ge E$ such that only the elements of A of finite F-orbit remain exceptional.

Proof We verify the axioms. Symmetry of $\lambda _{\Sigma } $ is simply by symmetry of $\Sigma $ . Lemma 5.3 of [Reference Bell and Moosa2] implies that the ultrametric inequality holds of $\lambda _{\Sigma } $ with $D=1$ . Since $\Sigma $ is finite there are finitely many $\sigma \in \Sigma ^*$ of length $\le N$ , and hence $\lambda _{\Sigma } $ satisfies the Northcott property. Finally, we prove that $\lambda _{\Sigma } $ satisfies the logarithmic property with $C=E=1$ and exceptional set $\Sigma $ . For the upper bound, note that if $a = [s_0\cdots s_{\ell } ]_F$ with $s_0,\ldots ,s_{\ell } \in \Sigma $ then $Fa = [0s_0\cdots s_{\ell } ]_F$ ; so $\lambda _{\Sigma } (Fa)\le \lambda _{\Sigma } (a)+1$ . It remains to show the lower bound.

Suppose $a\notin \Sigma $ . Write $\lambda _{\Sigma } (a) = \ell $ for some $\ell>1$ ; say $a = [s_0\cdots s_{\ell -1}]_F$ . Suppose for contradiction that $\lambda _{\Sigma } (F^ma) < m+\ell -1 $ ; so we can write $F^ma = [t_0\cdots t_{m+\ell -3}]_F$ . Then

(1) $$ \begin{align} F^ms_0+\cdots + F^{m+\ell -1}s_{\ell -1} = F^ma = t_0 + \cdots + F^{m+\ell -3}t_{m+\ell -3}. \end{align} $$

Then $t_0\in F\Gamma $ , so by axiom (iv) we get that $t_0 = Ft_0^{\prime }$ for some $t_0^{\prime }\in \Sigma $ . Inductively suppose for some $i<m-1$ we can write $t_0 + \cdots + F^it_i = F^{i+1}t_i^{\prime }$ for some $t_i^{\prime }\in \Sigma $ . Then $F^{i+1}(t_i^{\prime }+t_{i+1}) = t_0 + \cdots + F^{i+1}t_{i+1}$ which can be seen to be in $ F^{i+2}\Gamma $ using Equation (1) and the fact that $m\ge i+2$ . Hence $t_i^{\prime }+t_{i+1}\in F\Gamma $ by injectivity of F, and again by axiom (iv) we can write $t_i^{\prime }+t_{i+1} = Ft_{i+1}^{\prime }$ for some $t_{i+1}\in \Sigma $ . So $t_0 + \cdots + F^{i+1}t_{i+1} = F^{i+2}t_{i+1}^{\prime }$ . It follows that $t_0+\cdots +F^{m-1}t_{m-1} = F^mt_{m-1}^{\prime }$ for some $t_{m-1}^{\prime }\in \Sigma $ . (Note $t_{m-1}$ is defined since $\ell \ge 2$ .) So $F^ma = F^mt_{m-1}^{\prime } + F^mt_m + \cdots + F^{m+\ell -3}t_{m+\ell -3}$ , and thus

$$ \begin{align*}a = t_{m-1}^{\prime} + (t_m + \cdots + F^{\ell -3}t_{m+\ell -3}). \end{align*} $$

Hence by [Reference Bell and Moosa2, Lemma 5.3] we get that a can be represented by a string of length $\le \ell -1$ , contradicting our assumption that $\lambda _{\Sigma } (a) = \ell $ .

Proof Given $a\in \Gamma $ we can find $s_0\in S$ such that $a\equiv s_0{\pmod {F\Gamma }}$ . Then inductively we can find $s_1,\ldots ,s_{r-1}\in S$ such that $F^{-1}(a-s_0)\equiv s_1+\cdots +F^{r-2}s_{r-1}{\pmod {F^{r-1}\Gamma }}$ , at which point it follows that $a\equiv s_0+\cdots + F^{r-1}s_{r-1}{\pmod {F^r\Gamma }}$ .

Proof (1) $\implies $ (2) is Proposition 3.8, and we noted (2) $\implies $ (3) after the definition of length functions. For (3) $\implies $ (1), we appeal to [Reference Bell and Moosa2, Proposition 5.8]. Formally they require that $\Gamma $ be finitely generated as a group, but this is only used to deduce that $\Gamma /F^r\Gamma $ is finite for all r; by Lemma 3.9 we can assume as much from the fact that $\Gamma /F\Gamma $ is finite.

Proof By Theorem 3.10 there is a length function $\lambda $ for some $(\Gamma ,F^r)$ . One can check that $\lambda \restriction H$ is a length function for $(H,(F\restriction H)^r)$ . So again by Theorem 3.10 there is an $F^s$ -spanning set for H for some $s>0$ .

For the “furthermore,” note by the above and [Reference Bell and Moosa2, Lemmas 5.6 and 5.7] there is s such that there is an $F^s$ -spanning set $\Sigma $ for $H $ that is contained in an $F^s$ -spanning set $\Sigma '$ for $\Gamma $ . The right-to-left direction then follows from [Reference Bell and Moosa2, Proposition 6.8(b)]. For the left-to-right, note that $\{\sigma \in \Sigma ^* : [\sigma ]_{F^s}\in A\} = \{\sigma \in (\Sigma ')^* : [\sigma ]_{F^s}\in A\}\cap \Sigma ^*$ is the intersection of two regular languages, and is thus regular (see [Reference Yu7, Theorem 2.1]); so A is F-automatic in H.

Proof Note first that since F is injective and H is finite we get that $FH = H$ ; so there is indeed a well-defined and injective $F_0\colon \Gamma _0\to \Gamma _0$ that satisfies $\pi \circ F=F_0\circ \pi $ .

1. 1. Note that $\pi ([s_0\cdots s_n]_F) {{\kern-1.5pt}={\kern-1.5pt}} \pi (s_0) + \pi (Fs_1) + \cdots + \pi (F^ns_n) {{\kern-1.5pt}={\kern-1.5pt}} \pi (s_0) + F_0(\pi (s_1)) + \cdots + F_0^n(\pi (s_n)) {{\kern-1.5pt}={\kern-1.5pt}} [(\pi (s_0))\cdots (\pi (s_n))]_{F_0}$ .

2. 2. Suppose $\Sigma $ is an F-spanning set for $\Gamma $ ; we verify that $\pi (\Sigma )$ satisfies the axioms.

   1. (i) Suppose $a\in \Gamma _0$ . Since $\Sigma $ satisfies axiom (i) there is $s_0\cdots s_n \in \Sigma ^*$ such that $[s_0\cdots s_n]_F = a$ . Then by part (1) we get that $a = \pi (a) = [(\pi (s_0))\cdots (\pi (s_n))]_{F_0}$ .

   2. (ii) Since $0\in \Sigma $ we get that $0=\pi (0)\in \pi (\Sigma )$ . If $\pi (a)\in \pi (\Sigma )$ then since $\Sigma $ satisfies axiom (ii) we get that $-a\in \Sigma $ , and hence $-\pi (a)\in \pi (\Sigma )$ .

   3. (iii) Suppose $\pi (a_1),\ldots ,\pi (a_5)\in \pi (\Sigma )$ . Since $\Sigma $ satisfies axiom (iii) there are $b_0,b_1\in \Sigma $ such that $a_1+\cdots +a_5 = b_0 + Fb_1$ . Then $\pi (a_1)+\cdots +\pi (a_5) = \pi (b_0) + \pi (Fb_1) = \pi (b_0) + F_0(\pi (b_1))\in \pi (\Sigma ) + F_0(\pi (\Sigma ))$ , as desired.

   4. (iv) Suppose $\pi (a_1),\pi (a_2),\pi (a_3)\in \pi (\Sigma )$ and $\pi (a_1)+ \pi (a_2) + \pi (a_3) = F_0b$ for some $b\in \Gamma _0$ . Then $\pi (a_1+a_2+a_3) = F_0(\pi (b)) = \pi (Fb)$ , so there is $h\in H$ such that $a_1+a_2+a_3 = Fb + h$ . Since F is bijective on H, there is $h_0\in H$ such that $Fh_0 = h$ . So $a_1+a_2+a_3 = F(b+h_0)$ ; thus since $\Sigma $ satisfies axiom (iv) we get that $b+h_0\in \Sigma $ , and hence that $b=\pi (b+h_0) \in \pi (\Sigma )$ .

3. 3. Suppose $\Sigma _0 $ is an $F_0$ -spanning set for $\Gamma _0 $ ; we verify that $\pi ^{-1}(\Sigma _0 )$ satisfies the axioms.

   1. (i) Suppose $a\in \Gamma $ . Since $\Sigma _0 $ satisfies axiom (i) there is $s_0\cdots s_n\in \Sigma _0^*$ such that $\pi (a) = [s_0\cdots s_n]_{F_0} = [(\pi (s_0))\cdots (\pi (s_n))]_{F_0} = \pi ([s_0\cdots s_n]_F)$ (since each $s_i\in \Sigma _0\subseteq \Gamma _0$ ). Let $h=a-[s_0\cdots s_n]_F\in H$ . Then $a = h + [s_0\cdots s_n]_F = [(s_0+h)s_1\cdots s_n]_F$ and $s_0+h,s_1,\ldots ,s_n\in \pi ^{-1}(\Sigma _0)$ , as desired.

   2. (ii) Since $0\in \Sigma _0$ we get that $0 \in \pi ^{-1}(0)\subseteq \pi ^{-1}(\Sigma _0)$ . If $a+h\in \pi ^{-1}(\Sigma _0)$ with $a\in \Sigma _0$ and $h\in H$ , then since $\Sigma _0$ satisfies axiom (ii) we get that $-a\in \Sigma _0$ , and hence $-(a+h)\in \pi ^{-1}(\Sigma _0)$ .

   3. (iii) Suppose $a_1+h_1,\ldots ,a_5+h_5\in \pi ^{-1}(\Sigma _0)$ with each $a_i\in \Sigma _0$ and each $h_i\in H$ . Since $\Sigma _0$ satisfies axiom (iii) there are $b_0,b_1\in \Sigma _0$ such that

      $$ \begin{align*}a_1+\cdots +a_5 {{\kern-1pt}={\kern-1pt}} b_0 + F_0b_1 {{\kern-1pt}={\kern-1pt}} b_0 + F_0(\pi (b_1)) {{\kern-1pt}={\kern-1pt}} b_0 + \pi (Fb_1) {{\kern-1pt}={\kern-1pt}} b_0 + Fb_1 + h, \end{align*} $$
      for some $h\in H$ . Then
      $$ \begin{align*}(a_1+h_1)+\cdots +(a_5+h_5) = (b_0+ h_1+h_2+\cdots +h_5+h) + Fb_1 \end{align*} $$
      and $b_0+h_1+h_2+\cdots +h_5+h, b_1\in \pi ^{-1}(\Sigma _0)$ .

   4. (iv) Suppose $a_1+h_1,a_2+h_2,a_3+h_3\in \pi ^{-1}(\Sigma _0)$ with each $a_i\in \Sigma _0$ and each $h_i\in H$ ; suppose further that $(a_1+h_1) + (a_2+h_2) + (a_3+h_3) = Fb$ for some $b\in \Gamma $ . Then $a_1+a_2+a_3 = \pi (Fb) = F_0(\pi (b))$ ; thus since $\Sigma _0$ satisfies axiom (iv) we get that $\pi (b)\in \Sigma _0$ , and $b\in \pi ^{-1}(\Sigma _0)$ .

Proof of Theorem 3.12 We first reduce to the torsion-free case. By the fundamental theorem of finitely generated abelian groups we may assume $\Gamma =\mathbb {Z}^m \times H$ where H is a finite group; let $\pi \colon \Gamma \to \mathbb {Z}^m$ be the projection. Let $F_0$ be the endomorphism of $\mathbb {Z}^m$ induced by F; note then that $F_0^r$ is the endomorphism of $\mathbb {Z}^m$ induced by $F^r$ . So by Lemma 3.13 $\Gamma $ admits an $F^r$ -spanning set for some $r>0$ if and only if $\mathbb {Z}^m$ admits an $F_0^r$ -spanning set for some $r>0$ . Moreover under the identification $\Gamma \otimes _{\mathbb {Z}}\mathbb {C}=\mathbb {Z}^m\otimes _{\mathbb {Z}}\mathbb {C}$ we have that $F\otimes _{\mathbb {Z}}\operatorname {\mathrm {id}}_{\mathbb {C}} \sim F_0\otimes _{\mathbb {Z}}\operatorname {\mathrm {id}}_{\mathbb {C}}$ , and in particular they have the same eigenvalues.

We may therefore assume $\Gamma =\mathbb {Z}^m$ for some m and $F\in M_m(\mathbb {Z})$ .

• $(\impliedby )$ By replacing F with a power, we may assume ${\lvert \mu \rvert }>2$ for all $\mu \in \sigma (F)$ . We show there exists a height function for $(\Gamma ,F)$ . Pick a basis $\{e_1,\ldots ,e_m \}$ for $\mathbb {C}^m$ that puts F in Jordan canonical form. Let $h\colon \mathbb {C}^m\to \mathbb {R}_{\ge 0}$ be the infinity norm associated with $\{e_1,\ldots ,e_m\}$ : so $h(a_1e_1+\cdots +a_me_m) = \max _i {\lvert {a_i}\rvert }$ . We show that $h\restriction \mathbb {Z}^m$ is a height function for $(\Gamma ,F)$ . Triangle inequality and symmetry are clear. For the Northcott property, recall that two norms $\lVert {\cdot }\rVert _1$ and $\lVert {\cdot }\rVert _2$ on a vector space V are equivalent if there are $c_1,c_2>0$ such that $c_1\lVert {v}\rVert _1\le \lVert {v}\rVert _2 \le c_2\lVert {v}\rVert _1$ for all $v\in V$ ; recall further that all norms on a finite-dimensional space are equivalent. In particular, our infinity norm is equivalent to the usual infinity norm $\lVert {\cdot }\rVert _{\infty } $ on $\mathbb {C}^m$ , and there is $c>0$ such that $\lVert {v}\rVert _{\infty } \le ch(v)$ for all $v\in \mathbb {C}^m$ . So if $h(v)\le N$ then $\lVert {v}\rVert _{\infty } \le cN$ , and there can only be finitely many such $v\in \mathbb {Z}^m$ .

  It remains to check canonicity. Fix some $\beta>1$ such that $\beta +1<{\lvert \mu \rvert }$ for all $\mu \in \sigma (F)$ . Suppose $v = v_1e_1+\cdots +v_me_m\in \mathbb {C}^m\setminus \{0\}$ ; write $Fv = w_1e_1+\cdots +w_me_m$ . Fix i such that ${\lvert {v_i}\rvert } = h(v)$ . Depending on the structure of the Jordan blocks, we get that $w_i$ is either $\mu v_i + v_{i+1}$ or $\mu v_i$ (for $\mu \in \sigma (F)$ corresponding to $v_i$ ). In the first case, reverse triangle inequality yields

  $$ \begin{align*}h(Fv)\ge {\lvert{w_i} \rvert}\ge {\lvert {\mu }\rvert}{\lvert{v_i}\rvert} - {\lvert{v_{i+1}\rvert}} \ge ({\lvert\mu -1 \rvert}){\lvert{v_i} \rvert}> \beta {\lvert {v_i}\rvert} = \beta h(v), \end{align*} $$
  and in the second case we get
  $$ \begin{align*}h(Fv)\ge {\lvert{w_i} \rvert} = {\lvert\mu \rvert}{\lvert{v_i} \rvert}> \beta {\lvert{v_i} \rvert} = \beta h(v). \end{align*} $$
  So h satisfies canonicity, as desired.

• $(\implies )$ Suppose there is $\mu \in \sigma (F)$ with ${\lvert \mu \rvert } \le 1$ . There are two cases:

  • Case 1. Suppose there is $\mu \in \sigma (F)$ with ${\lvert \mu \rvert } <1$ ; the argument in this case is similar to Example 3.1. Since the same is true for all powers of F it suffices to show that there is no F-spanning set. Pick a basis $\{e_1,\ldots ,e_m\}$ for $\mathbb {C}^m$ that puts F into Jordan canonical form; for $x\in \mathbb {C}^m$ we write

    $$ \begin{align*}x = \sum_{i=1}^m f_i(x)e_i; \end{align*} $$
    so each $f_i\colon \mathbb {C}^m\to \mathbb {C}$ is linear. Pick some $e_k$ corresponding to the bottom-right of some Jordan block for $\mu $ ; so $f_k(Fx) = \mu f_k(x)$ for $x\in \mathbb {C}^m$ .

    Suppose for contradiction we had an F-spanning set $\Sigma $ . Let $M = \max \{{\lvert {f_k(a)} \rvert }:a\in \Sigma \}$ . Then if

    $$ \begin{align*}y = \sum_{i=0}^{\ell} F^ia_i \end{align*} $$
    for $a_i\in \Sigma $ then
    $$ \begin{align*}{\lvert{f_k(y)} \rvert} &= {\bigg\lvert {\sum_{i=0}^{\ell} \mu ^if_k(a_i)}\bigg\rvert} \le \sum_{i=0}^{\ell} {\lvert{\mu ^if_k(a_i)} \rvert} \\ &= \sum_{i=0}^{\ell} {\lvert \mu \rvert}^i{\lvert{f_k(a_i)} \rvert} \le M\sum_{i<\omega }{\lvert \mu \rvert}^i = M\frac1{1-{\lvert\mu \rvert} }. \end{align*} $$
    So every $y{{\kern-1.2pt}\in{\kern-1.2pt}} \mathbb {Z}^m$ satisfies ${\lvert {f_k(y)}\rvert }{{\kern-1.2pt}\le{\kern-1.2pt}} M\frac 1{1-{\lvert \mu \rvert } }$ . So since the integers are closed under doubling and $f_k$ is linear, we get that $f_k(y) = 0$ for each $y\in \mathbb {Z}^m$ . So $\mathbb {C}^m = \operatorname {\mathrm {span}}_{\mathbb {C}}\mathbb {Z}^m$ is spanned by $\{e_1,\ldots ,e_m\}\setminus \{e_k\}$ , a contradiction.

  • Case 2. Suppose ${\lvert \mu \rvert } \ge 1$ for all $\mu \in \sigma (F)$ ; pick some $\mu \in \sigma (F)$ with ${\lvert \mu \rvert } =1$ . We show that there is non-zero $a\in \mathbb {Z}^m$ such that $F^ia=F^ja$ for some $i\ne j$ , and deduce that no power of F admits a length function.

    Let $p_{\mu } (x)$ be the minimal polynomial for $\mu $ over $\mathbb {Q}$ . Note that if $\nu \in \mathbb {C}$ is a root of $p_{\mu } $ then so is $\nu ^{-1}$ . Indeed, this is true of $\mu $ since $\mu ^{-1}=\overline {\mu }$ and $p_{\mu } \in \mathbb {Q}[x]$ , and hence is true of all $\operatorname {\mathrm {Aut}}(\overline {\mathbb {Q}}/\mathbb {Q})$ -conjugates of $\mu $ . But $p_{\mu } $ divides the characteristic polynomial of F, and hence $p_{\mu } $ has no roots of modulus $<1$ by hypothesis. It follows that $p_{\mu } $ has no roots of modulus $>1$ either. That is, the roots of $p_{\mu } $ lie on the unit circle.

    Now, $p_{\mu } (F)$ isn’t invertible over $\mathbb {C}$ , since $p_{\mu } (F)v= p_{\mu } (\mu )v = 0$ for any eigenvector v of F with eigenvalue $\mu $ . So $p_{\mu } (F)$ isn’t invertible over $\mathbb {Q}$ , and thus $V:=\ker _{\mathbb {Q}}(p_{\mu } (F))$ is a non-trivial F-invariant subspace of $\mathbb {Q}^m$ . Furthermore $p_{\mu } (F\restriction V) = 0$ , so the minimal polynomial of $F\restriction V$ is separable (since $p_{\mu } $ is); so $F\restriction V$ is diagonalizable (over $\mathbb {C}$ ) with eigenvalues that are roots of $p_{\mu } $ , and hence lie on the unit circle. In particular in the inner product induced by the eigenbasis for $F\restriction V$ we get that $F\restriction V$ is unitary.

    Since V is a non-trivial subspace of $\mathbb {Q}^m$ it contains a non-zero $a\in \mathbb {Z}^m$ . So $Fa\in V\cap \mathbb {Z}^m$ as well and $\lVert {Fa}\rVert = \lVert {a}\rVert $ (where the norm is induced by the aforementioned inner product); inductively we get $\lVert {F^na}\rVert = \lVert {a} \rVert $ and $F^na\in \mathbb {Z}^m$ for all n. But $\lVert {\cdot }\rVert $ is equivalent to the Euclidean norm (since both are norms on a finite-dimensional space); so there are finitely many $b\in \mathbb {Z}^m$ with $\lVert {b}\rVert = \lVert {a}\rVert $ . So $F^i a = F^ja$ for some $i\ne j$ . By injectivity of F we get $F^{i-j}a = a$ , and hence that $(F^n)^{i-j} a = a$ for all n. It follows that the $F^n$ -orbit of a is finite for all $n>0$ . Since a has infinite order, Remark 3.6 yields that no power of F admits a length function. Hence by Theorem 3.10 $\Gamma $ does not admit an $F^r$ -spanning set for any $r>0$ .

Proof The $(S^{(n)},F^n)$ -kernel is clearly contained in the $(S,F)$ -kernel. Suppose the $(S,F)$ -kernel is infinite.

Note that if $\sigma =s_0\cdots s_{k-1},\tau =t_0\cdots t_{\ell -1}\in S^*$ , and $a\in \Gamma $ then

$$ \begin{align*} a\in (A_{\sigma} )_{\tau} &\iff t_0+\cdots +F^{\ell -1}t_{\ell -1}+F^{\ell} a\in A_{\sigma} \\ &\iff s_0 + \cdots + F^{k-1}s_{k-1} + F^k(t_0+\cdots +F^{\ell -1}t_{\ell -1}+F^{\ell} a) \in A \\ &\iff s_0 + \cdots + F^{k-1}s_{k-1} + F^kt_0 + \cdots + F^{k+\ell -1}t_{\ell -1} + F^{k+\ell }a \in A \\ &\iff a\in A_{\sigma \tau}. \end{align*} $$

So $(A_{\sigma } )_{\tau } = A_{\sigma \tau }$ ; in particular, if $A _{\sigma \tau }\ne A _{\sigma '\tau }$ then $A _{\sigma } \ne A _{\sigma '}$ .

Since the set of all $A_{\sigma } $ is infinite, there is $0\le i<n$ such that the set of $A_{\sigma } $ with ${\lvert \sigma \rvert } \equiv i{\pmod {n}}$ is infinite. Now, as S is finite, this means there is $\tau \in S^*$ of length i such that $\{A _{\rho \tau } : \rho \in S^*,{\lvert \rho \rvert } \in n\mathbb {Z}\} $ is infinite. It follows by the above observation that $\{A _{\rho } :\rho \in S^*,{\lvert \rho \rvert } \in n\mathbb {Z}\}$ is infinite, and so the $(S^{(n)}, F^n)$ -kernel is infinite.

Proof Let $N = \max \{\lambda (s-t) : s\in S,t\in T\}$ . Suppose the $(T,F)$ -kernel of A is finite.

Take an element $A _{\sigma } $ of the $(S,F)$ -kernel of $A $ , say with $\sigma = s_0\cdots s_{n-1}\in S^*$ . By Lemma 3.9 there is $\tau = t_0\ldots t_{n-1}\in T^*$ such that

$$ \begin{align*}s_0 + \cdots + F^{n-1}s_{n-1}\equiv t_0+\cdots +F^{n-1}t_{n-1}{\pmod{F^n(\Gamma )}}. \end{align*} $$

So $A_{\tau } $ lies in the $(T,F)$ -kernel of $A $ . Let

$$ \begin{align*}\delta = F^{-n}((s_0-t_0) + \cdots + F^{n-1}(s_{n-1}-t_{n-1})); \end{align*} $$

so for $a\in \Gamma $ we have

$$ \begin{align*} a+\delta \in A_{\tau} &\iff t_0 + \cdots +F^{n-1}t_{n-1} + F^n (a+\delta )\in A\\ &\iff t_0 + \cdots +F^{n-1}t_{n-1} + F^n a + (s_0-t_0)+\cdots +F^{n-1}(s_{n-1}-t_{n-1}) \in A\\ &\iff s_0 + \cdots F^{n-1}s_{n-1} + F^na \in A\\ &\iff a\in A_{\sigma}. \end{align*} $$

So $A_{\sigma } = A_{\tau } -\delta $ . Hence to show that the $(S,F)$ -kernel of A is finite it suffices to show that $\delta $ can take on one of only finitely many values (as $\sigma ,\tau $ vary). We show that $\lambda (\delta )$ is bounded in terms of $S,T$ , which suffices by the Northcott property.

We first bound $\lambda (F^n\delta ) = \lambda ((s_0-t_0) + \cdots + F^{n-1}(s_{n-1}-t_{n-1})) $ . Since $\lambda (s_0-t_0)\le N$ and $\lambda (F(s_1-t_1))\le N+C$ , the ultrametric inequality yields

$$ \begin{align*}\lambda ((s_0-t_0) + F(s_1-t_1))\le N+C+D. \end{align*} $$

Since $\lambda (F^2(s_2-t_2))\le N+2C$ , another application of ultrametric inequality yields

$$ \begin{align*}\lambda ((s_0-t_0) + F(s_1-t_1) + F^2(s_2-t_2))\le N+2C+D \end{align*} $$

(since by hypothesis $C\ge D$ ). Continuing inductively, we find that $\lambda (F^n\delta )\le N+(n-1)C+D$ . Hence by the logarithmic property we get that $\lambda (\delta )\le N-C+D+E$ .

Proof of Theorem 4.2 Suppose $\Gamma $ admits an $F^n$ -spanning set $\Sigma $ for some $n>0$ . By Proposition 3.8 $\lambda _{\Sigma } $ is a length function for $(\Gamma ,F^n)$ with associated constants $C,D,E$ such that $C\ge D$ . Suppose $A\subseteq \Gamma $ . Then by the previous two lemmas, the $(S,F)$ -kernel of A is finite if and only if the $(S^{(n)},F^n)$ -kernel of A is, which occurs if and only if the $(\Sigma ,F^n)$ -kernel of A is. (Note that an $F^n$ -spanning set must contain a representative of every coset of $F\Gamma $ .) But by [Reference Bell and Moosa2, Lemma 6.2] this is equivalent to A being F-automatic, as desired.

Proof By Proposition 2.6 this is equivalent to $\Delta = \{(a,a) : a\in \Gamma \}\subseteq \Gamma ^2$ being F-automatic. Fix a set S containing exactly one representative of each coset of $F\Gamma $ in $\Gamma $ ; we will show that the $(S^2,F)$ -kernel of $\Delta $ is finite. Note that if $s_0\cdots s_{n-1},t_0\cdots t_{n-1}\in S^{(n)}$ are unequal, say with i minimal such that $s_i\ne t_i$ , then since $s_{i} \not \equiv t_{i}{\pmod {F\Gamma }}$ and F is injective we get that $s_0+\cdots +F^{n-1}s_{n-1}{\not \equiv } t_0+\cdots + F^{n-1}t_{n-1}{\pmod {F^{i+1}\Gamma }}$ . So $s_0+\cdots +F^{n-1}s_{n-1}{\not \equiv } t_0+\cdots +F^{n-1}t_{n-1}{\pmod {F^n\Gamma }}$ , and thus $s_0 + \cdots + F^{n-1}s_{n-1} + F^na \ne t_0 + \cdots + F^{n-1}t_{n-1} + F^nb$ for any $a,b\in \Gamma $ . So $\Delta _{(\sigma ,\tau ) }$ is empty if $(\sigma , \tau ) \in (S^2)^*$ and $\sigma \ne \tau $ . Furthermore if $\sigma =\tau $ then by injectivity of F we get $\Delta _{(\sigma ,\tau )} = \Delta $ . So the $(S^2,F)$ -kernel of $\Delta $ contains two elements.

Fact 5.2 [Reference Bell and Moosa2, Proposition 7.1]

$L\subseteq \Sigma ^*$ is sparse if and only if it is a finite union of sets of the form $v_0w_1^*v_1\cdots v_{n-1}w_n^*v_n$ where $v_0,\ldots ,v_n,w_1,\ldots ,w_n\in \Sigma ^*$ .

Proof By Fact 5.2 we can write A as a finite union of sets of the form $[v_0w_1^*v_1\cdots w_n^*v_n]_{F^r}$ for some strings $v_i,w_i\in \Gamma ^*$ . By replacing F with $F^r$ we may assume $r=1$ . Let $s_0$ be the least common multiple of all the ${\lvert {w_i}\rvert }$ .

In the case where $\Gamma =\mathbb {Z}^m$ and F is multiplication by some $d>0$ , an intermediate result in the proof of [Reference Hawthorne5, Lemma 3.4] is that we can write A as a finite union of translates of sets of the form $[\tau _1^*\cdots \tau _n^*]_F$ where $\tau _1,\ldots ,\tau _n\in \Gamma ^*$ all have length $s_0$ . In fact with little additional effort the proof of this generalizes to our setting, and can be made to show that if $s\in s_0\mathbb {N}$ then we may take all $\tau _i$ to have length s rather than $s_0$ . But if we let $a_i = [\tau _i]_F$ then $[\tau _1^*\cdots \tau _n^*]_F = [a_1^*\cdots a_n^*]_{F^s}$ ; so we have written A in the desired form.

Proof

1. 1. The right-to-left is by definition; for the left-to-right, take an $F^r$ -spanning set $\Sigma $ for some $r{{\kern-1pt}>{\kern-1pt}}0$ and a sparse language $L{{\kern-1pt}\subseteq{\kern-1pt}} \Sigma ^*$ such that $A = [L]_{F^r}$ . Recall by [Reference Bell and Moosa2, Lemma 5.7] that $\Sigma ' = [\Sigma ^{(s)}]_{F^r}$ is an $F^{rs}$ -spanning set. Given $\sigma \in \Sigma ^*$ with $s\mid {\lvert \sigma \rvert } $ we can associate $\sigma '\in (\Sigma ')^*$ as follows: write $\sigma = \sigma _1\cdots \sigma _{\frac {{\lvert \sigma \rvert } }s}$ with each $\sigma _i\in \Sigma ^{(s)}$ , and set $\sigma ' = [\sigma _1]_{F^r}\cdots [\sigma _{\frac {{\lvert \sigma \rvert } }s}]_{F^r}$ . So $[\sigma ]_{F^r} = [\sigma ']_{F^{rs}}$ , and ${\lvert {\sigma '} \rvert } = \frac {{\lvert \sigma \rvert } }s$ .

   Note now that

   $$ \begin{align*}A = [L]_{F^r} = [L0^*\cap (\Sigma ^{(s)})^*]_{F^r} = [\underbrace{\{\sigma ' : \sigma \in L0^*\cap \Sigma ^{(s\mathbb{N})}\}}_{L'}]_{F^{rs}}. \end{align*} $$
   Since regular languages are closed under intersection (see [Reference Yu7, Theorem 2.1]), we get that $L0^*\cap (\Sigma ^s)^*$ is regular; one can then use a DFA that recognizes $L0^*\cap (\Sigma ^s)^*$ to construct an NFA that recognizes $L'$ . By Fact 5.2 $L0^*$ , and hence $L0^*\cap (\Sigma ^s)^*$ , is a sparse language; thus since ${\lvert {\sigma '} \rvert }= \frac {{\lvert \sigma \rvert } }s$ we get that $L'$ is sparse. So $A = [L']_{F^{rs}}$ is $F^s$ -sparse.

2. 2. Take an $F^r$ -spanning set $\Sigma $ and an $F^s$ -spanning set $\Theta $ with sparse languages $L_1\subseteq \Sigma ^*$ and $L_2\subseteq \Theta ^*$ such that $A = [L_1]_{F^r}$ and $B = [L_2]_{F^s}$ . By the argument given in the proof of (1), we may assume $r=s$ . By [Reference Bell and Moosa2, Lemma 5.6], there is an $F^r$ -spanning set $\Omega $ containing $\Sigma \cup \Theta $ . Then $L_1\cup L_2$ is a sparse language in $\Omega ^*$ , and $A\cup B = [L_1\cup L_2]_{F^r}$ . So $A\cup B$ is F-sparse.

3. 3. Take an $F^r$ -spanning set $\Sigma $ for some $r>0$ and a sparse language $L\subseteq \Sigma ^*$ such that $A = [L]_{F^r}$ . By Proposition 2.6 $\{\sigma \in \Sigma ^*:[\sigma ]_{F^r}\in X\}$ is regular. So if $L' = \{\sigma \in L : [\sigma ]_{F^r}\in X\}$ then $L'$ is regular (as the intersection of two regular languages; see [Reference Yu7, Theorem 2.1]) and thus sparse (as it’s contained in L). But $[L']_{F^r} = A\cap X$ ; so $A\cap X$ is F-sparse.

4. 4. We first check the case where $B = \{\gamma \}$ is a singleton. Take an $F^r$ -spanning set $\Sigma $ for some $r>0$ and a sparse language $L\subseteq \Sigma ^*$ such that $A = [L]_{F^r}$ . By [Reference Bell and Moosa2, Lemma 5.6] there is an $F^r$ -spanning set $\Sigma '\supseteq \Sigma $ that contains $a+\gamma $ for every $a\in \Sigma $ . Given $\sigma = a_1\cdots a_{{\lvert \sigma \rvert } } \in \Sigma ^*$ non-empty let $\sigma _{\gamma } = (a_1+\gamma )a_2\cdots a_{{\lvert \sigma \rvert } }\in (\Sigma ')^*$ ; so $[\sigma _{\gamma } ]_{F^r} = [\sigma ]_{F^r}+\gamma $ . It is routine to check that sparsity of L implies sparsity of $L_{\gamma } := \{\sigma _{\gamma } : \sigma \in L\} \subseteq (\Sigma ')^*$ . So $A+\gamma = [L_{\gamma } ]_{F^r}$ is F-sparse.

   We now do the general case. By Proposition 5.3 there is s such that there is an $F^s$ -spanning set and such that both A and B can be written as a finite union of translates of sets of the form $[a_1^*\cdots a_n^*]_{F^s}$ . Distributing, it suffices to check the case $A = \gamma + [a_1^*\cdots a_n^*]_{F^s}$ and $B = \gamma '+[b_1^*\cdots b_{n'}^*]_{F^s}$ . By the first case, we may assume $\gamma =\gamma '=0$ . Given $\sigma \in a_1^*\cdots a_n^*$ and $\tau \in b_1^*\cdots b_{n'}^*$ we let $\sigma \oplus \tau \in \Gamma ^*$ denote the string obtained by characterwise addition; so $[\sigma \oplus \tau ]_{F^s} = [\sigma ]_{F^s}+[\tau ]_{F^s}$ . Then

   $$ \begin{align*}a_1^*\cdots a_n^*\oplus b_1^*\cdots b_{n'}^* &= (a_1+b_1)^*(a_2^*\cdots a_n^*\oplus b_1^*\cdots b_{n'}^*)\\ &\quad\cup (a_1+b_1)^* (a_1^*\cdots a_n^* \oplus b_2^*\cdots b_{n'}^*) \end{align*} $$
   and is thus sparse by an inductive argument on $(n,n')$ . So $A+B = [a_1^*\cdots a_n^*\oplus b_1^*\cdots b_{n'}^*]_{F^s}$ is F-sparse.

Proof Otherwise $\lambda (a)> \max (\lambda (b), \lambda (a+b))+D= \max (\lambda (-b),\lambda (a+b))+D\ge \lambda (a)$ .

Proof Pick $r\in \mathbb {N}$ such that $rC\ge D$ , and let $K = \max \{\lambda ([\sigma ]_F) : \sigma \in S ^{(r)}\}$ .

We show by induction on $k\ge 1$ that if $\sigma \in S ^{(kr)}$ then $\lambda ([\sigma ]_F)\le (k-1)rC + D + K$ . The base case is just the definition of K. For the induction step, write $\sigma = \sigma _1\sigma _2$ where ${\lvert {\sigma _2} \rvert } =r$ . Then by the induction hypothesis $\lambda ([\sigma _1]_F)\le (k-2)rC + D + K$ , and by the logarithmic property we get that $\lambda (F^{(k-1)r}[\sigma _2]_F) \le \lambda ([\sigma _2]_F)+ (k-1)rC \le {(k-1)rC + K}$ . So by the ultrametric inequality we get that

$$ \begin{align*}\lambda ([\sigma ]_F) &= \lambda ([\sigma _1]_F + F^{(k-1)r}[\sigma _2]_F) \le \max((k-2)rC+D+K,(k-1)rC+K)+D\\ &= (k-1)rC+D+K \end{align*} $$

(since $rC\ge D$ ).

Now, for any $\sigma \in S ^*$ we can pad by some string of zeroes $\tau $ of length $<r$ to get that ${\lvert {\sigma \tau } \rvert }\in r\mathbb {Z}$ , at which point we get $\lambda ([\sigma ]_F) = \lambda ([\sigma \tau ]_F) \le ({\lvert {\sigma \tau } \rvert }-r)C+ D+ K\le C{\lvert \sigma \rvert } + D+K$ .

Proof Be replacing F with $F^r$ we may assume $r=1$ . Let $K\subseteq (\Sigma ^2)^*$ be the set of $\begin {pmatrix}{\sigma }\\{\tau }\end {pmatrix}$ such that

• • $\sigma \in L$ ;

• • $[\sigma ]_F = [\tau ]_F$ ; and

• • $\tau \in L\ \mathrm{and}\ \tau \prec \sigma,\ \mathrm{or}\ \tau \in L00^*$ .

So if $\sigma \in L$ then ${\begin {pmatrix}{\sigma }\\{\tau }\end {pmatrix}} \in K$ if and only if $\tau $ (with possibly the trailing $0$ removed) witnesses that $\sigma \notin \widetilde {L}$ ; so $\widetilde {L} = L\setminus \pi (K)$ , where $\pi \colon (\Sigma ^2)^*\to \Sigma ^*$ is projection to the first coordinate. So since L is regular it suffices to show that $\pi (K)$ is regular (since by [Reference Yu7, Theorems 2.1 and 2.2] regular languages are closed under Boolean combinations).

Note that K is regular: this is because $L\times L$ , equality (see Corollary 4.5), ending in $0$ , and $\prec $ are regular, and so K is a Boolean combination of regular languages. Fix a DFA $(\Sigma ^2, Q, q_0,\Omega ,\delta )$ for K; we use this to construct an NFA $(\Sigma ,Q',q_0^{\prime },\Omega ',\delta ')$ recognizing $\pi (K)$ . We let $Q' = Q$ , $q_0^{\prime } = q_0$ , and $\Omega ' = \Omega $ . For the transition function we set

$$ \begin{align*} \delta' (q, a) =\bigg\{\delta \bigg( {q, \begin{pmatrix}{a}\\{b}\end{pmatrix}}\bigg) : b\in \Sigma\bigg\}. \end{align*} $$

Then $\sigma $ is accepted by our NFA if and only if there is $\tau \in \Sigma ^*$ with ${\lvert \tau \rvert } ={\lvert \sigma \rvert } $ such that $\delta \left ( {q_0,{\begin {pmatrix}{\sigma }\\{\tau }\end {pmatrix}} }\right )\in \Omega $ ; i.e., such that ${\begin {pmatrix}{\sigma }\\{\tau }\end {pmatrix}} \in K$ . So our NFA recognizes $\pi (K)$ , and $\pi (K)$ is regular. So $\widetilde {L}$ is regular.

For the “moreover” clause, suppose $[L]_F$ is $\lambda _{\Sigma } $ -sparse. Note that $[\cdot ]_F$ is a bijection $ \widetilde {L}\to [L]_F $ ; furthermore by definition of $\lambda _{\Sigma } $ we have that $\lambda _{\Sigma } ([\sigma ]_F)\le {\lvert \sigma \rvert } $ . It follows that $\widetilde {L}$ is sparse: since $[L]_F$ is $\lambda _{\Sigma } $ -sparse, we get that

$$ \begin{align*}{\lvert{\{\sigma \in \widetilde{L} : {\lvert \sigma\rvert} \le x\}}\rvert} \le {\lvert{\{a\in [L]_F: \lambda _{\Sigma} (a)\le x\}} \rvert} = f_{[L]_F,\lambda_{\Sigma} }(x)\in O(x^d), \end{align*} $$

for some d.

Proof By Proposition 5.4-(1) it suffices to check the case $r=1$ ; so assume $\lambda $ is a length function for $(\Gamma ,F)$ . Let $C,D,E$ be the constants associated with $\lambda $ .

• $(\implies )$ Suppose A is F-sparse; so there is some $F^s$ -spanning set $\Sigma $ and some sparse $L\subseteq \Sigma ^*$ such that $A = [L]_{F^s}$ . We get by [Reference Bell and Moosa2, Proposition 6.8(b)] that A is F-automatic; it remains to show that A is $\lambda $ -sparse. Since $\lambda $ is also a length function for $(\Gamma ,F^s)$ (see Remark 3.4), we can replace F with $F^s$ and thus assume that $s=1$ . By Fact 5.2 L is a finite union of simple sparse languages. One can verify that a finite union of $\lambda $ -sparse sets is $\lambda $ -sparse; it thus suffices to check the case where L is simple sparse, say $L = v_0w_1^*\cdots v_{n-1}w_n^*v_n$ with $u_i,v_i\in \Sigma ^*$ . We apply induction on n; the base case $n=0$ is trivial.

  For the induction step, we have two cases.

  • Case 1. Suppose $[w_n^*v_n]_F$ is finite. Then

    $$ \begin{align*}A = \bigcup _{a \in [w_n^*v_n]_F} [v_0w_1^*\cdots w_{n-1}^*v_{n-1}a ]_F, \end{align*} $$
    and by the induction hypothesis each $[v_0w_1^*\cdots w_{n-1}^*v_{n-1}a ]_F$ is $\lambda $ -sparse. So A is $\lambda $ -sparse.

  • Case 2. Suppose $[w_n^*v_n]_F$ is infinite.

    Claim 5.11. There is $M\in \mathbb {R}$ and $i\in \mathbb {N}$ such that if $k_n\ge i$ then $\lambda ([v_0w_1^{k_1}\cdots w_n^{k_n}v_n]_F)\ge C{\lvert {v_0w_1^{k_1}\cdots w_n^{k_n}v_n} \rvert }+M $ .

    Proof Our strategy will be to write

    $$ \begin{align*}\underbrace{[v_0w_1^{k_1}\cdots w_n^{k_n}v_n]_F}_a &= [v_0w_1^{k_1}\cdots w_{n-1}^{k_{n-1}}v_{n-1}w_n^{k_n-i}]_F\\[-3pt] &\quad+ \underbrace{F^{{\lvert {v_0w_1^{k_1}\cdots w_{n-1}^{k_{n-1}}v_{n-1}w_n^{k_n-i}}\rvert}}[w_n^iv_n]_F}_b \end{align*} $$

    and then use the reverse ultrametric inequality to show that $\lambda (a)$ is not much less than $\lambda (b)$ .

    Applying Lemma 5.8 with $S=\Sigma $ , we find that there is $M_0\ge 0$ such that $\lambda ([\sigma ]_F)\le C{\lvert \sigma \rvert } +M_0$ for all $\sigma \in \Sigma ^*$ . Then by Northcott property there is some i such that $\lambda ([w_n^iv_n]_F)> M_0+D+E$ . Suppose $k_1,\ldots ,k_n\in \mathbb {N}$ with $k_n\ge i$ ; to avoid notational clutter we abbreviate $\sigma = v_0w_1^{k_1}\cdots w_{n-1}^{k_{n-1}}v_{n-1}w_n^{k_n-i}$ . We then wish to show that $\lambda ([\sigma w_n^iv_n]_F)$ is not much less than $\lambda (F^{{\lvert \sigma \rvert } }[w_n^iv_n]_F)$ .

    Note that

    $$ \begin{align*}\lambda (F^{{\lvert \sigma\rvert} }[w_n^iv_n]_F) {{\kern-1pt}\ge{\kern-1pt}} \lambda ([w_n^iv_n]_F){{\kern-1pt}+{\kern-1pt}}{\lvert \sigma\rvert} C -E{{\kern-1pt}>{\kern-1pt}} C{\lvert \sigma\rvert} {{\kern-1pt}+{\kern-1pt}}D{{\kern-1pt}+{\kern-1pt}}M_0 {{\kern-1pt}\ge{\kern-1pt}} \lambda ([\sigma ]_F){{\kern-1pt}+{\kern-1pt}}D \end{align*} $$

    by hypothesis on $M_0$ . So by the reverse ultrametric inequality we get that

    $$ \begin{align*}\lambda ([\sigma w_n^iv_n]_F) &= \lambda ([\sigma ]_F + F^{{\lvert \sigma\rvert} }[w_n^iv_n]_F) \ge \lambda (F^{{\lvert \sigma\rvert} }[w_n^iv_n]_F)-D\\ &\ge \lambda ([w_n^iv_n]_F)+{\lvert \sigma\rvert} C - D - E. \end{align*} $$

    Let $M = \lambda ([w_n^iv_n]_F)- {\lvert {w_n^iv_n} \rvert }C -D -E$ . Then if $k_n\ge i$ then $\lambda ([v_0w_1^{k_1}\cdots w_n^{k_n}v_n]_F)\ge {\lvert {v_0w_1^{k_1}\cdots w_n^{k_n}v_n} \rvert } C +M$ , as desired.

    Now, we can write
    $$ \begin{align*}L {{\kern-1pt}={\kern-1pt}} \{v_0w_1^{k_1}\cdots w_n^{k_n}v_n : k_1,\ldots ,k_n\in\mathbb{N},\ k_n\ge i\}{{\kern-1pt}\cup{\kern-1pt}}\bigcup _{j<i} v_0w_1^*\cdots w_{n-1}^*v_{n-1}w_n^jv_n. \end{align*} $$
    By the induction hypothesis each $[v_0w_1^*\cdots w_{n-1}^*v_{n-1}w_n^jv_n]_F$ is $\lambda $ -sparse; it remains to check the case $k_n\ge i$ .

    If $\tau =v_0w_1^{k_1}\cdots w_n^{k_n}v_n$ with $k_n\ge i$ and $\tau $ satisfies $\lambda ([\tau ]_F)\le x$ then by the claim ${\lvert \tau \rvert } C+M\le x$ , and thus ${\lvert \tau \rvert } \le C^{-1}( x-M)$ . But by hypothesis there are $d,K$ such that eventually ${{\lvert {\{\tau \in L :{\lvert \tau \rvert } \le y\,\}} \rvert } \le Ky^d}$ . So if x is sufficiently large there are at most $K(C^{-1}(x-M))^d\in O(x^d)$ strings $\tau \in L$ satisfying $\lambda ([\tau ]_F)\le x$ ; so A is $\lambda $ -sparse.

• $(\impliedby )$ Let $\Sigma $ be an $F^s$ -spanning set for some $s>0$ . Note first that A is $\lambda _{\Sigma } $ -sparse. Indeed, by Lemma 5.8 (applied to $(\Gamma ,F^s)$ with $S=\Sigma $ ) there is $M\in \mathbb {R}$ such that $\lambda ([\sigma ]_{F^s}) \le {\lvert \sigma \rvert } C+M$ for all $\sigma \in \Sigma ^*$ . So if $\lambda _{\Sigma } (a)\le x$ then $\lambda (a)\le xC+M $ ; thus $f_{A,\lambda _{\Sigma } }(x)\le f_{A,\lambda }(xC+M)\in O(x^d)$ for some d, and A is $\lambda _{\Sigma } $ -sparse.

  Let $L = \{\sigma \in \Sigma ^* : [\sigma ]_{F^s}\in A\}$ ; so L is regular by Proposition 2.6. Fix any total order $\preceq $ on $\Sigma $ , and let $\widetilde {L}$ be as in Lemma 5.9; so $\widetilde {L}$ is sparse, since $[L]_{F^s} = A$ is $\lambda _{\Sigma } $ -sparse. So $A = [\widetilde {L}]_{F^s}$ is F-sparse.

Proof The right-to-left direction is by definition of F-sparsity. For the left-to-right direction, we use Theorem 5.10 to deduce that $[L]_{F^r}$ is $\lambda _{\Sigma } $ -sparse, at which point it follows from Lemma 5.9 that $\widetilde {L}$ is sparse.

Proof For the right-to-left direction, note by Proposition 5.4(1) that A is $F^r$ -sparse. So there is $s>0$ with an $F^{rs}$ -spanning set $\Sigma $ for H and $L\subseteq \Sigma ^*$ sparse such that $A = [L]_{F^{rs}}$ . Then using [Reference Bell and Moosa2, Lemmas 5.6 and 5.7], since there is an $F^r$ -spanning set for $\Gamma $ we may assume there is an $F^{rs}$ -spanning set $\Sigma '$ for $\Gamma $ containing $\Sigma $ . Then $L\subseteq (\Sigma ')^*$ witnesses that A is F-sparse in $\Gamma $ .

For the left-to-right direction, fix any length function $\lambda $ for some $(\Gamma ,F^s)$ (using Theorem 3.10). One can check that $\lambda $ is a length function for H; so by Theorem 5.10 applied to H it suffices to show that A is F-automatic in $H $ and $\lambda $ -sparse. By Theorem 5.10 applied to $\Gamma $ we get that A is F-automatic in $\Gamma $ and $\lambda $ -sparse. Then Corollary 3.11 yields that A is F-automatic in H, and since $A\subseteq H$ we get that $\lambda $ -sparsity in $\Gamma $ agrees with $\lambda $ -sparsity in H. So A is F-sparse in H.

Proof

1. 1. We first show that $\Gamma $ itself is not F-sparse. Since F-sparse implies $F^r$ -sparse (Proposition 5.4 (1)) and F-invariant implies $F^r$ -invariant, we may assume there is an F-spanning set $\Sigma $ . By Lemma 3.5 we may assume the exceptional set of $\lambda _{\Sigma } $ contains only elements of finite F-orbit; say the new associated constants are $C,D,E$ . Note that we can take $C=1$ : the constants obtained from Proposition 3.8 are $C=D=E=1$ , and Lemma 3.5 doesn’t require changing C. Note that there is $a\in \Sigma $ of infinite F-orbit: otherwise by Remark 3.6 all $a\in \Sigma $ would be of finite order as well, and thus

   $$ \begin{align*}\mathbb{Z}[F]a= \left\{\sum_{i<{\lvert{\{a,Fa,\ldots \}}\rvert} } k_iF^ia : \text{ each } k_i < {\lvert {a} \rvert}\right\} \end{align*} $$
   would be finite, and $\Gamma = \mathbb {Z}[F]\Sigma $ would be finite, a contradiction.

   Fix $a\in \Sigma $ of infinite F-orbit; fix $s>D+E$ .

   Claim 5.15. Suppose $\sigma \in \{- a,0,a\}^*\setminus \{0\}^* $ . Then $[\sigma ]_{F^s}\ne 0$ .

   Proof We show that $\lambda _{\Sigma } ([\sigma ]_{F^s})\ne 0$ , which will suffice.

   Let $\ell ={\lvert \sigma \rvert }>0$ . The claim is clear when $\ell =1$ ; assume then that $\ell \ge 2$ . We may assume $\sigma $ has no trailing zeroes and, by possibly negating, that $\sigma _{\ell -1}=a$ ; so

   $$ \begin{align*}\lambda _{\Sigma} ([\sigma ]_{F^s}) = \lambda_{\Sigma} ([\sigma _0\cdots \sigma _{\ell -2}]_{F^s} + F^{s(\ell -1)}a). \end{align*} $$

   We look to apply the reverse ultrametric inequality. Note that $\lambda _{\Sigma } ([\sigma _0\cdots \sigma _{\ell -2}]_{F^s})\le s(\ell -2)+1 $ by definition of $\lambda _{\Sigma } $ . Thus

   $$ \begin{align*}\lambda _{\Sigma} (F^{s(\ell -1)}a)\ge 1+s(\ell -1)-E> 1+s(\ell -2)+D \ge \lambda_{\Sigma} ([\sigma _0\cdots \sigma _{\ell -2}]_{F^s})+D \end{align*} $$

   by the logarithmic property (recalling that $C=1$ ) and since $s>D+E$ ; note that the logarithmic property applies since a has infinite F-orbit. So by the reverse ultrametric inequality

   $$ \begin{align*}\lambda _{\Sigma} ([\sigma ]_{F^s})\ge \lambda_{\Sigma} (F^{s(\ell -1)}a) -D\ge 1+s(\ell -1)-E -D \ge 1+s-E-D> 0, \end{align*} $$

   since $\ell \ge 2$ and $s>D+E$ . So in particular $[\sigma ]_{F^s}\ne 0$ .

   It follows that $[\cdot ]_{F^s} \restriction \{0,a\}^*a$ is injective. Indeed, suppose $\sigma ,\tau \in \{0,a\}^*a$ are distinct; then we can write $[\sigma ]_{F^s}-[\tau ]_{F^s}= [\nu ]_{F^s}$ for some $\nu \in \{-a,0,a\}^*\setminus \{0\}^*$ . Hence by the claim $[\sigma ]_{F^s}-[\tau ]_{F^s}\ne 0$ .

   But then

   $$ \begin{align*}f_{\Gamma ,\lambda _{\Sigma} }(s\ell +1) &= {\lvert{\{[\sigma ]_F : \sigma \in\Sigma ^*, {\lvert \sigma\rvert} \le s\ell +1\}} \rvert} \ge {\lvert{\{ [\sigma ]_{F^s} : \sigma \in\{0,a\}^{(\ell )}a\}} \rvert}\\ &= {\lvert{\{0,a\}^{(\ell )}a} \rvert} = 2^{\ell}. \end{align*} $$
   So $f_{\Gamma ,\lambda _{\Sigma } }\notin O(x^d)$ for any d; so $\Gamma $ is not $\lambda _{\Sigma } $ -sparse, and hence by Theorem 5.10 $\Gamma $ is not F-sparse.

   Suppose now that H is an infinite F-invariant subgroup of $\Gamma $ ; we show that A contains no coset of H. Replacing A by a translate (which is harmless by Proposition 5.4(4)), it suffices to show that A doesn’t contain H. By the above special case we get that H isn’t F-sparse in H; so Corollary 5.13 yields that H isn’t F-sparse in $\Gamma $ . Since H is F-invariant, it is F-automatic in $\Gamma $ ; this follows from Corollary 3.11. So if we had $A\supseteq H$ then by Proposition 5.4(3) H would be F-sparse in $\Gamma $ , a contradiction. So $A\not \supseteq H$ , as desired.

2. 2. Again using Proposition 5.4(1) we may assume there is a length function $\lambda $ for $(\Gamma ,F)$ . Since F-sparsity is closed under translation (Proposition 5.4(4)), it suffices to show that A does not contain any infinite $H\le \Gamma $ ; suppose for contradiction there is such an H. Since $\Gamma $ is finitely generated and H is infinite there is some $a\in H$ of infinite order; we will show that $\mathbb {Z}a$ isn’t $\lambda $ -sparse. We show by induction on k that if $1\le n\le 2^k$ then $\lambda (na)\le \lambda (a)+kD$ . The base case $k=0$ is immediate. For the induction step, suppose the claim holds of k; suppose $2^k < n\le 2^{k+1}$ . Then

   $$ \begin{align*}\lambda (na) &= \lambda (2^ka + (n-2^k)a) \le \max(\lambda (2^ka),\lambda ((n-2^k)a))+D\\ &\le (\lambda (a)+kD)+D\le \lambda (a)+(k+1)D \end{align*} $$
   by the induction hypothesis.

   Then $\{na : n\in \mathbb {Z},\lambda (na)\le \lambda (a)+kD\}\supseteq \{na: 1\le n\le 2^k\}$ contains at least $2^k$ elements. So $f_{\mathbb {Z}a,\lambda }(x)\notin O(x^d)$ for any d, and $\mathbb {Z}a$ isn’t $\lambda $ -sparse. But $A\supseteq H\supseteq \mathbb {Z}a$ ; so $f_{A,\lambda }(x)\ge f_{\mathbb {Z}a,\lambda }(x)$ , and A isn’t $\lambda $ -sparse. So A isn’t F-sparse by Theorem 5.10, a contradiction.

Question 6.1. Suppose $\Gamma $ is a finitely generated abelian group and $F\colon \Gamma \to \Gamma $ is an injective endomorphism, such that $(\Gamma ,F)$ admits a spanning set for some $r>0$ . Which F-automatic sets of $\Gamma $ are stable?

Proof Fix $r>0$ for which there is a length function $\lambda $ for $(\Gamma ,F^r)$ , say with associated constants $C,D,E$ . By Lemma 3.5 and Remark 3.6 we may assume the logarithmic property applies to all non-zero elements.

Suppose $G\in \bigcap _{i\in \mathbb {N}}(F^i)$ , and suppose $a\in \Gamma $ ; suppose for contradiction that $Ga\ne 0$ . For $n\in \mathbb {N}$ since $G\in (F^{rn})$ there is $G_n\in \mathbb {Z}[F]$ such that $G = F^{rn}G_n$ . Since $Ga\ne 0$ we get that $G_na\ne 0$ , and thus the logarithmic property applies to $G_na$ . So $\lambda (Ga) = \lambda (F^{rn}G_na) \ge \lambda (G_na)+nC-E\ge nC-E$ . But this grows without bound, a contradiction. So $Ga = 0$ for all $a\in \Gamma $ , and $G=0$ .

Proof By replacing F with a power thereof we may assume $\Gamma $ admits an F-spanning set (since A is also $F^r$ -sparse by Proposition 5.4(1)). By Proposition 5.3 we can write A as a finite union of sets of the form $\gamma +[a_1^*\cdots a_n^*]_{F^s} $ for some $s>0$ and $\gamma ,a_1,\ldots ,a_n\in \Gamma $ . If we let $b_1,\ldots ,b_n\in \Gamma $ be such that $a_i = \sum _{j\ge i} b_i$ then we can rewrite

$$ \begin{align*}\gamma +[a_1^*\cdots a_n^*]_{F^s} = \gamma + \{[b_1^{e_1}]_{F^s} + \cdots + [b_n^{e_n}]_{F^s} : e_1\le\cdots \le e_n\} \end{align*} $$

and thus write A as a finite union of sets of this form. Fix one such $\gamma +\{[b_1^{e_1}]_{F^s} + \cdots + [b_n^{e_n}]_{F^s} : e_1\le \cdots \le e_n\}$ in the union; we show it is contained in some B of the desired form that is itself contained in A.

We will proceed by examining the $e_i$ such that $[b_1^{e_1}]_{F^s} + \cdots + [b_n^{e_n}]_{F^s}\in A$ .

Proof Fix $\sigma \in S_n$ , and suppose $e_{\sigma (1)}\le \cdots \le e_{\sigma (n)}$ . Let $c_i = \sum _{j\ge i}b_{\sigma (i)}$ ; so

$$ \begin{align*}[b_1^{e_1}]_{F^s}+\cdots + [b_n^{e_n}]_{F^s}\in A\iff [c_1^{e_1}c_2^{e_2-e_1}\cdots c_n^{e_n-e_{n-1}}]_{F^s}\in A-\gamma. \end{align*} $$

By [Reference Bell and Moosa2, Lemmas 5.6 and 5.7] there is an $F^s$ -spanning set $\Sigma $ containing all the $c_i$ ; so by Proposition 2.6 $\{\sigma \in \Sigma ^* : [\sigma ]_{F^s}\in A-\gamma \}$ is regular. Then as argued in the proof of [Reference Hawthorne5, Proposition 2.2] there is some Boolean combination $\phi (x_1,\ldots ,x_n)$ of congruences and equalities between one variable and one constant such that

$$ \begin{align*}(e_1,\ldots ,e_n)\in X &\iff [c_1^{e_1}c_2^{e_2-e_1}\cdots c_n^{e_n-e_{n-1}}]_{F^s}\\ &\iff (\mathbb{N},0,S,\delta \mathbb{N})\models \phi (e_1,e_2-e_1,\ldots ,e_n-e_{n-1}) \end{align*} $$

(again, under the assumption that $e_{\sigma (1)}\le \cdots \le e_{\sigma (n)}$ ). But a congruence or equality between a constant $N\in \mathbb {N}$ and either $e_1$ or $e_{i+1}-e_i$ can be expressed as a formula in $(\mathbb {N},0,S,\delta \mathbb {N})$ , for some sufficiently large $\delta $ . So this is in turn equivalent to $(\mathbb {N},0,S,\delta \mathbb {N})\models \psi (e_1,\ldots ,e_n)$ for some quantifier-free $\psi $ .

Doing this for all $\sigma $ and taking LCMs of the $\delta $ and disjunctions over the possible orderings of the $e_i$ , we find that there is a single quantifier-free formula $\phi $ in $(\mathbb {N},0,S,\delta \mathbb {N},<)$ such that $X = \phi (\mathbb {N}^n)$ . Then $\phi $ is a stable formula under any partitioning of its variables: large ladders for $\phi $ would yield large ladders for the corresponding partitioning of

$$ \begin{align*}x_1+\cdots + x_n\in A-\gamma, \end{align*} $$

and the latter is stable under any partitioning of the variables as A is stable (and addition is commutative and associative).

But the stable quantifier-free formulas in $(\mathbb {N},0,S,\delta \mathbb {N},<)$ are known to be quantifier-free formulas in $(\mathbb {N},0,S,\delta \mathbb {N})$ ; this is [Reference Hawthorne5, Proposition 3.3]. So X is quantifier-free definable in $(\mathbb {N},0,S,\delta \mathbb {N})$ .

We get by Lemma 6.4 that $(\Gamma ,F)$ satisfies (†). Moreover the fact that $\Gamma $ is infinite and finitely generated and that F is injective implies that $\mathbb {Z}[F]$ satisfies the other conditions assumed by [Reference Moosa and Scanlon6]: namely that $\mathbb {Z}[F]$ is a finite extension of $\mathbb {Z}$ generated by F and that F is not a zero divisor in $\mathbb {Z}[F]$ . So by [Reference Moosa and Scanlon6, Theorem A] $(\Gamma ,\mathcal {F})$ admits quantifier elimination; so Y (and hence $\gamma +Y$ ) is a Boolean combination of F-sets. At this point the argument given in the proof of [Reference Hawthorne5, Theorem 3.1] shows that $\gamma +Y$ is a Boolean combination of F-sparse F-sets. Now by Corollary 5.14 an F-sparse F-set must be groupless; so $\gamma +Y$ is a Boolean combination of groupless F-sets. But

$$ \begin{align*}\gamma +\{[b_1^{e_1}]_{F^s} + \cdots + [b_n^{e_n}]_{F^s}: e_1\le\cdots \le e_n\}\subseteq \gamma +Y \subseteq A. \end{align*} $$

So we can replace $\gamma +\{[b_1^{e_1}]_{F^s} + \cdots + [b_n^{e_n}]_{F^s}: e_1\le \cdots \le e_n\}$ with $\gamma +Y$ in the union defining A without changing the union. Applying this to all sets in the union, we have written A as a Boolean combination of groupless F-sets.