Computable roots of computable functions

Here are several interesting results from computable analysis:

Theorem 1. If $f$ is a computable function from $\mathbb{R}$ to $\mathbb{R}$ and $\alpha$ is an isolated root of $f$, then $\alpha$ is computable.

Corollary 2. If $p(x)$ is a polynomial over $\mathbb{R}$ with computable coefficients, then every root of $p(x)$ is computable.

Theorem 3. There is a effective closed subset of $\mathbb{R}$ which is nonempty (in fact, uncountable) but which has no computable point.

Theorem 4. There is a computable function from $\mathbb{R}$ to $\mathbb{R}$ which has uncountably many roots but no computable roots.

These are all well known to computable analysts and I take no credit for any ideas in this post. I happened to think about these theorems based on a question at math.stackexchange.com, and I realized the literature I usually look at doesn’t have proofs of them, so I am going to prove them here. The proofs are interesting because they will use a correspondence between root sets of continuous functions on $[0,1]$ and $\Pi^0_1$ classes in $2^{\omega}$. The latter are a standard tool in computability theory, and the correspondence reduces the above results to standard exercises from a computability course.

One interesting aspect is that these results have no direct formalization in Reverse Mathematics. When we formalize things in that setting, the adjective “computable” disappears, and so the first two results simply say that every root is a number. The third result becomes contradictory, claiming there is a nonempty set that has no points, and the fourth has the same issue. Of course we could try to directly formalize “is computable” using Kleene’s $T$ predicate, but that would be a sort of meta-formalization rather than a direct formalization of the results. This is why results like these can’t be directly found in Simpson (1999).

I want to sketch a proof of the four results using the following two theorems, which follow immediately from results in section II.7 of Simpson (1999). I have seen these cited to Nerode and Huang (1985); see the “history” section below.

Theorem 5. If $f$ is a computable function from $\mathbb{R}$ to $\mathbb{R}$ then there is an effective open set $U$ such that for all $x$, $x \in U$ if and only if $f(x) \not = 0$.
Theorem 6. If $U$ is an effective open subset of $\mathbb{R}$ then there is a continuous computable function $f \colon \mathbb{R} \to \mathbb{R}$ such that $U = \{ x : f(x) \not = 0\}$.

These two results, together with some understanding of effective open and closed sets, will be enough. First, here are the definitions:

Definition 7. A quickly converging Cauchy sequence in $\mathbb{R}$ is a sequence $(a_n)$ such that for all $n$ and $m > n$, $d(a_n, a_m) < 2^{-n}$.
Definition 8. A function $f\colon \mathbb{R} \to \mathbb{R}$ is computable if there is a Turing functional which, given any quickly converging Cauchy sequence $(a_n)$ of rationals, produces as output a quickly converging Cauchy sequence $(b_n)$ of rationals such that $f(\lim a_n) = \lim b_n$.
Definition 9. A set $U \subseteq \mathbb{R}$ is an effective open set if it is empty or is the union of an r.e. sequence of open rational intervals, and is an effective closed set if its complement is an effective open set.
Definition 10. A subset $U \subseteq 2^{\omega}$ is $\Sigma^0_1$ if it is empty or is the union of an r.e. sequence of cylinder sets, that is, sets of the form $N_\sigma = \{ g \in 2^{\omega} : \sigma \sqsubseteq g\}$. A subset $C \subseteq 2^{\omega}$ is $\Pi^0_1$ if its complement is $\Sigma^0_1$.

The $\Sigma^0_1$ and $\Pi^0_1$ subsets of $2^{\omega}$ play the same role as the effective open and effective closed subsets of $\mathbb{R}$, respectively. We first note that the functional $I$ from $2^{\omega}$ to $[0,1]$ such that
$$
I(g) = \sum_{i \in \omega} g(i) 2^{-(i+1)}.
$$
is surjective and computable in the sense that from any $g \in 2^{\omega}$ we can uniformly compute a quickly converging Cauchy sequence for $I(g)$. Moreover, $I$ is continuous in a nice way:

Theorem 11.

  • If $U$ is an effective open subset of $[0,1]$ then $I^{-1}(U)$ is a $\Sigma^0_1$ subset of $2^{\omega}$.
  • If $C$ is an effective closed subset of $[0,1]$ then $I^{-1}(C)$ is a $\Pi^0_1$ subset of $2^{\omega}$. Moreover, if $\alpha$ is an isolated point in $C$ and is not a dyadic rational then
    $I^{-1}(\alpha)$ is an isolated point in $I^{-1}(C)$.

This result gives Theorem 1 with little additional work.

Proof of Theorem 1. As a special case, given a computable function $f \colon [0,1] \to \mathbb{R}$, we first form the effective closed set $C$ of roots of $f$. We can assume $f$ has no dyadic rational roots because these are all computable. Now if $\alpha \in (0,1)$ is an isolated root of $f$ then $I^{-1}(\alpha)$ is isolated in $I^{-1}(C)$. But an isolated point in a $\Pi^0_1$ subclass of $2^{\omega}$ is computable, so $I^{-1}(\alpha)$ is computable, hence $\alpha$ is computable.

