Computable irrational numbers with representations of surprising complexity (Q2216036)

This paper begins with the following statement: (I) ``Irrational numbers are infinite objects.'' The authors consider representations of irrational numbers such as Cauchy sequences, Dedekind cuts, decimal expansions, binary expansions, continued fractions, and other representations defined in terms of sum approximations and best approximations. Their main question is the following: (Q) does one need unbounded search to convert one such representation \(R1\) of an irrational number into another representation \(R2\) of the same number? Their main idea to study such a question centers on the notion of a set \(\mathcal{S}\) of total computable functions with ``nice'' closure properties (formally defined in \S 3). Let \(\mathcal{S}_{R1}\) be the set of irrational numbers with an \(R1\) representation in \(\mathcal{S}\) and define \(\mathcal{S}_{R2}\) in the same way. The authors rephrase (Q) as follows: (Q') is there an arbitrarily large set \(\mathcal{S}\) of total computable functions with ``nice'' closure properties such that \(\mathcal{S}_{R1} \nsubseteq \mathcal{S}_{R2}\)? To study this question, the authors define a class of fast-growing computable functions \(f\) and define an irrational number \(\alpha_f=\sum_{i=1}^\infty P_i^{-f(i)}\), where \(P_i\) is the \(i\)-th prime. The authors show that some representations of \(\alpha_f\) are of low computational complexity (independent of \(f\)) while others are of arbitrarily high computational complexity (dependent on \(f\)). Moreover, the authors prove that, for every representation \(R\) considered in this paper (with the exception of Cauchy sequences), there are numbers \(\alpha\) and \(\beta\) whose \(R\)-representations are of low computational complexity while the \(R\)-representations of \(\alpha+\beta\) are of arbitrarily high computational complexity. Before concluding, I want to return to statement (I). The authors seem to believe that this is the case because they have in mind representations of irrational numbers such as decimal expansions and the others mentioned above. In all such cases, there seem to be two reasons to believe that irrational numbers are \textit{infinite objects}: \begin{itemize} \item[(R1)] every string of symbols representing an irrational number has infinitely many symbols and \item[(R2)] (therefore) for every arithmetic operation \(\sigma\) (like addition and multiplication) and the order (\(<\)) and equality (\(=\)) relations on irrational numbers, there is no algorithm (i.e. Turing program) that, for every irrational number \(\alpha\) and \(\beta\), computes \(\sigma(\alpha, \beta)\) (as opposed to an approximation to such result) or decides whether \(\alpha<\beta\) or \(\alpha=\beta\) holds. \end{itemize} The truth-value of (I) does not affect any result in this paper. However, it is interesting to observe that there are \textit{prima facie} good reasons not to believe (I) (which does not imply that there are good reasons to disbelieve that statement). Let us represent irrational numbers using segments in Euclidean geometry. If one allows constructions employing a collapsible compass and an unmarked ruler (as in Euclid's first book of the \textit{Elements}), then, for every arithmetic operation and the order and equality relations, there is an algorithm that, given two numbers, computes that operation or decides whether the relation holds. Descartes defines some such algorithms in the first book of \textit{La géométrie}. \textit{M. Beeson} provides similar algorithms for a rigid compass in the context of intuitionistic mathematics [Bull. Symb. Log. 22, No. 1, 1--104 (2016; Zbl 1403.03130)]. Therefore, for irrational numbers represented in such a geometric way, (R2) does not hold. One may argue that (R1) holds because a segment either (i) contains or (ii) is composed of infinitely many points. Neither option (containment and composition) holds if one takes the continuum to be prior to the points that one may isolate in it as, in different ways, the authors such as Aristotle (\textit{Physics iv. 1--5}), \textit{G. Veronese} [Fondamenti di geometria a più dimensioni e a più spezie di unita rettilinee esposti in forma elementare. Padova. Tipografia del seminario (1891; JFM 24.0483.01), Chapter IV, \S 1] and \textit{L. E. J. Brouwer} [Over de Grondslagen der Wiskunde. Amsterdam-Leipzig: Mass \& van Suchtelen (1907; JFM 38.0081.04), p. 3--4] did. (R1) may also not hold if one takes a segment to be composed by infinitely many points and one understands composition as mereological sum. The reason is that it is unclear whether the mereological sum of infinitely many parts is an infinite object. For these reasons, the reviewer is not convinced that the authors' opening statement (I) is true. More importantly, some considerations developed in this note (geometric representations of irrational numbers) may suggest further research in the spirit of the authors' paper (what are the computability-theoretic and complexity-theoretic properties of such representations? How do they compare with the representations that the authors did consider?).