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?

  • 17
    $\begingroup$ This sounds like a request for a 20 page expository article on the problem. Isn't that a bit too tall of an order for MSE? $\endgroup$
    – RghtHndSd
    Dec 10, 2014 at 19:17
  • 2
    $\begingroup$ I have voted to close this as too broad, but I suggest to the OP that maybe trimming some focus would make it eligible for re-opening. There is more than a thread of a legitimate question here for sure. If anything, I don't think the question is too broad, but too deep. $\endgroup$
    – Emily
    Dec 10, 2014 at 20:24
  • 7
    $\begingroup$ @RghtHndSd I have seen topics which have entire books about them, that are bigger and more famous than this problem (e.g. stuff related to the Riemann zeta function), yield excellent answers on this site surveying the topic. Let's say every page worth of condensed, survey exposition covers the same amount of material as a couple dozen pages of detailed writing. Have you personally come across five hundred pages worth of material on this single question that I hadn't even heard of before seeing it here? It's possible I suppose, but when you begin your comment with "it seems," I am skeptical. $\endgroup$
    – anon
    Dec 11, 2014 at 23:12
  • 4
    $\begingroup$ I have voted to reopen. This question strikes me as the type for which, if someone was knowledgeable enough to answer, they could do so relatively easily, and within a fraction of the character limit for answers. $\endgroup$
    – anon
    Dec 11, 2014 at 23:21
  • 2
    $\begingroup$ @anon: The question has been edited and several of the things listed are now removed. You mention that one can survey a large topic - sure. However, the way the question was previously asked, it sounded like it was not asking for a summary, it sounded like it was asking for a full exposition. I wrote this in the hope that the author would provide clarification. $\endgroup$
    – RghtHndSd
    Dec 12, 2014 at 0:03

1 Answer 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.

  • $\begingroup$ "Hardy and Littlewood's Theory of Numbers" ? Any precise reference? (or was it "Hardy and Wright"?) $\endgroup$
    – Wlod AA
    Mar 21, 2020 at 5:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.