Primitive recursive ordered fields and some applications

Abstract

We establish primitive recursive (PR) versions of some known facts about computable ordered fields of reals and computable reals, and apply them to prove primitive recursiveness of several important problems in linear algebra and analysis.

One of the central results of this paper is a partial PR analogue of Ershov–Madison’s theorem about real closures of computable ordered fields. It allows us, in particular, to obtain PR root-finding algorithms in the PR real and algebraic closures of PR fields with a certain property (PR splitting). We also relate the corresponding fields to the PR reals, as well as introduce and study the notion of a PR metric space. It enables us to derive sufficient conditions for PR computing of normal forms of matrices and solution operators of symmetric hyperbolic systems of PDEs. The methods represent a mix of symbolic and approximate algorithms.

Keywords

Ordered field real closure primitive recursion polynomial splitting root-finding spectral decomposition symmetric hyperbolic system of PDE

1. Introduction

In [34,35], computable ordered fields of reals were related to the field of computable reals and were used to prove computability of some problems in algebra and analysis (notably, spectral problems for symmetric matrices and computing solutions of symmetric hyperbolic systems of partial differential equations (PDEs) uniformly in matrix coefficients) in the rigorous sense of computable analysis [40]. The proposed sufficient conditions for computability are very broad but do not yield any complexity upper bounds because they use algorithms based on unbounded search through countable sets. We note that the situation here is rather subtle, e.g. the spectral decomposition of a real symmetric $2 \times 2$ -matrix is not computable [41] (as a multi-valued function on the reals) but it becomes computable (even for $n \times n$ -matrices uniformly in n) if matrix coefficients range over any fixed computable real closed field of reals.

In [36], the PTIME-presentability of the ordered field $R_{alg}$ of algebraic reals and PTIME-computability of some problems on algebraic numbers established in [1] were applied to find non-trivial upper complexity bounds for the aforementioned problems in algebra and analysis. A weak point here is that this approach applies only to problems with coefficients in $R_{alg}$ because $R_{alg}$ is currently the only known PTIME-presentable real closed ordered field.

Another weak point is that complexity classes like PTIME or PSPACE are often not closed under important constructions. E.g. the spectral decomposition of an algebraic symmetric $n \times n$ -matrix is PTIME-computable for any fixed n, but not uniformly in n. The same holds for the problem of root-finding for polynomials in $R_{alg} [x]$ [1]. For differential equations, PTIME is in many cases preserved for analytic/polynomial initial data: [6,19] for ordinary differential equations (ODEs), [23] for PDEs. However, for more general functional classes the situation is different: solving ODEs with a Lipshitz continuous PTIME computable right-hand part is PSPACE-complete [18]. Computing the solutions of the Dirichlet problem for the Poisson equation [20] and periodic boundary value problem for the heat equation [22], is #P₁-complete; according to [22,23], for a large class of linear evolutionary PDEs, the difference scheme method is in general in PSPACE, for some particular cases in #P, when applied to fixed real PTIME computable initial data.

Thus, it seems reasonable to investigate properties of the aforementioned problems for natural complexity classes in between PTIME and COMPUTABLE, to obtain better closure properties and efficient solutions of wider classes of problems. An obvious candidate here is the class PR of primitively recursive functions having a prominent role in computability theory and proof theory.

Recently, there was a renewed interest in primitively recursive (PR) structures (see e.g. [4] and references therein) which are recognized as a principal model for an emerging new paradigm of computability – the so called online computability (see e.g. [5]). PR-solvability of a problem yields a solution algorithm which does not use an exhaustive search through a structure (usually written as unbounded WHILE...DO, REPEAT...UNTIL, or μ operator); thus, it becomes possible to count working time of the algorithm. Although the upper complexity bounds for a PR-algorithm may be awfully large, this is a principal improvement compared with the general computability. As stressed in [4], PR-presentability of a structure may often be improved even compared with PTIME-presentability.

Thus, PR-presentability of structures (and PR-computability in general) seems important for the following reasons: it is in some respect close to feasible computability, is technically easier than, say PTIME-computability, and has much better closure properties. In this paper we investigate PR-versions of some results in [34,36]. The PR versions have their own flavour and complement the results in [34,36].

In particular, we find a PR-version (for Archimedean case) of the Ershov–Madison theorem on the computable real closure [9,25], relate PR ordered fields of reals to the field of PR reals, propose (apparently, new) notions of PR-computability in analysis and apply them to obtain new results on computability of PDE-solutions. Our notion of PR Archimedean field of reals uses the idea of PR Skolem functions which was earlier used by R.L. Goodstein in [14] in his development of a version of constructive analysis.1

¹
We are grateful to Vasco Brattka for the hint to Goodstein’s monography.

Our approach to PR computability in analysis sketched below is also related to the approach by W. Gomaa (see [13], comments after Remark 1) to PR computability on the reals.2

We are grateful to an anonymous reviewer of [32] for the hint to the survey by W. Gomaa.

More specifically, we identify a class of PRAS-fields (PR Archimedean fields of reals with PR-splitting) such that the above-mentioned problems over any such field are PR-computable. These results complement and contrast the results in [34,36], as well as some results in [1]. E.g., the class of PRAS-fields is shown to be richer than the class of PTIME-presentable fields but the union of this class is a proper subset of the set of PR reals (in contrast with the corresponding fact in [34]). In the applications sections, we show how this applies to spectral problems and (PR) solving of symmetric hyperbolic systems of PDEs. For the latter example the solution is computed numerically (via difference schemes) while the algebraic part is performed symbolically; this part also requires introducing definitions of PR real functions and operators.

In programming terms, we identify an important class of number fields and related algorithmic problems of algebra and analysis which may be programmed without using the above-mentioned unbounded cycle operators.

The present paper is an extended version of the conference paper [32] which contains new results, detailed proofs of some results which were only sketched in the conference version, and precise formulations of auxiliary facts. After some preliminaries on computable and PR-structures in the next section and on PR rings and fields in Section 3, we define in Section 4 PR-Archimedean fields and prove the PR-version of Ershov–Madison’s theorem for such fields. In Section 5 we introduce PR-splitting property and give a sufficient condition for uniqueness of the PR real closure and for the existence of PR root-finding algorithms in the PR real and algebraic closures of PR-fields with this property. In Section 6 we examine PR-versions of results in [34,35] on the relations of computable ordered fields of reals to the field of computable reals. In Section 7 we show that many transcendental reals may be included in a PRAS-field, in contrast with the PTIME-presentable ordered fields of reals for which no such example is known. In Section 8 we apply the obtained results to show the existence of PR algorithms for finding normal forms of matrices over any PRAS-field frequently used in applications. In Section 9 we introduce basic notions of a PR version of computable analysis which seems closely related to Goodstein’s version of constructive analysis. In Section 10 we apply the obtained results to proving PR-computability of solutions operators for symmetric hyperbolic systems of PDE, complementing the results in [34,36]. We conclude in Section 11 with a short informal discussion and some open problems.

2. PR structures

Here we recall some basic definitions and observations about PR functions and structures. We start with recalling basic notions related to computable structures (see e.g. [10,27,37] for additional details).

A numbering is any function with domain $N$ . Instead of $ν (n)$ we may write $ν_{n}$ whenever convenient. A numbering of a set B is a surjection β from $N$ onto B; sometimes we write $β_{n}$ or $β n$ instead of the “canonical” $β (n)$ . For numberings β and γ, β is reducible to γ (in symbols $β ⩽ γ$ ) iff $β = γ \circ f$ for some computable function f on $N$ , and β is equivalent to γ (in symbols $β \equiv γ$ ) iff $β ⩽ γ$ and $γ ⩽ β$ . These notions (due to A.N. Kolmogorov) enable to transfer the computability theory over $N$ to computability theory over many other countable structures.

Definition 1.
Let $ν : N \to B$ be a numbering. A relation $P \subseteq B^{n}$ on B is ν-computable if the relation $P (ν (k_{1}), \dots, ν (k_{n}))$ on $N$ is computable. A function $f : B^{n} \to B$ is ν-computable if $f (ν (k_{1}), \dots, ν (k_{n})) = ν g (k_{1}, \dots, k_{n})$ for some computable function $g : N^{n} \to N$ ; this notion is naturally extended to partial functions $f : \subseteq B^{n} \to B$ . More generally, given another numbering $μ : N \to C$ , a function $f : B^{n} \to C$ is $(ν, μ)$ -computable if $f (ν (k_{1}), \dots, ν (k_{n})) = μ g (k_{1}, \dots, k_{n})$ for some computable function $g : N^{n} \to N$ .
Definition 2.
A structure $B = (B; σ)$ of a finite signature σ is called constructivizable iff there is a numbering β of B such that all signature predicates and functions, and also the equality predicate, are β-computable. Such a numbering β is called a constructivization of $B$ , and the pair $(B, β)$ is called a constructive structure.

Note that all information about a constructive structure $(B, β)$ is contained in the numbering β (and computable functions representing the equality and signature functions and relations in this numbering) because $B = rng (β)$ . We sometimes use this to shorten notation in Sections 5 and 6.

The notion of a constructivizable structure is equivalent to the notion of a computably presentable structure popular in the Western literature. Obviously, $(B, β)$ is a constructive structure iff, given $n_{1}, \dots, n_{k} \in N$ and a quantifier-free σ-formula $ϕ (v_{1}, \dots, v_{k})$ with free variables among $v_{1}, \dots, v_{k}$ , one can compute the value $ϕ^{B} (β (n_{1}), \dots, β (n_{k}))$ of ϕ in $B$ .
Definition 3.
A structure $B = (B; σ)$ of a finite signature σ is called strongly constructivizable iff there is a constructivization β of B such that, given $n_{1}, \dots, n_{k} \in N$ and a first-order σ-formula $ϕ (v_{1}, \dots, v_{k})$ , one can compute the value $ϕ^{B} (β (n_{1}), \dots, β (n_{k}))$ . Such β is called a strong constructivization of $B$ , and the pair $(B, β)$ is called a strongly constructive structure.

Clearly, any strongly constructivizible structure is constructivizible and has a decidable first-order theory. The notion of a strongly constructive structure is equivalent to the notion of a decidable structure popular in the Western literature.

PR-versions of the notions defined above are obtained by changing “computable” to “PR” in the definitions above. In particular, for numberings β and γ, β is PR-reducible to γ (in symbols $β ⩽_{PR} γ$ ) iff $β = γ \circ f$ for some PR function f on $N$ , and β is PR-equivalent to γ (in symbols $β \equiv_{PR} γ$ ) iff $β ⩽_{PR} γ$ and $γ ⩽_{PR} β$ . For $ν : N \to B$ , a relation $P \subseteq B^{n}$ on B is ν-PR if the relation $P (ν (k_{1}), \dots, ν (k_{n}))$ on $N$ is PR. A function $f : B^{n} \to B$ is ν-PR if $f (ν (k_{1}), \dots, ν (k_{n})) = ν g (k_{1}, \dots, k_{n})$ for some PR function $g : N^{n} \to N$ . A structure $B = (B; σ)$ is PR-constructivizable iff there is a numbering β of B such that all signature predicates and functions, and also the equality predicate, are β-PR. Such β is called a PR-constructivization of $B$ , and the pair $(B, β)$ is called a PR structure.

Basic information on PR functions is supposed to be known; it may be found e.g. in [28]. The PR functions are generated from the distinguished functions $o = λ n .0$ , $s = λ n . n + 1$ , and $I_{i}^{n} = λ x_{1}, \dots, x_{n} . x_{i}$ by repeated applications of the operators of superposition S and primitive recursion R. Thus, any PR function is represented by a “correct” term in the partial algebra of functions over $N$ (“correct” terms are those satisfying some obvious constraints on the arities of the involved functions which guarantee that the resulted function on $N$ is total). Intuitively, any total function defined by an explicit definition using (not too complicated) recursion is PR; the unbounded μ-operator is of course forbidden but the bounded one is possible.