For the general case where $f\colon \mathbb{R} \to \mathbb{R}$, every isolated root $\alpha$ of $f$ is isolated in some rational interval $(q, 1+q)$; by translating $q$ units left and applying the special case, we see that $\alpha – q$ is computable, so $\alpha$ is computable as well. ∎

Corollary 2 follows immediately from Theorem 1 because every polynomial with computable coefficients gives a computable function, and every root of a polynomial is isolated.

Proof of Theorem 3. We ignore $I$ and use a more direct technique. The middle-thirds Cantor set $M \subseteq [0,1]$ is an effectively closed subset of $[0,1]$ which is computably homeomorphic to $2^{\omega}$. It is well known that there is a nonempty $\Pi^0_1$ class $P$ which has no computable points; this in turn gives an effective closed subset of $M$ under the homeomorphism. This subset of $M$ is nonempty because $P$ is, and has no computable points because each point in $M$ computes the corresponding point in $P$. The uncountability of the set follows from the Cantor-Bendixson analysis: if $P$ was countable it would have an isolated (and thus computable) point. ∎

Theorem 4 follows directly from Theorem 3 and Theorem 6.

History

I believe Corollary 2 and Theorem 4 are due to Specker, and Theorems 1 and 3 are due to Nerode and Huang (1985), although I am going by secondary sources to make these claims. The MathSciNet review of Specker (1959) claims Specker also used the existence of a nonempty $\Pi^0_1$ set with no computable points to prove Theorem 4. I cannot read the language that either of these papers was written in.

The correspondence between effective open (closed) subsets of $[0,1]$ and $\Sigma^0_1$ ($\Pi^0_1$) classes in $2^{\omega}$ was also apparently noticed by Nerode and Huang, although I have no idea whether their proof is similar to mine. It seems like this correspondence could have been known much earlier.

References

  • Nerode, Anil; Huang, Wen Qi. An application of pure recursion theory to recursive analysis. (Chinese) Acta Math. Sinica 28 (1985), no. 5, 625–636.
  • Simpson, Stephen. Subsystems of second-order arithmetic. Springer, 1999.
  • Specker, Ernst. Der Satz vom Maximum in der rekursiven Analysis. (German) In A. Heyting, editor, Constructivity in Mathematics, 254–265. North-Holland, 1959.
This entry was posted in Results worth knowing and tagged , . Bookmark the permalink.

4 Responses to Computable roots of computable functions

  1. Quinn Culver says:

    Great post. Some comments/questions:

    1. Notice that if $f$ actually crosses the $x$-axis at $\alpha$, then Theorem 1 is pretty easy to prove directly: fix a rational interval $[p,q]$ such that $\alpha$ is $f$’s only root in $[p,q]$. Then use the intermediate value theorem to hone in on $\alpha$. I guess if $f$ is nonnegative (or nonpositive), then it’s not so easy.

    2. Algorithmic randomness gives a simple proof of Theorem 3 (and for the same reason a simple proof of the existence of a $\Pi^{0}_{1}$ class in Cantor space with no computable member): Let $K_n=[0,1]-U_n$, where $\{U_n\}_{n \in \omega}$ is the universal Martin-L\:{o}f test. Then each $K_n$ is effectively closed and has positive measure, so is uncountable. But each member of $K_n$ is Martin-L\:{o}f random, hence incomputable.

    3. I’m curious to know what the function (which would have a given effectively closed set as its root set) in Theorem 6 looks like. In particular, would it be a violation of the “computable intermediate value theorem”? That is, would there be rationals $p$ and $q$ such that $f(p)<0<f(q)$, but $f$ has no computable root between $p$ and $q$? This wouldn't be the case if the function were always non-negative. Someone recently told me that this "computable intermediate value theorem" is indeed a theorem, but I was suspicious.

    4. A (minor) typo:
    "Theorem 4. There is an computable continuous…"

    5. I think saying "computable continuous" is redundant since computable implies continuous. (Note that this occurs twice.)

    • Carl Mummert says:

      Thanks for the detailed reading! I edited the post and made the last two changes you suggested.

      The function from Theorem 6 is constructed as follows. Enumerate the effective open set as a sequence $(I_n)$ of open intervals. On interval $I_n$, put a nonnegative bump function that is nonzero exactly on $I_n$ and has height $2^{-n}$. Then let $f$ be the pointwise sum of all these bump functions. This function $f$ is nonzero exactly on the open set, and is nonnegative everywhere. Also $\mathsf{RCA}_0$ is able to verify that this construction works.

    • Carl Mummert says:

      The computable IVT works fine. For simplicity assume the interval is $[0,1]$ and that $f(0) < 0 < f(1)$ and that the function has no rational roots (because these are all computable). Then $f(1/2)$ is either strictly positive or strictly negative, and with enough computation we can tell which of these alternatives is the case. Thus we have can replace either $0$ or $1$ with $1/2$. We iterate this process, halving the interval again and again, which gives a quickly converging Cauchy sequence for some root. There is a small subtlety that a different algorithm is needed if the function has a rational root, and there is no uniform way to tell whether a function has no rational roots. The uniform version of the IVT is not provable in $\mathsf{RCA}_0$ (it is equivalent to $\mathsf{WKL}_0$) while the non-uniformized version is provable in $\mathsf{RCA}_0$ as above.

Leave a Reply

Your email address will not be published. Required fields are marked *