Earlier, I was curious about whether a polynomial mapping $\mathbb Z^2\rightarrow\mathbb Z$ could be injective, and if so, what the minimum degree of such a polynomial could be. I've managed to construct such a quartic and rule out the existence of such a quadratic, but this leaves open the question of whether a cubic might exist. Equivalently my question is:
Can a cubic polynomial of two variables with integer coefficients be injective?
My intuition is that there probably is such a function since there is a quadratic bijection $\mathbb N^2\rightarrow\mathbb N$ so if we allow ourselves an extra "degree" to compensate for the transition from $\mathbb N$ to $\mathbb Z$, it seems like it ought to be sufficient. However, I have yet to come up with an example that I suspect of being injective nor any general method I might use to try to prove injectivity.
The Part of This Post That Isn't A Question, But That Helps Motivate It Or Maybe Inspire Someone:
So far I have determined that there is an injective quartic and there is not an injective quadratic. To construct the quartic which is injective, note that the map $f:\mathbb N^2 \rightarrow \mathbb N$ defined by $f(x,y)=(x+y)^2+y$ is injective and so is the map $g:\mathbb Z\rightarrow \mathbb N$ defined by $g(n)=2n^2-n$. Then, one can set
$$P(x,y)=f(g(x),g(y))$$
as an injective polynomial (of degree $4$) in the two variables.
No quadratic polynomial may exist because any integer valued polynomial of degree two has a (non-zero) multiple expressible as:
$$P(x,y)=(ax+P_1(y))^2+P_2(y)$$
where $P_1$ and $P_2$ are polynomials with integer coefficients. Then, if we choose some $y_1$ and a $y_2$ such that $y_1\equiv y_2 \pmod{4aP_1(y_1)}$, we clearly have that $P_1(y_1)\equiv P_1(y_2)\pmod a$ and that $P_2(y_1)-P_2(y_2)=4aP_1(y_1)k$ for integer $k$. Then, we can choose two integers $c_1$ and $c_2$ such that $$c_1^2-c_2^2=P_2(y_2) – P_2(y_1) $$
$$c_1\equiv c_2 \equiv P_1(y_1)\equiv P_1(y_2) \pmod a$$
In particular the values
$$c_1=P_1(y_1)+ak$$
$$c_2=P_1(y_1)-ak$$
satify the above. Then, choosing $$x_1=\frac{c_1-P_1(y_1)}{a}$$ $$x_2=\frac{c_2-P_1(y_2)}{a}$$ yields that $P(x_1,y_1)=P(x_2,y_2)$, since their difference is $(c_1^2-c_2^2) – (P_2(y_2)-P_2(y_1))$ which we chose the $c$'s to make $0$.
I have no idea how to approach the cubic case.
A Moderately Surprising Computational Result
Using Mathematica, I determined that there is no polynomial of degree three with integer coefficients with absolute value $2$ or less which is injective over the domain $(\mathbb Z \cap [-2,2])^2$. This surprises me, but it such a small set of polynomials that it might not mean anything other than that we might expect large-ish coefficients if a suitable polynomial does exist. (It could also be indicative of the fact that no such polynomial exists). I would have checked a larger range, but my computer crashed.
I also thought the solving the one-dimensional case completely might help, and can see that $$x\mapsto ax^3 + bx^2 + cx + d$$ is injective if and only if it cannot be written as $a(x-A)(x-B)\left(x-\frac{C}a\right)+k$ for integer $a,A,B,C,k$ – but this isn't super helpful, far as I can tell. However, the statement $f(x,y)$ is injective is equivalent to asserting that $t\mapsto f(m_1t + b_1,m_2t+b_2)$ is injective for all $m_1,b_1,m_2,b_2\in\mathbb Z$ with not both $m$ equalling $0$ – so this could be used to eliminate some cases, if nothing else.
Best Answer
Disclaimer: This is merely a too lengthy comment to fit in the comment section.
I still have no idea about the general degree $3$ case, but here is another proof that no polynomial of degree $2$ will work:
Write the polynomial $P(x,y)$ of degree $2$ as $$ P(x,y)=\sum_{i+j\leq 2}c_{ij} x^i y^j,\quad c_{ij}\in\mathbb Z $$ Consider a point $(a,b)\in\mathbb Z^2\setminus\{(0,0)\}$ and the expression $$ P(ta,tb)=\left(\sum_{i+j=2}c_{ij}a^ib^j\right)t^2+(c_{10}a+c_{01}b)t+c_{00} $$ If the coefficient $(c_{10}a+c_{01}b)$ is zero, then $t\mapsto P(ta,tb)$ is an even function. Then $$ P(ta,tb)=P(-ta,-tb) $$ for all $t\in\mathbb Z$. If $c_{10}=c_{01}=0$ we can choose any $(a,b)\in\mathbb Z^2\setminus\{(0,0)\}$. Otherwise $(a,b)=(-c_{01},c_{10})\neq(0,0)$ works. In any case, we have found an infinitude of pairs $(ta,tb),(-ta,-tb)$ contradicting $P$ being injective.