Degrees of Infinite Words, Polynomials and Atoms

Abstract

Our objects of study are finite state transducers and their power for transforming infinite words. Infinite sequences of symbols are of paramount importance in a wide range of fields, from formal languages to pure mathematics and physics. While finite automata for recognising and transforming languages are well-understood, very little is known about the power of automata to transform infinite words.

We use methods from linear algebra and analysis to show that there is an infinite number of atoms in the transducer degrees, that is, minimal non-trivial degrees.

This research has been supported by the Academy of Finland under the grant 257857.

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.

1 Introduction

The transformation realised by finite state transducers induces a partial order of degrees of infinite words: for words $v,w \in \varDelta ^{\mathbb {N}}$, we write $v \ge w$ if v can be transformed into w by some finite state transducer. If $v \ge w$, then v can be thought of as at least as complex as w. This complexity comparison induces equivalence classes of words, called degrees, and a partial order on these degrees, that we call transducer degrees.

The ensuing hierarchy of degrees is analogous to the recursion theoretic degrees of unsolvability, also known as Turing degrees, where the transformational devices are Turing machines. The Turing degrees have been widely studied in the 60’s and 70’s. However, as a complexity measure, Turing machines are too strong: they trivialise the classification problem by identifying all computable infinite words. Finite state transducers give rise to a much more fine-grained hierarchy.

We are interested in the structural properties of the hierarchy of transducer degrees. In this paper, we investigate the existence of atom degrees. An atom degree is a minimal non-trivial degree, that is, a degree that is directly above the bottom degree without interpolant degree.

Our Contribution. In [4, 7] it has been proven that the degree of the words $\langle n\rangle$ and $\langle n^2\rangle$ are atoms. Surprisingly, we find that this does not hold for $\langle n^3\rangle$. In particular, we show that the degree of $\langle n^k\rangle$ is never an atom for $k \ge 3$ (see Theorem 22). On the other hand, we prove that for every $k > 0$, there exists a unique atom among the degrees of words $\langle p(n)\rangle$ for polynomials p(n) of order k (see Theorem 31). (To avoid confusion between two meanings of degrees, namely degrees of words and degrees of polynomials, we speak of the order of a polynomial.) We moreover show that this atom is the infimum of all degrees of polynomials p(n) of order k.

Further Related Work. The paper [11] discusses complexity hierarchies derived from notions of reduction. The paper [9] gives an overview over the subject of transducer degrees and compares them with the well-known Turing degrees [12, 15]. Restricting the transducers to output precisely one letter in each step, we arrive at Mealy machines. These gives rise to an analogous hierarchy of Mealy degrees that has been studied in [2, 13]. The structural properties of this hierarchy are very different from the transducer degrees, see further [9].

2 Preliminaries

Let $\varSigma$ be an alphabet. We write $\varepsilon$ for the empty word, $\varSigma ^*$ for the set of finite words over $\varSigma$, and let $\varSigma ^+ = \varSigma ^*{\setminus }\{\varepsilon \}$. The set of infinite words over $\varSigma$ is $\varSigma ^{\mathbb {N}} = \{ \sigma \mid \sigma : \mathbb {N}\rightarrow \varSigma \}$ and we let $\varSigma ^\infty = \varSigma ^* \cup \varSigma ^{\mathbb {N}}$. Let $u,w \in \varSigma ^\infty$. Then u is called a prefix of w, denoted $u \sqsubseteq w$, if $u = w$ or there exists $u' \in \varSigma ^\infty$ such that $uu' = w$.

A sequential finite state transducer (FST) [1, 14], a.k.a. deterministic generalised sequential machine (DGSM), is a finite automaton with input letters and finite output words along the edges.

Definition 1

A sequential finite state transducer $A = \langle \varSigma ,\varGamma ,Q,q_{0},\delta ,\lambda \rangle$ consists of a finite input alphabet $\varSigma$, a finite output alphabet $\varGamma$, a finite set of states $Q$, an initial state $q_{0} \in Q$, a transition function ${\delta } : {Q\times \varSigma \rightarrow Q}$, and an output function ${\lambda } : {Q\times \varSigma \rightarrow \varGamma ^*}$. Whenever the alphabets $\varSigma$ and $\varGamma$ are clear from the context, we write $A = \langle Q,q_{0},\delta ,\lambda \rangle$.

We only consider sequential transducers and will simply speak of finite state transducers henceforth.

Definition 2

Let $A = \langle \varSigma ,\varGamma ,Q,q_{0},\delta ,\lambda \rangle$ be a finite state transducer. We homomorphically extend the transition function $\delta$ to $Q \times \varSigma ^* \rightarrow Q$ by: for $q \in Q$, $a \in \varSigma$, $u \in \varSigma ^*$ let $\delta (q,\varepsilon ) = q$ and $\delta (q,au) = \delta (\delta (q,a),u)$. We extend the output function $\lambda$ to $Q \times \varSigma ^\infty \rightarrow \varGamma ^\infty$ by: for $q \in Q$, $a \in \varSigma$, $u \in \varSigma ^\infty$, let $\lambda (q,\varepsilon ) = \varepsilon$ and $\lambda (q,au) = \lambda (q,a) \cdot \lambda (\delta (q,a),u)$.

We note that finite state transducers can be viewed as productive term rewrite systems [6] and the transduction of infinite words as infinitary rewriting [5].

3 Transducer Degrees

In this section, we explain how finite state transducers give rise to a hierarchy of degrees of infinite words, called transducer degrees. First, we formally introduce the transducibility relation $\ge$ on words as realised by finite state transducers.

Definition 3

