Interplay between insertion of zeros and the complexity of Dedekind cuts

Abstract

The topic of this paper is the study of the possibility of effective conversions between different representations of irrational numbers. We are interested in subrecursive computations, in which we disallow the use of unbounded search. It is well-known that the base expansion of an irrational number can be subrecursively computed from its Dedekind cut, but in the reverse direction this is not subrecursively possible. Thus it would be natural to try to understand how additional properties of the base expansion, such as the presence of specific patterns of zero digits, correlate with the complexity of the Dedekind cut. Our first result roughly states that if large parts of zero digits dominate over smaller parts of arbitrary digits and the base expansion has elementary complexity, then the Dedekind cut also has elementary complexity. Much more interesting is the case when one allows large parts of zero digits to alternate with large parts of arbitrary digits. We compare the complexity of the Dedekind cuts of an arbitrary irrational number and another irrational number, obtained by inserting long sequences of zero digits in its base expansion. We provide examples in which (1) both numbers have elementary Dedekind cuts, (2) the first number has complex Dedekind cut and elementary base expansion, but the second number has elementary Dedekind cut and (3) both numbers have complex Dedekind cuts and elementary base expansions. An open question remains, whether it is possible for the first number to have elementary Dedekind cut, while the second number has complex Dedekind cut.

Keywords

Irrational number representations base expansions Dedekind cuts subrecursive classes computable analysis

1. Introduction

There are many ways to represent irrational numbers. Some are more traditional, such as Cauchy sequences, Dedekind cuts or decimal expansions, while others have been introduced rather recently, like general sum approximations or left and right best approximations. Interestingly, all these representations are equivalent, that is they give rise to one and the same class of computable real numbers. Moreover, restricted to irrational numbers, any representation can be computably transformed into any other. Our main concern is the complexity of these transformations. It is known since the early days of computable analysis, that the representations of irrational numbers are not equivalent with respect to the class of primitive recursive functions. For example, there exist irrational numbers with a primitive recursive Cauchy sequence, whose Dedekind cut is not primitive recursive. Therefore we cannot transform a Cauchy sequence into a Dedekind cut by a primitive recursive algorithm.

We formulate our complexity framework in a more general way. We want to formalize computations, which do not use unbounded search. Any such computation can be modelled in a sufficiently large subrecursive class, having natural closure properties. Let $R_{1}$ and $R_{2}$ be two representations of irrational numbers. If there exists an arbitrarily large subrecursive class $S$ , such that some irrational number ξ has at least one $R_{2}$ -representation in $S$ , while the same ξ has no $R_{1}$ -representations in $S$ , then we can safely deduce that $R_{2}$ -representations cannot be transformed into $R_{1}$ -representations without using unbounded search.

Lars Kristiansen in [7,8] initiated an extensive study of irrational number representations in this general framework. Further collaboration with Frank Stephan and the present author led to several difficult results in [4], among them incomparability of the general sum approximations from below and from above. Previously, a number of papers study questions on real number representations in concrete complexity classes: Specker [17], Mostowski [13], Lehman [12], Lachlan [11] consider the primitive recursive functions, Ko [5,6] and Labhalla & Lombardi [10] the functions computable in polynomial time and more recently Skordev, Weiermann and the present author [1,15,16] subclasses of the second Grzegorczyk class.

The focus of the current paper is on Dedekind cuts and base expansions in a fixed base $b ⩾ 2$ . A standard linear algorithm converts the Dedekind cut into the base-b expansion. But conversely, a main result in [8] is that the base-b expansion cannot be transformed subrecursively into the Dedekind cut, that is without the use of unbounded minimization. We are motivated by the following general question:

In what way is the presence of patterns of zeros in the base expansion of an irrational number connected with the complexity of its Dedekind cut?

To our knowledge the question has not been studied from the perspective of complexity theory. The present paper aims to provide techniques, which will further be used for a more comprehensive treatment of the matter.

In our first result we consider a general situation, where the base expansion contains long intervals of consecutive zero digits in positions $[l_{i}, r_{i})$ , followed by much shorter intervals $[r_{i}, l_{i + 1})$ of arbitrary digits. In this case the Dedekind cut turns out to be subrecursively computable from the base expansion.

After that we want to allow long intervals of zero digits to alternate with long intervals of arbitrary digits. Let d be a sufficiently fast-growing function. We will construct an irrational number, whose base expansion contains zeros in all positions $[d_{2 i}, d_{2 i + 1})$ , but whose Dedekind cut is not subrecursively computable from its base expansion.

