Hilbert Tenth On Rationals

Mihai Prunescu is at the Institute of Mathematics of the Romanian Academy. He works in logic and complexity theory. We recently discussed his work on Hilbert’s Tenth.

Today we thought we would do a follow up discussion of a recent paper of his on the famous Hilbert’s Tenth problem.

“Hilbert’s Tenth” is actually a suite of problems: is it decidable whether a finite set of equations of a certain kind have a common solution over a certain domain? When the domain is the integers and the equations are polynomials set to zero we have the original form, which was shown to be undecidable by Yuriy Matiyasevich, completing work of Julia Robinson, Martin Davis, and Hilary Putnam. But over the reals, the problem for polynomial equations is decidable, and Hilbert himself had shown this over the complex numbers. The rational numbers are the key unsolved case, which I posted about eleven and ten years ago and again more recently.

The last post, two months ago, was about attempts to get leverage on the rationals by extending the equations to allow exponentiation. Mihai added several helpful comments to that post, and with his blessing, this is trying to restart the discussion as busy pandemic-impacted university terms for Ken and some others we know draw to a close.

Subtleties With Exponents

He has helped us understand a few subtleties in correspondence since then. They concern both that rational numbers and exponentials are involved. The focal point confounds our expectation that the square of any nonzero rational number should be positive. Here are two examples of issues:

• If and we put then gives a negative value on the right-hand side.
• If and we put then the negative square root of is a possible value.

If we have two equations and and we want to say that solves at least one of them, we can introduce the single equation

This is not affected by the subtleties. But now suppose we want to do AND instead of OR. The natural idea is to make the equation

However, suppose we have the equation . This is the same as . If we square it, we get

The abstract worry is that this could allow solutions where is chosen negative, though not intended as the square of (whether positive or negative). Mihai gave us a simple example of two exponential equations where unintended solutions occur after squaring and adding them. Consider

versus

The former set is solved only by with the exponents nonzero. The latter, however, allows solutions illustrating both issues above:

where in the latter, the negative square root of is taken. What this means is that with rationals and/or exponentials we must watch our manipulations more carefully.

The Theorem

The following theorem is essentially due to Mihai:

Theorem 1 Let be an integer polynomial. Then it is undecidable to determine whether there are in and also in so that

1. and

2. For each

   

Here as usual is the rationals. The full question whether the above theorem can be proved without any exponential functions remains open, after much attention by many researchers.

Some History

The reason we say “essentially” due to Prunescu must be explained. He recently published an article showing that The Exponential Diophantine Problem For is undecidable: It is in the Journal of Symbolic Logic (JSL), Volume 85, Issue 2.

His clever proof showed that the solutions over the rationals of

lie in a one-dimensional space. This space is parameterized by the integers and so it can be used to define the integers. This immediately proves the undecidability by reduction to the classic Hilbert’s Tenth over the integers.

Ken and I then wrote a post on our blog GLL explaining his JSL result. Mihai kindly added a comment on the post that basically stated the above theorem with .

I was initially puzzled since the above theorem seems to be stronger than his JSL theorem. His published result uses a binary exponential function and the new theorem needs only the unary function . Now it must be said that the cases could be incomparable—because the extra freedom of allowing any rational base in could promote a different kind of analysis that makes the existence of such solutions decidable. The equivalence logic coming back from undecidable cases over the integers might not apply in the above reduction. But the undecidability when the base is fixed to be still strikes me as capturing the general import.

What’s more, the theorem fixing as the base has a much simpler proof. It requires only a lemma that extends the famous Euclid Theorem: The value is not rational.

Proof of the Lemma

The proof rests on the famous result of Matiyasevich on Hilbert’s Tenth and the following lemma:

Lemma 2 Suppose that , , and . Then is an integer.

Proof: Clearly we can assume that . We will prove the lemma in two steps.

1. The value is an integer.

2. The value is an integer.

Let for integers that are co-prime and and .

Step (1): Now let

where and are co-prime integers. We can assume that ; otherwise, step (1) is true. Now

But and are co-prime since and are co-prime. But this implies that is not an integer, since . Note this uses that and . This contradiction proves step (1).

Step (2): By step (1) we thus have that

for some integer . Then

Thus is an integer and so by unique factorization it follows that must be an integer power of . Let . Then

This implies that and so that is an integer. This proves step (2).

Open Problems

We have shared the topic also with Joël Ouaknine and thank him for his comments as well. Addressing our readers, do you have any further comments? What do you think about the rationals?

Ken related an idea while corresponding with Mihai: Suppose we introduce a special squaring function with the properties that

• is always positive for nonzero .

• In particular, gives only the positive square root of .

• Terms with may not appear in exponents, nor be bases of them. They may only be added and multiplied.

The motivation is that now

does give the AND of the two equations. What then becomes of the above undecidability proofs, and does the AND property have other applications?