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:

• Some easy facts or getting getter acquainted
• Becoming more ambitious
• Some unpleasant thoughts
• ${\vdots}$
• 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.

HTP

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:

$\displaystyle \dots,-3,-2,-1,0,+1,+2,+3,\dots$

More formally, given an integer polynomial ${f(x_{1},\dots,x_{m})}$, it asks whether there are integers ${a_{1},\dots,a_{m}}$ so that

$\displaystyle f(a_{1},\dots,a_{m}) = 0.$

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 ${f(a_{1},\dots,a_{m})}$ 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 ${\mathsf{P}=\mathsf{NP}}$ problem: Where are the movies? Well there are movies on HTP.

Rationals

Let HTP(${R}$) be the following generalization of Hilbert’s Problem to polynomials over the ring ${R}$. Now we ask, given a polynomial ${f(x_{1},\dots,x_{m})}$ with coefficients from ${R}$, is there a solution ${a_{1},\dots.a_{m}}$ so that

$\displaystyle f(a_{1},\dots,a_{m}) = 0.$

When ${R}$ is the integers ${\mathbb{Z}}$ this is the original HTP, and we know that it is unsolvable in general.

What happens when we change the ring to the rationals ${\mathbb{Q}}$? 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: ${\mathbb{Z}}$ was solved in 1970 while ${\mathbb{Q}}$ 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(${\mathbb{Q}}$) could go either way?

An Approach

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(${\mathbb{Q}}$) 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 ${g(w_{1},\dots,w_{m},x)}$ so that

1. If ${x}$ is an integer, then there are rationals ${w_{1},\dots,w_{m}}$ so that ${g(w_{1},\dots,w_{n},x) = 0}$.
2. If ${g(w_{1},\dots,w_{m},x) = 0}$ for rationals, then ${x}$ is an integer.

We use this to reduce the solution to any integer equation to one over the rationals. Let ${f(x,y) = 0}$ be an integer equation we wish to solve. Then we consider the family of equations:

$\displaystyle \begin{array}{rcl} f(x,y) &=& 0 \\ g(r_{1},\dots,r_{m},x) &=& 0 \\ g(s_{1},\dots,s_{m},y) &=& 0. \end{array}$

It is not hard to prove that these three equations have a solution over the rationals if and only if ${f(x,y) = 0}$ has one over the integers.

But wait. HTP(${\mathbb{Q}}$) 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 ${h_{1} = 0}$ and ${h_{2} = 0}$ are both satisfied if and only if

$\displaystyle h_{1}^{2} + h_{2}^{2} = 0.$

The operation OR follows by considering

$\displaystyle h_{1} h_{2} = 0.$

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 ${+}$, ${\times}$, and equality it is possible to construct a formula ${\Gamma(x)}$ so that

$\displaystyle \Gamma(x) \text{ if and only if } x \in \mathbb{Z}.$

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.

Complexity Theory

As a complexity theorist I wonder if we cannot yet show that HTP(${\mathbb{Q}}$) 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(${\mathbb{Q}}$) is ${\mathsf{NP}}$-hard.

There are many ways to prove this. One is a simple encoding of the Knapsack Problem via

$\displaystyle \sum_{k} a_{k}x_{k} = b,$

with the additional equations ${x_{k}(x_{k}-1) = 0}$, for all ${k}$. 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(${\mathbb{Q}}$) should at least be ${\mathsf{NP}}$-hard for a fixed number of variables; the above construction uses ${n}$ variables. Another is that HTP(${\mathbb{Q}}$) should require at least exponential time, but I cannot prove this.

An Idea?

I have a concrete idea for showing that a constant number of variables are enough to render HTP(${\mathbb{Q}}$) is hard. It is based on an early result of Robinson. Define the set

$\displaystyle Int_{q} = \{ x \in \mathbb{Q} \mid x = \frac{a}{b}, a,b \in \mathbb{Z}, b \not\equiv 0 \bmod q \}.$

Robinson proved that this could be defined over ${\mathbb{Q}}$ using only existential quantifers, for any fixed prime ${q}$. 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(${\mathbb{Q}}$) is ${\mathsf{NP}}$-hard for a fixed number of variables.

Open Problems

