Transducer degrees: atoms, infima and suprema

Abstract

Although finite state transducers are very natural and simple devices, surprisingly little is known about the transducibility relation they induce on streams (infinite words). We collect some intriguing problems that have been unsolved since several years. The transducibility relation arising from finite state transduction induces a partial order of stream degrees, which we call Transducer degrees, analogous to the well-known Turing degrees or degrees of unsolvability. We show that there are pairs of degrees without supremum and without infimum. The former result is somewhat surprising since every finite set of degrees has a supremum if we strengthen the machine model to Turing machines, but also if we weaken it to Mealy machines.

1 Introduction

This paper is dedicated to Rob van Glabbeek, in the hope that the problems outlined in our paper evoke his interest, hopefully with the result that he applies his widely known problem solving powers to them. The open problems reported here have withstood several attempts to solve them. The problems arise in a very natural setting, centered around finite state transducers, devices that are natural in applications dealing with transforming infinite streams of symbols. In fact, we notice that in the general theory of automata we come across a relative terra incognita as soon as we come to automata as transducers on infinite words. Let us elaborate on this state of the art in automata theory.

Automata can be used as acceptors and transducers. As acceptors they simply accept or reject input words, and thereby define a language of accepted words. Transducers have a richer output. They transform input words into output words, and thereby realise a function on words.

Both aspects have been studied extensively for automata on finite words. There is also a large body of research on automata on infinite words, streams for short. Streams defined by finite automata, known as automatic sequences, play an important role in number theory. Automata for defining languages of streams are known as stream automata or $\omega$-automata. There are various versions of stream automata, in particular Büchi, Muller, Rabin and parity automata. They are the foundation of model checking and formal verification as they allow for describing the (un)acceptable behaviours of non-terminating systems such as operating systems, control systems or hardware.

Surprisingly, finite automata for transforming streams have hardly been studied. An exception are Turing machines. The stream transformation realised by Turing machines gives rise to a pre-order on the set of streams: here, for streams u, w, we have $u \ge w$ if u can be transformed into w by some Turing machine. The ensuing hierarchy of stream degrees has been extensively studied and is known as Turing degrees or degrees of unsolvability. Beyond Turing machines, there has been almost no research on the power of finite automata, such as finite state transducers or Mealy machines, for transforming streams.

In this paper, we are interested in the hierarchy of stream degrees arising from finite state transduction. Again, we are interested in the pre-order $\ge$ on streams where $u \ge w$ if u can be transformed into w by some finite state transducer. Two streams u, w are considered equivalent, denoted $u \equiv w$, if $u \ge w$ and $w \ge u$. The equivalence classes of $\equiv$ are called degrees, and $\ge$ induces a partial order on these degrees (which we also denote by $\ge$). We refer to this hierarchy as the Transducer degrees. We are interested in the structural properties of this partial order; basic features concern the existence of:

• (i) bottom degree, the set of ultimately periodic streams

  $$\begin{aligned} \{uvvv\cdots \,\mid \,u,v\,\text {finite words},\,v\,\text {non-empty} \}; \end{aligned}$$

• (ii) top degree, not existing (however, the sub-hierarchy of computable degrees has a top-degree);

• (iii) infinite chains, ascending and descending;

• (iv) atoms, that is, minimal non-bottom degrees;

• (v) infima and suprema, these are the greatest lower and least upper bounds;

Some of these questions have been addressed in previous work; see further [23]. In this paper we are interested in the existence of infima and suprema. Clearly this is analogous to the existence of greatest common divisor and least common divisor on the natural numbers. In this analogy, our atoms are the prime numbers. The present situation is different from the one of natural numbers in that suprema and infima now do not always exist. Indeed, we will construct, in a single joint construction, a pair of degrees that has no infimum and a pair of degrees that has no supremum. This result was announced in a preliminary way, still without proof, in [23].

1.1 Outline and contribution

In Sect. 2, we introduce finite state transducers and state some challenging questions that already arise at this stage. In Sect. 3, we introduce the partial order of Transducer degrees arising from the stream transformation realised by finite state transducers, and we describe the results of an investigation [12, 17, 19, 20] of the appearance of atoms in the hierarchy of degrees. In Sects. 4 and 5, we introduce mass products as computational tools to reason about finite state transduction of spiralling streams. In Sect. 6, we characterise the transducts of spiralling streams in terms of displaced mass products.

In Sect. 7, we answer a question from [17] by showing that there are pairs of degrees without infimum and without supremum. The existence of such pairs of degrees without supremum is somewhat surprising since every finite set of degrees has a supremum if we strengthen the transformations to Turing machines (yielding Turing degrees), but also if we weaken it to Mealy machines (yielding Mealy degrees). In both cases, a supremum of a pair of degrees $\{u^{\equiv }, w^{\equiv } \}$ can be obtained by taking the degree of the stream of pairs $(u(0),w(0))\,;\,(u(1),w(1))\,;\cdots$

1.2 Related work

This paper is concerned with stream transformation via finite state transducers. We refer to the hierarchies of stream degrees arising from finite state transducers, Turing machines and Mealy machines as Transducer degrees, Turing degrees and Mealy degrees, respectively.

The Turing degrees have been the subject of extensive research, see for instance [30, 33, 34]. In contrast, Mealy degrees and Transducer degrees have hardly been studied. The partial order of Mealy degrees is studied by G. Rayna [31] and A. Belov [2]. The Transducer degrees have been studied in [12, 17, 19, 20, 23]. The papers [12, 17, 19, 20] are concerned with atoms in this hierarchy. A comparison of Transducer degrees with the Turing degrees can be found in [23]. An interesting result about finite state transduction is due to M. Dekking [6] who has shown that every finite state transduct of a morphic stream is again morphic (or finite). Thus morphic sequences form a subhierarchy of the Transducer degrees.

Bosma and Zantema [5] study a hierarchy of two-sided infinite sequences arising from the transformation realised by permutation transducers. While the ultimately periodic sequences form the bottom degree under ordinary transduction, they split into three unpointed and seven pointed equivalence classes under permutation transduction. This study is continued in [39] with the focus on one-side infinite sequences.

2 Finite state transducers

Let us start with describing finite state transducers and give some examples how they operate on infinite streams. Already at this initial stage there are some easily stated but hard open problems.

A finite state transducer (FST) is a deterministic finite automaton which reads the input stream letter by letter, in each step producing an output word and changing its state. An example of an FST is depicted in Fig. 1.

Fig. 1

A finite state transducer realizing the difference of consecutive bits modulo 2

We write ‘$a w$’ along the transitions to indicate that the input letter is a and the output word is w. In a finite state transducer, the output word given by a transition can have arbitrary length (also empty).¹ The total output word is the concatenation of all the output words encountered along the edges.

Example 1

The transducer in Fig. 1 computes the difference of consecutive bits modulo 2. It transforms (transduces) the Thue–Morse sequence $\mathsf {M}$ into the period doubling sequence $\mathsf {PD}$:

$$\begin{aligned} 0\;\;\;1\;\;\;1\;\;\;0\;\;\;1\;\;\;0\;\;\;0\;\;\;1\;\;\cdots&= \; \mathsf {M}\\ \rightarrow \ \,\;\;1\;\;\;0\;\;\;1\;\;\;1\;\;\;1\;\;\;0\;\;\;1\;\;\cdots&= \; \mathsf {PD}\end{aligned}$$

The Thue–Morse sequence $\mathsf {M}$ is the fixed point of the morphism

$$\begin{aligned} \{ 0 \mapsto 01,\; 1 \mapsto 10 \} \end{aligned}$$

starting in 0. It can be obtained as the limit of iterating this morphism on the starting word 0:

$$\begin{aligned}&0 \\ \mapsto&\ 01 \\ \mapsto&\ 0110 \\ \mapsto&\ 01101001 \\&\qquad \vdots \end{aligned}$$

Likewise, the period doubling sequence $\mathsf {PD}$ can be obtained as the limit of iterating the morphism $\{ 0 \mapsto 11,\; 1 \mapsto 10 \}$ on the starting word 1.

Formally, finite state transducers are defined as follows. (For a thorough introduction to finite state transducers, we refer to [1, 32].) We write $\varepsilon$ for the empty word and $\varSigma ^\infty = \varSigma ^* \cup \varSigma ^\mathbb {N}$ for the set of finite and infinite words. We only consider sequential transducers and will simply speak of finite state transducers.

Definition 2

A finite state transducer$A= \langle \varSigma ,\varDelta ,Q,q_{0},\delta ,\lambda \rangle$ consists of

• (i) a finite input alphabet $\varSigma$,

• (ii) a finite output alphabet $\varDelta$,

• (iii) a finite set of states $Q$,

• (iv) an initial state $q_{0} \in Q$,

• (v) a transition function $\delta : Q\times \varSigma \rightarrow Q$, and

• (vi) an output function $\lambda : Q\times \varSigma \rightarrow \varDelta ^*$.

Whenever $\varSigma$ and $\varDelta$ are clear from the context, we write $A= {\langle }Q{,\,}q_{0}{,\,}\delta {,\,}\lambda {\rangle }$.

We extend the output and transition functions of the transducer from single letters to finite and infinite input words as follows.

Definition 3

Let $A= {\langle }\varSigma {,\,}\varDelta {,\,}Q{,\,}q_{0}{,\,}\delta {,\,}\lambda {\rangle }$ be a finite state transducer. We extend the transition function $\delta$ from $Q \times \varSigma \rightarrow Q$ to $Q \times \varSigma ^* \rightarrow Q$ by

$$\begin{aligned} \delta (q,\varepsilon )&=q&\delta (q,aw)&=\delta (\delta (q,a),w)&(q\in Q, a \in \varSigma , w\in \varSigma ^{*}) \end{aligned}$$

The output function $\lambda$ is extended to $Q \times \varSigma ^\infty \rightarrow \varDelta ^\infty$ by

$$\begin{aligned} \lambda (q,\varepsilon )&=\varepsilon&\lambda (q,aw)&=\lambda (q,a) \cdot \lambda (\delta (q,a),w)&(q\in Q, a \in \varSigma , w\in \varSigma ^\infty ) \end{aligned}$$

We sometimes write $A(u)$ as shorthand for $\lambda (q_0,u)$. So the transducer $A$ realises a function $A: \varSigma ^\mathbb {N} \rightarrow \varDelta ^{\infty }$.

2.1 Challenging questions

Although finite state transducers are a very simple and elegant form of automata, hardly anything is known about their power in transforming streams. Even for simple examples of streams, there exist no techniques to determine whether one can be transformed into the other. To wit, consider the following problems:

Open Problem 1

Consider the period doubling sequence $\mathsf {PD}$ and drop every third element:

It is easy to find a finite state transducer that transforms $\mathsf {PD}$ into $\mathsf {PD'}$. Is the reverse also possible, or is information irrevocably lost?

Open Problem 2

The Mephisto waltz sequence

$$\begin{aligned} \mathsf {W}= 001 001 110 001 001 110 110 110 001 \cdots \end{aligned}$$

is obtained as the limit of iterating the morphism $\{ 0\mapsto 001,\; 1\mapsto 110 \}$ on the starting word 0. Can the Thue–Morse sequence $\mathsf {M}$ be transformed into $\mathsf {W}$ via a finite state transducer?² Is the reverse possible?

There are currently no techniques available to answer such simple questions. We will come back these problems in the next section.

3 Transducer degrees

The transducibility relation arising from finite state transduction induces a partial order of stream degrees, which we call Transducer degrees. Here a stream u is at least as complex as w if u can be transformed into w by a finite state transducer. If the reverse is also possible, then both streams have the same complexity. A degree is an equivalence class of streams that have the same complexity.

The Transducer degrees are analogous to—but much more fine-grained than—the recursion-theoretic degrees of unsolvability or Turing degrees. Turing degrees have been the subject of extensive research in the 60’s and 70’s of the last century with many fascinating results and techniques (see for instance [27, 30, 33,34,35,36]). In the Turing degrees, sets of natural numbers are compared by means of transducibility using Turing machines. Note that a set of natural numbers is also a stream over the alphabet $\{0,1\}$ via its characteristic function. Thus the degrees of unsolvability can equivalently be considered as a hierarchy of stream degrees. Then we have Turing machines transforming streams into each other.

For a complexity comparison, Turing machines are too strong. We are typically interested in computable streams, but they are all identified by transducibility via Turing machines. In the hierarchy of Turing degrees, all computable streams are trivialised in the bottom degree. We are therefore interested in studying transducibility of streams with respect to less powerful devices, such as finite state transducers. A reduction of the computational power results in a finer structure of degrees. This point of view is also pursued in [39], further restricting to permutation transducers, leading to an even more refined hierarchy.

Here is the formal definition of the partial order of Transducer degrees.

Definition 4

Let $\varSigma$, $\varGamma$ be finite alphabets, and $u\in \varSigma ^\mathbb {N}$, $w\in \varGamma ^\mathbb {N}$ streams. Let $A = {\langle }\varSigma {,\,}\varDelta {,\,}Q{,\,}q_{0}{,\,}\delta {,\,}\lambda {\rangle }$ be a FST. We write $u\ge _{A} w$ if $w= \lambda (q_0,u)$. We write

$$\begin{aligned} u\ge w\;, \end{aligned}$$

and say that $w$ is a transduct of $u$, if there exists a FST A such that $u\ge _{A} w$.

We write $u\equiv w$ if a forth and a back transformation is possible, that is, $u\ge w$ and $w\ge u$. Thus,

$$\begin{aligned} {\equiv } \;\;=\;\; {(\ge \cap \le )}. \end{aligned}$$

We say that streams related by ${\equiv }$ are equivalent.

It is easily checked that ${\equiv }$ forms an equivalence relation, and we refer to the equivalence classes of ${\equiv }$ as degrees.

Every stream over a finite alphabet is equivalent to some stream over $\{0,1 \}$. So, every degree contains a representative from the set $\{0,1 \}^\mathbb {N}$. Thus, when investigating the partial order of stream degrees, it suffices to consider streams over the alphabet $\mathbf {2}= \{0,1 \}$.

Definition 5

The degree$u^{\equiv }$ of a stream $u\in \mathbf {2}^\mathbb {N}$ is the equivalence class of $u$ with respect to $\equiv$, that is:

$$\begin{aligned} u^{\equiv } = \{w\in \mathbf {2}^\mathbb {N}\mid u\equiv w\}. \end{aligned}$$

We write $\mathbf {2}^\mathbb {N}/_{\equiv }$ to denote the set of degrees $\{u^{\equiv } \mid u\in \mathbf {2}^\mathbb {N}\}$.

Fig. 2

The partial order of Transducer degrees. Some open problems are indicated in red: 1, ..., 5 refer to open problems 1, ..., 5, respectively. The blue nodes are degrees. Note that $\langle n \rangle$ and $\langle n^2 \rangle$ are atoms, while $\langle n^k \rangle$ is not an atom for $k \ge 3$. The notation $\langle \,\cdot \, \rangle$ is defined above. Here $p_k$ is a particular polynomial of order k. The degree of $\langle p_k \rangle$ is an atom and all other polynomials of order k can be transduced to $\langle p_k \rangle$, but not vice versa (color figure online)

The transducibility relation ${\ge }$ induces a partial order on the set of degrees $\mathbf {2}^\mathbb {N}/_{\equiv }$. We refer to this partial order as Transducer degrees.

Definition 6

The Transducer degrees are the partial order ${\langle }\mathbf {2}^\mathbb {N}/_{\equiv }{,\,}\ge {\rangle }$ where

$$\begin{aligned} u^{\equiv } \ge w^{\equiv } \quad \iff \quad u\ge w\end{aligned}$$

for all words $u,w\in \mathbf {2}^\mathbb {N}$.

Figure 2 displays some initial results about the hierarchy of Transducer degrees that have been obtained in  [12, 17, 19, 20, 23], and points to some open problems. We use the following notation: for $f : \mathbb {N}\rightarrow \mathbb {N}$ we define the stream

$$\begin{aligned} \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}$$