Let $w\in \varSigma ^{\mathbb {N}}$, $u\in \varGamma ^{\mathbb {N}}$ for finite alphabets $\varSigma$, $\varGamma$. Let $A = \langle \varSigma ,\varGamma ,Q,q_{0},\delta ,\lambda \rangle$ be a finite state transducer. We write $w\ge _{\text {A}} u$ if $u= \lambda (q_0,w)$. We write $w\ge _{\text {}}u$, and say that u is a transduct of w, if there exists a finite state transducer A such that $w\ge _{\text {A}} u$.

Note that the transducibility relation $\ge _{\text {}}$ is a pre-order. It thus induces a partial order of ‘degrees’, the equivalence classes with respect to $\ge _{\text {}} \cap \le _{\text {}}$. We denote equivalence using $\equiv$. It is not difficult to see that every word over a finite alphabet is equivalent to a word over the alphabet $\mathbf {2}= \{\,0,1\,\}$. For the study of transducer degrees it suffices therefore to consider words over the latter alphabet.

Definition 4

Define the equivalence relation $\equiv \;=\; (\ge _{\text {}} \cap \le _{\text {}})$. The (transducer) degree $w^{{\equiv }}$ of an infinite word $w$ is the equivalence class of $w$ with respect to $\equiv$, that is, $w^{{\equiv }} = \{u\in \mathbf {2}^{\mathbb {N}}\mid w\equiv u\}$. We write $\mathbf {2}^{\mathbb {N}}/_{{\equiv }}$ to denote the set of degrees $\{w^{{\equiv }} \mid w\in \mathbf {2}^{\mathbb {N}}\}$.

The transducer degrees form the partial order $\langle \mathbf {2}^{\mathbb {N}}/_{{\equiv }},\ge _{\text {}}\rangle$ ¹ induced by the pre-order $\ge _{\text {}}$ on $\mathbf {2}^{\mathbb {N}}$, that is, for words $w,u\in \mathbf {2}^{\mathbb {N}}$ we have $w^{{\equiv }} \ge _{\text {}}u^{{\equiv }} \iff w\ge _{\text {}}u$.

The bottom degree $\varvec{0}$ of the transducer degrees is the least degree of the hierarchy, that is, the unique degree $\mathfrak {a} \in \mathbf {2}^{\mathbb {N}}/_{{\equiv }}$ such that $\mathfrak {a} \le _{\text {}}\mathfrak {b}$ for every $\mathfrak {b} \in \mathbf {2}^{\mathbb {N}}/_{{\equiv }}$. The bottom degree $\varvec{0}$ consists of the ultimately periodic words, that is, words of the form $uvvv\cdots$ for finite words u, v where $v \ne \varepsilon$.

An atom is a degree that has only $\varvec{0}$ below itself.

Definition 5

An atom is a minimal non-bottom degree, that is, a degree $\mathfrak {a} \in \mathbf {2}^{\mathbb {N}}/_{{\equiv }}$ such that $\varvec{0}<_{\text {}}\mathfrak {a}$ and there exists no $\mathfrak {b} \in \mathbf {2}^{\mathbb {N}}/_{{\equiv }}$ with $\varvec{0}<_{\text {}}\mathfrak {b} <_{\text {}}\mathfrak {a}$.

4 Spiralling Words

We now consider spiralling words over the alphabet $\mathbf {2}= \{0,1\}$ for which the distance of consecutive 1’s in the word grows to infinity. We additionally require that the sequence of distances of consecutive 1’s is ultimately periodic modulo every natural number. The class of spiralling words allows for a characterisation of their transducts in terms of weighted products.

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

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

We write $\langle f(n)\rangle$ as shorthand for $\langle n \mapsto f(n)\rangle$.

Definition 6

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) \bmod m$ is ultimately periodic.

A word $\langle f\rangle$ is called spiralling whenever f is spiralling.

For example, $\langle p(n)\rangle$ is spiralling for every polynomial p(n) with natural numbers as coefficients. Spiralling functions are called ‘cyclically ultimately periodic’ in the literature [3]. For a tuple $\varvec{\alpha } = \langle \alpha _0,\ldots ,\alpha _{m}\rangle$, we define

• the length $|\varvec{\alpha }| = m+1$, and

• its rotation by $\varvec{\alpha }' = \langle \alpha _1,\ldots ,\alpha _{m},\alpha _0\rangle$.

Let A be a set and $f : \mathbb {N}\rightarrow A$ a function. We write $\mathcal {S}^{k}(f)$ for the k-th shift of f defined by $\mathcal {S}^{k}(f)(n) = f(n+k)$.

We use ‘weights’ to represent linear functions.

Definition 7

A weight $\varvec{\alpha }$ is a tuple $\langle a_0,\ldots ,a_{k-1},b\rangle \in \mathbb {Q}^{k+1}$ of rational numbers such that $k \in \mathbb {N}$ and $a_0,\ldots ,a_{k-1} \ge 0$. The weight $\varvec{\alpha }$ is called

• non-constant if $a_i \ne 0$ for some $i < k$, else constant,

• strongly non-constant if $a_i,a_j \ne 0$ for some $i< j < k$.

Now, let us also consider a tuple of tuples. For a tuple $\varvec{\alpha } = \langle \varvec{\alpha _0},\ldots ,\varvec{\alpha _{m-1}}\rangle$ of weights we define $||\varvec{\alpha }|| = \textstyle \sum _{i = 0}^{m-1} (\,|\varvec{\alpha _i}| - 1\,) \;.$

Definition 8

