33
$\begingroup$

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

$\endgroup$
12
  • 3
    $\begingroup$ Since Hilbert's tenth problem over $\mathbb{Q}$ is an open problem (see e.g. www-math.mit.edu/~poonen/slides/h10.pdf), you would have to think this is also open. $\endgroup$ Jul 29, 2013 at 18:14
  • 3
    $\begingroup$ Over $\mathbb{Z}$, surjectivity is certainly undecidable (but injectivity seems harder, as does working over $\mathbb{Q}$). Consider any polynomial that takes on every value except $0$. For example, $(2+2(y_1^2+\dots+y_4^2))(1+2y_5)$ (probably not the simplest construction). Then multiplying this polynomial by $p(x_1,\dots,x_n)^2 + z^2$ gives a polynomial that takes on every integer value iff $p(x_1,\dots,x_n)=0$ has a solution. $\endgroup$
    – Henry Cohn
    Jul 29, 2013 at 18:31
  • 10
    $\begingroup$ There is no algorithm to test if $f:\mathbb{Z}^n\to \mathbb{Z}$ is surjective, by reduction to Hilbert's Tenth Problem: An arbitrary polynomial $g(x_1,\ldots,x_n)$ has an integral zero if and only if $h:=x_{n+1}(1+2g(x_1,\ldots,x_n)^2)$ is surjective. (For the right-to-left implication, note that $g$ must vanish where $h$ takes the value 2.) $\endgroup$ Jul 29, 2013 at 18:31
  • 1
    $\begingroup$ @SJR, why not post your comment as an answer? $\endgroup$ Jul 29, 2013 at 19:51
  • 2
    $\begingroup$ Oops, I gave a correct argument given a polynomial that takes on every value except 0, but an incorrect polynomial with that property. Replacing it with $(1+y_1^2+\dots+y_4^2)(1+2y_5)$ works (unless I'm messing up again), but SJR's solution is nicer. $\endgroup$
    – Henry Cohn
    Jul 29, 2013 at 20:28

3 Answers 3

28
$\begingroup$

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!

$\endgroup$
8
  • $\begingroup$ Very nice. Thanks! -- Is there any chance to adapt this argumentation to answer the 'main' part of the question, i.e. the one on polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$? $\endgroup$
    – Stefan Kohl
    Aug 2, 2013 at 22:18
  • 2
    $\begingroup$ Actually, the injectivity argument works perfectly well over the rationals, provided that there is at least one injective polynomial that maps QxQ into Q. The upshot is that injectivity is decidable if and only if Hilbert's Tenth Problem for field of rational numbers is effectively solvable. $\endgroup$ Aug 2, 2013 at 22:31
  • $\begingroup$ But is there an injective polynomial from $\mathbb{Q}^n$ to $\mathbb{Q}$? -- This seems quite plausible, but Jonas Meyer's comment I referred to in the question suggests that it is at least in no way obvious. $\endgroup$
    – Stefan Kohl
    Aug 3, 2013 at 21:07
  • $\begingroup$ What is now still missing is an answer to the question whether surjectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ is algorithmically decidable -- respectively, an argument telling that this is also equivalent to Hilbert's Tenth Problem over $\mathbb{Q}$ or the like. $\endgroup$
    – Stefan Kohl
    Aug 3, 2013 at 21:10
  • 1
    $\begingroup$ @Stefan; Actually there is a third question that I wish I could answer. My argument shows that an oracle for determining surjectivity of rational maps could be used to test for rational zeros of polynomials. But is the converse true? Or is the surjectivity problem strictly harder than HTP for the rationals? $\endgroup$ Aug 6, 2013 at 21:38
3
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Thanks. -- But sorry -- there seem to be a few things I don't understand. For the beginning: firstly, the range of the mapping $f$ is $\mathbb{Q}$ rather than $\mathbb{Q}^n$. Secondly, what exactly are the mappings $f_i$ from $\mathbb{Q}^n$ to itself for? Thirdly, which of the coefficients of $f_i$ do you call $c_i$? Fourthly, is $c3x^3 = 3cx^3$ or rather $c3x^3 = c_3x^3$, etc.? $\endgroup$
    – Stefan Kohl
    Jul 30, 2013 at 13:12
  • $\begingroup$ @StefanKohl edited the question trying to answer your questions. In short, all $f_i$ are polynomials with range Q. Let me know if you have other questions. $\endgroup$
    – joro
    Jul 30, 2013 at 13:52
  • $\begingroup$ @StefanKohl In short if you have invertible polynomial map Q^n -> Q^n, all polynomials $f_i$ are surjective. You fix $f$ and the answer tries to find $f_2 \ldots f_n$ and the inverse map. There may be more than one solution. $\endgroup$
    – joro
    Jul 30, 2013 at 14:08
  • $\begingroup$ Thank you for the explanations! -- Though I find it somewhat difficult to assess the scope of applicability of your sketch of a method. By the way, how can it be detected whether the method fails for a particular polynomial, if at all? -- And is it right that the method cannot be used to disprove surjectivity of any polynomial? $\endgroup$
    – Stefan Kohl
    Jul 30, 2013 at 15:32
  • 2
    $\begingroup$ @StefanKohl The algorithm couldn't solve any of your challenges (it was fast since the constant coefficient was zero). You are right it can't disprove surjectivity (I suppose this was clearly stated in the answer). It fails if it can't compute the auxiliary polynomials f_2 .. f_n (they don't exist if f_1 is not surjective and maybe don't exist for certain surjective f_1). Btw, the algorithm needs to solve a nonlinear system which is hard. $\endgroup$
    – joro
    Jul 31, 2013 at 5:23
2
$\begingroup$

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

$\endgroup$
4
  • 6
    $\begingroup$ For algebraically closed and real closed fields doesn't this follow from decidability of the first order theory? $\endgroup$ Jul 30, 2013 at 0:54
  • 1
    $\begingroup$ I believe this IS their argument... $\endgroup$
    – Igor Rivin
    Jul 30, 2013 at 0:56
  • 4
    $\begingroup$ +1. But in this answer, one consider the problem with input having only polynomials with coefficients in $\mathbb{Q}$ (or relax to algebraic), but asking for injectivity/surjectivity of these polynomials over $\mathbb{R}$. If one wants to consider polynomials over $\mathbb{R}$, whose coefficients are given as oracles, then I believe it will be undecidable, because equality of reals given this way is undecidable, and one can reduce $a=b$ to the injectivity and/or surjectivity via the polynomial $p(x)=ax-bx$. $\endgroup$ Jul 30, 2013 at 1:28
  • $\begingroup$ @JoelDavidHamkins yes, in the paper I cite they point this out (since zero-equivalence is undecidable, just as you say). $\endgroup$
    – Igor Rivin
    Jul 30, 2013 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.