The PR-version of Definition 2 was introduced in [27]. After a long break, PR-structures appeared as an intermediate stage of proving PTIME-presentability of a structure (see e.g. [7,15]). After another break, PR-structures appeared in the literature as a promising candidate for capturing the so called online structures which give a practically relevant alternative to computable structures (see the discussion and additional references in [4]). The following notion from [4] is important for this approach: a structure $B$ is fully PR-presentable (FPR-presentable) if it is isomorphic to a PR structure with universe $N$ . Let us characterise the $FPR$ -structures in our (i.e., Mal’cev’s) terminology. We call a numbering ν PR-infinite if there is a PR function f such that $ν (f (i)) \neq ν (f (j))$ whenever $i \neq j$ .
Proposition 1.
An infinite structure $B$ is FPR-presentable iff it has a PR-constructivization β which is PR-infinite.
Proof.
We consider the less obvious direction. Let β be a PR-constructivization which is PR-infinite via f. Define a function $g : N \to N$ as follows: $g (0) = 0$ and $g (n + 1) = μ x (\forall i ⩽ n (β (x) \neq β (g (i))))$ . Since B is infinite, g is total and injective. Let $h (n) = max {f (0), \dots, f (n)}$ . Then $g (n + 1) = μ x ⩽ h (n) (\forall i ⩽ n (β (x) \neq β (g (i)))$ and h is PR, hence g is also PR. The numbering $γ = β \circ g$ is PR-reducible to β and injective. Conversely, $β ⩽_{PR} γ$ via the PR function $u (n) = μ x ⩽ n (β (n) = β (x))$ . Thus, γ is a bijective numbering of B PR-equivalent to β, so it is a bijective PR-constructivization of $B$ . Copying interpretations of signature symbols from $B$ to $N$ via $γ^{- 1}$ we obtain a PR-copy of $B$ with universe $N$ . □

Note that any PR-constructivization β of an associative commutative ring with 1 of characteristic 0 is PR infinite (via any PR function f such that $β (f (i))$ coincide with the element $1 + \dots + 1 \in B$ ( $i + 1$ summands)). Since in the subsequent sections we consider mostly rings and fields of characteristic 0, most of the PR-constructivizable structures are also FPR-presentable. As observed in [17], in fact any PR-constructivizable infinite field is FPR-presentable.

Importantly, all usual encodings and decodings of constructive objects (like pairs, triples, finite strings, terms, formulas and so on) used in computability theory and its applications may be done using PR functions [28]. For instance, there is a PR bijection $⟨ n_{1}, n_{2} ⟩$ between $N \times N$ and $N$ , with PR decoding functions. With some abuse, we use similar notation $⟨ n_{1}, n_{2}, n_{3} ⟩$ to encode triples and finite strings of natural numbers.

We give some examples of PR structures. The structure $(N; ⩽, +, \cdot)$ is clearly PR. The ordered ring $Z$ of integers is PR-constructivizable via the bijective numbering $ζ (2 n) = n$ and $ζ (2 n + 1) = - n - 1$ . The ordered field $Q$ of rationals is PR-constructivizable via the numbering $ϰ (⟨ n_{1}, n_{2}, n_{3} ⟩) = (n_{1} - n_{2}) {(n_{3} + 1)}^{- 1}$ . This numbering may be in the obvious way improved to a bijective PR-constructivization such that from a given n one can primitive recursively compute a fraction $a / b = ϰ ()$ , $a \in Z$ , $b \in N$ , and vice versa; below we always assume that ϰ is a bijection with these properties..

Let ${t_{n}}$ be the Gödel numbering of all variable-free terms of signature $σ \cup {c_{0}, c_{1}, \dots}$ where $c_{0}, c_{1}, \dots$ is an infinite sequence of new constant symbols. Let $B$ be a σ-structure. We associate with any numbering $ν : N \to B$ the numbering $\tilde{ν} : N \to B$ as follows: $\tilde{ν} (n)$ is the value of $t_{n}$ in $B$ when the constant $c_{i}$ is interpreted as $ν (i)$ . The following fact is a straightforward PR-analogue of a particular case of a theorem in [33].
Proposition 2.

For all $μ, ν : N \to B$ we have: $ν ⩽_{PR} \tilde{ν}$ , $μ ⩽_{PR} ν$ implies $\tilde{μ} ⩽_{PR} \tilde{ν}$ , and $\tilde{\tilde{ν}} ⩽_{PR} \tilde{ν}$ ; any σ-function is $\tilde{ν}$ -PR; if $ν ⩽_{PR} μ$ and any σ-function is μ-PR then $\tilde{ν} ⩽_{PR} μ$ .

If $(B, β)$ is a PR σ-structure and $ν ⩽_{PR} β$ then $\tilde{ν} ⩽_{PR} β$ and $(rng (\tilde{ν}), \tilde{ν})$ is a PR σ-substructure of $(B, β)$ generated by $rng (ν)$ ; in particular, $\tilde{β} \equiv_{PR} β$ .

We conclude this section with recalling a nice characterization of unary PR functions due to R. Robinson (see e.g. Section 3.5 in [28]). Consider the structure $(N; +, \circ, J, s, q)$ where $N = N^{N}$ is the set of unary functions on $N$ , + and ∘ are binary operations on $N$ defined by $(p + q) (n) = p (n) + q (n)$ and $(p \circ q) (n) = p (q (n))$ , J is a unary operation on $N$ defined by $J (p) (n) = p^{n} (0)$ where $p^{0} = {id}_{N}$ and $p^{n + 1} = p \circ p^{n}$ , s and q are distinguished elements defined by $s (n) = n + 1$ and $q (n) = n - {⌊ \sqrt{n} ⌋}^{2}$ where $⌊ x ⌋$ is the integer part of $x \in R$ , i.e., the unique integer m with $m ⩽ x < m + 1$ . This structure is known as the Robinson algebra.

Let $T_{0}$ be the set of variable-free terms t of signature $τ = {+, \circ, J, s, q}$ . The value t of t in the Robinson algebra is an element of $N$ . By Robinson’s theorem, the set ${t ∣ t \in T_{0}}$ of values t of such terms coincides with the set of unary PR functions. Using a standard Gödel’s encoding $N : T_{0} \to N$ by natural numbers (e.g., we can set $N (s) = 1$ , $N (q) = 3$ , $N (t + u) = 2 \cdot 3^{N (t)} \cdot 5^{N (u)}$ , $N (t \circ u) = 4 \cdot 3^{N (t)} \cdot 5^{N (u)}$ , and $N (J (t)) = 8 \cdot 3^{N (t)}$ ), one can construct a computable numbering ψ of the unary PR functions such that the operations +, ∘, J are ψ-PR (see e.g. Section 5.2 of [28] for the details). Recall that computability of ψ means that the binary function $ψ (n) (x)$ is computable; this binary function is not PR. Moreover there is a sequence ${t_{k}}$ in $T_{0}$ such that $t_{k} = ψ (k)$ and the function $k \mapsto N (t_{k})$ is PR.

More generally, for any $n ⩾ 0$ , let $T_{n}$ be the set of terms $t = t (v_{1}, \dots, v_{n})$ of signature τ with variables among a fixed list $v_{1}, \dots, v_{n}$ of pairwise distinct variables. Any $t \in T_{n}$ determines the n-ary operator t on $N$ by setting $t (g_{1}, \dots, g_{n})$ to be the value of t for $v_{i} = g_{i}$ . The functions of the form $t (g_{1}, \dots, g_{n})$ coincide with the functions PR in $g_{1}, \dots, g_{n}$ (the last notion is obtained from the “correct” terms mentioned in the Introduction by adding $g_{1}, \dots, g_{n}$ to the list of basic functions). As above, this yield a Gödel numbering $ψ^{n}$ of n-ary PR operators on $N$ . For $n = 0$ this numbering coincides with the numbering ψ of PR functions in the preceding paragraph. For $n = 1$ we obtain a numbering of unary PR-operators on $N$ which is PR-reducible to the standard numbering of Turing functionals. We use the introduced PR-operators on $N$ in Section 9 to define PR functions on the reals.
3. PR rings and fields

The literature on computable rings and fields is very rich but, surprisingly, the PR analogue of this theory does not seem to be considered extensively so far. In this section we collect a few notions and facts on PR rings and fields which are used in the sequel and which are analogues of their computable versions. We assume the reader to be familiar with basic notions and facts about rings and fields (see e.g. [39]). The word “ring” in this paper usually means “associative commutative ring with 1”, the only exception are rings of matrices which are in general not commutative. The investigation of PR rings and fields in parallel to the well known corresponding computable versions [10,37] is mostly straightforward but from time to time some complications do appear. We consider fields and ordered fields in signatures ${+, \cdot, -,^{- 1}, 0, 1}$ and ${+, \cdot, -,^{- 1} ⩽, 0, 1}$ resp.; for (ordered) rings the symbol $^{- 1}$ is of course removed.

Recall that an integral domain is a ring with no zero-divisors satisfying $1 \neq 0$ . With any integral domain $B$ we associate its quotient field $\tilde{B}$ . The elements of $\tilde{B}$ are the equivalence classes $[a, b]$ of pairs $(a, b)$ where $a, b \in B$ , $b \neq 0$ and the equivalence on pairs is defined by: $(a, b) \sim (a^{'}, b^{'})$ iff $a b^{'} = b a^{'}$ . With any numbering β of B we associate the numbering $\tilde{β}$ of $\tilde{B}$ as follows: $\tilde{β} (⟨ n_{1}, n_{2} ⟩) = [β (n_{1}), β (n_{2})]$ if $β (n_{2}) \neq 0$ , and $\tilde{β} (⟨ n_{1}, n_{2} ⟩) = 0$ otherwise. The next proposition is straightforward.

Proposition 3.

If β is a PR-constructivization of an integral domain $B$ then $\tilde{β}$ is a PR-constructivization of the quotient field $\tilde{B}$ .

If β is a PR-constructivization of an ordered ring $B$ (which is automatically an integral domain) then $\tilde{β}$ is a PR-constructivization of the quotient ordered field $\tilde{B}$ (with the unique ordering extending the given ordering of $B$ ).

With any numbering β of a (countable) ring $B$ we associate the numbering $β^{}$ (the precise notation should refer to the variable x, say we could use $β^{[x]}$ ) of the ring $B [x]$ of polynomials over $B$ with variable x as follows: $β^{} (⟨ i_{0}, \dots, i_{n} ⟩) = β (i_{0}) x^{0} + \dots + β (i_{n}) x^{n}$ where $⟨ i_{0}, \dots, i_{n} ⟩$ is a PR coding of the set $N^{+} = ⋃_{n} N^{n + 1}$ of finite non-empty strings of natural numbers. Iterating this construction, we obtain for each n the numbering $β^{[n]}$ of $B [x_{0}, \dots, x_{n}]$ (identifying $B [x_{0}, \dots, x_{n + 1}]$ with $B [x_{0}, \dots, x_{n}] [x_{n + 1}]$ ) as follows: $β^{[0]} = β^{}$ , $β^{[n + 1]} = {(β^{[n]})}^{}$ . Then the expression $β^{[ω]} (⟨ n, m ⟩) = β^{[n]} (m)$ defines a numbering of the set $B [x_{0}, x_{1}, \dots]$ of polynomials with any number of variables. The next proposition is straightforward.
Proposition 4.

Let $(A, α)$ and $(B, β)$ be PR rings, $A$ a subring of $B$ , and $α ⩽_{PR} β$ . Then $α^{[n]} ⩽_{PR} β^{[n]}$ for all n.

If β is a PR-constructivization of $B$ then $β^{[0]}, β^{[1]}, \dots, β^{[ω]}$ are PR-constructivizations of $B [x_{0}]$ , $B [x_{0}, x_{1}]$ , … , $B [x_{0}, x_{1}, \dots]$ respectively.

For any n, let $e v_{n} : B [x_{0}, \dots, x_{n}] \times B^{n} \to B$ be the evaluation function defined as follows: $e v_{n} (p, b_{0}, \dots, b_{n})$ is the value $p (b_{0}, \dots, b_{n})$ of p at $(b_{0}, \dots, b_{n}) \in B^{n}$ . Let $e v_{ω} : B [x_{0}, x_{1}, \dots] \times B^{+} \to B$ be the evaluation function which returns the value of a polynomial if the arities match and returns 0 otherwise. The next proposition is straightforward.
Proposition 5.
If $(B, β)$ is a PR ring then the evaluation functions are PR in the corresponding PR-constructivizations of the polynomial rings above.

Polynomials are closely related to terms in the signature of rings. We formulate a straightforward fact about such a relation to terms in signature $σ = {+, \cdot, c_{0}, c_{1}, \dots}$ . The direction from polynomials to terms is checked by induction on the number of monomials, the opposite direction – by induction on (the rank of) terms. Interestingly, the PTIME-version of this fact fails in both directions.
Proposition 6.
Let $(B, β)$ be a PR ring. Given $p \in B [x_{0}, \dots, x_{n}]$ , one can primitive recursively find a σ-term $t (x_{0}, \dots, x_{n})$ such that $p (b_{0}, \dots, b_{n}) = t^{B} (b_{0}, \dots, b_{n})$ for all $b_{0}, \dots, b_{n} \in B$ , where $c_{n}$ is interpreted as $β (n)$ . The same holds for the opposite direction $t \mapsto p$ .

Below we consider rings of polynomials only over integer domains and over fields. As is well known, the ring $B [x]$ has interesting arithmetic resembling in many respects the integer arithmetic. We mention (not systematically) some terminology and algorithms which have natural PR analogues. If $p = a_{n} x^{n} + \dots + a_{1} x + a_{0} \in B [x]$ , where $a_{n} \neq 0$ , then n is called the degree of p, denoted as $deg (p)$ . The element $a_{n}$ is the leading coefficient of p. If $a_{n} = 1$ or ( $n = 0$ and $a_{n} = 0$ ), then the polynomial is called normalized. We say that $p_{2}$ divides $p_{1}$ in $B [x]$ , $p_{2} (x) ∣ p_{1} (x)$ , if there is $q \in B [x]$ with $q p_{2} = p_{1}$ . A polynomial $q \in B$ is a greatest common divisor of $p_{1}$ , $p_{2}$ , if $q ∣ p_{i}$ for $i = 1, 2$ and the conditions $r ∣ p_{i}$ for $i = 1, 2$ imply $r ∣ q$ . A greatest common divisor always exists and is unique up to multiplication by a non-zero constant in $B$ . We denote by $gcd (p_{1}, p_{2})$ the normalized greatest common divisor.

A polynomial $p \in B [x]$ over a field is irreducible in $B [x]$ if $deg (p) ⩾ 1$ and the equality $p = p_{1} p_{2}$ implies that $deg (p_{1}) = 0$ or $deg (p_{2}) = 0$ . If p is an irreducible polynomial and $p ∣ p_{1} p_{2}$ , then $p ∣ p_{1}$ or $p ∣ p_{2}$ . Every non-zero polynomial $p \in B [x]$ is representable in the form $p = a p_{1} p_{2} \dots p_{k}$ , where $a \in B$ and $p_{i}$ are normalized irreducible polynomials, and such a representation is unique up to factor permutation; it is called the canonical decomposition of p.

The algorithm of polynomial division of $p_{1}$ by $p_{2}$ (where $p_{1}, p_{2} \in B [x]$ with $\deg_{R} (p_{1}) ⩾ \deg_{R} (p_{2}) > 0$ are given polynomials over a field) returns the quotient $q = quot (p_{1}, p_{2})$ and the remainder $r = rest (p_{1}, p_{2})$ polynomials such that $p_{1} = q p_{2} + r$ and $deg (r) < deg (p_{2})$ . The Euclidean algorithm, applied to such polynomials $p_{1}$ , $p_{2}$ , produces an iterated sequence of quotients and remainders and returns the greatest common divisor $gcd (p_{1}, p_{2})$ of $p_{1}$ , $p_{2}$ as the last non-zero remainder.

The derivative $p^{'}$ of a polynomial $p = a_{n} x^{n} + a_{n - 1} x^{n - 1} + \dots + a_{2} x^{2} + a_{1} x + a_{0}$ is defined as $n a_{n} x^{n - 1} + (n - 1) a_{n - 1} x^{n - 2} + \dots + 2 a_{2} x + a_{1}$ . If $p = a p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}}$ , where $a \in B$ , $p_{i}$ are distinct normalized irreducible polynomials, $e_{i} ⩾ 1$ , and $p_{i} (x) \neq p_{j} (x)$ for $i \neq j$ , then $gcd (p, p^{'}) = p_{1}^{e_{1} - 1} p_{2}^{e_{2} - 1} \dots p_{k}^{e_{k} - 1}$ , hence $p / gcd (p (x), p^{'}) = a p_{1} \dots p_{k}$ . A polynomial p is square-free if in the factorization above $e_{i} = 1$ for $i ⩽ k$ . For polynomials over a field $B$ of characteristic 0 this is equivalent to $gcd (p, p^{'}) = 1$ . In every field that extends $B$ , the roots of p and $p / gcd (p, p^{'})$ coincide and the latter polynomial does not have multiple roots. The next proposition is straightforward.
Proposition 7.
If $(B, β)$ is a PR field then $(B^{}, β^{})$ is a PR integral domain and the functions deg, quot, rest, gcd, ′ and the relations ∣, “ $p_{1}$ , $p_{2}$ are relatively prime”, “p is square-free” are $β^{}$ -PR.*

For any field $B$ , $B [x_{0}, \dots, x_{n}]$ is an integral domain whose quotient field $B (x_{0}, \dots, x_{n})$ is known as the field of rational functions over $B$ ; let $g : B {[x_{0}, \dots, x_{n}]}^{2} \to B (x_{0}, \dots, x_{n})$ be the surjection essentially defined before Proposition 3. For any normalized irreducible $p \in B [x]$ , let $B /_{(p)}$ be the quotient field of $B [x]$ by the maximal ideal $(p) = {q \in B [x] : p ∣ q}$ of $B [x]$ , and let $g_{p} : B [x] \to B /_{(p)}$ be the canonical surjection. The next proposition follows easily from the previous one and Proposition 3.
Proposition 8.
If $(B, β)$ is a PR field then so are also $(B (x_{0}, \dots, x_{n}), g \circ {(β^{[n]})}^{2})$ and $(B /_{(p)}, g_{p} \circ β^{})$ .

In the study of computable fields, the property of computable splitting is important. The PR-version of this notion is as follows: a PR field $(B, β)$ has PR splitting* if, given $p \in B [x]$ , one can primitive recursively find a canonical decomposition of p. Note that this implies that the property of being a reducible polynomial is $β^{}$ -PR. We do not currently know whether the opposite implication holds (although its computable version obviously holds). The following assertion collects straightforward PR-analogues of the corresponding well-known facts about computable splitting [10,37].
Proposition 9.

The PR field* $(Q, ϰ)$ has PR splitting.

If $(B, β)$ is a PR field which has PR splitting then so are the fields $(B (x_{0}, \dots, x_{n}), g \circ β^{[n]})$ and $(B /_{(p)}, g_{p} \circ β^{})$ from the previous proposition.*

Let $A \subseteq B$ be a field extension, $b_{0}, \dots \in B ∖ A$ , and let $A (b_{0}, \dots)$ be the subfield of $B$ generated by $A \cup {b_{0}, \dots}$ . If $b_{0}, \dots$ are algebraically independent (hence transcendental over $A$ ) then $A (b_{0}, \dots)$ is known to be isomorphic to the field $A (x_{0}, \dots)$ of rational functions (the standard isomorphism is induced by the polynomial evaluation function). If $b_{0}$ is algebraic over $A$ then $A (b_{0})$ is known to be isomorphic to the field $A [x] /_{(p_{b_{0}})}$ where $p_{b_{0}} \in A [x]$ is the (unique) normalized polynomial of minimal degree with $p_{b_{0}} (b_{0}) = 0$ .

If $A$ has characteristic 0 and $B$ is an algebraic closure of $A$ then for any $b_{0}, \dots, b_{n} \in B$ there exists $b \in B$ (called a primitive element for $b_{0}, \dots, b_{n}$ ) such that $A (b) = A (b_{0}, \dots, b_{n})$ (this follows from the well-known primitive element theorem, see e.g. Section 46 of [39]). Theorem 11 in [24] provides a constructive version of this theorem. Item 3 of the following proposition is a PR-version of this constructive version with essentially the same proof. Items 1 and 2 are straightforward PR versions of the facts mentioned in the previous paragraph.
Proposition 10.
Let $(A, α)$ and $(B, β)$ be PR fields such that $A \subseteq B$ , $α ⩽_{PR} β$ , $(A, α)$ has PR splitting, and let $b_{0}, \dots \in B ∖ A$ be a finite or infinite sequence, which is PR reducible to β provided it is infinite.
If $b_{0}, \dots$ are algebraically independent over $A$ then the standard isomorphism between $A (b_{0} \dots)$ and $A (x_{0}, \dots)$ , as well as its inverse, are represented by PR functions on the names.

If $b_{0}$ is algebraic over $A$ then the standard isomorphism between $A (b_{0})$ is $A [x] /_{(p_{b_{0}})}$ and its inverse are represented by PR functions on the names.

Let $A$ have characteristic 0 and let $B$ be an algebraic closure of $A$ . Given $p_{0}, \dots, p_{n} \in A [x]$ with $p_{i} (b_{i}) = 0$ for $i ⩽ n$ , one can primitive recursively find a primitive element b for $b_{0}, \dots, b_{n}$ and polynomials $p, q_{0}, \dots, q_{n} \in A [x]$ such that $p (b) = 0$ and $q_{i} (b) = b_{i}$ for $i ⩽ n$ .

Recall that a polynomial in $B [x_{1}, \dots, x_{n}]$ is symmetric if it does not change under any permutation of the variables. The symmetric polynomials $\begin{array}{l} s_{1} = x_{1} + \dots + x_{n}, s_{2} = x_{1} x_{2} + x_{1} x_{3} + \dots + x_{n - 1} x_{n}, \\ s_{3} = x_{1} x_{2} x_{3} + x_{1} x_{2} x_{4} + \dots + x_{n - 2} x_{n - 1} x_{n}, \dots, s_{n} = x_{1} x_{2} \dots x_{n} \end{array}$ are called elementary. It is well known that any symmetric polynomial $p \in B [x_{1}, \dots, x_{n}]$ may be obtained by substituting the expressions for $s_{1}, \dots, s_{n}$ in a suitable polynomial $φ \in B [s_{1}, \dots, s_{n}]$ . The standard proof of this fact is constructive (see e.g. Section 33 in [39]), and in fact the algorithm in that proof is PR. This yields the following.
Proposition 11.
Let $(B, β)$ be a PR ring. Given a symmetric $p \in B [x_{1}, \dots, x_{n}]$ , one can primitive recursively compute a polynomial $φ \in B [s_{1}, \dots, s_{n}]$ such that $p = φ (s_{1}, \dots, s_{n})$ .

Let $M_{n} (B)$ be the ring of $n \times n$ -matrices over a ring $B$ . We use standard terminology and notation from linear algebra. In particular, $det (A)$ is the determinant of $A = (a_{i j}) \in M_{n} (B)$ , $diag (a_{1}, \dots, a_{n})$ is the diagonal matrix with diagonal elements $a_{1}, \dots, a_{n} \in R$ , so in particular $I = I_{n} = diag (1, \dots, 1)$ is the unit matrix. The polynomial ${ch}_{A} = det (λ I - A) \in B [λ]$ is called the characteristic polynomial of A. With any numbering β of $B$ we associate the numbering $μ_{n}$ of $M_{n} (B)$ , by using the PR-bijection between $N^{n \times n}$ and $N$ . Let G be the set of non-degenerate matrices $A \in M_{n} (B)$ , i.e. matrices with non-zero determinants. If $B$ is a field then G coincides with the set of matrices A for which the matrix $A^{- 1}$ exists. Also rectangular matrices are useful, in particular for solving general (i.e., with arbitrary number of variables and equations) linear systems of equations. The next proposition is straightforward.
Proposition 12.
Let $(B; β)$ be a PR ring.
For any $n > 0$ , $μ_{n}$ is a PR-constructivization of the ring $M_{n} (B)$ uniformly in n.

The function $det : M_{n} (B) \to B$ is $(μ_{n}, β)$ -PR, and the set $μ_{n}^{- 1} (G)$ is PR uniformly in n.

The function $ch : M_{n} (B) \to B [λ]$ is $(μ_{n}, β^{})$ -PR uniformly in n.*

If $B$ is a field then there is a PR function $f : N \times N \to N$ such that ${(μ_{n} (i))}^{- 1} = μ_{n} (f (i, n))$ for all n and $i \in μ_{n}^{- 1} (G)$ .

Given a general linear system of equations over a PR field, one can (using, say, the Gauss method) primitive recursively find its general solution (i.e., a fundamental system of solutions).

Let $B$ be a ring and $p = a_{0} x^{0} + \dots + a_{m} x^{m}$ , $q = b_{0} x^{0} + \dots + b_{n} x^{n}$ be polynomials over $B$ . Recall that Silvester matrix for p, q is the matrix $S = S (p, q) \in M_{m + n} (B)$ whose first n rows are $\begin{matrix} (a_{m}, \dots, a_{0}, 0, \dots, 0), (0, a_{m}, \dots, a_{0}, 0, \dots, 0), (0, 0, a_{m}, \dots, a_{0}, 0, \dots, 0), \dots \end{matrix}$ and whose last m rows are $\begin{matrix} (b_{n}, \dots, b_{0}, 0, \dots, 0), (0, b_{n}, \dots, b_{0}, 0, \dots, 0), (0, 0, b_{n}, \dots, b_{0}, 0, \dots, 0), \dots \end{matrix}$
Definition 4.
For $m, n > 0$ , the resultant of p, q, denoted $res (p, q)$ is defined as the determinant $det (S)$ of the Silvester matrix for p, q. We also define $res (p, q) = a_{0}^{n}, b_{0}^{m}, 1$ respectively for $m = 0 < n$ , $n = 0 < m$ , $m = 0 = n$ .

Thus, $res : B [x] \times B [x] \to B$ . Note that the resultant may also be considered as a fixed polynomial in $Z [a_{0}, \dots, a_{m}, b_{0}, \dots, b_{n}]$ . Clearly, if β is a PR-constructivization of $B$ then the resultant is a PR function in the corresponding numberings $β^{}$ , β.

In the remainder of this section we assume that $B$ is a field. Recall that discriminant* $D (p)$ of $p = a_{0} x^{0} + \dots + a_{m} x^{m} \in B [x]$ (where $a_{m} \neq 0$ and $m > 1$ ) is defined by $D (p) = a_{m}^{2 m - 2} \prod_{i < j} {(x_{i} - x_{j})}^{2}$ where $x_{1}, \dots, x_{m}$ is a list of all roots (possibly with repetition) of p in an algebraic closure $\overline{B}$ of $B$ . In the next proposition we recall some properties of resultant and discriminant from [24,39]. Some other properties proved in [24] will be recalled later.
Proposition 13.

We have: $res (p, q) = 0$ iff either $a_{m} = b_{n} = 0$ or $gcd (p, q)$ has degree $> 0$ .

Let p be a polynomial over $B$ of degree $m > 1$ . Then p has a multiple root in $\overline{B}$ iff $D (p) = 0$ iff p is not square-free iff $gcd (p, p^{'}) \neq 1$ .

Let p be a polynomial over $B$ of degree $m > 1$ . Then $res (p, p^{'}) = \pm a_{m} D (p)$ , hence $D (p) \in B$ .

Let $p = a_{m} \prod_{i} (x - x_{i})$ and $q = b_{n} \prod_{j} (x - y_{j})$ be in $B [x_{1}, \dots, x_{m}, y_{1}, \dots, y_{n}] [x]$ . Then $res (p, q) = {(- 1)}^{m n} b_{n}^{m} \prod_{j} p (y_{j}) = a_{m}^{n} \prod_{i} q (x_{i}) = a_{m}^{n} b_{n}^{m} \prod_{i, j} (x_{i} - y_{j})$ .

Let p, q be polynomials of positive degrees m, n over $B$ , and $x_{1}, \dots, x_{m}$ and $y_{1}, \dots, y_{n}$ be the lists of all roots of p and q in $\overline{B}$ , respectively. Then the equalities of the previous item hold.

As already mentioned, proofs of results in this section follow easily from known proofs. PR analogues of many other algebraic facts may also be obtained this way. Below we prove some less straightforward results from PR algebra and analysis.
4. PR real closure

By a classical theorem of Artin and Schreier, for any ordered field $A$ there exists an algebraic ordered extension $\hat{A} \supseteq A$ which is real closed. Such an extension, called the real closure of $A$ , is unique in the sense that for any real closure $B$ of $A$ there is a unique isomorphism between $B$ and $\hat{A}$ identical on $A$ .

Yu.L. Ershov [9] and independently E.W. Madison [25] proved a computable version of the Artin–Schreier theorem: if $A$ is constructivizable then so is also $\hat{A}$ . In this section we make search for a PR analogue of the Ershov–Madison theorem. Though we have not found a complete analogue, we describe one for the case of Archimedean ordered fields. We recall some details of the proof of Ershov–Madison’s theorem in [25] which are used for our PR version (the proof in [9] is a particular case of a proof of a more general model-theoretic result and it is not currently clear how to adjust it to the PR case).

The author of [25] defines, from any given constructivization α of an ordered field $A$ , a constructivization $\hat{α}$ of the real closure $\hat{A}$ as follows (we use slightly modified notation). Let $P (i, k)$ mean that either $α_{i}^{*}$ is the zero polynomial (i.e., all coefficients of $α_{i}^{*}$ are zero) or $α_{i}^{*}$ has at most k roots in $\hat{A}$ . Then $\hat{α} (⟨ i, k ⟩) = 0$ if $P (i, k)$ , otherwise $\hat{α} (⟨ i, k ⟩)$ is the $(k + 1)$ -st (w.r.t. <) root b of $α_{i}^{*}$ in $\hat{A}$ (i.e., $α_{i}^{*} (b) = 0$ and there are precisely k roots of $α_{i}^{*}$ in $\hat{A}$ strictly below b).

It remains to check that $+, \cdot, ⩽$ are $\hat{α}$ -computable. As observed in [25], this follows from the Tarski quantifier elimination for real closed fields [38]. For instance, in order to check $\hat{α}$ -computability of + (equivalently, computability of the relation $\hat{α} (m) + \hat{α} (n) = \hat{α} (p)$ on $N$ ) it suffices to note that, using the definition of $\hat{α}$ one can compute, given $m, n, p \in N$ , a first-order formula $ϕ (x_{0}, \dots, x_{l})$ of signature $σ = {+, \cdot, -,^{- 1}, ⩽, 0, 1, c_{0}, c_{1}, \dots}$ and a string $(j_{0}, \dots, j_{l})$ of natural numbers such that $\hat{α} (m) + \hat{α} (n) = \hat{α} (p)$ iff $ϕ (α (j_{0}), \dots, α (j_{l}))$ is true in $\hat{A}$ . By the quantifier elimination, we can think that ϕ is quantifier-free. Since $A$ is a substructure of $\hat{A}$ , the values of $ϕ (α (j_{0}), \dots, α (j_{l}))$ in both structures coincide. Since $(A, α)$ is constructive, the relation $\hat{α} (m) + \hat{α} (n) = \hat{α} (p)$ is computable.

Unfortunately, this argument does not automatically yield the PR-version. If $(A, α)$ is PR then the Madison proof does yield that the graphs of signature functions are PR in $\hat{α}$ . This follows from the proof sketched above because Tarski’s quantifier elimination is PR, i.e., from an arbitrary first-order formula ϕ as above one can primitive recursively find an equivalent quantifier-free formula (even better complexity bounds for quantifier elimination are known, see e.g. [3] and references therein). So, at first glance the PR-version of the Ershov–Madison theorem automatically follows from Madison’s proof sketched above. But primitive recursiveness of a graph of a function does not imply primitive recursiveness of the function itself, see e.g. Section 6.4 of [28]. This is a major obstacle to proving the PR-version of the Ershov–Madison theorem in full generality. In fact, we currently do not have a proof for the general case. But we do have a reasonable version for a natural subclass of Archimedean fields.

Every Archimedean ordered field is isomorphic to a substructure of the ordered field $R$ of reals, so in the sequel we always assume that $A \subseteq R$ . In fact, we can also assume that $\hat{A} \subseteq R$ since $\hat{A}$ is isomorphic (over $A$ ) to the ordered field of real roots of non-zero polynomials from $A [x]$ . So, from now on we always assume that $A$ and $\hat{A}$ are ordered subfields of $R$ , i.e. $α, \hat{α} : N \to R$ , and $\hat{A}$ is the set of real roots of non-zero polynomials over $A$ .

Note that if $α : N \to R$ is a constructivization of $A$ then $(A, α)$ is computably Archimedean in the sense that $α (n) ⩽ f (n)$ , for a suitable computable function f. Again, the PR-version of the last fact, probably, does not hold in general. In fact, our proof below works only for PR-Archimedean fields which we define as the PR ordered subfields $(A, α)$ of $R$ such that there is a PR function f with $\forall n (α (n) ⩽ f (n))$ . The main result of this section is the following.

Theorem 1.
If $(A, α)$ is a PR-Archimedean subfield of $R$ then so is also $(\hat{A}, \hat{α})$ .

The theorem follows from Facts 1–7 proved below. Most of the facts just show that some standard algebraic functions are PR. The proofs of some facts are versions of the corresponding proofs in [1,2,24] which show that the ordered field $R_{alg}$ of algebraic reals is PTIME-presentable.
Fact 1.
There is a PR function f such that all real roots of any non-zero polynomial $α_{i}^{} \in A [x]$ are in the interval* $(- f (i), f (i))$ . In particular, $\hat{α} (⟨ i, k ⟩) < f (i)$ for all i, k (so $(\hat{A}, \hat{α})$ is PR-Archimedean provided that it is a PR ordered field).
Proof.
By the notation in Section 3, $α_{i}^{} = α (i_{0}) x^{0} + \dots + α (i_{n}) x^{n}$ . Since $α_{i}^{}$ is non-zero, we have $α (i_{m}) \neq 0$ where $m ⩽ n$ is the degree of $α_{i}^{}$ . As is well known, all real roots of $α_{i}^{}$ are in $(- M_{i}; M_{i})$ where $M_{i} = 1 + a | α {(i_{m})}^{- 1} | \in A$ and $a = max {| α (i_{j}) | : j < m}$ . Since $(A, α)$ is PR-Archimedean, there is a PR-function f with $M_{i} ⩽ f (i)$ . The second assertion follows from the definition of $\hat{α} (⟨ i, k ⟩)$ . □
Fact 2.
Given a polynomial $p \in A [x]$ of degree $> 1$ , one can primitive recursively find the Sturm sequence of polynomials $sseq (p) = (p_{0}, p_{1}, \dots, p_{m})$ in $A [x]$ with the following property: the number of real roots of p in any interval $(a, b]$ equals $v (a) - v (b)$ where $v (c)$ , for $c \in R$ , is the sign alternation number in the sequence $(p_{0} (c), p_{1} (c), \dots, p_{m} (c))$ .
Proof.
As is well known, the sequence sseq is defined as follows: $p_{0} = p$ , $p_{1} = p^{'}$ is the derivative of p, and for $j > 1$ , $p_{j}$ is the negative remainder after dividing $p_{j - 1}$ by $p_{j - 2}$ (thus, $sseq (p)$ is a small variation of the sequence from the Euclidean algorithm for p, $p^{'}$ ). By Proposition 7 and other remarks in Section 2, the sequence $sseq (p)$ can be found primitive recursively. □
Fact 3.
Given a non-zero polynomial $p \in A [x]$ and $a, b \in Q$ , one can primitive recursively find the number of real roots of p in the interval $(a, b]$ , as well as the number of all real roots of p.
Proof.
Follows from Facts 1, 2 and Proposition 5. □
Fact 4.
Given $p \in A [x]$ of degree $m ⩾ 2$ , one can primitive recursively find a positive rational $δ_{p} < Δ_{p}$ where $Δ_{p}$ is the smallest distance between distinct roots of p.
Proof.
Without loss of generality we can think that p has no multiple roots (otherwise, we can take $p / gcd (p, p^{'})$ instead of p where $gcd (p, p^{'})$ is the greatest common divisor of p and $p^{'}$ , because p and $p / gcd (p, p^{'})$ are known to have the same roots and the latter polynomial has no multiple roots, see remarks before Proposition 7). By Mahler’s theorem (see the corollary of Theorem 2 in [26]), $\begin{matrix} Δ_{p} > \sqrt{3} m^{- \frac{m + 2}{2}} {| D (p) |}^{\frac{1}{2}} | L {(p)}^{- (m - 1)} > m^{- (m + 2)} {| D (p) |}^{\frac{1}{2}} | L {(p)}^{- (m - 1)} \end{matrix}$ where $D (p)$ is the discriminant of p and $L (p) = | α (i_{0}) | + \dots + | α (i_{m}) |$ . Since $D (p) \in A$ by Proposition 13 and p has no multiple roots, $D (p) \neq 0$ . Since $(A, α)$ is PR-Archimedean, we can primitive recursively find a positive rational $δ_{p}$ below $m^{- (m + 2)} | D (p) |^{\frac{1}{2}} | L {(p)}^{- (m - 1)}$ . □
Fact 5.
Given a non-zero polynomial $p \in A [x]$ and a positive rational number ε, one can primitive recursively find a sequence $I_{1} < \dots < I_{l}$ (where $l ⩾ 0$ is the number of real roots of p) of pairwise disjoint rational intervals of length $⩽ ε$ which separate the real roots of p, i.e. every $I_{j}$ contains precisely one real root of p.
Proof.
Follows from the previous facts using the bisection method. □
Fact 6.
Operations +, ·, −, $^{- 1}$ on $\hat{A}$ are $\hat{α}$ -PR.
Proof.
All operations are considered similarly, so we give details only for +; we describe a PR function $f : N \times N \to N$ with $\hat{α} (m) + \hat{α} (m^{'}) = \hat{α} (f (m, m^{'}))$ . Let $m = ⟨ i, k ⟩$ and $m^{'} = ⟨ i^{'}, k^{'} ⟩$ . By the definition of $P (i, k)$ , this relation is PR. If $P (i, k)$ then we set $f (m, m^{'}) = m^{'}$ . If $\neg P (i, k)$ and $P (i^{'}, k^{'})$ then we set $f (m, m^{'}) = m$ . It remains to consider the case when both $P (i, k)$ and $P (i^{'}, k^{'})$ are false, i.e. $\hat{α} (m) = c$ is the $(k + 1)$ -st real root of $p = α_{i}^{}$ and $\hat{α} (m^{'}) = d$ is the $(k^{'} + 1)$ -st real root of $q = α_{i^{'}}^{}$ . It suffices to primitive recursively find $s, t \in N$ such that $\neg P (s, t)$ and $c + d$ is the $(t + 1)$ -st real root of $r = α_{s}^{} \in A [x]$ (then we can set $f (m, m^{'}) = ⟨ s, t ⟩$ ).

