1

Today while I'm looking at definition of Algorithm from Sipser's textbook, he defined the following language:

$$D_1 = \{ p \mid\ p\text{ is polynomial over }x\text{ with integral roots}\}$$.

This language is decidable since we can bound the integral roots between two values and we can try all possible values between these two numbers.

Now, I'm thinking about a the following language:

$$D_{1}^* = \{ p \mid\ p\text{ is polynomial over }x\text{ with }\mathbf{real}\text{ roots}\}$$

Is this language $D_{1}^*$ decidable? I don't think so since we have an infinite number of solutions between any two numbers in real numbers. Is my argument correct?

plop
  • 1,189
  • 4
  • 11
user777
  • 729
  • 3
  • 20
  • Look at Sturm theorem. That decides that language. It is not the most efficient way, but it is the easiest to explain and the one that possibly you have seen in algebra. More efficient ways are based on using Vincent's theorem. – plop Mar 12 '21 at 17:23
  • In Sturm's theorem you first construct a Sturm sequence. This is a sequence of polynomials that is obtained from the first one by taking derivative and then remainders in Euclidean division. Then the signs of the leading terms and their degrees tell you the number of real roots. If that number is equal to the degree of the given polynomial, then all roots are real. – plop Mar 12 '21 at 17:27
  • I just noticed that your languages is having one real root and not all real roots. That changes the last sentence of my previous comment. The condition becomes just checking that the number of roots given by Sturm theorem is $1$ and that's all. – plop Mar 12 '21 at 17:47
  • What is the representation you are working with @plop ? How would you represent a real valued polynomial? – nir shahar Mar 12 '21 at 17:52
  • 1
    @nirshahar You are going on a tangent getting lost in the woods. What is interesting about the problem is not the question of representing the input. The question doesn't specify. It should, but anyway. One can think a reasonable formulation of the problem. Either finite precision coefficients, or integer coefficients, or a real numbers machine. It is not really crucial. Pick one or check the source of the question for the assumption there. What is interesting is that from the input you can indeed decide the existence of a real root and one way to do this is via Sturm's theorem. – plop Mar 12 '21 at 18:39
  • 1
    @nirshahar All is needed to use Sturm's theorem will be to be given the coefficients, being able to add, subtract, multiply, divide and tell if a number is positive, negative or zero. Of course, if one chooses a version of the problem in which the input cannot allow one of these, then there is no way. Perhaps an interesting example is if we assume the coefficients to be computable numbers Then we cannot in general say when one of them is positive, negative or zero. The problem is doomed from the beginning. – plop Mar 12 '21 at 18:53
  • 1
    @nirshahar If one allows the input to be polynomials with coefficients that are computable numbers, then one cannot even tell, in general, whether a constant polynomial is zero or not. – plop Mar 12 '21 at 18:55
  • I totally agree with you there, but think a valid answer to this question should also mention that under normal circumstances this is not properly defined. – nir shahar Mar 12 '21 at 19:00
  • I checked that book by Sipser Introduction to the theory of computation, at least in the third edition, on page $184$, the $D_1$ that they define is in the context of talking about Hilbert's tenth problem. So, their intension there is only polynomials with integer coefficients. – plop Mar 12 '21 at 19:16

3 Answers3

4

Maybe I should summarize what I was saying in the comments.

Yes, the problem should be formulated precisely in order to give an answer.

About the cases in which the answer is NO:

For those formulations in which the answer is NO it is usually for a trivial reason. For example, one case that is mildly interesting is if we are considering the polynomials with coefficients that are computable numbers. These are numbers for which there is an algorithm such that for any given precision it terminates and gives you the digits of the number up to that precision. So, the input of $D_1^*$ in that case, would be a finite collection of such algorithms, one for each coefficient. Well, in this case $D_1^*$ cannot be decided, even for a constant polynomial. This is just because we cannot tell if that constant is zero or not.

The context in Sipser's book:

Now, I looked at the book by Sipser. They mention $D_1$ in the context of the Hilbert's tenth problem, which concerns polynomials (in several variables) with integer coefficients. In this context and many others you can indeed decide $D_1^*$.

The interesting part:

If the coefficients are such that we can (algorithmically) perform the following operations:

  • sum, subtraction, multiplication, division,
  • test if positive, test if negative, and test if zero.

Then we can decide if a polynomial has a real root.

For example, we can consider $D_1^*$ as a problem about polynomials with integer coefficients, or rational numbers, or constructible numbers, or algebraic numbers, or perhaps consider the problem with arbitrary real numbers but in a Blum-Shub-Smale machine instead of a Turing machine. As long as we can do the six basic operations above, we should be okay.

One way to decide could be using Sturm's theorem. Sturm's theorem says that the number of real roots of a square free polynomial with real coefficients in an interval $(a,b]$ is equal to the difference of the number of changes of sign at $a$ and the number of changes of sign at $b$ of the values of a Sturm sequence. See in the link above.

