Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x\_1, \dots, x\_n]$,
decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective,
respectively, injective? --
And what is the answer if $\mathbb{Q}$ is replaced by $\mathbb{Z}$?


The motivation for this question is Jonas Meyer's comment on the question
[Polynomial bijection from $\mathbb{Q} \times \mathbb{Q}$ to $\mathbb{Q}$](https://mathoverflow.net/questions/21003/)
which says that the explicit determination of an injective polynomial mapping
$f: \mathbb{Q}^2 \rightarrow \mathbb{Q}$ is already difficult, and that
checking whether the polynomial $x^7+3y^7$ is an example is also. 


**Added on Aug 8, 2013:** SJR's nice answer still leaves the following 3 problems open:


1. Is there at all an injective polynomial mapping from $\mathbb{Q}^2$ to $\mathbb{Q}$?
2. Would a positive answer to Hilbert's Tenth Problem over $\mathbb{Q}$ imply that
surjectivity of polynomial functions $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is
algorithmically decidable?
3. Hilbert's Tenth Problem over $\mathbb{Q}$.



Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?
We treat all four problems in turn. In all that follows $n>1$.


Surjectivity over $\mathbb{Q}$:


If there is an algorithm to test whether an arbitrary polynomial with rational coefficients is surjective as a map from $\mathbb{Q}^n$ into $\mathbb{Q}$ then Hilbert's Tenth Problem for $\mathbb{Q}$ is effectively decidable.


Proof: Let $g(x\_1,\ldots,x\_n)$ be any nonconstant polynomial with rational coefficients. We want to construct a polynomial $H$ that is surjective if and only if $g$ has a rational zero.


First we define an auxillary polynomial $h$ as follows;
$$h(y\_1,\ldots,y\_6):=y\_1^2+(1-y\_1y\_2)^2+y\_3^2+y\_4^2+y\_5^2+y\_6^2.$$
The point of the definition is that $h(\mathbb{Q}^6)$ is precisely the set of positive rationals. This follows from Lagrange's four-square theorem and from the fact that $y\_1^2+(1-y\_1y\_2)^2$ is never 0 but takes on arbitrarily small positive values at rational arguments.


Next, let $a$ be any positive rational such that $a$ is not the square of a rational, and such that for some tuple $b\in \mathbb{Q}^n$, it holds that $g(\bar{b})^2<a$. Define the polynomial $H$ as follows:
$$H(x\_1,\ldots,x\_n,\bar{y}):=g(\bar{x})^2(g(\bar{x})^2-a)h(\bar{y}).$$
Of the three factors that make up $H$, the only one that can vanish is $g(\bar{x})^2$. Therefore if $H$ is surjective then $g$ has a rational zero. Conversely if $g$ has a rational zero then $H$ is surjective: Obviously $H$ takes on the value 0. To obtain any rational $r\ne 0$ as a value of $H$, choose $\bar{b}\in \mathbb{Q}^n$ such $g(\bar{b})^2-a$ has the same sign as $r$ and such that $g(\bar{b})\ne 0$, and then choose values for the tuple $\bar{y}$ so that $h(\bar{y})$ is whatever positive rational it needs to be.


Surjectivity over $\mathbb{Z}$: 


There is no algorithm to test surjectivity of a polynomial map $f:\mathbb{Z}^n\to \mathbb{Z}$. The proof is by reduction to Hilbert's Tenth Problem.
Let $g(x\_1,\ldots,x\_n)$ be a polynomial with integer coefficients. Then $g$ has an integral zero if and only if $h:=x\_{n+1}(1+2g(x\_1,\ldots,x\_n)^2)$ is surjective. For if $g$ has an integral zero $\bar{a}$, then $h(x\_1,a\_1\ldots,a\_n)=x\_1$: therefore $h$ is surjective. Conversely, if $h$ is surjective then choose $\bar{a}\in \mathbb{Z}^n$ such that $h(\bar{a})=2.$ Then $a\_{n+1}(1+2g(a\_,\ldots,a\_n)^2)=2$, which is possible only if $g(\bar{a})=0$.


Injectivity over $\mathbb{Z}$: 


There is no algorithm to test injectivity (also by reduction to HTP).


We shall make use of the non-obvious fact that there are polynomials $\pi\_n$ mapping $\mathbb{Z}^n$ into $\mathbb{Z}$ injectively. Such maps are constructed in a paper by Zachary Abel 
[here.](http://zacharyabel.com/papers/Favorite-Problem_A07_HCMR.pdf)


Let $g(x\_1,\ldots,x\_n)$ be a polynomial with integer coefficients. Let $h$ be the polynomial $gg\_1$, where $g\_1$ is obtained by substituting $x\_1+1$ for $x\_1$ in $g$. The point of this definition is that $g$ has an integral zero if and only if $h$ has at least two different integral zeros.


Define the polynomial $H(x\_1\ldots,x\_n)$ as follows:


$$H(\bar{x}):=\pi\_{n+1}(x\_1h(\bar{x}),\ldots,x\_nh(\bar{x}),h(\bar{x})).$$


We claim that $g$ has an integral zero if and only if the polynomial $H(\bar{x})$ does not define an injective map from $\mathbb{Z}^n$ into $\mathbb{Z}$. This gives the reduction of the injectivity problem to Hilbert's Tenth Problem.


To prove the claim, suppose, for the left-to-right implication, that $g$ has an integral zero $\bar{a}$. Then $h(\bar{a})=0$, and $h$ has a different integral zero, call it $\bar{b}$. But then
$$H(\bar{a})=H(\bar{b})=\pi\_{n+1}(\bar{0}),$$
so $H$ is not injective.


For the right-to-left implication, suppose that $H$ is not injective, and fix two different tuples $\bar{a},\bar{b}\in \mathbb{Z}^n$ such that $H(\bar{a})=H(\bar{b})$. Since $\pi\_{n+1}$ is injective, the following equations hold:
\begin{align\*}
a\_1h(\bar{a})&=b\_1h(\bar{b})\\
&\,\vdots\\
a\_nh(\bar{a})&=b\_nh(\bar{b})\\
h(\bar{a})&=h(\bar{b})
\end{align\*}
If $h(\bar{a})$ was not 0, then by dividing each of the first $n$ equations by $h(\bar{a})$, it would follow that the tuples $\bar{a}$ and $\bar{b}$ were identical, a contradiction. So $h(\bar{a})=0$, hence $g$ has an integral zero.


Injectivity over $\mathbb{Q}$:


The same technique that we used over $\mathbb{Z}$ works perfectly well, assuming that we have polynomials $\pi\_n$ mapping $\mathbb{Q}^n$ into $\mathbb{Q}$ injectively. The existence of such polynomials is, it seems, an open question. But if there are no such polynomials then the decision problem for injectivity disappears!


