20
$\begingroup$

Given a real number uniquely defined by a finite system of equations and inequalities with rational coefficients involving the standard elementary functions only. Is it decidable whether this number is rational?

Edit: The system of equations and inequalities may have $n$ real-valued variables, and the real number to be defined is $\xi$. By decomposition using intermediate variables, we may suppose that each inequality is of the form $x_i\,\omega\, c$ where $\omega\in\{<,>,\le,\ge\}$ and $c$ is an integer, and each equation is of the form $x_i=\xi$, or $x_i=c$ where $c$ is an integer, or $x_i=x_j\circ x_k$ with $\circ\in\{+,-,*,/\}$, or $x_i=\phi(x_k)$ where $\phi\in E$ with a specified set $E$ of elementary functions, such as $E=\{\exp,\log\}$. The answer to the question might depend on the choice of $E$.

I assume that $\xi$ is uniquely determined (hence defined) by this system of equations and inequalities. One may even assume that one has a proof for this, should this help.

The algorithm may be defined according to any of various traditional models, specifying a sensible set of primitive operations (including the rational operations [e.g., on bits or on reals] and branching on an expression). I am more interested in the applicable techniques than in an answer for a particular model.

Note that the Wikipedia article on the constant problem claims (by reference to D.H. Bailey, Mathematics of Computation 50 (1988), 275–281) a result from which decidability would follow, but this claim is spurious.

$\endgroup$
  • 2
    $\begingroup$ I believe this follows from the decidability of first-order theories of the reals. $\endgroup$ – Joseph O'Rourke Nov 17 '15 at 12:09
  • 5
    $\begingroup$ @JosephO'Rourke I don't quite see how to get this from Tarski's theorem on real-closed fields, since in that result, we are not allowed to have a predicate for the rationals. The structure $\langle \mathbb{R},+,\cdot,0,1,<,\mathbb{Q}\rangle$ is undecidable. $\endgroup$ – Joel David Hamkins Nov 17 '15 at 12:24
  • 2
    $\begingroup$ @GerryMyerson, for that particular case, either the "say yes" algorithm or the "say no" algorithm will get the right answer. What we need is to encode undecidability into such equations. $\endgroup$ – Joel David Hamkins Nov 17 '15 at 12:29
  • 2
    $\begingroup$ I am not quite clear on your specifications, but see Richardson's theorem for an undecidability result at least somewhat in that context. $\endgroup$ – user9072 Nov 17 '15 at 12:31
  • 7
    $\begingroup$ If we don't have $E$ (so we only have the field operations), the answer is "yes" by quantifier elimination. Any first order statement which singles out a unique for $x$ must be equivalent to one which uses no other variables, so of the form $f(x)=0$ combined with some inequalities. But the rational root theorem lets us find all rational roots of $f$ and then we can test the inequalities. $\endgroup$ – David E Speyer Nov 17 '15 at 16:27
6
$\begingroup$

This is a long comment rather than an answer.

Your problem is what is known as a "promise problem." The input comes equipped with a promise, namely that there exists a unique real solution. Presumably, if the promise is violated, then the algorithm is "off the hook" and can do anything it likes, including failing to halt.

I'm not aware of any research on the decidability of promise problems. (There is some work on the computational complexity of decidable promise problems.) The essential difficulty of your problem seems to reside in its nature as a promise problem, rather than on anything about rational numbers. To see this, let us consider the related question: Is being an integer decidable? This looks just as difficult as your question.

In the computational complexity realm, it's often possible to pass between promise problems and existence-of-a-solution problems. That is, the questions "there exists a unique solution; what is it?" and "does there exist a solution?" are closely related, and one can often reduce one to the other. Indeed, for your problem, if we had an algorithm to answer "does there exist a rational solution?" then we could solve your problem. However, I don't see how to create a reduction in the opposite direction, because I don't see how to create suitable promise problems starting from an arbitrary system. If we could, then perhaps the fact that Hilbert's tenth problem over $\mathbb Q$ is still open could be used to show that your problem is still open.

