125
$\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
  • 12
    $\begingroup$ Related: Polynomial bijection from ℚ×ℚ to ℚ? @ MO $\endgroup$
    – Grigory M
    Dec 21, 2014 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$ Feb 26, 2015 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, 2015 at 15:34
  • 3
    $\begingroup$ In the one-dimensional criterion (last paragraph), you need to add $A\ne B$ as condition $\endgroup$ Apr 12, 2015 at 12:07
  • 5
    $\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$ Sep 15, 2017 at 5:03

1 Answer 1

10
$\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$
1
  • 6
    $\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, 2018 at 18:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .