Skip to content

Hilbert’s Tenth Over The Rationals

August 7, 2010


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 {f(x,y)} so that

\displaystyle  f:\mathbb{Q}^2 \rightarrow \mathbb{Q}

is a bijection? That is, can we map pairs of rational numbers {(x,y)} to one rational number {z} 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 {\mathbb{Q}^2} and {\mathbb{Q}} are countable. The usual proof that {\mathbb{Q}} is countable arranges the rational numbers into a sequence of the form:

\displaystyle  0, 1, -1, 2, -2, 1/2, -1/2, 3, \dots

The fractions {r/s} are arranged based on the size of {r} and {s}. 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 {f:\mathbb{Q}^2 \rightarrow \mathbb{Q}} that is one-to-one, let alone being bijective? This is believed for many polynomials such as {f(x,y) = x^7 + 3y^7}, 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 {\mathbb{Q}}.

Theorem: If the BC is true, then for any {n \ge 2}, there is a bijection

\displaystyle  f:\mathbb{Q}^n \rightarrow \mathbb{Q}

where {f} is a polynomial mapping.

The proof of this is quite simple, and I will give the proof for {n=4}. Define

\displaystyle  g(x,y,u,v) = f(f(x,y),f(u,v)).

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

Suppose that {g(x,y,u,v) = g(x',y',u',v')} for some rationals. Then,

\displaystyle  f(f(x,y),f(u,v)) = f(f(x',y'),f(u',v')),

which implies that {f(x,y) = f(x',y')} and {f(u,v) = f(y',v')}. This follows since {f} is injective. Then, clearly {x=x'} and {y=y'} and {u=u'} and {v=v'}.

Next suppose that {z} is some rational number. There are {a,b} rational so that {f(a,b) = z}. Further, there are {x,y} and {u,v} so that {f(x,y)=a} and {f(u,v) = b}. This implies that

\displaystyle  g(x,y,u,v) = f(f(x,y),f(u,v)) = f(a,b) = z.

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 {P(x_1,x_2,\dots,x_m)} 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 {x_1,x_2,\dots,x_m} 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

\displaystyle  \exists y_1 \dots \exists y_n \ R(x,y_1,\dots,y_n) = 0

is true for a rational {x} if and only if {x} 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 {a,b} so that

\displaystyle  P(a,b) = 0

is equivalent to the existence of rationals {a,b} so that

\displaystyle  \exists y \exists z \ R(a,y)^2 +R(b,z)^2 + P(a,b)^2 = 0.

Here {y} denotes an {n}-tuple {y_1,\dots,y_n}, and {z} denotes {z_1,\dots,z_n}.

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 {\forall} and {\exists} 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

\displaystyle P(x_1,\dots,x_n) = 0.

Let {\Sigma^*} denote those where all the prenex quantifiers are existential, and let {\Pi^*} where they all are universal quantifiers. We can mix these as usual; thus,

\displaystyle  \Sigma^* \Pi^* \Sigma^*

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

\displaystyle  \Sigma^* \Pi^2 \Sigma^*

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

In this notation, Poonen proves:

Theorem: There is a {\Pi^2 \Sigma^* } formula that defines the integers.

Thus, formulas of the form: {\Sigma^* \Pi^2 \Sigma^* } 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:

\displaystyle  L = (a+x_1^2+x_2^2+x_3^2+x_4^2)(b+x_1^2+x_2^2+x_3^2+x_4^2)\Delta

where

\displaystyle  \Delta = ( x_1^2 -ax_2^2-bx_3^2+abx_4^2-1) + \prod_{n=0}^{2309} \left((n-x-2x_1)^2-4ay_2-4by_3^2+4aby_4^2-4 \right)^2.

Define {\psi(x)} to be

\displaystyle  \forall a \forall b \exists x_1 \dots \exists x_4 \exists y_2 \dots \exists y_4 \; L=0.

Then Poonen’s main theorem is:

