It is known that the polynomial $f(n,m)=\frac{1}{2}(n+m)(n+m+1)+m$ defines bijection $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ (Put pairs of $\mathbb{N}$ into the semi-infinite matrix and count them by diagonals). Does there exist a polynomial bijection $\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$? The question is related to the open question about polynomial bijection $\mathbb{Q}\times\mathbb{Q}\to\mathbb{Q}$ here.

  • 5
    $\begingroup$ Related but not decisive: thehcmr.org/issue1_2/bert_and_ernie.pdf $\endgroup$ Dec 28 '12 at 6:53
  • 6
    $\begingroup$ [It's also AMM 6028, which remains unsolved as far as I know.] $\endgroup$ Dec 28 '12 at 7:02
  • 4
    $\begingroup$ @Dickman: It took a me a while to know what you were talking about. Let me add the link books.google.es/books?id=KX6D6hefyA0C&pg=217 $\endgroup$
    – boumol
    Dec 28 '12 at 11:44
  • 6
    $\begingroup$ @Dicman and @Boumol: Thank you for interesting references. Interesting, AMM6028 asks for polynomials with integer coefficients. In fact, the bijection $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ I know has rational coefficients. Does there exist polynomial $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ bijection with integer coefficients? $\endgroup$ Dec 28 '12 at 18:32
  • 3
    $\begingroup$ Updated: zacharyabel.com/papers/Favorite-Problem_A07_HCMR.pdf $\endgroup$
    – Steve D
    Mar 9 '16 at 22:09

It is an open problem. Maximal results about bijections from $\mathbb N\times \mathbb N$, $\mathbb Z\times \mathbb N$, $\mathbb Z\times \mathbb Z$ to $\mathbb N$ are contained in

John S. Lew, Arnold L. Rosenberg, Polynomial indexing of integer lattice-points I. General concepts and quadratic polynomials, J. Number Theory 10 (1978) pp 192-214, doi:10.1016/0022-314X(78)90035-5.
Polynomial indexing of integer lattice-points II. Nonexistence results for higher-degree polynomials, J. Number Theory 10 (1978) pp 215-243, doi:10.1016/0022-314X(78)90036-7

  • 1
    $\begingroup$ I edited the references and links. $\endgroup$ Mar 10 '16 at 7:05

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.