Hilbert’s Tenth Again
I think it’s never too late to start anything, except maybe being a ballerina. — Wendy Liebman
|
| Mujeres Con Ciencia source |
Marta Sved was a Hungarian mathematician who in 1930 moved to Down Under and became a teacher of math at the University of Adelaide. Over fifty years later, in 1985, Sved got a PhD. Clearly Liebman’s quote applies to Sved’s pursuit of a PhD.
Today I cannot resist talking about a particular paper of hers in the Mathematics Magazine—Volume 63 Number 1, February 1990:
Mathematics Magazine is a reviewed journal that focuses on exposition, history, and connections to other parts of math. I am a longtime reader of this journal. I have been getting this and other similar math mag’s for years. I am sure I saw this paper and the theorem. I did not see any reason to be overly excited by the result. However, the theorem plays a critical role in solving a long time open problem.
Note, this paper did not make the cover, but I believe it should have. To see why we must look at the famous Hilbert Tenth Problem.
Hilbert’s Tenth
Recall this is the problem: Given a polynomial equation
over the integers, decide if there is a solution over the integers. This was famously proved to be undecidable by the combined work of Martin Davis, Hilary Putnam, and Julia Robinson, and was completed by Yuri Matiyasevich in 1970.
Davis, Putnam, and Robinson proved this first for exponential equations—they allowed 
Solving a famous open problem only increases our interest in related questions. One class of questions involved replacing the integers by other rings. One of the major questions is what happens if we ask for solutions to
over the rationals? This is currently open—see our posted on this and two related ones, plus a topical paper by Bjorn Poonen, for some comments.
Hilbert Tenth Over Rationals
Following the history of the classic version of Hilbert’s Tenth, Mihai Prunescu proved:
Theorem 1 It is undecidable to determine whether an exponential equation in many variables is solvable over the rationals.
This just appeared as The Exponential Diophantine Problem For Rationals in the current issue of the JSL:
It is a short paper—two pages. The key is it shows that it is possible to define the integers by an exponential equation over the rationals. Is there a Matiyasevich out there who will remove the need for exponentials?
Using Exponentials over the Rationals
Prunescu uses the following equation:
The solutions of this equation form a single parameterized family, and allow one to achieve the needed task:
Define the natural numbers from the rational solutions to this equation.
Lemma 2 Suppose that
are rationals so that
. Then for some integer
Moreover, every
His proof outline is to suppose that 
for some
This is an amazing trick—in my opinion.
Prunescu deserves a tip-of-the-hat for this insight. At the high level he is using this: Suppose that 
Then there is a rational operation on 
The Lemma
Prunescu needs the above lemma. He does not prove it, but says:
The equation
The results had been available for a long time—the book was published over a hundred years ago in 1920.
It is interesting to ask why it took so long to realize the connection? I looked at Dickson’s book and found the reference not so clean. I then did a Google search for results on the equation:
The search found that Sved proved in the paper in the Mathematics Magazine—Volume 63 Number 1, February 1990 the following:
Lemma 3 Suppose that
Moreover, every
That is, Sved proved the key lemma in full detail in 1990. Thus over thirty years ago, in an available journal, the exact lemma needed was available.
Why did so all of us miss that Sved’s analysis of the equation
could be used to solve an open problem. One that was open for decades?
Perhaps it says that Prunescu’s insight was indeed surprising. Perhaps. It does raise questions about improving his theorem. For example: Can a similar theorem be proved with only exponentials of the form
This would improve the undecidability theorem a bit.
Open Problems
Perhaps we also should look at results from not top “professional” journals. Hmmm I think I will start looking at them with a new eye. How about you?
Perhaps we also should look at results from not top “professional” journals. Hmmm I think I will start looking at them with a new eye. How about you?
[some layout improvements]
Congratulations to Prunescu! What about solvability of polynomial equations over the ring of Gaussian integers (complex numbers with integral real and imaginary parts) : is this undecidable too?
Dear Pascal, Hilbert 10 was proven undecidable over all quadratic algebraic integer rings by Jan Denef. For the special case of the Gauss integers, there is an extra proof by Matiyasevich in his book about Hilbert 10. But about the exponential diophantine problem in number FIELDS different from Q [as this would be the natural question to put here] I have no ideea and I suppose that nothing is known so far.
Thanks!
Dear Pascal:
Yes congrats in order. Note he proves this only with exponential too.
Best
Dick
All right, but what about the Gaussian integers: is it known whether the problem is undecidable like it is for the “true” integers?
https://vixra.org/abs/1905.0250
In some paper I read Matiyasevich speculates that Hilbert really meant to ask about polys over Q.
The status over Q is of course open, though the recent result pushes me into the undecidable camp.
If H10 over undecidable that would explain why there has been so little progress in trying to find cases that are decidable.
I didn’t read her paper when wrote the following
paper, extending the consideration for hypercomplex
numbers:
https://vixra.org/abs/1905.0250
Hello! Thanks for this article! Just some comments:
– Meanwhile we have undecidability in diophantine exponential equations, not only in systems. The conjunction can be written down because the radical closure of Q is not algebraically closed. One takes a polynomial f(x) which has no solutions in the radical closure. Its homogenized f(x,y) =0 can be used to write the conjunction of exponential diophantine expressions P = 0 /\ Q = 0 as f(P, Q) = 0. An example of f(x, y) is x^5 – xy^4 – y^5.
– For x in Q, you have x in Z if and only if Exists y in Q, y = 2^x. So the exponential diophantine equations in 2^x are easier to prove undecidable. But there is no direct implication between the undecidability of exponential diophantine equations in 2^x and the undecidability of exponential diophantine equations in x^y.
Dear Mihai Prunescu:
Thanks. I really like you paper and result. Impressive.
Good catch on Q and fixed 2^x etc….missed that
Best
Dick
I like very much your posts about Hilbert 10, and the whole blog. I was not aware of this blog. Now I am following it. Best, Mihai
Maybe my story of the Lemma would be of some interest. I found the Lemma as a problem in the romanian book “Probleme de aritmetica si teoria numerelor” by Ion Cucurezeanu, published in Romania in 1978. Different colleagues of mine, who participated in mathematical competitions in the seventies and the eighties, recall to have learned the problem during training lectures for such competitions. I was lucky to find the book put outside, on the floor of the University of Bucharest, in March 2019, because some people wanted to clean their offices and to get rid of “””old stuff”””. I opened it exactly at the page with the solution. The idea was instantaneous, so I ran to the first PC to write down the note.
Marta Sved did her MSc at Adelaide Uni in 1965 (on finite geometry), and both that and her PhD thesis sit on the shelves in the room next to mine!