# Hilbert’s Tenth Over The Rationals

* Can there be a bijection from pairs of rationals to rationals? *

Bjorn Poonen is a famous number theorist at MIT, who has many honors and awards, including being one of the few four time Putnam Exam winners. He has worked on many aspects of number theory, including the “dark side” as he calls it. The dark side consists of results that show that something is undecidable.

Today I plan on discussing one of the simplest to state open problems that I have heard in years. The problem is from number theory, which has many simple to state, but impossible problems. Hopefully, this problem can be solved.

One must always recall the great Carl Gauss’ quote:

I confess that Fermat’s Theorem as an isolated proposition has very little interest for me, because I could easily lay down a multitude of such propositions, which one could neither prove nor dispose of.

Number theory is filled with such innocent sounding problems that are impossible to resolve.

Perhaps Gauss was wrong about this particular example—Fermat’s Theorem turned out to be central to modern number theory—but he is certainly right in general. Perhaps Fermat is “the exception that proves the rule.” Too bad this phrase is not a real logical rule—proving theorems would be much easier, if it were. See this for an interesting discussion on what

“the exception that proves the rule”

really means.

Poonen has at least one strong connection to Georgia Tech—he worked with one of our mathematics faculty, Ernie Croot, when Ernie was a post-doc at MIT. Ernie is terrific and has done some very neat work that I will discuss in detail another day.

** The Problem **

The open problem is: does there exist a polynomial map so that

is a bijection? That is, can we map pairs of rational numbers to one rational number so that the map is one-to-one and onto? Further, the map must be defined by a polynomial. We know that such bijections exist from Georg Cantor’s famous work, since both and are countable. The usual proof that is countable arranges the rational numbers into a sequence of the form:

The fractions are arranged based on the size of and . But, this sequence is quite messy, and is far from being definable by a polynomial.

In a sense the shock of this question, let’s call it the **Bijection Conjecture** (BC), is that it is open at all. How can there be such a mapping? The method of Cantor clearly yields a very complicated function. How could a function from pairs of rationals map to single rationals and be a polynomial? Seems unlikely, but of course who knows.

The problem was first raised by the famous logician Harvey Friedman. He asked several related questions about other possible mappings. For instance, does there even exist a polynomial that is one-to-one, let alone being bijective? This is believed for many polynomials such as , but nobody has proved even one. These problems have enjoyed some recent interest. which I attribute partly to this paper by Poonen, to Andy Drucker who discussed it and related questions on his excellent blog, and to the discussion on the math-overflow site.

** A Simple Consequence **

There are two simple consequences of the BC. The first shows that a bijection exists for any number of copies of .

Theorem:If the BC is true, then for any , there is a bijection

where is a polynomial mapping.

The proof of this is quite simple, and I will give the proof for . Define

Clearly, is a polynomial. The key question is: is it a bijection?

Suppose that for some rationals. Then,

which implies that and . This follows since is injective. Then, clearly and and and .

Next suppose that is some rational number. There are rational so that . Further, there are and so that and . This implies that

** Relationship To Hilbert’s Tenth **

The second consequence concerns Hilbert’s Tenth problem (H10) and a potential generalization to rationals. It is a result that is related to questions, as Poonen says, from the dark side of number theory. I shall talk about this connection for the rest of this post.

One of the most celebrated such results is that deciding whether or not a polynomial has an *integer* solution is undecidable. This is the famous negative solution to Hilbert’s Tenth. An obvious question, which is still open, is what happens if we ask for solutions where the are allowed to be rationals? This is open—I discussed it recently as a potential million dollar problem.

An approach to proving that H10 extended to the rationals is also undecidable is to show that the integers are definable by a polynomial formula. Suppose

is true for a rational if and only if is actually an integer. Note, the quantifiers range over rationals. Then, we can transform a question about integers into a question about rationals—this would show that H10 for rationals is also undecidable. For example, the existence of integers so that

is equivalent to the existence of rationals so that

Here denotes an -tuple , and denotes .

This idea goes back to the early work of Julia Robinson, who proved in her Ph.D. thesis that the integers *were* definable in the first order theory of rationals. This proves that the first order theory of rationals is undecidable.

The question is whether the restriction of that theory to formulas with existential quantifiers only, whose body is a single polynomial set equal to zero, is likewise undecidable. Robinson’s undecidable formulas had several levels of alternating and quantifiers, making them relatively complex. Over the years there have been improvements, and the best known is, I believe, due to Poonen.

** Defining Integers Via Rationals **

Let’s consider formulas of the form: a series of prenex quantifiers and then a polynomial equation

