5
$\begingroup$

The problem whether a real function $f$ has a root or not is undecidable, given that $f$ is from a class of functions including polynomials and the sine function (http://dl.acm.org/citation.cfm?id=321856). Usually, undecidability is proved by using a periodic function like sin to encode integer problems. Is there anything known about undecidability of the root existence problem for some "reasonable" class of functions with bounded domains, such as from a bounded $\Omega\subset\mathbb{R}^m$ to $\mathbb{R}^n$?

$\endgroup$
3
  • $\begingroup$ As mentioned in mathoverflow.net/questions/109814 , the real field expanded with all analytic functions on a bounded domain is an o-minimal structure. However, I’m not aware of any results on the decidability of its reducts to a finite language (note that decidability of an o-minimal structure is equivalent to decidability of the root existence problem for its definable functions). Decidability of the real field with exponentiation is a notorious open problem related to Schanuel’s conjecture. $\endgroup$ Nov 9, 2012 at 12:19
  • $\begingroup$ Also, asking the functions to have bounded domain does not make much of a difference per se. A “reasonable” class of functions on, say, $(0,1)^m$ can be made into a “reasonable” class of functions on $\mathbb R^m$, and vice versa, by composing with a “reasonable” homeomorphism of $(0,1)$ and $\mathbb R$, such as $1/(1-x)-1/x$. $\endgroup$ Nov 9, 2012 at 12:23
  • $\begingroup$ Emil: right, thank you. What I have in mind is in fact compact domains (typically, finite unions of cubes), my formulation was not very good. $\endgroup$ Nov 9, 2012 at 21:02

2 Answers 2

6
$\begingroup$

Suppose there is an algorithm that decides whether a function $f\colon \Omega \to \mathbb{R}$ has a root. Then one can also compute a root of $f$ if $f$ has one.

One can see this using a standard bi-partition argument: Cover $\Omega$ with finitely many balls of radius $1$. This is possible since the closure of $\Omega$ is compact. Then using the algorithm we can find a ball that contains a root of $f$. Then we cover this ball with balls of radius $2^{-1}$ and again find a smaller ball which contains a root...

Iterating this process yield a sequence converging to a root of $f$ with rate $2^{-n}$ or in other words a Cauchy-real representation for a root.

Now, finding a root for a function implies Brouwer's fixed point theorem.

To see that let $\Omega$ be bounded and closed and $g\colon \Omega \to \Omega$ continuous. $g$ has a fixed-point at any root of the function $f\colon \Omega \to \mathbb{R}$, $f(x):= \lvert g(x) - x\rvert$.

For Brouwers fixed point theorem it is known that there is no algorithm to find solutions, see for instance Computable counter-examples to the Brouwer fixed-point theorem, Petrus H. Potgieter.

Thus, we can conclude that there is no algorithm which decides whether a function has a root.

$\endgroup$
3
  • 1
    $\begingroup$ The questions asks for an algorithm deciding whether or not the function has a root, not an algorithm for finding a root. So you need an extra step to show that deciding whether there is a solution in $\Omega$ also allows you to compute one. I think that can be done but it would be nice to include here. $\endgroup$ Jan 19, 2013 at 16:35
  • $\begingroup$ @François thank you, I missed that point. $\endgroup$
    – alexod
    Jan 19, 2013 at 18:23
  • $\begingroup$ This is really beautiful! $\endgroup$
    – Victor
    Jan 13, 2014 at 11:56
0
$\begingroup$

Suppose $f$ is continuous (and therefore uniformly continuous) on a compact domain $K \subseteq {\mathbb R}^n$ (and this is effective in the sense that given $\epsilon > 0$ you can construct $\delta > 0$ such that $\|x - y\| < \delta$ implies $\|f(x) - f(y)\| < \epsilon$. Then if $f(x) = 0$ has no solution in $K$ you can prove that fact: take $\epsilon > 0$ small enough, take $\delta$ as above, cover $K$ with finitely many open balls of radius $\delta$, and compute the values of $f$ at the centres of these balls with sufficient precision to show they all have norm $> \epsilon$.

$\endgroup$
2
  • $\begingroup$ Robert: thank you. However, in this way you can only prove the non-existence of a root (if it doesn't exists). $\endgroup$ Nov 9, 2012 at 21:07
  • $\begingroup$ Peter: Yes, I know. I don't think there is any way in general to prove the existence of a root if it does exist. $\endgroup$ Nov 11, 2012 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.