Many bijective pairing functions $f:\mathbb N \times \mathbb N \rightarrow \mathbb N$ exists, including polynomial ones such as the Cantor pairing function

$$f(n,m) = \frac{1}{2}(n + m)(n + m + 1)+m$$

All such functions are of course by definition invertible, and for some of them $f^{-1}:\mathbb N \rightarrow \mathbb N \times \mathbb N$ has a closed form as well. In case of the Cantor function, $f^{-1}$ is not a polynomial however.

Is there a bijection $f:\mathbb N \rightarrow \mathbb N \times \mathbb N$ with


such that $f_1$ and $f_2$ are polynomials in $n$?


No, this would require $f_1, f_2 : \mathbb{N} \to \mathbb{N}$ to be surjective polynomials. The only such function is the identity.

Proof: Let $f: \mathbb{N} \to \mathbb{N}$ be a surjective polynomial. Then there is $c_1$ such that $f$ is monotone on $[c_1,\infty)$, since $f'$ is also a polynomial there is $c_2$ such that $f'$ is monotone on $[c_2,\infty)$. Let $c:=\max\{c_1,c_2\}$.

Now let $n := \max f([0,c]\cap \mathbb{N})+1$ and by surjectivity $k \in \mathbb{N}$ with $f(k)=n$

$f(k + 1) \in \mathbb{N}$ by surjectivity and monotonicity $f(k + 1) = n+1$ and inductively $f(k + m) = n+m$

Since $f'$ is monotone on $[c,\infty)$ $f'$ has to be constant there, i.e. $f''=0$ therefore f is linear.

Btw. there are not many (known) polynomial bijections $f:\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ either. In fact by the Fueter-Polya-Theorem the Cantor Pairing function $C_1(x,y)$ and its reverse $C_2(x,y):=C_1(y,x)$ are the only quadratic such polynomials. It is assumed that there exists none of higher degree.


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.