$\endgroup$
  • $\begingroup$ It seems easy to remove the promise by asking for a 4-way decision: The given system has no/exactly one/at most one/at least one rational solution, allowing for a subset of the options being returned. $\endgroup$ – Arnold Neumaier Nov 17 '15 at 17:49
  • 2
    $\begingroup$ @ArnoldNeumaier If you state the problem that way, then I can prove the problem at hand becomes definitely undecidable; we can encode the halting problem by means of diophantine equations, which we can encode using $\sin$ as an elementary function. The point of a promise problem is that it may be easier to solve the promise case, even if you can't decide whether the promise is true or not. $\endgroup$ – Joel David Hamkins Nov 17 '15 at 19:10
  • $\begingroup$ @JoelDavidHamkins : How exactly are you getting around the fact that Hilbert's tenth problem over $\mathbb Q$ is still open? $\endgroup$ – Timothy Chow Nov 17 '15 at 21:14
  • $\begingroup$ @TimothyChow Hilbert's 10th problem is just about diophantine equations, but the OP allows elementary functions, and my argument uses the $\sin$ function. $\endgroup$ – Joel David Hamkins Nov 17 '15 at 23:47
  • $\begingroup$ @JoelDavidHamkins : Sorry for being dense, but I still don't follow. I understand how you can use the sine function to encode diophantine equations, but Arnold wants to know if there exists a rational solution, not if there exists an integer solution. Asking if a system of polynomial equations with integer coefficients has a rational solution is not known to be an undecidable problem. $\endgroup$ – Timothy Chow Nov 18 '15 at 3:27
9
$\begingroup$

As Timothy Chow pointed out, the OP's question is most naturally formulated as a promise problem: given a finite system of equations and inequalities in finitely many variables and the promise that it has a solution and furthermore that all solutions have the same value for the particular variable $\xi$, determine whether or not that value of $\xi$ is rational.

Let me show here in various ways that if we drop the promise-problem aspect of the problem, it is not decidable.

Theorem. There is no computable procedure to determine whether a given finite system of equations and inequalities, allowing the operations $+,\cdot,0,1,\sin$, has a solution in the reals.

Proof. We shall use the variables $\xi,x_1,\ldots,x_n$ and another variable $p$. By insisting that $\sin(p)=0$ and $p>0$, we can ensure that $p$ is an positive integer multiple of $\pi$. By insisting that $\sin(x_i\cdot p)=0$, we can ensure that each $x_i$ is an integer.

In this way, we may transform any diophantine equation $q(\vec x)=0$, where $q$ is polynomial in several variables over the integers, into a system over the reals, such that $q(\vec x)=0$ has a solution over the integers if and only if the new system has a solution over the reals.

But it is a well-known consequence of the MRDP theorem that we cannot computably decide whether a given diophantine equation has a solution over the integers (and this was the solution to Hilbert's 10th problem). QED

Theorem. There is no computable procedure to determine whether a given finite system of equations and inequalities in the variables $x_1,\ldots,x_n,\xi$, allowing the operations $+,\cdot,0,1,\sin$, has at least one rational value $\xi$ that is part of a solution. Furthermore, this remains undecidable even given the promise that there is at most one value $\xi$ that is part of a solution, and that no irrational $\xi$ are solutions.

Proof. For any diophantine equation $q(\vec x)=0$, consider the modified system over the reals, using the additional variable $p$, where we insist that $q(\vec x)=0$ and also $\sin(p)=0$, $p>0$, and $\sin(x_i\cdot p)=0$, which ensure that $p$ is a positive integer multiple of $\pi$ and that all the $x_i$'s are integers. Finally, add the equation $\xi=0$.

The original diophantine equation has a solution over the integers just in case the new system has a solution over the reals, and in any such solution, $\xi$ will be rational, because it will be $0$. So the original system has a solution over the integers if and only if the new system has at least one solution for which $\xi$ is rational. So this is not decidable. QED

Theorem. There is no computable procedure to determine whether a given finite system of equations and inequalities in the variables $x_1,\ldots,x_n,\xi$, allowing the operations $+,\cdot,0,1,\sin$, has at most one rational $\xi$ that is part of a solution. Furthermore, this remains undecidable under the promise that there are at most two values of $\xi$ that solve the system, both rational.

Proof. We use the same idea, but replace the equation $\xi=0$ with the equation $\xi(\xi-1)=0$. So this system has either no solutions or $\xi=0$ and $\xi=1$ are both solutions. QED

These theorems do not seem to answer the full question: given a finite system of equations and inequalities, and given the promise that there is exactly one value of $\xi$ that is part of a solution, determine whether this value of $\xi$ is rational or not.

$\endgroup$
  • $\begingroup$ Thanks for this. I see it now: It is only $\xi$ whose rationality is under scrutiny, not all the variables in the system. $\endgroup$ – Timothy Chow Nov 18 '15 at 18:31
4
$\begingroup$

I found a paper by Babai, Just, and Meyer auf der Heide that answers a closely related question.

They prove among others (see the discussion on p.101) that there are no anlytic computation trees (ACTs) that accept the complement of the rationals in the reals, and hence would prove the irrationality of a number.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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