The Degree of Squares is an Atom

Abstract

We answer an open question in the theory of degrees of infinite sequences with respect to transducibilityby finite-state transducers. An initial study of this partial order of degrees was carried out in [1], but many basic questions remain unanswered.One of the central questions concerns the existence of atom degrees, other than the degree of the ‘identity sequence’ $1 0^0 1 0^1 1 0^2 1 0^3 \cdots$. A degree is called an ‘atom’ if below it there is only the bottom degree $\varvec{0}$, which consists of the ultimately periodic sequences. We show that also the degree of the ‘squares sequence’ $1 0^0 1 0^1 1 0^4 1 0^9 1 0^{16}\cdots$ is an atom.

As the main tool for this result we characterise the transducts of ‘spiralling’ sequences and their degrees. We use this to show that every transduct of a ‘polynomial sequence’ either is in $\varvec{0}$ or can be transduced back to a polynomial sequence for a polynomial of the same order.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Fig. 1.

A finite-state transducer realising the sum of consecutive bits modulo 2.

1 Introduction

Finite-state transducers are ubiquitous in computer science, but little is known about the transducibility relation they induce on infinite sequences. A finite-state transducer (FST) is a deterministic finite automaton which reads the input sequence letter by letter, in each step producing an output word and changing its state. An example of an FST is depicted in Fig. 1, where we write ‘a | w’ along the transitions to indicate that the input letter is a and the output word is w. For example, it transduces the Thue-Morse sequence $\mathsf {T}= 0110 1001 1001 0110 \cdots$ to the period doubling sequence $\mathsf {P}= 101 1 101 0 101 1 101 1 \cdots$.

We are interested in transductions of infinite sequences. We say that a sequence $\sigma$ is transducible to a sequence $\tau$, $\sigma \ge \tau$, if there exists an FST that transforms $\sigma$ into $\tau$. The relation $\ge$ is a preorder on the set $\Sigma ^{\mathbb {N}}$ of infinite sequences, which induces an equivalence relation $\equiv$ on $\Sigma ^{\mathbb {N}}$, and a partial order on the set of (FST) degrees, that is, the equivalence classes with respect to $\equiv$.

So we have $\mathsf {T}\ge \mathsf {P}$. Also the back transformation can be realised by an FST, $\mathsf {P}\ge \mathsf {T}$. Hence the sequences are equivalent, $\mathsf {T}\equiv \mathsf {P}$, and are in the same degree.

The bottom degree $\varvec{0}$ is formed by the ultimately periodic sequences, that is, all sequences of the form $u v v v \cdots$ for finite words u, v with v non-empty. Every infinite sequence can be transduced to any ultimately periodic sequence.

There is a clear analogy between degrees induced by transducibility and the recursion-theoretic degrees of unsolvability (Turing degrees). Hence many of the problems settled for Turing degrees, predominantly in the 1940s, 50s and 60s, can be asked again for FST degrees.

Fig. 2.

Possible structures in the hierarchy (no intermediate points on the arrows).

Some initial results on FST degrees have been obtained in [1]: the partial order of degrees is not dense, not well-founded, there exist no maximal degrees, and a set of degrees has an upper bound if and only if the set is countable. The morphic degrees, and the computable degrees form subhierarchies. Also shown in [1] is the existence of an ‘atom’ degree, namely the degree of $1 0^0 1 0^1 1 0^2 1 0^3 \cdots$.¹ A degree $D \ne \varvec{0}$ is an atom if there exists no degree strictly between D and the bottom degree $\varvec{0}$. Thus every transduct of a sequence in an atom degree D is either in $\varvec{0}$ or still in D. The following questions, which have been answered for Turing degrees, remain open for the FST degrees:

• (i) How many atom degrees exist?

• (ii) When do two degrees have a supremum (or infimum)? In particular, are there pairs of degrees without a supremum (infimum)?

• (iii) Do the configurations displayed in Fig. 2 exist?

• (iv) Can every finite distributive lattice be embedded in the hierarchy?

At the British Colloquium for Theoretical Computer Science 2014, Jeffrey Shallit offered £20 for each of the following questions, see [2]:

• (a) Is the degree of the Thue-Morse sequence an atom?

• (b) Are there are atom degrees other than that of $1 0^0 1 0^1 1 0^2 1 0^3 \cdots$?

We answer (b) by showing that the degree of the ‘squares’ $1 0^0 1 0^1 1 0^4 1 0^9 \cdots$ is an atom. The main tool that we use in the proof is a characterisation of transducts of ‘spiralling’ sequences (Theorem 4.22), which has the following consequence (Proposition 5.1): For all $k \ge 1$ it holds that every transduct $\sigma \not \in \varvec{0}$ of the sequence $\langle n^k\rangle = 1 0^{0^k} 1 0^{1^k} 1 0^{2^k} 1 0^{3^k} \cdots$ has, in its turn, a transduct of the form $\langle p(n)\rangle = 1 0^{p(0)} 1 0^{p(1)} 1 0^{p(2)} 1 0^{p(3)} \cdots$ where p(n) is a polynomial also of degree k. This fact not only enables us to show that the degree of the squares sequence is an atom, by using it for $k=2$, but it also suggests that the analogous result for the degree of $\langle n^k\rangle$, for arbitrary $k \ge 1$, has come within reach. For this it would namely suffice to show, for polynomials p(n) of degree k, that $\langle p(n)\rangle$ can be transduced back to $\langle n^k\rangle$.

We obtain that there is a pair of non-zero degrees whose infimum is $\varvec{0}$, namely the pair of atom degrees of $\langle n\rangle$ and $\langle n^2\rangle$. We moreover use Theorem 4.22 to show that there is a non-atom degree that has no atom degree below it (Theorem 4.24).

2 Preliminaries

We use standard terminology and notation, see, e.g., [3]. Let $\Sigma$ be an alphabet, i.e., a finite non-empty set of symbols. We denote by $\Sigma ^*$ the set of all finite words over $\Sigma$, and by $\varepsilon$ the empty word. We let $\Sigma ^+ = \Sigma ^*\setminus \{\varepsilon \}$. The set of infinite sequences over $\Sigma$ is $\Sigma ^{\mathbb {N}} = \{ \sigma \mid \sigma : \mathbb {N}\rightarrow \Sigma \}$ with $\mathbb {N}= \{0,1,2,\ldots \}$, the set of natural numbers. For $u \in \Sigma ^*$, we let $u^\omega = u u u \cdots$. We define $\mathbb {N}_{<k} = \{0,1,\ldots ,k-1\}$. We let $\Sigma ^\infty = \Sigma ^* \cup \Sigma ^{\mathbb {N}}$ denote the set of all words over $\Sigma$. For $u \in \Sigma ^*$ and $v \in \Sigma ^\infty$ we write $u \sqsubseteq v$ to denote that u is a prefix of v, that is, when $v = uv'$ for some $v' \in \Sigma ^\infty$. For $f : \mathbb {N}\rightarrow A$ and $k \in \mathbb {N}$, the k-th shift of f is defined by $\mathcal {S}^{k}(f)(n) = f(n+k)$, for all $n \in \mathbb {N}$.

