Examples of polynomial injections $f:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$

Question

I've seen that there are polynomial bijections $f:\mathbb{N}\times \mathbb{N}\to \mathbb{N},$ for example $f(m,n)=\frac{1}{2}(n+m)(n+m-1)+m.$ I'm looking for more examples of injective polynomials from $\mathbb{N}\times \mathbb{N}\to \mathbb{N}.$ Are these common? Are there simple examples that are easy to prove injective?

Also, I should clarify that I am looking for an example that is fundamentally different than the example I gave, not just modifications of it. Preferably there would be a simple explanation of why this example was injective.

Answer 1

Apparently there is such an injection:

$$ (3x^2 + x + 1) + (3x^2 + x + 1 + 3y^2 + y + 1)^2 $$

I found this in a comment at this MO question, and they also link this article, which provides a wealth of information on a related problem (finding polynomial injections $\mathbb{Z}^4 \hookrightarrow \mathbb{Z}$), and thus, by plugging in $f(x,x,y,y)$, on this problem.

As an aside, it's well known that every integer polynomial $\mathbb{N}^2 \to \mathbb{N}$ can be written as a linear combination of the form

$$ p(x,y) = \sum a_{ij} \binom{x}{i} \binom{y}{j}. $$

I don't have the time to come up with anything right now, but it seems reasonable that you could play around with this representation in order to force injectivity.

---

I hope this helps ^_^

Answer 2

It's easy to construct injective polynomials from $\Bbb N$ to $\Bbb N$: any increasing polynomial will do, for example, and thus any (nonzero) polynomial with nonnegative coefficients will do.

This observation might seem irrelevant, but note that if $g_1,g_2,h\colon \Bbb N\to \Bbb N$ are injective polynomials, then $$ h\Big( f\big( g_1(m), g_2(n) \big) \Big) $$ (where $f$ is the polynomial in the OP) is an injective polynomial from $\Bbb N^2$ to $\Bbb N$. One can generate a huge number of examples this way.