There seem to be several very interesting problems here. The one that perhaps we can help with is to show that HTP(${\mathbb{Q}}$) is really hard.

Note: There is a conference this August at Brown on ${\mathsf{P}=\mathsf{NP}}$. 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.

1. July 19, 2011 8:02 am

If Hilbert’s 10th problem turns out to be solvable over $\mathbb{Q}$, I think it will require some deep number theory. For example it’s known that Hilbert’s 10th Problem is solvable over $\mathbb{Q}_p$ and over $\mathbb{R}$, so the fact that it’s not known to be solvable over $\mathbb{Q}$ indicates that failure of the Hasse principle is at the heart of the matter, and there is a lot of work in this direction. (In fact my understanding is that there is no unconditional solution to Hilbert’s 10th problem even in the very special case of rational points on elliptic curves, and the conditional solution basically assumes that the failure of the Hasse principle can be made finite.)

Bjorn Poonen wrote a very nice survey on this subject, although it may be outdated now. Apparently it’s not known whether or not it could be possible for Hilbert’s 10th problem to be solvable over some number fields and not others, which would be a fascinating thing to know about number fields.

2. July 19, 2011 11:47 am

Weiming has launched a web site http://www.cognitivelogic.org and announced thier solution of P=NP.

July 19, 2011 7:00 pm

… or how to recycle famous mathematical puzzles into spam.

3. July 19, 2011 2:42 pm

One important thing to note is that for a lot of rings R, HTP(R) is known to be true. For example, HTP(Z[i]). In contrast, HTP for the reals is false (since first order real arithmetic is complete). It seems that for pretty much every ring R that we understand things well we have either HTP(R) or we have a decision procedure for the solvability diophantine equations over R. Q is a very interesting case in that regard, in that it is reasonable to think it might fall in a middle ground, with HTP(Q) false but no decision procedure for diphohantine equations over Q.

4. July 20, 2011 3:47 am

HTP(Q) is at least as hard as the existential theory of the real numbers (the series of reductions goes as follows: existential theory of the reals can be encoded as solvability of a set of strict inequalities over the reals which is then equivalent to solvability of strict inequalities over the rationals [since the rationals are dense], and solvability of a set of strict inequalities over the rationals can be rephrased as solvability of f(q1, … qn) = 0 using standard tricks). This means that HTP(Q) is at least as hard as deciding the sum of square root problems, the (Euclidean) minimum weight triangulation and many other problems that are not known to lie in NP.

Since the existential theory of the reals lies in PSPACE, this suggests that encoding anything in HTP(Q) above PSPACE has to rely on properties of the rationals that are not shared by the real numbers.

5. July 20, 2011 9:23 am

Gödel’s Lost Letter and P=NP is off to a fine start for its fourth century! In addition to Sasha Shlapentokh’s excellent article, please let me commend also one of the articles that her survey references, namely Barry Mazur’s Questions of decidability and undecidability in number theory (1994), which asks:

It may now be an appropriate time for number theorists and logicians to take a closer look at Diophantine families whose integral solutions are undecidable. Can one gain some clue concerning their undecidability from their algebraic geometry, their Hodge theory, their differential geometry, or perhaps, the structure of their rational solutions?

As several recent Gödel’s Lost Letter and P=NP columns have discussed, this Shlapentokh-Mazur approach for understanding decidability is broadly effective too in understanding computational complexity, simulability, verification, etc.

It is natural to wonder, what might be some longer-term consequences of this increasingly integrated appreciation of universality, naturality, and decidability? Here Tim Gowers’ recent comment on Gödel’s Lost Letter: Make Your Own World provides concrete guidance. To appreciate this guidance, we can cast the question that Dick asked and Tim answered, namely “What would you do if you could make your own world?”, into the form of a practical engineering assertion. For this purpose we start with the following general-purpose template, which physicist Julian Schwinger’s students lovingly distilled from Schwinger’s own articles and lectures:

“Although ‘1’ is not perfectly ‘0’ we can effectively regard …”

In the case at hand Schwinger’s template guides us in extending Lipton’s question and Gowers’ answer from the domain of fantasy to the domain of practice as follows:

“Although ‘NP’ is not formally separable from ‘P’ we can effectively regard them as separable whenever our main focus is mathematical understanding as contrasted with rigorous proof. Similarly, although ‘Hilbert space’ is not perfectly a ‘secant-Segre variety’ we can effectively regard it as such whenever our main focus is dynamical understanding as contrasted with quantum computation.”

To the extent that Tim Gowers’ second world becomes real in the 21st century, the preceding is a concise Schwinger-style description of what it might look like.

Viewed in this practical light, a theme that is shared by several recent Gödel’s Lost Letter columns, and by the Shlapentokh and Mazur articles, and by the recent comments by Gowers and GASARCH (and by many other commenters too) is that while we patiently await definitive answers to questions that may be logically infeasible to decide (like P versus NP) or physically infeasible to observe (like quantum state-space’s affine varietal structures), we have the option of concurrently working to evolve a 21st century “Standard Model of Computation” that — like the 20th century Standard Model of Physics — rests upon foundations of Mazur-Lipton-Gowers-Shlapentokh-type that are … well … beautifully empirical.

The result would be an immensely exciting and productive 21st century to live in. This I take to be the practical point of Tim Gowers’ extraordinary “two worlds” post, and also, the main reason Gödel’s Lost Letter and P=NP is such an interesting weblog.

July 20, 2011 9:35 am

Sorry for the mundane request, but I am curious about the joke you cite. Could you please tell the rest of it?

• July 20, 2011 12:35 pm

I’m not sure I know that exact version myself, but all versions play on the idea of thinking by “reducing” a problem to an already-solved case. Suppose you need to put out a fire and the pail is in the corner of the room. You solve this first problem by bringing the pail to the sink, filling it, and dousing the fire. Now suppose the pail is at the sink and another similar fire breaks out. To demonstrate that you can solve this second problem, all you have to do is move the pail to the corner—then you can refer to the solution of the first problem.

Of course this is not the most expeditious way to put out a fire. But often you can save time and space in a paper by saying a lemma follows from some other result in the literature, even if this misses a stronger truth that might be usable (later) to improve your main theorem.

July 21, 2011 7:38 pm

Oh, Yes, I see it! =)

But, personally, I am not sure space is the (only) matter. Mathematicians seem to consider modularity and/or simplicity as measures of the much desired “elegance” of a proof. So keeping a proof simple by simply using a known lemma usually look like a natural choice…

July 20, 2011 2:40 pm

Here’s a version from http://www.sonoma.edu/math/faculty/falbo/jokes.html:

An engineer and a mathematician shared an apartment. Their kitchen was equiped with an electric stove, and every morning someone had placed a pot of water on the back-right burner so they could make coffee. They both knew what knob turned on this burner. One morning the engineer came into the kitchen and found the pot was on the front-left burner. He got out the stove’s schematics and followed the wiring diagram and finally figured out which knob turned on this burner and he then used that knob and made the coffee. The next moring the mathematician came in and also found the pot on the front-left burner. He moved the pot to the back-right burner, thereby reducing the problem to one which he had already solved.

July 20, 2011 11:25 am

Usually people who try to discover the famous P versus NP problem say “I have solved it”. For me, personally, it seems a bit pretentious to announce such discovery as a fact. I also think it will be difficult for a non-expert in the subject to solve it; this possibility would be like the probability of one in a million. Since 6 years ago I spent my time trying to solve this problem as a hobby and I have found that the model of Turing machines is a great tool to demonstrate that result. I also think, that a trivial way to prove a result in this field is proving that the language sets P and NP are disjoint, demonstrating that there is a problem in NP that is not in P. I upload to Arxiv the version number 11 which although it maybe have trivial mistakes, such as lack of proficiency in English, still remain me convinced since a few months ago. I want someone to refute my arguments, but I am just a lover of the subject outside the academic circuit, I have no one does. Please help me, here is the address:
http://arxiv.org/abs/1011.2730
(Version 11)

July 21, 2011 5:26 pm

Same comment as above.

August 2, 2011 8:13 am

Serge your comment seems me like another that i received the last week and cited:
I don’t see a bad intention in that phrase, however is a little pessimistic and skeptical.
But i going tell you that the person who wrote this email questioned in some way that the Integer multiplication with one fixed value and other variable can be unique for each chosen variable with the value and in operations in bits. This doubt is ridiculous, nevertheless it helps me to improve my paper, because i realize that he doesn’t understand nothing at all.
I challenge you: Could you give some reasons to believe that i am definetly wrong?
Maybe you can, maybe not.
But if you try i would be very thankful for that.
Good luck Serge and thank you for your comment.