In more detail, for a fixed base b and any irrational number ξ we define the irrational number $ξ^{'}$ by inserting zero digits in positions $[d_{2 i}, d_{2 i + 1})$ for all i and retaining the other digits of ξ by shifting them to the right. For a fixed subrecursive class $S$ , let $S_{b E}$ ( $S_{D}$ ) be the set of irrational numbers with base-b expansion (Dedekind cut) in the class $S$ . We provide examples for irrational numbers ξ, α, β in $S_{b E}$ , such that: (1) $ξ \in S_{D}$ , $ξ^{'} \in S_{D}$ , (2) $α \notin S_{D}$ , $α^{'} \in S_{D}$ , (3) $β \notin S_{D}$ , $β^{'} \notin S_{D}$ . The last fourth case, whether there exists δ with $δ \in S_{D}$ , $δ^{'} \notin S_{D}$ , remains unsolved.

The present paper is based on an invited lecture at Mal’tsev meeting, 2022 and also on a conference paper [2], which contains concise versions of some of the presented results.

The reader interested in other topics on computable real numbers and real functions should consult the textbook [18] on computable analysis.

2. Basic facts on base expansions

In this section we will define base expansions of real numbers and we will prove some simple facts, regarding the distribution of digits of rational numbers.

Any natural number $b ⩾ 2$ will be called a base and the numbers in the set ${0, 1, \dots, b - 1}$ will be regarded as base-b digits.

For any base-b digit $D$ we define the complement digit $\overline{D} = b - 1 - D$ .

For a number $M \in Z$ and a finite sequence $D_{1}, D_{2}, \dots, D_{n}$ of base-b digits, we denote by ${(M . D_{1} D_{2} \dots D_{n})}_{b}$ the rational number $M + \sum_{i = 1}^{n} D_{i} b^{- i}$ .

Definition 2.1.
For $M \in Z$ and an infinite sequence $D_{1}, D_{2}, \dots$ of base-b digits, we will say that ${(M . D_{1} D_{2} \dots)}_{b}$ is the base-b expansion of $ξ \in R$ if for all $n ⩾ 1$ $\begin{array}{r} {(M . D_{1} D_{2} \dots D_{n})}_{b} ⩽ ξ < {(M . D_{1} D_{2} \dots D_{n})}_{b} + b^{- n} . \end{array}$ We identify the base-b expansion with the function $E_{b}^{ξ} : N \to Z$ , such that $\begin{array}{r} E_{b}^{ξ} (0) = M, E_{b}^{ξ} (n) = D_{n} (for n ⩾ 1) . \end{array}$

Since the second inequality is strict, every real number has a unique base-b expansion and $E_{b}^{ξ}$ is well defined. Base expansions ending with infinite sequence of $\overline{0}$ digits are not allowed according to this definition.

Let ξ be a rational number. If for some n we have $ξ = {(M . D_{1} D_{2} \dots D_{n})}_{b}$ with $D_{n} \neq 0$ , then we say ξ has a finite base-b expansion and the number n is called the base-b length of ξ. Clearly, the base-b expansion of ξ stabilizes in $0$ digits. If such an n does not exist, then we say ξ has an infinite base-b expansion. In this case, it is well-known that the base-b expansion is periodic (we give a proof below) and the period will not consist entirely of $0$ digits or entirely of $\overline{0}$ digits.

Now we will present a standard algorithm to compute the base-b digits of a rational number and then use it to give upper bounds on the number of consecutive $0$ -s or $\bar{0}$ -s in its base-b expansion.
Lemma 2.2.
Let $q \in Q$ , $q = M + \frac{m}{n}$ , where $M \in Z$ , $m, n \in N$ , $m < n$ . Let b be a base and ${(M . D_{1} D_{2} \dots)}_{b}$ be the base-b expansion of q. Consider the sequence $\begin{array}{r} r_{0} = m, r_{i + 1} = (r_{i} \cdot b) mod n, \end{array}$ so that $r_{i + 1}$ is the remainder of $r_{i} \cdot b$ divided by n. Let $q_{i + 1}$ be the quotient of the same division, $r_{i} \cdot b = q_{i + 1} \cdot n + r_{i + 1}$ . Then we have $q_{i} = D_{i}$ for all $i ⩾ 1$ .
Proof.
Since $m < n$ we have $0 ⩽ r_{i} < n$ and $\begin{array}{r} q_{i + 1} ⩽ q_{i + 1} + \frac{r_{i + 1}}{n} = \frac{r_{i} \cdot b}{n} < b \end{array}$ for all $i \in N$ , thus $q_{i + 1}$ is indeed a base-b digit. By induction on i we show that $\begin{matrix} (Claim) & q = {(M . q_{1} q_{2} \dots q_{i})}_{b} + \frac{r_{i}}{n \cdot b^{i}} \end{matrix}$ for all i. The claim is obvious for $i = 0$ . Now assume it holds for some i. Then $\begin{array}{r} q = {(M . q_{1} q_{2} \dots q_{i})}_{b} + \frac{r_{i} \cdot b}{n \cdot b^{i + 1}} \end{array}$ and by definition $\begin{aligned} q & = {(M . q_{1} q_{2} \dots q_{i})}_{b} + \frac{q_{i + 1} \cdot n + r_{i + 1}}{n \cdot b^{i + 1}} \\ = {(M . q_{1} q_{2} \dots q_{i})}_{b} + q_{i + 1} \cdot b^{- (i + 1)} + \frac{r_{i + 1}}{n \cdot b^{i + 1}}, \end{aligned}$ which is the same as $\begin{array}{r} q = {(M . q_{1} q_{2} \dots q_{i} q_{i + 1})}_{b} + \frac{r_{i + 1}}{n \cdot b^{i + 1}} \end{array}$ and the claim is settled. Now since $0 ⩽ r_{i} < n$ we have $\begin{array}{r} {(M . q_{1} q_{2} \dots q_{i})}_{b} ⩽ q < {(M . q_{1} q_{2} \dots q_{i})}_{b} + b^{- i}, \end{array}$ which clearly implies what we need, since q has a unique base-b expansion. □

Observe that if $r_{i} = 0$ for some i, then $r_{j} = q_{j} = D_{j} = 0$ for all $j > i$ , therefore q has a finite base-b expansion. Conversely, let q have a finite base-b expansion, so there exists i, such that $D_{j} = 0$ for all $j > i$ . An easy induction shows that $r_{i + s} = r_{i} \cdot b^{s}$ for all s. But this is only possible if $r_{i} = 0$ , because the sequence r is bounded. We have proved that $\begin{matrix} q has a finite base- b expansion iff there exists i, such that r_{i} = 0 . \end{matrix}$ In addition, $r_{i} = 0$ iff $m \cdot b^{i}$ is divisible by n. Therefore, if $\frac{m}{n}$ is in its lowest terms, $r_{i} = 0$ iff n divides $b^{i}$ . So we can determine if q has a finite base-b expansion by checking if its denominator n divides some power of b, or equivalently if all prime factors of n are also prime factors of b.

Now let q have an infinite base-b expansion. Thus $r_{i} \neq 0$ for all i, hence $r_{i} \in {1, 2, \dots, n - 1}$ . By the pigeonhole principle, there exist i, j with $0 ⩽ i < j < n$ , such that $r_{i} = r_{j}$ and this implies $r_{i + s} = r_{j + s}$ and $D_{i + s} = D_{j + s}$ for all $s > 0$ . Thus the base-b expansion of q has the periodic form $\begin{array}{r} M . D_{1} D_{2} \dots D_{i} D_{i + 1} \dots D_{j} D_{i + 1} \dots D_{j} \dots . \end{array}$
Theorem 2.3.
Let $q = \frac{m}{n}$ be a rational number and b be a base, such that q has an infinite base-b expansion. Assume also that $s \in N$ satisfies $b^{s} ⩾ n$ . Then for every x, at least one of the base-b digits $D_{x + 1}, D_{x + 2}, \dots, D_{x + s}$ of q is different from $0$ and at least one of them is different from $\overline{0} = b - 1$ .
Proof.
Suppose that $D_{x + i} = 0$ for all $i \in {1, 2, \dots, s}$ . This clearly implies that $r_{x + i} = r_{x + i - 1} \cdot b$ for all such i. Therefore, $r_{x + s} = r_{x} \cdot b^{s}$ . But we know that $r_{x} \neq 0$ , since q has an infinite base-b expansion. Thus we obtain $\begin{array}{r} b^{s} ⩽ r_{x} \cdot b^{s} = r_{x + s} < n, \end{array}$ which clearly contradicts the assumed inequality $b^{s} ⩾ n$ .

Now suppose that $D_{x + i} = \overline{0} = b - 1$ for all $i \in {1, 2, \dots, s}$ . This implies $\begin{array}{r} r_{x + i - 1} \cdot b = (b - 1) \cdot n + r_{x + i} ⟺ r_{x + i} = (r_{x + i - 1} - n) \cdot b + n \end{array}$ for all such i, therefore $r_{x + s} = (r_{x} - n) \cdot b^{s} + n$ . Since q has an infinite base-b expansion, we have $r_{x + s} \neq 0$ . Thus we obtain consecutively $\begin{array}{r} 0 < r_{x + s} < n ⟹ 0 < n - r_{x + s} < n ⟹ 0 < (n - r_{x}) \cdot b^{s} < n \end{array}$ and by using $r_{x} < n$ , we infer $b^{s} ⩽ (n - r_{x}) \cdot b^{s} < n$ , which leads to the same contradiction as above.

Note that we could have used the first part of the proof applied to $1 - q$ , which also has an infinite base-b expansion, to prove the second part of the theorem. □
Corollary 2.4.
Let $q = \frac{m}{n}$ and b be a base with $b^{s} ⩾ n$ . If the base-b digits $D_{x + 1}, D_{x + 2}, \dots, D_{x + s}$ of q are all equal to $0$ , then q has a finite base-b expansion of length $⩽ x$ . If they are all equal to $\overline{0}$ , then $x = 0$ , $n = b^{s}$ and $m = b^{s} - 1 (mod n)$ .
Proof.
An inspection of the above proof shows that in the first case $r_{x} = 0$ , therefore the base-b length of q is at most x. In the second case, $r_{x + s} = 0$ and the base-b length of q is exactly $x + s$ , because $D_{x + s} = \overline{0}$ . It follows that q in its lowest terms has denominator $b^{x + s}$ , therefore $n ⩾ b^{s + x}$ . But we also have $b^{s} ⩾ n$ . The only possibility for these two inequalities to hold simultaneously is $x = 0$ and $n = b^{s}$ . □
Definition 2.5.
For a real number ξ, the function $D^{ξ} : Q \to {0, 1}$ will be called the Dedekind cut of ξ if $D^{ξ} (q) = 0$ for $q < ξ$ and $D^{ξ} (q) = 1$ for $q ⩾ ξ$ .

Of course, if ξ is irrational, then the second inequality is strict.
3. Subrecursive classes

In this section we define formally our complexity framework. A measure for the complexity of a particular representation of some irrational number will be its membership in different subrecursive classes. If the representation belongs to a small enough subrecursive class, then we regard it as simple. If the representation does not belong to a sufficiently large subrecursive class, then we considered it complex.

Let ϕ and ψ be total functions of several arguments in $N$ .

We denote $ϕ ⩽_{E} ψ$ (ϕ is elementary in ψ), if ϕ can be generated from ψ and the initial elementary functions ( $x \mapsto x + 1$ , $x \mapsto 2^{x}$ , $(x, y) \mapsto max (x, y)$ , and the projections $(x_{1}, \dots, x_{k}) \mapsto x_{i}$ ) by composition and bounded primitive recursion (this is ordinary primitive recursion with the additional assumption that the resulting function is bounded above by an already generated function). We say that ϕ is elementary, if ϕ is elementary in the constant 0.

Let us fix an elementary coding of finite sequences of natural numbers: $⟨ x_{0}, \dots, x_{k} ⟩ \in N$ is the code of the list $x_{0}, \dots, x_{k}$ , so that the function $(⟨ x_{0}, \dots, x_{k} ⟩, i) \mapsto x_{i}$ is elementary. We assume the code of a sequence is monotonically increasing in each of its elements and also with respect to taking extensions.

Definition 3.1.
Let $S$ be a class of total computable functions in $N$ .

We say that $S$ is computably enumerable if there exists a computable function $U : N^{2} \to N$ , such that $f \in S$ if and only if $f (x_{1}, \dots, x_{k}) = U (e, ⟨ x_{1}, \dots, x_{k} ⟩)$ for some e.

A subrecursive class $S$ is a computably enumerable class, which contains the initial elementary functions and is closed under composition and bounded primitive recursion.

Note that for the purposes of the current paper we use bounded primitive recursion, as opposed to ordinary primitive recursion. Of course, ordinary primitive recursion can be formalized by an algorithm, which does not use unbounded search, so it would be natural to use it in our definition, but our results remain true with this stronger growth preserving condition.

Observe that a subrecursive class $S$ is closed also under bounded summation, bounded product and under all other familiar bounded schemata. The elementary functions form the least subrecursive class with respect to set inclusion.

By exploiting the elementary coding from above, we may also allow the integers $Z$ and the rationals $Q$ as arguments or values of the total functions that we use. As an example, by fairly standard techniques, we can define an elementary ternary function $\begin{array}{r} digit : N \times Q \times N \to Z, {digit}_{n} (q, b) = E_{b}^{q} (n), \end{array}$ which gives the n-th base-b digit of the rational number q in any base $b ⩾ 2$ .

A unary function $f : N \to N$ is honest, if $f (x) ⩾ 2^{x}$ , $f (x + 1) ⩾ f (x)$ for all $x \in N$ and the graph of f is elementary (the relation $f (x) = y$ is elementary in x, y).

The k-th iterate of f is defined as follows: $f^{0} (x) = x$ , $f^{k + 1} (x) = f (f^{k} (x))$ for all $x \in N$ .

We will need the function $U$ and the relation $T_{1}$ from Kleene’s Normal Form Theorem, which are both elementary. For any unary $ϕ ⩽_{E} f$ we can choose e, k, such that for all $n \in N$ $\begin{matrix} (3.1) & ϕ (n) = U (μ t ⩽ f^{k} (n) [T_{1} (e, n, t)]) \end{matrix}$ and the μ-operator always succeeds in finding the corresponding t.

For any honest function f we define the jump $f^{'}$ of f by: $f^{'} (x) = f^{x + 1} (x)$ . It is straightforward to show that $f^{'}$ is also honest and that if $ϕ ⩽_{E} f$ , then $ϕ (x) < f^{'} (x)$ for all sufficiently large x.

For any subrecursive class $S$ there exists an honest function f, such that $ϕ ⩽_{E} f$ for all $ϕ \in S$ . Such an honest function can be obtained effectively from a computable index of the enumeration function U. Observe that $f^{'} \notin S$ , because $f^{'}$ grows faster than all functions in $S$ .
Lemma 3.2.
For every honest function f and natural numbers x, y:
$y ⩽ x \Rightarrow x + y ⩽ f (x)$ ,

$y < x \Rightarrow x y ⩽ f (x)$ ,

$y ⩽ x^{2} \Rightarrow y \cdot f (x) ⩽ f (f (x))$ ,

$y ⩽ x \Rightarrow y^{x} < f (f (x))$ ,

$y ⩽ x^{3} \Rightarrow x y ⩽ f (f (x))$ .

Proof.
Straightforward, since f is increasing and $f (x) ⩾ 2^{x}$ . □

From now on we will tacitly use Lemma 3.2 in all inequalities, which involve estimating the growth rate of honest functions.

In case the reader is not comfortable with the presented level of details, we recommend Sections 2, 3 in [4] for full proofs of the stated results. See also [9] for more extensive treatment of honest functions and [14] of subrecursive classes.

For a subrecursive class $S$ , we denote $\begin{array}{r} S_{b E} = {ξ \in R ∖ Q | E_{b}^{ξ} \in S}, S_{D} = {ξ \in R ∖ Q | D^{ξ} \in S} . \end{array}$

A simple algorithm, which computes the base-b digits of ξ successively using at most $b - 1$ calls to $D^{ξ}$ for each digit can be formalized by bounded primitive recursion (the integer part of ξ may be used as a constant). It shows that $E_{b}^{ξ} ⩽_{E} D^{ξ}$ (even uniformly in b) and therefore $S_{D} \subseteq S_{b E}$ . But as proven in Section 6 in [8], the inclusion is strict. Our motivation is to better understand how the presence of patterns in the base expansion of an irrational number correlates with the complexity of its Dedekind cut.
4. Long parts of zero digits dominating over shorter parts of arbitrary digits

As in the previous section, $S$ is a subrecursive class, f is an honest function, such that $ϕ \in S$ implies $ϕ ⩽_{E} f$ . Thus the jump $f^{'}$ of f grows faster than any function in $S$ .

We will use a fixed sequence d, such that $d_{0} > 0$ and $d_{i + 1} = f^{'} (d_{i})$ for all i. We consider the intervals $[d_{i}, d_{i + 1})$ as long, because one cannot reach $d_{i + 1}$ when having $d_{i}$ by means of a function from $S$ for sufficiently large i. However, the graph of d is elementary, because $f^{'}$ is honest.

Theorem 4.1.
Let b be any base and ξ be an irrational number, $ξ \in S_{b E}$ . Assume there exist a strictly increasing function $g : N \to N$ , such that $g \in S$ and $\begin{matrix} (4.1) & d_{i} + 1 ⩽ x ⩽ d_{i + 1} - g (d_{i}) ⟹ E_{b}^{ξ} (x) = 0 . \end{matrix}$ for all x and all sufficiently large i. Then $ξ \in S_{D}$ .
Proof.
The idea here is that given a rational number q, we will be able to compute i, such that q cannot have a string of zero digits in all positions $[d_{i} + 1, d_{i + 1} - g (d_{i})]$ in its base b-expansion, unless q has a finite base-b expansion. Therefore, we can compare q and ξ using only $E_{b}^{ξ}$ .

First observe that d is strictly increasing and grows faster than $f^{'}$ , so that $d \notin S$ . Since $g \in S$ , we may choose $i_{0}$ , such that $\begin{matrix} (4.2) & d_{i + 1} = f^{'} (d_{i}) > g (d_{i}) + 2 d_{i} \end{matrix}$ holds for all $i ⩾ i_{0}$ . Let us suppose that (4.1) also holds for all $i ⩾ i_{0}$ .

We will now describe an algorithm for the Dedekind cut of ξ, which shows that $ξ \in S_{D}$ .

Start of algorithm. Given a rational number q:

Step 1. Compute m, n such that $q = m n^{- 1}$ and $n ⩾ d_{i_{0}}$ .

Step 2. Search for the unique $i ⩾ i_{0}$ , such that $d_{i} ⩽ g (n) + 2 n < d_{i + 1}$ .

Step 3. Compute $q_{i} = \sum_{x = 0}^{d_{i}} E_{b}^{ξ} (x) b^{- x}$ .

Step 4. If $q ⩽ q_{i}$ give output 0, otherwise give output 1. End of algorithm.

All steps are formalizable in the class $S$ . In Step 1, $d_{i_{0}}$ is a fixed number and can be hardcoded as a constant in the algorithm. In Step 2, the search for i is bounded as $i < d_{i}$ . Furthermore, $g \in S$ and the graph of d is elementary, which allows to check the two inequalities. In Step 3, we have $d_{i} ⩽ g (n) + 2 n$ , therefore we can compute $d_{i}$ using the graph of d. Since $E_{b}^{ξ} \in S$ , we can also compute $q_{i}$ . Step 4 is obviously elementary in q and $q_{i}$ .

It remains to prove that the algorithm correctly computes $D^{ξ}$ . The easy case is when $q ⩽ q_{i}$ , because obviously $q ⩽ q_{i} < ξ$ and $D^{α} (q) = 0$ . Suppose now that $q_{i} < q$ . Then the algorithm outputs 1 and assume by way of a contradiction that $D^{ξ} (q) = 0$ , so we have $q_{i} < q < ξ$ . We will prove the inequality $\begin{array}{r} d_{i} + n < d_{i + 1} - g (d_{i}) . \end{array}$ Indeed, if $n ⩽ d_{i}$ it follows easily from (4.2) and if $n > d_{i}$ we have $\begin{array}{r} d_{i} + g (d_{i}) + n < g (n) + 2 n < d_{i + 1}, \end{array}$ due to the choice of i and the fact that g is increasing. Now $q_{i}$ has base-b length $⩽ d_{i}$ and (4.1) implies that the base-b digits of ξ in positions $d_{i} + 1, d_{i} + 2, \dots, d_{i} + n$ are all equal to $0$ , thus the same is true for q. By Corollary 2.4 this is only possible if q has a finite base-b expansion of length $⩽ d_{i}$ , since q has denominator n. This clearly implies $q = q_{i}$ , because the first $d_{i}$ base-b digits of $q_{i}$ and ξ coincide. But we are in the case $q_{i} < q$ – contradiction. □

Observe that $g (d_{i})$ is very small compared to $d_{i + 1} = f^{'} (d_{i})$ , because $f^{'}$ grows faster than any function in $S$ . For all sufficiently large i the base-b expansion of ξ has the following form: $\begin{aligned} ... * \underline{0000......0000} \overset{length g (d_{i - 1})}{\overset{︷}{* * ... * }} 00000000.........00000000 \overset{length g (d_{i})}{\overset{︷}{\underline{ * * * ...... * * * }}} 0... \\ d_{i} ↑ d_{i + 1} ↑ \end{aligned}$ and this is the reason why long stretches of zeros are followed by (relatively) small parts of arbitrary digits. Note that the lengths of the underlined parts are commensurable, being functions of $d_{i}$ .

In the following corollary we provide examples of irrational numbers ξ, which satisfy the premises of Theorem 4.1. The function $h \in S$ can be chosen in arbitrary way, as long as it has non-zero values. There are similar examples in [7,8], in which h is a constant function. Corollary 4.2.
Let b be any base and let the functions* $a, h : N \to N$ satisfy the following conditions:

$h \in S$ and $0 < a_{i + 1} = h (d_{i})$ for all $i \in N$ . Then the series $\sum_{k = 0}^{\infty} a_{k} b^{- d_{k}}$ is convergent and its sum ξ is an irrational number, such that $ξ \in S_{D}$ .
Proof.
Let us take $g \in S$ , such that $h (x) ⩽ g (x)$ for all $x \in N$ and g is strictly increasing. In order to apply the theorem, we need to prove that $ξ \in S_{b E}$ and that (4.1) holds for all x and all sufficiently large i. We again choose $i_{0}$ , such that (4.2) is true for all $i ⩾ i_{0}$ . Then we obtain $\begin{array}{r} a_{k + 1} b^{- d_{k + 1}} = h (d_{k}) b^{- d_{k + 1}} < b^{g (d_{k})} b^{- d_{k + 1}} ⩽ b^{- 2 d_{k} - 1} \end{array}$ for all $k ⩾ i_{0}$ and this easily implies $\sum_{k = i + 1}^{\infty} a_{k} b^{- d_{k}} < b^{- d_{i}}$ for all $i ⩾ i_{0}$ . It follows that the series is indeed convergent and by the same token $\begin{array}{r} \sum_{k = i + 1}^{\infty} a_{k} b^{- d_{k}} < a_{i + 1} b^{- d_{i + 1}} + b^{- d_{i + 1}} = (h (d_{i}) + 1) b^{- d_{i + 1}} ⩽ b^{- d_{i + 1} + g (d_{i})} \end{array}$ for all $i ⩾ i_{0}$ . Let ξ be the sum of the series. Note that the rational number $q_{i} = \sum_{k = 0}^{i} a_{k} b^{- d_{k}}$ has a finite base-b expansion of length $⩽ d_{i}$ and since $a_{i + 1} > 0$ the inequalities $\begin{array}{r} q_{i} < ξ < q_{i} + b^{- d_{i + 1} + g (d_{i})} \end{array}$ hold for all $i ⩾ i_{0}$ . It follows that (4.1) is true for all x and all $i ⩾ i_{0}$ and also that ξ is irrational.

Now we give an algorithm, computing the base-b expansion $E_{b}^{ξ}$ .

Start of algorithm. Given a natural number n:

Step 1. Search for the unique $i ⩾ i_{0}$ , such that $d_{i} ⩽ n^{'} < d_{i + 1}$ , where $n^{'} = max (n, d_{i_{0}})$ .

Step 2. Compute $d_{i}$ and $q_{i}$ . If $n + g (d_{i}) ⩽ d_{i + 1}$ output ${digit}_{n} (q_{i}, b)$ . Otherwise, go to Step 3.

Step 3. Compute $d_{i + 1}$ and $q_{i + 1}$ . Output ${digit}_{n} (q_{i + 1}, b)$ . End of algorithm.

The correctness of the algorithm follows from the fact that the first $d_{i}$ base-b digits of $q_{i}$ and ξ are the same for any $i ⩾ i_{0}$ . Note also that in case $d_{i} + 1 ⩽ n ⩽ d_{i + 1} - g (d_{i})$ we have ${digit}_{n} (q_{i}, b) = 0 = E_{b}^{ξ} (n)$ by (4.1).

Finally, we argue that $E_{b}^{ξ} \in S$ . Indeed, in Step 1 the search is bounded ( $i < d_{i} ⩽ n^{'}$ ) and can be formalized using the graph of d, which is elementary ( $d_{i_{0}}$ is fixed). In Step 2, we have $d_{k} ⩽ n^{'}$ for all $k ⩽ i$ , thus we can compute $d_{0}, d_{1}, \dots, d_{i}$ and also $a_{0}, a_{1}, \dots, a_{i}$ , since $h \in S$ and $a_{k} = h (d_{k - 1})$ for all non-zero k ( $a_{0}$ can be used as constant). Therefore, we can also compute $q_{i}$ . After that using $g \in S$ we can obtain $n + g (d_{i})$ and test the inequality using the graph of d again. Step 3 is invoked only when $d_{i + 1} < n + g (d_{i})$ , so in this case we can compute $d_{i + 1}$ and then $q_{i + 1}$ as above. Of course, we are allowed to use the elementary function $digit$ . □

5. Long parts of zero digits alternating with long parts of arbitrary digits

Now what happens if we allow longer parts of arbitrary digits? In the present section we will consider specific irrational numbers, in which long sequences of zeros alternate with long sequences of arbitrary digits. An irrational number of this form is considered in the last example on page 22 in [8] and it is shown that its Dedekind cut is elementary. Motivated by this example we asked the following question:

Is it possible to modify the proof of Theorem 4.1, so that we can prove $ξ \in S_{D}$ by only assuming that $E_{b}^{ξ} \in S$ and that ξ has long stretches of $0$ -s in its base-b expansion with no restriction on the remaining base-b digits of ξ?

We will see that the answer to this question is negative. In the example from [8], all non-zero digits of ξ are equal to $\overline{0}$ and this is crucial to deduce that $ξ \in S_{D}$ . On the other hand, we shall see the other extreme in this section, where the remaining digits may constitute an irrational number of very high complexity, but still we may have elementary Dedekind cut.

We will again use the fixed sequence d with $d_{0} > 0$ and $d_{i + 1} = f^{'} (d_{i})$ for all i, where $f^{'}$ grows faster than any function in a subrecursive class $S$ .

For the sake of brevity, let us denote $σ_{k} = \sum_{j < k} (d_{2 j + 1} - d_{2 j})$ . Note that $σ_{k + 1}$ can be computed elementarily from $d_{2 k + 1}$ and that $σ_{k + 1} < d_{2 k + 1}$ for all $k \in N$ .

Definition 5.1.
For an arbitrary irrational number ξ we define $ξ^{'}$ in the following manner: $\begin{array}{r} E_{b}^{ξ^{'}} (x) = \{\begin{array}{ll} E_{b}^{ξ} (x), & if x < d_{0}, \\ 0, & if d_{2 i} ⩽ x < d_{2 i + 1}, \\ E_{b}^{ξ} (x^{'}), & if d_{2 i + 1} ⩽ x < d_{2 i + 2}, \end{array} \end{array}$ where $x^{'} = x - σ_{i + 1}$ .

In other words, we produce $ξ^{'}$ by inserting a string of $0$ -s in the base-b expansion of ξ in positions $[d_{2 i}, d_{2 i + 1})$ for all i and by preserving the base-b digits of ξ by properly shifting them to the right. To compute the position $x^{'}$ in the original number ξ we subtract from x the number $σ_{i + 1}$ of added $0$ -s preceding the position x. Clearly, $ξ^{'}$ is irrational, because its base-b expansion is neither finite, nor periodic.

Note also that $E_{b}^{ξ^{'}} ⩽_{E} E_{b}^{ξ}$ : given x we can compute the unique i, such that $d_{2 i} ⩽ x < d_{2 i + 2}$ using the graph of d. We can also check if $x ⩾ d_{2 i + 1}$ and compute $x^{'}$ in case it is true, because $x^{'}$ is elementary in x and $d_{2 i + 1}$ .

We will need two auxiliary function $ins : N \times R \to R$ and $del : N \times R \to R$ for insertion and deletion of finite portions of digits in the base-b expansions.

For $i \in N$ and $δ \in R$ : let the real number $ins (i, δ)$ be obtained from δ by inserting $0$ -s in the base-b expansion of δ in positions $[d_{2 j}, d_{2 j + 1})$ for all $j < i$ and let $del (i, δ)$ be obtained from δ by deleting the base-b digits of δ in the same positions, so that $del (i, ins (i, δ)) = δ$ .
Lemma 5.2.
The numbers $ins (i, q)$ and $del (i, q)$ can be computed elementarily from i, q and for any $i \in N$ and $q \in Q$ .
Proof.
We have the following equalities: ( $r ↾ d_{2 i}$ is a shorthand for $\sum_{s < d_{2 i}} {digit}_{s} (r, b) b^{- s}$ ) $\begin{aligned} ins (0, q) = q, ins (i + 1, q) = ins (i, q) ↾ d_{2 i} + b^{d_{2 i} - d_{2 i + 1}} \cdot (ins (i, q) - ins (i, q) ↾ d_{2 i}), \\ del (0, q) = q, del (i + 1, q) = del (i, q ↾ d_{2 i} + r - r ↾ d_{2 i}), where \\ r = b^{d_{2 i + 1} - d_{2 i}} \cdot (q - q ↾ d_{2 i}) . \end{aligned}$ It is easy to obtain an upper bound for the denominators of $ins (i, q)$ and $del (i, q)$ , which is elementary in i, q and . Since the integer parts of $ins (i, q)$ and $del (i, q)$ are equal to the integer part of q, a similar upper bound can be obtained for their numerators. Therefore, $ins (i, q)$ and $del (i, q)$ can be produced by bounded primitive recursion as functions of i, q and . □

Our aim will be to explore how complex the Dedekind cuts of ξ and $ξ^{'}$ are relative to one another. In the next theorem we show that if ξ satisfies the premises of Theorem 4.1, then this suffices to prove $ξ^{'} \in S_{D}$ .
Theorem 5.3.
Let ξ be an irrational number, such that $E_{b}^{ξ} \in S$ and assume there exist a strictly increasing function $g \in S$ and a natural number $i_{0}$ , such that ( 4.1 ) is true for all x and all $i ⩾ i_{0}$ . Then $ξ^{'} \in S_{D}$ .
Proof.
First of all, $ξ \in S_{b E}$ implies $ξ^{'} \in S_{b E}$ . The idea of the algorithm for the Dedekind cut of $ξ^{'}$ will be to try to produce a position P, up to which there will be a guaranteed difference between the base-b expansions of $ξ^{'}$ and the input q. After that we can compute the first P base-b digits of $ξ^{'}$ and q (using $E_{b}^{ξ^{'}}$ and $digit$ ) and then easily determine the value $D^{ξ^{'}} (q)$ .

Start of algorithm. Given a rational number q:

Step 0. If q has an infinite base-b expansion proceed with Step 1. Otherwise, compute the base-b length s of q and $\tilde{q} = \sum_{j ⩽ s} E_{b}^{ξ^{'}} (j) b^{- j}$ . If $q ⩽ \tilde{q}$ give output 0 and if $q > \tilde{q}$ give output 1.

Step 1. Compute m, n, such that $q = m n^{- 1}$ and $n ⩾ d_{i_{0}}$ . Search for the unique i, such that $d_{2 i} ⩽ n < d_{2 i + 2}$ .

Step 2. Check whether the following relation holds: $d_{2 i} + n < d_{2 i + 1}$ . If it is true, proceed with Step 4 ( $P = d_{2 i} + n$ ), otherwise go to Step 3.

Step 3. Compute $d_{2 i + 1}$ , $σ_{i + 1}$ and $u_{i} = d_{2 i + 1} + 1 + g (d_{2 i + 1})$ . Check the inequality: $u_{i} + n < d_{2 i + 2}$ . If it holds, proceed with Step 4 ( $P = d_{2 i + 1} + 1 + σ_{i + 1} + n$ ). If it does not, compute $d_{2 i + 2}$ and proceed with Step 4 ( $P = d_{2 i + 2} + n$ ).

Step 4 (parameter P). Compute the least $k ⩽ P$ , such that ${digit}_{k} (q, b) \neq E_{b}^{ξ^{'}} (k)$ .

If ${digit}_{k} (q, b) < E_{b}^{ξ^{'}} (k)$ return 0, otherwise return 1. End of algorithm.

We argue that the algorithm can be formalized in $S$ .

In Step 0, we can check elementarily whether q has finite or infinite base-b expansion and in the former case compute its base-b length s. Since $E_{b}^{ξ^{'}} \in S$ and $S$ is closed under bounded summation, we can compute $\tilde{q}$ . The rest of Step 0 is obviously elementary.

In Step 1, the computation of m, n is trivially elementary, because $d_{i_{0}}$ is a fixed number. The search for i is bounded ( $i < n$ ) and we can check the two inequalities using the graph of d, which is elementary. Observe that at the end of Step 1, we do not know if we will be able to compute $d_{2 i + 1}$ or $d_{2 i + 2}$ .

In Step 2, we can compute $d_{2 i}$ ( $d_{2 i} ⩽ n$ ) and check the inequality again using the graph of d. In Step 3, we have $d_{2 i + 1} ⩽ d_{2 i} + n$ , so we can compute $d_{2 i + 1}$ , $u_{i}$ ( $g \in S$ ) and also $σ_{i + 1}$ , because it is elementary in $d_{2 i + 1}$ . After that, we check in a similar way the inequality $u_{i} + n < d_{2 i + 2}$ and compute $d_{2 i + 2}$ in case it is false.

In Step 4, we have previously calculated the parameter P, so we can execute the bounded search using the functions $digit$ and $E_{b}^{ξ^{'}}$ , which belong to the class $S$ .

Now we prove the correctness of the algorithm.

In Step 0, if q has a finite base-b expansion of length s, then clearly we need to check only the first s base-b digits of $ξ^{'}$ in order to compare $ξ^{'}$ and q.

The output in Step 4 is obviously correct, provided that the search for k is successful. So it remains to prove that in the three cases where Step 4 is invoked, the value of the parameter P is correct, that is the base-b expansions of $ξ^{'}$ and q differ in at least one position $⩽ P$ .

Let us assume that $d_{2 i} + n < d_{2 i + 1}$ in Step 2. On one hand, by Theorem 2.3 at least one base-b digit of q in positions $d_{2 i}, \dots, d_{2 i} + n$ is different from $0$ . On the other hand, $ξ^{'}$ by definition has base-b digit $0$ in all positions in $[d_{2 i}, d_{2 i} + n]$ . Thus $P = d_{2 i} + n$ is a correct value in this case.

Suppose that $u_{i} + n < d_{2 i + 2}$ in Step 3. We have $n ⩾ d_{i_{0}}$ and $n < d_{2 i + 2}$ , which implies $2 i + 1 ⩾ i_{0}$ , therefore we can use (4.1) and the definition of $ξ^{'}$ to obtain successively $\begin{aligned} d_{2 i + 1} + 1 ⩽ x^{'} ⩽ d_{2 i + 2} - g (d_{2 i + 1}) ⟹ E_{b}^{ξ} (x^{'}) = 0, \\ d_{2 i + 1} + 1 + σ_{i + 1} ⩽ x ⩽ d_{2 i + 2} - g (d_{2 i + 1}) + σ_{i + 1} ⟹ E_{b}^{ξ^{'}} (x) = 0 . \end{aligned}$ Note that $d_{2 i + 2} - g (d_{2 i + 1}) + σ_{i + 1} < d_{2 i + 2}$ , which is implied by $σ_{i + 1} < d_{2 i + 1}$ and $g (d_{2 i + 1}) ⩾ d_{2 i + 1}$ . Now the supposed inequality $u_{i} + n < d_{2 i + 2}$ and $u_{i} = d_{2 i + 1} + 1 + g (d_{2 i + 1})$ give $\begin{array}{r} d_{2 i + 1} + 1 + σ_{i + 1} + n < d_{2 i + 2} - g (d_{2 i + 1}) + σ_{i + 1} \end{array}$ and we may reason as in the previous Step 2: some base-b digit of q in a position in the interval $[d_{2 i + 1} + 1 + σ_{i + 1}, \dots, d_{2 i + 1} + 1 + σ_{i + 1} + n]$ is different from $0$ , while $ξ^{'}$ has only $0$ -s in the same positions. Therefore, the value $P = d_{2 i + 1} + 1 + σ_{i + 1} + n$ is correct.

Finally, since $d_{2 i + 2} + n < 2 d_{2 i + 2} < d_{2 i + 3}$ , the number q possesses a non-zero base-b digit in at least one position in $[d_{2 i + 2}, d_{2 i + 2} + n]$ , while by definition $ξ^{'}$ does not. Therefore, $P = d_{2 i + 2} + n$ is a correct value in this last case. □

Note that the above algorithm works, because we have the additional property (4.1) of ξ, which we use substantially in Step 3. It allows us to resolve the case where we can compute $d_{2 i + 1}$ , but we cannot compute $d_{2 i + 2}$ .

Now we will consider another property, which combined with $ξ \in S_{b E}$ implies $ξ^{'} \in S_{D}$ .
Definition 5.4.
The function $\hat{T} : Q \to Q$ will be called a trace function from below for the irrational number ξ if $\begin{array}{r} q < ξ ⟹ q < \hat{T} (q) < ξ \end{array}$ for any $q \in Q$ .

Trace functions are connected with other representations of the irrational numbers, which we will not define formally. It is shown in [3] that if the general sum approximation from below of ξ is in the class $S$ , then one can construct a trace function from below for ξ, which belongs to $S$ . Such a construction is also possible, provided that the continued fraction of ξ belongs to $S$ (see [7]).

One of the anonymous referees posed the question whether the existence of a trace function from below in $S$ for ξ is sufficient to infer that the Dedekind cut $D^{ξ}$ is also in $S$ . Of course, there does not exist a uniform computable conversion from $\hat{T}$ to $D^{ξ}$ , simply because $\hat{T}$ can be a trace function from below for more that one irrational number. But it turns out that a non-uniform subrecursive conversion (which depends on external information about ξ) is also not possible. One can construct a computable irrational number ξ, such that $D^{ξ} \notin S$ , but ξ has elementary trace function from below. The next lemma shows that the situation changes if we add the additional assumption that the base-b expansion of ξ belongs to $S$ .
Lemma 5.5.
Let $ξ \in S_{b E}$ and let there exist a trace function from below $\hat{T}$ for ξ, such that $\hat{T} \in S$ . Then $ξ \in S_{D}$ .
Proof.
We will give an algorithm for the Dedekind cut $D^{ξ}$ , which is elementary in $E_{b}^{ξ}$ and $\hat{T}$ . Note that the difficulty here is that if the inequality $q < \hat{T} (q)$ holds, then $\hat{T}$ alone will not reveal whether $q < ξ$ or $q > ξ$ .

Start of algorithm. Given a rational number q:

Step 1. Compute $\hat{T} (q)$ . If $\hat{T} (q) ⩽ q$ give output 1, else go to Step 2.

Step 2. Compute the least n, such that ${digit}_{n} (q, b) \neq {digit}_{n} (\hat{T} (q), b)$ .

Step 3. If there exists $k ⩽ n$ , such that ${digit}_{k} (q, b) \neq E_{b}^{ξ} (k)$ , go to Step 4. Otherwise, give output 1.

Step 4. Compute the least $k ⩽ n$ with ${digit}_{k} (q, b) \neq E_{b}^{ξ} (k)$ . If ${digit}_{k} (q, b) < E_{b}^{ξ} (k)$ return 0, otherwise return 1. End of algorithm.

For the correctness of the algorithm, we only need to justify the output in Step 3. Assume $q < ξ$ . Then $q < \hat{T} (q) < ξ$ and since the base-b expansions of q and $\hat{T} (q)$ differ in position n, the base-b expansions of q and ξ differ in at least one position $⩽ n$ . It follows that the output 1 in Step 3 is indeed correct.

The algorithm is obviously elementary in $E_{b}^{ξ}$ and $\hat{T}$ . Note that the search for n in Step 2 is bounded by the product of the denominators of q and $\hat{T} (q)$ . Since $E_{b}^{ξ} \in S$ and $\hat{T} \in S$ , we obtain $D^{ξ} \in S$ , that is $ξ \in S_{D}$ . □

Now we are ready to prove our result, which connects the complexity of $D^{ξ^{'}}$ with the existence of a trace function from below.
Theorem 5.6.
Let $ξ \in S_{b E}$ and let there exist a trace function from below $\hat{T} \in S$ for ξ. Then $ξ^{'} \in S_{D}$ .
Proof.
Our algorithm for $D^{ξ^{'}}$ will be very similar to the one in Theorem 5.3 with modifications starting from Step 3 onwards.

Start of algorithm. Given a rational number q:

Step 0. If q has an infinite base-b expansion proceed with Step 1. Otherwise, compute the base-b length s of q and $\tilde{q} = \sum_{j ⩽ s} E_{b}^{ξ^{'}} (j) b^{- j}$ . If $q ⩽ \tilde{q}$ give output 0 and if $q > \tilde{q}$ give output 1.

Step 1. Compute m, n, such that $q = m n^{- 1}$ and $n ⩾ d_{0}$ . Search for the unique i, such that $d_{2 i} ⩽ n < d_{2 i + 2}$ .

Step 2. Check whether the following relation holds: $d_{2 i} + n < d_{2 i + 1}$ . If it is true, proceed with Step 7 ( $P = d_{2 i} + n$ ), otherwise go to Step 3.

Step 3. Compute $d_{2 i + 1}$ . Search for $x < d_{2 i + 1}$ , such that ${digit}_{x} (q, b) \neq E_{b}^{ξ^{'}} (x)$ . In case such an x exists, proceed with Step 7 ( $P = x$ ), otherwise go to Step 4.

Step 4. Compute $q^{'} = del (i + 1, q)$ . If $D^{ξ} (q^{'}) = 1$ , return 1. Otherwise, go to Step 5.

Step 5. Compute $\hat{T} (q^{'})$ . Search for the least l, such that ${digit}_{l} (q^{'}, b) \neq {digit}_{l} (\hat{T} (q^{'}), b)$ and compute $l^{'} = l + σ_{i + 1}$ .

Step 6. Check the inequality: $l^{'} < d_{2 i + 2}$ . If it holds, proceed with Step 7 ( $P = l^{'}$ ). If it does not, compute $d_{2 i + 2}$ and proceed with Step 7 ( $P = d_{2 i + 2} + n$ ).

Step 7 (parameter P). Compute the least $k ⩽ P$ , such that ${digit}_{k} (q, b) \neq E_{b}^{ξ^{'}} (k)$ .

If ${digit}_{k} (q, b) < E_{b}^{ξ^{'}} (k)$ return 0, otherwise return 1. End of algorithm.

It is not hard to see that the algorithm can be formalized in $S$ . The five important points are: (1) $E_{b}^{ξ^{'}} \in S$ , since $E_{b}^{ξ^{'}} ⩽_{E} E_{b}^{ξ}$ and $E_{b}^{ξ} \in S$ ; (2) the graph of d is elementary; (3) we have access to $d_{2 i + 1}$ in Steps 3, 4, 5; (4) $del (i + 1, q)$ can be computed in Step 3 using Lemma 5.2; (5) $\hat{T} \in S$ by assumption and $D^{ξ} \in S$ by Lemma 5.5.

It remains to check the correctness of the modified steps. In Step 4 the base-b expansions of q and $ξ^{'}$ are identical in all positions $< d_{2 i + 1}$ . Therefore $q = ins (i + 1, q^{'})$ and $q^{'} > ξ$ implies $q = ins (i + 1, q^{'}) > ins (i + 1, ξ) > ξ^{'}$ . So the output 1 in Step 4 is correct. In Step 5 we have $q^{'} < \hat{T} (q^{'}) < ξ$ and clearly, the base-b expansions of $q^{'}$ and ξ differ in at least one position $⩽ l$ , which guarantees that the base-b expansions of $q = ins (i + 1, q^{'})$ and $ins (i + 1, ξ)$ will differ in a position $⩽ l^{'}$ . In the case $l^{'} < d_{2 i + 2}$ , $ins (i + 1, ξ)$ and $ξ^{'}$ coincide in all positions $⩽ l^{'}$ , therefore $P = l^{'}$ is a correct value for the parameter of Step 7. □

So far we have seen irrational numbers ξ, such that $ξ \in S_{D}$ and $ξ^{'} \in S_{D}$ . It is important to note that the proofs of Theorem 5.3 and Theorem 5.6 both used additional properties of ξ besides $E_{b}^{ξ} \in S$ . By a closer inspection of the algorithm, it becomes clear that it is not possible to advance from $d_{2 i + 1}$ to $d_{2 i + 2}$ without such properties. Indeed, we will see in the next section that the sole assumption $ξ \in S_{b E}$ is not sufficient to prove $ξ^{'} \in S_{D}$ . However, we do not know if there exists $δ \in S_{D}$ (a stronger assumption than $δ \in S_{b E}$ ), such that $δ^{'} \notin S_{D}$ .

Our next task will be to produce α with $α \in S_{b E}$ and $α^{'} \in S_{D}$ , but $α \notin S_{D}$ .

In order to do that we turn to the construction from Theorem 5.3 in [8]. Since it is crucial for understanding the rest of the paper, we reproduce the proof with some slight modifications.
Definition 5.7.
Let p be a prime, which does not divide b and $d_{0} = max (p, b)$ .

Let the sequence $q : N \to Q$ be defined by $\begin{aligned} q_{0} = p^{- 1}, q_{2 i + 1} = q_{2 i}, \\ q_{2 i + 2} = \{\begin{array}{ll} q_{2 i + 1} - p^{- b k}, & if U (μ t ⩽ d_{2 i + 2} [T_{1} ({(i)}_{0}, d_{2 i + 1}, t)]) ⩾ q_{2 i + 1}, \\ q_{2 i + 1} + p^{- b l}, & otherwise, \end{array} \\ k = k_{i} = μ_{k ⩾ d_{2 i + 2}} [{digit}_{k} (q_{2 i + 1}, b) \neq 0], l = l_{i} = μ_{l ⩾ d_{2 i + 2}} [{digit}_{l} (q_{2 i + 1}, b) \neq \overline{0}], \end{aligned}$ and let $α = {lim}_{i \to \infty} q_{i}$ .

Claim 1. For all $i \in N$ : $\begin{matrix} (5.1) & d_{2 i + 2} ⩽ k_{i} < 2 d_{2 i + 2}, d_{2 i + 2} ⩽ l_{i} < 2 d_{2 i + 2} and \exists m \in N (q_{2 i} = m p^{- 2 b d_{2 i}}) . \end{matrix}$

Proof of Claim 1. Induction on i. Clearly, $q_{0} = p^{- 1}$ can be written in the form $q_{0} = m p^{- 2 b d_{0}}$ . Now assume we have $q_{2 i} = m p^{- 2 b d_{2 i}}$ for some i. Let s be the number of consecutive $0$ -s in the base-b expansion of $q_{2 i}$ , starting at position $d_{2 i + 2}$ . Since p does not divide b, $q_{2 i}$ has an infinite base-b expansion and it follows from Theorem 2.3 that $b^{s} < p^{2 b d_{2 i}}$ , therefore $\begin{array}{r} k_{i} = d_{2 i + 2} + s < d_{2 i + 2} + 2 p b d_{2 i} < d_{2 i + 2} + f^{'} (f^{'} (d_{2 i})) = 2 d_{2 i + 2} . \end{array}$ The other equality $l_{i} < 2 d_{2 i + 2}$ is proved analogously by taking the number of consecutive $\overline{0}$ -s. Now $q_{2 i + 2} = q_{2 i} - p^{- b k_{i}}$ or $q_{2 i + 2} = q_{2 i} + p^{- b l_{i}}$ and the denominators of both summands are powers of p with exponents $⩽ 2 b d_{2 i + 2}$ . This establishes the induction step.

Applying again Theorem 2.3 and noting that $b^{2 p b d_{2 i}} > p^{2 b d_{2 i}}$ , we obtain that for all $x, i \in N$ : $\begin{aligned} (5.2) & \exists j_{1} \in [x, x + 2 p b d_{2 i}] {digit}_{j_{1}} (q_{2 i}, b) \neq 0, \\ (5.3) & \exists j_{2} \in [x, x + 2 p b d_{2 i}] {digit}_{j_{2}} (q_{2 i}, b) \neq \overline{0} . \end{aligned}$

Claim 2. $q_{2 i} < q_{2 i + 2} \Rightarrow q_{2 i} < α and q_{2 i} > q_{2 i + 2} \Rightarrow q_{2 i} > α$ .

Proof of Claim 2. We have $α - q_{2 i} = \sum_{j = i}^{\infty} (q_{2 j + 2} - q_{2 j})$ . Now assume $q_{2 i} < q_{2 i + 2}$ . Then $\begin{array}{r} α - q_{2 i} = p^{- b l_{i}} + \sum_{j = i + 1} (q_{2 j + 2} - q_{2 j}) > 0, \end{array}$ because using (5.1) we can infer $\begin{array}{r} | \sum_{j = i + 1} (q_{2 j + 2} - q_{2 j}) | ⩽ \sum_{j = i + 1} | q_{2 j + 2} - q_{2 j} | ⩽ \sum_{j = i + 1} p^{- b d_{2 j + 2}} < p^{- 2 b d_{2 i + 2}} < p^{- b l_{i}} . \end{array}$ The proof of the second part is symmetric.

Claim 3. $E_{p}^{α} \notin S$ , therefore $α \notin S_{D}$ .

Proof of Claim 3. Assume the opposite $E_{p}^{α} \in S$ , so that $E_{p}^{α} ⩽_{E} f$ . Then $ϕ ⩽_{E} f$ , where $ϕ (n) = \sum_{x = 0}^{n} E_{p}^{α} (x) p^{- x}$ . We choose e and k, so that (3.1) holds for all n. We can pick i and j, such that $i = ⟨ e, j ⟩$ and $d_{2 i + 1} ⩾ k$ (since $⟨ e, j ⟩$ is strictly increasing in j). Now we have: $\begin{aligned} ϕ (d_{2 i + 1}) & = U (μ t ⩽ f^{k} (d_{2 i + 1}) [T_{1} (e, d_{2 i + 1}, t)]) \\ = U (μ t ⩽ f^{'} (d_{2 i + 1}) [T_{1} (e, d_{2 i + 1}, t)]) = U (μ t ⩽ d_{2 i + 2} [T_{1} ({(i)}_{0}, d_{2 i + 1}, t)]) . \end{aligned}$

First case: $ϕ (d_{2 i + 1}) ⩾ q_{2 i + 1}$ . Then by construction $q_{2 i + 2} < q_{2 i + 1} = q_{2 i}$ and by Claim 2, $\begin{array}{r} α < q_{2 i} = q_{2 i + 1} ⩽ ϕ (d_{2 i + 1}), \end{array}$ which is impossible, because $α = \sum_{x = 0}^{\infty} E_{p}^{α} (x) p^{- x}$ .

Second case: $ϕ (d_{2 i + 1}) < q_{2 i + 1}$ . Note that $2 b d_{2 i} < d_{2 i + 1}$ , therefore by Claim 1, both numbers $ϕ (d_{2 i + 1})$ and $q_{2 i + 1} = q_{2 i}$ have finite base-p expansions of length $⩽ d_{2 i + 1}$ . So the first position, in which these base-p expansions are different is $⩽ d_{2 i + 1}$ . It follows that $α < q_{2 i}$ and $q_{2 i + 2} < q_{2 i}$ by Claim 2, while by construction $q_{2 i + 2} > q_{2 i + 1} = q_{2 i}$ - a contradiction.

Claim 4. The base-b expansions of $q_{2 i}$ and α coincide in all positions less than $d_{2 i + 2}$ , that is $\begin{array}{r} {digit}_{n} (q_{2 i}, b) = E_{b}^{α} (n) for all n < d_{2 i + 2} . \end{array}$

Proof of Claim 4. Suppose $q_{2 i + 2} = q_{2 i} + p^{- b l_{i}}$ . By Claim 2, we have $q_{2 i} < α$ and following a similar argument: $\begin{array}{r} α - q_{2 i} ⩽ \sum_{j = i} | q_{2 j + 2} - q_{2 j} | ⩽ p^{- b l_{i}} + \sum_{j = i + 1} p^{- b d_{2 j + 2}} < p^{- b l_{i}} + p^{- 2 b d_{2 i + 2}} < 2 p^{- b l_{i}} ⩽ b^{- l_{i}}, \end{array}$ because $p^{b} ⩾ 2 b \Rightarrow p^{b l_{i}} ⩾ 2 b^{l_{i}}$ . We have obtained $q_{2 i} < α < q_{2 i} + b^{- l_{i}}$ . It remains to note that $l_{i} ⩾ d_{2 i + 2}$ and ${digit}_{l_{i}} (q_{2 i}, b) \neq \overline{0}$ . In the other case $q_{2 i + 2} = q_{2 i} - p^{- b k_{i}}$ , we have the inequalities $q_{2 i} - b^{- k_{i}} < α < q_{2 i}$ and ${digit}_{k_{i}} (q_{2 i}, b) \neq 0$ , so the claim follows analogously.

Claim 5. $q_{2 i}$ can be computed elementarily in $d_{2 i}$ , and $E_{b}^{α}$ is elementary.

Proof of Claim 5. By the definition of $q_{2 i}$ and (5.1), there exists an elementary function H, such that $q_{2 i + 2} = H (q_{2 i}, d_{2 i + 2})$ . Moreover, the denominator and nominator of $q_{2 i}$ are bounded by an elementary function of $d_{2 i}$ . Therefore, $q_{2 i}$ can be computed with bounded primitive recursion as a function of $d_{2 i}$ .

Now given $n \in N$ : we search for the unique i, such that $d_{2 i} ⩽ n < d_{2 i + 2}$ and give output ${digit}_{n} (q_{2 i}, b)$ . Clearly, this is an elementary algorithm, which by Claim 4 computes $E_{b}^{α} (n)$ .

It will be convenient to introduce a notation for the function $χ : N \to {0, 1}$ ,

so that $χ (i + 1) = 0$ is a shorthand for the predicate used in the construction of α. Note that by Claim 5, $χ (i)$ can be computed elementarily in $d_{2 i}$ .

The intuition behind the construction of α is the following: in order to obtain $E_{p}^{α} \notin S$ , we make sure that α stays far enough from certain rational numbers q with finite base-p expansion, generated using the class $S$ . When we take a left turn ( $q_{2 i + 2} < q_{2 i}$ ) α is guaranteed to be different from such a $q ⩾ q_{2 i}$ and similarly, when we take a right turn ( $q_{2 i + 2} > q_{2 i}$ ), α is guaranteed to be different from such a $q < q_{2 i}$ . Of course, the subtle point is to obtain $E_{b}^{α} \in S$ at the same time.

While it is clear that $α \notin S_{D}$ , it turns out that $α^{'} \in S_{D}$ . The reason seems to be that adding strings of zero digits in positions $[d_{2 i}, d_{2 i + 1})$ for all i destroys the effect of the right turns (though the effect of the left turns is preserved). Theorem 5.8.
The Dedekind cut of $α^{'}$ is elementary, where α is the irrational number constructed in Definition 5.7 .
Proof.
We will describe an algorithm to compute the Dedekind cut of $α^{'}$ using the method from Theorem 5.3 and Theorem 5.6.

Start of algorithm. Given a rational number q:

Step 0. If q has an infinite base-b expansion proceed with Step 1. Otherwise, compute the base-b length s of q and $\tilde{q} = \sum_{j ⩽ s} E_{b}^{α^{'}} (j) b^{- j}$ . If $q ⩽ \tilde{q}$ give output 0 and if $q > \tilde{q}$ give output 1.

Step 1. Compute m, n, such that $q = m n^{- 1}$ and $n ⩾ d_{0}$ . Search for the unique i, such that $d_{2 i} ⩽ n < d_{2 i + 2}$ .

Step 2. Check whether the following relation holds: $d_{2 i} + n < d_{2 i + 1}$ . If it is true, proceed with Step 5 ( $P = d_{2 i} + n$ ), otherwise go to Step 3.

Step 3. Compute $d_{2 i + 1}$ , $q_{2 i}$ and $q_{2 i}^{'} = ins (i + 1, q_{2 i})$ . If $q = q_{2 i}^{'}$ , then give output 1, otherwise go to Step 4.

Step 4. Compute the least s, such that ${digit}_{s} (q, b) \neq {digit}_{s} (q_{2 i}^{'}, b)$ . Check the inequality: $s < d_{2 i + 2}$ . If it holds, proceed with Step 5 ( $P = s$ ). If it does not, compute $d_{2 i + 2}$ and proceed with Step 5 ( $P = d_{2 i + 2} + n$ ).

Step 5 (parameter P). Compute the least $k ⩽ P$ with ${digit}_{k} (q, b) \neq E_{b}^{α^{'}} (k)$ .

If ${digit}_{k} (q, b) < E_{b}^{α^{'}} (k)$ return 0, otherwise return 1. End of algorithm.

It is easy to see that the algorithm is elementary: $E_{b}^{α^{'}}$ is elementary, since $E_{b}^{α^{'}} ⩽_{E} E_{b}^{α}$ and $ins (i + 1, q_{2 i})$ can be computed in Step 3 using Lemma 5.2, because we have access to $d_{2 i + 1}$ .

As for the correctness, only the new Steps 3, 4 require justification.

In Step 3, we know by Claim 4 that the first $d_{2 i + 2}$ base-b digits of α and $q_{2 i}$ coincide. The same is true for $ins (i + 1, α)$ and $q_{2 i}^{'} = ins (i + 1, q_{2 i})$ , because they are obtained by inserting $0$ -s in the same positions. Of course, $ins (i + 1, α)$ and $α^{'}$ are also identical in all positions $< d_{2 i + 2}$ . Now $q = q_{2 i}^{'}$ implies that ${digit}_{x} (q, b) = E_{b}^{α^{'}} (x)$ for all $x < d_{2 i + 2}$ . But $d_{2 i + 2} + n < 2 d_{2 i + 2} < d_{2 i + 3}$ , thus by Theorem 2.3 at least one base-b digit of q in positions $[d_{2 i + 2}, d_{2 i + 3})$ is not $0$ , whereas $α^{'}$ has only $0$ -s in the same positions. We conclude that $q > α^{'}$ and the output 1 is correct. Note that we cannot use Step 5 to produce this output, because we do not have access to a position P in which the base-b expansions of $α^{'}$ and q are different.

In Step 4, if $s < d_{2 i + 2}$ , then the base-b expansions of $α^{'}$ and q are different in position s, since ${digit}_{s} (q_{2 i}^{'}, b) = E_{b}^{α^{'}} (s)$ . We conclude that the value $P = s$ is correct for the parameter in Step 5. □

6. An irrational number with a complex Dedekind cut, which remains complex after adding long sequences of zeros

Our goal in this section will be to produce an irrational number β with an elementary base-b expansion, such that $β \notin S_{D}$ and $β^{'} \notin S_{D}$ .

We will again exploit the construction of the number α from Definition 5.7, but this time in a more sophisticated manner. The idea is roughly the following: firstly, we construct the number γ, whose base-b expansion is obtained from the base-b expansion of α by simultaneously inserting $0$ -s in all positions $[d_{2 i}, d_{2 i + 1})$ with ( $χ (i) = 0$ ) and $\overline{0}$ -s in all positions $[d_{2 i}, d_{2 i + 1})$ with ( $χ (i) = 1$ ). Unlike the real number $α^{'}$ from the previous section, whose definition destroyed the effect of the right turns in the construction of α, the definition of γ is consistent with both the left and the right turns. Therefore, we will be able to show that $γ \notin S_{D}$ . After that we produce $β^{'}$ by adding $1$ to the last digit in each string of $\overline{0}$ -s in positions $[d_{2 i}, d_{2 i + 1})$ with . Clearly, each of these strings will be transformed into a string of $0$ -s and we will see that only a small portion of other digits is altered. Moreover, since the added $1$ -s are sparse enough, the complexity of the Dedekind cut will not change, that is $β^{'} \notin S_{D}$ . Finally, it turns out that after removing the strings of $0$ -s from $β^{'}$ , the produced number β will still have a Dedekind cut outside $S$ .

We emphasize again the reason for the different complexity of $α^{'}$ and $β^{'}$ . The number $β^{'}$ is close enough to γ, which is defined in such a way as to preserve the effects of the construction of α. The number $α^{'}$ is not close enough to α and its definition destroys the effects of the construction of α.

More formally, we begin by defining γ: $\begin{array}{r} E_{b}^{γ} (x) = \{\begin{array}{ll} E_{b}^{α} (x), & if x < d_{0}, \\ 0, & if d_{2 i} ⩽ x < d_{2 i + 1} & χ (i) = 0, \\ \overline{0}, & if d_{2 i} ⩽ x < d_{2 i + 1} & χ (i) = 1, \\ E_{b}^{α} (x^{'}), & if d_{2 i + 1} ⩽ x < d_{2 i + 2}, \end{array} \end{array}$ where $x^{'} = x - σ_{i + 1}$ . First of all $E_{b}^{γ}$ is elementary: $E_{b}^{α}$ and the graph of d are elementary, $χ (i)$ is elementary in x when $d_{2 i} ⩽ x$ and $x^{'}$ is elementary in x in the case $d_{2 i + 1} ⩽ x$ . Also note that γ is irrational, because α is irrational or as a corollary of the following theorem.

Theorem 6.1.
$γ \notin S_{D}$ .
Proof.
We will need to use the function ${ins}^{'} : N \times R \to R$ (very similar to $ins$ from the previous section) defined by $\begin{array}{r} {ins}^{'} (i, δ) = ins (i, δ) + \sum_{j < i} (χ (j) . (b^{- d_{2 j} + 1} - b^{- d_{2 j + 1} + 1})) . \end{array}$ So to compute ${ins}^{'} (i, δ)$ we insert $0$ -s in the base-b expansion of ξ in positions $[d_{2 j}, d_{2 j + 1})$ for all $j < i$ and in the case $χ (j) = 1$ we change them to $\overline{0}$ -s. Note that for $q \in Q$ , ${ins}^{'} (i, q)$ is elementary in i, q and , which follows from Lemma 5.2 and the fact that the bounded sum in the second summand is elementary in i, .

Suppose by way of a contradiction that $D^{γ} \in S$ , so that $D^{γ} ⩽_{E} f$ .

Part 1. In this part we will prove we can choose i, such that $\begin{matrix} (6.1) & χ (i + 1) = 0 ⟺ {ins}^{'} (i + 1, q_{2 i}) < γ . \end{matrix}$ To this end we will need the auxiliary functions $\tilde{q}$ and $\tilde{{ins}^{'}}$

and also the function ψ, defined by $ψ (n) = μ_{x ⩽ n} [d_{x} ⩾ n]$ . All of them are easily seen to be elementary.

It will be instructive to follow the proof of Claim 3 from the previous section. Let us define the function ϕ by $\begin{array}{r} ϕ (n) = \{\begin{array}{ll} \frac{1}{2} \tilde{q} (i, n) & if D^{γ} (\tilde{{ins}^{'}} (i + 1, \tilde{q} (i, n), n)) \neq 0, \\ \tilde{q} (i, n) & if D^{γ} (\tilde{{ins}^{'}} (i + 1, \tilde{q} (i, n), n)) = 0, \end{array} \end{array}$ where . We have assumed $D^{γ} ⩽_{E} f$ , so it easily follows that $ϕ ⩽_{E} f$ . Hence we can choose e, k, such that (3.1) holds for all n and we also pick i, j with $i = ⟨ e, j ⟩$ and $d_{2 i + 1} ⩾ k$ . For this choice of i, we obtain exactly as in Claim 3 that $\begin{array}{r} χ (i + 1) = 0 ⟺ q_{2 i + 2} < q_{2 i} ⟺ ϕ (d_{2 i + 1}) ⩾ q_{2 i + 1} = q_{2 i}, \end{array}$ so we must show that $\begin{array}{r} ϕ (d_{2 i + 1}) ⩾ q_{2 i} ⟺ {ins}^{'} (i + 1, q_{2 i}) < γ . \end{array}$ But this is easily done by substitution of $d_{2 i + 1}$ for n in the definition of ϕ, noting that $\begin{array}{r} ψ (d_{2 i + 1}) = 2 i + 1, \tilde{q} (i, d_{2 i + 1}) = q_{2 i}, \tilde{{ins}^{'}} (i + 1, q_{2 i}, d_{2 i + 1}) = {ins}^{'} (i + 1, q_{2 i}) . \end{array}$

Part 2. Now we consider two cases after choosing i from Part 1.

Case 1. $χ (i + 1) = 0$ is true. Since the base-b expansions of α and $q_{2 i}$ are identical in all positions less than $d_{2 i + 2}$ , the same is true for γ and ${ins}^{'} (i + 1, q_{2 i})$ , because they are obtained from α and $q_{2 i}$ by adding strings of $0$ -s or $\overline{0}$ -s in the same positions. In positions $[d_{2 i + 2}, d_{2 i + 3})$ by definition γ has only $0$ -s, because $χ (i + 1) = 0$ . On the other hand, ${ins}^{'} (i + 1, q_{2 i})$ will have at least one non-zero base-b digit in these positions. Indeed, in all positions $⩾ d_{2 i + 1}$ the base-b expansion of ${ins}^{'} (i + 1, q_{2 i})$ coincides with the shifted base-b expansion of $q_{2 i}$ . Therefore by (5.2), we can choose j, such that $\begin{array}{r} j \in [d_{2 i + 2}, d_{2 i + 2} + 2 p b d_{2 i}] & {digit}_{j} ({ins}^{'} (i + 1, q_{2 i}), b) \neq 0 \end{array}$ and in addition, $j ⩽ d_{2 i + 2} + 2 p b d_{2 i} < 2 d_{2 i + 2} < d_{2 i + 3}$ . We have proved that ${ins}^{'} (i + 1, q_{2 i}) > γ$ , which contradicts (6.1), because we are in the case $χ (i + 1) = 0$ .

Case 2. $χ (i + 1) = 1$ is true. The argument here is symmetric. We may choose j by (5.3), such that $\begin{array}{r} j \in [d_{2 i + 2}, d_{2 i + 2} + 2 p b d_{2 i}] & {digit}_{j} ({ins}^{'} (i + 1, q_{2 i}), b) \neq \overline{0}, \end{array}$ moreover γ and ${ins}^{'} (i + 1, q_{2 i})$ coincide in all positions less than $d_{2 i + 2}$ and γ has $\overline{0}$ -s in $[d_{2 i + 2}, d_{2 i + 3})$ . Therefore, ${ins}^{'} (i + 1, q_{2 i}) < γ$ , which contradicts (6.1) and $χ (i + 1) = 1$ . □
Definition 6.2.
Let us define for an arbitrary i $\begin{matrix} (6.2) & q_{i}^{γ} = \sum_{s < d_{2 i}} E_{b}^{γ} (s) b^{- s}, q_{i}^{'} = \sum_{j < i} χ (j) b^{- d_{2 j + 1} + 1}, \hat{q_{i}} = q_{i}^{γ} + q_{i}^{'} \end{matrix}$ and $\begin{array}{r} β^{'} = lim_{i \to \infty} \hat{q_{i}} = γ + \sum_{j = 0}^{\infty} χ (j) b^{- d_{2 j + 1} + 1} . \end{array}$

Note that the summands of the series contribute only in the case $χ (j) = 1$ , that is when γ has $\overline{0}$ -s in the positions $[d_{2 j}, d_{2 j + 1})$ .
Lemma 6.3.
For all n, i $\begin{aligned} (6.3) & n < d_{2 i + 2} - 1 - 2 p b d_{2 i} ⟹ {digit}_{n} (q_{i + 1}^{γ} + b^{- d_{2 i + 2} + 1}, b) = E_{b}^{γ} (n), \\ (6.4) & χ (i) = 0 ⟹ \hat{q_{i}} ⩽ β^{'} < \hat{q_{i}} + b^{- d_{2 i + 1} + 1}, \\ (6.5) & χ (i) = 1 ⟹ \hat{q_{i}} + b^{- d_{2 i} + 1} ⩽ β^{'} < \hat{q_{i}} + b^{- d_{2 i} + 1} + b^{- d_{2 i + 1} + 1} . \end{aligned}$
Proof.
By the definitions of $q_{i + 1}^{γ}$ and γ, the base-b expansion of $q_{i + 1}^{γ}$ in positions $[d_{2 i + 1}, d_{2 i + 2})$ coincides with the shifted base-b expansion of $q_{2 i}$ and α. Note also that $[d_{2 i + 2} - 1 - 2 p b d_{2 i}, d_{2 i + 2}) \subseteq [d_{2 i + 1}, d_{2 i + 2})$ , because $d_{2 i + 1} + 2 p b d_{2 i} < d_{2 i + 2}$ . Now we apply (5.3) to obtain j, such that $\begin{array}{r} j \in [d_{2 i + 2} - 1 - 2 p b d_{2 i}, d_{2 i + 2}) & {digit}_{j} (q_{i + 1}^{γ}, b) \neq \overline{0} . \end{array}$ Clearly, by adding $b^{- d_{2 i + 2} + 1}$ to $q_{i + 1}^{γ}$ we will only change its base-b digits from position j onwards, thus (6.3) holds for all n.

Observe that (6.3) is also true with the stronger antecedent $n < d_{2 i + 1}$ .

Now we turn to the other two statements from the lemma.

Case 1. Suppose that $χ (i) = 0$ . Then γ has $0$ -s in positions $[d_{2 i}, d_{2 i + 1})$ and we have $\begin{array}{r} q_{i}^{γ} ⩽ γ < q_{i}^{γ} + b^{- d_{2 i + 1} + 1} . \end{array}$ The first inequality in (6.4) follows trivially: $\begin{array}{r} \hat{q_{i}} = q_{i}^{γ} + q_{i}^{'} ⩽ γ + \sum_{j < i} χ (j) b^{- d_{2 j + 1} + 1} ⩽ β^{'} . \end{array}$ As for the second one, we have $γ < q_{i}^{γ} + b^{- d_{2 i + 1} + 1}$ , but the base-b length of the right-hand side is less than $d_{2 i + 1}$ , hence using (6.3) we infer $\begin{array}{r} q_{i + 1}^{γ} + b^{- d_{2 i + 2} + 1} < q_{i}^{γ} + b^{- d_{2 i + 1} + 1} \end{array}$ and since the inequality is strict and the base-b length of both sides is less than $d_{2 i + 2}$ , $\begin{array}{r} q_{i + 1}^{γ} + 2 b^{- d_{2 i + 2} + 1} ⩽ q_{i}^{γ} + b^{- d_{2 i + 1} + 1} . \end{array}$ This implies (using $χ (i) = 0$ ) $\begin{aligned} β^{'} & = γ + \sum_{j = 0}^{\infty} χ (j) b^{- d_{2 j + 1} + 1} \\ < q_{i + 1}^{γ} + b^{- d_{2 i + 2} + 1} + q_{i}^{'} + \sum_{j > i} χ (j) b^{- d_{2 j + 1} + 1} \\ < q_{i + 1}^{γ} + 2 b^{- d_{2 i + 2} + 1} + q_{i}^{'} ⩽ q_{i}^{γ} + b^{- d_{2 i + 1} + 1} + q_{i}^{'} \\ = \hat{q_{i}} + b^{- d_{2 i + 1} + 1}, \end{aligned}$ which proves the second part of (6.4).

Case 2. Now assume $χ (i) = 1$ . Then γ has $\overline{0}$ -s in positions $[d_{2 i}, d_{2 i + 1})$ , thus $\begin{array}{r} q_{i}^{γ} + b^{- d_{2 i} + 1} - b^{- d_{2 i + 1} + 1} ⩽ γ < q_{i}^{γ} + b^{- d_{2 i} + 1} . \end{array}$ The first inequality in (6.5) follows easily: $\begin{array}{r} \hat{q_{i}} + b^{- d_{2 i} + 1} = q_{i}^{γ} + q_{i}^{'} + b^{- d_{2 i} + 1} ⩽ γ + \sum_{j ⩽ i} χ (j) b^{- d_{2 j + 1} + 1} ⩽ β^{'} . \end{array}$ Then using $γ < q_{i}^{γ} + b^{- d_{2 i} + 1}$ , similarly to Case 1 we obtain $\begin{array}{r} q_{i + 1}^{γ} + 2 b^{- d_{2 i + 2} + 1} ⩽ q_{i}^{γ} + b^{- d_{2 i} + 1} . \end{array}$ Therefore $\begin{aligned} β^{'} & = γ + \sum_{j = 0}^{\infty} χ (j) b^{- d_{2 j + 1} + 1} \\ < q_{i + 1}^{γ} + b^{- d_{2 i + 2} + 1} + q_{i}^{'} + \sum_{j ⩾ i} χ (j) b^{- d_{2 j + 1} + 1} \\ < q_{i + 1}^{γ} + 2 b^{- d_{2 i + 2} + 1} + q_{i}^{'} + b^{- d_{2 i + 1} + 1} ⩽ q_{i}^{γ} + b^{- d_{2 i} + 1} + q_{i}^{'} + b^{- d_{2 i + 1} + 1} \\ = \hat{q_{i}} + b^{- d_{2 i} + 1} + b^{- d_{2 i + 1} + 1} . \end{aligned}$ □
Corollary 6.4.
For all n, i $\begin{array}{r} d_{2 i + 1} ⩽ n < d_{2 i + 2} - 1 - 2 p b d_{2 i} ⟹ E_{b}^{β^{'}} (n) = E_{b}^{γ} (n) . \end{array}$
Proof.
Let n, i satisfy the inequalities in the antecedent. Since $\hat{q_{i + 1}} = q_{i + 1}^{γ} + q_{i + 1}^{'}$ and the base-b length of $q_{i + 1}^{'}$ is strictly smaller than $d_{2 i + 1}$ we have that the base-b expansions of $\hat{q_{i + 1}}$ and $q_{i + 1}^{γ}$ are identical in all positions $[d_{2 i + 1}, d_{2 i + 2})$ .

In the case $χ (i + 1) = 0$ , (6.4) and $n < d_{2 i + 2}$ give $\begin{array}{r} E_{b}^{β^{'}} (n) = {digit}_{n} (\hat{q_{i + 1}}, b) = {digit}_{n} (q_{i + 1}^{γ}, b) = E_{b}^{γ} (n) \end{array}$ and in the case $χ (i + 1) = 1$ , (6.5) and (6.3) give $\begin{array}{r} E_{b}^{β^{'}} (n) = {digit}_{n} (\hat{q_{i + 1}} + b^{- d_{2 i + 2} + 1}, b) = {digit}_{n} (q_{i + 1}^{γ} + b^{- d_{2 i + 2} + 1}, b) = E_{b}^{γ} (n), \end{array}$ so we have the needed equality in both cases. □

It is evident from (6.4) and (6.5) that $β^{'}$ has $0$ -s in positions $[d_{2 i}, d_{2 i + 1})$ in its base-b expansion for all i, due to the fact that the base-b length of both $\hat{q_{i}}$ and $\hat{q_{i}} + b^{- d_{2 i} + 1}$ is strictly smaller than $d_{2 i}$ . Since γ is irrational, its base-b expansion does not stabilize in $0$ -s. Therefore, by Corollary 6.4 the base-b expansion of $β^{'}$ also does not stabilize in $0$ -s. This clearly implies that $β^{'}$ is irrational, because its base-b expansion has arbitrarily long strings ot $0$ -s and thus it cannot be periodic.
Theorem 6.5.
$E_{b}^{β^{'}}$ is elementary and $β^{'} \notin S_{D}$ .
Proof.
In both algorithms below we will use the rational numbers $\hat{q_{i}}$ and $q_{i}^{'}$ from Definition 6.2 (both are elementary in $d_{2 i}$ ). We begin with an algorithm for $E_{b}^{β^{'}}$ .

Start of algorithm. Given a natural number n:

Step 0. If $n < d_{0}$ , give the output $E_{b}^{β^{'}} (n)$ directly, otherwise go to Step 1.

Step 1. Compute the unique i, such that $d_{2 i} ⩽ n < d_{2 i + 2}$ .

Step 2. If $n < d_{2 i + 1}$ is true, give output $0$ . Otherwise, go to Step 3.

Step 3. Compute $d_{2 i}$ and check the inequality $n + 1 + 2 p b d_{2 i} < d_{2 i + 2}$ . In case it is true, give the output $E_{b}^{γ} (n)$ . In case it is false, go to Step 4.

Step 4. Compute $d_{2 i + 2}$ and the number $\hat{q_{i + 1}}$ from (6.2). If $χ (i + 1) = 0$ , give the output ${digit}_{n} (\hat{q_{i + 1}}, b)$ . If $χ (i + 1) = 1$ , give the output ${digit}_{n} (\hat{q_{i + 1}} + b^{- d_{2 i + 2} + 1}, b)$ . End of algorithm.

This algorithm is elementary: in Step 0, $d_{0}$ is a fixed number, so we can use a table for the needed values. All computations involving d are elementary, because so is the graph of d. In Step 3 we use the elementary function $E_{b}^{γ}$ . In Step 4, $\hat{q_{i + 1}}$ and $χ (i + 1)$ are elementary in $d_{2 i + 2}$ .

As for correctness: the output of Step 2 agrees with the fact that the base-b expansion of $β^{'}$ has $0$ -s in positions $[d_{2 i}, d_{2 i + 1})$ . In Step 3 the output is correct due to Corollary 6.4. In Step 4 we use $n < d_{2 i + 2}$ and (6.4) in the case $χ (i + 1) = 0$ , as well as (6.5) in the case $χ (i + 1) = 1$ .

For the second part of the theorem, we show that $D^{γ} ⩽_{E} D^{β^{'}}$ . Since we know that $γ \notin S_{D}$ , this will imply $β^{'} \notin S_{D}$ . We only prove the correctness of the algorithm and leave the reader to check it is elementary in $D^{β^{'}}$ .

Start of algorithm. Given a rational number q:

Step 0. If q has an infinite base-b expansion proceed with Step 1. Otherwise, compute $q^{'} = \sum_{j ⩽ s} E_{b}^{γ} (j) b^{- j}$ , where s is the base-b length of q. If $q ⩽ q^{'}$ give output 0 and if $q > q^{'}$ give output 1.

Step 1. Compute m, n, such that $q = m n^{- 1}$ and $n ⩾ d_{0}$ .

Step 2. Find the unique i, such that $d_{2 i} ⩽ n < d_{2 i + 2}$ and compute $\tilde{q_{i}} = q + q_{i}^{'}$ .

Step 3. Use $D^{β^{'}}$ to check: $\tilde{q_{i}} < β^{'}$ . If false, give output 1. If true, go to Step 4.

Step 4. Check the inequality $d_{2 i} + 2 n b^{n} < d_{2 i + 1}$ . If it holds, give output 0. Otherwise, go to Step 5.

Step 5. Compute $d_{2 i + 1}$ and $\tilde{q_{i + 1}} = q + q_{i + 1}^{'}$ . Use $D^{β^{'}}$ to check: $\tilde{q_{i + 1}} < β^{'}$ . If false, return 1. If true, return 0. End of algorithm.

The output in Step 0 is clearly correct in case q has a finite base-b expansion of length s. Note that after Step 0, both $\tilde{q_{i}}$ (in Step 2) and $\tilde{q_{i + 1}}$ (in Step 5) have infinite base-b expansion, because so does q.

In Step 3, consider the case $β^{'} ⩽ \tilde{q_{i}}$ . We have $\begin{array}{r} β^{'} ⩽ q + q_{i}^{'} ⩽ q + \sum_{j = 0}^{\infty} χ (j) b^{- d_{2 j + 1} + 1}, \end{array}$ therefore $γ ⩽ q$ and the output 1 is correct.

Suppose the inequality in Step 4 holds and that the output 0 is wrong, that is $γ ⩽ q$ . We also have $\tilde{q_{i}} < β^{'}$ after Step 3, hence $\begin{array}{r} \tilde{q_{i}} < β^{'} ⩽ q + \sum_{j = 0}^{\infty} χ (j) b^{- d_{2 j + 1} + 1} = \tilde{q_{i}} + \sum_{j = i}^{\infty} χ (j) b^{- d_{2 j + 1} + 1} < \tilde{q_{i}} + b^{- d_{2 i + 1} + 2} . \end{array}$ Let us denote by $n^{'}$ the denominator of $\tilde{q_{i}}$ . Clearly we have $n^{'} ⩽ n b^{d_{2 i}} ⩽ n b^{n}$ . By Theorem 2.3 we can choose j, such that $j \in [d_{2 i + 1} - n^{'} - 1, d_{2 i + 1} - 2]$ and ${digit}_{j} (\tilde{q_{i}}, b) \neq \overline{0}$ . It follows that for all s $\begin{array}{r} s < d_{2 i + 1} - n^{'} - 1 ⟹ {digit}_{s} (\tilde{q_{i}}, b) = {digit}_{s} (\tilde{q_{i}} + b^{- d_{2 i + 1} + 2}, b) = E_{b}^{β^{'}} (s) . \end{array}$ On one hand, we know that the base-b expansion of $β^{'}$ has only $0$ -s in positions $[d_{2 i}, d_{2 i + 1})$ . Therefore, the same is true for $\tilde{q_{i}}$ in positions $[d_{2 i}, d_{2 i + 1} - n^{'} - 2]$ . On the other hand, we have $[d_{2 i}, d_{2 i} + n^{'} - 1] \subseteq [d_{2 i}, d_{2 i + 1} - n^{'} - 2]$ , since $d_{2 i} + 2 n^{'} ⩽ d_{2 i} + 2 n b^{n} < d_{2 i + 1}$ due to the assumed inequality in Step 4. Applying Corollary 2.4 we infer that $\tilde{q_{i}}$ has a finite base-b expansion, which contradicts the assumption on q after Step 0. We conclude that the output 0 is correct.

If $\tilde{q_{i + 1}} ⩾ β^{'}$ in Step 5, we have $β^{'} ⩽ q + q_{i + 1}^{'} ⩽ q + \sum_{j = 0}^{\infty} χ (j) b^{- d_{2 j + 1} + 1}$ , therefore $γ ⩽ q$ and the output 1 is correct. Now let $\tilde{q_{i + 1}} < β^{'}$ and assume the output 0 is wrong, that is $γ ⩽ q$ . Similarly to Step 4 we have $\begin{array}{r} \tilde{q_{i + 1}} < β^{'} ⩽ q + \sum_{j = 0}^{\infty} χ (j) b^{- d_{2 j + 1} + 1} < \tilde{q_{i + 1}} + b^{- d_{2 i + 3} + 2} . \end{array}$ Let us denote by $n^{″}$ the denominator of $\tilde{q_{i + 1}}$ . By applying Theorem 2.3 in the same way as in Step 4, we obtain that for all s $\begin{array}{r} s < d_{2 i + 3} - n^{″} - 1 ⟹ {digit}_{s} (\tilde{q_{i + 1}}, b) = {digit}_{s} (\tilde{q_{i + 1}} + b^{- d_{2 i + 3} + 2}, b) = E_{b}^{β^{'}} (s) . \end{array}$ Since $β^{'}$ has $0$ -s in positions $[d_{2 i + 2}, d_{2 i + 3})$ in its base-b expansion, $\tilde{q_{i + 1}}$ also has $0$ -s in positions $[d_{2 i + 2}, d_{2 i + 3} - n^{″} - 2]$ . Now $n^{″}$ is the product of the denominators of q and $q_{i + 1}^{'}$ and $n < d_{2 i + 2}$ , therefore: $\begin{aligned} d_{2 i + 2} + 2 n^{″} + 1 & < d_{2 i + 2} + 2 n \cdot b^{d_{2 i + 1}} + 1 \\ < d_{2 i + 2} + 2 d_{2 i + 2} \cdot f (f (d_{2 i + 1})) + 1 \\ < d_{2 i + 2} + 2 {(d_{2 i + 2})}^{2} + 1 < d_{2 i + 3} . \end{aligned}$ So we have $[d_{2 i + 2}, d_{2 i + 2} + n^{″} - 1] \subseteq [d_{2 i + 2}, d_{2 i + 3} - n^{″} - 2]$ and $\tilde{q_{i + 1}}$ has $0$ -s in these positions. By Corollary 2.4, $\tilde{q_{i + 1}}$ has a finite base-b expansion, which contradicts the assumption on q after Step 0. Therefore, the output 0 is correct. □

Now we proceed with the study of the irrational number β, obtained by removing the $0$ -s in positions $[d_{2 i}, d_{2 i + 1})$ for all i from the base-b expansion of $β^{'}$ .

The following picture aims to clarify how the numbers α, β, $β^{'}$ are related: $\begin{aligned} χ (i) = 0 χ (i + 1) = 1 \\ d_{2 i} ↓ d_{2 i + 1} ↓ (+1) ↓ d_{2 i + 2} ↓ d_{2 i + 3} \\ β^{'} : .... α α 00000...00000 α α ..... α α ⋆ ⋆ 0000...0000 α α .... \\ β : .. α α α α ..... α α ⋆ ⋆ α α .... \\ (+1) ↑ \tilde{d_{2 i + 2}} \end{aligned}$ Sample values of $χ (i)$ and $χ (i + 1)$ are shown. The α-parts contain the digits of the base-b expansion of α. The starred part represents the changed digits after adding $1$ in position $d_{2 i + 2} - 1$ . Observe that the weight of the added $1$ is changed to $\tilde{d_{2 i + 2}} - 1$ after removing the zeros before position $d_{2 i + 2}$ to obtain β.
Definition 6.6.
We define the base-b expansion of β by $\begin{array}{r} E_{b}^{β} (n) = E_{b}^{β^{'}} (x) ⟺ (x < d_{0} & n = x) \lor (d_{2 i + 1} ⩽ x < d_{2 i + 2} & n = x - σ_{i + 1}) \end{array}$ (in agreement with Definition 5.1).

Formally, we must check that for any $n ⩾ d_{0}$ there exist unique x and i, such that the second disjunct of the right-hand side holds. Indeed, suppose $i_{1} < i_{2}$ and that for some $x_{1}$ , $x_{2}$ we have $\begin{array}{r} d_{2 i_{1} + 1} ⩽ x_{1} < d_{2 i_{1} + 2}, d_{2 i_{2} + 1} ⩽ x_{2} < d_{2 i_{2} + 2}, x_{1} - σ_{i_{1} + 1} = x_{2} - σ_{i_{2} + 1}, \end{array}$ so that $\begin{array}{r} x_{2} - x_{1} = \sum_{i_{1} < j ⩽ i_{2}} (d_{2 j + 1} - d_{2 j}) . \end{array}$ Since d is increasing, the last equality implies $x_{2} - x_{1} ⩽ d_{2 i_{2} + 1} - d_{2 i_{1} + 2}$ . But according to the above assumptions $x_{2} - x_{1} > d_{2 i_{2} + 1} - d_{2 i_{1} + 2}$ , a contradiction. This establishes the uniqueness of x and i, because $i_{1} = i_{2}$ clearly implies $x_{1} = x_{2}$ .

Now for a given $n ⩾ d_{0}$ , let us choose k, such that $d_{2 k} ⩽ n < d_{2 k + 2}$ . Let us also denote $\tilde{x} = n + σ_{k + 1}$ . Clearly, $\tilde{x} = n + σ_{k} + d_{2 k + 1} - d_{2 k} ⩾ d_{2 k + 1}$ . We have: $\begin{aligned} (6.6) & \tilde{x} & < d_{2 k + 2} ⟹ i = k & x = \tilde{x}, \\ (6.7) & \tilde{x} & ⩾ d_{2 k + 2} ⟹ i = k + 1 & x = \tilde{x} + d_{2 k + 3} - d_{2 k + 2}, \end{aligned}$ because in the second case $d_{2 k + 3} ⩽ \tilde{x} + d_{2 k + 3} - d_{2 k + 2}$ and $\begin{array}{r} \tilde{x} + d_{2 k + 3} - d_{2 k + 2} < n + d_{2 k + 1} + d_{2 k + 3} - d_{2 k + 2} < d_{2 k + 1} + d_{2 k + 3} < d_{2 k + 4} . \end{array}$ This establishes the existence.
Theorem 6.7.
$E_{b}^{β}$ is elementary.
Proof.
Observe that we always have $E_{b}^{β^{'}} ⩽_{E} E_{b}^{β}$ , but in general $E_{b}^{β} ≰_{E} E_{b}^{β^{'}}$ . Nevertheless, in our concrete case we can use $E_{b}^{β^{'}}$ , because we know it is elementary by Theorem 6.5. We will also use the elementary function $E_{b}^{α}$ .

Start of algorithm. Given a natural number n:

Step 0. If $n < d_{0}$ , return $E_{b}^{β^{'}} (n)$ , otherwise go to Step 1.

Step 1. Compute the unique k, such that $d_{2 k} ⩽ n < d_{2 k + 2}$ .

Step 2. If $n < d_{2 k + 1}$ is true, return $E_{b}^{α} (n)$ . Otherwise, go to Step 3.

Step 3. Compute $d_{2 k + 1}$ and the number $\tilde{x} = n + σ_{k + 1}$ . Check the inequality $\tilde{x} < d_{2 k + 2}$ . In case it is true, return $E_{b}^{β^{'}} (\tilde{x})$ . In case it is false, return $E_{b}^{α} (n)$ . End of algorithm.

We leave the reader to check that the algorithm is elementary and we will only discuss correctness. In Step 2, consider the case $n < d_{2 k + 1}$ . Now $\tilde{x}$ is well-defined, though we do not know if we can compute it. Still we have the inequalities $\begin{array}{r} d_{2 k + 1} ⩽ \tilde{x} < 2 d_{2 k + 1} < d_{2 k + 2} - 1 - 2 p b d_{2 k} . \end{array}$ Therefore, by (6.6), Corollary 6.4 and the definition of γ we have $\begin{array}{r} E_{b}^{β} (n) = E_{b}^{β^{'}} (\tilde{x}) = E_{b}^{γ} (\tilde{x}) = E_{b}^{α} (n) . \end{array}$ In Step 3, in the case $\tilde{x} < d_{2 k + 2}$ we again have $E_{b}^{β} (n) = E_{b}^{β^{'}} (\tilde{x})$ by (6.6). And finally, assume $\tilde{x} ⩾ d_{2 k + 2}$ . Then (6.7) gives $E_{b}^{β} (n) = E_{b}^{β^{'}} (x)$ , where $x = \tilde{x} + d_{2 k + 3} - d_{2 k + 2}$ . Now we have $\begin{array}{r} d_{2 k + 3} ⩽ x < n + d_{2 k + 1} + d_{2 k + 3} - d_{2 k + 2} < d_{2 k + 3} + d_{2 k + 1} < d_{2 k + 4} - 1 - 2 p b d_{2 k + 2} . \end{array}$ By Corollary 6.4 and the definition of γ, $\begin{array}{r} E_{b}^{β} (n) = E_{b}^{β^{'}} (x) = E_{b}^{γ} (x) = E_{b}^{α} (x^{'}) = E_{b}^{α} (n), \end{array}$ because $x^{'} = x - σ_{k + 2} = n$ . □

The next lemma gives an important relation between the Dedekind cuts of α and β.
Lemma 6.8.
For natural numbers j, i, let us denote $\begin{array}{r} \tilde{d_{2 j}} = d_{2 j} - σ_{j}, q_{i}^{″} = \sum_{j ⩽ i} χ (j) b^{- \tilde{d_{2 j}} + 1} . \end{array}$ Then the following equivalence is true: $\begin{matrix} (6.8) & q_{2 i} < α ⟺ q_{2 i} + q_{i}^{″} < β . \end{matrix}$
Proof.
We begin with the following auxiliary fact: for any n, i $\begin{matrix} (6.9) & n < \tilde{d_{2 i}} ⟹ E_{b}^{β} (n) = {digit}_{n} (q_{2 i} + q_{i}^{″}, b) . \end{matrix}$ Let $i = 0$ , that is $n < \tilde{d_{0}} = d_{0}$ . Then using (6.4) and (6.5) we obtain $\begin{array}{r} E_{b}^{β} (n) = E_{b}^{β^{'}} (n) = {digit}_{n} (\hat{q_{0}} + χ (0) b^{- d_{0} + 1}, b) \end{array}$ and we also have $\begin{array}{r} {digit}_{n} (\hat{q_{0}} + χ (0) b^{- d_{0} + 1}, b) = {digit}_{n} (q_{0} + χ (0) b^{- d_{0} + 1}, b) = {digit}_{n} (q_{0} + q_{0}^{″}, b), \end{array}$ because the base-b expansions of $\hat{q_{0}}$ and $q_{0}$ coincide in all positions less than $d_{0}$ (with the base-b expansions of γ and α).

Now let $i > 0$ and assume (6.9) holds for some i and all n. We show it holds also for $i + 1$ and all n. First consider the case $\tilde{d_{2 i}} ⩽ n < \tilde{d_{2 i + 2}}$ . We have $\begin{array}{r} d_{2 i} - σ_{i} ⩽ n < d_{2 i + 2} - σ_{i + 1} . \end{array}$ Let us denote $x = n + σ_{i + 1}$ . Then $d_{2 i + 1} ⩽ x < d_{2 i + 2}$ . Hence by Definition 6.6 and (6.4), (6.5) $\begin{aligned} E_{b}^{β} (n) & = E_{b}^{β^{'}} (x) = {digit}_{x} (\hat{q_{i + 1}} + χ (i + 1) b^{- d_{2 i + 2} + 1}, b) \\ = {digit}_{x} (q_{i + 1}^{γ} + χ (i + 1) b^{- d_{2 i + 2} + 1}, b) . \end{aligned}$ The last equality is true, because $\hat{q_{i + 1}} = q_{i + 1}^{γ} + q_{i + 1}^{'}$ and the base-b length of $q_{i + 1}^{'}$ is strictly less than $d_{2 i + 1}$ . We proceed: $\begin{aligned} E_{b}^{β} (n) & = {digit}_{x} (q_{i + 1}^{γ} + χ (i + 1) b^{- d_{2 i + 2} + 1}, b) \\ = {digit}_{x} (\sum_{d_{2 i + 1} ⩽ s < d_{2 i + 2}} E_{b}^{γ} (s) b^{- s} + χ (i + 1) b^{- d_{2 i + 2} + 1}, b) \\ = {digit}_{x} (\sum_{d_{2 i + 1} ⩽ s < d_{2 i + 2}} E_{b}^{α} (s - σ_{i + 1}) b^{- s} + χ (i + 1) b^{- d_{2 i + 2} + 1}, b) \\ = {digit}_{n + σ_{i + 1}} (\sum_{\tilde{d_{2 i}} ⩽ m < \tilde{d_{2 i + 2}}} E_{b}^{α} (m) b^{- m - σ_{i + 1}} + χ (i + 1) b^{- \tilde{d_{2 i + 2}} + 1 - σ_{i + 1}}, b) \\ = {digit}_{n} (\sum_{\tilde{d_{2 i}} ⩽ m < \tilde{d_{2 i + 2}}} E_{b}^{α} (m) b^{- m} + χ (i + 1) b^{- \tilde{d_{2 i + 2}} + 1}, b) \\ = {digit}_{n} (q_{2 i + 2} + q_{i}^{″} + χ (i + 1) b^{- \tilde{d_{2 i + 2}} + 1}, b) = {digit}_{n} (q_{2 i + 2} + q_{i + 1}^{″}, b) . \end{aligned}$ For the last row, observe that the base-b expansions of α and $q_{2 i + 2}$ coincide in all positions less than $\tilde{d_{2 i + 2}}$ and that the base-b length of $q_{i}^{″}$ is strictly less than $\tilde{d_{2 i}}$ .

Now the case $n < \tilde{d_{2 i}}$ remains. By the inductive hypothesis we have $\begin{array}{r} E_{b}^{β} (n) = {digit}_{n} (q_{2 i} + q_{i}^{″}, b) = {digit}_{n} (q_{2 i + 2} + q_{i}^{″}, b) . \end{array}$ Recall that $q_{2 i}$ and $q_{2 i + 2}$ coincide with α in all positions less than $\tilde{d_{2 i}}$ .

By Corollary 6.4, for all x, such that $d_{2 i + 1} ⩽ x < d_{2 i + 2} - 1 - 2 p b d_{2 i}$ , we have $\begin{array}{r} E_{b}^{β} (m) = E_{b}^{β^{'}} (x) = E_{b}^{γ} (x) = E_{b}^{α} (m), \end{array}$ where $m = x - σ_{i + 1}$ . It follows that $\begin{matrix} (6.10) & \tilde{d_{2 i}} ⩽ m < \tilde{d_{2 i + 2}} - 1 - 2 p b d_{2 i} ⟹ E_{b}^{β} (m) = E_{b}^{α} (m) . \end{matrix}$ Consider the rational number $q_{2 i + 2} + q_{i + 1}^{″}$ . We know that its base-b expansion is identical to β in positions $[\tilde{d_{2 i}}, \tilde{d_{2 i + 2}})$ . On one hand, by (6.10) it is also identical to α in $[\tilde{d_{2 i}}, \tilde{d_{2 i + 2}} - 1 - 2 p b d_{2 i})$ . On the other hand, $q_{2 i + 2} + q_{i}^{″}$ also coincides with α in the same positions. Since the difference between the two numbers $q_{2 i + 2} + q_{i + 1}^{″}$ and $q_{2 i + 2} + q_{i}^{″}$ is $χ (i + 1) b^{- \tilde{d_{2 i + 2}} + 1}$ , it follows that they also coincide in all positions less than $\tilde{d_{2 i}}$ and we conclude that $\begin{array}{r} E_{b}^{β} (n) = {digit}_{n} (q_{2 i + 2} + q_{i}^{″}, b) = {digit}_{n} (q_{2 i + 2} + q_{i + 1}^{″}, b) . \end{array}$

We are now ready to prove (6.8). On one hand, $q_{2 i}$ and α coincide in base b in all positions less than $d_{2 i}$ . On the other hand, (5.1) easily implies that $| q_{2 i + 2} - q_{2 i} | ⩾ p^{- 2 b d_{2 i + 2}} > b^{- 2 p b d_{2 i + 2}}$ and thus the base-b expansions of $q_{2 i}$ and $q_{2 i + 2}$ differ in at least one position $⩽ 2 p b d_{2 i + 2}$ .

First, let $q_{2 i} < α$ . This clearly implies $q_{2 i} < q_{2 i + 2}$ and $χ (i + 1) = 1$ . Therefore, $\begin{array}{r} q_{2 i} + q_{i}^{″} < q_{2 i + 2} + q_{i}^{″} < q_{2 i + 2} + q_{i + 1}^{″} = q_{2 i + 2} + q_{i}^{″} + b^{- \tilde{d_{2 i + 2}} + 1} . \end{array}$ By (6.9), β coincides with $q_{2 i + 2} + q_{i + 1}^{″}$ in all positions $< \tilde{d_{2 i + 2}}$ . Moreover, the rational numbers $q_{2 i} + q_{i}^{″}$ and $q_{2 i + 2} + q_{i + 1}^{″}$ differ in at least one position $< \tilde{d_{2 i + 2}}$ . Hence, $q_{2 i} + q_{i}^{″} < β$ .

Second, let $α < q_{2 i}$ . Then $q_{2 i + 2} < q_{2 i}$ and $χ (i + 1) = 0$ . So in this case we have $\begin{array}{r} q_{2 i + 2} + q_{i + 1}^{″} = q_{2 i + 2} + q_{i}^{″} < q_{2 i} + q_{i}^{″} \end{array}$ and the first difference is in some position in $[d_{2 i + 2}, 2 p b d_{2 i + 2}]$ . Using (6.9), we obtain that β and $q_{2 i + 2} + q_{i + 1}^{″}$ are the same in all positions less than $\tilde{d_{2 i + 2}}$ . Furthermore, (6.10) gives that β coincides with α and thus also with $q_{2 i + 2} + q_{i + 1}^{″}$ in all positions in $[\tilde{d_{2 i + 2}}, \tilde{d_{2 i + 4}} - 1 - 2 p b d_{2 i + 2})$ . But the latter interval contains $[d_{2 i + 2}, 2 p b d_{2 i + 2}]$ , because $\begin{array}{r} 2 p b d_{2 i + 2} + 2 p b d_{2 i + 2} + 1 + σ_{i + 2} < 3 d_{2 i + 3} < d_{2 i + 4} . \end{array}$ It follows that $β < q_{2 i} + q_{i}^{″}$ . □

We are ready to prove our last theorem. Theorem 6.9.
$β \notin S_{D}$ .
Proof.
It suffices to show that $D^{α} ⩽_{E} D^{β}$ , because we know that $α \notin S_{D}$ . In the algorithm we will use the rational number $q_{i}^{″}$ , defined in Lemma 6.8. Note that $q_{i}^{″}$ is elementary in $d_{2 i}$ .

Start of algorithm. Given a rational number q:

Step 1. Compute m, n, such that $q = m n^{- 1}$ and $n ⩾ d_{0}$ .

Step 2. Find the unique i, such that $d_{2 i} ⩽ n < d_{2 i + 2}$ and compute $q_{2 i}$ and $q_{i}^{″}$ .

Step 3. If $q \neq q_{2 i}$ , go to Step 4. If $q = q_{2 i}$ , then ask $D^{β}$ to check $q + q_{i}^{″} < β$ . If true, give output 0, otherwise give output 1.

Step 4. Compute the least s, such that ${digit}_{s} (q, b) \neq {digit}_{s} (q_{2 i}, b)$ . Check: $s < d_{2 i + 2}$ . In case it is false go to Step 5. In case it is true: Check $q < q_{2 i}$ . If true, give output 0, otherwise give output 1.

Step 5. Compute $d_{2 i + 2}$ , $q_{2 i + 2}$ and $q_{i + 1}^{″}$ . If $q \neq q_{2 i + 2}$ , go to Step 6. If $q = q_{2 i + 2}$ , then ask $D^{β}$ to check $q + q_{i + 1}^{″} < β$ . If true, give output 0, otherwise give output 1.

Step 6. Check: $q < q_{2 i + 2}$ . If true, return 0, otherwise return 1. End of algorithm.

We will only show that the algorithm correctly computes $D^{α} (q)$ .

In Step 3, case $q = q_{2 i}$ and Step 5, case $q = q_{2 i + 2}$ the output is correct thanks to (6.8).

Assume $s < d_{2 i + 2}$ is true in Step 4, so that q and $q_{2 i}$ differ in at least one position less than $d_{2 i + 2}$ . Since $q_{2 i}$ and α coincide in all positions less than $d_{2 i + 2}$ , $q < α$ is equivalent to $q < q_{2 i}$ . The same argument, applied in Step 6, gives that $q < α$ if and only if $q < q_{2 i + 2}$ , provided that the least t, such that ${digit}_{t} (q, b) \neq {digit}_{t} (q_{2 i + 2}, b)$ is less than $d_{2 i + 4}$ , so it remains to prove this is indeed the case.

Note that q has denominator n, $q_{2 i + 2}$ has denominator $p^{2 b d_{2 i + 2}}$ by (5.1) and t is the first position in which their base-b expansions differ, therefore: $\begin{array}{r} \frac{1}{n . p^{2 b d_{2 i + 2}}} ⩽ | q_{2 i + 2} - q | ⩽ \frac{1}{b^{t - 1}}, \end{array}$ which implies $\begin{array}{r} t ⩽ b^{t - 1} ⩽ n . p^{2 b d_{2 i + 2}} < d_{2 i + 2} . p^{2 b d_{2 i + 2}} < f (f (f (d_{2 i + 3}))) < d_{2 i + 4} . \end{array}$ □

7. Conclusion

We have examined the connection between the presence of some patterns of zeros in base expansions of irrational numbers and the complexity of their Dedekind cuts.

In our first result, we have proved that the complexity of the Dedekind cut of an irrational number is the same as the complexity of its base expansion, provided that long sequences of zero digits are followed by relatively small sequences of arbitrary digits.

After that we allowed long sequences of zero digits to alternate with long sequences of arbitrary digits in the base expansion. For any irrational number ξ we consider another irrational number $ξ^{'}$ , which is obtained from ξ by inserting long sequences of zeros in its base expansion. For any subrecursive class $S$ , we have given examples of irrational numbers with elementary base expansions, which show that three of the four cases are possible:

(1) ξ and $ξ^{'}$ have Dedekind cut in $S$ ; (2) α does not have Dedekind cut in $S$ , but $α^{'}$ does; (3) both β and $β^{'}$ do not have Dedekind cut in $S$ .

The only case, which remains unsettled is whether there exists an irrational number δ, such that $δ \in S_{D}$ and $δ^{'} \notin S_{D}$ . The proofs of Theorem 5.3 and Theorem 5.6 where we obtain $ξ^{'} \in S_{D}$ depend on special properties of ξ. Moreover, we know that $ξ \in S_{b E}$ does not imply $ξ^{'} \in S_{D}$ . Therefore, if $ξ \in S_{D}$ indeed implies $ξ^{'} \in S_{D}$ , some new argument, which makes clever use of bases different from b, will likely be required.

The present line of research considers a rather specific problem on two well-known representations of irrational numbers. There are a number of unexplored representations, such as graphs of trace functions or base expansions with restricted digits. It will be interesting to see how they fit in the already complicated picture of representations.

And finally, at least for some of the results, it might be interesting to formulate and study them relative to subrecursive classes below the elementary level, for example, the second Grzegorczyk class $E^{2}$ , the class of lower elementary functions $L^{2}$ or the class $M^{2}$ , considered in [16]. The machinery becomes much weaker on this level, where we (presumably) do not have access to uniform coding of sequences.

Footnotes

Acknowledgements

This paper is supported by the Bulgarian National Science Fund through contract KP-06-Austria-04/06.08.2019 and by the Sofia University Science Fund through continuation of contract 80-10-180/17.05.2023.

References

Georgiev, Continued fractions of primitive recursive real numbers, Mathematical Logic Quarterly 61 (2015), 288–306. doi:10.1002/malq.201400013.

Georgiev, Dedekind cuts and long strings of zeros in base expansions, in: Connecting with Computability, Computability in Europe 2021,

De Mol,

Weiermann,

Manea and

Fernández-Duque, eds, LNCS, Vol. 12813, Springer, 2021, pp. 248–259. doi:10.1007/978-3-030-80049-9_23.

Georgiev,

Kristiansen and

Stephan, On general sum approximations of irrational numbers, in: Sailing Routes in the World of Computation, Computability in Europe 2018,

Manea,

R.G.

Miller and

Nowokta, eds, LNCS, Vol. 10936, Springer, 2018, pp. 194–203. doi:10.1007/978-3-319-94418-0_20.

Georgiev,

Kristiansen and

Stephan, Computable irrational numbers with representations of surprising complexity, Annals of Pure and Applied Logic 172(2) (2021), 102893. doi:10.1016/j.apal.2020.102893.

Ko, On the definitions of some complexity classes of real numbers, Mathematical Systems Theory 16 (1983), 95–109. doi:10.1007/BF01744572.

Ko, On the continued fraction representation of computable real numbers, Theoretical Computer Science 47 (1986), 299–313. doi:10.1016/0304-3975(86)90154-4.

Kristiansen, On subrecursive representability of irrational numbers, Computability 6 (2017), 249–276. doi:10.3233/COM-160063.

Kristiansen, On subrecursive representability of irrational numbers, part II, Computability 8 (2019), 43–65. doi:10.3233/COM-170081.

Kristiansen,

J.-C.

Schlage-Puchta and

Weiermann, Streamlined subrecursive degree theory, Annals of Pure and Applied Logic 163 (2012), 698–716. doi:10.1016/j.apal.2011.11.004.

10.

Labhalla and

Lombardi, Real numbers, continued fractions and complexity classes, Annals of Pure and Applied Logic 50 (1990), 1–28. doi:10.1016/0168-0072(90)90052-4.

11.

A.H.

Lachlan, Recursive real numbers, The Journal of Symbolic Logic 28(1) (1963), 1–16. doi:10.2307/2271331.

12.

R.S.

Lehman, On primitive recursive real numbers, Fundamenta Mathematica 49(2) (1961), 105–118. doi:10.4064/fm-49-2-105-118.

13.

Mostowski, On computable sequences, Fundamenta Mathematica 44 (1957), 37–51. doi:10.4064/fm-44-1-37-51.

14.

H.E.

Rose, Subrecursion, Functions and Hierarchies, Clarendon Press, Oxford, 1984.

15.

Skordev, Computability of real numbers by using a given class of functions in the set of the natural numbers, Mathematical Logic Quarterly 48(Suppl. 1) (2002), 91–106. doi:10.1002/1521-3870(200210)48:1+<91::AID-MALQ91>3.0.CO;2-L.

16.

Skordev,

Weiermann and

Georgiev,

M^{2}

-Computable real numbers, Journal of Logic and Computation 22(4) (2008), 899–925. doi:10.1093/logcom/exq050.

17.

Specker, Nicht konstruktiv beweisbare Sätze der Analysis, Journal of Symbolic Logic 14 (1949), 145–158. doi:10.2307/2267043.

18.

Weihrauch, Computable Analysis, Springer-Verlag, Berlin/Heidelberg, 2000.