Let $f : \mathbb {N}\rightarrow \mathbb {Q}$ be a function. For a weight $\varvec{\alpha } = \langle a_0,\ldots ,a_{k-1},b\rangle$ we define $\varvec{\alpha } \cdot f \in \mathbb {Q}$ by $\varvec{\alpha } \cdot f \;=\; a_0 f(0) + a_1 f(1) + \cdots + a_{k-1} f(k-1) + b \,.$ For a tuple of weights $\varvec{\alpha } = \langle \varvec{\alpha _0},\varvec{\alpha _1},\ldots , \varvec{\alpha _{m-1}}\rangle$, we define the weighted product $\varvec{\alpha } \otimes f : \mathbb {N}\rightarrow \mathbb {Q}$ by induction on n:

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

We say that $\varvec{\alpha } \otimes f$ is a natural weighted product if $(\varvec{\alpha } \otimes f)(n) \in \mathbb {N}$ for all $n \in \mathbb {N}$.

Weighted products are easiest understood by an example.

Example 9

Let $f(n) = n^2$ be a function and $\varvec{\alpha } = \langle \varvec{\alpha _1},\varvec{\alpha _2}\rangle$ a tuple of weights with $\varvec{\alpha _1} = \langle 1,2,3,4\rangle$, $\varvec{\alpha _2} = \langle 0,1,1\rangle$. Then the weighted product $\varvec{\alpha } \otimes f$ can be visualised as follows

Intuitively, the weight $\varvec{\alpha _1} = \langle 1,2,3,4\rangle$ means that 3 consecutive entries are added while being multiplied by 1, 2 and 3, respectively, and 4 is added to the result.

We introduce a few operations on weights. We define scalar multiplication of weights in the obvious way. We also introduce a multiplication $\odot$ that affects only the last entry of weights (the constant term).

Definition 10

Let $c \in \mathbb {Q}_{\ge 0}$, $\varvec{\alpha } = \langle a_{0},\ldots ,a_{\ell -1},b\rangle$ a weight, $\varvec{\beta } = \langle \varvec{\beta _0},\ldots ,\varvec{\beta _{m-1}}\rangle$ a tuple of weights. We define

$$\begin{aligned} c\varvec{\alpha }&= \langle ca_0,\ldots ,ca_{\ell -1},cb\rangle&\varvec{\alpha } \odot c&= \langle a_0,\ldots ,a_{\ell -1},bc\rangle \\ c\varvec{\beta }&= \langle c\varvec{\beta _0},\ldots ,c\varvec{\beta _{m-1}}\rangle&\varvec{\beta } \odot c&= \langle \varvec{\beta _0} \odot c,\ldots ,\varvec{\beta _{m-1}} \odot c\rangle \end{aligned}$$

The following lemma follows directly from the definitions.

Lemma 11

Let $c \in \mathbb {Q}_{\ge 0}$, $\varvec{\alpha }$ a tuple of weights, and $f : \mathbb {N}\rightarrow \mathbb {Q}$ a function. Then $c(\varvec{\alpha } \otimes f) = (c\varvec{\alpha }) \otimes f = (\varvec{\alpha } \odot c) \otimes (cf)$.    $\square$

It is straightforward to define a composition of tuples of weights such that $\varvec{\beta } \otimes (\varvec{\alpha } \otimes f) = (\varvec{\beta } \otimes \varvec{\alpha }) \otimes f$ for every function $f : \mathbb {N}\rightarrow \mathbb {Q}$. Note that $\varvec{\alpha } \otimes f$ is already defined. For the precise definition of $\varvec{\beta } \otimes \varvec{\alpha }$, we refer to [8]. It involves many details whose explicitation would not be illuminating. We will employ the following two properties of composition.

Lemma 12

Let $\varvec{\alpha },\varvec{\beta }$ be tuples of weights. Then we have that $\varvec{\beta } \otimes (\varvec{\alpha } \otimes f) = (\varvec{\beta } \otimes \varvec{\alpha }) \otimes f$ for every function $f : \mathbb {N}\rightarrow \mathbb {Q}$.    $\square$

Lemma 13

Let $\varvec{\alpha }$ be tuple of weights, and $\varvec{\beta }$ a tuple of strongly non-constant weights. Then $\varvec{\alpha } \otimes \varvec{\beta }$ is of the form $\langle \gamma _0,\ldots ,\gamma _{k-1}\rangle$ such that for every $i \in \mathbb {N}_{<k}$, the weight $\gamma _i$ is either constant or strongly non-constant.    $\square$

We need a few results on weighted products from [4].

Lemma 14

([4]). Let $f : \mathbb {N}\rightarrow \mathbb {N}$, and $\varvec{\alpha }$ a tuple of weights. If ${\varvec{\alpha } \otimes f}$ is a natural weighted product (i.e. $\forall n \in \mathbb {N}.\; (\varvec{\alpha } \otimes f)(n) \in \mathbb {N}$), then $\langle f\rangle \ge _{\text {}}\langle \varvec{\alpha } \otimes f\rangle$.    $\square$

For the proof of Theorem 21, below, we use the following auxiliary lemma. The lemma gives a detailed structural analysis, elaborated and explained in [4], of the transducts of a spiralling word $\langle f\rangle$.

Lemma 15

([4]). 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 _{\text {}}\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 $\varvec{\alpha }$, and tuples of finite words $\varvec{p}$ and $\varvec{c}$ with $|\varvec{\alpha }| = |\varvec{p}| = |\varvec{c}| = m > 0$ such that $\sigma = w \cdot \prod _{i = 0}^{\infty } \prod _{j = 0}^{m-1} p_j \, c_j^{\varphi (i,j)}$ where $\varphi (i,j) = (\varvec{\alpha } \otimes \mathcal {S}^{n_0}(f))(mi + j)$, and

• (i) $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

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

Example 16

We continue Example 9. We have $\alpha = \langle \alpha _0,\alpha _1\rangle$. Accordingly, we have prefixes $p_0,p_1 \in \mathbf {2}^*$ and cycles $c_0,c_1 \in \mathbf {2}^*$. Then the transduct $\sigma$ in Lemma 15, defined by the double product, can be derived as follows:

