Inverse pairing function with polynomial constituents

Question

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

$$f(n)=(f_1(n),f_2(n))$$

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

Answer 1

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.