A Special Case of Hilbert’s Tenth Problem
July 19, 2010 6 Comments
In 1900, David Hilbert posed a list of 23 quality problems in mathematics, many of them remain unsolved till date. These problems have caused a significant progress in various disciplines of mathematics. Briefings and current status of the problems can be found here. In this post, I am going to brief Hilbert’s Tenth Problem and pose a related puzzle problem.
A root of a multivariate polynomial 
In 1970, Yuri Matijasevic proved that there can not exist an algorithm for the problem. But what about the special case when the input polynomials are univariate only i.e. Does there exist an algorithm which when given a univariate polynomial with integral coefficients as input tells if at all there are any integral root to it? If yes, then what would be the best possible algorithm for this with respect to time complexity ( i.e. the number of steps it takes to arrive at the answer (yes/no) on the worst case input to your algorithm).
PS: People can post their (full/partial) solutions in the comments section.
First person to give a solution which is the one I’ve in my mind, or a better one will be treated with a 5-star chocolate*.
*conditions applied.
well, I have a solution. But I’ll tell you only when you reveal the Terms and Conditions in public.
Anyways, a chocolate isn’t a big deal. So my sol. is that a univariate polynomial expression has as many number of real roots as the number of sign changes in its coefficients. My answer gives the real roots and not the integral roots. For integral roots, I may have to think for some more time and noow I’m in no mood to do that
‘in public’ :O
. Will get you a chocolate for your effort.
changes sign twice, but has not integral roots.
there is no public around, just you and me
btw
With regard to terms and conditions, there are two conditions:-
)
1. Winner should not be geographically very far away from me.
2. It should be his own solution, not that he poses the question on a popular maths forum and get the solution. One may work in team. This post is to induce the pleasure of finding things out amongst those CS people who feel lost. ( but now it seems to me like people are feeling more lost after reading the post, 40 visits to this post and just one comment
well, as I already mentioned, my solution gives real roots and not integral roots. will have to work on it
.. will come back to you after some time (in Kamal Sir’s style 
)
mmm.. Looks like there is an algorithm for the problem…
I will explain using the example used by you, which is — f(x) = x^2 – x + 1
Lets just say that an integral root exists. Then without any loss in generality, I can write the same equation in this way:
f(x) = (x – a)f1(x) [where a is an integer]
And we know from our class 8/9, how to derive the f1(x). [by checking out the cooeficient of xi's in f1(x)]
Hope its clear and correct.
btw… Nice Read Mehta saab!
Totally my bad! I need to think more on this…. (duh! office! office! )