On a Lattice of Degrees of Representationsof Irrational Numbers
Lars Kristiansen

Department of Mathematics, University of Oslo
Department of Informatics, University of OsloCiE 2023: Unity of Logic and Computation
Batumi, Georgia – July 28, 2023

What is a representation of the irrational numbers?
I will tell you.
Beware! I will not tell you what a representation of the real numbers is.

We identify an irrational number α with its Dedkind cut. The Dedekind
cut of an irrational α is the function α : Q −→ {0, 1} where(α(q) =0if q < α1

if q > α.

We will use the representation by Dedekind cuts to define whatrepresentation in general is. In principle, we could have use any othercomputable representation for this purpose, but it isconvenient to use a representation that is uniquea good idea to use a well-know representation.

What is a representation?
Definition
A class of functions R is a representation (of the irrational numbers) if
there exist oracle Turing machines M and N such thatfor every irrational α ∈ (0, 1) there exists f ∈ R such thatα = ΦfM and f = ΦαNfor every g ∈ R there exist an irrational α ∈ (0, 1) such thatα = ΦgM = ΦfM where f = ΦαNWhen α = ΦgM , we say that g represents α and that g is anR-representation of α.

Example
A function C : N+ −→ Q is a Cauchy sequence for α if
|α − C (n)| < n−1 .

Let C be the class of all Cauchy sequences for irrational numbers in theinterval (0, 1).
Then C is a representation.

Example
A function E : N+ −→ {0, 1} is the base-2 expansion of α if
α =∞XE (i)2−i .

i=1

Let 2E be the class of all base-2 expansions of irrational numbers in theinterval (0, 1).
Then 2E is a representation.

Example
A function T : Q ∩ [0, 1] −→ (0, 1) is the trace function for α if
|α − T (q)| < |α − q| .

Let T be the class of all trace functions for irrational numbers in theinterval (0, 1).
Then T is a representation.

Example
Recall that the Dedekind cut of an irrational α is the function
α : Q −→ {0, 1} where(α(q) =0if q < α1

if q > α.

Let D be the class of all Dedekind cuts of irrational numbers in theinterval (0, 1).
Then D is a representation.

Example of something that is not a representation(but which come close).
A function L : N −→ (0, 1) is a left cut for α if the sequence
L(0), L(1), L(2), . . .
contains (i) all the rationals less than α and (ii) only rational less that α.
A class of left cuts will not be a representation. We cannot compute theDedekind cut of α from a left cut for α.

Example of something that is not a representation(but which come close).
Cauchy sequences without a modulus of convergence. Let C : N+ −→ Q
be such that∀n ∈ N+ ∃N i > N → |α − C (i)| < n−1

A class of such functions will not be a representation. We cannot
compute the Dedekind cut of α from such a function.

Next we define an ordering relation S over the representations.
Intuitiviely, we want
R1 S R2 to be true if an R2 -representation of α can be
subrecursively converted into an R1 -representation of α(subrecursively = ”without unbounded search”)
R1 6S R2 to be true if unbounded search is required in order toconvert R2 -representation of α into an R1 -representation of α.
More intuition . . .
If R1 S R2 holds, then the representation R2 gives more
information than the representation R1 .

More intuition . . .
Let C be a Cauchy sequence for the irrational number α.

More intuition . . .
Let C be a Cauchy sequence for the irrational number α.
How can we decide if α lies above or below 1/3?
Consider C as an oracle. (We assume that α is irrational, so α lies
strictly above or strictly below 1/3.)

We may ask C . . .
C (0) = ?
C (1) = ?
C (2) = ?
C (3) = ?
..
.

We may ask C . . .
C (0) = 1/3
C (1) = ?
C (2) = ?
C (3) = ?
..
.

We may ask C . . .
C (0) = 1/3
C (1) = 1/3
C (2) = ?
C (3) = ?
..
.

We may ask C . . .
C (0) = 1/3
C (1) = 1/3
C (2) = 1/3
C (3) = 1/3..
.
C (16) = 1/3
C (17) = 1/3

We may ask C . . .
..
.
C (16) = 1/3
C (17) = 1/3
Now, we know that α is close to 1/3, that isα−13<117

but we still don’t know if α lies above or below 1/3.

Now

C (a sufficiently large number) =a rational that allows
me to conclude if αlies above or below 1/3

Now

C (a sufficiently large number) =a rational that allows
me to conclude if αlies above or below 1/3

but we need unbounded search to find that number.

Now

C (a sufficiently large number) =a rational that allows
me to conclude if αlies above or below 1/3

but we need unbounded search to find that number.
I cannot find the number by a subrecursive computation.
I need full Turing computability.

If we have access to the Dedekind cut of α, then we can easily decide if
1/3 lies above or below α.

If we have access to the Dedekind cut of α, then we can easily decide if
1/3 lies above or below α.
If D(1/3) = 0, then 1/3 lies below α
If D(1/3) = 1, then 1/3 lies above α

If we have access to the Dedekind cut of α, then we can easily decide if
1/3 lies above or below α.
If D(1/3) = 0, then 1/3 lies below α
If D(1/3) = 1, then 1/3 lies above α
Just one question is needed. No unbounded search is required.

If we have access to the Dedekind cut of α, then we can easily decide if
1/3 lies above or below α.
If D(1/3) = 0, then 1/3 lies below α
If D(1/3) = 1, then 1/3 lies above α
Just one question is needed. No unbounded search is required.
A subrecursive computation is sufficient to answer the question.

This example shows that we cannot compute the Dedekind cut of α
subrecursively in a Cauchy sequence for α.
We want
D 6S C
where
D is the representation by Dedekind cuts
C is the representation by Cauchy sequences.

This example shows that we cannot compute the Dedekind cut of α
subrecursively in a Cauchy sequence for α.
We want
D 6S C
where
D is the representation by Dedekind cuts
C is the representation by Cauchy sequences.
In contrast, we can compute a Cauchy sequence for α subrecursively in
the Dedekind cut of α.

Let α be an irrational number between 0 and 1.
We can compute a Cauchy sequence C for α subrecursively in theDedekind cut of α: Let C (1) = 2−1 and(C (n + 1) =C (n) − 2−n−1
C (n) + 2−n−1

if D(C (n)) = 0otherwise.

Let α be an irrational number between 0 and 1.
We can compute a Cauchy sequence C for α subrecursively in theDedekind cut of α: Let C (1) = 2−1 and(C (n + 1) =C (n) − 2−n−1
C (n) + 2−n−1

We want thatC S D .

if D(C (n)) = 0otherwise.

Now, . . . the formal definition of S .
We need some auxiliary definitions.

We need the time bounds.
Definition
A function t : N −→ N is a time bound if (i) n ≤ t(n), (ii) t is increasingand (iii) t is time-constructible: there is a single-tape Turing machine
that, on input 1n , computes t(n) in O(t(n)) steps.

We need the notation O(t)R .
Definition
Let t be a time-bound and let R be a representation. Then, O(t)Rdenotes the class of all irrational α in the interval (0, 1) such that at least
one R-representation of α is computable by a Turing machine running intime O(t(n)) (where n is the length of the input).

Example
Let C be the representation by Cauchy sequences. Let α ∈ (0, 1) beirrational.
Then the following two statements are equivalent (by definition).
12

α ∈ O(n2 )C
at least one Cauchy sequence for α can be computed by a Turingmachine running in time O(n2 ) (where n is the length of the input).

ExampleLet 2E be the representation by base-2 expansions. Let α ∈ (0, 1) beirrational.
Then the following two statements are equivalent.
212

α ∈ O(24n )2Ethe base-2 expansion of α can be computed by a Turing machine2
running in time O(24n ) (where n is the length of the input).

Now we are ready for the definition of S .
Definition
Let t be a time-bound. Let R1 and R2 be representations. The relation
R1 S R2 holds if there for any time-bound t exists a time-bound s such
thatO(t)R2 ⊆ O(s)R1 .
If the relation R1 S R2 holds, we will say that the representation R1 issubrecursive in the representation R2 .

Let us see why we have C S 2E.
There is a natural subrecursive algorithm for converting the base-2
expansion of α into a Cauchy sequence for α (no unbounded searchinvolved).

Let us see why we have C S 2E.
There is a natural subrecursive algorithm for converting the base-2
expansion of α into a Cauchy sequence for α (no unbounded search
involved).
Analyse that algorithm and conclude: If a Turing machine can computethe base-2 expansion of α in time O(t(n)), then a Turing machine cancompute a Cauchy sequence for α in time O(25t(n) ).

Let us see why we have C S 2E.
There is a natural subrecursive algorithm for converting the base-2
expansion of α into a Cauchy sequence for α (no unbounded searchinvolved).
Analyse that algorithm and conclude: If a Turing machine can computethe base-2 expansion of α in time O(t(n)), then a Turing machine cancompute a Cauchy sequence for α in time O(25t(n) ).
Thus
O(t(n))2E ⊆ O(25t(n) )C .

Let us see why we have C S 2E.
There is a natural subrecursive algorithm for converting the base-2
expansion of α into a Cauchy sequence for α (no unbounded searchinvolved).
Analyse that algorithm and conclude: If a Turing machine can computethe base-2 expansion of α in time O(t(n)), then a Turing machine cancompute a Cauchy sequence for α in time O(25t(n) ).
Thus
O(t(n))2E ⊆ O(25t(n) )C .
Thus, for any time-bound t there exists a time-bound s such thatO(t(n))2E ⊆ O(s(n))C .
(this holds when s(n) = 25t(n) ).

Let us see why we have C S 2E.
There is a natural subrecursive algorithm for converting the base-2
expansion of α into a Cauchy sequence for α (no unbounded searchinvolved).
Analyse that algorithm and conclude: If a Turing machine can computethe base-2 expansion of α in time O(t(n)), then a Turing machine cancompute a Cauchy sequence for α in time O(25t(n) ).
ThusO(t(n))2E ⊆ O(25t(n) )C .
Thus, for any time-bound t there exists a time-bound s such thatO(t(n))2E ⊆ O(s(n))C .
(this holds when s(n) = 25t(n) ).
Thus, we have C S 2E (by the definition of S ).

This generalises. In general we can prove R1 S R2 by the following
recipe.
Find a subrecursive algorithm for converting an R2 -representation of α
into an R1 -representation of α (no unbounded search).

This generalises. In general we can prove R1 S R2 by the following
recipe.
Find a subrecursive algorithm for converting an R2 -representation of α
into an R1 -representation of α (no unbounded search).
Analyse that algorithm and conclude: If a Turing machine can computean R2 -representation of α in time O(t(n)), then a Turing machine cancompute an R1 -representation α in time O(st (n)) where st is atime-bound depending on t.

This generalises. In general we can prove R1 S R2 by the following
recipe.
Find a subrecursive algorithm for converting an R2 -representation of α
into an R1 -representation of α (no unbounded search).
Analyse that algorithm and conclude: If a Turing machine can computean R2 -representation of α in time O(t(n)), then a Turing machine cancompute an R1 -representation α in time O(st (n)) where st is atime-bound depending on t.
Thus, for any time-bound t there exists a time-bound s such that
O(t(n))R2 ⊆ O(s(n))R1 .
Thus, we have R1 S R2 (by the definition of S ).

To prove R1 6S R2 migh not be all that easy.
Then we have to prove thatthere exists a time-bound t such thatfor any time-bound sO(t(n))R2 6⊆ O(s(n))R1

To prove R1 6S R2 might not be all that easy . . .
. . . which again can be proved by proving
there exists a time-bound t such thatfor any time-bound s
there exists an irrational β ∈ (0, 1) such thatβ ∈ O(t(n))R2 \ O(s(n))R1

That there for any time-bond s exists such a β will typically be proved bya diagonalisation argument. Such arguments may be tedious andinvolved.

The relation S is a preorder. Thus S induce a degree structure on therepresentations (standard stuff will follow).

Let R and Q be representations.
R ≡S Q⇔def

R S Q and Q S R .

R ≺S Q⇔def

R S Q and Q 6S R .

We define the degree of the representation R, denoted deg(R), as theequivalence class given bydeg(R) = { Q | Q ≡S R } .
The set of all degrees, denoted S, is given by
S = { deg(R) | R is a representation } .
We will use a, b, c (possible decorated) to denote degrees. We will use ≤and < to denote the ordering relations induced on the degrees by S and≺S , respectively.

It turns out that this degree structure is a lattice. That is, there areoperators ∪ and ∩ on the degrees such thata ∪ b is the least upper bound of a and ba ∩ b is the greatest lower bound of a and b.
for any a, b ∈ S.

It turns out that the degree structure has a top and bottom degree.
Let 0 denote the degree of the representation by Weirauch intersections(nested intervals).
Let 1 denote the degree of the representation by continued fractions.
Theorem
We have0 ≤ a ≤ 1
for any degree a.

Definition
A function I : N −→ Q × Q is a Weihrauch intersection for the real
number α if the left component of the pair I (i) is strictly less that theright component of the pair I (i) (for all i ∈ N) and{α} =∞
\IiO

i=0

where IiO denotes the open interval given by the the pair I (i).
If we have a Weihrauch intersection for an irrational number α, the wecan compute the Dedekind cut of α (we will need unbounded search). If
we have the Dedekind cut of α, we can obviously compute a Weihrauchintersection for α (we do not need unbounded search).
The class of all Weihrauch intersections for irrationals in the intervall(0, 1) is a representation.

Definition
Let α be an irrational in the interval (0, 1). The continued fraction of α
is the unique function f : N+ −→ N+ such that α = [0; f (1), f (2), . . .]where1[ 0; a1 , a2 , a3 . . . ] = 0 +
1
a1 +
1
a2 +
a3 + . . .

The class of all continued fractions of irrationals in the intervall (0, 1) is arepresentation.

Weihrauch intersections

Cauchy sequences

Base-b expansions

Base-b sum approx.
from below

Base-b 0 expansion

Base-b 0 sum approx.
from above

Dedekind cuts

Best approx.
from below

Best approx.
from above

Continued fractions

Figure 1: Overview.

arXiv:2304.07227 [pdf, ps, other] math.LO cs.CC
On representations of real numbers and the computational complexity ofconverting between such representations.
Authors: Amir M. Ben-Amram, Lars Kristiansen, Jakob Grue Simonsen————————————————————Another paper recently submitted to a journal (but not to arXive):
A Degree Structure on Representations of Irrational Numbers
Authors: Amir M. Ben-Amram, Lars Kristiansen