By (the proof of) Theorem 6 in [24], the polynomial $r = res (p (x - y), q (y))$ has $c + d$ as a root (in fact, the complex roots of r coincide with the sums of complex roots of p, q). By remarks before Proposition 13, we can primitive recursively find s with $r = α_{s}^{}$ . For any rational intervals $(a, b) ∋ c$ and $(a^{'}, b^{'}) ∋ d$ , the interval $I = (a + a^{'}, b + b^{'})$ contains $c + d$ , and its length may be made arbitrarily small. Using Fact 5, we can primitive recursively find a sequence $I_{1} < \dots < I_{l}$ of rational intervals which separate all real roots of r such that I intersects precisely one interval $I_{t}$ , $t ⩽ l$ , of this sequence. Then $c + d \in I_{t}$ , hence it remains to set $f (m, m^{'}) = ⟨ s, t ⟩$ . □
Fact 7.
The relation ⩽ on $\hat{A}$ is $\hat{α}$ -PR.
Proof.
By Fact 6, it suffices to show that the relation $0 ⩽ \hat{α} (m)$ is PR. Let again $m = ⟨ i, k ⟩$ . By the definition of $\hat{α} (m)$ we have: $0 ⩽ \hat{α} (m)$ iff either $P (i, k)$ or ( $\neg P (i, k)$ and the $(k + 1)$ -st real root of $α_{i}^{}$ is non-negative). Consider the case when $P (i, k)$ is false. By Fact 5, we can primitive recursively find a sequence $I_{1} < \dots < I_{l}$ (where $l > k$ is the number of real roots of $α_{i}^{}$ ) of pairwise disjoint rational intervals of length $⩽ ε$ such that every $I_{j}$ contains precisely one real root of $α_{i}^{}$ . Then $\hat{α} (m) \in I_{k + 1}$ . Assume first that $α_{i}^{} (0) = 0$ (i.e., $α (i_{0}) = 0$ ). Then $0 \in I_{j}$ for a unique $j ⩽ l$ , hence $0 ⩽ \hat{α} (m)$ iff $j ⩽ k + 1$ .

In the case $α_{i}^{} (0) \neq 0$ , we consider the polynomial $q = x α_{i}^{} \in \hat{A} [x]$ which satisfies $q (0) = 0$ . Computing the sequence $I_{1} < \dots < I_{l}$ for polynomial q in place of $α_{i}^{}$ and applying the argument of the previous paragraph we see that $0 ⩽ \hat{α} (m)$ iff $j < k + 1$ . Altogether, these arguments and the primitive recursiveness of relation $P (i, k)$ complete the proof. □

By a classical theorem of Steinitz, for any field $A$ there exists its algebraic closure $\overline{A} \supseteq A$ which is unique in the sense that for any algebraic closure $B$ of $A$ there is an isomorphism between $B$ and $\overline{A}$ identical on $A$ . M. Rabin [31] proved a computable version of the Steinitz theorem: if $A$ is constructivizable then so is also $\overline{A}$ . The uniqueness up to computable isomorphism holds for constructive fields which have computable splitting. Though we do not yet know a complete PR-analogue of Rabin’s theorem, we note that the algebraic closures of PR Archimedean ordered fields are PR-constructive.

Recall (see e.g. Chapters 10, 11 of [39]) that a real closed field $B$ is never algebraically closed (the polynomial $x^{2} + 1$ has no root in $B$ ) but its algebraic closure $\overline{B}$ is constructed very easily by adjoining a root of $x^{2} + 1$ . Thus, $\overline{B}$ is isomorphic to $B \times B$ where the arithmetic on pairs is similar to that of the field $C$ of complex numbers. If $(A, α)$ is a constructive ordered subfield of $R$ , let $\bar{α}$ be the induced numbering of $\overline{A}$ (considered as a subfield of $C$ ), i.e. $\bar{α} ⟨ n_{1}, n_{2} ⟩ = (\hat{α} (n_{1}), \hat{α} (n_{2}))$ . The following is an immediate corollary of Theorem 1. Corollary 1.
If $(A, α)$ is a PR-Archimedean ordered subfield of* $R$ then $(\overline{A}, \overline{α})$ is a PR subfield of $C$ .
Remark 1.
The computable versions of proofs above show that the computable version of Theorem 1 holds: If $(A, α)$ is a constructive ordered subfield of $R$ then so is also $(\hat{A}, \hat{α})$ .

5. PR root-finding

We say that a computable field $(B, β)$ has computable root-finding (cf. [11,29]) if, given a polynomial $p \in B [x]$ of degree $> 1$ , one can compute a (possibly, empty) list of all roots of p in $B$ . Theorem 4.43 in [11] states that $(B, β)$ has computable root-finding iff it has computable splitting. As usual, the notion of PR root-finding is obtained by changing “computable” to “PR” in the definition above. The proof of Theorem 4.43 in [11] works for the PR-version which, together with Proposition 11, yields the following.

Proposition 14.
A PR field has PR root-finding iff it has PR splitting.

Obviously, every computable algebraically closed field has computable root-finding, but the proof makes use of the unbounded search. The next theorem shows that the PR-version of this holds at least for some fields considered above. To shorten formulations, we denote by $pro (R)$ (resp. $pra (R)$ , $pras (R)$ ) the set of all $α : N \to R$ such that $(A, α)$ , $A = rng (α)$ , is a PR-constructive ordered subfield of $R$ (resp., a PR-Archimedean, a PR-Archimedean ordered subfield with PR splitting). By a PRAS-field we mean an ordered subfield $A$ of $R$ which has a PR-constructivization $α \in pras (R)$ . In the remaining part of the paper, we usually denote by $A$ , $\hat{A}$ , $\overline{A}$ the (ordered) fields associated with α, $\hat{α}$ , $\overline{α}$ , respectively.
Theorem 2.
If $α \in pras (R)$ then $(\hat{A}, \hat{α})$ and $(\overline{A}, \overline{α})$ have PR root-finding.

Under the assumption $α \in pras (R)$ we first establish some auxiliary facts. Let $σ = {+, \cdot, c_{0}, c_{1}, \dots}$ .
Fact 1.
Given a polynomial $p \in A [x_{0}, \dots, x_{k}]$ and polynomials $p_{0}, \dots, p_{k} \in A [x]$ of positive degrees, one can primitive recursively find $q \in A [x]$ of positive degree such that, for all complex roots $b_{i}$ of $p_{i}$ , $i ⩽ k$ , the value $p (b_{0}, \dots, b_{k})$ is a root of q.
Proof.
Let $r^{+}$ , $r^{\cdot}$ be binary operators on $A [x]$ such that all sums (resp. products) of complex roots of p, q are among the roots of $r^{+} (p, q)$ (resp. $r^{\cdot} (p, q)$ ). By the proof of Theorem 6 in [24] (see also the proof of Fact 6 in the previous section), operators $r^{+}$ , $r^{\cdot}$ are given by explicit formulas (based on a resultant calculus) which show they are $α^{}$ -PR.

We associate with any σ-term $t = t (x_{0}, \dots, x_{k})$ the polynomial $q_{t} \in A [x]$ as follows: $q_{c_{n}} = x - α (n)$ , $q_{x_{i}} = p_{i}$ , $q_{t_{1} + t_{2}} = r^{+} (q_{t_{1}}, q_{t_{2}})$ , $q_{t_{1} \cdot t_{2}} = r^{\cdot} (q_{t_{1}}, q_{t_{2}})$ . By induction on t one easily checks that, for all complex roots $b_{i}$ of $p_{i}$ , $i ⩽ k$ , $t^{A} (b_{0}, \dots, b_{k})$ is a root of $q_{t}$ .

By Proposition 6, from $p \in A [x_{0}, \dots, x_{k}]$ one can primitive recursively find a σ-term $t = t (x_{0}, \dots, x_{k})$ such that $p (b_{0}, \dots, b_{k}) = t^{A} (b_{0}, \dots, b_{k})$ for all $b_{0}, \dots, b_{k} \in A$ . Thus, we can take $q = q_{t}$ . □
Fact 2.
Given a non-zero polynomial* $r \in A [x]$ , one can primitive recursively find $q_{1}, q_{2} \in A [x]$ such that, for any complex root $b = (b_{1}, b_{2})$ of r, the real part $b_{1}$ is a root of $q_{1}$ and the imaginary part $b_{2}$ is a root of $q_{2}$ .
Proof.
Let $q_{1} = q$ be the polynomial obtained from the algorithm of Fact 1 for $p (x_{0}, x_{1}) = \frac{1}{2} (x_{0} + x_{1})$ and $p_{0} = p_{1} = r$ . For any complex root $b = (b_{1}, b_{2})$ of r we then have: $p (b, \bar{b}) = b_{1}$ , b is a root of $p_{0}$ , and $\bar{b}$ is a root of $p_{1}$ where $\bar{b} = (b_{1}, - b_{2}) = b_{1} - i b_{2}$ is the complex conjugate of b and i is the imaginary unit. Thus, $q_{1}$ has the desired property.

Let now $q = a_{0} + a_{1} x + a_{2} x^{2} + \dots$ be the polynomial obtained from the algorithm of Fact 1 for $p (x_{0}, x_{1}) = \frac{1}{2} (x_{0} - x_{1})$ and $p_{0} = p_{1} = r$ . For any complex root $b = (b_{1}, b_{2})$ of r we then have: $p (b, \bar{b}) = i b_{2}$ , b is a root of $p_{0}$ , and $\bar{b}$ is a root of $p_{1}$ . Thus, $q (i b_{2}) = 0$ , hence also $q (- i b_{2}) = 0$ . Summing up the last two equalities we see that $q_{2} (b_{2}) = 0$ where $q_{2} = a_{0} + a_{2} x^{2} + \dots$ . Thus, $q_{2}$ has the desired property. □
Fact 3.
Given a polynomial $p = b_{0} x^{0} + \dots + b_{n} x^{n} \in \overline{A} [x]$ and polynomials $q_{0}, \dots, q_{n} \in A [x]$ such that $q_{i} (b_{i}) = 0$ for each $i ⩽ n$ , one can primitive recursively find $r \in A [x]$ such that every complex root of p is among the roots of r.
Proof.
The proof is essentially the same as in the Algorithm 3 of [24], hence we give only a sketch. Since $(A, α)$ has PR splitting, we may without loss of generality think that $q_{0}, \dots, q_{n}$ are irreducible. By Proposition 10(3), we may primitive recursively find $b \in \overline{A}$ and irreducible $t, p_{0}, \dots, p_{n} \in A [y]$ such that $A (b) = A (b_{0}, \dots, b_{n})$ $t (b) = 0$ , and $p_{i} (b) = b_{i}$ for all $i ⩽ n$ . Let $s = gcd (t, p_{n})$ . We may without loss of generality think that $deg (s) = 0$ (otherwise, replace t by $t / s$ ). Then the polynomial $r = res (t, q)$ , where $q = p_{0} x^{0} + \dots + p_{n} x^{n} \in A [y] [x]$ , has the desired properties. By the results in Section 3, r may be found primitive recursively. □
Proof of Theorem 2.
Given $p \in \overline{A} [x]$ , we have to primitive recursively find all complex roots of p. By Fact 3, we can find $r \in A [x]$ such that all complex roots of p are among the roots of r. By Fact 2, we can find $q_{1}, q_{2} \in A [x]$ such that, for any complex root $b = (b_{1}, b_{2})$ of r, the real part $b_{1}$ is a root of $q_{1}$ and the imaginary part $b_{2}$ is a root of $q_{2}$ . By the definition of $\overline{α}$ and the results of Section 4, we can find the lists $b_{1, 0} < \dots < b_{1, m}$ and $b_{2, 0} < \dots < b_{2, n}$ of all real roots of $q_{1}$ and $q_{2}$ , respectively. Then all complex roots of p are among $(b_{1, i}, b_{2, j})$ where $i ⩽ m$ , $j ⩽ n$ . Substituting these complex numbers one by one in p and using Proposition 5, we can primitive recursively choose all complex roots of p.

It remains to show that $(\hat{A}, \hat{α})$ has PR root-finding. Let $p \in \hat{A} [x]$ ; we have to find a list of all real roots of p. Since $\hat{α} ⩽_{PR} \overline{α}$ , we have ${\hat{α}}^{} ⩽_{PR} {\overline{α}}^{}$ by Proposition 4. By the previous paragraph, we can compute the list of all complex roots of p. Choosing the real numbers from this list, we obtain a list of all real roots of p. □
Corollary 2.

For all $α, β \in pra (R)$ , we have: $α ⩽_{PR} \hat{α} \in pra (R)$ , $α ⩽_{PR} β$ implies $\hat{α} ⩽_{PR} \hat{β}$ , and similarly for $pras (R)$ in place of $pra (R)$ .

For any $α \in pras (R)$ , $\hat{\hat{α}} ⩽_{PR} \hat{α} \in pras (R)$ , so $α \mapsto \hat{α}$ is a closure operator on $(pras (R); ⩽_{PR})$ .

As mentioned in Section 4, the real closure of an ordered field is unique up to isomorphism over this ordered field. We conclude this section with a PR-version of this fact. The proof is an easy adaptation of the proof for the classical case (see e.g. [39], Theorem 8 in Section 82). Proposition 15.
Let $α \in pras (R)$ and let $(B, β)$ be a PR-Archimedean ordered field such that it has PR root-finding, $B$ is a real closure of $A$ and $α ⩽_{PR} β$ . Then $(\hat{A}, \hat{α})$ is PR isomorphic to $(B, β)$ over $(A, α)$ , i.e. there is an (unique) isomorphism f from $\hat{A}$ onto $B$ such that f is identical on A, f is $(\hat{α}, β)$ -PR, and $f^{- 1}$ is $(β, \hat{α})$ -PR.
Remark 2.
Let $co (R)$ , $cs (R)$ be the computable analogues of $pra (R)$ , $pras (R)$ , i.e. $co (R)$ (resp. $cs (R)$ ) is the set of all maps $α : N \to R$ such that $(A, α)$ is a constructive ordered subfield of $R$ (resp., a constructive ordered subfield which has computable splitting). The proofs above apply to these computable analogues, in particular the computable version of Proposition 15 gives a sufficient condition for uniqueness of the computable real closure.

6. PRAS-fields vs. PR reals

In [34,35] we have shown that for any finite set F of computable reals there is a computable real closed ordered subfield $(B, β)$ of the computable reals such that $F \subseteq B$ (see also a more general Theorem 4.1 in [30] obtained independently). This fact implies the following charaterization of the union of all constructivizable ordered fields of reals: $\begin{matrix} R_{c} = ⋃ {A ∣ α \in co (R)} = ⋃ {A ∣ α \in cs (R)} \end{matrix}$ where $R_{c}$ is the set of computable reals and $co (R)$ , $cs (R)$ are the computable analogues of $pra (R)$ , $pras (R)$ . In this section we are interested in PR-analogues of these facts from [34,35].

The PR-analogue of $R_{c}$ is the ordered field $R_{p}$ of PR reals. In this section we often cite the survey [8] on PR reals where references to the source papers may be found; we sometimes use slightly different notation from that in [8]. Recall that a real number a is PR if $a = {lim}_{n} q_{n}$ for a PR sequence ${q_{n}}$ of rational numbers which is fast Cauchy, i.e. $| q_{n} - q_{n + 1} | < 2^{- n}$ for all n. There is a natural numbering τ of $R_{p}$ . To define it precisely, we describe some technical details which will also be used in Section 9.

With any $p \in N$ (see the end of Section 2) we associate the sequence $ϰ \circ p \in Q^{N}$ of rational numbers. Since $ϰ : N \to Q$ is a bijection, the function $p \mapsto ϰ \circ p$ is a bijection between $N$ and $Q^{N}$ . From the properties of ϰ in Section 2 it follows that p is PR iff $ϰ \circ p$ is PR, and similarly for functions of larger arity. By $Ca$ we denote the set of all $p \in N$ such that $ϰ \circ p$ is fast Cauchy. With any $p \in N$ we associate $\tilde{p} \in N$ as follows: if $\forall i < n (| ϰ (p (i)) - ϰ (p (i + 1)) | < 2^{- i})$ then $\tilde{p} (n) = p (n)$ , else $\tilde{p} (n) = p (i_{0})$ where $i_{0} = μ i < n (| ϰ (p (i)) - ϰ (p (i + 1)) | ⩾ 2^{- i})$ . Clearly, $\tilde{p} \in Ca$ for each $p \in N$ , and if $p \in Ca$ then $\tilde{p} = p$ , in particular $Ca = {\tilde{p} ∣ p \in N}$ .

Now we define the numbering τ of $R_{p}$ by: $τ (e) = {lim}_{n} ϰ ({\tilde{ψ}}_{e} (n))$ where ψ is the numbering of unary PR functions from the end of Section 2 and $ψ_{e} = ψ (e)$ . In the next proposition we collect some properties of the introduced objects.

Proposition 16.

$R_{p}$ is a subfield of $R$ , and operations +, −, · are τ-PR.

The sequence of reals ${τ (e)}$ is computable, hence the inclusion $R_{p} \subseteq R_{c}$ is proper.

The relation < on $R_{p}$ is τ-c.e.

The ordered field $R_{p}$ is real closed.

The ordered field $R_{p}$ is not constructivizable.

Proof.
(1) Proof is easily extracted (say) from the proofs of Proposition 4.1 and Theorem 4.2 in [8] and the remarks at the end of Section 2. We have to find a PR function g such that $τ (m) + τ (n) = τ (g (m, n))$ , and similarly for −, ·. Denote the sequences ${\tilde{ψ}}_{m}$ and ${\tilde{ψ}}_{n}$ by ${p_{i}}$ and ${q_{i}}$ , respectively. These are PR fast Cauchy sequences of rationals converging to $τ (m)$ and $τ (n)$ , respectively.

Then $| p_{i + 1} - p_{j + 1} | < 2^{- k}$ and $| q_{i + 1} - q_{j + 1} | < 2^{- k}$ for $i, j ⩾ k$ . Let $r_{i} = p_{i} + q_{i}$ , then ${r_{i + 2}}$ is a fast Cauchy sequence of rationals that converges to $τ (m) + τ (n)$ . By the properties of ϰ, $h = {ϰ^{- 1} (r_{i + 2})}$ , $h = h_{m, n}$ is a PR function from $Ca$ , hence $\tilde{h} = h$ . By Robinson’s theorem, $h_{m, n} = t_{m, n}$ for some $t_{m, n} \in T_{0}$ . Moreover, the terms $t_{m, n}$ may be chosen so that the function $(m, n) \mapsto N (t_{m, n})$ is PR. Then for some binary PR function g we have $h_{m, n} = ψ_{g (m, n)}$ . Therefore, $τ (m) + τ (n) = τ (g (m, n))$ , as desired.

For the operation − the proof is the same, only now we have to set $r_{i} = p_{i} - q_{i}$ . For the operation · the proof is the same, only now we have to set $r_{i} = p_{i} \cdot q_{i}$ and $h = {ϰ^{- 1} (r_{i + f (m, n, i)})}$ , for a suitable PR function f (see the proof of Theorem 4.2 in [8]).

(2) The computability of the sequence follows from the definition of τ. The properness of inclusion follows by the well-known property of the computable reals.

(3) Obvious from the definition of τ.

(4) This is due to Peter Hertling (private communication [16], with permission to mention the formulation here).

(5) This is proved in [21]. □
Remark 3.
The reciprocal partial function $x^{- 1}$ is not τ-PR (this is proved by essentially the same argument as that in Proposition 24(2); the argument is topological, hence more natural to be discussed in Section 9). Nevertheless, the restriction of the reciprocal function to $R_{p} ∖ (- \frac{1}{n + 1}, \frac{1}{n + 1})$ is τ-PR uniformly in n.

For any $α \in pra (R)$ , let $R_{p} (α)$ be the set of PR reals b such that the sign of polynomials in $A [x]$ at b is checked primitive recursively. Formally, for any real b, let $sign (b)$ be 0, 1, 2 depending on whether b is zero, positive, or negative. Then $R_{p} (α)$ is the set of all $b \in R_{p}$ such that the function $i \mapsto sign (α_{i}^{} (b))$ is PR. More generally, for any $n ⩾ 0$ , let $R_{p}^{[n]} (α)$ be the set of tuples $\bar{b} = (b_{0}, \dots, b_{n})$ of PR reals such that the function $i \mapsto sign (α_{i}^{[n]} (b_{0}, \dots, b_{n}))$ is PR where $α^{[n]}$ is the numbering of $A [x_{0}, \dots, x_{n}]$ from Section 4. Note that $R_{p} (α) = R_{p}^{[0]} (α)$ .
Proposition 17.

If $α, β \in pra (R)$ and* $α ⩽_{PR} β$ then $R_{p} {(β)}^{[n]} \subseteq R_{p} {(α)}^{[n]}$ for all n.

For all $α \in pra (R)$ and n we have: $R_{p} {(α)}^{[n]} \subseteq R_{p} {(ϰ)}^{[n]}$ .

For any $α \in pro (R)$ we have $A \subseteq R_{p} (α)$ .

For any $α \in pra (R)$ there is a uniformly PR sequence ${g_{n}}$ of PR functions $g_{n} : N \to Q$ such that ${g_{n} (i)}_{i}$ is a fast Cauchy sequence converging to $α (n)$ , in particular $α ⩽_{PR} τ$ .

Proof.
1. Let $\bar{b} \in R_{p} (β)$ , so $i \mapsto sign (β_{i}^{} (\bar{b}))$ is PR. Since $α ⩽_{PR} β$ , by Proposition 4 we have $α^{[n]} ⩽_{PR} β^{[n]}$ , so $α_{i}^{[n]} = β_{f (i)}^{[n]}$ for some PR function f. Then $sign (α_{i}^{[n]} (\bar{b})) = sign (β_{f (i)}^{[n]} (\bar{b}))$ , hence $i \mapsto sign (α_{i}^{[n]} (\bar{b}))$ is PR.

2. The assertion follows from item 1 because, clearly, $ϰ ⩽_{PR} α$ .

3. Let $a \in A$ and let $a_{0}, a_{1} \in Z$ satisfy $a_{0} < a < a_{1}$ . Using the bisection method starting with the interval $[a_{0}, a_{1}]$ and the PR-constructivity of α, we construct a PR function $g : N \to Q$ such that $| g (i) - a | ⩽ (a_{1} - a_{0}) \cdot 2^{- i}$ . Then ${g (i)}_{i}$ is a fast Cauchy sequence converging to a, hence $a \in R_{p}$ . Moreover, by Proposition 4 we get $a \in R_{p} (α)$ .

4. Since $(A, α)$ is PR-Archimedean, $- f (n) < α (n) < f (n)$ for some PR function f. Using the bisection method as in (3) with $[- f (n), f (n)]$ in place of $[a_{0}, a_{1}]$ , we construct a uniformly PR sequence ${g_{n}}$ with the specified properties. The uniformity yields a PR function f such that $ϰ^{- 1} \circ g_{n} = ψ_{f (n)}$ . By the definition of τ, $α ⩽_{PR} τ$ via f. □

By items 2 and 3 of the last proposition, $α \in pra (R)$ implies $rng (α) \subseteq R_{p} (ϰ)$ , hence all PR ordered fields of reals are contained in $R_{p} (ϰ)$ . The next result shows which elements of $R_{p} (ϰ)$ (and, moreover, which finite tuples of reals) can be included into some PR ordered field of reals.
Theorem 3.
Let* $α \in pras (R)$ and $\bar{b} \in R_{p}^{n}$ . Then $\exists β \in pras (R) (α ⩽_{PR} β \land b_{0}, \dots, b_{n} \in B)$ (where $B = rng (β)$ ) iff $\bar{b} \in R_{p}^{[n]} (α)$ .
Proof.
If $β \in pra (R)$ , $α ⩽_{PR} β$ , and $b_{0}, \dots, b_{n} \in B$ , then $i \mapsto sign (α_{i}^{[n]} (\bar{b}))$ is PR by Proposition 4, hence $\bar{b} \in R_{p}^{[n]} (α)$ .

Conversely, let $\bar{b} \in R_{p}^{[n]} (α)$ . First we consider the case when $b_{0}, \dots, b_{n}$ are algebraically independent over $A$ , hence $sign (α_{i}^{[n]} (\bar{b})) \in {1, 2}$ for every i with $α_{i}^{[n]} \neq 0$ . Then $A (b_{0}, \dots, b_{n})$ with the induced numbering γ is a PR field by Proposition 8 because it is isomorphic to the field $A (x_{0}, \dots, x_{n})$ of rational functions. The elements of $A (b_{0}, \dots, b_{n})$ have the form $p (\bar{b}) / q (\bar{b})$ for some $p, q \in A [x_{0}, \dots, x_{n}]$ , $q \neq 0$ . Since $p (\bar{b}) / q (\bar{b}) > 0$ iff both $p (\bar{b})$ , $q (\bar{b})$ are positive or both $p (\bar{b})$ , $q (\bar{b})$ are negative, γ is a PR constructivization of $A (b_{0}, \dots, b_{n})$ . By Proposition 9, $γ \in pras (R)$ , hence we can take $β = γ$ .

Now let $\bar{b} \in R_{p}^{n}$ be arbitrary. Without loss of generality (renumbering $b_{0}, \dots, b_{n}$ if necessary), let $j ⩽ n$ be the unique number such that $b_{0}, \dots, b_{j - 1}$ are algebraically independent over $A$ while $b_{j}, \dots, b_{n}$ are algebraic over $A (b_{0}, \dots, b_{j - 1})$ . Let γ be defined as in the previous paragraph for $j > 0$ (with n replaced by $j - 1$ ) and $γ = α$ for $j = 0$ . By the previous paragraph and Proposition 2, we can take $β = \hat{γ}$ . □

The results above imply the following characterization of the union of all PRAS-fields.
Corollary 3.
$R_{p} (ϰ) = ⋃ {A ∣ α \in pro (R)} = ⋃ {A ∣ α \in pra (R)} = ⋃ {A ∣ α \in pras (R)}$ .
Proof.
Obviously, $⋃ {A ∣ α \in pro (R)} \supseteq ⋃ {A ∣ α \in pra (R)} \supseteq ⋃ {A ∣ α \in pras (R)}$ . By Proposition 17(3), $R_{p} (ϰ) \supseteq ⋃ {A ∣ α \in pro (R)}$ , so it suffices to show that $R_{p} (ϰ) \subseteq ⋃ {A ∣ α \in pras (R)}$ . This follows from Theorem 3 because $ϰ \in pras (R)$ . □

This corollary would yield satisfactory PR-analogues of some facts mentioned in the beginning of this section, if we had $R_{p} (ϰ) = R_{p}$ . In the next proposition we will show that this is not the case.

First we recall some facts about continuous fractions. Associate with any real x the sequence of integers ${x_{i}}$ (which we call here the canonical continuous fraction for x) and an auxiliary sequence ${d_{i}}$ as follows:

let $x_{0} = ⌊ x ⌋$ be the integer part of x and $d_{0} : = x - ⌊ x ⌋$ ;

if $d_{0} = 0$ then let $x_{1} = 0$ , otherwise let $x_{1} = ⌊ d_{0}^{- 1} ⌋$ and $d_{1} : = d_{0}^{- 1} - ⌊ d_{0}^{- 1} ⌋$ ;

if $x_{i + 1} = 0$ or $d_{i + 1} = 0$ then let $x_{i + 2} = 0$ , otherwise let $x_{i + 2} = ⌊ d_{i + 1}^{- 1} ⌋$ and $d_{i + 2} : = d_{i + 1}^{- 1} - ⌊ d_{i + 1}^{- 1} ⌋$ .

It is well known that x is rational iff $\exists i (x_{i + 1} = 0)$ . It is easy to see that $0 ⩽ d_{i} < 1$ , $x_{i + 1} ⩾ 0$ , $x_{i + 1} = 0$ implies $x_{i + 2} = 0$ , and $x_{i + 1} > 0 \land x_{i + 2} = 0$ imply $x_{i + 1} ⩾ 2$ . Note that the set of all integer sequences ${x_{i}}$ with these properties is in a bijective correspondence with $R$ which is given by ${x_{i}} \mapsto x = {lim}_{n} y_{n}$ where $y_{0} = x_{0}$ , $y_{1} = x_{0} + \frac{1}{x_{1}}$ for $x_{1} \neq 0$ and $y_{1} = y_{0}$ otherwise, $y_{2} = x_{0} + \frac{1}{x_{1} + \frac{1}{x_{2}}}$ for $x_{2} \neq 0$ and $y_{2} = y_{1}$ otherwise, and so on. The converse map $x \mapsto {x_{i}}$ is given by “computing” the canonical continuous fraction for x.

The set of reals with the PR canonical continuous fraction has a natural numbering γ constructed as follows. Associate with any sequence $ν = {x_{i}}$ of integers the sequence $ν^{'} = {x_{i}^{'}}$ as follows: $x_{0}^{'} = x_{0}$ ; if $x_{1} < 1$ then $x_{1}^{'} = 0$ , otherwise $x_{1}^{'} = x_{1}$ ; if $x_{i + 1} = 0$ or $x_{i + 2} < 1$ then $x_{i + 2}^{'} = 0$ , otherwise $x_{i + 2}^{'} = x_{i + 2}$ . Then $ν^{'}$ has the properties above, and if ν has these properties then $ν^{'} = ν$ . Let now ${ν_{n}}$ be the sequence of PR integer sequences induced by the computable sequence ${ψ_{n}}$ of all unary PR functions (as usual, we implicitly use a suitable PR bijection between $N$ and $Z$ ); then the sequence ${ν_{n}^{'}}$ consists of all PR sequences with the properties above. Setting $γ (n) = lim ν_{n}^{'}$ , we obtain a natural numbering $γ : N \to R$ of all reals with the PR canonical continuous fraction.
Proposition 18.
The inclusion $R_{p} (ϰ) \subseteq R_{p}$ is strict.
Proof.
Let $R_{4}$ be the set of reals which have PR continuous fractions (see [8]) and references therein). By a theorem of Lehman, the inclusion $R_{4} \subseteq R_{p}$ is strict (for a proof see e.g. Theorem 7.4 in [8]). So, it suffices to show that $R_{p} (ϰ) \subseteq R_{4}$ . By Corollary 3, it suffices to show that $A \subseteq R_{4}$ for every $α \in pra (R)$ .

