Are there exotic polynomial bijections from $\mathbb N^d$ onto $\mathbb N$?

Question

The Cantor bijection given by $$(x,y)\longmapsto {x+y\choose 2}-{x\choose 1}+1$$ is a bijection from $\{1,2,3,\dotsc\}^2$ onto $\{1,2,3,\dotsc\}$.

It can be generalized to bijections $\varphi_d:\{1,2,3,\dotsc\}^d \longrightarrow \{1,2,3,\dotsc\}$ given by $$(x_1,\dotsc,x_d)\longmapsto (d+1\bmod 2)+(-1)^d\sum_{k=1}^d(-1)^k{x_1+\dotsb+x_k\choose k}$$ where $(d+1\bmod 2)$ equals $1$ if $d$ is even and $0$ otherwise. (The proof is a sort of double induction on $d$ and on the sum $x_1+x_2+\dotsb+x_d$.)

It is of course possible to consider compositions of the above formulæ in order to get additional, more complicated polynomial bijections.

A straightforward counting argument shows that we obtain in this way $d! s_d$ different polynomial bijections between $\{1,2,\dotsc\}^d$ and $\{1,2,\dotsc\}$ where $s_1,s_2,\dotsc$ are the little Schroeder numbers with generating series $$\sum_{n=1}^\infty s_nq^n=\frac{1+q-\sqrt{1-6q+q^2}}{4}\ .$$

Are there other "exotic" polynomial bijections (between $\{1,2,\dotsc\}^d\longrightarrow \{1,2,\dotsc\}$)?

(The answer is obviously "no" for $d=1$ and unknown for $d=2$. I do not know if an "exotic" bijection is known for $d=3$.)

Added for completeness: Sketch of a proof that $\varphi_d$ is a bijection: We set $$A_d(n)=\{(x_1,\ldots,x_d)\in\{1,2,\ldots\}^d\ \vert\ x_1+x_2+\ldots+x_d=n\}$$ and $A_d(\leq n)=A_d(d)\cup A_d(d+1)\cup \ldots\cup A_d(n)$.

It is enough to prove that $\varphi_d$ induces a bijection between $A_d(\leq n)$ and $\{1,\ldots,{n\choose d}\}$.

This is clearly true for $d=1$ (and arbitrary $n$) and for $n=d$ with arbitrary $d$.

Since $(x_1,\ldots,x_d)\longmapsto (x_1,\ldots,x_{d-1})$ is a bijection between $A_d(n)$ and $A_{d-1}(\leq n-1)$ we have (using slightly abusing notations for sets) \begin{align*}\varphi_d(A_d(n))&= {n\choose d}-\left(\varphi_{d-1}(A_{d-1}(\leq n-1))-1\right)\\ &=\left\{{n\choose d}-{n-1\choose d-1}+1,\ldots,{n\choose d}\right\}\\ &=\left\{{n-1\choose d}+1,\ldots,{n\choose d}\right\} \end{align*} which ends the proof of the induction step.

Answer 1

Wikipedia says "The generalization of the Cantor polynomial in higher dimensions" is $$(x_1,\ldots,x_n) \mapsto x_1+\binom{x_1+x_2+1}{2}+\cdots+\binom{x_1+\cdots +x_n+n-1}{n}$$ Note that this is not equivalent to your generalisation $$(x_1,\ldots,x_d)\mapsto (d+1\bmod 2)+ \sum_{k=1}^d(-1)^{k+d}{x_1+\dotsb+x_k\choose k}$$ so the word "The" is misleading. Lew, Morales, and Sánchez proved (Diagonal polynomials for small dimension, Math. Sys. Th. 29 (1996) 305–310) that these two families give the only "diagonal polynomials" up to permutation of variables for dimension 3, where a "diagonal polynomial" is a bijection $\mathbb{N}^d \to \mathbb{N}$ which orders all tuples satisfying $x_1 + \cdots + x_d = k$ before any tuple satisfying $x_1 + \cdots + x_d = k + 1$. In the same edition Morales and Lew gave $2^{d-2}$ inequivalent (i.e. not related by permutation of variables) diagonal polynomials for higher $d$ (An enlarged family of packing polynomials on multidimensional lattices, Math. Sys. Th. 29 (1996) 293-303).