Let denote those where all the prenex quantifiers are existential, and let where they all are universal quantifiers. We can mix these as usual; thus,

denotes first existential, then universal, and last existential. We will also allow, for example,

to denote formulas where the block of universal are just two quantifiers.

In this notation, Poonen proves:

Theorem:There is a formula that defines the integers.

Thus, formulas of the form: are undecidable via the H10-based argument of the last section. See this other paper by Poonen for details. I will just show you what his formulas look like.

Consider the following definitions:

where

Define to be

Then Poonen’s main theorem is:

Theorem:For all rational , the formula is true if and only if is an integer.

Poonen’s paper makes clever use of quaternions, and properties of various Diophantine equations.

I can add one comment, which will decrease the mystery a bit about these formulas. Suppose at some point in such a formula you require a variable that only takes on non-negative rational values. You cannot use , since while that is always non-negative, it misses many values. Joseph Lagrange’s famous four-square theorem comes to the rescue. Just use

By his theorem, can take on any non-negative *rational* value. His famous theorem says that every natural number is the sum of four squares, but it is easy to extend his theorem to rational values.

** Using The BC To Define Integers **

I noticed BC implies the following simple theorem, which I am sure is known. But I thought it would be nice to point out the power of the BC conjecture.

Theorem:If BC is true, then the class of formulas of the form

is undecidable over the rational numbers.

Note, the above class of formulas is different in two ways from Poonen’s: the first existential quantifier is one variable and the universal quantifier is just one variable too.

*Proof:*

I will sketch the proof. The key insight is that assuming that BC is true allows us to reduce multiple quantifiers to one. More precisely, consider a formula of the form

where denotes a string of quantifiers of any type and is a polynomial. Then, this formula is equivalent to

Let’s prove that (1) implies (2). Assume that (1) is true and (2) is false. Then, there must be a so the latter is false. There are and so that , since the mapping is onto. But,

is true. Thus,

is true: set and . This is a contradiction.

Let’s now prove that (2) implies (1). Assume that (2) is true and (1) is false. Then, there must be and so that

Set . Consider the formula

This formula is true. Since the mapping is one-to-one, this implies that

is also true. This is a contradiction. The rest of the proof is that there is a similar transformation that works for existential quantifiers. The following two formulas are equivalent:

and

I will super sketch this result, since it is really almost the same as the case of universal quantifiers. Suppose the first formula is true for and . Then, set . Clearly, the second formula is true. Suppose next the second formula is true, and the first is false. Then,

for all and . Also for some the formula

is true. There must be and so that , since is onto. But then,

which is a contradiction.

** Open Problems **

Can there really be a bijection from to given by a polynomial?

I also believe that there should be other simple consequences of this strong assumption. Can we find other applications? I guess that the ability to map tuples of rationals to one rational, by a polynomial map, must have other applications in computational complexity.

[fixed typo]

### Trackbacks

- World Wide News Flash
- Fermat’s Last Theorem Proof by Tom Ballard « INNOWORLD
- David Hilbert Speaks « Gödel’s Lost Letter and P=NP
- Hilbert’s 10.5th Problem « Gödel’s Lost Letter and P=NP
- Rough Problems | Gödel's Lost Letter and P=NP
- A Quest For Simple Hard Statements | Gödel's Lost Letter and P=NP
- Diophantine Equations | Gödel's Lost Letter and P=NP
- The Halting No Go Theorem | Gödel's Lost Letter and P=NP

Nice post!

Another cool thing about Poonen is his interest in helping younger students get exposed to advanced math. I sat in on at least one of his engaging lectures at the Berkeley Math Circle while I was in high school.

> His famous theorem says that every natural number is the sum of two square

sum of four squares

Thanks for typo.

Two -> Four will fix.

I don’t know how relevant it is to this topic specifically (I don’t understand it well enough), but there was also this recent post to arXiv regarding Hilberts 10th, and is perhaps further reason for the current talk about it: http://arxiv.org/abs/1008.0809

Noon,

Great to point out. It is very relevant.

Thanks

Ernie Croot III was a postdoc at UC Berkeley.

Could you give a reference on a constructable bijection between tuples of rational numbers and a single rational number that isn’t required to be a polynomial? I take it from you blog that some such bijection exists.using the method of Cantor, but can it be given explicit closed form? Thanks.

I forgot to mention I am looking for a continuous bijection. That is a simpler problem than a polynomial bijection. I guess you could construct a discontinuous bijection by bit interweaving, i.e. the first digit of the coded rational is the first digit of the first of the pair of rationals, the second is the first digit of the second of the pair and so on. Thanks again. I noticed there haven’t been any recent posts here so I hope this post doesn’t get lost.