Hilbert’s 10.5th Problem
Solving equations over the rationals
Alexandra (Sasha) Shlapentokh is a number theorist who works on a variety of problems including those related to Hilbert’s Tenth Problem.
Today I wish to discuss a neat survey paper of hers that just appeared in The Bulletin of Symbolic Logic.
Her paper is titled, “Defining Integers.” This is a pretty short and simple sounding title, but what is so hard about defining integers? It depends—more in a moment. The paper is a beautiful survey of some of the questions still open around Hilbert’s Tenth. I especially like the light touch of the article, since some papers in logic journals—even surveys—can be heavy on notation and hard to read. Not this one.
Her paper is a joy to read. Here are some of the sections titles, which should make it clear that this is a cool paper:
- A question and answer
- Some easy facts or getting getter acquainted
- Becoming more ambitious
- Some unpleasant thoughts
- Meanwhile in a galaxy not far away
Take a look at the paper yourself. Let’s discuss Hilbert’s Tenth, and some of the still-open questions that may be tractable.
Hilbert’s Tenth Problem (HTP) is the question raised by David Hilbert at his famous 1900 Paris lecture on whether or not there is an algorithm to decide whether a Diophantine equation has a solution over the integers:
More formally, given an integer polynomial , it asks whether there are integers so that
It is notable that Hilbert asked his question before there was even a formal notion of algorithm. His original wording was:
Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.
The famous theorem of Martin Davis, Yuri Matiyasevich, Hilary Putnam, and Julia Robinson showed that there can be no “process” to solve HTP:
Theorem: Hilbert’s Tenth Problem is unsolvable.
That is there is no algorithm that given a polynomial decides whether or not it has an integer solution. In 1944 Emil Post declared that Hilbert’s tenth problem “begs for an unsolvability proof.” The proof came in 1970 as Matiyasevich completed the last key step of a program started by Davis, Putnam, and Robinson; a program that many doubted would ever work.
This is one of the great examples of how mathematicians who share ideas can lead to solutions of very hard problems. A more recent example is the work on the Poincaré Conjecture: there Grigori Perelman used the program of Richard Hamilton to solve the Poincaré Conjecture in the remaining case of three dimensions.
See The Movie
Dick Karp once asked me about the problem: Where are the movies? Well there are movies on HTP.
Let HTP() be the following generalization of Hilbert’s Problem to polynomials over the ring . Now we ask, given a polynomial with coefficients from , is there a solution so that
When is the integers this is the original HTP, and we know that it is unsolvable in general.
What happens when we change the ring to the rationals ? The answer is curt: it is unknown whether or not there is an algorithm for solving such equations. It seems a bit surprising that this is the case, but the rational case has resisted progress now for decades: was solved in 1970 while is still open. Since it lasted past the millennium, we think of this as Hilbert’s problem 10.5.
Shlapentokh, in her paper, discusses what is known about the rational case. I gather that the belief is that HTP over the rationals will also be undecidable; I also gather that the belief in this outcome is not as sure as some of the beliefs that we have in complexity theory. Are mathematicians more open-minded? Or is the evidence still mixed enough that HTP() could go either way?
There is an ancient joke about how mathematicians think—the punch line is “move the pail to the corner of the room.” I am sure you all have heard it.
One approach to showing that HTP() is also undecidable is to use this method: reduce the rational case to the previously solved problem for the integers. In order to do this we need to be able to define the integers by polynomials over the rationals. Suppose that there were a polynomial so that
- If is an integer, then there are rationals so that .
- If for rationals, then is an integer.
We use this to reduce the solution to any integer equation to one over the rationals. Let be an integer equation we wish to solve. Then we consider the family of equations:
It is not hard to prove that these three equations have a solution over the rationals if and only if has one over the integers.
But wait. HTP() allows only one equation not several. Luckily it turns out that equations over rationals are easily seen to be closed under AND and also OR. The equations and are both satisfied if and only if
The operation OR follows by considering
Shlapentokh’s paper goes into some details on approaches to defining integers in the theory of rationals. This is an open problem. Even worse there is some evidence that it may be impossible. Again see her paper for the details.
Julia Robinson, back in her seminal thesis, showed a number of beautiful results. One is that the integers are definable in the first-order theory of the rationals. This means that using quantifiers over the rationals and , , and equality it is possible to construct a formula so that
Shlapentokh paper explains, at a high level, how this is proved, and presents some recent advances in improving Robinson’s work. But all the improvements still need both universal and existential quantifiers. So this approach is stuck at the moment.
As a complexity theorist I wonder if we cannot yet show that HTP() is undecidbale, can we at least should that it is computationally hard? I asked Shlapentokh this just recently, and she said she was unaware of any such results. The following is a trivial lower bound:
Theorem: The problem HTP() is -hard.
There are many ways to prove this. One is a simple encoding of the Knapsack Problem via
with the additional equations , for all . Use the above AND trick to make these equations into one equation.
I cannot believe that this is the best—I must be missing something basic here. I think there should be two improvements. One is that HTP() should at least be -hard for a fixed number of variables; the above construction uses variables. Another is that HTP() should require at least exponential time, but I cannot prove this.
I have a concrete idea for showing that a constant number of variables are enough to render HTP() is hard. It is based on an early result of Robinson. Define the set
Robinson proved that this could be defined over using only existential quantifers, for any fixed prime . That means that there is a polynomial whose solutions define this set. If we could extend this to any fixed composite, then we could prove:
Conjecture: HTP() is -hard for a fixed number of variables.
There seem to be several very interesting problems here. The one that perhaps we can help with is to show that HTP() is really hard.
Note: There is a conference this August at Brown on . At least one of the talks are on various aspects of HTP. Unfortunately neither I nor Ken can be attend, so perhaps someone can help us report on the conference? Let me know if you wish to “guest” post on the conference.