The infinite word $\sigma$ is the infinite concatenation of w followed by alternating $p_0 c_0^{e_0}$ and $p_1 c_1^{e_1}$, where the exponents $e_0$ and $e_1$ are the result of applying weights $\alpha _0$ and $\alpha _1$, respectively.

The following theorem characterises the transducts of spiralling words up to equivalence ($\equiv$).

Theorem 17

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

Roughly speaking, the next proposition states that polynomials of order k are closed under transduction.

Proposition 18

([4]). Let p(n) be a polynomial of order 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 _{\text {}}\langle q(n)\rangle$ for some polynomial q(n) of order k with non-negative integer coefficients.

5 The Degree of $\langle n^k\rangle$ is Not an Atom for $k \ge 3$

We show that the degree of $\langle n^k\rangle$ is not an atom for $k \ge 3$. For this purpose, we prove a strengthening of Theorem 17, a lemma on weighted products of strongly non-constant weights, and we employ the power mean inequality.

First, we recall the power mean inequality [10].

Definition 19

For $p \in \mathbb {R}$, the weighted power mean $M_p(\varvec{x})$ of $\varvec{x} = \langle x_1,x_2,\ldots ,x_n\rangle \in \mathbb {R}_{>0}^n$ with respect to $\varvec{w} = \langle w_1,w_2,\ldots ,w_n\rangle \in \mathbb {R}_{>0}^n$ with $\sum _{i = 1}^n w_i = 1$ is

$$\begin{aligned} M_{\varvec{w},0}(\varvec{x})&= \textstyle \prod _{i=1}^{n} x_i^{w_i}&M_{\varvec{w},p}(\varvec{x})&= (\textstyle \sum _{i=1}^{n} w_i x_i^p)^{1/p} \,. \end{aligned}$$

Proposition 20

(Power mean inequality). For all $p,q\in \mathbb {R}$, $\varvec{x},\varvec{w} \in \mathbb {R}_{>0}^n$:

$$\begin{aligned}\begin{gathered} p < q \implies M_{\varvec{w},p}(\varvec{x}) \le M_{\varvec{w},q}(\varvec{x})\\ ( p = q \vee x_1 = x_2 = \cdots = x_n ) \iff M_{\varvec{w},p}(\varvec{x}) = M_{\varvec{w},q}(\varvec{x}) \,. \end{gathered}\end{aligned}$$

Theorem 17 characterises transducts of spiralling sequences only up to equivalence. This makes it difficult to employ the theorem for proving non-transducibility. We improve the characterisation for the case of spiralling transducts as follows.

Theorem 21

Let $f,g : \mathbb {N}\rightarrow \mathbb {N}$ be spiralling functions. Then $\langle g\rangle \ge _{\text {}}\langle f\rangle$ if and only if some shift of f is a weighted product of a shift of g, that is:

$$\begin{aligned} \mathcal {S}^{n_0}(f) = \varvec{\alpha } \otimes \mathcal {S}^{m_0}(g) \end{aligned}$$

for some $n_0, m_0 \in \mathbb {N}$ and a tuple of weights $\varvec{\alpha }$.

Theorem 21 is a strengthening of Theorem 17 in the sense that the characterisation uses equality ($=$ and shifts) instead of equivalence ($\equiv$). We will employ the gained precision to show that certain spiralling transducts of $\langle n^k\rangle$ cannot be transduced back to $\langle n^k\rangle$, and conclude that $\langle n^k\rangle$ is not an atom for $k \ge 3$. See further Theorem 22. Note, however, that Theorem 21 only characterises spiralling transducts whereas Theorem 17 characterises all transducts.

Proof

(Theorem 21 ). For the direction ‘$\Leftarrow$’, assume that $\mathcal {S}^{n_0}(f) = \varvec{\alpha } \otimes \mathcal {S}^{m_0}(g)$. Then we have $\langle g\rangle \equiv \langle \mathcal {S}^{m_0}(g)\rangle \ge _{\text {}}\langle \varvec{\alpha } \otimes \mathcal {S}^{m_0}(g)\rangle = \langle \mathcal {S}^{n_0}(f)\rangle \equiv \langle f\rangle$ by invariance under shifts and by Lemma 14.

For the direction ‘$\Rightarrow$’, assume that $\langle g\rangle \ge _{\text {}}\langle f\rangle$. Then by Lemma 15 there exist $m_0,m \in \mathbb {N}$, $w \in \mathbf {2}^*$, $\varvec{\alpha }$, $\varvec{p}$ and $\varvec{c}$ with $|\varvec{\alpha }| = |\varvec{p}| = |\varvec{c}| = m > 0$ such that:

$$\begin{aligned} \langle f\rangle = \textstyle w \cdot \prod _{i = 0}^{\infty } \prod _{j = 0}^{m-1} p_j \, c_j^{\varphi (i,j)} \end{aligned}$$

(1)

where $\varphi (i,j) = (\varvec{\alpha } \otimes \mathcal {S}^{m_0}(g))(mi + j)$ such that the conditions (i) and (ii) of Lemma 15 are fulfilled.

Note that, as $\lim _{n\rightarrow \infty } f(n) = \infty$, the distance of ones in the sequence $\langle g\rangle$ tends to infinity. For every $j \in \mathbb {N}_{<m}$, the word $p_j$ occurs infinitely often in $\langle f\rangle$ by (1), and hence $p_j$ can contain at most one occurrence of the symbol 1.