Theorem: For all rational {x}, the formula {\psi(x)} is true if and only if {x} 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 {y} that only takes on non-negative rational values. You cannot use {y^2}, since while that is always non-negative, it misses many values. Joseph Lagrange’s famous four-square theorem comes to the rescue. Just use

\displaystyle  y = x_1^2 + x_2^2 + x_3^2 + x_4^2.

By his theorem, {y} 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

\displaystyle  \Sigma \ \Pi \ \Sigma^*

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

\displaystyle  	\forall x \forall y \ \mathsf{Q} \ \phi(x,y,\dots)=0 \ \ \ \ \ (1)

where {\mathsf{Q}} denotes a string of quantifiers of any type and {\phi} is a polynomial. Then, this formula is equivalent to

\displaystyle  	\forall z \ \mathsf{Q} \ \exists x \exists y \ [f(x,y) -z]^2 + \phi(x,y,\dots)^2 = 0. \ \ \ \ \ (2)

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

\displaystyle  \mathsf{Q} \ \phi(x_0,y_0,\dots) = 0

is true. Thus,

\displaystyle  \mathsf{Q} \ \exists x \exists y \ [f(x,y) -z_0]^2 + \phi(x,y,\dots)^2 = 0

is true: set {x = x_0} and {y = y_0}. 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 {x_0} and {y_0} so that

\displaystyle  \mathsf{Q} \ \phi(x_0,y_0,\dots) \neq 0.

Set {z_0 = f(x_0,y_0)}. Consider the formula

\displaystyle  \mathsf{Q} \ \exists x \exists y \ [f(x,y) -z_0]^2 + \phi(x,y,\dots)^2 = 0.

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

\displaystyle  \mathsf{Q} \ \phi(x_0,y_0,\dots) = 0

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:

\displaystyle  \exists x \exists y \ \mathsf{Q} \ \phi(x,y,\dots)=0

and

\displaystyle  \exists z \ \mathsf{Q} \ \exists x \exists y \ [f(x,y) -z]^2 + \phi(x,y,\dots)^2 = 0.

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 {x=x_0} and {y=y_0}. Then, set {z=f(x_0,y_0)}. Clearly, the second formula is true. Suppose next the second formula is true, and the first is false. Then,

\displaystyle  \mathsf{Q} \ \phi(x,y,\dots) \neq 0

for all {x} and {y}. Also for some {z_0} the formula

\displaystyle  \mathsf{Q} \ \exists x \exists y \ [f(x,y) -z_0]^2 + \phi(x,y,\dots)^2 = 0.

is true. There must be {x_0} and {y_0} so that {f(x_0,y_0)=z_0}, since {f} is onto. But then,

\displaystyle  \mathsf{Q} \ \phi(x_0,y_0,\dots) = 0,

which is a contradiction.

\Box

Open Problems

Can there really be a bijection from {\mathbb{Q}^2} to {\mathbb{Q}} 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 {n} tuples of rationals to one rational, by a polynomial map, must have other applications in computational complexity.

[fixed typo]

About these ads
13 Comments leave one →
  1. August 7, 2010 2:10 pm

    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.

  2. anonymous permalink
    August 8, 2010 12:58 am

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

    sum of four squares

    • rjlipton permalink*
      August 8, 2010 11:09 am

      Thanks for typo.

      Two -> Four will fix.

  3. August 8, 2010 6:24 am

    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

    • rjlipton permalink*
      August 8, 2010 11:07 am

      Noon,

      Great to point out. It is very relevant.

      Thanks

  4. SubtleLisp permalink
    August 13, 2010 8:27 am

    Ernie Croot III was a postdoc at UC Berkeley.

  5. January 3, 2012 9:28 pm

    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.

    • January 3, 2012 10:11 pm

      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.

Trackbacks

  1. World Wide News Flash
  2. Fermat’s Last Theorem Proof by Tom Ballard « INNOWORLD
  3. David Hilbert Speaks « Gödel’s Lost Letter and P=NP
  4. Hilbert’s 10.5th Problem « Gödel’s Lost Letter and P=NP
  5. Rough Problems | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,224 other followers