First we show that $n \mapsto ⌊ α_{n} ⌋$ is a PR function from $N$ to $Z$ . Let $h : Z \to N$ be a PR function such that $z = α_{h (z)}$ for every $z \in Z$ . Since $α \in pra (R)$ , for some PR function f we have $- f (n) < α_{n} < f (n)$ , hence $0 < α_{n} + f (n) < 2 f (n)$ . Since $⌊ α_{n} ⌋ = ⌊ α_{n} + f (n) ⌋ - f (n)$ , it suffices to show that the function $n \mapsto ⌊ α_{n} + f (n) ⌋$ is PR. But this follows from PR-constructivity of $(A, α)$ and the obvious equalities $\begin{array}{rcl} ⌊ α_{n} + f (n) ⌋ & = & μ m < 2 f (n) (m ⩽ α_{n} + f (n) < m + 1) \\ = & μ m < 2 f (n) (α_{h (m)} ⩽ α_{n} + α_{h (f (n)))} < α_{h (m + 1)}) . \end{array}$ Let ${x_{i}^{n}}_{i}$ be the canonical continuous fraction for $α_{n}$ . By the definition above, it is a PR sequence of rationals (even uniformly in n), hence $α_{n} \in R_{4}$ and therefore $A \subseteq R_{4}$ . □