By condition (ii), we have for every $j \in \mathbb {N}_{<m}$ that $c_j \ne \varepsilon$, and the weight $\varvec{\alpha _j}$ is not constant. As $\lim _{n\rightarrow \infty } g(n) = \infty$, it follows that $c_j^2$ appears infinitely often in $\langle f\rangle$ by (1). Hence $c_j$ consists only of 0’s, that is, $c_j \in \{0\}^+$ for every $j \in \mathbb {N}_{<m}$.

By condition (i) we never have $c_j^\omega = p_{j+1} c_{j+1}^\omega$ for $j \in \mathbb {N}_{<m}$ (where addition is modulo m). As $c_j^\omega = 0^\omega$ and $p_{j+1} 0^\omega = p_{j+1} c_{j+1}^\omega$, we obtain that $p_{j+1}$ must contain a 1. Hence, for every $k \in \mathbb {N}_{<m}$, the word $p_j$ contains precisely one 1.

Finally, we apply the following transformations to ensure $p_j = 1$ and $c_j = 0$ for every $j \in \mathbb {N}_{<m}$:

• (i) For every $j \in \mathbb {N}_{<m}$ such that $c_j = 0^h$ for some $h > 1$, we set $c_j = 0$ and replace the weight $\varvec{\alpha _j}$ in $\varvec{\alpha }$ by $h\varvec{\alpha _j}$.

• (ii) For every $j \in \mathbb {N}_{<m}$ such that $p_j = 0^h 1 0^\ell$ for some $h \ge 1$ or $\ell \ge 1$, we set $p_j = 1$ and replace the weight $\varvec{\alpha _j}$ in $\varvec{\alpha }$ by $(\varvec{\alpha _j}+\ell )$ and the weight $\varvec{\alpha _{j-1}}$ by $(\varvec{\alpha _{j-1}} + h)$. Here, for a weight $\varvec{\gamma } = \langle x_0,\ldots ,x_{\ell -1},y\rangle$ and $z \in \mathbb {Q}$, we write $\varvec{\gamma } + z$ for the weight $\langle x_0,\ldots ,x_{\ell -1},y+z\rangle$. If $j = 0$, we moreover append $0^h$ to the word w.

Note that both transformations leave Eq. (1) valid, they do not change the result of the double product.

Thus we now have $p_j = 1$ and $c_j = 0$ for every $j \in \mathbb {N}_{<m}$. It follows from (1) that $\langle f\rangle = w \langle \varvec{\alpha } \otimes \mathcal {S}^{m_0}(g)\rangle$. Hence $\mathcal {S}^{n_0}(f) = \varvec{\alpha } \otimes \mathcal {S}^{m_0}(g)$ for some $n_0\in \mathbb {N}$.    $\square$

Theorem 22

For $k \ge 3$, the degree of $\langle n^k\rangle$ is not an atom.

Proof

Define $f : \mathbb {N}\rightarrow \mathbb {N}$ by $f(n) = n^k$. We have $\langle f\rangle \ge _{\text {}}\langle g\rangle$ where $g : \mathbb {N}\rightarrow \mathbb {N}$ is defined by $g(n) = (2n)^k + (2n+1)^k$. Assume that we had $\langle g\rangle \ge _{\text {}}\langle f\rangle$. Then, by Theorem 21 we have $\mathcal {S}^{n_0}(f) = \varvec{\alpha } \otimes \mathcal {S}^{m_0}(g)$ for some $n_0, m_0 \in \mathbb {N}$ and a tuple of weights $\varvec{\alpha }$. Note that $g = \langle \langle 1,1,0\rangle \rangle \otimes f$ and

$$\begin{aligned} \mathcal {S}^{n_0}(f)&= \varvec{\alpha } \otimes \mathcal {S}^{m_0}(\langle \langle 1,1,0\rangle \rangle \otimes f) \\&= \varvec{\alpha } \otimes (\langle \langle 1,1,0\rangle \rangle \otimes \mathcal {S}^{2 m_0}(f)) = \varvec{\beta } \otimes \mathcal {S}^{2 m_0}(f) \end{aligned}$$

where $\varvec{\beta } = \varvec{\alpha } \otimes \langle \langle 1,1,0\rangle \rangle$. By Lemma 13 every weight in $\varvec{\beta }$ is either constant or strongly non-constant. As $\mathcal {S}^{n_0}(f)$ is strictly increasing (and hence contains no constant subsequence), each weight in $\varvec{\beta }$ must be strongly non-constant.

Let $\varvec{\beta } = \langle \varvec{\beta _0},\ldots ,\varvec{\beta _{\ell -1}}\rangle$. For every $n \in \mathbb {N}$ we have:

$$\begin{aligned} \begin{aligned} \mathcal {S}^{n_0}(f)(\ell n)&= (\varvec{\beta } \otimes \mathcal {S}^{2 m_0}(f))(\ell n) = \varvec{\beta _0} \cdot \mathcal {S}^{2 m_0 + ||\varvec{\beta }||\cdot n}(f)\;. \end{aligned} \end{aligned}$$

(2)

Then we have

$$\begin{aligned} \mathcal {S}^{n_0}(f)(\ell n)&= (n_0 + \ell n)^k \nonumber = \textstyle \sum _{i=0}^{k} \left( {\begin{array}{c}k\\ i\end{array}}\right) n_0^i \ell ^{k-i}n^{k-i} \nonumber \\&= \ell ^k n^k + k n_0 \ell ^{k-1} n^{k-1} + \cdots + k n_0^{k-1} \ell n + n_0^k \;. \end{aligned}$$

(3)

Let $\varvec{\beta _0} = \langle a_0,a_1,\ldots ,a_{h-1},b\rangle$. We define $c_i = a_i ||\varvec{\beta }||^k$ and $d_i = (2m_0 + i)/ ||\varvec{\beta }||$. We obtain

