Interplay between insertion of zeros and the complexity of Dedekind cuts

Article type: Research Article

Authors: Georgiev, Ivan^{; *}

Affiliations: Faculty of Mathematics and Informatics, Sofia University, 5 James Bourchier blvd., 1164 Sofia, Bulgaria

Correspondence: [*] Corresponding author. ivandg@fmi.uni-sofia.bg.

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

DOI: 10.3233/COM-230469

Journal: Computability, vol. 13, no. 2, pp. 135-159, 2024