Bowen’s Problem 32 and the conjugacy problem for systems with specification

The methods of mathematical logic can be useful in establishing impossibility results. For example, a descriptive set-theoretic complexity argument was used by Wojtaszczyk and Bourgain who solved Problem 49 from the Scottish book by establishing the non-existence of certain types of Banach spaces, see [Kec12, Section 33.26]. In a similar vein, the theory of complexity of Borel equivalence relations can be used to demonstrate the impossibility of classifying certain mathematical objects. An equivalence relation $E$ on a standard Borel space $X$ is smooth if there exists a Borel assignment $f\colon X\to Y$ of elements of another standard Borel space $Y$ to elements of $X$ which provides a complete classification of the equivalence relation $E$, i.e., two elements $x,y\in X$ are $E$-related if and only if $f(x)=f(y)$. The definition is broad enough to justify a Borel version of the Church–Turing thesis, namely that an isomorphism relation admits a concrete classification if and only if it is smooth. For example, recently Panagiotopoulos, Sparling and Christodoulou [PSC23] utilized this notion to show that there does not exist a concrete observable that is complete and Borel definable, solving a long-standing problem in general relativity.

Smooth equivalence relations are actually only at the beginning of a larger hierachy of descriptive set-theoretic complexity. Given two equivalence relations $E$ and $F$ on standard Borel spaces $X$ and $Y$, respectively, we say that $E$ is Borel-reducible to $F$, written $E\leq_{B}F$ if there exists a Borel map $f\colon X\to Y$ such that for $(x_{1},x_{2})\in X\times X$ we have $(x_{1},x_{2})\in E$ if and only if $(f(x_{1}),f(x_{2})))\in F$. The Borel complexity of an isomorphism problem measures how complicated the problem is in comparison with other equivalence relations, when we compare equivalence relations using Borel reductions. Equivalence relations which are Borel-reducible to the equality $=$ on the real numbers, or anything that can be coded by real numbers, are exactly the smooth ones. However, the hierarchy goes much higher. The next step is formed by the hyperfinite equivalence relations [DJK94], that is those which are induced by Borel actions of the group $\mathbb{Z}$. Another successor of $=$ is defined in terms of the Friedman–Stanley version of the Turing jump [FS89], and is denoted by $=^{+}$. The jump can be iterated and all of the countable iteration of ⁺ on $=$ are induced by Borel actions of the group $S_{\infty}$ of permutations of $\mathbb{N}$. The class of equivalence relations reducible to actions of $S_{\infty}$ is quite large (cf. the recent result of Paolini and Shelah [PS24]) but not every Borel equivalence relation is in that class. In [Hjo00a] Hjorth developed the theory of turbulence and showed that turbulent group actions are not Borel reducible to any Borel $S_{\infty}$-action. The theory of complexity of equivalence relations also continues in the class of equivalence relations induced by actions of more general groups than $S_{\infty}$ (cf. [Cle12, GK03, Sab16, Zie16]).

A lot of effort has been put in measuring the complexity of problems arising in dynamical systems. The breakthrough for measure-preserving systems came with the results of Foreman and Weiss [FW04] and of Foreman, Rudolph and Weiss [FRW11]. In [FW04] Foreman and Weiss showed that the conjugacy relation of ergodic transformations is turbulent and in [FRW11] Foreman, Rudolph and Weiss showed that the conjugacy relation of ergodic transformations is not Borel, and thus the classification problem in ergodic theory is intractable. In topological dynamics, Camerlo and Gao [CG01] proved that the conjugacy of Cantor systems is the most complicated among equivalence relation induced by actions of $S_{\infty}$ and for minimal Cantor systems it is shown in [DGRK⁺24] that the relation is not Borel.

In contrast, the conjugacy relation of symbolic systems is quite simple from the point of view of descriptive set theory. Since every isomorphism between symbolic systems is given by a block code [Hed69], the conjugacy of symbolic systems is a countable Borel equivalence relation, i.e. a Borel equivalence relation whose equivalence classes are countable. Clemens [Cle09] proved that for a finite alphabet $A$ the topological conjugacy of symbolic systems of $A^{\mathbb{Z}}$ is a universal countable Borel equivalence relation. In [GJS16] Gao, Jackson and Seward generalized it from subsystems of $A^{\mathbb{Z}}$ to subsystems of $A^{G}$ where $G$ is a countable group which is not locally finite, while for a locally finite group $G$ they showed that the conjugacy of subsystems of $A^{G}$ is hyperfinite. It remains unknown whether the conjugacy of minimal subsystems of $A^{\mathbb{Z}}$ is a universal countable Borel equivalence relation, which is connected to a conjecture of Thomas [Tho19, Conjecture 1.2] on the isomorphism of complete groups. In fact, it is not known [ST17, Question 1.3] whether the conjugacy relation restricted to Toeplitz systems is hyperfinite or not.