$$\begin{aligned} \ \varvec{\beta _0} \cdot \mathcal {S}^{2 m_0 + ||\varvec{\beta }||\cdot n}(f) \nonumber =&\ b + \textstyle \sum _{i = 0}^{h-1} a_i f(2 m_0 + ||\varvec{\beta }||\cdot n + i) \nonumber \\ =&\ b + \textstyle \sum _{i = 0}^{h-1} a_i f(||\varvec{\beta }||(n + \frac{2m_0+i}{||\varvec{\beta }||})) \nonumber \\ =&\ b + \textstyle \sum _{i = 0}^{h-1} a_i ||\varvec{\beta }||^k(n + d_i)^k = b + \sum _{i = 0}^{h-1} c_i (n + d_i)^k \nonumber \\ =&\ b + \textstyle \sum _{i = 0}^{h-1} c_i (n^k + k d_i n^{k-1} + \cdots + k d_i^{k-1} n + d_i^k) \;. \end{aligned}$$

(4)

Recall Eq. (2). Comparing the coefficients of $n^k$, $n^{k-1}$ and n in (3) and (4) we obtain

$$\begin{aligned} \ell ^k&= \sum _{i = 0}^{h-1} c_i&kn_0 \ell ^{k-1}&= \sum _{i = 0}^{h-1} c_i k d_i&kn_0^{k-1} \ell&= \sum _{i = 0}^{h-1} c_i k d_i^{k-1} \,\text {, and hence} \\ 1&= \sum _{i = 0}^{h-1} \frac{c_i}{\ell ^k}&\frac{n_0}{\ell }&= \sum _{i = 0}^{h-1} \frac{c_i}{\ell ^{k}} d_i&\frac{n_0^{k-1}}{\ell ^{k-1}}&= \sum _{i = 0}^{h-1} \frac{c_i}{\ell ^{k}} d_i^{k-1} \,. \end{aligned}$$

This is in contradiction with the weighted power means inequality (Proposition 20). Clearly all $d_i$ are distinct, and, as a consequence of $\varvec{\beta _0}$ being strongly non-constant, there are at least two $i \in \mathbb {N}_{<h}$ for which $c_i \ne 0$. Thus our assumption $\langle g\rangle \ge _{\text {}}\langle f\rangle$ must have been wrong. Hence the degree of $\langle n^k\rangle$ is not an atom.   $\square$

6 Atoms of Every Polynomial Order

In the previous section, we have seen that $\langle n^k\rangle$ is not an atom for $k \ge 3$. In this section, we show that for every order $k \in \mathbb {N}$ there exists a polynomial p(n) of order k such that the degree of the word $\langle p(n)\rangle$ is an atom. As a consequence, there are at least $\aleph _0$ atoms in the transducer degrees.

As we have seen in the proof of Theorem 22, whenever $k \ge 3$, we have that $\langle n^k\rangle \ge _{\text {}}\langle g(n)\rangle$, but not $\langle g(n)\rangle \ge _{\text {}}\langle n^k\rangle$ for $g(n) = (2n)^k + (2n+1)^k$. Thus there exist polynomials p(n) of order k for which $\langle p(n)\rangle$ cannot be transduced to $\langle n^k\rangle$. However, the key observation underlying the construction in this section is the following: Although we may not be able to reach $\langle n^k\rangle$ from $\langle p(n)\rangle$, we can get arbitrarily close (Lemma 25, below). This enables us to employ the concept of continuity.

In order to have continuous functions over the space of polynomials to allow limit constructions, we now permit rational coefficients. For $k \in \mathbb {N}$, let $\mathfrak {Q}_k$ be the set of polynomials of order k with non-negative rational coefficients. We also use polynomials in $\mathfrak {Q}_k$ to denote spiralling sequences. However, we need to give meaning to $\langle q(n)\rangle$ for the case that the block sizes q(n) are not natural numbers. For this purpose, we make use of the fact that the degree of a word $\langle f(n)\rangle$ is invariant under multiplication of the block sizes by a constant, as is easy to see. More precisely, for $f : \mathbb {N}\rightarrow \mathbb {N}$, we have $\langle f(n)\rangle \equiv \langle d \cdot f(n)\rangle$ for every $d \in \mathbb {N}$ with $d \ge 1$. So to give meaning to $\langle q(n)\rangle$, we multiply the polynomial by the least natural number $d > 0$ such that $d \cdot q(n)$ is a natural number for every $n\in \mathbb {N}$.

Definition 23

We call a function $f : \mathbb {N}\rightarrow \mathbb {Q}$ naturalisable if there exists a natural number $d \ge 1$ such that for all $n \in \mathbb {N}$ we have $(d \cdot f(n)) \in \mathbb {N}$.

For naturalisable $f : \mathbb {N}\rightarrow \mathbb {Q}$ we define $\langle f\rangle \;=\; \langle d\cdot f\rangle$ where $d \in \mathbb {N}$ is the least number such that $d \ge 1$ where for all $n \in \mathbb {N}$ we have $(d \cdot f(n)) \in \mathbb {N}$. (Note that, for $f : \mathbb {N}\rightarrow \mathbb {N}$, $\langle f(n)\rangle$ has been defined in Sect. 4.)

Observe that every $q(n) \in \mathfrak {Q}_k$ is naturalisable (multiply by the least common denominator of the coefficients). Also, naturalisable functions are preserved under weighted products.

Now, Lemma 14 can be generalised as follows. There is no longer need to require that the weighted product is natural. All weighted products of naturalisable functions can be realised by finite state transducers.

Lemma 24

Let $f : \mathbb {N}\rightarrow \mathbb {Q}$ be naturalisable, and $\varvec{\alpha }$ a tuple of weights. Then $\varvec{\alpha } \otimes f$ is naturalisable and $\langle f\rangle \ge _{\text {}}\langle \varvec{\alpha } \otimes f\rangle$.