We say that f is the block function of $\langle f \rangle$. By a block we refer to an occurrence of a factor in $\langle f \rangle$ of the shape $1 \underbrace{00 \cdots 0}_{0\,\text {or more}}$ that is followed by a 1.

We often write $\langle f(n) \rangle$ to denote the sequence $\langle n \mapsto f(n) \rangle$. For instance:

$$\begin{aligned} \langle n \rangle&= 1\;10\;100\;1000\;10000\;100000\;\cdots \\ \langle n^2 \rangle&= 1\;10\;10000\;1000000000\;\cdots \end{aligned}$$

The stream $\langle n \rangle$ is called ‘rarified ones’ in [26].

To get a better understanding of the hierarchies as mentioned, we discuss a few basic properties: bottom degrees and atoms.

3.1 Initial observations

An initial study of this partial order of degrees has been carried out in [17]. The hierarchy (displayed in Fig. 2) 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. A comparison with the well-known Turing degrees can be found in [23].

3.2 Bottom degree

The bottom degree$\mathbf {0}$ is a degree that is less than or equal to all other degrees:

That is, for all degrees $\mathbf {x}$ we have $\mathbf {0}\le \mathbf {x}$. For the Turing degrees the bottom degree consists of all computable streams. For the Transducer degrees, it consists of all ultimately periodic streams, streams of the form $uvvvv\cdots$ for finite words u, v.

3.3 Atoms

An interesting concept is that of an atom degree, that is, a degree that is directly above the bottom degree with nothing in-between:

Thus the atom degrees reduce only to $\mathbf {0}$ or themselves. Intuitively, the information content of a stream residing in an atom degree is ‘indivisible’: whatever transducer is applied on this stream, either the result is ultimately periodic (the structure is entirely destroyed), or there is enough structure left for a transducer to reconstruct the original stream.

• (i) In the Mealy degrees, there exist no atom degrees, see further [2].

• (ii) In the Turing degrees, atoms are usually referred to as minimal degrees. A famous result about Turing degrees, obtained by Spector [36], is the existence of an atom degree strictly below the first Turing jump (the degree of the halting problem). Lacombe [33] has extended the construction of Spector to show that there are continuum many atoms in the Turing degrees. So, embedded in the Transducer degrees, these streams would be uncomputable; hence above our focus of interest.

For the Transducer degrees, the existence of atoms has been investigated in the papers [12, 17, 19, 20]. We give a short account of our findings there. To discern atoms we focused on a substructure of the degrees hierarchy inhabited by streams with polynomial block function. We found that

• (i) the degree of $\langle n \rangle$ is an atom,

• (ii) the degree of $\langle n^2 \rangle$ is an atom, and

• (iii) the degree of $\langle n^k \rangle$ is not an atom for $k \ge 3$.

Moreover, we found that for every $k \ge 1$, there is a unique atom among the degrees of polynomials of order k, namely the degree of $\langle p_k(n) \rangle$ where

$$\begin{aligned} p_k(n) = \sum _{i = 0}^{k - 1} (k n + i)^k. \end{aligned}$$

It turns out that for every polynomial q(n) of order k, we have $\langle q(n) \rangle \ge \langle p(n) \rangle$. So, the degree of $\langle p(n) \rangle$ is the infimum of all degrees of polynomials of order k. This is illustrated in Fig. 3.

Fig. 3

Structure of degrees of polynomials of order $k \ge 3$. The node 3 points to open problem 3 concerning the view on this part of the degree structure

So, the $p_k$ is somehow “generic”. We have

$$\begin{aligned} p_1(n)&= n\\ p_2(n)&= (2n+0)^2 + (2n+1)^2 = 8n^2 + 4n + 1\\&\vdots \end{aligned}$$

Open Problem 3

How many degrees exist among polynomials of order k? What is the structure of the degrees of polynomials? In particular, is there a degree between $\langle n^k \rangle ^{\equiv }$ and $\langle p_k(n) \rangle ^{\equiv }$, for $k \ge 3$?

Summarising, there is at least a countably infinite number of atom degrees. But it remains an open problem whether there are continuum many.

3.4 Further problems for transducer degrees

Beyond these initial observations, the structure of the Transducer degrees is largely unexplored territory. There is a plethora of interesting further questions, including:

• (i) Does every degree have a minimal cover, that is, a degree directly above with nothing in-between?

• (ii) When does a pair of degrees have a least upper (greatest lower) bound?

• (iii) Is every degree $\mathfrak {a}$ the greatest lower bound of a pair of degrees ($\ne \mathfrak {a}$)?

• (iv) Are there interesting dense substructures? Are there dense intervals? That is degrees $\mathfrak {a}$ and $\mathfrak {e}$ with $\mathfrak {a} \lneq _{} \mathfrak {e}$ such that for all $\mathfrak {b},\mathfrak {d}$ with $\mathfrak {a} \le _{} \mathfrak {b} \lneq _{} \mathfrak {d} \le _{} \mathfrak {e}$, there exists $\mathfrak {c}$ with $\mathfrak {b} \lneq _{} \mathfrak {c} \lneq _{} \mathfrak {d}$.

• (v) How complex is the first-order theory in the language ${\langle }{\ge _{}}{,\,}{=}{\rangle }$?

• (vi) Are there suitable notions of Kolmogorov complexity that have relations to the Transducer degrees.

Further, we want to highlight the following open questions.

Open Problem 4

Is the degree of Thue-Morse an atom?

Fig. 4

Are these structures possible in the Transducer degrees?

Open Problem 5

Are there continuum many atoms? Does there exist some non-computable atom? Here a degree is non-computable if it contains a non-computable stream (then all streams in the degree are non-computable).

Open Problem 6

Can every finite partial order be embedded in the hierarchy? Can every finite distributive lattice be embedded in the hierarchy? In particular:

• (i) Is there a degree that has precisely three degrees below itself: two incomparable degrees and the bottom degree?

• (ii) Is there a degree that has precisely two degrees below itself?

Structures (i) and (ii) are displayed in Fig. 4 on the left and right, respectively.

4 The algebra of masses

To introduce our counterexample (to the existence of suprema and infima in the Transducer degrees) in the next section, we need some preparations. In particular, we need certain linear operations on functions $f : \mathbb {N}\rightarrow \mathbb {Q}$ which we refer to as mass products. Many of these tools are from [12, 19, 20]. However, we simplify the presentation and strengthen some of the results.

4.1 Mass products and displacements

Definition 7

A weight is a non-empty tuple of non-negative rational numbers. A weight $\langle a_0,\ldots ,a_{k-1}\rangle$ is called zero if $a_0,\ldots ,a_{k-1} = 0$.

