Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?

Question

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}$ 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}$.

Answer 1

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.

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!

Answer 2

Here is a heuristic algorithm which recognizes some (not all) surjective polynomials (this worked for me in practice).

The main idea is to try to find invertible polynomial map $$ f, f_2 \ldots f_n \; : \mathbb{Q}^n \to \mathbb{Q}^n$$

Select bound $d$ for the degree of $f_2 \ldots f_n$ and make the coefficient of $f_i$ new variables $c_i$.

Compute the determinant $D$ of the jacobian matrix of $ f, f_2 \ldots f_n$ and try to solve symbolically for $c_i$, $D=1$.

If this succeeds, the jacobian conjecture implies the inverse map is polynomial and solving the inverse map gives you solutions as a side effect.

Added clarification answering Stefan's question

1. The range of $f$. It is $\mathbb{Q}$ as are the ranges of $f_i$. In the example the given $f(x,y)$ is polynomial in x,y as is $f_2$. In the example $A,B \in \mathbb{Q}$.

2. $f_i$ are auxiliary polynomials which are used by the jacobian conjecture

3. The coefficients of $f_i$. To construct the polynomials $f_i$, for each $f_i$ generate all monomials in $x_i$ up to the chosen degree $d$. $c_j$ are variables which are coefficients of each monomial in $x_i$, e.g. $c_{13} x_2 x_3$. So $f_i=\sum c_k \prod x_j$. The determinant $D$ must be constant $\forall x_i$, so all coefficients of $x_i$ except the constant must be $0$ and the constant coeff. must be nonzero. In the given example, the solution allows some coefficients like $c_3$ to take any value.

4. About $c3 x$. This was copied from CAS and means $c_3 x^3$.

Example.

Take $f(x,y)={x}^{3}+3\,{x}^{2}y+3\,x{y}^{2}+{y}^{3}+3\,{x}^{2}+6\,xy+3\,{y}^{2}+2 \,x+3\,y$

Solving $D=1$ symbolicall gives $$ f_2(x,y)= {\it c1}\,x+{\it c3}\,{x}^{3}+{\it c2}\,{x}^{2}+{\it c4}\,{x}^{4}+{ \it c20}\,{y}^{4}+{\it c15}\,{y}^{3}+{\it c10}\,{y}^{2}+{\it c5}\,y+{ \it c25}+{\it c24}\,{x}^{4}{y}^{4}+{\it c19}\,{x}^{4}{y}^{3}+{\it c23} \,{x}^{3}{y}^{4}+{\it c14}\,{x}^{4}{y}^{2}+{\it c18}\,{x}^{3}{y}^{3}+{ \it c22}\,{x}^{2}{y}^{4}+{\it c9}\,{x}^{4}y+{\it c13}\,{x}^{3}{y}^{2}+ {\it c17}\,{x}^{2}{y}^{3}+{\it c21}\,x{y}^{4}+{\it c8}\,{x}^{3}y+{\it c12}\,{x}^{2}{y}^{2}+{\it c16}\,x{y}^{3}+{\it c7}\,{x}^{2}y+{\it c11} \,x{y}^{2}+{\it c6}\,xy$$

The inverse map of $f = A, f_2 = B$ is $$ x=3\,{\it c3}\,A+3\,{\it c25}-A+{{\it c3}}^{3}{A}^{3}+{{\it c25}}^{3 }-{B}^{3}+6\,{\it c3}\,A{\it c25}-6\,{\it c3}\,AB-6\,{\it c25}\,B-6\,{ \it c3}\,A{\it c25}\,B-3\,B+3\,{{\it c3}}^{2}{A}^{2}+3\,{{\it c25}}^{2 }+3\,{B}^{2}+3\,{{\it c3}}^{2}{A}^{2}{\it c25}-3\,{{\it c3}}^{2}{A}^{2 }B+3\,{\it c3}\,A{{\it c25}}^{2}+3\,{\it c3}\,A{B}^{2}-3\,{{\it c25}}^ {2}B+3\,{\it c25}\,{B}^{2}$$ $$y=A-{{\it c3}}^{3}{A}^{3}-{{\it c25}}^{3}+{ B}^{3}-6\,{\it c3}\,A{\it c25}+6\,{\it c3}\,AB+6\,{\it c25}\,B+6\,{ \it c3}\,A{\it c25}\,B-2\,{\it c3}\,A+2\,B-2\,{\it c25}-3\,{{\it c3}}^ {2}{A}^{2}-3\,{{\it c25}}^{2}-3\,{B}^{2}-3\,{{\it c3}}^{2}{A}^{2}{\it c25}+3\,{{\it c3}}^{2}{A}^{2}B-3\,{\it c3}\,A{{\it c25}}^{2}-3\,{\it c3}\,A{B}^{2}+3\,{{\it c25}}^{2}B-3\,{\it c25}\,{B}^{2} $$

This approach fails for $f = x y$ (modulo errors) and succeeds for the Cantor pairing.

If you have specific examples, let me know to test my implementation.

Answer 3

Injectivity/surjectivity over $\mathbb{R}$ is decidable, see this paper by Balreira, Kosheleva, Kreinovich. For $\mathbb{C}^n$ injective implies bijective by Ax-Grothendieck. None of this answers the question, but it's a start...