A special class of symbolic systems is formed by systems with specification, considered by Bowen [Bow71]. A dynamical system satisfies the specification property if for every $\varepsilon>0$ we can find $k\in\mathbb{N}$ such that given any collection of finite fragments of orbits, there exists a point which is $\varepsilon$-closely following these orbit segments and takes $k$ steps to switch between consecutive orbit segments (a formal definition is given in Section 3). Nowadays, the specification property in symbolic systems for general discrete groups goes also under the name of strong irreducibility, as discussed for example by Glasner, Tsankov, Weiss and Zucker [GTWZ21], Frisch and Tamuz [FT17] and Frisch, Seward and Zucker [FSZ24]. Around 1970’s Bowen wrote an influential list of open problems, which is now maintained on the webpage [Bowb]. Problem 32 [Bowa] asks to

classify symbolic systems with specification.

Several results in the direction of a classification have been obtained, as reported on the website [Bowa]. For example Bertrand [Ber88] proved that every symbolic system with specification is synchronized and Thomsen [Tho06] found a connection with the theory of countable state Markov chains. However, a complete classification has not been obtained. Buhanan and Kwapisz [BK14] proved a result suggesting that systems with specification are quite complicated. They considered the cocyclic shift spaces, which is a countable family of symbolic systems with specification and proved in [BK14, Theorem 1.1] that the problem of equality of cocyclic shift spaces is undecidable. However, the equality relation is a much simpler relation than the conjugacy on such systems. In this paper we prove the following, which shows that a classification with any concrete invariants is impossible.

In fact, in Theorem 5.9 we prove that the conjugacy relation of symbolic systems with specification is not hyperfinite and essentially the same proof shows that it is not treeable; see Theorem 6.4.

Next, we will look the conjugacy relation of pointed systems with the specification property and consider its complexity. It turns out that in order to compute the complexity for pointed Cantor systems with the specification property, we need to solve a problem posed in a paper of Ding and Gu [DG20].

In [DG20] Ding and Gu consider the equivalence relation $E_{\mathrm{cs}}$ defined on the space of metrics on $\mathbb{N}$, where two metrics are equivalent if the identity map on $\mathbb{N}$ extends to a homeomorphism of the completions of $\mathbb{N}$ with respect to those two metrics. The restriction of $E_{\mathrm{cs}}$ to the set of metrics whose completion is compact is denoted by $E_{\mathrm{csc}}$. This is a natural equivalence relation from the point of view of descriptive set theory, and it is interesting to ask what is its complexity. Indeed, Ding and Gu ask [DG20, Question 4.11] whether for a given countable ordinal $\alpha$ and a natural number $n$, the restriction of $E_{\mathrm{csc}}$ to the metrics whose completion is homeomorphic to $\omega^{1+\alpha}\cdot n+1$ is Borel-reducible to $=^{+}$. Even though this question does not seem directly connected to the topological conjugacy of systems with specification, we find a connection between the relation $E_{\mathrel{csc}}$ and Cantor systems, using a construction coming from the work of Williams [Wil84] and the work of Kaya [Kay17a] and we answer it in the positive, by showing a slightly stronger statement. By $\mathbb{X}_{0\textrm{-dim}}$ we denote the set of metrics on $\mathbb{N}$ whose completion is zero-dimensional. The result below implies in particular a positive answer to [DG20, Question 4.11].

Finally, in [BV23] Bruin and Vejnar also studied the conjugacy relation of pointed transitive systems

and asked [BV23, Table 1, Question 5.6] about the complexity of the conjugacy of pointed transitive homeomorphisms of the Hilbert cube. It turns out that the conjugacy of pointed transitive homeomorphisms of the Hilbert cube has the same complexity as the conjugacy relation of Hilbert cube systems with the specification property and in this paper we answer this question as follows.

In particular, the conjugacy of pointed transitive Hilbert cube systems is not classifiable by countable structures, as opposed to most other relations considered in [BV23].

