On the problem of polynomial bijection from $\mathbb Q\times\mathbb Q$ to $\mathbb Q$

The question titled "Polynomial bijection from $\mathbb Q\times\mathbb Q$ to $\mathbb Q$" which was posed on MathOverflow attracted quite a lot of attention (and may be the question with most wrong answers ever asked on the website according to the comments of other users).

I have gone through some of the comments and realized that this question is related to the "abc conjecture" as well as to the "Bombieri-Lang conjecture".

Would you explain (in a way that is precise but accessible to an undergraduate student)

• why is this problem so difficult and what its solution would imply;

• what are its relationships with the "abc conjecture" and the "Bombieri-Lang conjecture";

• and what are the major reference papers on the topic (have there been any major progresses recently in ideas and methods to tackle the question)?

I see that it also not known if there is an injection. What are the differences between the problems in respect with the three points listed above?

Solution 1:

What would the solution of this problem imply? It could be a first step towards proving H10Q, Hilbert's tenth problem over the rationals.

This is a major open problem: Given an equation $$P(x,y,\ldots,z)=0,$$ is there an algorithm to determine if it has rational roots?

We might make progress by paralleling the answer for Hilbert's tenth problem, H10Z, which is the corresponding question over the integers. That problem has a negative solution: no algorithm can take a polynomial and determine whether it has integer roots.

The proof of H10Z works by emulating Turing-machine computation using polynomials over the integers, as in Davis. It starts with the small step of emulating pairing using polynomials, using an injective function $N \times N \rightarrow N$: $$u(a,b)=\frac{1}{2}(a+b-2)(a+b-1)+b.$$

To see why this is useful, follow Davis's procedure to find a polynomial $P$ such that $$y=\prod_{k=1}^x(1+k^2)\ \leftrightarrow\ \exists z_1,\ldots,z_m \in \mathbf{N}\ P(x,y,z_1,\ldots,z_m)=0.$$ The very first steps, starting with Davis's theorem 1.1, require the use of a pairing function like $u$.

H10Q can be seen as asking whether polynomials over the rationals can emulate Turing machines in the same way as polynomials over the integers. To solve H10Q by paralleling the proof of H10Z, a natural first step is to look for a polynomial pairing function like $u$ above, and that would be an injection $Q \times Q \rightarrow Q$.

The undergraduate-level references for this seem limited. Most papers on H10Q approach it differently, via Diophantine definitions of the integers in the rationals, so they motivate this problem but don't help to solve it. Hardy and Littlewood's Theory of Numbers may be a good reference for the negative result that no quadratic polynomial can work. Poonen's paper linked in the MO question has a positive result on higher-degree polynomials, relying on the above-mentioned conjectures from algebraic geometry. We might get an undergraduate-level answer eventually, but the current path is more advanced.