In follow-up papers, Morales (Diagonal polynomials and diagonal orders on multidimensional lattices, Th. Comput. Sys. 30 (1997) 367–382) showed that this was an undercount, and in particular listed 6 inequivalent diagonal polynomials for $d=4$; and Sánchez described A family of $(n-1)!$ diagonal polynomial orders of $\mathbb{N}^n$, Order 12 (1997).

Fetter, Arredondo, and Morales proved in The diagonal polynomials of dimension four, Adv. Applied Math. 34 (2005) 316-334 that the six polynomials which Morales and Sánchez describe are all the diagonal polynomials of dimension 4 (up to permutation of variables). As far as I know it's an open question whether there are diagonal polynomials outside Sánchez's family for $d > 4$.

(Disclosure: I have not been able to read all of these papers, as I don't currently have access to a library with journal subscriptions, so I'm relying on the reports of the two I've found online).

I'm not sure to what extent these diagonal polynomials count as "exotic", but it is at least interesting to note that there's more than one per dimension, and this is far too long for a comment anyway.

Answer 2

It seems that the problem is well studied. Here are a few comments and a reference.

It is equivalent that $$f(x,y) = {x+y+2\choose 2}-{x+1\choose 1}$$ is a bijection from $\mathbb{N}_0^2$ onto $\mathbb{N}_0=\{0,1,2,3,\dotsc\}$.

A bijection in either setting easily translates to one in the other, so whichever comes out cleaner can be used.

A nicer expansion of this same map is $$f(x,y)= {x+y+1\choose 2}+{y\choose 1}$$

This is (up to swapping $x$ and $y$) the way that the Cantor Polynomial is described in Wikipedia. The linked article states that

• By a 1923 theorem of Polya, that these are the only two quadratic polynomial bijections.
• The proof is surprisingly difficult with much easier proofs starting in 2002.
• It is conjectured, but unproven, that there are no other polynomial bijections in dimension $2$.
• The corresponding polynomial in dimension $n$ is $ x_1 + \binom{x_1+x_2+1}{2} + \cdots +\binom{x_1+\cdots +x_n+n-1}{n}$

More information is in this paper by M. Nathanson. Evidently it has been shown for $n=2$ that there are no polynomial bijections of degree $3$ or $4$.

If one wished to take a crack at this, the following (well known) observation may be helpful:

Consider for a moment the set $S$ of all maps from $\mathbb{N}_0^2$ onto $\mathbb{Z}$. Some of these are polynomials $$\sum_{i,j}c_{ij}x^iy^j$$ with rational coefficients, although the coefficients need not be integers.

A better basis than the set of monomials $x^iy^j$ is the set of products $\binom{x}i\binom{y}j.$ We don't actually care about the entire set $S$, but if we did, that first set is not clearly useful. However any member of $S$ is seen to have a unique expansion $$\sum b_{ij}\binom{x}{i}\binom{y}{j}$$ with coefficients from $\mathbb{Z}$ and any such expansion is in $S.$ Convergence is not an issue since only finitely many of these products are non-zero at any particular point. And the polynomial maps are simply the ones with a finite expansion.

In this spirit the bijection could be written

$$f(x,y)={x+1 \choose 2}+{y+1 \choose 2}+{x+1 \choose 1}{y \choose 1}$$ $$={x+1 \choose 2}+{y \choose 2}+{x+2\choose 1}{y \choose 1}.$$ $$={x \choose 2}+{x \choose 1}{y \choose 1}+{y \choose 2}+{x \choose 1}+2{y \choose 1}.$$