In this paper, by a system, we mean a pair $(X,\varphi)$ where $X$ is a compact metric space and $\varphi$ is a homeomorphism of $X$. Given a point $x\in X$, its orbit is $O(x)=\{\varphi^{n}(x)\colon n\in\mathbb{Z}\}$ and its forward orbit is $\{\varphi^{n}(x)\colon n\geq 0\}$. A point $x\in X$ is called transitive if the forward orbit of $x$ is dense in $X$. A system $(X,\varphi)$ is transitive if there is a transitive point in $X$. If $X$ has no isolated points, then a system $(X,\varphi)$ is transitive if and only if there is a point in $X$ whose orbit is dense. A pointed transitive system $(X,\varphi,x)$ is a transitive system $(X,\varphi)$ together with a point $x$ whose forward orbit is dense. A subsystem of a system $(X,\varphi)$ is a system $(Y,\psi)$ such that $Y$ is a nonempty closed set satisfying $\varphi(Y)=Y$ and $\psi$ is the restriction of $\varphi$ to $Y$.

Two systems $(X,\varphi)$ and $(Y,\psi)$ are conjugate if there exists a homeomorphism $\rho\colon X\to Y$ such that $\rho\varphi=\psi\rho$. Two pointed systems $(X,\varphi,x)$ and $(Y,\psi,y)$ are conjugate if they are conjugate by $\rho$ such that $\rho(x)=y$.

A factor map from $(X,\sigma)$ to $(Y,\tau)$ is a continuous surjection $\pi$ from $X$ to $Y$, such that $\pi\sigma=\tau\pi$.

We say that a dynamical system $(Y,\tau)$ is equicontinuous if the family of functions $\{\tau^{n}:n\in\mathbb{Z}\}$ is equicontinuous. Every system $(X,\varphi)$ admits the unique maximal equicontinuous factor that is there exists an equicontinuous system $(Y,\tau)$ and a factor map $\pi$ from $(X,\varphi)$ to $(Y,\tau)$ such that if $\theta$ is a factor from $(X,\varphi)$ to an equicontinuous system $(Z,\rho)$, then there is a factor map $\eta$ from $(Y,\tau)$ to $(Z,\rho)$ satisfying $\pi=\eta\theta$.

For any compact space metric $X$, the shift map $\sigma\colon X^{\mathbb{Z}}\to X^{\mathbb{Z}}$ is defined for $x=(x(n))_{n\in\mathbb{Z}}\in X^{\mathbb{Z}}$ as $\sigma(x)=(\sigma(x)(n))_{n\in\mathbb{Z}}$, where $\sigma(x)(n)=x(n+1)$ for all $n\in\mathbb{Z}$. We call the system $(X^{\mathbb{Z}},\sigma)$ the full shift over $X$.

Given $z\in X^{\mathbb{Z}}$ and $p\in\mathbb{N}$ define the $p$-periodic part of $z$ as

and let ${\rm Per}(z)=\bigcup_{p\in\mathbb{N}}{\rm Per}_{p}(z)$. Also, we write ${\rm Aper}(z)=\mathbb{Z}\setminus{\rm Per}(z)$ for the aperiodic part of $z$. A sequence $z\in X^{\mathbb{Z}}$ is a Toeplitz sequence, if its aperiodic part ${\rm Aper}(z)$ is empty. A subsystem of the full shift over $X$ is a Toeplitz system if it is equal to the closure of the orbit of a Topelitz sequence $z\in X^{\mathbb{Z}}$.

By a symbolic system (over $A$) or shift space (over $A$) we mean a subsystem of the full shift $(A^{\mathbb{Z}},\sigma)$ where $A$ is a finite discrete space. In such a case, the set $A$ is referred to as the alphabet. By the classical result of Curtis, Hedlund, and Lyndon, any isomorphism $\varphi$ between shift spaces of $A^{\mathbb{Z}}$ for an alphabet $A$ is given by a block code [Hed69], which means that there exist $r\in\mathbb{N}$ and $f\colon A^{2r+1}\to A$ such that for every $k\in\mathbb{Z}$ and $x=(x(n))_{n\in\mathbb{Z}}\in A^{\mathbb{Z}}$ we have

