33

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

Community
  • 1
Stefan Kohl
  • 19,498
  • 21
  • 73
  • 136
  • 3
    Since Hilbert's tenth problem over $\mathbb{Q}$ is an open problem (see e.g. http://www-math.mit.edu/~poonen/slides/h10.pdf), you would have to think this is also open. – Sam Hopkins Jul 29 '13 at 18:14
  • Great question. To establish undecidability, perhaps we might hope somehow to reduce the diophantine solution problem over $\mathbb{Z}$ to the injectivity problem for $\mathbb{Z}$... – Joel David Hamkins Jul 29 '13 at 18:14
  • 3
    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. – Henry Cohn Jul 29 '13 at 18:31
  • 10
    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.) – Sidney Raffer Jul 29 '13 at 18:31
  • @HenryCohn: sorry, but I don't understand your argument: as I see, the polynomial $(2+2(y_1^2 + \dots + y_4^2))(1+2y_5)$ you give takes only even values. Also, I think the polynomial $p(x_1, \dots, x_n)^2 + z^2$ takes only nonnegative values. – Stefan Kohl Jul 29 '13 at 19:48
  • @SamHopkins: maybe -- though not necessarily ... . – Stefan Kohl Jul 29 '13 at 19:51
  • 1
    @SJR, why not post your comment as an answer? – Joel David Hamkins Jul 29 '13 at 19:51
  • @SJR: Very nice argument! -- Can injectivity possibly be dealt with in a similar way? – Stefan Kohl Jul 29 '13 at 19:54
  • 2
    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. – Henry Cohn Jul 29 '13 at 20:28
  • 1
    It seems hard to do injectivity in a similar way, because it seems hard to prove injectivity! Any reduction would produce lots and lots of examples of injective polynomials $\mathbb Z^n \to \mathbb Z$, which I don't think we have many of currently. – Will Sawin Jul 29 '13 at 22:44
  • @WillSawin: There could still be an easy proof that injectivity is algorithmically undecidable -- who knows ... . – Stefan Kohl Jul 29 '13 at 23:22
  • I'm just saying the same method probably won't work. – Will Sawin Jul 30 '13 at 00:08

3 Answers3

28

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!

Sidney Raffer
  • 6,159
  • 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}$? – Stefan Kohl Aug 02 '13 at 22:18
  • 2
    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. – Sidney Raffer Aug 02 '13 at 22:31
  • 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. – Stefan Kohl Aug 03 '13 at 21:07
  • 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. – Stefan Kohl Aug 03 '13 at 21:10
  • @Stefan: I've added an argument for the surjectivity problem over Q. – Sidney Raffer Aug 06 '13 at 18:07
  • Finally, only two problems remain: the first is the question whether there is a polynomial which maps $\mathbb{Q}^n$ to $\mathbb{Q}$ injectively, and the second is Hilbert's Tenth Problem over $\mathbb{Q}$. There is little hope for solving the latter here, but of course it would be nice to find an answer to the former question (which seems to be of unclear difficulty). In any case I think the answer is nice enough to accept at this point. – Stefan Kohl Aug 06 '13 at 19:28
  • 1
    @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? – Sidney Raffer Aug 06 '13 at 21:38
  • Indeed whether the surjectivity problem is strictly harder than HTP for $\mathbb{Q}$ is interesting as well, and as long as one doesn't know the answer to HTP for $\mathbb{Q}$ or if the answer is positive, it is indeed a separate question. -- So definitely, I would find it interesting to get this answered. – Stefan Kohl Aug 06 '13 at 22:31
3

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.

joro
  • 24,174
  • 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.? – Stefan Kohl Jul 30 '13 at 13:12
  • @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. – joro Jul 30 '13 at 13:52
  • @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. – joro Jul 30 '13 at 14:08
  • 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? – Stefan Kohl Jul 30 '13 at 15:32
  • As for test examples, what does your implementation tell about surjectivity / non-surjectivity of $f(x_1,x_2,x_3) = x_1^2+x_2^2+x_3^2$, of $f(x_1,x_2,x_3) = x_1 x_2 x_3$, of $f(x_1,x_2,x_3) = x_1 x_2+x_1 x_3+x_2 x_3$ or of $f(x_1,x_2,x_3,x_4) = x_1^2+x_2^3+x_3^4+x_4^5$? -- And by the way, which computer algebra system do you use? – Stefan Kohl Jul 30 '13 at 15:57
  • 2
    @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. – joro Jul 31 '13 at 05:23
2

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

Igor Rivin
  • 95,560
  • 6
    For algebraically closed and real closed fields doesn't this follow from decidability of the first order theory? – Benjamin Steinberg Jul 30 '13 at 00:54
  • 1
    I believe this IS their argument... – Igor Rivin Jul 30 '13 at 00:56
  • 4
    +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$. – Joel David Hamkins Jul 30 '13 at 01:28
  • @JoelDavidHamkins yes, in the paper I cite they point this out (since zero-equivalence is undecidable, just as you say). – Igor Rivin Jul 30 '13 at 12:47