112
$\begingroup$

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.

$\endgroup$
  • 11
    $\begingroup$ Related: Polynomial bijection from ℚ×ℚ to ℚ? @ MO $\endgroup$ – Grigory M Dec 21 '14 at 11:47
  • 3
    $\begingroup$ I got curious and started a larger computational search, which so far has excluded all cubic polynomials in $\mathbb Z[x, y]$ where the sum of the absolute values of the coefficients is at most 22. You need to test for injectivity over a much larger domain, though: for a polynomial like $8x^3 + 15y$, the closest inputs mapping to the same output are $(8, y)$ and $(-7, y + 456)$. $\endgroup$ – Anders Kaseorg Feb 26 '15 at 10:06
  • 7
    $\begingroup$ @AndersKaseorg: No polynomial of the form $P(x,y)=f(x)+qy$ will work, since there are only finitely many congruence classes modulo $q$ so there must exist distinct $x_1,x_2\in\mathbb Z$ with $[f(x_1)]_q=[f(x_2)]_q$ such that $f(x_1)-f(x_2)=qy$ for some $y\in\mathbb Z$. And then $P(x_1,0)=P(x_2,y)$. $\endgroup$ – String Mar 12 '15 at 15:34
  • 3
    $\begingroup$ In the one-dimensional criterion (last paragraph), you need to add $A\ne B$ as condition $\endgroup$ – Hagen von Eitzen Apr 12 '15 at 12:07
  • 4
    $\begingroup$ I realize this is an old question, but I have verified that no degree-$3$ polynomials with coefficients of absolute value $\leq 2$ are injective from $\mathbb{Z}^2\to \mathbb{Z}$ - in fact they all fail to be injective over $-20\leq x,y \leq 20$. $\endgroup$ – Carl Schildkraut Sep 15 '17 at 5:03
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The comment-length version is: If $P(x,y)=a+bx+cy+dx^2+exy+fy^2$, then either $P(c,-b)=P(-c,b)$ or $P(1,-1)=P(-1,1)$ shows that $P$ is not injective. $\endgroup$ – user210229 Dec 25 '18 at 18:52

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.