15
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ Does "I ignore if an exotic bijection is known for $d = 3$" mean that you don't know (which is suggested by context), or you don't care (which seems to be the literal meaning)? $\endgroup$
    – LSpice
    Aug 4, 2021 at 22:17
  • 3
    $\begingroup$ @LSpice, the original meaning of "ignore" is "be ignorant of", and while it's fallen out of favour in English it persists in other languages with Latin influence. $\endgroup$ Aug 4, 2021 at 22:45
  • 1
    $\begingroup$ "So-called"? Do you intend the negative connotation that this bijection should not be attributed to Cantor? (I ask because non-native speakers of English are sometimes surprised to hear that the use of "so-called" expresses skepticism.) $\endgroup$ Aug 9, 2021 at 18:46
  • 1
    $\begingroup$ Sorry, no skepticism was not intended. I have suppressed the ill-chosen adjectif. $\endgroup$ Aug 9, 2021 at 20:27
  • 2
    $\begingroup$ @JoelDavidHamkins I thought it was pretty clear that Roland was using "so-called" in the "commonly named" sense, rather than the "falsely or inappropriately named" sense, which is a perfectly valid form of the adjective. It is hard to read his original sentence as finding fault specifically with "Cantor" when "so-called" is modifying the entire phrase "Cantor bijection". $\endgroup$ Aug 9, 2021 at 20:56

2 Answers 2

14
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Maybe $2d-2$ should be $2^{d-2}$. That would be consistent with finding two for $d=3$ and not finding six for $d=4$, but I don't feel like spending 40EUR to get access to the paper. $\endgroup$ Aug 7, 2021 at 13:26
  • $\begingroup$ It was indeed $2^{d-2}$, but not in "Diagonal polynomials of small dimension". There they cite "An enlarged family of packing polynomials on multidimensional lattices" where you can find the construction of their $2^{d-2}$ polynomials, which I found freely available online. $\endgroup$
    – mme
    Aug 7, 2021 at 18:44
  • $\begingroup$ Thanks, @mme. Google Scholar gives a link which seems to be broken, but with your additional prod I've found a gratis (albeit I had to create a account) PDF. $\endgroup$ Aug 7, 2021 at 18:59
7
$\begingroup$

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}.$$

$\endgroup$
3
  • $\begingroup$ The counts in the question correspond to permuting the variables, parenthesising them, and then using the "corresponding polynomial in dimension $n$" for each parenthetic group of size $n$. $\endgroup$ Aug 7, 2021 at 10:31
  • $\begingroup$ Although, on looking more carefully, the generalisation to higher orders is different to the one given in the question. $\endgroup$ Aug 7, 2021 at 11:03
  • $\begingroup$ I'd just like to add thanks for the reference: it was chasing through its references that I found the ones mentioned in my answer. $\endgroup$ Aug 7, 2021 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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