We use the notation $\mathbf {a}$ to denote a tuple $\mathbf {a} = \langle a_0,a_1,\ldots ,a_{k-1}\rangle$ where the $a_i$ are elements from some set A; the length of $\mathbf {a}$ is k. Given a tuple $\mathbf {a}$ we use $a_i$ for the element indexed i, that is, we start indexing from 0 onward. We use the notation $\mathbf {a}'$ to denote the rotated tuple  $\mathbf {a}' = \langle a_1,\ldots ,a_{k-1}, a_0\rangle$.

3 Finite-State Transducers and Degrees

For a thorough introduction to finite-state transducers, we refer to [3]. Here we only consider complete pure sequential finite-state transducers, where for every state q and input letter a there is precisely one successor state $\delta (q,a)$, and the functions realised by these transducers preserve prefixes. We use $\mathbf {2}= \{0,1\}$ both for the input and the output alphabet.

Definition 3.1

A finite-state transducer (FST) is a tuple $T = \langle Q,q_0,\delta ,\lambda \rangle$ where Q is a finite set of states, $q_{0} \in Q$ is the initial state, $\delta : Q \times \mathbf {2}\rightarrow Q$ is the transition function, and $\lambda : Q \times \mathbf {2}\rightarrow \mathbf {2}^*$ is the output function.

We homomorphically extend the transition function $\delta$ to $Q \times \mathbf {2}^* \rightarrow Q$ and the output function $\lambda$ to $Q \times \mathbf {2}^\infty \rightarrow \mathbf {2}^\infty$ as follows:

$$\begin{aligned} \delta (q,\varepsilon )&= q&\delta (q,au)&= \delta (\delta (q,a),u)&(q \in Q, a \in \mathbf {2}, u \in \mathbf {2}^*) \\ \lambda (q,\varepsilon )&= \varepsilon&\lambda (q,au)&= \lambda (q,a) \cdot \lambda (\delta (q,a),u)&(q \in Q, a \in \mathbf {2}, u \in \mathbf {2}^\infty )\,. \end{aligned}$$

The function $T : \mathbf {2}^\infty \rightarrow \mathbf {2}^\infty$ realised by the FST T is defined by $T(u) = \lambda (q_0,u)$, for all $u \in \mathbf {2}^\infty$.

Definition 3.2

Let $T = \langle Q,q_0,\delta ,\lambda \rangle$ be an FST. A zero-loop in T is a sequence of states $q_{1},\ldots ,q_{n}$ with $n > 1$ such that $q_1 = q_n$ and $q_{i} \ne q_{j}$ for all i, j with $1 \le i < j < n$ and $q_{i+1} = \delta (q_{i},0)$ for all $1 \le i < n$. The length of the zero-loop is $n-1$. (Note that there can only be finitely many zero-loops in an FST.) Let $T = \langle Q,q_0,\delta ,\lambda \rangle$ be an FST. We define $\mathsf {Z}(T)$ as the least common multiple of the lengths of all zero-loops of T.

Let T be an FST with states Q. From any state $q \in Q$, after reading the word $0^{|Q|}$, the automaton must have entered a zero-loop (by the pigeonhole principle there must be a state repetition). By definition of $\mathsf {Z}(T)$, the length $\ell$ of this loop divides $\mathsf {Z}(T)$; say $\mathsf {Z}(T) = d \ell$ for some $d \ge 1$. As a consequence, reading $0^{|Q|+i\cdot \mathsf {Z}(T)}$ yields the output $\lambda (q,0^{|Q|})$ followed by d i copies of the output of the zero-loop. This yields a pumping lemma for FSTs, see also [1, Lemma 29].

Lemma 3.3

Let $T = \langle Q,q_0,\delta ,\lambda \rangle$ be an FST. For every $q \in Q$ and $n \ge |Q|$ there exist words $p,c \in \mathbf {2}^*$ such that for all $i \in \mathbb {N}$, $\delta (q,1 0^{n + i \cdot \mathsf {Z}(T)}) = \delta (q,1 0^n)$ and $\lambda (q,1 0^{n + i \cdot \mathsf {Z}(T)}) = p c^{i}$ .

Definition 3.4

Let T be an FST, and let $\sigma ,\tau \in \mathbf {2}^{\mathbb {N}}$ be infinite sequences. We say that T transduces $\sigma$ to $\tau$, and that $\tau$ is the T-transduct of $\sigma$, which we denote by $\sigma \ge _{T} \tau$, whenever $T(\sigma ) = \tau$. We write $\sigma \ge \tau$, and call $\tau$ a transduct of $\sigma$, if there exists an FST T such that $\sigma \ge _{T} \tau$.

Clearly, the relation $\ge$ is reflexive. By composition of FSTs (the so-called ‘wreath product’), the relation $\ge$ is also transitive, see [1, Remark 9]. We write $\sigma >\tau$ when $\sigma \ge \tau$ but not $\tau \ge \sigma$. Whenever we have $\sigma \ge \tau$ as well as a back-transduction $\tau \ge \sigma$, we consider $\sigma$ and $\tau$ to be equivalent.

Definition 3.5

We define the relation ${\equiv } \subseteq \mathbf {2}^{\mathbb {N}} \times \mathbf {2}^{\mathbb {N}}$ by ${\equiv } = {\ge } \cap {\ge ^{-1}}$. For a sequence $\sigma \in \mathbf {2}^{\mathbb {N}}$ the equivalence class $[\sigma ] = \{\tau \mid \sigma \equiv \tau \}$ is called the degree of $\sigma$.

A degree $[\sigma ]$ is an atom if $[\sigma ] \ne \varvec{0}$ and there is no degree $[\tau ]$ such that $[\sigma ] >[\tau ] >\varvec{0}$.

4 Characterising Transducts of Spiralling Sequences

In this section we characterize the transducts of ‘spiralling’ sequences. Proofs omitted in the text can be found in the extended version [4].

Definition 4.1

For a function $f : \mathbb {N}\rightarrow \mathbb {N}$ we define the sequence $\langle f\rangle \in \mathbf {2}^{\mathbb {N}}$ by

$$\begin{aligned} \displaystyle \langle f\rangle = \prod _{i = 0}^{\infty } 1 0^{f(i)} = 1 0^{f(0)} \, 1 0^{f(1)} \, 1 0^{f(2)} \, \cdots \,. \end{aligned}$$

For a sequence $\langle f\rangle$, we often speak of the n-th block of $\langle f\rangle$ to refer to the occurrence of the word $10^{f(n)}$ in $\langle f\rangle$.

In the sequel we often write $\langle f(n)]\rangle$ to denote the sequence $\langle n \mapsto f(n)\rangle$. We note that there is a one-to-one correspondence between functions $f : \mathbb {N}\rightarrow \mathbb {N}$, and infinite sequences over the alphabet $\mathbf {2}$ that start with the letter 1 and that contain infinitely many occurrences of the letter 1. Every degree is of the form $[\langle f\rangle ]$ for some $f : \mathbb {N}\rightarrow \mathbb {N}$.