We guess that the inclusion $R_{p} (ϰ) \subseteq R_{4}$ is also strict.
Remarks 1.
1. From the proof it follows that for any $α \in pra (R)$ the relation $α_{n} \in Z$ is PR (because it is equivalent to $α_{n} = α_{h (⌊ α_{n} ⌋)}$ ).

2. Also, the proof shows that $α ⩽_{PR} γ$ (this follows from the definition of the numbering $γ : N \to R$ above and the fact that the sequence ${x_{i}^{n}}_{i}$ is PR uniformly in n).

3. For the computable versions of $pra (R)$ and $pras (R)$ all proofs of this section remain valid and yield the results mentioned in the beginning of this section because, as one easily checks, $R_{c} (ϰ) = R_{c}$ and the function $i \mapsto sign (α_{i}^{[n]} (\bar{b}))$ is computable for every $\bar{b} \in R_{c}$ . Note that the computable versions of $pro (R)$ and $pra (R)$ coincide.

We see that the relations between classes ${A ∣ α \in pro (R)}$ , ${A ∣ α \in pra (R)}$ , ${A ∣ α \in pras (R)}$ and fields $R_{p}$ , $R_{4}$ are much more intricate than for their computable analogues.

How rich is the collection $pras (R)$ ? By Proposition 9(1), $ϰ \in pras (R)$ . By Proposition 2, $pras (R)$ is closed under $α \mapsto \hat{α}$ , hence $\hat{ϰ} \in pras (R)$ , i.e., $R_{alg}$ is a PRAS-field. In fact, $R_{alg}$ is even PTIME-presentable [1,2]. Moreover, it is open whether there is PTIME-presentable ordered field of reals beyond $R_{alg}$ . In the next section we show that PRAS-fields may contain transcendental numbers.
7. PRAS-fields beyond $R_{alg}$

In this section we examine which transcendental PR reals (and tuples of PR reals) may be included in a PRAS-field. First we show that there are PRAS-fields of any countable transcendence degree.

Theorem 4.

For any $α \in pras (R)$ and any non-empty rational interval I there exists $b \in I \cap R_{p} (α)$ which is transcendental over $A$ .

For any $α \in pras (R)$ there exists a uniformly PR infinite sequence $b_{0}, b_{1}, \dots$ of reals which are algebraically independent over $A$ and satisfy $\bar{b} \in R_{p}^{[n]} (α)$ for every n where $\bar{b} = (b_{0}, \dots, b_{n - 1})$ .

Proof.
1. We define by induction PR sequences ${q_{j}}$ of rational numbers and ${I_{j}}$ of rational open intervals such that $q_{0} \in I_{0} = I$ and, for every j, $I_{j} \supseteq [I_{j + 1}]$ where $[I_{j + 1}]$ is the closure of $I_{j + 1}$ , and $q_{j + 1} \in I_{j + 1} \subseteq (q_{j} - 2^{- j}, q_{j} + 2^{- j})$ . Then we set $b = {lim}_{j} q_{j}$ which automatically guarantees that ${q_{j}}$ is fast Cauchy and hence $b \in R_{p}$ . The remaining properties of b are obtained by taking some additional care.

Let $I_{0} = I$ and $q_{0}$ be any rational number in $I_{0}$ . Assume by induction that we already have defined $q_{j}$ , $I_{j}$ for $j ⩽ n$ which satisfy the properties above for $j < n$ . Then we define $q_{n + 1}$ , $I_{n + 1}$ as follows. If the polynomial $α_{n}^{}$ is zero or has no real roots, choose $q_{n + 1}$ , $I_{n + 1}$ arbitrarily such that $I_{n} \supseteq [I_{n + 1}]$ and $q_{n + 1} \in I_{n + 1} \subseteq (q_{n} - 2^{- n}, q_{n} + 2^{- n})$ . Otherwise, use Fact 5 in Section 4 to primitive recursively find a non-empty rational open interval J such that $[J] \subseteq I_{n}$ and $[J]$ contains no real root of $α_{n}^{}$ ; then $α_{n}^{}$ is either positive on $[J]$ or negative on $[J]$ , and this alternative is checked primitive recursively. Now choose $q_{n + 1}$ , $I_{n + 1}$ as above but with the additional property $I_{n + 1} \subseteq J$ . Then the sequences ${q_{j}}$ , ${I_{j}}$ are PR and satisfy the properties specified in the previous paragraph.

Note that $b \in I_{n}$ for all n, and if $α_{n}^{}$ is non-zero then it is either positive or negative on $I_{n + 1} ∋ b$ , hence $α_{n}^{} (b) \neq 0$ ; therefore, b is transcendental over $A$ . If $α_{n}^{}$ is zero then $sign (α_{n}^{} (b)) = 0$ , otherwise $sign (α_{n}^{} (b)) = 1, 2$ depending on whether $α_{n}^{}$ is positive on $[J]$ or is negative on $[J]$ . Therefore, the function $n \mapsto sign (α_{n}^{} (b))$ is PR and hence $b \in R_{p} (α)$ .

2. Note that the construction $α \mapsto b$ in item 1 is PR in the sense that, given an index for $α \in pras (R)$ (i.e., a code of tuple of indices for PR functions representing the equality and the signature symbols, and also of the splitting function), one can primitive recursively find a π-index for b and a PR-index of the function $n \mapsto sign (α_{n}^{} (b))$ .

Let $b_{0} = b$ . Since the construction in Proposition 3 is PR, we can primitive recursively find an index of $β \in pras (R)$ with $rng (β) = A (b)$ . Since the construction in Theorem 4 is PR, we can primitive recursively find an index of $\hat{β} \in pras (R)$ with $rng (\hat{β}) = \hat{A (b)}$ .

