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 ${A \text{ or } B}$ is true also when both ${A}$ and ${B}$ are true.

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 ${n}$ dimensions. Strange? Jeff has a relevant quote:

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 ${x,y}$

$\displaystyle (x+2)(y+2) = N,$

is as hard as integer factoring. This follows since ${x+2}$ and ${y+2}$ must be non-trivial factors of ${N}$. Note this relies on the fact that ${x+2}$ and ${y+2}$ are both greater than or equal to ${2}$.

We can delete “nonnegative” in the above by the following simple idea. Suppose that ${N}$ has two factors that are both congruent to ${3}$ modulo ${8}$. If not, then we can still factor, but I believe the idea is clearer without adding extra complications. Then solve in integers

$\displaystyle (8x + 3)(8y+3) = N.$

By assumption on ${N}$ there is a solution of this equation. Moreover suppose that ${x,y}$ are some solution. The key is that ${8x + 3}$ cannot be ${\pm 1}$ and ${8y+3}$ also cannot be ${\pm 1}$. Then it follows that each is also not equal to ${N}$ in absolute value. Thus

$\displaystyle 1 < |8x+3| < N,$

and we have factored ${N}$.

### NP-hard

Jeff points out that it is unlikely that Diophantine problems are going to be classified by the NP-hard machinery. He says

${\dots}$ 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

$\displaystyle F(x,y,z,\dots)= 0,$

have a rational solution ${x,y,z,\dots}$? Of course the famous Hilbert’s Tenth problem asks for integer solutions of polynomials and is undecidable. The rational case is open. We have discussed it before here. See this for a survey.

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 $(x+2)(y+2)$ by a equation that works over the rationals. The attempt failed. I was also unable to find a reference for such a result either. So perhaps it is open.

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

June 19, 2019 8:16 pm

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?

June 20, 2019 9:18 am

Dear S. Smith:

Thanks for comment. Given a $f(x)=0$ one can find the roots in polynomial time. This avoids factoring. But this only works for $f(x)$ not for $f(x,y,z)=0$. It is the complication of several variables that makes it hard.

Best

Dick

2. June 20, 2019 1:34 am

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.

June 20, 2019 11:18 am

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

4. June 20, 2019 10:04 pm

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.

5. June 22, 2019 3:03 pm

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