The following lemma is concerned with some basic operations on functions that have no effect on the degree of $\langle f\rangle$ (multiplication with a constant, and x- and y-shifts), and others by which we may go to a lower degree (taking subsequences, merging blocks).

Lemma 4.2

Let $f : \mathbb {N}\rightarrow \mathbb {N}$, and $a,b \in \mathbb {N}$. It holds that:

Definition 4.3

Let A be a set. A function $f : \mathbb {N}\rightarrow A$ is ultimately periodic if for some integers $n_0 \ge 0$, $p > 0$ we have $f(n + p) = f(n)$ for all $n \ge n_0$.

Definition 4.4

A function $f : \mathbb {N}\rightarrow \mathbb {N}$ is called spiralling if

• (i) $\lim _{n \rightarrow \infty } f(n) = \infty$, and

• (ii) for every $m \ge 1$, the function $n \mapsto f(n) \text {mod} m$ is ultimately periodic.

Functions with the property (ii) in Definition 4.4 have been called ‘ultimately periodic reducible’ by Siefkes [5] (quotation from [6]). Note that the identity function is spiralling. Furthermore scalar products, and pointwise sums and products of spiralling functions are again spiralling. As a consequence also polynomials $a_k n^k + a_{k-1} n^{k-1} + \cdots + a_0$ are spiralling.

In the remainder of this section, we will characterise the transducts $\sigma$ of $\langle f\rangle$ for spiralling f. We will show that if such a transduct $\sigma$ is not ultimately periodic, then it is equivalent to a sequence $\langle g\rangle$ for a spiralling function g, and moreover, g can be obtained from f by a ‘weighted product’.

Lemma 4.5

Let $f : \mathbb {N}\rightarrow \mathbb {N}$ be a spiralling function. We have $\langle f\rangle \ge \sigma$ if and only if $\sigma$ is of the form

$$\begin{aligned} \sigma = w \cdot \prod _{i = 0}^{\infty } \prod _{j = 0}^{m-1} p_j \, c_j^{\varphi (i,j)}&\text {where}&\varphi (i,j) = \frac{f(n_0 + m i + j) - a_j}{z} \,, \end{aligned}$$

(1)

for some integers $n_0,m,a_j \ge 0$ and $z > 0$, and finite words $w, p_j, c_j \in \mathbf {2}^*$ $(0 \le j <m)$ such that $\varphi (i,j) \in \mathbb {N}$ for all $i \in \mathbb {N}$ and $j \in \mathbb {N}_{<m}$.

Proof

Assume $\langle f\rangle \ge \sigma$ and let $T = \langle Q,q_0,\delta ,\lambda \rangle$ be an FST that transduces $\langle f\rangle$ to $\sigma$. As f is spiralling, there exist $\ell _0, p \in \mathbb {N}$, $p > 0$ such that $f(n) \equiv f(n+p) \pmod {\mathsf {Z}(T)}$ for every $n \ge \ell _0$. Moreover, as a consequence of $\lim _{n \rightarrow \infty } f(n) = \infty$, there exists $\ell _1 \in \mathbb {N}$ such that $f(n) \ge |Q|$ for every $n \ge \ell _1$.

For $n \in \mathbb {N}$, let $q_n \in Q$ be the state that the automaton T is in, before reading the n-th occurrence of 1 in the sequence $\sigma$ (i.e., the start of the block $1 0^{f(n)}$). By the pigeonhole principle there exist $n_0,m \in \mathbb {N}$ with $\max \{\ell _0,\ell _1\} < n_0$ and $m > 0$ such that $m \equiv 0 \pmod {p}$ and $q_{n_0} = q_{n_0+m}$. Then, for every $i \in \mathbb {N}$ and $j \in \mathbb {N}_{<m}$, we have $f(n_0 + mi + j) \ge |Q|$ and $f(n_0 + mi + j) \equiv f(n_0 + j) \pmod {\mathsf {Z}(t)}$. For $j \in \mathbb {N}_{<m}$, we define $a_j = \min \{f(n_0 + mi + j) \mid i \in \mathbb {N}\}$. Note that $a_j \ge |Q|$. Then for all $i \in \mathbb {N}$ and $j \in \mathbb {N}_{<m}$ we have: $f(n_0 + mi + j) = a_j + \varphi (i,j) \cdot z$ where $\varphi (i,j) = (f(n_0 + mi + j)-a_j) / z$ and $z = \mathsf {Z}(T)$. Using Lemma 3.3 it follows by induction that $q_{n_0+n} = q_{n_0+m+n}$ for every $n \in \mathbb {N}$. Hence $q_{n_0+j} = q_{n_0+mi+j}$ for every $i \in \mathbb {N}$ and $j \in \mathbb {N}_{<m}$. Then, again by Lemma 3.3, for every $j \in \mathbb {N}_{<m}$ there exist words $p_j,c_j \in \mathbf {2}^*$ such that $\lambda (q_{n_0+mi+j}, 1 0^{f(n_0 + mi + j)}) = \lambda (q_{n_0+j}, 1 0^{a_j + \varphi (i,j) \cdot \mathsf {Z}(T)}) = p_j c_j^{\varphi (i,j)}$ for all $i \in \mathbb {N}$. We conclude that

$$\begin{aligned} \sigma = \prod _{n = 0}^{\infty } \lambda (q_n,10^{f(n)}) = w \cdot \prod _{i = 0}^{\infty } \prod _{j = 0}^{m-1} p_j \, c_j^{\varphi (i,j)}\,, \end{aligned}$$

where $w = \prod _{n = 0}^{n_0-1} \lambda (q_n,10^{f(n)})$.

For the other direction, we refer to the extended version [4].    $\square$

Fig. 3.

Transducers used in Examples 4.6 and 4.8.

Example 4.6

We illustrate the influence of both the zero-loops of the automaton as well as the growth of the block lengths of the input sequence, on the size m of the innermost product of Lemma 4.5. Consider the FST $T = \langle \{q_0,q_1,q_2\},q_0,\delta ,\lambda \rangle$ in Fig. 3 on the left, and the sequence $\langle \left\lfloor {\frac{n}{2}}\right\rfloor \rangle = 1 1 10 10 10^2 10^2 10^3 10^3 10^4 10^4 \cdots$, where $\left\lfloor {x}\right\rfloor = \max \{ n \in \mathbb {N}\mid n \le x \}$. We investigate the sequence $r_0 a_0 r_1 a_1 r_2 \cdots$ of states r of T alternated with letters a from the input sequence, in such a way that T is in state $r_n$ after having read the word $a_0 a_1 \cdots a_{n-1}$,

$$\begin{aligned} \underline{q_0} 1 q_2 1 q_1 1 q_0 0 q_1 1 q_0 0 q_1 1 q_0 0 q_1 0 q_2 1 q_1 0 q_2 0 \underline{q_0} 1 q_2 0 q_0 0 q_1 0 q_2 1 q_1 0 q_2 0 q_0 0 \cdots \end{aligned}$$