August 2, 2011 8:23 am

See version 13…

August 2, 2011 4:04 pm

OK Frank, just let me some time to read it thoroughly. The problem is, I’m not a professional either but I promise you to take a close look at your candidate solution.

August 5, 2011 8:10 am

Serge I forgot to tell you: if you have any doubt of my paper you can email me. I am just an amateur and my English is not very good, however i going to try to explain whatever it comes from your reading. I don’t have your email; if you email me i will answer you the next week when i am available. Until then…

August 5, 2011 5:11 pm

Frank, it seems that your argument relies on too many details of the model of Turing machines, whereas it should work in any computing model. I wonder if you could rephrase it in some pseudo programming language. I’m not saying that anything is wrong in it, but it’s so hard to understand… I think you should try to rephrase the core of your argument in good English (or in good Spanish) in order to be able to explain it to any advanced student in math, or even to summarize it into a short comment on this blog.

August 8, 2011 8:08 am

Serge i going to explain you in few words my arguments, but remember that my English is not so good, nevertheless i going to try to help you to understand a little. Turing in the past century shows a problem that any Turing machine can’t decide (when i mean decide i want to say if it can determine the answer is yes or no) named the Halting Problem. Turing also shows what is know in nowdays as reductibility, which means reduce a turing machine in another. Using this techniques it found many others undecidable problems. I took one of those problems and i reduce to my own new undecidable problem and i found another problem too, which i proved that belong in the NP class and i called it Certifying. These two problems have the following relation: if the np problem (Certifying) would be in P then it will imply that this undecidable problem will be in NP too. This result means that Certifying can’t belongs to P class because it will imply a contradiction, the reason is this:any undecidable problem can’t belong to NP class because the NP problems are decidable. The another details you must try to understand making a slowly and carefully reading of the paper, however i will taking to account what you said, although i must warn you: my paper can be difficult to understand for people who don’t have enough knowledge in the Turing model and another complexity issues. Thanks and good luck….

August 8, 2011 8:40 am

OK I see. If there’s no mistake in all this you deserve the Millennium Prize. But it’s so important that you should indeed try to replace the Turing machines by your favourite algorithmic language. And if there happened to be a little mistake somewhere you could catch it immediately.

August 8, 2011 10:06 am

I am actually conscious that any trivial error in the rest of the paper can overthrow my intend, that’s why i don’t claim for that prize, i’m only searching for people for discuss my arguments: this is what i love. I also realize that my argument can seem you a little difficult and i was thinking, how can i give you a hint? And i quickly came this idea into my mind, i gonna expose you like a question, maybe in this way you will understand much better:
Can you delimit the output of all pseudo programming language always in polynomial size (with a constant exponent as large as you want) with respect the input?
My answer is no: this is what i think is the achilles heel of my paper. As you see is very simple but i try to make it the whole proof in a rigorous way. Maybe is not the best way (for example i assume that the reader understand that in case where i don’t mentioned in which tape is going to put the input, i always put in the first tape), maybe it can has trivial errors, however i am almost convinced that something good can show my intend.

August 8, 2011 10:49 am

I can’t answer your question but at least it should be possible for you to rewrite your argument by means of single tape machines only. The simpler the tools, the easier the understanding.
Good luck Frank with your research!

August 8, 2011 1:02 pm

Thank you Serge…

August 3, 2011 8:48 am

When i said ” the language sets P and NP are disjoint” i actually want to say ” the language sets P and NP are different” which is no the same. My native language is not the English and i made a mistake on writing that comment.

August 3, 2011 1:23 pm

I will put a fragment of my abstract for avoid being misunderstood again:
“The existence of a language in NP, proven not to belong to P, is sufficient evidence to establish the separation of P from NP. If a language is not recursive, it can’t belong to the complexity class NP. We find a problem in NP which is not in P; because if it would be present in that class, then it will imply that some undecidable problem will be in NP too. That’s why it can be confirmed by reduction ad absurdum the following result: P doesn’t equal NP.”
Waiting for criticism, like they say…