If the polynomial input $p$ has complex coefficients we can just work with the $\gcd$ of its real and imaginary parts. If the polynomial is not square-free, then we divide it by the $\gcd(p,p')$ to make it square-free. These transformations don't preserve the answer. Remember that one can compute $\gcd$ using using the Euclidean algorithm. So, we only need the arithmetic operations mentioned above.

One way to construct a Sturm sequences is the following: The first term is $p$, the second term is $p'$, the derivative of $p$. If $q_i,q_{i+1}$ are two consecutive terms of the sequence constructed so far, then the next term $q_{i+2}$ is equal to the remainder of $q_{i}$ divided by $q_{i+1}$ and with the sign switched. This procedure is always finite since remainders always have smaller and smaller degrees.

plop
  • 1,189
  • 4
  • 11
1

You have said what roots you care about, but not what the coefficients of the polynomial might be. We have various options here:

  1. We could use integer coefficients. Then it is decidable whether there are real roots or not. We don't go and do an exhaustive search over the reals for this, but instead essentially exploit that an integer polynomial can't get arbitrarily close to $0$ without reaching it.

  2. We could use rational coefficients. It is still decidable, this case reduces to the one above by multiplying with some common multiple of the denominators.

  3. We could use algebraic numbers. Here the coding becomes a bit tricky - we code algebraic numbers by giving their characteristic polynomial plus a rational interval in which the desired number is the only root of the polynomial. It is still decidable whether a polynomial has a zero, this can be deduced by an appeal to the theory of real closed fields being decidable.

  4. We could use real number coefficients. We can no longer use finite words to code our inputs, but a Turing machine can process infinite sequences just fine. However, the real numbers (and subsequently the space of polynomials with real coefficients) is connected, and as a consequence has no non-trivial decidable subsets.

Arno
  • 3,065
  • 10
  • 22
  • How would a TM work with an infinite sequence? it will never stop... Also, you cant multiply by a common denominator since there is an infinite number of them. – nir shahar Mar 12 '21 at 17:24
  • @nirshahar TMs have infinite tapes, so of course it can start with a full description of a real polynomial written on it. Also of course, it cannot read the entire input and then stop. Which is why decision problems over the reals are indeed boring (but computable functions on the reals are not). – Arno Mar 12 '21 at 17:27
  • @nirshahar A polynomial has finitely many coefficients, otherwise it ceases to be a polynomial and is a formal power series instead. – Arno Mar 12 '21 at 17:27
  • Wtf? from when do TMs have infinite tapes? The usual definition has only one tape. If it would have infinite tapes then all languages are decidable in $O(1)$ time – nir shahar Mar 12 '21 at 17:28
  • @nirshahar infinite tape $\neq$ infinitely many tapes – Arno Mar 12 '21 at 17:28
  • Oh i get what you meant. However, it would still never finish reading its input and will never finish computing. So it doesn't change my argument – nir shahar Mar 12 '21 at 17:29
  • Unless we want a finite precision that it. – nir shahar Mar 12 '21 at 17:31
  • @nirshahar The issue with your argument is that you'd also claim that it doesn't make sense to ask whether eg addition of real numbers is a computable function, but it does make sense and it is a computable function. – Arno Mar 12 '21 at 17:31
  • But still, the computation will never stop: It might compute one decimal place after another, but there would be an infinite number of decimal places. It will never finish computing. Here we care about accepting as well, not only outputting some value. This means the TM needs to halt, which doesn't happen here at all – nir shahar Mar 12 '21 at 17:34
  • 1
    Your case 1 has the correct answer, but the argument is not. That is not how you decide if a polynomial has a real root. Doing an "exhaustive search over the reals" is not a terminating algorithm. – plop Mar 12 '21 at 17:38
  • @plop Doing an exhaustive search over the real is what the OP considered as the obvious but impossible attempt. As you can see in my answer, I point out that that is not how it works. – Arno Mar 12 '21 at 17:47
  • "exploit that an integer polynomial can't get arbitrarily close to 0 without reaching it" is also not an algorithm either. – plop Mar 12 '21 at 17:48
0

Yes, but to formalize it you might need to do a bit more work. First, what is the encoding of a polynomial? This is a tricky thing: since we can't have all polynomials representations available to us, since we can't encode all real numbers. This will mean that the decidability of this language is somewhat not interesting, since it comes from the impossibility of representation as strings rather than the actual language and its properties.

Moreover, I would argue it does not even make sense to ask this question when condsidering all reals, because it is impossible to represent as a language, while decidability and other similar definitions all talk about languages.

But, if you would restrict yourself to some finite representation of polynomials, you might not cover all real polynomials, but you can be not too far away from it. For example, you can represent all rational polynomials, and because the rationals are dense in the real line, then we would get a "close enough" representation. Defining like that would make the question more tangible, and the undecidability could be proven from more interesting properties than just that its impossible to represent.

nir shahar
  • 11,538
  • 3
  • 14
  • 35