The two underlined occurrences of $q_0$ indicate a repetition of states in combination with a repetition of the block size modulo $\mathsf {Z}(T) = 3$. The number of blocks between these occurrences, forming the repetition, is $m = 6$. Actually, following the proof of Lemma 4.5 precisely, the algorithm would instead select the repetition starting from the second underlined occurrence of $q_0$. The reason is that in general, when reading a block $100\cdots 0$, only after reading |Q| zeros, we are guaranteed to be in a zero-loop. For this FST T, all states are on a zero-loop, and so we enter the loop immediately.

From Lemma 4.5 it follows that FSTs can only transform the length of blocks by linear functions (and merge blocks). As a consequence, FSTs typically cannot slow down the growth rate of blocks in spiralling sequences by more than a linear factor. This yields the following simple criterion for non-reducibility.

Lemma 4.7

Let $f,g : \mathbb {N}\rightarrow \mathbb {N}$ be such that f is spiralling, g is not ultimately periodic and $g \in o(f)$, i.e., for every $a \in \mathbb {N}$ there is $n_0 \in \mathbb {N}$ such that for all $n \ge n_0$ it holds that $f(n) \ge a g(n)$. Then $\langle f\rangle \not \ge \langle g\rangle$.

Note that the reverse $\langle g\rangle \not \ge \langle f\rangle$ does not follow. For example, we have $\langle 4^n\rangle \not \ge \langle 2^n\rangle$, but $\langle 2^n\rangle \ge \langle 4^n\rangle$.

There can be several ways to factor the transduct $\sigma$ in the statement of Lemma 4.5, as shown by the following example.

Example 4.8

Consider the FST $T = \langle \{q_0,q_1\},q_0,\delta ,\lambda \rangle$ in Fig. 3 on the right, and the sequence $\langle n\rangle = 1 10 10^2 10^3 10^4 \cdots$. The T-transduct of $\langle n\rangle$ is $T(\langle n\rangle ) = 1 \, 1 (01) \, 1 (10)^2 \, 1 (01)^3 \, 1 (10)^4 \, \cdots$. Using the double product (1) of Lemma 4.5 we have $w = \varepsilon$, $n_0 = 0$, $m = 2$, $p_0 = p_1 = 1$, $c_0 = 01$, $c_1 = 10$, $a_0 = a_1 = 0$, and $z = \mathsf {Z}(T) = 1$. Thus, $\varphi (i,j) = 2i + j$. Note that $c_1^\omega = p_0 c_0^\omega$, and so we can merge the factors of the innermost product, decreasing its size to $m = 1$. Then $T(\langle n\rangle ) = 1101 \, 1101 (0101) \, 1101 (0101)^2 \, 1101 (0101)^3 \, \cdots$, that is, in the double product (1), $T(\langle n\rangle )$ can be factored by choosing $m = 1$, $p_0 = 1101$, and $c_0 = 0101$.

Whenever we have the situation $c_j^\omega = p_{j+1}c_{j+1}^\omega$ in the representation (1) for some $j \in \mathbb {N}_{<m}$ (addition is modulo m), we speak of a ‘transition ambiguity’. We will eliminate such ambiguities by merging factors of the innermost product, as in Lemma 4.10. In general, this merging may involve weighted sums in the exponents. The following lemma is folklore, see for instance [7].

Lemma 4.9

If a sequence $\sigma$ is periodic with period lengths k and $\ell$, then it is periodic with period length $\gcd (k,\ell )$.

Lemma 4.10

Let $u,v,w \in \mathbf {2}^*$ be finite words with $u,w \ne \varepsilon$ such that $u^\omega = v w^\omega$. Then there exists a word $x \in \mathbf {2}^*$ and $a,b \in \mathbb {N}$ such that $u^m vw^n = vx^{am+bn}$ for all $m,n \in \mathbb {N}$.

Our goal is to obtain a simple characterisation of the degrees of the transducts $\sigma$ of spiralling sequences $\langle f\rangle$. To this end, we transform the transduct $\sigma$ into a sequence $\sigma '$ by replacing in the double product of Lemma 4.5 the displayed occurrence of $p_j$ by 1 and of $c_j$ by 0 for every $j \in \mathbb {N}_{<m}$. To guarantee that this transformation does not change the degree, that is $\sigma ' \equiv \sigma$, we first have to resolve transition ambiguities.

For the back transformation blocks $10^{\varphi (i,j)}$ have to be replaced by $p_j c_j^{\varphi (i,j)}$, an operation that is easily realised by an FST. If the product does not contain transition ambiguities, then also the transformation from $\sigma$ into $\sigma '$ can be realised by an FST and thus does not change the degree of the sequence, hence $\sigma \equiv \sigma '$. If there exists $j \in \mathbb {N}_{<m}$ with $c_j^\omega = p_{j+1}c_{j+1}^\omega$, then, by this transformation of $\sigma$ into $\sigma '$, one possibly leaves the degree of $\sigma$, i.e., $\sigma >\sigma '$. This is because for large enough $i\in \mathbb {N}$, an FST cannot recognise where a block $p_j c_j^{\varphi (i,j)}$ ends and where the next block $p_{j+1} c_{j+1}^{\varphi (i,j+1)}$ starts. This might make it impossible to realise the transformation by an FST, as then the FST cannot replace $p_{j+1}$ by 1.

Definition 4.11

A weight is a tuple $\langle a_0,\ldots ,a_{k-1},b\rangle \in \mathbb {Q}^{k+1}$ of rational numbers such that $a_0,\ldots ,a_{k-1} \ge 0$. Given a weight $\alpha = \langle a_0,\ldots ,a_{k-1},b\rangle$ and a function $f : \mathbb {N}\rightarrow \mathbb {N}$ we define $\alpha \cdot f \in \mathbb {Q}$ by

$$\begin{aligned} \alpha \cdot f \;=\; a_0 f(0) + a_1 f(1) + \cdots + a_{k-1} f(k-1) + b \,. \end{aligned}$$

The weight $\alpha$ is called constant when $a_j = 0$ for all $j \in \mathbb {N}_{<k}$. For a tuple of weights $\mathbf {\alpha } = \langle \alpha _0,\ldots ,\alpha _{m-1}\rangle$ we define its rotation by $\mathbf {\alpha }' = \langle \alpha _1,\ldots ,\alpha _{m-1},\alpha _0\rangle$.

For functions $f : \mathbb {N}\rightarrow \mathbb {N}$, and tuples $\mathbf {\alpha } = \langle \alpha _0,\alpha _1,\ldots , \alpha _{m-1}\rangle$ of weights, the weighted product of $\mathbf {\alpha }$ and f is a function $\mathbf {\alpha } \otimes f : \mathbb {N}\rightarrow \mathbb {Q}$ that is defined by induction on n through the following scheme of equations:

$$\begin{aligned} (\mathbf {\alpha } \otimes f)(0)&= \alpha _0 \cdot f \\ (\mathbf {\alpha } \otimes f)(n+1)&= (\mathbf {\alpha }' \otimes \mathcal {S}^{|\alpha _0|-1}(f))(n)&(n \in \mathbb {N}) \end{aligned}$$

where $|\alpha _i|$ is the length of the tuple $\alpha _i$, and $\mathcal {S}^{k}(f)$ is the k-th shift of f. A weighted product $\mathbf {\alpha } \otimes f$ is called natural if $(\mathbf {\alpha } \otimes f)(n) \in \mathbb {N}$ for all $n \in \mathbb {N}$.

In what follows, all weighted products $\mathbf {\alpha } \otimes f$ that we consider are assumed to be natural.

Example 4.12

Let $f(n) = n$ for all $n \in \mathbb {N}$, and $\mathbf {\alpha } = \langle \alpha _1,\alpha _2\rangle$ with $\alpha _1 = \langle 1,2,3,4\rangle$, $\alpha _2 = \langle 0,1,1\rangle$. Interpreting the functions f and $\mathbf {\alpha } \otimes f$ as sequences, the computation of $\mathbf {\alpha } \otimes f$ can be visualised as follows:

Thus, for $n = 0,1,2,3\ldots$ , $(\mathbf {\alpha } \otimes f)(n)$ takes the values $12,5,42,10,\ldots$ .

Lemma 4.13

Let $\mathbf {\alpha }$ be an m-tuple of weights ($m > 0$), and let $f : \mathbb {N}\rightarrow \mathbb {N}$. For all $n \in \mathbb {N}$ we have $(\mathbf {\alpha } \otimes f)(n) = \alpha _r \cdot \mathcal {S}^{t}(f)$ where $q,r \in \mathbb {N}$ with $r < m$ are such that $n = qm + r$, and $t = q \cdot \sum _{j = 0}^{m-1}(|\alpha _j| - 1) + \sum _{j = 0}^{r-1}(|\alpha _j| - 1)$.

Lemma 4.14

Let $f : \mathbb {N}\rightarrow \mathbb {N}$. If $\langle \mathbf {\alpha } \otimes f\rangle \not \in \varvec{0}$, then there exists $i \in \mathbb {N}_{<|\mathbf {\alpha }|}$ such that $\alpha _i$ is a non-constant weight.

Lemma 4.15

Let $f:\mathbb {N}\rightarrow \mathbb {N}$ be spiralling, and let $\mathbf {\alpha }$ be a tuple of non-constant weights. Then $\mathbf {\alpha } \otimes f$ is spiralling.

We will show that weighted products give rise to a characterisation, up to equivalence $\equiv$, of functions realised by FSTs on the set of spiralling sequences, see Theorem 4.22.

Lemma 4.16

Let $f : \mathbb {N}\rightarrow \mathbb {N}$, and $\mathbf {\alpha }$ a tuple of weights. If ${\mathbf {\alpha } \otimes f}$ is a natural weighted product, then we have $\langle f\rangle \ge \langle \mathbf {\alpha } \otimes f\rangle$.

Proof

Let $m = |\mathbf {\alpha }|$, $k_i = |\alpha _i| - 1$, and $\alpha _i = \langle a_{i,0}/d_i,a_{i,1}/d_i,\ldots ,a_{i,k_i-1}/d_i,b_i/d_i\rangle$ with $a_{i,j},d_i \in \mathbb {N}$ and $b_i \in \mathbb {Z}$ for all $i \in \mathbb {N}_{<m}$ and $j \in \mathbb {N}_{<k_i}$ (clearly weights can always be brought into this form).

We define $T = \langle Q,q_{m-1,k_{m-1}-1}^{0},\delta ,\lambda \rangle$ consisting of states $q_{i,j}^{h}$ for every $i \in \mathbb {N}_{<m}$, $j \in \mathbb {N}_{<k_i}$, and h such that $\min (0,b_i) \le h <d_i$. The superscript h ($\min (0,b)_i \le h <d_i$) in a state $q_{i,j}^h$ indicates the amount $h/d_i$ of zeros that still has to be consumed/produced. The transition and output functions $\langle \delta ,\lambda \rangle : Q \times \mathbf {2}\rightarrow Q \times \mathbf {2}^*$ of T are defined as follows; let $\mathrm {id_{\ge 0}}: \mathbb {Z}\rightarrow \mathbb {N}$ be defined by $\mathrm {id_{\ge 0}}(z) = z$ if $z \ge 0$ and $\mathrm {id_{\ge 0}}(z) = 0$ otherwise.

$$\begin{aligned} \langle \delta ,\lambda \rangle (q_{i,j}^{h},0)&= \langle q_{i,j}^{h'},0^e\rangle&\text {where } e = \left\lfloor {\mathrm {id_{\ge 0}}(h + a_{i,j})/d_i}\right\rfloor , h' = h + a_{i,j} - e d_i\\ \langle \delta ,\lambda \rangle (q_{i,j}^{h},1)&= \langle q_{i,j+1}^{h},\varepsilon \rangle&(j < k_i - 1) \\ \langle \delta ,\lambda \rangle (q_{i,k_i-1}^{h},1)&= \langle q_{i',0}^{h'},1 0^e\rangle&\text {where } e = \left\lfloor {\mathrm {id_{\ge 0}}(b_{i'})/d_{i'}}\right\rfloor , h' = b_{i'} - e d_{i'}\,, \end{aligned}$$

where $i' = i+1 \text {mod}{m}$. See [4] for the proof of $\langle f\rangle \ge _T \langle \mathbf {\alpha } \otimes f\rangle$.    $\square$

Definition 4.17

Let $f : \mathbb {N}\rightarrow \mathbb {N}$ be a function, and, for some $m > 0$, let $\mathbf {\alpha }$ be an m-tuple of weights such that $\mathbf {\alpha } \otimes f$ is a natural weighted product. Let $\mathbf {p}$ and $\mathbf {c}$  be m-tuples of finite words. We define the sequence $\varPhi (f,\mathbf {\alpha },\mathbf {p},\mathbf {c}) \in \mathbf {2}^{\mathbb {N}}$ by

$$\begin{aligned} \varPhi (f,\mathbf {\alpha },\mathbf {p},\mathbf {c}) = \prod _{i = 0}^{\infty } \prod _{j = 0}^{m-1} p_j \, c_j^{\varphi (i,j)}&\text {where}&\varphi (i,j) = (\mathbf {\alpha } \otimes f)(mi + j) \,. \end{aligned}$$

Note that $\langle f\rangle$ can also be cast into this notation: $\langle f\rangle = \varPhi (f,\langle \langle 1,0\rangle \rangle ,\langle 1\rangle ,\langle 0\rangle )$. For the following lemma we recall that for a tuple $\mathbf {a} = \langle a_0,a_1,\ldots ,a_{k-1}\rangle$, we write $\mathbf {a}'$ for the rotation $\langle a_1,\ldots ,a_{k-1},a_0\rangle$.

Lemma 4.18

Let f, $\mathbf {\alpha }$, $\mathbf {p}$, $\mathbf {c}$ be as in Definition 4.17. We have $\varPhi (f,\mathbf {\alpha },\mathbf {p},\mathbf {c}) = p_0 c_0^{\alpha _0 \cdot f} \cdot \varPhi (\mathcal {S}^{|\alpha _0|-1}(f),\mathbf {\alpha }',\mathbf {p}',\mathbf {c}')$.

Lemma 4.19

Let $f : \mathbb {N}\rightarrow \mathbb {N}$ be a spiralling function, and let $\sigma \in \mathbf {2}^{\mathbb {N}}$ be such that $\langle f\rangle \ge \sigma$ and $\sigma \not \in \varvec{0}$. Then there exist $n_0, m \in \mathbb {N}$, a word $w \in \mathbf {2}^*$, a tuple of weights $\mathbf {\alpha }$, and tuples of words $\mathbf {p}$ and $\mathbf {c}$ with $|\mathbf {\alpha }| = |\mathbf {p}| = |\mathbf {c}| = m > 0$ such that:

• (i) $\sigma = w \cdot \varPhi (\mathcal {S}^{n_0}(f),\mathbf {\alpha },\mathbf {p},\mathbf {c})$,

• (ii) $c_j^\omega \ne p_{j+1} c_{j+1}^\omega$ for every j with $0 \le j < m-1$, and $c_{m-1}^\omega \ne p_{0} c_{0}^\omega$, and

• (iii) $c_j \ne \varepsilon$, and $\alpha _j$ is non-constant, for all $j \in \mathbb {N}_{<m}$.

Proof

By Lemma 4.5, there exist $n_0, m, a_j, z \in \mathbb {N}$ ($j \in \mathbb {N}_{<m}$), $w \in \mathbf {2}^*$, and $\mathbf {p}, \mathbf {c} \in (\mathbf {2}^*)^m$ such that $\sigma = w \cdot \varPhi (\mathcal {S}^{n_0}(f),\mathbf {\alpha },\mathbf {p},\mathbf {c})$, where, for $j \in \mathbb {N}_{<m}$, $\alpha _j$ is defined by $\alpha _j = \langle \frac{1}{z},{-}\frac{a_j}{z}\rangle$.

We now repeatedly alter the tuples $\mathbf {\alpha }$, $\mathbf {p}$, $\mathbf {c}$ until conditions (ii) and (iii) are fulfilled while condition (i) is upheld. For this we let $n_0 \in \mathbb {N}$, $w \in \mathbf {2}^*$, $m \in \mathbb {N}$, $\mathbf {\alpha }$, $\mathbf {p}$, and $\mathbf {c}$ with $|\mathbf {\alpha }| = |\mathbf {p}| = |\mathbf {c}| = m$ be arbitrary such that (i) holds.

First note that, if $m = 1$ and condition (ii) or (iii) are violated, then $\sigma \in \varvec{0}$, contradicting the assumption.

In case (ii) does not hold, consider the smallest $h \in \mathbb {N}_{<m}$ such that $c_h^\omega = p_{h+1} c_{h+1}^\omega$ where addition in the subscripts is computed modulo m. We assume $h < m-1$; the case $h = m-1$ proceeds analogously, using Lemma 4.18. For $i \in \mathbb {N}$ and $j \in \mathbb {N}_{<m}$, we let $\varphi (i,j) = (\mathbf {\alpha } \otimes \mathcal {S}^{n_0}(f))(mi + j)$. By Lemma 4.10 there are integers $a,b \ge 0$ and a word $x \in \mathbf {2}^*$ such that $c_h^{\varphi (i,h)} p_{h+1} c_{h+1}^{\varphi (i,h+1)} = p_{h+1} x^{a \varphi (i,h) + b \varphi (i,h+1)}$ ($\star$). We now define a tuple of weights $\mathbf {\beta }$, and tuples of words $\mathbf {q}$ and $\mathbf {d}$, with $|\mathbf {\beta }| = |\mathbf {q}| = |\mathbf {d}| = m - 1$, as follows: Let $j \in \mathbb {N}_{<m-1}$. If $j < h$, then we define $q_j = p_j$, $d_j = c_j$, and $\beta _j = \alpha _j$. If $j > h$, we define $q_j = p_{j+1}$, $d_j = c_{j+1}$, and $\beta _j = \alpha _{j+1}$. If $j = h$, we define $q_j = p_h p_{h+1}$, $d_j = x$, and we let the weight $\beta _j$ be defined as follows: For $\alpha _h = \langle r_0,r_1,\ldots ,r_{k-1},e\rangle$ and $\alpha _{h+1} = \langle r'_0,r'_1,\ldots ,r'_{\ell -1},e'\rangle$, let $\beta _h = \langle a r_0, a r_1, \ldots , a r_{k-1}, b r'_0, b r'_1, \ldots , b r'_{\ell - 1}, a e + b e'\rangle$. By definition of $\mathbf {q}$, $\mathbf {d}$, and $\mathbf {\beta }$, to verify $\varPhi (\mathcal {S}^{n_0}(f),\mathbf {\alpha },\mathbf {p},\mathbf {c}) = \varPhi (\mathcal {S}^{n_0}(f),\mathbf {\beta },\mathbf {q},\mathbf {d})$, it suffices to check, for all $i \in \mathbb {N}$, $p_h c_h^{\varphi (i,h)} p_{h+1} c_{h+1}^{\varphi (i,h+1)} = q_h d_h^{\varphi '(i,h)}$; here, for $i \in \mathbb {N}$ and $j \in \{0,\ldots ,m-2\}$, $\varphi '(i,j)$ is defined by $\varphi '(i,j) = (\mathbf {\beta } \otimes \mathcal {S}^{n_0}(f))((m-1)i+j)$. Fix $i \in \mathbb {N}$. By Lemma 4.13 we have $\varphi (i,h) = \alpha _h \cdot \mathcal {S}^{t}(f)$ and $\varphi (i,h+1) = \alpha _{h+1} \cdot \mathcal {S}^{t + k}(f)$, for some $t \in \mathbb {N}$. Also we have $\varphi '(i,h) = \beta _h \cdot \mathcal {S}^{t'}(f)$ for some $t' \in \mathbb {N}$. By definition of $\mathbf {\beta }$ we obtain $t' = t$. It follows that $\varphi '(i,h) = a \cdot \varphi (i,h) + b \cdot \varphi (i,h+1)$, and we conclude by ($\star$). Repeat the procedure with $\mathbf {\beta }$, $\mathbf {q}$, $\mathbf {d}$.

For the case (iii) that does not hold we refer to the extended version [4].    $\square$

For the proof of the following theorem we allow for a more liberal version of transducers. Instead of input letters along the edges we now allow input words. Transitions of these transducers are of the form $q \mathop {\longrightarrow }\limits ^{\langle u,v\rangle |w} q'$. The idea is that this transition is taken if the automaton is in state q and the input word is of the form $uv\tau$. Then the automaton produces output w and switches to state $q'$, consuming u and continuing with $v\tau$.

Definition 4.20

An FST with look-ahead ($\text {FST}^{\star }$) is a tuple $T = \langle Q,q_0,D,\delta ,\lambda \rangle$ where Q is a finite set of states, $q_{0} \in Q$ is the initial state, the finite set $D \subseteq Q \times \mathbf {2}^{+} \times \mathbf {2}^{*}$ is the input domain of the transition function $\delta : D \rightarrow Q$, and the output function $\lambda : D \rightarrow \mathbf {2}^*$, satisfying the following condition: for all $q \in Q$, $u_1,u_2,v_1,v_2 \in \mathbf {2}^*$ if $u_1u_2$ is a prefix of $v_1v_2$ and $\langle q,u_1,u_2\rangle \in D$ and $\langle q,v_1,v_2\rangle \in D$, then $u_1 = v_1$ and $u_2 = v_2$.

We lift $\delta$ to a partial function $\delta ^\star : Q \times \mathbf {2}^* \rightharpoonup Q$ by $\delta ^\star (q,\varepsilon ) = q$ and

$$\begin{aligned} \delta ^\star (q,u_1u_2v)&= \delta ^\star (\delta (q,u_1,u_2),u_2v)&(\langle q,u_1,u_2\rangle \in D, v \in \mathbf {2}^*)\,. \end{aligned}$$

Similarly, we lift $\lambda$ to a partial function $\lambda ^\star : Q \times \mathbf {2}^\infty \rightharpoonup \mathbf {2}^\infty$ by $\lambda ^\star (q,\varepsilon ) = \varepsilon$ and

$$\begin{aligned} \lambda ^\star (q,u_1u_2v)&= \lambda (q,u_1,u_2) \cdot \lambda ^\star (\delta (q,u_1,u_2),u_2v)&(\langle q,u_1,u_2\rangle \in D, v \in \mathbf {2}^\infty )\,. \end{aligned}$$

The partial function $T : \mathbf {2}^\infty \rightharpoonup \mathbf {2}^\infty$ realised by the $\text {FST}^{\star }$ T is defined by $T(u) = \lambda ^\star (q_0,u)$, for all $u \in \mathbf {2}^\infty$.

These transducers can be simulated by FSTs.

Lemma 4.21

For every $\text {FST}^{\star }$ T there is an FST $T'$ such that for all $u \in \mathbf {2}^\infty$, $T'(u) = T(u)$ whenever T(u) is defined.

Theorem 4.22

Let $f : \mathbb {N}\rightarrow \mathbb {N}$ be spiralling, and $\sigma \in \mathbf {2}^{\mathbb {N}}$. Then $\langle f\rangle \ge \sigma$ if and only if $\sigma \equiv \langle \mathbf {\alpha } \otimes \mathcal {S}^{n_0}(f)\rangle$ for some integer $n_0 \ge 0$, and a tuple of weights $\mathbf {\alpha }$.

Proof

One direction is by Lemma 4.16. For the other, assume $\langle f\rangle \ge \sigma$. If $\sigma \in \varvec{0}$, then $\sigma \equiv \langle \langle \langle 0,0\rangle \rangle \otimes \mathcal {S}^{0}(f)\rangle = \langle n \mapsto 0\rangle = 1^\omega$. Thus let $\sigma \not \in \varvec{0}$. By Lemma 4.19 there exist $n_1, m \in \mathbb {N}$, $w \in \mathbf {2}^*$, $\mathbf {\alpha }$, $\mathbf {p}$ and $\mathbf {c}$ with $|\mathbf {\alpha }| = |\mathbf {p}| = |\mathbf {c}| = m > 0$ such that $\sigma = w \cdot \varPhi (\mathcal {S}^{n_1}(f),\mathbf {\alpha },\mathbf {p},\mathbf {c})$, and fulfilling the conditions (ii) and (iii) of Lemma 4.19. We abbreviate $g = \mathbf {\alpha } \otimes \mathcal {S}^{n_1}(f)$. We will show that $\sigma \equiv \langle g\rangle$.

By Lemma 4.15 we have that the function g is spiralling too.

By conditions (ii) and (iii), for every $j \in \mathbb {N}_{<m}$, there exists $t_j \in \mathbb {N}$ such that $c_j^\omega (t_j) \ne (p_{j+1}c_{j+1}^\omega )(t_j)$ (where addition is modulo m); let $t_j$ be minimal with this property.

For $j \in \mathbb {N}_{<m}$, let $\ell _j,\ell _j' \in \mathbb {N}$ be minimal such that $|c_j c_j^{\ell _j}| > t_j$ and $|p_{j+1} c_{j+1}^{\ell _j'}| > t_j$. Then by minimality of $t_j$ and $\ell _j$, we obtain

• (i) $c_j c_j^{\ell _j-1} \sqsubseteq p_{j+1} c_{j+1}^{\ell '_j} \tau$ for every $\tau \in \mathbf {2}^{\mathbb {N}}$, and

• (ii) $c_j c_j^{\ell _j} \not \sqsubseteq p_{j+1} c_{j+1}^{\ell '_j} \tau$ for every $\tau \in \mathbf {2}^{\mathbb {N}}$

(with again addition computed modulo m). From (i) we moreover obtain

• (iii) $c_j c_j^{\ell _j} \sqsubseteq c_j^{n} p_{j+1} c_{j+1}^{\ell '_j} \tau$ for every $n > 0$ and $\tau \in \mathbf {2}^{\mathbb {N}}$.

Next, we take a suffix $\sigma '$ of $\sigma$ such that every occurrence of a block $p_{j+1} c_{j+1}^{\varphi (i,j)}$ has as a prefix $p_{j+1} c_{j+1}^{\ell _j}$. Let $n_2 \in \mathbb {N}$ be such that for $g' = \mathcal {S}^{n_2 \cdot m}(g)$ we have that $g'(n) > \max \{t_j \mid j \in \mathbb {N}_{<m}\}$ for all $n \in \mathbb {N}$; the existence of such an $n_2$ follows from g being spiralling. To prove $\sigma \equiv \langle g\rangle$ it suffices to show $\sigma ' \equiv \langle g'\rangle$ where

$$\begin{aligned} \sigma '&= \prod _{i = n_2}^{\infty } \prod _{j=0}^{m-1} p_j c_j^{\varphi (i,j)} = \prod _{i = 0}^{\infty } \prod _{j=0}^{m-1} p_j c_j^{\varphi '(i,j)}&\langle g'\rangle&= \prod _{i = 0}^{\infty } \prod _{j=0}^{m-1} 1 0^{\varphi '(i,j)} \end{aligned}$$

where $\varphi (i,j) = g(mi + j)$, and $\varphi '(i,j) = g'(mi + j)$. Note that by the choice of $n_2$, we have $\varphi '(i,j+1) \ge \ell '_j$ for all $i \in \mathbb {N}$ and $j \in \mathbb {N}_{<m}$.

It is clear how to construct an FST that transduces $\langle g'\rangle$ to $\sigma '$. For $\sigma ' \ge \langle g'\rangle$, we define a $\text {FST}^{\star }$ $T = \langle Q,q_{m-1},D,\delta ,\lambda \rangle$, as follows, and apply Lemma 4.21. Let $Q = \{q_j \mid j \in \mathbb {N}_{<m}\}$ and $D = \{ \langle q_j,c_j,c_j^{\ell _j}\rangle \mid j \in \mathbb {N}_{<m}\} \cup \{ \langle q_j,p_{j+1},c_{j+1}^{\ell '_j}\rangle \mid j \in \mathbb {N}_{<m}\}$, and define $\delta ,\lambda$ by

$$\begin{aligned} \langle \delta ,\lambda \rangle (q_j,c_j,c_j^{\ell _j}) = \langle q_j,0\rangle \quad \quad \langle \delta ,\lambda \rangle (q_j,p_{j+1},c_{j+1}^{\ell _j'}) = \langle q_{j+1},1\rangle \,. \end{aligned}$$

We now argue that $\sigma ' \ge _T \langle g'\rangle$. This follows from the following facts:

• (a) $\lambda ^\star (q_j,p_{j+1}c^{\varphi '(i,j+1)} \tau ) = 1 \cdot \lambda ^\star (q_{j+1}, c^{\varphi '(i,j+1)} \tau )$,

• (b) $\lambda ^\star (q_j,c_j^{n}p_{j+1}c^{\varphi '(i,j+1)} \tau ) = 0 \cdot \lambda ^\star (q_{j+1}, c^{\varphi '(i,j+1)} \tau )$ for all $n > 0$, since by item (iii) we have $c_j c_j^{\ell _j} \sqsubseteq c_j^{n}p_{j+1}c^{\varphi '(i,j+1)} \tau$.    $\square$

Lemma 4.23

Let $f : \mathbb {N}\rightarrow \mathbb {N}$ be spiralling, and $\sigma \not \in \varvec{0}$ with $\langle f\rangle \ge \sigma$. Then we have $\sigma \ge \langle \langle \beta \rangle \otimes \mathcal {S}^{n_0}(f)\rangle$ for some integer $n_0 \ge 0$, and a non-constant weight $\beta$.

Theorem 4.24

There is a non-atom, non-zero degree $[\sigma ]$ that has no atom degree below it. Hence, non-zero transducts of $\sigma$ start an infinite descending chain.

Proof

We define the function $f : \mathbb {N}\rightarrow \mathbb {N}$ by $f(n) = 2^n$. We show that the degree $[\langle f\rangle ]$ has no atom degree below it. Let $\sigma \not \in \varvec{0}$ with $\langle f\rangle \ge \sigma$. By Lemma 4.23 there is a non-constant weight $\beta = \langle a_0,a_1,\ldots ,a_{k-1},b\rangle$ such that $\sigma \ge \langle g\rangle$ where $g = \langle \beta \rangle \otimes \mathcal {S}^{n_0}(f)$. Since $f(n) = 2^n$ it follows that

$$\begin{aligned} g(n) = b+\sum _{i =0}^{k-1} a_i 2^{n_0+nk+i} = b + 2^{nk}\sum _{i =0}^{k-1} a_i 2^{n_0 +i} = (g(0)-b) \cdot 2^{nk} + b \,. \end{aligned}$$

By Lemma 4.16 we have that $\langle g\rangle = \langle (g(0)-b) \cdot 2^{nk} + b\rangle \equiv \langle 2^{nk}\rangle$. Thus we have $\sigma \ge \langle 2^{nk}\rangle$. Also $\langle 2^{nk}\rangle \ge \langle 2^{2nk}\rangle$ holds by Lemma 4.2 (iv), and by Lemma 4.7 we conclude $\langle 2^{2nk}\rangle \not \ge \langle 2^{nk}\rangle$.    $\square$

5 Squares

In [1] it is shown that $[\langle n\rangle ]$ is an atom degree. One of the main questions of [1] is whether there exist other atom degrees. Here we show that also $[\langle n^2\rangle ]$ is an atom degree. The main tool is Theorem 4.22, the characterisation of transducts of spiralling sequences, which implies the following proposition.

Proposition 5.1

Let p(n) be a polynomial of degree k with non-negative integer coefficients, and let $\sigma$ be a transduct of $\langle p(n)\rangle$ with $\sigma \notin \varvec{0}$. Then $\sigma \ge \langle q(n)\rangle$ for some polynomial q(n) of degree k with non-negative integer coefficients.

Proof

By Lemma 4.23 it follows that $\sigma \ge \langle \langle \alpha \rangle \otimes \mathcal {S}^{n_0}(p)\rangle$ for some integer $n_0 \ge 0$, and a non-constant weight $\alpha = \langle a_{0},\ldots ,a_{k-1},b\rangle$. Let $h \in \mathbb {N}_{<k}$ be such that $a_{h} \ne 0$. Then we find $(\langle \alpha \rangle \otimes \mathcal {S}^{n_0}(p))(n) = b + \sum _{j=0}^{k-1} a_{j} \cdot p(n_0 + nk + j)$, which can easily be recognised to be a polynomial q(n) of degree k.    $\square$

Theorem 5.2

The degree $[\langle n^2\rangle ]$ is an atom.

Proof

Let $\sigma \in \mathbf {2}^{\mathbb {N}}$ be a transduct of $\langle n^2\rangle$ such that $\sigma$ is not ultimately periodic. By Proposition 5.1 there are integers $a > 0$, $b,c \ge 0$ such that $\sigma \ge \langle an^2 + bn + c\rangle$. We first assume $2a \ge b$. Abbreviate $f(n) = a n^2 + (2a+b)n$. The roman numbers below refer to Lemma 4.2. We derive

$$\begin{aligned} \langle a n^2 + bn + c\rangle&\equiv \langle a n^2 + bn\rangle&\text {by } \text {(iii)} \\&\equiv \langle a (n+1)^2 + b(n+1)\rangle&\text {by } \text {(ii)} \\&\equiv \langle f(n)\rangle&\text {by } \text {(iii)} \\&\ge \langle b(f(2n)) + (2a-b)(f(2n+1))\rangle&\text {by } \text {(v)} \\&\equiv \langle 8 a^2 n^2 + 16 a^2 n\rangle \equiv \langle 8 a^2 (n+1)^2\rangle&\text {by } \text {(iii)} \\&\equiv \langle (n+1)^2\rangle&\text {by } \text {(i)} \\&\equiv \langle n^2\rangle&\text {by } \text {(ii)} \,. \end{aligned}$$

If $2a < b$, choose d such that $2ad \ge b$. Then we have $\langle an^2 + bn\rangle \ge \langle ad^2n^2 + bdn\rangle$ by (iv), and we reason as above for $\langle a'n^2 + b'n\rangle$ with $a' = ad^2$ and $b' = bd$.

This shows that every non-ultimately periodic transduct of $\langle n^2\rangle$ can be transduced back to $\langle n^2\rangle$. Hence, the degree of $\langle n^2\rangle$ is an atom.    $\square$