Proof

Let $\varvec{\alpha } = \langle \varvec{\alpha _0},\ldots ,\varvec{\alpha _{m-1}}\rangle$ for some $m \ge 1$. Let $c \in \mathbb {N}$ with $c \ge 1$ be minimal such that all entries of $c\varvec{\alpha }$ are natural numbers. Let $d \in \mathbb {N}$ with $d \ge 1$ be the least natural number such that $\forall n \in \mathbb {N}\;(d \cdot f(n)) \in \mathbb {N}$.

Then we obtain $((dc\varvec{\alpha }) \otimes f)(n) \in \mathbb {N}$ for ever $n\in \mathbb {N}$. By the definition of weighted products it follows immediately that $(dc\varvec{\alpha }) \otimes f = dc(\varvec{\alpha } \otimes f)$, and hence $\varvec{\alpha } \otimes f$ is naturalisable. Let $e \in \mathbb {N}$ with $e \ge 1$ be the least natural number such that $\forall n \in \mathbb {N}\;(e \cdot (\varvec{\alpha } \otimes f)(n)) \in \mathbb {N}$.

We have the following transduction

This concludes the proof.    $\square$

The following lemma states that every word $\langle q(n)\rangle$, for a polynomial $q(n) \in \mathfrak {Q}_k$ of order k, can be transduced arbitrarily close to $\langle n^k\rangle$.

Lemma 25

Let $k \ge 1$ and let $q(n) \in \mathfrak {Q}_k$ be a polynomial of order k. For every $\varepsilon > 0$ we have $\langle q(n)\rangle \ge _{\text {}}\langle n^k + b_{k-1} n^{k-1} + \cdots + b_1 n\rangle$ for some rational coefficients $0 \le b_{k-1},\ldots ,b_1 < \varepsilon$.

Proof

Let $q(n) = a_kn^k + a_{k-1} n^{k-1} + \cdots + a_1 n + a_0$, and let $\varepsilon > 0$ be arbitrary. Then for every $d \in \mathbb {N}$, we have

$$\begin{aligned} \langle q(n)\rangle&\ge _{\text {}}\langle q(dn)\rangle \ge _{\text {}}\langle \frac{q(dn)}{a_k d^k}\rangle = \langle n^k + \frac{a_{k-1}}{a_k d}n^{k-1} + \ldots + \frac{a_{1}}{a_k d^{k-1}}n^1 + \frac{a_{0}}{a_k d^{k}} \rangle \\&\ge _{\text {}}\langle n^k + \frac{a_{k-1}}{a_k d}n^{k-1} + \ldots + \frac{a_{1}}{a_k d^{k-1}}n^1 \rangle \end{aligned}$$

The first transduction is picking a subsequence of the blocks. The second transduction is a division of the size of each block (application of Lemma 24 with the weight $\langle \langle 1/a_k d^k,0\rangle \rangle$). The last transduction amounts to removing a constant number of zeros from each block (application of Lemma 24 with the weight $\langle \langle 1,-a_{0}/(a_k d^{k})\rangle \rangle$). Finally, note that the last polynomial in the transduction is of the desired form if $d \in \mathbb {N}$ is chosen large enough.    $\square$

For polynomials $p(n) \in \mathfrak {Q}_k$, we want to express weighted products $\langle \varvec{\alpha }\rangle \otimes p$ in terms of matrix products. For that purpose we need a couple of definitions.

Definition 26

For weights $\varvec{\alpha } = \langle a_0, \dots , a_{k - 1}, b\rangle$ we define a column vector $U(\varvec{\alpha }) = (a_0, \dots , a_{k - 1})^T.$

Definition 27

If $p(n) = \sum _{i = 0}^k c_i n^i$ is a polynomial of order k, we define a column vector $V(p(n)) = (c_1, \dots , c_k)^T$ and a square matrix

$$\begin{aligned} M(p(n)) = (V(p(kn + 0)),\,\dots ,\,V(p(kn + k - 1)))\,. \end{aligned}$$

