Diophantine Equations
Complexity of solving polynomial equations
|
| [ Jeff ] |
Jeff Lagarias is a mathematician or a professor at the University of Michigan.
Today I wish to discuss Diophantine equations.
Note, the “or” is a poor joke: For mathematicians 
Jeff has a paper titled Complexity of Diophantine Equations and related talk version. It is a nice review of some of the issues around Diophantine equations.
He has worked on number theory, on complexity theory, and on many other problems. Some are applied and some theoretical. He with Peter Shor solved an open problem years ago that was first stated by Ott-Heinrich Keller in 1930. Our friends at Wikipedia state:
In geometry, Keller’s conjecture is the conjecture that in any tiling of Euclidean space by identical hypercubes there are two cubes that meet face to face.
For dimensions ten or more it is now proved to be false thanks to Jeff and Peter. I am amazed by such geometric results, since I have no geometric intuition. Ten dimensions is way beyond me—although curiously I am okay in 
Every dimension is special.
Complexity of Diophantine Equations
Recall the main problem is to find solutions to equations usually restricted to be integers or rationals. This restriction makes the problems hard as in open, and hard as in computationally difficult.
Factoring-Hard
Jeff mentions the following hardness result in his talk: Solving in nonnegative integers for 
is as hard as integer factoring. This follows since 
We can delete “nonnegative” in the above by the following simple idea. Suppose that 
By assumption on 
and we have factored
NP-hard
Jeff points out that it is unlikely that Diophantine problems are going to be classified by the NP-hard machinery. He says
shows the (possible) mismatch of “natural” Diophantine problems with the P versus NP question.
Factoring is one of those in between problems that could be in P, but most believe that it could not be NP-hard.
Rational Case
The problem of deciding whether a polynomial has a rational root is still open. That is given a polynomial with integer coefficients, does the equation
have a rational solution 
I had tried to see if we could at least prove the following: The decision problem over the rationals is at NP-hard. I thought for a while that I could show that solving equations over the rationals is at least NP-hard. My idea was to try to replace 
Open Problems
Is it undecidable to determine whether a polynomial has a root over the rationals? Can we at least get that it is factoring hard?
By the rational root theorem, if you can factor integers, you can find all the rational roots of a polynomial by exhaustive search. Or am I missing something?
Dear S. Smith:
Thanks for comment. Given a
one can find the roots in polynomial time. This avoids factoring. But this only works for 
not for 
. It is the complication of several variables that makes it hard.
Best
Dick
Manders and Adleman proved that a type of quadratic Diophantine equation is NP-complete: NP-complete decision problems for binary quadratics, JCSS 16:168–184, 1978.
Dear Chris Moore:
Yes they proved this. But it was not about rational solutions. Also it added that the solutions where in some restricted range.
https://www.sciencedirect.com/science/article/pii/0022000078900442
Best
Dick
” Can we at least get that it is factoring hard?”
I think this follows from a little work from the twin results that every non-negative rational is the sum of the squares of four rational numbers and that every non-negative integer is the sum of the squares of four integers. We will also use heavily that the union and intersection of two Diophantine sets is also Diophantine.
Set P(n) to be a set of rationals defined as follows . Set P(0)= {q in Q| q = w^2 + x^2+y^2 + z^2 satisfying, each of w,x,y,z is either 0,1 or is greater than or equal to 2}. Note that P(0) is Q-Diophantine. For any positive integer n, define P(n) as the same as P(0) but where one also insists that w,x,y and z are in P(n-1). For any fixed n, P(n) is Diophantine.
Note also that for any n, any non-integer element of P(n) is at least 2^2^n . Then to factor an integer N, we need to ask if the Diophantine equation given by (x+2)(y+2)=N with x and y in P(k+1) where k is the ceiling of log_2 log_2 n, and where x is between A and B. This corresponds precisely to asking if N has an integer factor between A and B, which is the classic decision version of the factoring problem.
Since P(k) grows only at the log log of n, our resulting Diophantine equation is only slightly longer than the binary expansion of N, so this reduction really is straightforward. Notice also that the degree of this equation if we do each of the and pieces carefully can also be kept low. I think with a little work, one should be able to get that a version of this is no higher than degree 6, and it might be possible to reduce it further.
A result of Ronyai implies that under randomized reductions, and assuming GRH, it is at least as hard as factoring squarefree integers. Isomorphism of finite dimensional algebras over the rationals can be phrased as finding a solution to a system of rational equations. But by taking the sum of squares we can convert the system into a single rational equation. Ronyai (STOC 1987, https://doi.org/10.1145/28395.28438) shows that deciding isomorphism of 4-dimensional algebras over the rationals is at least as hard (randomly) as factoring squarefree integers, assuming GRH.
Jeff Lagarias is an amazing guy. (and he always calls me Jil .) An obvious question is if general Binary Quadratic Diophantine Equation (BQDE) can be solved efficiently by quantum computers. (Of course this would be the case if such problems can polynomially be reduced to factoring.)