Taking $\hat{β}$ in place of α, we primitive recursively find an index of some $b_{1}$ transcendental over $\hat{A (b_{0})}$ . It is easy to check that $b_{0}$ , $b_{1}$ are algebraically independent over $A$ and $(b_{0}, b_{1}) \in R_{p}^{[2]} (\hat{β}))$ . Iterating this process indefinitely, we obtain a desired sequence $b_{0}, b_{1}, \dots$ . □
Corollary 4.
There are PRAS-fields of any countable transcendence degree.*
Proof.
By Theorems 4(2) (for $α = ϰ$ ) and 3, any of the ordered fields $Q$ , $Q (b_{0})$ , $Q (b_{0}, b_{1})$ , … , $Q (b_{0}, b_{1}, \dots)$ is a PRAS-field. □
Remarks 2.
1. Theorem 4 and Proposition 3 imply that the algebraic closures of the fields $Q (x_{0}, \dots, x_{n})$ for every n, and of $Q (x_{0}, x_{1}, \dots)$ , are PR-constructivizable (the latter fact is a step to proving the PR-version of the Rabin theorem mentioned in Section 4).

2. From the construction of numbers $b, b_{0}, b_{1}, \dots$ in the proof Theorem 4 it follows that all these numbers are in the set PRT defined below.

An important problem is to determine whether a given concrete transcendental real (or a tuple of such reals) may be included in some PRAS-field. In general, this question seems very difficult but for some concrete numbers (including the Euler number e and the circle number π) the solution follows from results of Goodstein’s monograph [14].

By a PR-Cauchy sequence we mean a PR sequence ${s_{i}}$ of rationals such that for some PR function N it holds: $\forall k \forall m, n ⩾ N (k) (| s_{m} - s_{n} | < 2^{- k})$ . Since further results of this section essentially depend on notions and results of the appendix to [14], we make some of our notations closer to those in [14]. Let ${P_{r}}_{r ⩾ 0}$ be the natural numbering of non-zero rational polynomials defined by $P_{r} = ϰ_{f (r)}^{}$ where $ϰ^{}$ is the numbering of $Q (x)$ from Section 3 and f is the PR function enumerating the PR set $n ∣ ϰ_{n}^{*} \neq 0$ in the increasing order. Definition 5 ([14]).

By a PR transcendental real we mean a PR-Cauchy sequence ${s_{i}}$ such that for some PR functions k, N we have: $| P_{r} (s_{n}) | > 2^{k (r)}$ for every $n ⩾ N (r)$ . Let PRT denote the set of limits of PR transcendental reals.

Lemma 1.

The set of limits of PR-Cauchy sequences coincides with $R_{p}$ .

If ${s_{i}}$ and ${q_{i}}$ are PR-Cauchy sequences then so are also ${s_{i} + q_{i}}$ , ${s_{i} - q_{i}}$ , and ${s_{i} \cdot q_{i}}$ .

If ${s_{i}}$ is a PR-Cauchy sequence then so is also ${P_{r} (s_{i})}$ , even uniformly in r, i.e., there is a binary PR function M such that $| P_{r} (s_{i}) - P_{r} (s_{j}) | < 2^{- k}$ for all $i, j ⩾ M (r, k)$ .

Every number in PRT is transcendental.

Proof.
Items 1–3 are easy consequences of Proposition 4.1 and Theorem 4.2 in [8]. Item 4 (observed in the appendix of [14]) is obvious. □
Theorem 5.
We have $PRT \subseteq R_{p} (ϰ)$ , hence every number from PRT may be included in some PRAS-field.
Proof.
Let ${s_{i}}$ be a PR transcendental real; for the first assertion, we have to show that $s = {lim}_{i} s_{i}$ is in $R_{p} (ϰ)$ . By Theorem 3, it suffices to show that the sign of the value $P_{r} (s)$ may be found primitive recursively. Since s is transcendental by Lemma 1(4), we get the dichotomy: $P_{r} (s) > 0$ or $P_{r} (s) < 0$ . Therefore, it suffices to check that $P_{r} (s) > 0$ is a PR unary relation on r.

By Definition 5, there are PR functions k, N such that $| P_{r} (s_{n}) | > 2^{- k (r)}$ for every $n ⩾ N (r)$ . By Lemma 1, there is a binary PR function M such that $| P_{r} (s_{i}) - P_{r} (s_{j}) | < 2^{- k}$ for all $i, j ⩾ M (r, k)$ . For the number $f (r) = max (N (r), M (r, k (r) + 2))$ we then have $| P_{r} (s_{f (r)}) | > 2^{- k (r)}$ and $| P_{r} (s) - P_{r} (s_{f (r)}) | < 2^{- k (r) - 1}$ (because $s = {lim}_{i} s_{i}$ ). Therefore, $P_{r} (s) > 0$ iff $P_{r} (s_{f (r)}) > 0$ . But f is a PR function, so $P_{r} (s) > 0$ is a PR relation.

For the second assertion, let $s \in PRT$ . Then $s \in R_{p} (ϰ)$ by the first assertion. Since $Q$ is a PRAS-field, by Theorem 3 so is also the ordered field $Q (s)$ that contains s. □
Corollary 5.
The ordered fields $Q (e)$ , $Q (π)$ , $\hat{Q (e)}$ , and $\hat{Q (π)}$ are PRAS-fields.
Proof.
In the appendix of [14] it is proved that $e, π \in PRT$ , hence $Q (e)$ and $Q (π)$ are PRAS-fields by the proof of Theorem 5. By Corollary 2(2), $\hat{Q (e)}$ and $\hat{Q (π)}$ are also PRAS-fields. □
Remark 4.
Again, the results of this section are more intricate than their computable analogues in [34]. We illustrate this by the ordered field $Q (e, π)$ . By the general fact in [34] mentioned in the beginning of Section 6, $Q (e, π)$ is a computable ordered field with splitting (the computable analogue of PRAS-fields). But we do not know whether it is a PRAS-field. The point is that it is open whether e and π are algebraically dependent (a long-standing open question in number theory). If yes, then $Q (e, π)$ is a PRAS field by Corollary 2(ii). If not, a serious additional investigation is still needed to see whether $π \in R_{p} (\hat{α})$ where α is a PRAS-constructivization of $Q (e)$ .

8. PR linear algebra

Here we show PR computability of some problems of linear algebra frequently used in applications.

As follows from an old result of F. Rellich (see e.g. [41]), the spectral problems discussed in this section are non-computable if we consider them, as is usually done in the books on linear algebra, for arbitrary real or complex matrices, and understand computability in the sense of A. Turing. This leads to computational instabilities when these problems are solved numerically, which was our original motivation to identify restricted computable versions of these problems. We will show that these problems are PR for matrices over any PRAS-field.

Recall that spectrum of any complex matrix from $M \in M_{n} (C)$ is a sequence $spec (M) = (λ_{1}, \dots, λ_{n})$ of all eigenvalues of M (each eigenvalue occurs in the sequence several times, according to its multiplicity). The following fact immediately follows from Theorem 2 and Proposition 12.

Proposition 19.
Let $A$ be a PRAS-field. Given n and a symmetric matrix $M \in M_{n} (\hat{A})$ , one can primitive recursively find a spectrum of M uniformly in n.

As is well known, all eigenvalues of any symmetric real matrix are real. Spectral decomposition of such a matrix $A \in M_{n} (R)$ is a pair $((λ_{1}, \dots, λ_{n}), (v_{1}, \dots, v_{n}))$ where $λ_{1} ⩽ \dots ⩽ λ_{n}$ is the non-decreasing spectrum of A and $v_{1}, \dots, v_{n}$ is a corresponding orthonormal basis of eigenvectors, i.e. $A v_{i} = λ_{i} v_{i}$ for $i = 1, \dots, n$ .
Proposition 20.
Let $A$ be a PRAS-field. Given n and a symmetric matrix $A \in M_{n} (\hat{A})$ , one can primitive recursively find a spectral decomposition of A uniformly in n.
Proof.
By Proposition 19, we can primitive recursively compute the increasing sequence $μ_{1} < \dots < μ_{m}$ of all distinct roots of ${ch}_{A}$ and the corresponding multiplicities $r_{1}, \dots, r_{m}$ . Using the Gauss method, we then primitive recursively find, for each $j = 1, \dots, m$ , a basis $(w_{1}^{j}, \dots, w_{r_{j}}^{j})$ for the eigenspace ${x ∣ (μ_{j} \cdot I_{n} - A) x = 0}$ corresponding to $μ_{j}$ . Applying the Gram–Schmidt orthonormalisation process $(w_{1}, \dots, w_{r}) \mapsto (v_{1}, \dots, v_{r})$ which is (with simplified indices) given by the recurrent formulas $\begin{matrix} v_{1} = w_{1}, v_{k + 1} = w_{k + 1} - \sum_{i = 1}^{k} \frac{w_{k + 1} \cdot v_{i}}{| v_{i} |^{2}}, \end{matrix}$ we primitive recursively obtain an orthonormal basis $(v_{1}^{j}, \dots, v_{r_{j}}^{j})$ for this eigenspace. Putting together the orthonormal bases for all j, we obtain a desired orthornormal basis $(v_{1}, \dots, v_{n})$ for the whole space. Of course, the orthonormal basis of eigenvectors is not unique. It is only important that some such basis may be found primitive recursively. □

The last proposition may be extended to a natural class of complex matrices. A matrix $A \in M_{n} (C)$ is normal if $A \cdot A^{} = A^{} \cdot A$ where $A^{} = ({\bar{a}}_{j, i})$ is the conjugate matrix* for $A = (a_{i, j})$ , and A is self-adjoint if $A^{} = A$ . Note that every symmetric real matrix is self-adjoint, and every self-adjoint matrix is normal. It is known that for any eigenvalue μ of a normal matrix A the multiplicity of μ coincides with the dimension of the corresponding eigenspace, and this eigenspace has a basis consisting of eigenvectors. The next extension of Proposition 20 is thus proved by the same argument.
Proposition 21.
Let* $A$ be a PRAS-field. Given n and a normal matrix $A \in M_{n} (\overline{A})$ , one can primitive recursively find a spectral decomposition of A uniformly in n.

By a matrix pencil we mean a pair $(A, B)$ (often written in the form $μ A - B$ ) of real non-degenerate symmetric matrices such that A is positive definite (i.e., all of its eigenvalues are positive). By spectral decomposition of such a pencil we mean a tuple $\begin{matrix} ((λ_{1}, \dots, λ_{n}), (v_{1}, \dots, v_{n}), (μ_{1}, \dots, μ_{n}), (w_{1}, \dots, w_{n})) \end{matrix}$ such that $((λ_{1}, \dots, λ_{n}), (v_{1}, \dots, v_{n}))$ and $((μ_{1}, \dots, μ_{n}), (w_{1}, \dots, w_{n}))$ are spectral decompositions of the symmetric matrices A and $D^{} L^{} B L D$ respectively, where L is the matrix formed by vectors $v_{1}, \dots, v_{n}$ written as columns, $L^{}$ is the transposition of L, and $D = diag {\frac{1}{\sqrt{λ_{1}}}, \frac{1}{\sqrt{λ_{2}}}, \dots, \frac{1}{\sqrt{λ_{n}}}}$ .
Proposition 22.
Let* $A$ be a PRAS-field. Given n and a matrix pencil $(A, B)$ with matrices A, B in $M_{n} (\hat{A})$ , one can primitive recursively find a spectral decomposition of $(A, B)$ uniformly in n.
Proof.
First we find a spectral decomposition $((λ_{1}, \dots, λ_{n}), (v_{1}, \dots, v_{n}))$ of A using the algorithm of Proposition 20. Then we primitive recursively find the matrix $D^{} L^{} B L D$ . Applying the algorithm of Proposition 20 to this matrix, we compute the remaining items $(μ_{1}, \dots, μ_{n})$ , $(w_{1}, \dots, w_{n})$ . Note that $(μ_{1}, \dots, μ_{n})$ coincides with the spectrum of (in general, non-symmetric) matrix $A^{- 1} B$ . □

An important normal form for square matrices over an algebraically closed field is the Jordan normal form. The next proposition gives a sufficient condition for PR-computability of this form similar to those given above. The proof, which is obtained by inspecting any standard algorithm solving this problem written with all details (as e.g. the algorithm in Section 18 of [12]), is omitted. Proposition 23.
Let $A$ be a PRAS-field. Given n and a matrix $M \in M_{n} (\overline{A})$ , one can primitive recursively and uniformly in n find a Jordan normal form $J \in M_{n} (\overline{A})$ for M and a non-degenerate matrix $C \in M_{n} (\overline{A})$ with $M = C^{- 1} J C$ .

9. PR analysis

Computable analysis, developed by many people, was systematized in [40]. A central notion of computable analysis (due to A. Turing) is the notion of a computable (partial) function on the reals and on more complex spaces. In this section we attempt to develop a small part of PR analysis. Our approach is somewhat related to earlier works [13,14].

