Welcome to MathOverflow

Question

2

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$?

flag	asked Nov 9 at 9:24 peter franek 317●5

	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. – Emil Jeřábek Nov 9 at 12:19
	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$. – Emil Jeřábek Nov 9 at 12:23
	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. – peter franek Nov 9 at 21:02

alexod · Accepted Answer · 2013-01-19 18:23:02Z UTC

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.

Robert Israel · Answer 2 · 2012-11-09 20:05:31Z UTC

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$.

(Un)Decidability of the root existence problem for functions with bounded domain

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.