For any alphabet $A$ we write $A^{*}$ for $\bigcup_{n=0}^{\infty}A^{n}$. We refer to the elements of $A^{*}$ as to words. If $w\in A^{n}$, then we refer to $n$ as to the length of $w$ and denote it by $|w|$. We use the convention that the empty word, denoted by $\epsilon$ is the unique word of length $0$. We write $A^{*}_{\mathrm{even}}$ for the set of all words of even length and $A^{*}_{\mathrm{odd}}$ for the set of all words of odd length.

For an interval $[a,b]\subseteq\mathbb{Z}$ and $z\in A^{\mathbb{Z}}$, by $z[a,b]$, we denote the sequence $(z(a),z(a+1),\dots,z(b))\in A^{b-a+1}$. Similarly, we set $z[a,b)=(z(a),z(a+1),\dots,z(b-1))\in A^{b-a}$.

Given a symbolic system $X\subseteq A^{\mathbb{Z}}$, its language $\mathrm{Lang}(X)$ is the collection of words in $A^{*}$ appearing in elements of $X$:

For a symbolic system $(X,\sigma)$ over $A$ transitivity is equivalent to the statement that for all $u,v\in\mathrm{Lang}(X)$, there exists $w\in A^{*}$ such that $uwv\in\mathrm{Lang}(X)$, see [BMN00, Section 3.7.2].

Let $E$ be a countable equivalence relation on the standard Borel space $X$. We say that $E$ is hyperfinite if it can be written as an increasing union of Borel equivalence relations with finite equivalence classes. An equivalence relation is hyperfinite if and only if it is induced by a Borel action of the group $\mathbb{Z}$ [DJK94, Theorem 5.1]. An equivalence relation $E$ is treeable [JKL02, Definition 3.1] if there exists a Borel graph on the vertex set $X$ which is a forest and whose connected components are the equivalence classes of $E$.

The group $S_{\infty}$ is the group of all permutations of $\mathbb{N}$. An equivalence relation is classifiable by countable structures if it is Borel-reducible to an action of $S_{\infty}$, see [Hjo00b]. The relation $=^{+}$ is the relation on $\mathbb{N}^{\mathbb{N}}$ defined by $(x_{n})=^{+}(y_{n})$ if $\{x_{n}:n\in\mathbb{N}\}=\{y_{n}:n\in\mathbb{N}\}$.

Let $G$ be a Polish group acting on a Polish space $X$ in a Borel way. We denote by $E^{X}_{G}$ the induced equivalence relation. Given $x\in X$ and open sets $U\subseteq X$ and $V\subseteq G$ with $x\in U$ and $1\in V$, the local $U$-$V$-orbit of $x$, denoted $O(x,U,V)$, is the set of $y\in U$ for which there exist $l\in\mathbb{N}$ and $x=x_{0},x_{1},\ldots,x_{l}=y\in U$, and $g_{0},\ldots,g_{l-1}\in V$ such that $x_{i+1}=g_{i}\cdot x_{i}$ for all $0\leq i<l$. An action of $G$ on $X$ is turbulent [Hjo00b] if every orbit is dense and meager and every local orbit is somewhere dense. By the Hjorth turbulence theorem [Hjo00b, Corollary 3.19] the equivalence relation $E^{G}_{X}$ induced by a turbulent action is not classifiable by countable structures.

Given a compact space $X$ we write $\mathrm{Homeo}(X)$ for the group of homeomorphisms of $X$. The group $\mathrm{Homeo}(X)$ is a Polish group with the compact-open topology. If $d$ is a metric on $X$, then the topology is induced by the uniform metric on $\mathrm{Homeo}(X)$, also denoted by $d$ defined as $d(f,g)=\sup\{d(f(x),g(x)):x\in X\}$. A subset $X\subseteq{[0,1]^{\mathbb{N}}}$ is a $Z$-set (see [VM88, Chapter 6.2]) if for every continuous function $f\colon{[0,1]^{\mathbb{N}}}\to{[0,1]^{\mathbb{N}}}$ and every $\varepsilon>0$ there exists a continuous function $g\colon{[0,1]^{\mathbb{N}}}\to{[0,1]^{\mathbb{N}}}\setminus X$ such that $d(f,g)<\varepsilon$.

Bowen introduced the specification property in [Bow71] to study Axiom A diffeomorphisms. It is a strengthening (a uniform version) of transitivity. Informally, a dynamical system satisfies the specification property if for every $\varepsilon>0$ we can find $k$ such that given any collection of finite fragments of orbits (orbit segments), there exists a point which follows $\varepsilon$-closely these orbit segments and takes $k$ steps to switch between consecutive orbit segments.

The specification property for a symbolic system $X$ can be restated in terms of the language $\mathrm{Lang}(X)$ in a similar fashion as transitivity.

It should be noted that, in the literature, some authors also consider other notions of specification, weaker than that introduced by Bowen. For example, sometimes one may require the existence of $k\in\mathbb{N}$ such that for every $w,u\in\mathrm{Lang}(X)$ there exists $v\in\mathrm{Lang}(X)$ with $|v|\leq k$ such that $wvu\in\mathrm{Lang}(X)$. For the whole panorama of specification-like properties of dynamical systems see the survey [KŁO16].

In this section, we construct families of symbolic systems that will allow us to provide lower bounds for the complexity of conjugacy problem for systems with the specification property.

Assume that $A$ is a finite alphabet containing a distinguished symbol $\#$ and $A\setminus\{\#\}\neq\emptyset$. Given a set $R\subseteq(A\setminus\{\#\})^{*}_{\text{odd}}$, we define

Now, for $R\subseteq(A\setminus\{\#\})^{*}_{\text{odd}}$ we define the shift space

In other words, $w\in(A\setminus\{\#\})^{*}_{\text{odd}}$ can appear between two consecutive occurrences of $\#$ in $x\in X(R)$ if and only if $w\in R$. Note that any $v\in(A\setminus\{\#\})^{*}_{\text{even}}$ is allowed between two consecutive $\#$’s in $x\in X(R)$. In particular, $\#^{l}$ is an allowed word for every $l\geq 1$. It follows that every word over $A\setminus\{\#\}$ is allowed in $X(R)$ so we always have $(A\setminus\{\#\})^{\mathbb{Z}}\subseteq X(R)$. Hence, $X(R)\neq\emptyset$ for every $R\subseteq(A\setminus\{\#\})^{*}_{\text{odd}}$. Let

The space $\mathcal{S}(A)$ consists of nonempty closed subsets of $A^{\mathbb{Z}}$, so it is naturally endowed with the Vietoris topology. The powerset of ${(A\setminus\{\#\})^{*}_{\text{odd}}}$, identified with $2^{(A\setminus\{\#\})^{*}_{\text{odd}}}$, also has the natural compact metric topology and the function $2^{(A\setminus\{\#\})^{*}_{\text{odd}}}\ni R\mapsto X(R)\in\mathcal{S}(A)$ is continuous, hence $\mathcal{S}(A)$ is a compact metric space.

Our starting point is the following.

In the next sections, we will use the above idea to show that the conjugacy problem for systems with specification is highly nontrivial. However, in order to work over over the alphabet $\{0,1\}$ we will need a more subtle version of Proposition 4.2.

To work over the alphabet $\{0,1\}$ we replace the alphabet $A$ with a finite nonempty set $B$ that consists of nonempty words over $\{0,1\}$, that is $B\subseteq\{0,1\}^{*}\setminus\{\epsilon\}$. We call $B$ a code and we refer to the elements of $B$ as to blocks. We identify words or sequences obtained by concatenating elements of $B$ with the corresponding words over $\{0,1\}$ as follows. Given a word $w=w(0)\ldots w(l-1)$ over the code $B$ we write $w_{\flat}$ for the word over $\{0,1\}$ obtained by concatenating $w(0),\ldots,w(l-1)$. We write $({B}^{*}_{\text{even}})_{\flat}$ for the set of all words over $\{0,1\}$ that can be written as $w_{\flat}$, where $w$ is a concatenation of an even number of blocks from $B$, that is $w\in{B}^{*}_{\text{even}}$. We write $({B}^{*}_{\text{odd}})_{\flat}$ for the collection of all $w_{\flat}$, where $w$ is a concatenation of odd number of blocks over $B$, that is $w\in{B}^{*}_{\text{odd}}$. Since the empty word $\epsilon$ has length zero, we have $\epsilon\in({B}^{*}_{\text{even}})_{\flat}$. Note that the length of $w\in({B}^{*}_{\text{even}})_{\flat}$ need not to be even.

Given a bi-infinite sequence $x=(x(k))_{k\in\mathbb{Z}}$ with entries in a code $B$ we write $x_{\flat}$ for the element of $\{0,1\}^{\mathbb{Z}}$ obtained by concatenating the words appearing in $x$ so that the first letter of $x(0)$ appears at the position $0$ in $x_{\flat}$. The collection of all shifts of bi-infinite sequences $x_{\flat}$ where $x\in B^{\mathbb{Z}}$ is a symbolic subsystem of $\{0,1\}^{\mathbb{Z}}$, which will be denoted by ${{B}}^{\mathbb{Z}}_{\flat}$. That is,

Given a subsystem $X\subseteq B^{\mathbb{Z}}$ we write

and note that $X_{\flat}$ is a subsystem of ${{B}}^{\mathbb{Z}}_{\flat}\subseteq\{0,1\}^{\mathbb{Z}}$.

Now, given a code $B$, treating $B$ as the alphabet in the definition of $\mathcal{S}(B)$, we define

Note that if a code $B$ is recognizable, then every sufficiently long word $w\in\mathrm{Lang}({{B}}^{\mathbb{Z}}_{\flat})$ can be in a unique way decomposed into blocks in $B$ meaning that

where $u_{1},\ldots,u_{k}\in B$ and $p,s\notin B$, but $p$ is a proper suffix of a block in $B$ and $s$ is a proper prefix of a block in $B$. In particular, $|p|,|s|<\max\{|w|:w\in B\}$.

For every $R\subseteq(B\setminus\{\#\})^{*}_{\text{odd}}$ we write

If $B$ is a recognizable code, then

In analogy with Lemma 4.1 we have the following result. It gives us the topology on $\mathcal{S}(B)_{\flat}$.

Note that if $\varphi\in\mathrm{Aut}(B^{\mathbb{Z}})$ is block-length-preserving, then for every $x\in B^{\mathbb{Z}}$ and $k\in\mathbb{Z}$ we have $|x(k)|=|\varphi(x)(k)|$.

Given a recognizable code $B$ we will consider the symbolic systems in the class ${\mathcal{S}(A)}_{\flat}$. However, in general the systems in the class ${\mathcal{S}(A)}_{\flat}$ may not have the specification property despite Proposition 4.2. To see that, first note that the system consisting of a single finite periodic orbit of length grater than $1$ does not have the specification property. This is easily seen using Proposition 3.3. Indeed, if the length of the orbit is $q$, then the system has realization as a symbolic subsystem $X$ of $\{0,1,\ldots,q-1\}^{\mathbb{Z}}$ consisting of the orbit of $(\ldots,0,1,2,\ldots,q-1,0,1,2,\ldots,q-1,\ldots$) and if $u,v,w\in\mathrm{Lang}(X)$ are such that $uvw\in\mathrm{Lang}(X)$, then $|v|$ depends on the last digit of $u$ and the first digit of $w$. Next, note that a factor of a system with the specification property also has the specification property. Therefore, a system with specification cannot have a finite orbit as a factor. Now, if $B$ is a finite recognizable code such that the lengths of all blocks in $B$ are divisible by $q\geq 2$, then the system ${{B}}^{\mathbb{Z}}_{\flat}\in{\mathcal{S}(A)}_{\flat}$ factors onto the finite orbit of length $q$. Indeed, note that for every $y\in{{B}}^{\mathbb{Z}}_{\flat}$ there is $0\leq l<\max\{|w|:w\in A\}$ such that $\sigma^{l}(y)\in(B^{\mathbb{Z}})_{\flat}$ and taking $\theta(y)=l\mod q$ defines a factor map and therefore the system ${{B}}^{\mathbb{Z}}_{\flat}\in{\mathcal{S}(A)}_{\flat}$ thus does not have the specification property (it only has the specification property relative to the periodic factor, see [KŁO16, Definition 37] and [Jun11, Definition 3.1 & Theorem 3.6].)

Thus, in order to prove that every symbolic system in ${\mathcal{S}(A)}_{\flat}$ has the specification property, we need to assume that $B$ is a finite and recognizable code such that there are at least two relatively prime numbers among the lengths of the words in $B$. In fact, to simplify our reasoning, we will work with a finite code $B$ with a distinguished symbol $\#\in B$ of odd length $r$ and we will assume that all blocks in $B\setminus\{\#\}$ have the same length $q$ that is relatively prime with $r$.

In the sequel we will need several admissible codes $B$ such that the size of $B\setminus\{\#\}$ is a power of $2$. There is an abundance of such codes, which we show in the next several lemmas.