For any $n ⩾ 0$ , let $ψ^{(n)}$ be the computable numbering of n-ary PR operators on the Baire space $N = N^{N}$ from the end of Section 2. An example of unary PR operator is the function $q \to \tilde{q}$ defined in Section 6. This operator is clearly a retraction of $N$ onto $Ca$ , i.e. $\tilde{q} \in Ca$ for each $q \in N$ and $\tilde{q} = q$ for $q \in Ca$ . Recall that, by the definition, $q \in Ca$ iff $ϰ \circ q$ is fast Cauchy. Another example is the function $q \to q^{'}$ defined at the end of Section 6. Note that every PR operator on $N$ is total and the class of such operators is closed under composition.

We proceed with defining PR functions on the reals. Similarly to the ideas of computable analysis, we can use a suitable surjection $γ : N \to R$ to transfer primitive recursiveness on $N$ to that on $R$ (and then, may be, to more complex spaces). Namely, we define $γ (p) = {lim}_{n} ϰ (\tilde{p} (n))$ and call this γ the Cauchy representation of $R$ . Note that γ is an admissible representation in the sense of [40], and it is computably equivalent to the Cauchy representation of $R$ defined in [40].

Definition 6.
A partial function $f : \subseteq R^{n} \to R$ is called PR if there is a PR function $g : N^{n} \to N$ (called a γ-realizer of f) such that $f (γ (p_{1}), \dots, γ (p_{n})) = γ (g (p_{1}, \dots, p_{n}))$ for all $p_{1}, \dots, p_{n} \in N$ .

Although this definition looks similar to the definition of a computable partial function on the reals, there is an important difference: while in the computable case the computable realizer may be partial, the PR-realizers are always total, as any PR operator on $N$ . Clearly, the PR functions on the reals are computable, and in fact they form a very restricted subclass of the computable functions. Nevertheless, many practically important functions are PR. We illustrate similarities and differences between computable and PR functions by providing some examples.
Proposition 24.

The functions +, ·, − on $R$ (and on $C$ ) are PR.

For every polynomial $f \in R_{p} [x_{1}, \dots, x_{n}]$ , the corresponding evaluation function $f_{p} : R^{n} \to R$ is PR.

The reciprocal partial function $x^{- 1}$ on $R$ (and on $C$ ) is computable but not PR (cf. Remark 3 ).

The class of PR functions (and the class of PR partial functions) on $R$ is closed under composition.

The 0-ary total functions on $R$ coincide with the PR reals.

Let $f : \subseteq R^{n} \to R$ be a PR partial function on the reals. Then its restriction $f |_{R_{p}}$ to $R_{p}$ is τ-PR.

Proof.
1. This is proved by essentially the same argument as that in the proof of Proposition 16(1).

2. Follows from item 1.

3. The computability of the reciprocal partial function is well known (with a computable partial realizer). Suppose for a contradiction that it is PR and let g be its PR realizer (which is automatically total). Then g is computable, hence also continuous. Let $q = {2^{- i}}$ and let $r = {a_{i}}$ be the unique sequence of rationals with $g (ϰ^{- 1} \circ q) = ϰ^{- 1} \circ r$ . Since g is continuous, for a suitable n we have: for any fast Cauchy sequence $q^{'} = {q_{i}}$ of rationals with $q_{0} = 2^{- 0}, \dots$ , $q_{n} = 2^{- n}$ , the corresponding sequence $r^{'} = {a_{i}^{'}}$ of rationals with $g (ϰ^{- 1} \circ q^{'}) = ϰ^{- 1} \circ r^{'}$ , satisfies $a_{0}^{'} = a_{0}$ . Let $x = lim q^{'}$ and $y = lim (ϰ \circ \tilde{p})$ where $p = ϰ^{- 1} \circ r^{'}$ . Note that the first element of the sequence $ϰ \circ \tilde{p}$ is $a_{0}$ , and that $x^{- 1} = y$ whenever $x \neq 0$ (because g is a realizer for $^{- 1}$ ). Since $q^{'}$ and $ϰ \circ \tilde{p}$ are fast Cauchy, we have $x \in [2^{- n} - 2^{- n + 1}, 2^{- n} + 2^{- n + 1}]$ , $y \in [a_{0} - 2, a_{0} + 2]$ .

Let now $m > n$ be any integer with $2^{m} > a_{0} + 2$ , and define $q^{'} = {q_{i}}$ as follows: $q_{0} = 2^{- 0}, \dots$ , $q_{n} = 2^{- n}$ , and $q_{n + i + 1} = 2^{- m}$ . Then $x = 2^{- m}$ , hence $y = x^{- 1} = 2^{m} \notin [a_{0} - 2, a_{0} + 2]$ . A contradiction.

4. The assertion follows from the corresponding fact for realizers which are PR operators on $N$ .

5. Obvious.

6. Let g be a PR realizer for f, then $g = u$ for some $u (v_{1}, \dots, v_{n}) \in T_{n}$ (we use the notation and facts from the end of Section 2). It suffices to show that the PR function $h (k_{1}, \dots, k_{n}) = N (u (t_{k_{1}}, \dots t_{k_{n}}))$ satisfies $f (τ (k_{1}), \dots, τ (k_{n})) = τ (h (k_{1}, \dots, k_{n}))$ whenever $f (τ (k_{1}), \dots, τ (k_{n}))$ is defined. Indeed, we have: $\begin{array}{rcl} f (τ (k_{1}), \dots, τ (k_{n})) & = & f (γ (ψ (k_{1})), \dots, γ (ψ (k_{n}))) = γ (g (ψ (k_{1}), \dots, ψ (k_{n})) \\ = & g (t_{k_{1}}, \dots, t_{k_{n}}) = γ (ψ (h (k_{1}, \dots, k_{n}))) = τ (h (k_{1}, \dots, k_{n})) . \end{array}$ □
Remark 5.
PR analysis is much more intricate than computable analysis. For instance, the computable version of the basic notion of “elementary function” is straightforward but the corresponding “correct” PR analogue is far from obvious, as demonstrated in particular by the facts about the reciprocal function. Nevertheless, we guess that many important concrete functions are PR. For instance, the results in the appendix to [14] suggest that this is the case for the functions sin, cos though some additional work is needed to adjust the arguments in [14] to our context.

An important notion of computable analysis is the notion of a computable metric space. Having in mind applications in the next section, we propose the following PR versions of this notion.
Definition 7.

By a PR metric space we mean a triple $(M, d, ν)$ where $(M, d)$ is a metric space, $ν : N \to M$ is a numbering of a dense subset $M_{0} \subseteq M$ , and there is a ternary PR sequence ${q_{m, n, i}}$ of rationals such that, for all m, n, ${q_{m, n, i}}_{i}$ is fast Cauchy $d (ν_{m}, ν_{n}) = {lim}_{i} q_{m, n, i}$ .

For $α \in pra (R)$ , by an α-PR metric space we mean a triple $(M, d, ν)$ as above such that $d (ν_{m}, ν_{n}) = {\hat{α}}_{f (m, n)}$ , for a suitable binary PR function f.

With any triple $(M, d, ν)$ as above we can in the usual way associate the so-called Cauchy representation of M, i.e., the partial function $ν^{}$ from $N$ onto M as follows: $ν^{} (p) = x$ iff the sequence ${ν_{p (n)}}$ is fast Cauchy and converges to x. For every α-PR metric space $(M, d, ν)$ , the Cauchy representation is constructed more regularly. Namely, let the set $Ca = {Ca}_{ν} \subseteq N$ and the function $p \mapsto \tilde{p} = {\tilde{p}}_{ν}$ on $N$ be defined in the same way as the corresponding objects in Section 6 but with ν in place of ϰ and d in place of the usual distance function on the reals. Then again $p \mapsto \tilde{p}$ is a PR retraction from $N$ onto $Ca$ . We set $ν^{} (p) = lim (ν \circ \tilde{p})$ whenever the limit exists.
Proposition 25.

Any ϰ-PR metric space is an α-PR metric space for every* $α \in pra (R)$ .

If $(M, d, ν)$ is an α-PR metric space and $(M, d)$ is complete then $ν^{}$ is total.*

For every infinite α-PR metric space $(M, d, ν)$ there is an injective numbering $ν^{'} \equiv_{PR} ν$ , so $(M, d, ν^{'})$ is an α-PR metric space and $ν^{} \equiv_{PR} ν^{' }$ .

Every α-PR metric space is a PR metric space.

Proof.
1. This follows from $ϰ ⩽_{PR} α$ .

2. Obvious by the definition of Cauchy representation.

3. The numbering $ν^{'}$ is constructed from ν in the same way as the numbering γ is constructed from β in the proof of Proposition 1. The properties of $ν^{'}$ are obvious. Note that, say, the reduction $μ ⩽_{PR} ν$ between partial representations means that there is a unary PR operator f on $N$ such that $μ_{p} = ν_{f (p)}$ for every $p \in dom (μ)$ .

4. Let f be a binary PR function f such that $d (ν_{m}, ν_{n}) = {\hat{α}}_{f (m, n)}$ . Proposition 17(4) yields the sequence ${q_{m, n, i}}$ witnessing that $(M, d, ν)$ is a PR metric space. □

Definition 7 naturally extends to the definition of a PR function between PR metric spaces:
Definition 8.
Let $(M, d, ν)$ and $(M_{1}, d_{1}, ν_{1})$ be PR metric spaces. A partial function $f : \subseteq M \to M_{1}$ is PR if it has a PR realizer w.r.t. $ν^{}$ , $ν_{1}^{}$ , i.e., there is a unary PR operator g on $N$ such that $ν_{1}^{} (g (p)) = f (ν^{} (p))$ for every $p \in dom (ν^{})$ .

For readers’ convenience, we give examples of PR metric spaces (and normed spaces) and PR functions between them relevant to the next section; for more detailed definitions of these spaces see e.g. [35] and references therein. For any $n ⩾ 1$ , the Euclidean vector space $R^{n}$ carries the sup-norm $‖ x ‖_{\infty} = max {| x_{i} |}$ and the Euclidean norm $‖ x ‖_{2} = \sqrt{\sum x_{i}^{2}}$ ; we denote the corresponding metrics by $d_{\infty}$ and $d_{2}$ , respectively. Define the function $ϰ^{n} : N \to R^{n}$ by $ϰ^{n} (⟨ k_{1}, \dots, k_{n} ⟩) = (ϰ (k_{1}), \dots, ϰ (k_{n}))$ .

There are several natural subspaces and variations of the Euclidean spaces, in particular the space $S \subseteq R^{n \times n}$ of symmetric real matrices, the space $S_{+}$ of symmetric real positively definite matrices, and the m-dimensional unitary cube $Q = {[0, 1]}^{m}$ . They have numberings of dense subsets induced by the corresponding numbering $ν \in {ϰ^{n^{2}}, ϰ^{n}}$ , using the easy fact that the sets $ν^{- 1} (S)$ , $ν^{- 1} (S_{+})$ , and $ν^{- 1} (Q)$ are PR.

Important modifications of the Euclidean spaces are the spaces of grid functions. Consider, for any positive integer N, the uniform rectangular grid $G_{N}$ on $Q = {[0, 1]}^{m}$ defined by the points $\begin{matrix} (\frac{i_{1} - \frac{1}{2}}{2^{N}}, \frac{i_{2} - \frac{1}{2}}{2^{N}}, \dots, \frac{i_{m} - \frac{1}{2}}{2^{N}}) \end{matrix}$ where $1 ⩽ i_{1}, i_{2}, \dots$ , $i_{m} ⩽ 2^{N}$ . Let $h = 1 / 2^{N}$ be the corresponding spatial grid step and τ be a time step. Denote $G_{N}^{τ} = G_{N} \times {l τ}_{l = 1}^{L}$ , where L is the number of the time steps. We will consider the grid norms $\begin{matrix} {‖ g^{(h)} ‖}_{s} = {max}_{x \in G_{N}} | g^{(h)} (x) |, {‖ g^{(h)} ‖}_{L_{2}}^{2} = h^{m} \sum_{x \in G_{N}} ⟨ g^{(h)} (x), g^{(h)} (x) ⟩ \end{matrix}$ on the grid functions $g^{(h)} : G_{N} \to R^{n}$ and the $s L_{2}$ -norm $\begin{matrix} {‖ v^{(h)} ‖}_{s L_{2}} = {max}_{t \in {l τ}_{l = 1}^{M}} h^{m} \sum_{x \in G_{N}} ⟨ v^{(h)} (t, x), v^{(h)} (t, x) ⟩ \end{matrix}$ on the grid functions $v^{(h)} (t, x) : G_{N}^{τ} \to R^{n}$ . The numberings of dense sets (formed by the rational functions on the grids) are induced by the numbering ϰ.

We work with several functional spaces most of which are subsets of the set $C (R^{m}, R^{n}) ≃ C {(R^{m}, R)}^{n}$ of integrable continuous functions $φ : R^{m} \to R^{n}$ equipped with the $L_{2}$ -norm. In particular, we deal with the space $C (Q, R^{n}) ≃ C {(Q, R)}^{n}$ (resp. $C^{k} (Q, R^{n})$ ) of continuous (resp. k-time continuously differentiable) functions $φ : Q \to R^{n}$ equipped with the $L_{2}$ -norm $\begin{matrix} ‖ φ ‖_{L_{2}} = {(\int_{Q} {| φ (x) |}^{2} d x)}^{\frac{1}{2}}, {| φ (x) |}^{2} = ⟨ φ, φ ⟩ = \sum_{i = 1}^{n} φ_{i}^{2} (x) . \end{matrix}$ We will also use the sup-norm $\begin{matrix} ‖ φ ‖_{s} = sup_{x \in Q} | φ (x) |, ‖ f ‖_{s} = sup_{(t, x) \in [0, T] \times Q} | f (t, x) | \end{matrix}$ on $C (Q, R^{n})$ or $C ([0, T] \times Q, R^{n})$ and the $s L_{2}$ -norm $\begin{matrix} ‖ u ‖_{s L_{2}} = sup_{0 ⩽ t_{0} ⩽ T} \sqrt{\int_{Q} {| u (t_{0}, x) |}^{2} d x} \end{matrix}$ on $C ([0, T] \times Q, R^{n})$ where $T > 0$ . Whenever we want to emphasize the norm we use notation like $C_{L_{2}} (Q, R^{n})$ , $C_{s} (Q, R^{n})$ or $C_{s L_{2}} ([0, T] \times Q, R^{n})$ .

Associate with any rational grid function $f_{N} : G_{N} \to Q$ the continuous extension ${\tilde{f}}_{N} : Q \to R$ of f obtained by piecewise-linear interpolation on each coordinate, and similarly for grid functions $G_{N}^{τ} \to Q$ . Such interpolations are known as multilinear interpolations. Note that the restriction of ${\tilde{f}}_{N}$ to any grid cell is a polynomial of degree m. The extensions ${\tilde{f}}_{N}$ induce a countable dense set in $C (Q, R^{n})$ (or $C ([0, T] \times Q, R^{n})$ ) with any of the three norms induced by ϰ and natural numberings of the grids $G_{N}$ for all $N ⩾ 1$ and of the grids $G_{N}^{τ}$ for all $N ⩾ 1$ and rational τ.

Along with the mentioned norms, their A-modifications, for a given matrix A, are useful. In particular, the A-modification of the $L_{2}$ -norms is defined by $\begin{matrix} ‖ φ ‖_{A, L_{2}} = \sqrt{\int_{Q} ⟨ A φ, φ ⟩ d x} \end{matrix}$ while the A-modification of the $s L_{2}$ -norms is defined by $\begin{matrix} ‖ u ‖_{A, s L_{2}} = sup_{0 ⩽ t_{0} ⩽ T} \sqrt{\int_{Q} ⟨ A u (t_{0}, x), u (t_{0}, x) ⟩ d x}, \end{matrix}$ and in a similar way for the grid norms. Proposition 26.

The spaces* $(R^{n}, d_{\infty}, ϰ^{n})$ and $(R^{n}, d_{2}, ϰ^{n})$ are ϰ-PR metric spaces uniformly in n.

The spaces S, $S_{+}$ , Q and the spaces of grid functions are ϰ-PR metric spaces uniformly in their dimensions.

For any $n ⩾ 1$ , the spaces $C_{s} (Q, R^{n})$ , $(C_{L_{2}} (Q, R^{n})$ , and $C_{s L_{2}} ([0, T] \times Q, R^{n})$ are ϰ-PR metric spaces uniformly in n.

Let $α \in pras (R)$ and let A be a symmetric matrix in $M_{n} (\hat{A})$ . Then the spaces from (3), equipped with the A-modified metrics, are α-PR metric spaces uniformly in n.

The restriction $φ \mapsto φ |_{G}$ is a PR function from $C_{s} (Q, R^{n})$ to ${(R^{n})}^{G}$ .

The operator $f \mapsto \tilde{f}$ is a PR function from ${({(R^{n})}^{G})}_{s}$ to $C_{L_{2}} (Q, R^{n})$

Proof.
Items (1,2) are obvious from the definition.

3. The proof is a straightforward calculation which shows that the distance between elements of the dense subsets is an algebraic real which is uniformly primitive recursively computable. Item (6) is considered similarly, only now calculations are made within the PRAS-field $\hat{A}$ .

Items (4,5) follow from the definitions and well-known properties of the multilinear interpolations. □

10. PR solutions of PDE

Here we apply the above-developed theory to investigate the question when the solution operators for hyperbolic symmetric systems of PDE are PR. This complements the results in [34] and [36] where computability and bit complexity of such operators were examined.

For simplicity we discuss here only the Cauchy initial value problem (the boundary value problems are considered similarly) stated as follows: $\begin{matrix} (1) & \{\begin{matrix} A \frac{\partial u}{\partial t} + \sum_{i = 1}^{m} B_{i} \frac{\partial u}{\partial x_{i}} = f (t, x_{1}, \dots, x_{m}), t ⩾ 0, \\ u |_{t = 0} = φ (x_{1}, \dots, x_{m}) . \end{matrix} \end{matrix}$ Here $A = A^{*} > 0$ and $B_{i} = B_{i}^{*}$ are non-degenerate symmetric $n \times n$ -matrices, $t ⩾ 0$ , $x = (x_{1}, \dots, x_{m}) \in Q = {[0, 1]}^{m}$ , $φ : Q \to R^{n}$ , $f : [0, + \infty) \times Q ⇀ R^{n}$ , and $u : [0, + \infty) \times Q ⇀ R^{n}$ is a partial function acting on the domain $H \subseteq [0, + \infty) \times Q$ of existence and uniqueness of the Cauchy problem (1). The set H is known to be (see e.g. [36] for references and additional information) the intersection of semi-spaces $\begin{matrix} t ⩾ 0, x_{i} - μ_{\max}^{(i)} t ⩾ 0, x_{i} - 1 - μ_{\min}^{(i)} t ⩽ 0 (i = 1, \dots, m) \end{matrix}$ of $R^{m + 1}$ where $μ_{\min}^{(i)}$ , $μ_{\max}^{(i)}$ are the minimum and maximum of the eigenvalues of $A^{- 1} B_{i}$ .

Below we formulate sufficient conditions for PR-computability of the solution operator for (1) by putting some restrictions on matrices $A, B_{1}, \dots, B_{m}$ and functions φ, f. Matrix coefficients are usually in a real closed PRAS-field $A$ . The results below are PR analogues of the corresponding results in [35,36]. Most of the technical details are the same as in those papers, so we only give short proof sketches pointing to the new details.

We start with formulating two auxiliary facts. The next immediate corollary of Propositions 20 and 22 shows that we can primitive recursively compute H. Our algorithms for solving the Cauchy problem are for technical reasons presented only for the case when H satisfies the condition $μ_{\min}^{(i)} < 0 < μ_{\max}^{(i)}$ for all $i = 1, \dots, m$ (which implies that H is compact); this condition often holds for natural physical systems.

Proposition 27.
Let $A$ be a PRAS-field. Given $m, n ⩾ 1$ and $A, B_{1}, \dots, B_{m} \in M_{n} (\hat{A})$ as in ( 1 ), one can compute $(μ_{max}^{(1)}, \dots, μ_{max}^{(m)}, μ_{min}^{(1)}, \dots, μ_{min}^{(m)})$ and check the condition $μ_{\min}^{(i)} < 0 < μ_{\max}^{(i)}$ for all $i = 1, \dots, m$ primitive recursively uniformly in m, n. Thus, the algorithm finds the domain H satisfying the condition above, or reports on the absence of such a domain.

We also need another immediate corollary of Propositions 20 and 22 about the spectral decomposition $((λ_{1}, \dots, λ_{n}), (v_{1}, \dots, v_{n}))$ of the matrix A as in (1). Let $λ_{max}$ , $λ_{min}$ be respectively the maximum and minimum of $λ_{1}, \dots, λ_{n}$ . Let L be the orthonormal matrix formed by vectors $v_{1}, \dots, v_{n}$ written in columns, so $L^{} A L = Λ = diag {λ_{1}, λ_{2}, \dots, λ_{n}}$ , and let $D = Λ^{- \frac{1}{2}}$ . For each $i = 1, \dots, m$ , let $((μ_{1}^{(i)}, \dots, μ_{n}^{(i)}), (w_{1}^{i}, \dots, w_{n}^{i}))$ be the spectral decomposition of the symmetric matrix $D^{} L^{} B_{i} L D$ . Let $μ_{max}^{(i)}$ , $μ_{min}^{(i)}$ be respectively the maximum and minimum of $μ_{1}^{(i)}, \dots, μ_{n}^{(i)}$ . Let $M_{i} = diag {μ_{1}^{(i)}, \dots, μ_{n}^{(i)})}$ and $K_{i}$ be the orthonormal matrix formed by vectors $w_{1}^{i}, \dots, w_{n}^{i}$ written in columns, so $K_{i}^{} D^{} L^{} B_{i} L D K_{i} = M_{i}$ . Let $T_{i} = L D K_{i}$ for each $i = 1, \dots, m$ .
Proposition 28.
Let $A$ be a PRAS-field. Given $m, n ⩾ 1$ and $A, B_{1}, \dots, B_{m} \in M_{n} (\hat{A})$ as in ( 1 ), one can primitive recursively uniformly in m, n compute the quantities $A^{- 1}$ , $T_{i}$ , $T_{i}^{- 1}$ , $λ_{max}$ , $λ_{min}$ , $μ_{max}^{(i)}$ , $μ_{min}^{(i)}$ , $μ_{k}^{(i)}$ ( $i = 1, \dots, m$ , $k = 1, \dots, n$ ) specified above.

Now we are able to formulate our results about PR-computability of the Cauchy problem. The last proposition contains all information used in the Godunov difference scheme which in the central part of our algorithm. All details of the algorithm are given in [36]. The next result is a PR-version of Theorem 5.2 in [34] (though Theorem 5.2 was about the boundary-value problem). Moreover, for notation simplicity we stick to the case $f \equiv 0$ , as in [36].
Theorem 6.
Let $A$ be a PRAS-field and let $M, p ⩾ 2$ be integers. Then the solution operator $(A, B_{1}, \dots, B_{m}, φ) \mapsto u$ for ( 1 ) is a PR-computable function (uniformly in m, n) from $S_{+} \times S^{m} \times C_{s}^{p + 1} (Q, R^{n})$ to $C_{s L_{2}}^{p} (H, R^{n})$ where S and $S_{+}$ are respectively the sets of all symmetric and symmetric positively definite matrices from $M_{n} (\hat{A})$ , $‖ \frac{\partial φ}{\partial x_{i}} ‖_{s} ⩽ M$ and $‖ \frac{\partial^{2} φ}{\partial x_{i} \partial x_{j}} ‖_{s} ⩽ M$ for $i, j = 1, 2, \dots, m$ .
Proof.
We first make precise computations as in Propositions 27 and 28. With these quantities at hand, we repeat computations with the Godunov scheme as in Section 5.2. of [34]. Namely, we primitive recursively transform any given sequence ${φ_{k}}$ of grid functions $φ_{k} : G_{i_{k}} \to Q^{n}$ such that their multilinear interpolations ${{\tilde{φ}}_{k}}$ form a fast Cauchy sequence converging in $C_{s} (Q, R^{n})$ to φ, to a fast Cauchy sequence converging in $C_{s L_{2}}^{p} (H, R^{n})$ to the solution of the Cauchy problem. For any k we first compute the time step $τ_{k}$ as in Lemma 4.4 of [35]; this computation is PR. Then we compute the grid function $υ_{k} : G_{i_{k}}^{τ} \to A^{n}$ by the algorithm of Godunov’s scheme; these computations are performed precisely within the field $\hat{A}$ and they are PR since the involved metric spaces are α-PR (see Propositions 26 and 25(1)).

In this way, we primitive recursively transform any given sequence ${φ_{k}}$ to the sequence ${υ_{k}}$ . As shown in Sections 5.2 and 5.3 of [34], the corresponding sequence ${{\tilde{υ}}_{k}}$ of interpolations satisfies $‖ {\tilde{υ}}_{k} - u ‖_{s L_{2}} ⩽ c \cdot 2^{- k}$ where c is a constant depending only on $A, B_{1}, \dots, B_{n}, M$ . Moreover, the estimates in Sections 5.2 and 5.3 of [35] show that c is also computed primitive recursively. Let m satisfy $c < 2^{m}$ , then the m-shift of ${{\tilde{υ}}_{k}}$ is the desired fast Cauchy PR sequence of approximations to the solution of (1). □

For fixed $A, B_{1}, \dots, B_{m} \in M_{n} (\hat{A})$ , Theorem 6 of course implies PR-computability of the solution operator $φ \mapsto u$ for (1). The next result (which is a PR-version of Theorem 5.1 in [34]) shows that the assumption $A, B_{1}, \dots, B_{m} \in M_{n} (\hat{A})$ may be weakened to $A, B_{1}, \dots, B_{m} \in R_{p}$ .
Theorem 7.
Let $M, p ⩾ 2$ be integers and $A, B_{1}, \dots, B_{m} \in M_{n} (R_{p})$ be fixed matrices satisfying the conditions in ( 1 ) such that $μ_{\min}^{(i)} < 0 < μ_{\max}^{(i)}$ for all $i = 1, \dots, m$ . Then the solution operator $φ \mapsto u$ for ( 1 ) is a PR-computable function (uniformly in m, n) from $C_{s}^{p + 1} (Q, R^{n})$ to $C_{s L_{2}}^{p} (H, R^{n})$ ,whenever φ satisfies the conditions $‖ \frac{\partial φ}{\partial x_{i}} ‖_{s} ⩽ M$ and $‖ \frac{\partial^{2} φ}{\partial x_{i} \partial x_{j}} ‖_{s} ⩽ M$ for $i, j = 1, 2, \dots, m$ .
Proof.
All the quantities from Propositions 27 and 28 are fixed elements of $R_{p}$ because this field is real closed by Proposition 16(4). With these data at hand, all computations in the Godunov scheme are made within $R_{p}$ using only the operations +, ·, −, hence these computations are τ-PR by Proposition 16(1) where τ is the numbering of $R_{p}$ . Thus, the grid functions $υ_{k}$ take now values in $R_{p}$ uniformly in k. In fact, we can work directly with the corresponding fast Cauchy PR sequences of rationals, and the family of all such sequences is uniformly PR, hence we can primitive recursively compute arbitrarily precise rational approximations to the grid functions $υ_{k}$ . □
Remark 6.
Let $n_{A}, n_{1}, \dots, n_{m}$ be the cardinalities of spectra of A and of the matrix pencils $μ A - B_{1}, \dots, μ A - B_{m}$ , resp. Theorem 5.3 in [34] (formulated there also for $f = 0$ ) states that the operator $(A, B_{1}, \dots, B_{m}, n_{A}, n_{1}, \dots, n_{m}, φ) \mapsto u$ sending any sequence $A, B_{1}, \dots, B_{m}$ of symmetric real matrices (with some restrictions similar to those in Theorem 6) such that the matrix pencils $μ A - B_{i}$ have no zero eigenvalues, to the solution of (1), is a computable partial function from the space $S_{+} \times S^{m} \times N^{m + 1} \times C_{s}^{p + 1} (Q, R^{n})$ to $C_{s L_{2}}^{p} (H, R^{n})$ . The PR-version of this theorem would give just its strengthening to the claim that the operator is PR. Unfortunately, the proof in [35] does not straightforwardly yield this strengthening because it first computes “good enough” rational approximations to $A, B_{1}, \dots, B_{m}$ but this computation makes use of the unbounded search.

We conclude this section with the following PR-version of Theorem 2 in [36]. Note that formulation is broader than in [36] because now the algorithm is uniform on m, n, a and works with numbers beyond algebraic ones. Theorem 8.
Let $A$ be a PRAS-field. Given integers $m, n, a ⩾ 1$ , matrices $A, B_{1}, \dots, B_{m} \in M_{n} (\hat{A})$ , and rational functions $φ_{1}, \dots, φ_{n} \in \hat{A} (x_{1}, \dots, x_{m})$ , $f_{1}, \dots, f_{n} \in \hat{A} (t, x_{1}, \dots, x_{m})$ as in ( 1 ), one can primitive recursively uniformly in m, n, a compute a rational $T > 0$ with $H \subseteq [0, T] \times Q$ , a spatial rational grid step h dividing 1, a time grid step τ dividing T and an h, τ-grid function $v : G_{N}^{τ} \to \hat{A}$ such that $‖ u - \tilde{υ ∣_{H}} ‖_{s L_{2}} < a^{- 1}$ , where $\tilde{υ ∣_{H}}$ is the multilinear interpolation of the restriction of the grid function υ to H.
Proof.
The proof is an easy modification of the proof of Theorem 2 in [36]. First we use Propositions 27 and 28 to primitive recursively compute input data for the difference scheme algorithm. Then we use the algorithm of Section 4.1 in [36] to compute the space and time grid steps h, τ which guarantee the estimate $‖ u - \tilde{υ ∣_{H}} ‖_{s L_{2}} < a^{- 1}$ (for fixed parameters this algorithm works in polynomial time but uniformity requires a bit higher complexity). Then we use the algorithm of Godunov’s scheme which is written in detail in [36] as an explicit sequence of matrix computation which are precise computations within the field $\hat{A}$ . The results of the current paper show that these computations are PR. Note that the resulting grid function $υ : G_{N}^{τ} \to A^{n}$ takes values in $A$ . If needed, Proposition 17(4) may be used to primitive recursively compute a rational-valued grid function with the same precision estimate. □

11. Conclusion

Papers [34–36], and also this paper, is a mix of symbolic algorithms (which aim to find precise solutions), and approximate algorithms (which aim to find “good enough” approximations to precise solutions). The symbolic algorithms implemented e.g. in computer algebra systems correspond well to computations on discrete structures (with mathematical foundations in the classical computability and complexity theory). The approximate algorithms included in many numerical mathematics packages correspond well to computations on continuous structures (with mathematical foundations in the field of computability and complexity in analysis).

The fast progress of computation theory in the last decades made informal descriptions of several algorithms in standard textbooks in algebra and analysis insufficient and sometimes even incorrect. They typically remain correct when interpreted in countable discrete structures like those in Section 3, though a finer distinction between general computability and feasible computability is desirable. Some algorithms interpreted in continuous structures (like the real or complex numbers) become even incorrect (see examples in Section 8); it seems desirable to add corresponding comments (which mention the computable analysis approach) in the next editions of such textbooks.

11.1. Some open problems

We hope that the present paper demonstrates that PR computations is a natural next step in the investigation of this interaction because it provides a natural borderline between problems in algebra and analysis computable in principle and feasible problems. Although PR functions were thoroughly investigated in computability theory and proof theory, their study in computable structure theory and computable analysis seems still in the very beginning. There are many natural open questions about PR and more feasible computations, e.g.:

Is there a PR field $(B, β)$ such that the property of being a reducible polynomial is $β^{*}$ -PR but $(B, β)$ does not have PR splitting?

Is there a PR ordered subfield of $R$ which is not PR-Archimedean?

Is the algebraic closure of any PR field PR-constructivizable?

Is there a PR-constructive algebraically closed field without PR root-finding?

Is there $α \in pra (R)$ such that $\hat{α} \notin pras (R)$ ?

Describe the degree spectrum of the ordered field $R_{p}$ .

Is the field $Q (e, π)$ a PRAS-field?

Is there a PTIME-presentable ordered field of reals which contains a transcendental number?

Are the functions sin, cos on $R$ PR-computable?

Footnotes

Acknowledgements

The authors thank Pavel Alaev, Sergey Goncharov, Valentina Harizanov, Peter Hertling, Iskander Kalimullin, Julia Knight, Russell Miller, Andrey Morozov, and Xizhong Zheng for useful discussions and bibliographical hints.

This work is supported by Mathematical Center in Akademgorodok under agreement No. 075-15-2022-281 with the Ministry of Science and Higher Education of the Russian Federation.

List of the main abbreviations and notations

References

P.E.

Alaev and

V.L.

Selivanov, Polynomial-time presentations of algebraic number fields (extended abstract), in: Proceedings of the Conference Computability in Europe,

Manea,

Miller and

Novotka, eds, LNCS, Vol. 10936, Springer, Berlin, 2018.

P.E.

Alaev and

V.L.

Selivanov, Fields of algebraic numbers computable in polynomial time I, Algebra and Logic 58(6) (2019), 673–705, (Russian, there is an English translation). doi:10.33048/alglog.2019.58.601.

Basu,

Pollack and

Roy, Algorithms in Real Algebraic Geometry, Springer, Heidelberg, 2006.

Bazhenov,

Downey,

Kalimullin and

Melnikov, Foundations of online structure theory, Bulletin of Symbolic Logic 25(2) (2019), 141–181. doi:10.1017/bsl.2019.20.

Borodin and

El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998.

Bournez,

Graça and

Pouly, Solving analytic differential equations in polynomial time over unbounded domains, in: Mathematical Foundations of Computer Science 2011, Lecture Notes in Comput. Sci., Vol. 6907, Springer, Heidelberg, 2011, pp. 170–181. doi:10.1007/978-3-642-22993-0_18.

D.A.

Cenzer and

J.B.

Remmel, Polynomial-time versus recursive models, Ann. Pure Appl. Logic 54(1) (1991), 17–58. doi:10.1016/0168-0072(91)90008-A.

Chen,

Su and

Zheng, Primitive recursive real numbers, Mathematical Logic Quarterly 53(4/5) (2007), 365–380. doi:10.1002/malq.200710005.

Y.L.

Ershov, Numbered fields, in: Proc. 3-rd Intern. Congr. for Logic, Methodology and Philosophy of Science, Amsterdam, 1967, 1968, pp. 31–35.

10.

Y.L.

Ershov and

S.S.

Goncharov, Constructive Models, Scientific Book, Novosibirsk, 1999, (in Russian, there is an English Translation).

11.

Fröhlich and

J.C.

Shepherdson, Effective procedures in field theories, Philos. Trans. London Roy. Soc. 248(950) (1956), 407–432. doi:10.1098/rsta.1956.0003.

12.

I.M.

Gelfand, Lectures on Linear Algebra, Interscience Pulishers, New York, 1963.

13.

Gomaa, Algebraic characterizations of computable analysis real functions, Int. J. Unconv. Comput. 7(4) (2011), 245–272.

14.

R.L.

Goodstein, Recursive Analysis, North Holland, Amsterdam, 1961.

15.

Grigorieff, Every recursive linear ordering has a copy in DTIMESPACE(n, log(n)), J. Symb. Log. 55(1) (1990), 260–276. doi:10.2307/2274966.

16.

Hertling, The set of primitive recursive reals is a real closed field (private communication).

17.

I.S.

Kalimullin and

Miller, Primitive recursive fields and categoricity, Algebra and Logic 58(1) (2–19) (2019), 132–138, (Russian, there is an English translation).

18.

Kawamura, Lipschitz continuous ordinary differential equations are polynomial-space complete, Computational Complexity 19(2) (2010), 305–332. doi:10.1007/s00037-010-0286-0.

19.

Kawamura,

Steinberg and

Thies, Parameterized complexity for uniform operators on multidimensional analytic functions and ODE solving, in: Proc 25th Int. Workshop on Logic, Language, Information, and Computation (WOLLIC), 2018, pp. 223–236. doi:10.1007/978-3-662-57669-4_13.

20.

Kawamura,

Steinberg and

Ziegler, On the computational complexity of the Dirichlet problem for Poisson’s equation, Mathematical Structures in Computer Science 27(8) (2017), 1437–1465. doi:10.1017/S096012951600013X.

21.

N.G.

Khisamiev, Non-constructivizability of some ordered fields of real numbers, Siberian Mathematical Journal 28(5) (1987), 193–195.

22.

Koswara,

Pogudin,

Selivanova and

Ziegler, Bit-complexity of solving systems of linear evolutionary partial differential equations, in: Proc. 16th International Computer Science Symposium in Russia, LNCS, Vol. 12730, pp. 223–241.

23.

Koswara,

Selivanova and

Ziegler, Computational complexity of real powering and improved solving linear differential equations, in: LNCS, Vol. 11532, 2019.

24.

Loos, Computing in algebraic extensions, in: Computer Algebra: Symbolic and Algebraic Computations, Springer-Verlag, 1982, pp. 115–138. doi:10.1007/978-3-7091-3406-1_9.

25.

E.W.

Madison, A note on computable real fields, J. Symbolic Logic 35(2) (1970), 239–241. doi:10.2307/2270515.

26.

Mahler, An inequality for the discriminant of a polynomial, Michigan Mathematical Journal 11 (1964), 257–262.

27.

A.I.

Mal’cev, Constructive algebras, in: The Metamathematics of Algebraic Systems, Uspechi Mat. Nauk, Vol. 16, North Holand, Amsterdam, 1961, pp. 3–60, in Russian, English translation, 1971, p. 148–214.

28.

A.I.

Mal’cev, Algorithms and Recursive Functions, Fizmatgiz, Moscow, 1964, (Russian, English translation: Wolters-Noordhoff, 1970.).

29.

Miller, Is it harder to factor a polynomial or to find a root?, Transactions of the American Mathematical Society 362(10) (2010), 5261–5281. doi:10.1090/S0002-9947-2010-04918-9.

30.

Miller and

Ocasio Gonzalez, Degree spectra of real closed fields, Archive for Mathematical Logic 58 (2019), 387–411. doi:10.1007/s00153-018-0638-z.

31.

M.O.

Rabin, Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc. 95(2) (1960), 341–360. doi:10.1090/S0002-9947-1960-0113807-4.

32.

Selivanov and

Selivanova, Primitive recursive ordered fields and some applications, in: CASC 2021,

Boulier et al., eds, LNCS, Vol. 12865, 2021, pp. 353–369.

33.

V.L.

Selivanov, On a class of reducibilities in recursion theory, Probabilistic Methods and Cybernetics, Kazan University 18 (1982), 83–101, (Russian).

34.

Selivanova and

Selivanov, Computing solution operators of boundary-value problems for some linear hyperbolic systems of PDEs, Logical Methods in Computer Science 13(4:13) (2017), 1–31.

35.

S.V.

Selivanova and

V.L.

Selivanov, On constructive number fields and computability of solutions of PDEs, Doklady Mathematics 477(3) (2017), 282–285.

36.

S.V.

Selivanova and

V.L.

Selivanov, Bit complexity of computing solutions for symmetric hyperbolic systems of PDEs with guaranteed precision, Computability 10(2) (2021), 123–140.

37.

Stoltenberg-Hansen and

J.V.

Tucker, Computable rings and fields, in: Handbook of Computability Theory,

Griffor, ed., Elsevier, 1999, pp. 363–447. doi:10.1016/S0049-237X(99)80028-7.

38.

Tarski, A Decision Method for Elementary Algebra and Geometry, 2nd edn, University of California Press, Berkeley and Los Angeles, California, 1951.

39.

B.L.

van der Waerden , Algebra, Springer, Berlin, 1967.

40.

Weihrauch, Computable Analysis, Springer, Berlin, 2000.

41.

Ziegler and

Brattka, A computable spectral theorem, in: Proc. CCA-2001, Lecture Notes in Computer Science, Vol. 2064, 2001, pp. 378–388.

Primitive recursive ordered fields and some applications

Abstract

Keywords

1. Introduction

1 We are grateful to Vasco Brattka for the hint to Goodstein’s monography.

11.1. Some open problems

Footnotes

Acknowledgements

List of the main abbreviations and notations

References

¹
We are grateful to Vasco Brattka for the hint to Goodstein’s monography.