We also write V(p) short for V(p(n) and M(p) for M(p(n)).

Note that we have omitted the constant term $c_0$ from the definition of V(p). The reason is that for every $f : \mathbb {N}\rightarrow \mathbb {N}$ and $c \in \mathbb {N}$ we have $\langle f(n)\rangle \equiv \langle f(n) + c\rangle$. These words are of the same degree because a finite state transducer can add (or remove) a constant number of symbols 0 to (from) every block of 0’s. For the same reason, b was omitted from the definition of $U(\varvec{\alpha })$.

Example 28

Consider the polynomial $n^3$:

$$\begin{aligned} V(n^3) = \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \qquad \text {and} \qquad M(n^3) = \begin{pmatrix} 0 &{} 9 &{} 36 \\ 0 &{} 27 &{} 54 \\ 27 &{} 27 &{} 27 \end{pmatrix} \end{aligned}$$

where the columns vectors of the matrix $M(n^3)$ are given by $V((3n)^3)$, $V((3n+1)^3)$ and $V((3n+2)^3)$.

Lemma 29

Let $k \ge 1$. Let $\varvec{\alpha } = \langle a_0, \dots , a_{k - 1}, b\rangle$ be a weight and $p(n) \in \mathfrak {Q}_k$. Then $M(p) \,U(\varvec{\alpha }) = V(\langle \varvec{\alpha }\rangle \otimes p)$.

Proof

A direct calculation shows that

$$\begin{aligned} M(p) \,U(\varvec{\alpha })&= \sum _{i = 0}^{k - 1} a_i V(p(kn + i)) = V\big (\sum _{i = 0}^{k - 1} a_i p(kn + i)\big ) \\&= V\big (\sum _{i = 0}^{k - 1} a_i p(kn + i) + b\big ) = V(\langle \varvec{\alpha }\rangle \otimes p)\;, \end{aligned}$$

which proves the lemma.    $\square$

Let us take a closer look at the matrix $M(n^k)$. The element on the ith row and jth column is ${M_{i,j} = \left( {\begin{array}{c}k\\ i\end{array}}\right) k^i (j - 1)^{k - i}}$. Dividing the ith row by $\left( {\begin{array}{c}k\\ i\end{array}}\right) k^i$ for each i gives a Vandermonde-type matrix, which is invertible. Thus also $M(n^k)$ is invertible.

Lemma 30

For $k \ge 1$, $M(n^k)$ is invertible.    $\square$

Theorem 31

Let $k \ge 1$. Let $a_0, \dots , a_{k - 1}$ be positive rational numbers, $\varvec{\alpha } = \langle a_0, \dots , a_{k - 1}, 0\rangle ,$ and

$$\begin{aligned} p(n) = (\langle \varvec{\alpha }\rangle \otimes n^k)(n) = \sum _{i = 0}^{k - 1} a_i (k n + i)^k. \end{aligned}$$

Then $\langle q(n)\rangle \ge _{\text {}}\langle p(n)\rangle$ for all $q(n) \in \mathfrak {Q}_k$. Moreover, the degree $\langle p(n)\rangle ^{{\equiv }}$ is an atom. Note that the degree $\langle p(n)\rangle ^{{\equiv }}$ is the infimum of all degrees of words $\langle q(n)\rangle$ with $q(n) \in \mathfrak {Q}_k$.

Proof

By Lemma 29, $M(n^k) \,U(\varvec{\alpha }) = V(p).$ By Lemma 30, $M(n^k)$ is invertible and we can write $U(\varvec{\alpha }) = M(n^k)^{-1} V(p).$ By Lemma 25, for every $\varepsilon > 0$ there exists $q_\varepsilon \in \mathfrak {Q}_k$ such that $\langle q(n)\rangle \ge _{\text {}}\langle q_\varepsilon (n)\rangle$ and

$$\begin{aligned} q_\varepsilon (n) = n^k + b_{k-1} n^{k-1} + \dots + b_1 n \end{aligned}$$

with $0 \le b_i \le \varepsilon$ for every $i \in \{1, \dots , k - 1\}$. We will show that if $\varepsilon$ is small enough, then $\langle q_\varepsilon (n)\rangle \ge _{\text {}}\langle p(n)\rangle .$

We have $\lim _{\varepsilon \rightarrow 0} M(q_\varepsilon ) = M(n^k).$ As $\det (M(n^3)) \ne 0$ and the determinant function is continuous, also $\det (M(q_\varepsilon )) \ne 0$ for all sufficiently small $\varepsilon$. Then $M(q_\varepsilon )$ is invertible, and we define $U_\varepsilon = M(q_\varepsilon )^{-1} V(p).$ We would like to have $U_\varepsilon = U(\gamma )$ for some weight $\gamma$. This is not always possible, because some elements of $U_\varepsilon$ might be negative. However, by the continuity of matrix inverse and product,

$$\begin{aligned} \lim _{\varepsilon \rightarrow 0} U_\varepsilon&= \lim _{\varepsilon \rightarrow 0} (M(q_\varepsilon )^{-1} V(p)) = (\lim _{\varepsilon \rightarrow 0} M(q_\varepsilon ))^{-1} V(p) = M(n^k)^{-1} V(p) = U(\varvec{\alpha }) \end{aligned}$$

Since every element of $U(\varvec{\alpha })$ is positive, we can fix a small enough $\varepsilon$ so that every element of $U_\varepsilon$ is positive. Then we have $U_\varepsilon = U(\gamma )$ for some weight $\gamma$.

We have $M(q_\varepsilon ) \,U(\gamma ) = V(\langle \gamma \rangle \otimes q_\varepsilon )$ by Lemma 29, and $M(q_\varepsilon ) \,U(\gamma ) = V(p)$ by the definition of $U_\varepsilon$. As a consequence $(\langle \gamma \rangle \otimes q_\varepsilon )(n) = p(n) + c$ for some constant c. By Lemma 24, we obtain $\langle q_\varepsilon (n)\rangle \ge _{\text {}}\langle p(n)\rangle .$

It remains to show that the degree $\langle p(n)\rangle ^{{\equiv }}$ is an atom. Assume that $\langle p(n)\rangle \ge _{\text {}}w$ and $w \not \in \varvec{0}$. By Proposition 18 we have $w \ge _{\text {}}\langle q(n)\rangle$ for some $q(n) \in \mathfrak {Q}_k$. As shown above, $\langle q(n)\rangle \ge _{\text {}}\langle p(n)\rangle$, thus $w \ge _{\text {}}\langle p(n)\rangle$. Hence $\langle p(n)\rangle ^{{\equiv }}$ is an atom.    $\square$

7 Future Work

Our results hint at an interesting structure of the transducer degrees of words $\langle p(n)\rangle$ for polynomials p(n) of order $k \in \mathbb {N}$. Here, we have only scratched the surface of this structure. Many questions remain open, for example:

• (i) What is the structure of ‘polynomial spiralling’ degrees (depending on $k \in \mathbb {N}$)? Is the number of degrees finite for every $k \in \mathbb {N}$?

• (ii) Are there interpolant degrees between the degrees of $\langle n^k\rangle$ and $\langle p_k(n)\rangle$?

• (iii) Are there continuum many atoms?

• (iv) Is the degree of the Thue–Morse sequence an atom?