Let $\varvec{\alpha } = \langle \alpha _0,\ldots ,\alpha _{\ell -1}\rangle$ and $\varvec{\beta } = \langle \beta _0,\ldots ,\beta _{\ell '-1}\rangle$ be tuples. We define

• the length$|\varvec{\alpha }| = \ell$,

• the rotation$\varvec{\alpha }^{(0)} = \varvec{\alpha }$ and $\varvec{\alpha }^{(n+1)} = \langle \alpha _1,\ldots ,\alpha _{\ell -1},\alpha _0\rangle ^{(n)}$,

• the concatenation$\varvec{\alpha } \mathrel {;}\varvec{\beta } = \langle \alpha _0,\ldots ,\alpha _{\ell -1}, \beta _0,\ldots ,\beta _{\ell '-1} \rangle$, and

• the unfolding$\varvec{\alpha }^n$ for $n > 0$ by induction: $\varvec{\alpha }^1 = \varvec{\alpha }$ and $\varvec{\alpha }^{n+1} = \varvec{\alpha } \mathrel {;}\varvec{\alpha }^n$.

Definition 8

A mass is a non-empty tuple of weights. A positive mass consists only of non-zero weights.

For a mass $\overrightarrow{\varvec{\alpha }} = \langle \varvec{\alpha _0},\ldots ,\varvec{\alpha _{\ell -1}}\rangle$, we define

$$\begin{aligned} ||\overrightarrow{\varvec{\alpha }}|| = |\varvec{\alpha _0}| + |\varvec{\alpha _1}| + \cdots + |\varvec{\alpha _{\ell -1}}|, \end{aligned}$$

that is, the sum of the lengths of its entries.

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)$. So, $\mathcal {S}^{k}(\,\cdot \,)$ is the operator removing the first k elements of a stream.

Our goal is to realise periodic transformations on streams as in Example 9. Here ‘mass products’ are a general format to transform streams by multiplying and grouping consecutive elements together, and ‘displacements’ are used for adding constants to the elements of a stream in a periodic fashion. Mass products and displacements are best understood by examples.

Example 9

Define $f : \mathbb {N}\rightarrow \mathbb {Q}$ by $f(n) = n^2$ for every $n \in \mathbb {N}$. Let $\overrightarrow{\varvec{\alpha }} = \langle \varvec{\alpha _0},\varvec{\alpha _1}\rangle$ be a mass where $\varvec{\alpha _0} = \langle 1,2,3\rangle$ and $\varvec{\alpha _1} = \langle 0,1\rangle$. Moreover, let $\varvec{\beta } = \langle 4,1\rangle$. Then $\varvec{\beta } \oplus (\overrightarrow{\varvec{\alpha }} \otimes f)$ can be visualised as

The weight $\varvec{\alpha _0} = \langle 1,2,3\rangle$ means that 3 consecutive entries are added while being multiplied by 1, 2 and 3, respectively.

A finite state transducer that realises the displaced mass product $\varvec{\beta } \oplus (\overrightarrow{\varvec{\alpha }} \otimes f)$ on the corresponding block streams is shown in Fig. 5. For every $f : \mathbb {N}\rightarrow \mathbb {N}$, the transducer transforms the block stream $\langle f \rangle$ to $\langle \varvec{\beta } \oplus (\overrightarrow{\varvec{\alpha }} \otimes f) \rangle$.

The implementation of these transformations is entirely straightforward, the details are as in the following definition.

Definition 10

Let $f : \mathbb {N}\rightarrow \mathbb {Q}$ be a function, $\overrightarrow{\varvec{\alpha }} = \langle \varvec{\alpha _0},\varvec{\alpha _1}, \ldots , \varvec{\alpha _{m-1}}\rangle$ a mass, $\varvec{\alpha _0} = \langle a_0,\ldots ,a_{k-1}\rangle$ a weight, and $\varvec{\beta } = \langle b_0, b_1, \ldots , b_{m-1}\rangle \in \mathbb {Q}^+$.

• (i) The scalar product$\varvec{\alpha _0} \cdot f \in \mathbb {Q}$ is defined by

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

• (ii) The mass product$\overrightarrow{\varvec{\alpha }} \otimes f : \mathbb {N}\rightarrow \mathbb {Q}$ is defined by induction on n:

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

• (iii) The displacement$\varvec{\beta } \oplus f : \mathbb {N}\rightarrow \mathbb {Q}$ is defined by induction on n:

  $$\begin{aligned} (\varvec{\beta } \oplus f)(0)&= f(0) + b_0 \\ (\varvec{\beta } \oplus f)(n+1)&= (\varvec{\beta }^{(1)} \oplus \mathcal {S}^{1}(f))(n)&(n \in \mathbb {N}) \end{aligned}$$

Fig. 5

A finite state transducer that realises the mass product and displacement given in Example 9 on the corresponding block stream

Remark 11

The transducer in Fig. 5 can also be viewed as an infinitary term rewrite system [18, 24] operating on infinite words. The rewrite rules are:

$$\begin{aligned} q_0 0&\rightarrow 0 q_0&q_1 0&\rightarrow 00 q_1&q_2 0&\rightarrow 000 q_2&q_3 0&\rightarrow q_3&q_4 0&\rightarrow 0 q_4 \\ q_0 1&\rightarrow q_1&q_1 1&\rightarrow q_2&q_2 1&\rightarrow 00001 q_3&q_3 1&\rightarrow 0 q_4&q_4 1&\rightarrow 1 q_0. \end{aligned}$$

Rewrite systems are more powerful than transducers. This flexibility can be convenient for reasoning about transformations of infinite words (or infinite terms). On the other hand, the increased power results in undecidability of many properties such as equivalence [9, 15, 16].

As a rewrite system, the properties termination (normalisation) and confluence are of interest; see for instance [7, 21, 22, 28, 38]. This rewrite system above is not infinitary normalising [11, 29] on all terms due to the term $q_3 0 0 0 0 \cdots$ admitting an infinite divergent rewrite sequence. So, when viewing erasing transducers as rewrite systems, the notion of interest is that of local termination [8, 25] and local productivity [13, 14, 40] on a given set of starting terms.

4.2 Computing with mass products

The following definitions help computing with mass products.

Definition 12

For a mass $\overrightarrow{\varvec{\alpha }} = \langle \varvec{\alpha _0},\ldots ,\varvec{\alpha _{\ell -1}}\rangle$ we define

$$\begin{aligned} \langle \alpha |_{0}, \alpha |_{1}, \ldots , \alpha |_{||\overrightarrow{\varvec{\alpha }}||-1}\rangle&= \varvec{\alpha _0} \mathrel {;}\cdots \mathrel {;}\varvec{\alpha _{\ell -1}}. \end{aligned}$$

So, $\alpha |_{i}$ denotes the i-th element of the weight $\varvec{\alpha _0} \mathrel {;}\cdots \mathrel {;}\varvec{\alpha _{\ell -1}}$ (we count from 0).

Example 13

Let $\overrightarrow{\varvec{\alpha }} = \langle \langle 3,1,5\rangle ,\langle 1\rangle ,\langle 2,4\rangle \rangle$. Then we have

$$\begin{aligned} \alpha |_{0}&= 3&\alpha |_{1}&= 1&\alpha |_{2}&= 5&\alpha |_{3}&= 1&\alpha |_{4}&= 2&\alpha |_{5}&= 4. \end{aligned}$$

For a mass $\overrightarrow{\varvec{\alpha }} = \langle \varvec{\alpha _0},\ldots ,\varvec{\alpha _{\ell -1}}\rangle$, we define a function $\varphi (\overrightarrow{\varvec{\alpha }},\,\cdot \,)$ that maps the index i of an element $\alpha |_{i}$ to the number j of the weight $\varvec{\alpha _j}$ that $\alpha |_{i}$ belongs to.

Definition 14

For a mass $\overrightarrow{\varvec{\alpha }} = \langle \varvec{\alpha _0},\ldots ,\varvec{\alpha _{\ell -1}}\rangle$, we define a function

$$\begin{aligned} \varphi (\overrightarrow{\varvec{\alpha }},\,\cdot \,) : \{0,\ldots ,||\overrightarrow{\varvec{\alpha }}||-1 \} \rightarrow \{0,\ldots ,|\overrightarrow{\varvec{\alpha }}|-1 \} \end{aligned}$$

by

$$\begin{aligned} \varphi (\overrightarrow{\varvec{\alpha }},i)&= \min \{ k \in \{0,\ldots ,\ell -1 \} \mid i < |\varvec{\alpha _0}| + \cdots + |\varvec{\alpha _{k}}| \} \end{aligned}$$

for every $0 \le i < ||\overrightarrow{\varvec{\alpha }}||$.

Example 15

Let $\overrightarrow{\varvec{\alpha }} = \langle \langle 3,1,5\rangle ,\langle 1\rangle ,\langle 2,4\rangle \rangle$. Then

$$\begin{aligned} \varphi (\overrightarrow{\varvec{\alpha }},0)&= 0&\varphi (\overrightarrow{\varvec{\alpha }},1)&= 0&\varphi (\overrightarrow{\varvec{\alpha }},2)&= 0 \\ \varphi (\overrightarrow{\varvec{\alpha }},3)&= 1&\varphi (\overrightarrow{\varvec{\alpha }},4)&= 2&\varphi (\overrightarrow{\varvec{\alpha }},5)&= 2. \end{aligned}$$

It is not hard to see that this amounts to simply stepping through a mass and recording the number of the weight you are in. So, $\overrightarrow{\varvec{\alpha }}$ yields 000122 for the steps 012345.

The following lemma provides an alternative way to compute mass products.

Lemma 16

Let $\overrightarrow{\varvec{\alpha }} = \langle \varvec{\alpha _0},\ldots ,\varvec{\alpha _{\ell -1}}\rangle$ be a mass. Then

$$\begin{aligned} ( \overrightarrow{\varvec{\alpha }} \otimes f )(h |\overrightarrow{\varvec{\alpha }}| + h') = \sum _{\begin{array}{c} i \in \{0,\ldots ,||\overrightarrow{\varvec{\alpha }}||-1 \} \\ \varphi (\overrightarrow{\varvec{\alpha }},i) = h' \end{array}} \big (\; \alpha |_{i} \cdot f(h ||\overrightarrow{\varvec{\alpha }}|| + i) \;\big ) \end{aligned}$$

for every $f : \mathbb {N}\rightarrow \mathbb {Q}$, $h \in \mathbb {N}$ and $h' \in \{0,\ldots ,|\overrightarrow{\varvec{\alpha }}|-1 \}$. $\square$

Example 17

We consider the mass product from Example 9. Let $\overrightarrow{\varvec{\alpha }} = \langle \varvec{\alpha _0},\varvec{\alpha _1}\rangle$ where $\varvec{\alpha _0} = \langle 1,2,3\rangle$ and $\varvec{\alpha _1} = \langle 0,1\rangle$. Then we have

$$\begin{aligned} \alpha |_{0} = 1&\alpha |_{1} = 2&\alpha |_{2} = 3&\alpha |_{3} = 0&\alpha |_{4} = 1 \\ \varphi (\overrightarrow{\varvec{\alpha }},0) = 0&\varphi (\overrightarrow{\varvec{\alpha }},1) = 0&\varphi (\overrightarrow{\varvec{\alpha }},2) = 0&\varphi (\overrightarrow{\varvec{\alpha }},3) = 1&\varphi (\overrightarrow{\varvec{\alpha }},4) = 1. \end{aligned}$$

and $|\overrightarrow{\varvec{\alpha }}| = 2$, $||\overrightarrow{\varvec{\alpha }}|| = 5$. We compute $(\overrightarrow{\varvec{\alpha }} \otimes f)(3) = ( \overrightarrow{\varvec{\alpha }} \otimes f )(1 |\overrightarrow{\varvec{\alpha }}| + 1)$:

$$\begin{aligned} ( \overrightarrow{\varvec{\alpha }} \otimes f )(1 |\overrightarrow{\varvec{\alpha }}| + 1)&= \sum _{\begin{array}{c} i \in \{0,\ldots ,||\overrightarrow{\varvec{\alpha }}||-1 \} \\ \varphi (\overrightarrow{\varvec{\alpha }},i) = 1 \end{array}} \big (\; \alpha |_{i} \cdot f(1 ||\overrightarrow{\varvec{\alpha }}|| + i) \;\big ) \\&= \alpha |_{3} \cdot f(1 ||\overrightarrow{\varvec{\alpha }}|| + 3) + \alpha |_{4} \cdot f(1 ||\overrightarrow{\varvec{\alpha }}|| + 4) \\&= 0 \cdot 64 + 1 \cdot 81 = 81. \end{aligned}$$

4.3 Properties of mass products

Unfolding a mass does not change its semantics.

Lemma 18

We have $\overrightarrow{\varvec{\alpha }} \otimes f = \overrightarrow{\varvec{\alpha }}^n \otimes f$ for every mass $\overrightarrow{\varvec{\alpha }}$, function $f : \mathbb {N}\rightarrow \mathbb {Q}$ and natural number $n > 0$. $\square$

By definition of mass products we have

$$\begin{aligned} \mathcal {S}^{}( \overrightarrow{\varvec{\alpha }} \otimes f ) = \overrightarrow{\varvec{\alpha }}^{(1)} \otimes \mathcal {S}^{|\varvec{\alpha _0}|}(f). \end{aligned}$$

(1)

The following lemma generalises this to arbitrary shifts.

Lemma 19

Let $f : \mathbb {N}\rightarrow \mathbb {Q}$ and $\overrightarrow{\varvec{\alpha }} = \langle \varvec{\alpha _0},\ldots ,\varvec{\alpha _{\ell -1}}\rangle$ a mass. Then

$$\begin{aligned} \mathcal {S}^{h |\overrightarrow{\varvec{\alpha }}| + h'}( \overrightarrow{\varvec{\alpha }} \otimes f ) = \overrightarrow{\varvec{\alpha }}^{(h')} \otimes \mathcal {S}^{ h||\overrightarrow{\varvec{\alpha }}|| + \sum _{i = 0}^{h'-1} |\varvec{\alpha _i}| }(f) \end{aligned}$$

for every $h \in \mathbb {N}$ and $h' \in \{0,\ldots ,|\overrightarrow{\varvec{\alpha }}|-1 \}$.

Proof

The claim is obvious for $h' = 0$. For $h' > 0$ it follows from (1) by induction on $h'$. $\square$

4.4 Composition of mass products

We have already defined how a mass $\overrightarrow{\varvec{\beta }}$ is applied to a function $f : \mathbb {N}\rightarrow \mathbb {Q}$ (a stream of rational numbers) with the result a function $\overrightarrow{\varvec{\beta }} \otimes f$. Often we need to iterate such products, obtaining for a second mass $\overrightarrow{\varvec{\alpha }}$ the product

$$\begin{aligned} \overrightarrow{\varvec{\alpha }} \otimes (\overrightarrow{\varvec{\beta }} \otimes f) . \end{aligned}$$

In analogy with ordinary function composition, satisfying $(f \circ g)(x) = f(g(x))$ for functions f, g, it will be convenient to have likewise a composition of masses, again denoted with $\otimes$, so that we have the ‘associative rule’

$$\begin{aligned} \overrightarrow{\varvec{\alpha }} \otimes (\overrightarrow{\varvec{\beta }} \otimes f) = (\overrightarrow{\varvec{\alpha }} \otimes \overrightarrow{\varvec{\beta }}) \otimes f. \end{aligned}$$

Note that the left-hand side is already defined, but the right-hand side not yet; we have to define $\overrightarrow{\varvec{\alpha }} \otimes \overrightarrow{\varvec{\beta }}$.

Bearing in mind how $\overrightarrow{\varvec{\beta }} \otimes f$ is defined in Definition 10, it is straightforward how to proceed, in particular viewing the ‘tripod’ picture in Example 9. All we have to do is pipelining this tripod (in general ‘n-pods’ in periodic repetition) construction for $\overrightarrow{\varvec{\beta }}$ with a second layer for $\overrightarrow{\varvec{\alpha }}$ as in the following example and figure. Having this double layered tripod processing, we must then describe the effect of the two layers, for masses $\overrightarrow{\varvec{\alpha }}$ and $\overrightarrow{\varvec{\beta }}$, into a single layer, a mass called $\overrightarrow{\varvec{\alpha }} \otimes \overrightarrow{\varvec{\beta }}$. It is then clear by the construction that indeed $\overrightarrow{\varvec{\alpha }} \otimes (\overrightarrow{\varvec{\beta }} \otimes f) = (\overrightarrow{\varvec{\alpha }} \otimes \overrightarrow{\varvec{\beta }}) \otimes f$.

Of course, the extraction of the precise formal definition of $\overrightarrow{\varvec{\alpha }} \otimes \overrightarrow{\varvec{\beta }}$ requires meticulous care, but in principle is straightforward based on the periodical repetitions of the weights in both masses $\overrightarrow{\varvec{\alpha }}$ and $\overrightarrow{\varvec{\beta }}$. We give an example that displays the intuition, and provide the ensuing formal definition.

Fig. 6

The composition of masses derived from a two-layered ‘tripod’ construction

Example 20

Continuing Example 9, let $\overrightarrow{\varvec{\alpha }} = \langle \varvec{\alpha _0},\varvec{\alpha _1}\rangle$ and $\overrightarrow{\varvec{\beta }} = \langle \varvec{\beta _0},\varvec{\beta _1}\rangle$, where

$$\begin{aligned} \varvec{\alpha _0}&= \langle 2,1\rangle&\varvec{\beta _0}&= \langle 1,2,3\rangle \\ \varvec{\alpha _1}&= \langle 1\rangle&\varvec{\beta _1}&= \langle 0,1\rangle . \end{aligned}$$

The composition $\overrightarrow{\varvec{\alpha }} \otimes \overrightarrow{\varvec{\beta }}$ can be derived by the two-layered ‘tripod’ construction displayed in Fig. 6. We unfold (repeat) the masses $\overrightarrow{\varvec{\alpha }}$ and $\overrightarrow{\varvec{\beta }}$ such that we have $||\overrightarrow{\varvec{\alpha }}|| = |\overrightarrow{\varvec{\beta }}|$; then the tripods align and there is a repetition. Afterwards the edges are ‘composed’ by multiplying the labels along the path. We derive

$$\begin{aligned} \overrightarrow{\varvec{\beta }} \otimes \overrightarrow{\varvec{\alpha }} = \langle \langle 2,4,6,\; 0,1\rangle ,\; \langle 1,2,3\rangle ,\; \langle 0,2,\; 1,2,3\rangle ,\; \langle 0,1\rangle \rangle . \end{aligned}$$

See Example 23 for the formal computation.

We now derive a formal definition of the composition $\overrightarrow{\varvec{\alpha }} \otimes \overrightarrow{\varvec{\beta }}$ which follows closely the idea of the construction displayed in Fig. 6.

Definition 21

For $a \in \mathbb {Q}_{\ge 0}$ and a weight $\varvec{\alpha } = \langle \alpha _0,\ldots ,\alpha _{\ell -1}\rangle$, we define:

$$\begin{aligned} a \cdot \varvec{\alpha }&= \langle a \cdot \alpha _0,\ldots , a \cdot \alpha _{\ell -1}\rangle \;. \end{aligned}$$

If $\overrightarrow{\varvec{\beta }} = \langle \varvec{\beta _0},\ldots ,\varvec{\beta _{\ell -1}}\rangle$ is a mass, we define the scalar product

$$\begin{aligned} \varvec{\alpha } \cdot \overrightarrow{\varvec{\beta }} = ( \alpha _0 \cdot \varvec{\beta _0} ) \mathrel {;}\cdots \mathrel {;}( \alpha _{\ell -1} \cdot \varvec{\beta _{\ell -1}} ). \end{aligned}$$

Definition 22

The product$\overrightarrow{\varvec{\alpha }} \otimes \overrightarrow{\varvec{\beta }}$ of masses $\overrightarrow{\varvec{\alpha }}$ and $\overrightarrow{\varvec{\beta }}$ is defined as follows. Let $\overrightarrow{\varvec{\alpha }} = \langle \varvec{\alpha _0},\ldots ,\varvec{\alpha _{\ell -1}}\rangle$ and $\overrightarrow{\varvec{\beta }} = \langle \varvec{\beta _0},\ldots ,\varvec{\beta _{\ell '-1}}\rangle$.

If $||\overrightarrow{\varvec{\alpha }}|| = |\overrightarrow{\varvec{\beta }}|$, define

$$\begin{aligned} \overrightarrow{\varvec{\alpha }} \otimes \overrightarrow{\varvec{\beta }}&= (\varvec{\alpha _0} \cdot \overrightarrow{\varvec{\gamma _0}} ) \mathrel {;}(\varvec{\alpha _1} \cdot \overrightarrow{\varvec{\gamma _1}} ) \mathrel {;}\cdots \mathrel {;}(\varvec{\alpha _{\ell -1}} \cdot \overrightarrow{\varvec{\gamma _{\ell -1}}} ), \end{aligned}$$

where, for $0 \le i < \ell$,

$$\begin{aligned} \overrightarrow{\varvec{\gamma _i}}&= \langle \varvec{\beta _{k_i}}, \varvec{\beta _{k_i + 1}}, \ldots , \varvec{\beta _{k_i + |\varvec{\alpha _i}| - 1}} \rangle \\ k_i&= ||\langle \varvec{\alpha _0}, \varvec{\alpha _1}, \ldots , \varvec{\alpha _{i-1}}\rangle || = |\varvec{\alpha _0}| + |\varvec{\alpha _1}| + \cdots + |\varvec{\alpha _{i-1}}|. \end{aligned}$$

If $||\overrightarrow{\varvec{\alpha }}|| \ne |\overrightarrow{\varvec{\beta }}|$, define

$$\begin{aligned} \overrightarrow{\varvec{\alpha }} \otimes \overrightarrow{\varvec{\beta }} = \overrightarrow{\varvec{\alpha }}^{c/||\overrightarrow{\varvec{\alpha }}||} \otimes \overrightarrow{\varvec{\beta }}^{{c}/|\overrightarrow{\varvec{\beta }}|} , \end{aligned}$$

where c is the least common multiple of $||\overrightarrow{\varvec{\alpha }}||$ and $|\overrightarrow{\varvec{\beta }}|$.

Example 23

We continue Example 20. We compute $\overrightarrow{\varvec{\alpha }} \otimes \overrightarrow{\varvec{\beta }}$. We have $||\overrightarrow{\varvec{\alpha }}|| = 3$ and $|\overrightarrow{\varvec{\beta }}| = 2$. Thus, we have to unfold $\overrightarrow{\varvec{\alpha }}$ twice and $\overrightarrow{\varvec{\beta }}$ thrice:

$$\begin{aligned} \overrightarrow{\varvec{\alpha }}^2 = \langle \varvec{\alpha _0},\varvec{\alpha _1},\varvec{\alpha _0},\varvec{\alpha _1}\rangle&\overrightarrow{\varvec{\beta }}^3 = \langle \varvec{\beta _0},\varvec{\beta _1},\varvec{\beta _0},\varvec{\beta _1},\varvec{\beta _0},\varvec{\beta _1}\rangle . \end{aligned}$$

Then

$$\begin{aligned}&\overrightarrow{\varvec{\alpha }} \otimes \overrightarrow{\varvec{\beta }} = \overrightarrow{\varvec{\alpha }}^2 \otimes \overrightarrow{\varvec{\beta }}^3 \\&= \langle \varvec{\alpha _0},\varvec{\alpha _1},\varvec{\alpha _0},\varvec{\alpha _1}\rangle \otimes \langle \varvec{\beta _0},\varvec{\beta _1},\varvec{\beta _0},\varvec{\beta _1},\varvec{\beta _0},\varvec{\beta _1}\rangle \\&= (\varvec{\alpha _0} \cdot \langle \varvec{\beta _0},\varvec{\beta _1}\rangle ) \mathrel {;}(\varvec{\alpha _1} \cdot \langle \varvec{\beta _0}\rangle ) \mathrel {;}(\varvec{\alpha _0} \cdot \langle \varvec{\beta _1},\varvec{\beta _0}\rangle ) \mathrel {;}(\varvec{\alpha _1} \cdot \langle \varvec{\beta _1}\rangle ) \\&= \langle \langle 2,4,6,\; 0,1\rangle ,\; \langle 1,2,3\rangle ,\; \langle 0,2,\; 1,2,3\rangle ,\; \langle 0,1\rangle \rangle . \end{aligned}$$

Lemma 24

We have $\overrightarrow{\varvec{\alpha }} \otimes (\overrightarrow{\varvec{\beta }} \otimes f) = (\overrightarrow{\varvec{\alpha }} \otimes \overrightarrow{\varvec{\beta }}) \otimes f$ for every function $f : \mathbb {N}\rightarrow \mathbb {Q}$, and all masses $\overrightarrow{\varvec{\alpha }},\overrightarrow{\varvec{\beta }}$.

Proof

Left to the reader; see the construction in Fig. 6 and Example 20. $\square$

4.5 Operations that leave the degree unchanged

Displacements leave the degree of the associated block sequence unchanged.

Lemma 25

We have $\langle f \rangle \equiv \langle \varvec{\beta } \oplus f \rangle$ for every $f : \mathbb {N}\rightarrow \mathbb {Q}_{\ge 0}$ and every $\varvec{\beta } \in \mathbb {Q}^+$ such that $\varvec{\beta } \oplus f$ is non-negative.

Proof

Finite state transducers can add (and remove) a constant amount of zeros to (from) blocks $1 0\cdots 0$ in a periodic fashion. $\square$

The next lemma enables us to ‘drop’ zero weights from masses, while leaving the degree of the corresponding block stream unchanged.

Lemma 26

Let $\overrightarrow{\varvec{\alpha }} = \langle \varvec{\alpha _0},\ldots ,\varvec{\alpha _{\ell -1}}\rangle$ be a mass such that $\ell \ge 2$ and $\varvec{\alpha _k}$ is zero for some $0 \le k < \ell$.

• (i) If $k > 0$, define

  $$\begin{aligned} \overrightarrow{\varvec{\alpha '}}&= \langle \varvec{\alpha _0},\ldots ,\varvec{\alpha _{k-2}}, \varvec{\beta }, \varvec{\alpha _{k+1}},\ldots , \varvec{\alpha _{\ell -1}}\rangle&\varvec{\beta }&= \varvec{\alpha _{k-1}} \mathrel {;}\varvec{\alpha _{k}}. \end{aligned}$$

• (ii) If $k < \ell -1$, define

  $$\begin{aligned} \overrightarrow{\varvec{\alpha '}}&= \langle \varvec{\alpha _0},\ldots ,\varvec{\alpha _{k-1}}, \varvec{\beta }, \varvec{\alpha _{k+2}},\ldots , \varvec{\alpha _{\ell -1}}\rangle&\varvec{\beta }&= \varvec{\alpha _{k}} \mathrel {;}\varvec{\alpha _{k+1}}. \end{aligned}$$

In both cases, we have $\langle \overrightarrow{\varvec{\alpha }} \otimes f \rangle \equiv \langle \overrightarrow{\varvec{\alpha '}} \otimes f \rangle$ for every $f : \mathbb {N}\rightarrow \mathbb {N}$.

Proof

Let $f : \mathbb {N}\rightarrow \mathbb {N}$. Let $g = \overrightarrow{\varvec{\alpha }} \otimes f$ and $g' = \overrightarrow{\varvec{\alpha '}} \otimes f$. Since $\varvec{\alpha _k}$ is zero, we have that $g(k + \ell n) = 0$ for every $n \in \mathbb {N}$. We consider the cases (i) and (ii).

For case (i), the mass $\overrightarrow{\varvec{\alpha '}}$ is obtained from $\overrightarrow{\varvec{\alpha }}$ by merging (concatenating) the weights $\varvec{\alpha _{k-1}}$ and $\varvec{\alpha _k}$. Likewise, for case (ii), the mass $\overrightarrow{\varvec{\alpha '}}$ is obtained from $\overrightarrow{\varvec{\alpha }}$ by concatenating $\varvec{\alpha _k}$ and $\varvec{\alpha _{k+1}}$.

In both cases, thinking of g and $g'$ as sequences of natural numbers, it follows that $g'$ is obtained from g by dropping the elements at indices $k + \ell n$ for $n \in \mathbb {N}$. As we have $g(k + \ell n) = a_k$ for every $n \in \mathbb {N}$, it follows that $\langle g \rangle \equiv \langle g' \rangle$ since a finite state transducer can easily realise the periodic insertion or removal of blocks of size 0. Thus, $\langle \overrightarrow{\varvec{\alpha }} \otimes f \rangle \equiv \langle \overrightarrow{\varvec{\alpha '}} \otimes f \rangle$ in both cases. $\square$

Example 27

To illustrate Lemma 26, let

$$\begin{aligned} \overrightarrow{\varvec{\alpha }} = \langle \langle 1,2\rangle ,\langle 0,0\rangle ,\langle 5\rangle ,\langle 2,3\rangle \rangle . \end{aligned}$$

Then, in the lemma, we have

• (i) $\overrightarrow{\varvec{\alpha '}} = \langle \langle 1,2,0,0\rangle ,\langle 5\rangle ,\langle 2,3\rangle \rangle$, or

• (ii) $\overrightarrow{\varvec{\alpha '}} = \langle \langle 1,2\rangle ,\langle 0,0,5\rangle ,\langle 2,3\rangle \rangle$.

In both cases, we have $\langle \overrightarrow{\varvec{\alpha }} \otimes f \rangle \equiv \langle \overrightarrow{\varvec{\alpha '}} \otimes f \rangle$ for every $f : \mathbb {N}\rightarrow \mathbb {N}$.

Theorem 28

Let $\overrightarrow{\varvec{\alpha }}$ be a mass containing at least one non-zero weight. Then there exists a positive mass $\overrightarrow{\varvec{\alpha '}}$ such that

$$\begin{aligned} \langle \overrightarrow{\varvec{\alpha }} \otimes f \rangle \equiv \langle \overrightarrow{\varvec{\alpha '}} \otimes f \rangle \end{aligned}$$

for every $f : \mathbb {N}\rightarrow \mathbb {N}$.

Proof

By repeated application of Lemma 26 we can drop all zero weights from $\alpha$. This yields $\langle \overrightarrow{\varvec{\alpha }} \otimes f \rangle \equiv \langle \overrightarrow{\varvec{\alpha '}} \otimes f \rangle$ for mass $\overrightarrow{\varvec{\alpha '}}$ consisting only of non-zero weights. $\square$

5 The algebra of spiralling functions

For our construction, we consider the subhierarchy of degrees based on the interesting class of spiralling number-theoretic functions [3, 4, 12] and as a computational device, a form of scalar products.

Definition 29

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 stream $\langle f \rangle$ is called spiralling whenever f is spiralling.

Spiralling functions are called ‘cyclically ultimately periodic’ in the literature, see for instance, [3, 4].³ The class of spiralling functions is closed under addition and multiplication. It is also closed under the addition of constants and the multiplication with non-zero constants. For instance, polynomials with natural numbers as coefficients are spiralling (if they are not constant).

Note that for every $f : \mathbb {N}\rightarrow \mathbb {N}$ and $d \in \mathbb {N}_{>0}$, $\langle f \rangle \equiv \langle d \cdot f \rangle$. So, we may ignore constant factors as they do not change the degree of the stream. This enables us to use functions $f : \mathbb {N}\rightarrow \mathbb {Q}_{\ge 0}$ with, as it were, ‘rational block size’, as long as there exists $d \in \mathbb {N}_{>0}$ such that $d \cdot f : \mathbb {N}\rightarrow \mathbb {N}$.

Definition 30

A function $f : \mathbb {N}\rightarrow \mathbb {Q}_{\ge 0}$ has a common denominator if there exists $d \in \mathbb {N}_{>0}$ such that $d \cdot f(n) \in \mathbb {N}$ for every $n \in \mathbb {N}$.

For a function $f : \mathbb {N}\rightarrow \mathbb {Q}_{\ge 0}$ with a common denominator, we define

$$\begin{aligned}{}[f] = d\cdot f&\text {and}&\langle f \rangle = \langle [f] \rangle , \end{aligned}$$

where $d \in \mathbb {N}_{>0}$ is minimal with the property $d \cdot f(n) \in \mathbb {N}$ for every $n \in \mathbb {N}$.

Definition 31

A function $f : \mathbb {N}\rightarrow \mathbb {Q}_{\ge 0}$ is called spiralling if

• (i) f has a common denominator, and

• (ii) $[f]$ is spiralling.

We write

to denote the set of spiralling function from $\mathbb {N}\rightarrow \mathbb {Q}_{\ge 0}$. We use

to denote the spiralling functions from $\mathbb {N}\rightarrow \mathbb {N}$.

Definition 32

A function $f : \mathbb {N}\rightarrow \mathbb {Q}$ is called non-negative if $f(n) \ge 0$ for every $n \in \mathbb {N}$.

The next two lemmas follow straightforwardly by the respective definitions and elementary arithmetic. The existence of a common denominator is preserved under displacements and mass products.

Lemma 33

Let $f : \mathbb {N}\rightarrow \mathbb {Q}_{\ge 0}$ be a function with common denominator. Let $\overrightarrow{\varvec{\alpha }}$ be a mass, and let $\varvec{\beta } \in \mathbb {Q}^+$ such that $\varvec{\beta } \oplus f$ is non-negative. Then the functions $\overrightarrow{\varvec{\alpha }} \otimes f$ and $\varvec{\beta } \oplus f$ have a common denominator. $\square$

The class of spiralling sequences is closed under shifts, displacements and mass products with positive masses.

Lemma 34

Let

. Then

• (i)

  

  for every $n \in \mathbb {N}$,

• (ii)

  

  for every $\varvec{\beta } \in \mathbb {Q}^+$ such that $\varvec{\beta } \oplus f$ is non-negative, and

• (iii)

  

  for every positive mass $\overrightarrow{\varvec{\alpha }}$. $\square$

Lemma 35

For every positive integer p, and

,

.

Proof

Let $m \in \mathbb {N}$. We show that $p^{f(n)}$ is ultimately periodic modulo m. By the pigeonhole principle, there are $a,b > 0$ such that $p^a \equiv p^{a+b} ({\text {mod}\,} m)$. Hence, we have ($\star$) $p^{a'} \equiv p^{a' + kb} ({\text {mod}\,} m)$ for all $a' \ge a$ and $k \in \mathbb {N}$. Since f is ultimately periodic modulo b, there exist $n_0,r \in \mathbb {N}$ such that $f(n) \equiv f(n+r) ({\text {mod}\,} b)$ for all $n \ge n_0$. Now let $N \ge n_0$ be such that $f(n) > a$ for all $n \ge N$. Then for all $n > N$, there exist $a' \ge a$ and $k_1,k_2\in \mathbb {N}$ such that $f(n) = a' + k_1 b$ and $f(n+r) = a' + k_2 b$. Then by ($\star$) we conclude $p^{f(n)} \equiv p^{a'} \equiv p^{f(n+r)} ({\text {mod}\,} m)$. $\square$

Clearly, the identity function is spiralling, hence, by Lemma 35, $p^n$ is spiralling. A second application of the lemma yields that also $p^{p^n}$ is a spiralling function.

Remark 36

The condition that $\lim _{n\rightarrow \infty } f(n)$ exists in the definition of spiralling is necessary for Lemma 35. For a counterexample, consider the function $f : \mathbb {N}\rightarrow \mathbb {N}$ given by $f(n) = 1$ if $n = k!+1$ for some k, and $f(n) = n$ otherwise. Let $m\in \mathbb {N}$. Then $\forall k \ge m$, $k!+1 \equiv 1 ({\text {mod}\,} m)$, and hence $f(n) \equiv n ({\text {mod}\,} m)$ for large enough $n\in \mathbb {N}$. This function f is ultimately periodic modulo every $m\in \mathbb {N}$, but it has no limit. Then $2^{f(n)} \equiv 2 ({\text {mod}\,} 4)$ if and only if n is of the form $n = k! + 1$, thus not periodic.

6 Characterisation of transducts of spiralling sequences

In this section, we characterise the transducts of spiralling sequences in terms of mass products.

The following theorem characterises transducts of spiralling sequences up to equivalence in terms of displaced mass products.

Theorem 37

([12]) Let

, and $\sigma \in \mathbf {2}^\mathbb {N}$. We have $\langle f \rangle \ge \sigma$ if and only if

$$\begin{aligned} \sigma \equiv \langle \varvec{\beta } \oplus (\overrightarrow{\varvec{\alpha }} \otimes \mathcal {S}^{n_0}(f)) \rangle \end{aligned}$$

for some $n_0 \in \mathbb {N}$, a mass $\overrightarrow{\varvec{\alpha }}$ and $\varvec{\beta } \in \mathbb {Q}^{|\overrightarrow{\varvec{\alpha }}|}$.

For our purposes, we require a slight strengthening of this theorem ensuring that the transduct is either ultimately periodic or spiralling.

Theorem 38

Let

, and $\sigma \in \mathbf {2}^\mathbb {N}$. We have $\langle f \rangle \ge \sigma$ if and only if

• (i) $\sigma$ is ultimately periodic, or

• (ii) $\sigma \equiv \langle \overrightarrow{\varvec{\alpha }} \otimes \mathcal {S}^{n_0}(f) \rangle$ for some $n_0 \in \mathbb {N}$, and a positive mass $\overrightarrow{\varvec{\alpha }}$.

In the latter case, we have

by Lemma 34.

Proof

The direction ‘$\Leftarrow$’ follows from Theorem 37.

For ‘$\Rightarrow$’, let

and let $\sigma \in \mathbf {2}^\mathbb {N}$ be not ultimately periodic. By Theorem 37 and Lemma 25 we have $\sigma \equiv \langle \overrightarrow{\varvec{\alpha }} \otimes \mathcal {S}^{n_0}(f) \rangle$ for some $n_0 \in \mathbb {N}$, and a mass $\overrightarrow{\varvec{\alpha }}$. As $\sigma$ is not ultimately periodic, $\overrightarrow{\varvec{\alpha }}$ contains some non-zero weights. By Theorem 28 we conclude that $\sigma \equiv \langle \overrightarrow{\varvec{\alpha }} \otimes \mathcal {S}^{n_0}(f) \rangle \equiv \langle \overrightarrow{\varvec{\alpha '}} \otimes \mathcal {S}^{n_0}(f) \rangle$ for some positive mass $\overrightarrow{\varvec{\alpha '}}$. $\square$

Theorem 38 characterises transducts of spiralling sequences up to equivalence. The following theorem strengthens the characterisation (equivalence is replaced by shifts) for the case the transduct is also a spiralling sequence.

Theorem 39

([19]) Let

. Then $\langle g \rangle \ge \langle f \rangle$ if and only if some shift of f is a displacement of a mass product of a shift of g, that is:

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

(2)

for some $n_0, m_0 \in \mathbb {N}$, a mass $\overrightarrow{\varvec{\alpha }}$ and $\varvec{\beta } \in \mathbb {Q}^{|\overrightarrow{\varvec{\alpha }}|}$.

Theorem 38 states that every transduct of a spiralling stream is either ultimately periodic (in the bottom degree) or again equivalent to a spiralling stream. So, the set of degrees containing spiralling streams is closed under transduction and thus forms a subhierarchy of the Transducer degrees. For understanding the structure of this subhierarchy it suffices to understand when spiralling streams can be transduced into each other. Theorem 39 characterises this inter-transducibility of spiralling streams in terms of displaced mass products:

• For spiralling functions f, g we have $\langle g \rangle \ge \langle f \rangle$ if and only if some shift of f is the displaced mass product of some shift of g.

So, the interesting question is: what preorder does equation (2) induce on the set of spiralling functions?

7 Infima and suprema

After our account of the presence of atom degrees, a next natural focus point of our attention is the question whether the degree hierarchy has suprema and infima for pairs of degrees. Here another contrast with Turing degrees and Mealy degrees manifests itself. While these last hierarchies do possess suprema for every finite set of degrees, we show that this is not the case for Transducer degrees, and thereby answers a question of [17].

We now present two counterexamples for the price of one. We give one construction that yields at the same time that there are pairs of degrees without infimum and pairs of degrees without supremum. The idea of the construction is illustrated in Fig. 7.

Fig. 7

The idea behind the construction to show that there are pairs of degrees without supremum, and pairs of degrees without infimum; the degree $\gamma$ does not exist

We construct streams $\sigma _1$, $\sigma _2$, $\tau _1$, $\tau _2$ in such a way that the degrees $\sigma _1^{\equiv }$, $\sigma _2^{\equiv }$ are upper bounds of $\{ \tau _1^{\equiv }, \tau _2^{\equiv } \}$, and the following property holds:

($\star$):

there exists no degree $\gamma ^{\equiv }$ that is at the same time a lower bound of $\{ \sigma _1^{\equiv }, \sigma _2^{\equiv } \}$ and an upper bound of $\{ \tau _1^{\equiv }, \tau _2^{\equiv } \}$.

Observe that any infimum of $\{ \sigma _1^{\equiv }, \sigma _2^{\equiv } \}$ or supremum of $\{ \tau _1^{\equiv }, \tau _2^{\equiv } \}$ would satisfy this property. Showing that such a the degree $\gamma ^{\equiv }$ does not exist, thus implies that $\{ \sigma _1^{\equiv }, \sigma _2^{\equiv } \}$ has no infimum, and $\{ \tau _1^{\equiv }, \tau _2^{\equiv } \}$ has no supremum.

For convenience, we introduce the following notation:

Definition 40

For sets of streams (or degrees) U, V we write $U \ge V$ if $u \ge v$ for every $u \in U$ and $v \in V$.

We have $\{ \sigma _1, \sigma _2 \} \ge \{ \tau _1, \tau _2 \}$, but there does not exist $\gamma$ such that

To this end, we choose $\sigma _1,\sigma _2,\tau _1,\tau _2$ as follows:

Definition 41

We define $\sigma _1,\sigma _2,\tau _1,\tau _2 \in \{0,1 \}^\omega$ by:

$$\begin{aligned} \sigma _1&= \prod _{i = 0}^{\infty } (1 0^{2^{2^i}}1 0^{3^{3^{3^i}}})&\sigma _2&= \prod _{i = 0}^{\infty } (1 0^{3^{3^{3^i}}}1 0^{2^{2^i}}) \\ \tau _1&= \prod _{i = 0}^{\infty } 1 0^{2^{2^i}} = \langle 2^{2^i} \rangle&\tau _2&= \prod _{i = 0}^{\infty } 1 0^{3^{3^{3^i}}} = \langle 3^{3^{3^i}} \rangle \end{aligned}$$

We have

$$\begin{aligned} \{ \sigma _1, \sigma _2 \} \ge \{ \tau _1, \tau _2 \} \end{aligned}$$

by deleting every second block (beginning from the first or second block, respectively). Thus, $\sigma _1^{\equiv }$, $\sigma _2^{\equiv }$ are upper bounds of $\{ \tau _1^{\equiv }, \tau _2^{\equiv } \}$. Figure 8 illustrates the growth of the block sizes in $\sigma _1,\sigma _2,\tau _1,\tau _2$ and indicates possible and impossible transductions between these streams.

Fig. 8

The graphs illustrate growth of the block size of $\sigma _1$ (upper left), $\sigma _2$ (upper right), $\tau _1$ (lower left) and $\tau _2$ (lower right). The green (solid) arrows stand for finite state transductions, while the red circle and the grey (dotted) arrows represent impossible transductions (color figure online)

Proving ($\star$) is non-trivial as we need to reason about all possible upper/lower bounds, and all possible finite state transductions. To reason about the transducts of $\sigma _1$ and $\sigma _2$, we will employ Theorems 38 and  39.

Remark 42

Note that the double exponential growth ${2^{2^i}}$ of the block sizes is necessary for the construction. Consider

$$\begin{aligned} \sigma _1'&= \prod _{i = 0}^{\infty } (10^{2^{i}}10^{3^{3^{3^i}}})&\sigma _2'&= \prod _{i = 0}^{\infty } (10^{3^{3^{3^i}}}10^{2^{i}}) \\ \tau _1'&= \prod _{i = 0}^{\infty } 10^{2^{i}}&\tau _2'&= \prod _{i = 0}^{\infty } 10^{3^{3^{3^i}}}. \end{aligned}$$

Then we have $\sigma _1' \equiv \sigma _2'$, both streams reside in the same degree. For instance, for $\sigma _1' \ge \sigma _2'$: delete the first block 10, and transduce every block $0^{2^i}$ to $0^{2^{i-1}}$ by replacing $00 \mapsto 0$. Then $\gamma ^{\equiv }$ exists, e.g., take $\gamma = \sigma _1'$.

We define functions $s_1,s_2,t_1,t_2 : \mathbb {N}\rightarrow \mathbb {N}$ that correspond to the block size of $\sigma _1,\sigma _2,\tau _1,\tau _2$, respectively. We recall that the block size is the stream of run-lengths of blocks of zeros (the distance of ones in the stream).

Definition 43

We define $t_1,t_2 : \mathbb {N}\rightarrow \mathbb {N}$ by

$$\begin{aligned} t_1(n)&= 2^{2^n}&t_2(n)&= 3^{3^{3^n}}, \end{aligned}$$

and $s_1,s_2 : \mathbb {N}\rightarrow \mathbb {N}$ by

$$\begin{aligned} s_1(n)&= {\left\{ \begin{array}{ll} t_1(n/2) &{}\text {if}\,n\,\text {is even}\\ t_2((n-1)/2) &{}\text {if}\,n\, \text {is odd} \end{array}\right. }&s_2(n)&= {\left\{ \begin{array}{ll} t_2(n/2) &{}\text {if}\,n\, \text {is even}\\ t_1((n-1)/2) &{}\text {if}\,n\, \text {is odd}. \end{array}\right. } \end{aligned}$$

Lemma 44

We have $\sigma _1 = \langle s_1 \rangle$, $\sigma _2 = \langle s_2 \rangle$, $\tau _1 = \langle t_1 \rangle$ and $\tau _2 = \langle t_2 \rangle$. $\square$

Lemma 45

We have

. $\square$

7.1 Proof idea

Before we get to the proof we will give a rough sketch of the idea. Assume that

$$\begin{aligned} \{ \langle s_1 \rangle , \langle s_2 \rangle \} \ge \{\langle g \rangle \} \ge \{ \langle t_1 \rangle , \langle t_2 \rangle \} \end{aligned}$$

for some $g : \mathbb {N}\rightarrow \mathbb {N}$. By Theorem 38 we may assume that g is spiralling.

For functions $f,h : \mathbb {N}\rightarrow \mathbb {N}$, we write

$$\begin{aligned} f \approx h \quad \iff \quad&\exists c_1,c_2 > 0.\,\, \exists n_f,n_h.\, \\&\quad \forall n.\,\; c_1 h(n_h + n) \le f(n_f + n) \le c_2 h(n_h + n). \end{aligned}$$

Note that $\approx$ is an equivalence relation (symmetric and transitive). (The relation $\approx$ is similar to the well-known Big-Theta notation.)

The basic idea of the proof is as follows. We show that

$$\begin{aligned} \big ( \{ \langle s_1 \rangle \} \ge \{\langle g \rangle \} \ge \{ \langle t_1 \rangle , \langle t_2 \rangle \} \big ) \quad \mathrel {\Longrightarrow }\quad s_1 \approx g, \end{aligned}$$

(3)

and similarly,

$$\begin{aligned} \big ( \{ \langle s_2 \rangle \} \ge \{\langle g \rangle \} \ge \{ \langle t_1 \rangle , \langle t_2 \rangle \} \big ) \quad \mathrel {\Longrightarrow }\quad s_2 \approx g. \end{aligned}$$

Then we have $s_1 \approx g \approx s_2$. However, this yields a contradiction since $s_1 \not \approx s_2$!

We briefly outline the proof of (3). In this sketch we ignore shifts and displacements. By Theorem 39 every spiralling transduct $\langle h \rangle$ of $\langle s_1 \rangle$ is of the form $h = \overrightarrow{\varvec{\alpha }} \otimes s_1$:

We consider a transduction from $\langle s_1 \rangle$ to $\langle t_1 \rangle$; let $t_1 = \overrightarrow{\varvec{\alpha }} \otimes s_1$. In Fig. 8 this is a transduction from the upper left to the lower left; referring to this figure we will speak of white and black blocks. Then:

• (i) The ‘only’ way to transduce $\langle s_1 \rangle$ to $\langle t_1 \rangle$ is to erase all black blocks of length $3^{3^{3^n}}$, for otherwise the lengths of the blocks of the transduct grows faster than $t_1(n) = 2^{2^n}$. As a consequence $||\overrightarrow{\varvec{\alpha }}||$ is even and $\alpha |_{i} = 0$ for every odd i.

• (ii) Thus, $\langle t_1 \rangle$ is created only from the white blocks of length $2^{2^n}$ in $\langle s_1 \rangle$. The transduction cannot erase (skip) any of these blocks as the resulting subsequence would grow faster than $t_1$. Thus, $\alpha |_{i} > 0$ if and only if i is even.

• (iii) For the same reason, the transduction also cannot merge white blocks of length $2^{2^n}$ in $\langle s_1 \rangle$. So, every weight in $\overrightarrow{\varvec{\alpha }}$ contains precisely one positive $\alpha |_{i}$ with i even.

For a precise formulation of these properties, see Lemma 48.

Likewise, consider a transduction from $\langle s_1 \rangle$ to $\langle t_2 \rangle$; let $t_2 = \overrightarrow{\varvec{\alpha '}} \otimes s_1$. Using similar reasoning as above, we then can conclude that:

• (iv) The transduction cannot erase any of the black blocks of length $3^{3^{3^n}}$. Thus, we have $\alpha '|_{i} > 0$ for every odd i.

See Lemma 49 for the precise formulation.

Now, if $\langle g \rangle$ exists, then we have $\langle s_1 \rangle \ge \langle g \rangle \ge \{\langle t_1 \rangle ,\langle t_2 \rangle \}$. This gives rise to transductions from $\langle s_1 \rangle$ to $\langle t_1 \rangle$ and from $\langle s_1 \rangle$ to $\langle t_2 \rangle$ which both ‘start’ with common transduction from $\langle s_1 \rangle$ to $\langle g \rangle$. Therefore, consider the common begin piece from $\langle s_1 \rangle$ to $\langle g \rangle$, say $g = \overrightarrow{\varvec{\beta }} \otimes s_1$. Then:

• (v) The transduction can neither erase white blocks of length $2^{2^n}$ by (ii), nor black blocks of length $3^{3^{3^n}}$ by (vi). So, $\beta |_{i} > 0$ for every i.

• (vi) The transduction can also not merge the white blocks of length $2^{2^n}$ with any other block by (i) and (iii). Thus, every weight in $\overrightarrow{\varvec{\beta }}$ has length 1.

So, the crucial conclusion is: every weight in $\overrightarrow{\varvec{\beta }}$ is non-zero and has length 1! Thus, the transduction $\langle s_1 \rangle \ge \langle g \rangle$ is of the form

As a consequence, we have $s_1 \approx g$. Now, the contradiction arises as outlined above.

7.2 Proof

We will now prove the non-existence of $\gamma$ in several steps. In the next lemmas we investigate how $\gamma$ arises as a transduct of $\sigma _1 = \langle s_1 \rangle$, and how $\gamma$ gives rise to $\tau _1 = \langle t_1 \rangle$ and $\tau _2 = \langle t_2 \rangle$.

Lemma 46

Assume that $\{ \sigma _1, \sigma _2 \} \ge \{\gamma \} \ge \{ \tau _1, \tau _2 \}$ for some stream $\gamma \in \mathbf {2}^\mathbb {N}$. Then the same holds for a spiralling stream $\gamma$ of the form

$$\begin{aligned} \gamma = \langle \overrightarrow{\varvec{\alpha }} \otimes \mathcal {S}^{n_0}(s_1) \rangle \end{aligned}$$

(4)

for some $n_0 \in \mathbb {N}$ and a positive mass $\overrightarrow{\varvec{\alpha }}$.

Proof

Let $\gamma \in \mathbf {2}^\mathbb {N}$ such that $\{ \sigma _1, \sigma _2 \} \ge \{\gamma \} \ge \{ \tau _1, \tau _2 \}$. The stream $\gamma$ is not ultimately periodic as its transducts $\tau _1$ and $\tau _2$ are not. By Theorem 38 there exists $n_0 \in \mathbb {N}$ and a positive mass $\overrightarrow{\varvec{\alpha }}$ such that $\gamma \equiv \langle \overrightarrow{\varvec{\alpha }} \otimes \mathcal {S}^{n_0}(s_1) \rangle$. Since equivalent streams behave the same with respect to transducibility, without loss of generality we may assume that $\gamma = \langle \overrightarrow{\varvec{\alpha }} \otimes \mathcal {S}^{n_0}(s_1) \rangle$. Moreover, by Lemma 34 we have

. $\square$

Lemma 47

Assume that $\{ \sigma _1, \sigma _2 \} \ge \{\gamma \} \ge \{ \tau _1, \tau _2 \}$ for some stream $\gamma \in \mathbf {2}^\mathbb {N}$. Then we have $\{ \sigma _1, \sigma _2 \} \ge \{\gamma \} \ge \{ \tau _1, \tau _2 \}$ for some $\gamma$ such that

$$\begin{aligned} \gamma&= \langle \overrightarrow{\varvec{\alpha }} \otimes \mathcal {S}^{z}(s_1) \rangle \\ \mathcal {S}^{m}(t_1)&= \varvec{\delta } \oplus ( (\overrightarrow{\varvec{\beta }} \otimes \overrightarrow{\varvec{\alpha }}) \otimes {\mathcal {S}^{z}(s_1)} ) \\ \mathcal {S}^{m'}(t_2)&= \varvec{\delta '} \oplus ( (\overrightarrow{\varvec{\beta '}} \otimes \overrightarrow{\varvec{\alpha }}^{(r)}) \otimes {\mathcal {S}^{z'}(s_1)} ) \end{aligned}$$

for some $z,z' \in \mathbb {N}$ with $z \le z'$, positive masses $\overrightarrow{\varvec{\alpha }}, \overrightarrow{\varvec{\beta }}, \overrightarrow{\varvec{\beta '}}$, displacements $\varvec{\delta } \in \mathbb {Q}^{|\overrightarrow{\varvec{\beta }}|}$ and $\varvec{\delta '} \in \mathbb {Q}^{|\overrightarrow{\varvec{\beta '}}|}$, and $r \in \{0,\ldots ,|\overrightarrow{\varvec{\alpha }}|-1 \}$.

Moreover, we may assume that the following conditions hold:

$$\begin{aligned}&|\overrightarrow{\varvec{\alpha }}| \text { is even, } ||\overrightarrow{\varvec{\beta }}|| = ||\overrightarrow{\varvec{\beta '}}|| = |\overrightarrow{\varvec{\alpha }}|, \\&z' - z \equiv \sum _{i = 0}^{r-1} |\varvec{\alpha _i}| ({\text {mod}\,} ||\overrightarrow{\varvec{\alpha }}||), \end{aligned}$$

where $\overrightarrow{\varvec{\alpha }} = \langle \varvec{\alpha _0},\ldots ,\varvec{\alpha _{\ell -1}}\rangle$.

Proof

Let $\gamma \in \mathbf {2}^\mathbb {N}$ such that $\{ \sigma _1, \sigma _2 \} \ge \{\gamma \} \ge \{ \tau _1, \tau _2 \}$. By Lemma 46 we may assume that $\gamma = \langle \overrightarrow{\varvec{\alpha '}} \otimes \mathcal {S}^{n_0}(s_1) \rangle$ for some $n_0 \in \mathbb {N}$ and a positive mass $\overrightarrow{\varvec{\alpha '}}$ such that

.

Since $\gamma \ge \tau _1$ and $\gamma \ge \tau _2$, Theorem 39 yields

$$\begin{aligned} \mathcal {S}^{m}(t_1)&= \varvec{\delta } \oplus ( \overrightarrow{\varvec{\beta }} \otimes \mathcal {S}^{n_1}(\overrightarrow{\varvec{\alpha '}} \otimes \mathcal {S}^{n_0}(s_1)) ) , \nonumber \\ \mathcal {S}^{m'}(t_2)&= \varvec{\delta '} \oplus ( \overrightarrow{\varvec{\beta '}} \otimes \mathcal {S}^{n_2}(\overrightarrow{\varvec{\alpha '}} \otimes \mathcal {S}^{n_0}(s_1)) ) . \end{aligned}$$

(5)

for some $m,m',n_1,n_2 \in \mathbb {N}$, masses $\overrightarrow{\varvec{\beta }},\overrightarrow{\varvec{\beta '}}$ and $\varvec{\delta } \in \mathbb {Q}^{|\overrightarrow{\varvec{\beta }}|}$, $\varvec{\delta '} \in \mathbb {Q}^{|\overrightarrow{\varvec{\beta '}}|}$. Without loss of generality $n_1 \le n_2$, for otherwise we can take shifts (of left- and right-hand side) in (5). Moreover, we may assume that

• (i) $|\overrightarrow{\varvec{\alpha '}}|$ is even, for otherwise we can use $\overrightarrow{\varvec{\alpha '}}^2$ instead of $\overrightarrow{\varvec{\alpha '}}$, and

• (ii) $||\overrightarrow{\varvec{\beta }}|| = ||\overrightarrow{\varvec{\beta '}}|| = |\overrightarrow{\varvec{\alpha '}}|$, for otherwise we can unfold $\overrightarrow{\varvec{\alpha '}}$, $\overrightarrow{\varvec{\beta }}$, $\overrightarrow{\varvec{\beta '}}$, $\varvec{\delta }$ and $\varvec{\delta '}$ to the least common multiple of $||\varvec{\beta }||$, $||\overrightarrow{\varvec{\beta '}}||$, $|\overrightarrow{\varvec{\alpha '}}|$.

There exist unique $h_1,h_2 \in \mathbb {N}$ and $h_1', h_2' \in \{0,\ldots ,|\overrightarrow{\varvec{\alpha '}}|-1 \}$ such that

$$\begin{aligned} n_1 = h_1 |\overrightarrow{\varvec{\alpha '}}| + h_1'&n_2 = h_2 |\overrightarrow{\varvec{\alpha '}}| + h_2'. \end{aligned}$$

Let $\overrightarrow{\varvec{\alpha '}} = \langle \varvec{\alpha '_0},\ldots ,\varvec{\alpha '_{\ell -1}}\rangle$ and define

$$\begin{aligned} z = n_0 + h_1 ||\overrightarrow{\varvec{\alpha '}}|| + \sum _{i = 0}^{h_1'-1} |\varvec{\alpha '_i}|,&z' = n_0 + h_2 ||\overrightarrow{\varvec{\alpha '}}|| + \sum _{i = 0}^{h_2'-1} |\varvec{\alpha '_i}|. \end{aligned}$$

From $n_1 \le n_2$ follows that $h_1 \le h_2$ and $z \le z'$. Then by Lemma 19, we have

$$\begin{aligned} \mathcal {S}^{m}(t_1)&= \varvec{\delta } \oplus ( \overrightarrow{\varvec{\beta }} \otimes (\overrightarrow{\varvec{\alpha '}}^{(h_1')} \otimes \mathcal {S}^{z}(s_1)) ), \\ \mathcal {S}^{m'}(t_2)&= \varvec{\delta '} \oplus ( \overrightarrow{\varvec{\beta '}} \otimes (\overrightarrow{\varvec{\alpha '}}^{(h_2')} \otimes \mathcal {S}^{z'}(s_1)) ). \end{aligned}$$

Let $\overrightarrow{\varvec{\alpha }} = \overrightarrow{\varvec{\alpha '}}^{(h_1')}$. Note that $|\overrightarrow{\varvec{\alpha }}| = |\overrightarrow{\varvec{\alpha '}}|$, and thus, properties (i) and (ii) are not affected. Let $r \in \{0,\ldots ,|\overrightarrow{\varvec{\alpha }}|-1 \}$ such that $h_1' + r \equiv h_2' ({\text {mod}\,} |\overrightarrow{\varvec{\alpha }}|)$. Then $\overrightarrow{\varvec{\alpha }}^{(r)} = \overrightarrow{\varvec{\alpha '}}^{(h_2')}$ and we have

$$\begin{aligned} \mathcal {S}^{m}(t_1)&= \varvec{\delta } \oplus ( (\overrightarrow{\varvec{\beta }} \otimes \overrightarrow{\varvec{\alpha }}) \otimes {\mathcal {S}^{z}(s_1)} ), \nonumber \\ \mathcal {S}^{m'}(t_2)&= \varvec{\delta '} \oplus ( (\overrightarrow{\varvec{\beta '}} \otimes \overrightarrow{\varvec{\alpha }}^{(r)}) \otimes {\mathcal {S}^{z'}(s_1)} ) \end{aligned}$$

(6)

by Lemma 24. Moreover, $\langle \gamma \rangle \equiv \langle \mathcal {S}^{n_1}(\gamma ) \rangle$ and by Lemma 19:

$$\begin{aligned} \mathcal {S}^{n_1}(\gamma ) = \mathcal {S}^{n_1}(\overrightarrow{\varvec{\alpha '}} \otimes \mathcal {S}^{n_0}(s_1)) = \overrightarrow{\varvec{\alpha }} \otimes \mathcal {S}^{z}(s_1). \end{aligned}$$

So, without loss of generality, we can take $\gamma = \overrightarrow{\varvec{\alpha }} \otimes \mathcal {S}^{z}(s_1)$.

Since $h_1 \le h_2$,

$$\begin{aligned} z - z' \equiv \sum _{i = 0}^{h_1'-1} |\varvec{\alpha '_i}| - \sum _{i = 0}^{h_2'-1} |\varvec{\alpha '_i}| \equiv -\sum _{i = h_1'}^{h_2'-1} |\varvec{\alpha '_i}| \equiv -\sum _{i = 0}^{r-1} |\varvec{\alpha _i}| ({\text {mod}\,} ||\overrightarrow{\varvec{\alpha }}||). \end{aligned}$$

This concludes the proof. $\square$

The function $s_1$ is an alternating interleaving of $t_1(n) = 2^{2^n}$ and $t_2(n) = 3^{3^{3^n}}$; we will speak of white and black blocks, respectively. So, the white blocks are those at even positions, and the black blocks are at the odd positions in $\langle s_1 \rangle$. The following lemma investigates how $\langle t_1 \rangle$ can arise as a transduct of $\langle s_1 \rangle$. It states that, any transduction that transforms $\langle s_1 \rangle$ into $\langle t_1 \rangle$ has the following properties:

• (a) It must erase all black blocks; so, all the blocks of length $3^{3^{3^{n}}}$ must be multiplied by 0.

• (b) It cannot erase (or merge) any of the white blocks of length $2^{2^n}$.

A violation of (a) or (b) would result in a transduct whose block size grows too quickly, that is, more than a constant factor faster than $t_1$.

Lemma 48

Assume that

$$\begin{aligned} \mathcal {S}^{m}(t_1) = \varvec{\delta } \oplus ( \overrightarrow{\varvec{\tau }} \otimes {\mathcal {S}^{z}(s_1)} ) \end{aligned}$$

(7)

for some $m,z \in \mathbb {N}$, $\overrightarrow{\varvec{\tau }} = \langle \varvec{\tau _0},\ldots ,\varvec{\tau _{\ell '-1}}\rangle$ a mass and $\varvec{\delta } \in \mathbb {Q}^{|\overrightarrow{\varvec{\tau }}|}$. Moreover, assume that $||\overrightarrow{\varvec{\tau }}||$ is even. Then:

• (i) $\forall i \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \}$: $\tau |_{i} = 0$$\iff$$z + i$ is odd.

• (ii) If z is even, then $\forall i \in \{0,\ldots ,\ell '-1 \}$: $\varphi (\overrightarrow{\varvec{\tau }},2i) = i$.

• (iii) If z is odd, then $\forall i \in \{0,\ldots ,\ell '-1 \}$: $\varphi (\overrightarrow{\varvec{\tau }},2i+1) = i$.

Proof

We start by showing that:

$$\begin{aligned} \tau |_{i} = 0 \text {for every }\,i \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \} \text {such that }\,z + i\,\text {is odd.} \end{aligned}$$

(8)

For a contradiction, assume that $\tau |_{k} \ne 0$ for some $k \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \}$ such that $z + k$ is odd. Let $\varvec{\delta } = \langle \delta _0,\ldots ,\delta _{\ell '-1}\rangle$.

From assumption (7) and Lemma 16 we obtain:

$$\begin{aligned} \mathcal {S}^{m}(t_1)(h |\overrightarrow{\varvec{\tau }}| + h')&= \delta _{h'} + \sum _{\begin{array}{c} i \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \} \\ \varphi (\overrightarrow{\varvec{\tau }},i) = h' \end{array}} \big (\; \tau |_{i} \cdot \mathcal {S}^{z}(s_1)(h ||\overrightarrow{\varvec{\tau }}|| + i) \;\big ) \end{aligned}$$

for every $h \in \mathbb {N}$ and $h' \in \{0,\ldots , |\overrightarrow{\varvec{\tau }}|-1 \}$. Take $h' = \varphi (\overrightarrow{\varvec{\tau }},k)$, then

$$\begin{aligned} \mathcal {S}^{m}(t_1)(h |\overrightarrow{\varvec{\tau }}| + h')&\ge \tau |_{k} \cdot \mathcal {S}^{z}(s_1)(h ||\overrightarrow{\varvec{\tau }}|| + k) \end{aligned}$$

and, hence,

$$\begin{aligned} t_1(m + h|\overrightarrow{\varvec{\tau }}| + h') \ge&\ \tau |_{k} \cdot s_1(z + h ||\overrightarrow{\varvec{\tau }}|| + k) = \tau |_{k} \cdot t_2(\frac{z + h ||\overrightarrow{\varvec{\tau }}|| + k - 1}{2}) \end{aligned}$$

(9)

since $z + k$ is odd and $||\overrightarrow{\varvec{\tau }}||$ is even. Recall that $t_1(n) = 2^{2^n}$ and $t_2(n) = 3^{3^{3^n}}$. So, for large enough h, the formula on the right grows much faster than that on the left-hand side of the inequality. Thus, the inequality (9) cannot hold for all $h \in \mathbb {N}$. This is a contradiction, and we have established that (8) holds.

Thus, every second entry of $\varvec{\tau _0} \mathrel {;}\cdots \mathrel {;}\varvec{\tau _{\ell '-1}}$ is 0. However, none of the weights $\varvec{\tau _0}$, ..., $\varvec{\tau _{\ell '-1}}$ is zero since the left-hand side of (7) grows to infinity. So, each of these weights must contain a non-zero entry. It follows that $|\overrightarrow{\varvec{\tau }}| \le ||\overrightarrow{\varvec{\tau }}|| / 2$.

Next, we show that:

$$\begin{aligned} |\overrightarrow{\varvec{\tau }}| = ||\overrightarrow{\varvec{\tau }}|| / 2. \end{aligned}$$

(10)

For a contradiction, assume $|\overrightarrow{\varvec{\tau }}| < ||\overrightarrow{\varvec{\tau }}|| / 2$. Let $\ell _0 = |\varvec{\tau _0}|$. So,

$$\begin{aligned} \varvec{\tau _0} = \langle \tau |_{0},\tau |_{1},\ldots ,\tau |_{\ell _0-1}\rangle \end{aligned}$$

Since $\varvec{\tau _0}$ is not zero, it holds that $\tau |_{k} > 0$ for some $k \in \{0,\ldots ,\ell _0-1 \}$. Then $z + k$ is even by (8). Let $h' = \varphi (\overrightarrow{\varvec{\tau }},k)$, then as above we have for every $h \in \mathbb {N}$:

$$\begin{aligned} t_1(m + h|\overrightarrow{\varvec{\tau }}| + h') \ge&\ \tau |_{k} \cdot s_1(z + h ||\overrightarrow{\varvec{\tau }}|| + k) = \tau |_{k} \cdot t_1(\frac{z + h ||\overrightarrow{\varvec{\tau }}|| + k}{2}) \end{aligned}$$

since $z + k$ is even and $||\overrightarrow{\varvec{\tau }}||$ is even. Therefore,

$$\begin{aligned} 2^{2^{m + h|\overrightarrow{\varvec{\tau }}| + h'}} \ge&\ \tau |_{k} \cdot 2^{2^{\frac{z}{2} + h \frac{||\overrightarrow{\varvec{\tau }}||}{2} + \frac{k}{2}}}. \end{aligned}$$

However, $|\overrightarrow{\varvec{\tau }}| < ||\overrightarrow{\varvec{\tau }}||/2$. Hence, the inequality cannot hold for arbitrary large h. This is a contradiction, and, thus, the claim (10) holds.

Let us summarise. Every second entry of $\varvec{\tau _0} \mathrel {;}\cdots \mathrel {;}\varvec{\tau _{\ell '-1}}$ is 0 by (8), and we have $\ell ' = |\overrightarrow{\varvec{\tau }}| = ||\overrightarrow{\varvec{\tau }}|| / 2$ by (10). Thus, $\varvec{\tau _0} \mathrel {;}\cdots \mathrel {;}\varvec{\tau _{\ell '-1}}$ contains at most $\ell '$ non-zero entries. On the other hand, each weight $\varvec{\tau _0}$, ..., $\varvec{\tau _{\ell '-1}}$ contains a non-zero entry. Therefore, we conclude that $\varvec{\tau _0} \mathrel {;}\cdots \mathrel {;}\varvec{\tau _{\ell '-1}}$ contains precisely $\ell '$ non-zero entries, and each weight $\varvec{\tau _0}$, ..., $\varvec{\tau _{\ell '-1}}$ contains precisely one them. From (8) we obtain:

$$\begin{aligned} \tau |_{i} = 0 \quad \iff \quad z + i\,\text {is odd} \end{aligned}$$

for every $i \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \}$. Since each weight contains precisely one non-zero entry, we conclude that:

• (i) If z is even, then $\forall i \in \{0,\ldots ,\ell '-1 \}$: $\varvec{\tau _i}$ contains $\tau |_{2i}$.

• (ii) If z is odd, then $\forall i \in \{0,\ldots ,\ell '-1 \}$: $\varvec{\tau _i}$ contains $\tau |_{2i+1}$.

This concludes the proof. $\square$

The following lemma investigates how $t_2$ can be obtained as a transduct of $s_1$. Roughly speaking, the lemma states that the values of $s_1$ at odd indices are copied, giving rise to $t_2$.

Lemma 49

Assume that

$$\begin{aligned} \mathcal {S}^{m}(t_2) = \varvec{\delta } \oplus ( \overrightarrow{\varvec{\tau }} \otimes {\mathcal {S}^{z}(s_1)} ) \end{aligned}$$

(11)

for some $m,z \in \mathbb {N}$, $\overrightarrow{\varvec{\tau }} = \langle \varvec{\tau _0},\ldots ,\varvec{\tau _{\ell '-1}}\rangle$ a mass and $\varvec{\delta } \in \mathbb {Q}^{|\tau |}$. Moreover, assume that $||\overrightarrow{\varvec{\tau }}||$ is even. Then:

• (i) $\forall i \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \}$: $\tau |_{i} > 0$ if $z + i$ is odd.

• (ii) If z is even, then $\forall i \in \{0,\ldots ,\ell '-1 \}$: $\varphi (\overrightarrow{\varvec{\tau }},2i+1) = i$.

• (iii) If z is odd, then$\forall i \in \{0,\ldots ,\ell '-1 \}$: $\varphi (\overrightarrow{\varvec{\tau }},2i) = i$.

Proof

First, we show that every weight $\varvec{\tau _0},\ldots ,\varvec{\tau _{\ell -1}}$ contains some $\tau |_{i}$ such that $\tau |_{i} > 0$ and $z+i$ is odd. More precisely, we prove:

$$\begin{aligned} \begin{aligned}&\forall h' \in \{0,\ldots ,|\overrightarrow{\varvec{\tau }}|-1 \}.\, \exists i \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \}.\, \\&\varphi (\overrightarrow{\varvec{\tau }},i) = h' \;\wedge \; \tau |_{i} > 0 \;\wedge \;\,z+i\,\text {is odd} \end{aligned} \end{aligned}$$

(12)

For a contradiction, we assume that there exists $h' \in \{0,\ldots ,|\overrightarrow{\varvec{\tau }}|-1 \}$ such that

($\dagger$):

$\tau |_{i} = 0$ for every $i \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \}$ for which $\varphi (\overrightarrow{\varvec{\tau }},i) = h'$ and $z+i$ is odd.

From assumption (11) and Lemma 16 we obtain:

$$\begin{aligned} \mathcal {S}^{m}(t_2)(h |\overrightarrow{\varvec{\tau }}| + h') =&\ \delta _{h'} + \sum _{\begin{array}{c} i \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \} \\ \varphi (\overrightarrow{\varvec{\tau }},i) = h' \end{array}} \big (\; \tau |_{i} \cdot s_1(z + h ||\overrightarrow{\varvec{\tau }}|| + i) \;\big ) \\ =&\ \delta _{h'} + \sum _{\begin{array}{c} i \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \} \\ \varphi (\overrightarrow{\varvec{\tau }},i) = h' \\ z+i\, \text {is even} \end{array}} \big (\; \tau |_{i} \cdot t_1(\frac{z + h ||\overrightarrow{\varvec{\tau }}|| + i}{2}) \;\big ) \quad (\text {by} (\dagger )) \end{aligned}$$

for every $h \in \mathbb {N}$ since $||\overrightarrow{\varvec{\tau }}||$ is even. Thus, for

$$\begin{aligned} c = \sum _{\begin{array}{c} i \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \} \\ \varphi (\overrightarrow{\varvec{\tau }},i) = h' \\ z+i\, \text {is even} \end{array}} \tau |_{i}, \end{aligned}$$

we have

$$\begin{aligned} t_2(m + h|\overrightarrow{\varvec{\tau }}| + h') \le&\ \delta _{h'} + c \cdot t_1(\frac{z + h ||\overrightarrow{\varvec{\tau }}|| + ||\overrightarrow{\varvec{\tau }}||}{2}) \end{aligned}$$

(13)

for every $h \in \mathbb {N}$. Recall that $t_1(n) = 2^{2^n}$ and $t_2(n) = 3^{3^{3^n}}$. Thus, for large enough h, the inequality (13) cannot hold. This is a contradiction, and hence, claim (12) holds.

As $||\overrightarrow{\varvec{\tau }}||$ is even, from (12) it follows that $|\overrightarrow{\varvec{\tau }}| \le ||\overrightarrow{\varvec{\tau }}||/2$. We show that:

$$\begin{aligned} |\overrightarrow{\varvec{\tau }}| = ||\overrightarrow{\varvec{\tau }}|| / 2. \end{aligned}$$

(14)

For a contradiction, assume $|\overrightarrow{\varvec{\tau }}| < ||\overrightarrow{\varvec{\tau }}|| / 2$. Let $\ell _0 = |\varvec{\tau _0}|$. So,

$$\begin{aligned} \varvec{\tau _0} = \langle \tau |_{0},\tau |_{1},\ldots ,\tau |_{\ell _0-1}\rangle . \end{aligned}$$

By (12), $\tau |_{k} > 0$ for some $k \in \{0,\ldots ,\ell _0-1 \}$ such that $z + k$ is odd. Let $h' = \varphi (\overrightarrow{\varvec{\tau }},k)$. From assumption (11) and Lemma 16 it follows that:

$$\begin{aligned} t_2(m + h|\overrightarrow{\varvec{\tau }}| + h') \ge&\ \tau |_{k} \cdot s_1(z + h ||\overrightarrow{\varvec{\tau }}|| + k) = \tau |_{k} \cdot t_2(\frac{z + h ||\overrightarrow{\varvec{\tau }}|| + k - 1}{2}) \end{aligned}$$

for every $h \in \mathbb {N}$, and hence,

$$\begin{aligned} t_2(m + h' + h|\overrightarrow{\varvec{\tau }}|) \ge&\ \tau |_{k} \cdot t_2(\frac{z+k-1}{2} + h \frac{||\overrightarrow{\varvec{\tau }}||}{2}). \end{aligned}$$

However, $t_2(n) = 3^{3^{3^n}}$ and we have assumed $|\overrightarrow{\varvec{\tau }}| < ||\overrightarrow{\varvec{\tau }}||/2$. Thus, the inequality cannot hold for all $h \in \mathbb {N}$. This is a contradiction, and hence the claim (14) holds.

So, $||\overrightarrow{\varvec{\tau }}||$ is even, $\ell ' = |\overrightarrow{\varvec{\tau }}| = ||\overrightarrow{\varvec{\tau }}||/2$ and every weight $\varvec{\tau _0}$, ..., $\varvec{\tau _{\ell '-1}}$ contains some $\tau |_{i}$ such that $z+i$ is odd. There are precisely $||\overrightarrow{\varvec{\tau }}||/2$ elements $\tau |_{i}$ such that $z+i$ is odd, and thus each weight contains precisely one of them. This implies that

• (i) If z is even, then $\forall i \in \{0,\ldots ,\ell '-1 \}$: $\varvec{\tau _i}$ contains $\tau |_{2i}$.

• (ii) If z is odd, then $\forall i \in \{0,\ldots ,\ell '-1 \}$: $\varvec{\tau _i}$ contains $\tau |_{2i+1}$.

Moreover, using (12) we can conclude that

$$\begin{aligned} \tau |_{i} > 0 \quad \iff \quad z + i\, \text {is odd} \end{aligned}$$

(15)

for every $i \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \}$. $\square$

Lemma 50

There exists no $\gamma \in \mathbf {2}^\mathbb {N}$ such that $\{ \sigma _1, \sigma _2 \} \ge \{\gamma \} \ge \{ \tau _1, \tau _2 \}$.

Proof

For a contradiction, assume that such $\gamma \in \mathbf {2}^\mathbb {N}$ exists. Then, by Lemma 47, we have $\{ \sigma _1, \sigma _2 \} \ge \{\gamma \} \ge \{ \tau _1, \tau _2 \}$ for some $\gamma$ such that

$$\begin{aligned} \gamma&= \langle \overrightarrow{\varvec{\alpha }} \otimes \mathcal {S}^{z}(s_1) \rangle \\ \mathcal {S}^{m}(t_1)&= \varvec{\delta } \oplus ( (\overrightarrow{\varvec{\beta }} \otimes \overrightarrow{\varvec{\alpha }}) \otimes {\mathcal {S}^{z}(s_1)} ) \\ \mathcal {S}^{m'}(t_2)&= \varvec{\delta '} \oplus ( (\overrightarrow{\varvec{\beta '}} \otimes \overrightarrow{\varvec{\alpha }}^{(r)}) \otimes {\mathcal {S}^{z'}(s_1)} ) \end{aligned}$$

for some $z,z' \in \mathbb {N}$ with $z \le z'$, positive masses $\overrightarrow{\varvec{\alpha }}, \overrightarrow{\varvec{\beta }}, \overrightarrow{\varvec{\beta '}}$, $\varvec{\delta } \in \mathbb {Q}^{|\overrightarrow{\varvec{\beta }}|}$ and $\varvec{\delta '} \in \mathbb {Q}^{|\overrightarrow{\varvec{\beta '}}|}$, and $r \in \{0,\ldots ,|\overrightarrow{\varvec{\alpha }}|-1 \}$.

Moreover, we may assume that $|\overrightarrow{\varvec{\alpha }}|$ is even, $||\overrightarrow{\varvec{\beta }}|| = ||\overrightarrow{\varvec{\beta '}}|| = |\overrightarrow{\varvec{\alpha }}|$ and

$$\begin{aligned} z' - z \equiv R ({\text {mod}\,} ||\overrightarrow{\varvec{\alpha }}||), \end{aligned}$$

where $\overrightarrow{\varvec{\alpha }} = \langle \varvec{\alpha _0},\ldots ,\varvec{\alpha _{\ell -1}}\rangle$ and $R = \sum _{i = 0}^{r-1} |\varvec{\alpha _i}|$.

The proof now proceeds in three parts, namely,

• (A) We show that $\alpha |_{i} > 0$ for every $i \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \}$.

• (B) We show that $|\varvec{\alpha _i}| = 1$ for every $i \in \{0,\ldots ,\ell -1 \}$.

• (C) We put things together and conclude.

Part (A): Let $\overrightarrow{\varvec{\tau }} = \overrightarrow{\varvec{\beta }} \otimes \overrightarrow{\varvec{\alpha }}$ and $\overrightarrow{\varvec{\tau '}} = \overrightarrow{\varvec{\beta '}} \otimes \overrightarrow{\varvec{\alpha }}^{(r)}$. Then

$$\begin{aligned} \mathcal {S}^{m}(t_1)&= \varvec{\delta } \oplus ( \overrightarrow{\varvec{\tau }} \otimes {\mathcal {S}^{z}(s_1)} ) \\ \mathcal {S}^{m'}(t_2)&= \varvec{\delta '} \oplus ( \overrightarrow{\varvec{\tau '}} \otimes {\mathcal {S}^{z'}(s_1)} ). \end{aligned}$$

By definition of $\otimes$, $||\overrightarrow{\varvec{\tau }}|| = ||\overrightarrow{\varvec{\tau '}}|| = ||\overrightarrow{\varvec{\alpha }}||$ and, for every $i \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \}$,

$$\begin{aligned} \tau |_{i}&= \beta |_{\varphi (\overrightarrow{\varvec{\alpha }},i)} \cdot \alpha |_{i} \end{aligned}$$

(16)

$$\begin{aligned} \tau '|_{i}&= \beta '|_{\varphi (\overrightarrow{\varvec{\alpha }}^{(r)},i)} \cdot \alpha ^{(r)}|_{i}. \end{aligned}$$

(17)

By Lemma 48,

$$\begin{aligned} \tau |_{i} > 0 \iff z + i\,\text {is even} \end{aligned}$$

(18)

for every $i \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \}$; thus, by (16),

$$\begin{aligned} z + i\, \text {is even} \;\mathrel {\Longrightarrow }\; \alpha |_{i} > 0. \end{aligned}$$

(19)

By Lemma 49, $z' + j\, \text {is odd} \;\mathrel {\Longrightarrow }\; \tau '|_{j} > 0$ for every $j \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \}$; thus, by (17),

$$\begin{aligned} z' + j\, \text {is odd} \;\mathrel {\Longrightarrow }\; \alpha ^{(r)}|_{j} > 0. \end{aligned}$$

(20)

By the definitions of R and $\alpha ^{(r)}|_{j}$,

$$\begin{aligned} \alpha |_{i} = \alpha ^{(r)}|_{j}&\Leftarrow i \equiv j + R ({\text {mod}\,} ||\overrightarrow{\varvec{\alpha }}||) \nonumber \\&\Leftrightarrow i \equiv j + z' - z ({\text {mod}\,} ||\overrightarrow{\varvec{\alpha }}||) \nonumber \\&\Leftrightarrow z + i \equiv z' + j ({\text {mod}\,} ||\overrightarrow{\varvec{\alpha }}||) \end{aligned}$$

(21)

By (20), (21) and since $||\overrightarrow{\varvec{\alpha }}||$ is even,

$$\begin{aligned} z + i\, \text {is odd} \;\mathrel {\Longrightarrow }\; \alpha |_{i} > 0. \end{aligned}$$

(22)

for every $i \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \}$.

From (19) and (22) it follows that:

$$\begin{aligned} \forall i \in \{0,\ldots ,||\overrightarrow{\varvec{\tau }}||-1 \}.\; \alpha |_{i} > 0. \end{aligned}$$

(23)

Part (B): We show that

$$\begin{aligned} \forall i \in \{0,\ldots ,\ell -1 \}.\; |\varvec{\alpha _i}| = 1. \end{aligned}$$

(24)

For a contradiction, assume that $|\varvec{\alpha _k}| > 1$ for some $k \in \{0,\ldots ,\ell -1 \}$. Let

$$\begin{aligned} k_1&= |\varvec{\alpha _0}| + |\varvec{\alpha _1}| + \cdots + |\varvec{\alpha _{k-1}}|, \\ k_2&= k_1 + |\varvec{\alpha _k}| - 1. \end{aligned}$$

Then $k_1 < k_2$, $\varvec{\alpha _k} = \langle \alpha |_{k_1},\ldots ,\alpha |_{k_2}\rangle$, and $\varphi (\overrightarrow{\varvec{\alpha }},i) = k$ for every $i \in \{k_1,\ldots ,k_2 \}$. Let $h,h' \in \{k_1,\ldots ,k_2 \}$ such that $z + h$ is even and $z + h'$ is odd. Since $z + h$ is even, we get $\tau |_{h} > 0$ from (18). As $\varphi (\overrightarrow{\varvec{\alpha }},h) = k$, we conclude $\beta |_{k} > 0$ by (16). However, by (16) and (23), $\tau |_{i} > 0$ for every $i \in \{k_1,\ldots ,k_2 \}$; thus also for $i = h'$. This contradicts (18) since $z + h'$ is odd. Hence, claim (24) holds.

Part (C): Recall that

$$\begin{aligned} \gamma = \langle \overrightarrow{\varvec{\alpha }} \otimes \mathcal {S}^{z}(s_1) \rangle . \end{aligned}$$

By Theorem 39,

$$\begin{aligned} \mathcal {S}^{n_0}( \overrightarrow{\varvec{\alpha }} \otimes \mathcal {S}^{z}(s_1) ) = \varvec{\delta } \oplus ( \overrightarrow{\varvec{\xi }} \otimes \mathcal {S}^{m_0}(s_2) ) \end{aligned}$$

for some $n_0, m_0 \in \mathbb {N}$, a mass $\overrightarrow{\varvec{\xi }} = \langle \varvec{\xi _0},\ldots ,\varvec{\xi _{\ell '-1}}\rangle$ and $\varvec{\delta } \in \mathbb {Q}^{|\overrightarrow{\varvec{\xi }}|}$.

In parts (A) and (B) of this proof, we have established that $|\varvec{\alpha _i}| = 1$ for every $i \in \{0,\ldots ,\ell -1 \}$. As the functions $s_1$ and $s_2$ are both obtained by interleaving $t_1$ and $t_2$, we can apply the same reasoning to transductions of $\langle s_2 \rangle$ as we have done for $\langle s_1 \rangle$. So, by reasoning as above (using analogous versions of Lemmas 48 and 49), we conclude that $|\varvec{\xi _i}| = 1$ for every $i \in \{0,\ldots ,\ell '-1 \}$.

By Lemma 19, we get

$$\begin{aligned} \mathcal {S}^{n_0}( \overrightarrow{\varvec{\alpha }} \otimes \mathcal {S}^{z}(s_1) ) = \overrightarrow{\varvec{\alpha }}^{(n_0)} \otimes \mathcal {S}^{z+n_0}(s_1) = \varvec{\delta } \oplus ( \overrightarrow{\varvec{\xi }} \otimes \mathcal {S}^{m_0}(s_2) ) \end{aligned}$$

since $|\varvec{\alpha _i}| = 1$ for every $i \in \{0,\ldots ,\ell -1 \}$.

Thus,

$$\begin{aligned} \overrightarrow{\varvec{\zeta }} \otimes \mathcal {S}^{n}(s_1) = \varvec{\delta } \oplus ( \overrightarrow{\varvec{\xi }} \otimes \mathcal {S}^{m}(s_2) ) \end{aligned}$$

(25)

for $\zeta = \overrightarrow{\varvec{\alpha }}^{(n_0)}$, $n = z + n_0$ and $m = m_0$. Both $\overrightarrow{\varvec{\zeta }}, \overrightarrow{\varvec{\xi }}$ are positive masses consisting only of weights of length 1, and $|\varvec{\delta }| = |\overrightarrow{\varvec{\xi }}|$.

Without loss of generality we may assume that:

• (i) n is even, for otherwise we can take a shift $\mathcal {S}^{}(\;\cdot \;)$ on left and right;

• (ii) $|\overrightarrow{\varvec{\zeta }}| = |\overrightarrow{\varvec{\xi }}| = |\varvec{\delta }|$ and $|\overrightarrow{\varvec{\zeta }}|$ is even; otherwise, we unfold $\overrightarrow{\varvec{\zeta }}$, $\overrightarrow{\varvec{\xi }}$ and $\varvec{\delta }$.

Then

$$\begin{aligned} \overrightarrow{\varvec{\zeta }}&= \langle \langle \zeta _0\rangle ,\ldots ,\langle \zeta _{\ell -1}\rangle \rangle \\ \overrightarrow{\varvec{\xi }}&= \langle \langle \xi _0\rangle ,\ldots ,\langle \xi _{\ell -1}\rangle \rangle \\ \varvec{\delta }&= \langle \langle \delta _0\rangle ,\ldots ,\langle \delta _{\ell -1}\rangle \rangle \end{aligned}$$

for some even $\ell \in \mathbb {N}$, $\zeta _0,\ldots ,\zeta _{\ell -1} > 0$ and $\xi _0,\ldots ,\xi _{\ell -1} > 0$. From (25), we get

$$\begin{aligned} ( \overrightarrow{\varvec{\zeta }} \otimes \mathcal {S}^{n}(s_1) )(h\ell )&= ( \varvec{\delta } \oplus ( \overrightarrow{\varvec{\xi }} \otimes \mathcal {S}^{m}(s_2) ) )(h\ell ) \end{aligned}$$

for every $h \in \mathbb {N}$. We have

$$\begin{aligned} ( \overrightarrow{\varvec{\zeta }} \otimes \mathcal {S}^{n}(s_1) )(h\ell )&= \zeta _0 \cdot t_1((n + h\ell )/2) \\ ( \varvec{\delta } \oplus ( \overrightarrow{\varvec{\xi }} \otimes \mathcal {S}^{m}(s_2) ) )(h\ell )&= \delta _0 + \xi _0 \cdot s_2(m + h\ell ) \end{aligned}$$

and, hence,

$$\begin{aligned} \zeta _0 \cdot t_1((n + h\ell )/2) = \delta _0 + \xi _0 \cdot s_2(m + h\ell ) \end{aligned}$$

for every $h \in \mathbb {N}$. If m is even, then $s_2(m + h\ell ) = t_2((m + h\ell )/2)$. This gives a contradiction since $t_2$ grows much faster than $t_1$. Thus m must be odd, and

$$\begin{aligned}&\ \zeta _0 \cdot t_1((n + h\ell )/2) = \zeta _0 \cdot 2^{2^{(n + h\ell )/2}} \\&\ \parallel \\&\ \delta _0 + \xi _0 \cdot s_2(m + h\ell ) = \delta _0 + \xi _0 \cdot t_1((m + h\ell -1)/2) = \delta _0 + \xi _0 \cdot 2^{2^{(m + h\ell -1)/2}} \end{aligned}$$

for every $h \in \mathbb {N}$. From

$$\begin{aligned} \zeta _0 \cdot 2^{2^{(n + h\ell )/2}} = \delta _0 + \xi _0 \cdot 2^{2^{(m + h\ell -1)/2}} \end{aligned}$$

it follows that $(n + h\ell )/2 = (m + h\ell -1)/2$ and, thus, $m = n+1$.

Likewise, we get

$$\begin{aligned} ( \overrightarrow{\varvec{\zeta }} \otimes \mathcal {S}^{n}(s_1) )(h\ell +1)&= \zeta _1 \cdot t_2((n + h\ell )/2) \\ ( \varvec{\delta } \oplus ( \overrightarrow{\varvec{\xi }} \otimes \mathcal {S}^{m}(s_2) ) )(h\ell +1)&= \delta _1 + \xi _1 \cdot t_2((m + h\ell +1)/2) \end{aligned}$$

for every $h \in \mathbb {N}$. It follows that $(n + h\ell )/2 = (m + h\ell +1)/2$ and, thus, $m = n-1$.

We have reached a contradiction: $n-1 = m = n+1$, and, hence, our assumption must have been wrong. This concludes the proof. $\square$