¿Son la subjetividad y la inyectividad de las funciones polinómicas de $\mathbb{Q}^n$ a $\mathbb{Q}$ ¿se puede decidir algorítmicamente?

Question

¿Existe un algoritmo que, dado un polinomio $f \in \mathbb{Q}[x_1, \dots, x_n]$ , decide si el mapeo $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ es suryectiva, respectivamente, inyectiva? -- ¿Y cuál es la respuesta si $\mathbb{Q}$ se sustituye por $\mathbb{Z}$ ?

La motivación de esta pregunta es el comentario de Jonas Meyer sobre la cuestión Biyección polinómica de $\mathbb{Q} \times \mathbb{Q}$ a $\mathbb{Q}$ que dice que la determinación explícita de un mapeo polinómico inyectivo $f: \mathbb{Q}^2 \rightarrow \mathbb{Q}$ ya es difícil, y que comprobar si el polinomio $x^7+3y^7$ es un ejemplo también.

Añadido el 8 de agosto de 2013: La bonita respuesta de SJR sigue dejando abiertos los siguientes 3 problemas:

1. ¿Existe en absoluto un mapeo polinómico inyectivo desde $\mathbb{Q}^2$ a $\mathbb{Q}$ ?

2. ¿Una respuesta positiva al décimo problema de Hilbert sobre $\mathbb{Q}$ implican que la subjetividad de las funciones polinómicas $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ ¿es ¿es decidible algorítmicamente?

3. El décimo problema de Hilbert sobre $\mathbb{Q}$ .

Answer 1

Tratamos los cuatro problemas sucesivamente. En todo lo que sigue $n>1$ .

La subjetividad sobre $\mathbb{Q}$ :

Si existe un algoritmo para comprobar si un polinomio arbitrario con coeficientes racionales es suryente como mapa de $\mathbb{Q}^n$ en $\mathbb{Q}$ entonces el décimo problema de Hilbert para $\mathbb{Q}$ es efectivamente decidible.

Prueba: Sea $g(x_1,\ldots,x_n)$ sea cualquier polinomio no constante con coeficientes racionales. Queremos construir un polinomio $H$ que es suryente si y sólo si $g$ tiene un cero racional.

Primero definimos un polinomio auxiliar $h$ de la siguiente manera; $$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.$$ El punto de la definición es que $h(\mathbb{Q}^6)$ es precisamente el conjunto de los racionales positivos. Esto se deduce del teorema de los cuatro cuadrados de Lagrange y del hecho de que $y_1^2+(1-y_1y_2)^2$ nunca es 0, sino que toma valores positivos arbitrariamente pequeños en los argumentos racionales.

A continuación, dejemos que $a$ sea cualquier racional positivo tal que $a$ no es el cuadrado de un racional, y tal que para alguna tupla $b\in \mathbb{Q}^n$ se sostiene que $g(\bar{b})^2<a$ . Definir el polinomio $H$ de la siguiente manera: $$H(x_1,\ldots,x_n,\bar{y}):=g(\bar{x})^2(g(\bar{x})^2-a)h(\bar{y}).$$ De los tres factores que componen $H$ el único que puede desaparecer es $g(\bar{x})^2$ . Por lo tanto, si $H$ es suryente entonces $g$ tiene un cero racional. A la inversa, si $g$ tiene un cero racional entonces $H$ es suryente: Obviamente $H$ toma el valor 0. Para obtener cualquier racional $r\ne 0$ como un valor de $H$ , elija $\bar{b}\in \mathbb{Q}^n$ tal $g(\bar{b})^2-a$ tiene el mismo signo que $r$ y tal que $g(\bar{b})\ne 0$ y, a continuación, elegir los valores de la tupla $\bar{y}$ para que $h(\bar{y})$ es cualquier racionalidad positiva que se necesite.

La subjetividad sobre $\mathbb{Z}$ :

No hay ningún algoritmo para probar la subjetividad de un mapa polinómico $f:\mathbb{Z}^n\to \mathbb{Z}$ . La prueba es por reducción al décimo problema de Hilbert. Sea $g(x_1,\ldots,x_n)$ sea un polinomio con coeficientes enteros. Entonces $g$ tiene una integral cero si y sólo si $h:=x_{n+1}(1+2g(x_1,\ldots,x_n)^2)$ es suryente. Ya que si $g$ tiene una integral cero $\bar{a}$ entonces $h(x_1,a_1\ldots,a_n)=x_1$ : por lo tanto $h$ es suryente. A la inversa, si $h$ es suryente entonces elige $\bar{a}\in \mathbb{Z}^n$ tal que $h(\bar{a})=2.$ Entonces $a_{n+1}(1+2g(a_,\ldots,a_n)^2)=2$ , lo que sólo es posible si $g(\bar{a})=0$ .

Inyectabilidad sobre $\mathbb{Z}$ :

No hay ningún algoritmo para probar la inyectividad (también por reducción a HTP).

Haremos uso del hecho no obvio de que hay polinomios $\pi_n$ cartografía $\mathbb{Z}^n$ en $\mathbb{Z}$ de forma inyectable. Tales mapas se construyen en un artículo de Zachary Abel aquí.

Dejemos que $g(x_1,\ldots,x_n)$ sea un polinomio con coeficientes enteros. Sea $h$ sea el polinomio $gg_1$ , donde $g_1$ se obtiene sustituyendo $x_1+1$ para $x_1$ en $g$ . El sentido de esta definición es que $g$ tiene una integral cero si y sólo si $h$ tiene al menos dos ceros integrales diferentes.

Definir el polinomio $H(x_1\ldots,x_n)$ de la siguiente manera:

$$H(\bar{x}):=\pi_{n+1}(x_1h(\bar{x}),\ldots,x_nh(\bar{x}),h(\bar{x})).$$

Afirmamos que $g$ tiene un cero integral si y sólo si el polinomio $H(\bar{x})$ no define un mapa inyectivo desde $\mathbb{Z}^n$ en $\mathbb{Z}$ . Esto da la reducción del problema de inyectividad al décimo problema de Hilbert.

Para demostrar la afirmación, supongamos, para la implicación de izquierda a derecha, que $g$ tiene una integral cero $\bar{a}$ . Entonces $h(\bar{a})=0$ y $h$ tiene un cero integral diferente, llámalo $\bar{b}$ . Pero entonces $$H(\bar{a})=H(\bar{b})=\pi_{n+1}(\bar{0}),$$ así que $H$ no es inyectiva.

Para la implicación de derecha a izquierda, supongamos que $H$ no es inyectiva, y fija dos tuplas diferentes $\bar{a},\bar{b}\in \mathbb{Z}^n$ tal que $H(\bar{a})=H(\bar{b})$ . Desde $\pi_{n+1}$ es inyectiva, se cumplen las siguientes ecuaciones: \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*} Si $h(\bar{a})$ no era 0, entonces dividiendo cada una de las primeras $n$ ecuaciones por $h(\bar{a})$ se deduce que las tuplas $\bar{a}$ y $\bar{b}$ eran idénticos, una contradicción. Así que $h(\bar{a})=0$ Por lo tanto $g$ tiene un cero integral.

Inyectabilidad sobre $\mathbb{Q}$ :

La misma técnica que utilizamos sobre $\mathbb{Z}$ funciona perfectamente bien, asumiendo que tenemos polinomios $\pi_n$ cartografía $\mathbb{Q}^n$ en $\mathbb{Q}$ de forma inyectable. La existencia de tales polinomios es, al parecer, una cuestión abierta. Pero si no hay tales polinomios, ¡el problema de decisión para la inyectividad desaparece!

Answer 2

He aquí un algoritmo heurístico que reconoce algunos (no todos) polinomios sobreyectivos (esto me ha funcionado en la práctica).

La idea principal es tratar de encontrar un mapa polinómico invertible $$ f, f_2 \ldots f_n \; : \mathbb{Q}^n \to \mathbb{Q}^n$$

Seleccione el límite $d$ para el grado de $f_2 \ldots f_n$ y hacer que el coeficiente de $f_i$ nuevas variables $c_i$ .

Calcular el determinante $D$ de la matriz jacobiana de $ f, f_2 \ldots f_n$ y tratar de resolver simbólicamente para $c_i$ , $D=1$ .

Si esto tiene éxito, la conjetura jacobiana implica que el mapa inverso es polinómico y la resolución del mapa inverso da soluciones como efecto secundario.

Aclaración añadida respondiendo a la pregunta de Stefan

1. La gama de $f$ . Es $\mathbb{Q}$ al igual que los rangos de $f_i$ . En el ejemplo, el $f(x,y)$ es polinómica en x,y al igual que $f_2$ . En el ejemplo $A,B \in \mathbb{Q}$ .

2. $f_i$ son polinomios auxiliares que son utilizados por la conjetura jacobiana

3. Los coeficientes de $f_i$ . Para construir los polinomios $f_i$ , para cada $f_i$ generan todos los monomios en $x_i$ hasta el grado elegido grado $d$ . $c_j$ son variables que son coeficientes de cada monomio en $x_i$ Por ejemplo $c_{13} x_2 x_3$ . Así que $f_i=\sum c_k \prod x_j$ . El determinante $D$ debe ser constante $\forall x_i$ por lo que todos los coeficientes de $x_i$ excepto que la constante debe ser $0$ y el coeficiente constante debe ser distinto de cero. En el ejemplo dado, la solución permite algunos coeficientes como $c_3$ para tomar cualquier valor.

4. Acerca de $c3 x$ . Esto fue copiado de CAS y significa $c_3 x^3$ .

Ejemplo .

Toma $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$

Resolver $D=1$ simbólico da $$ 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$$

El mapa inverso de $f = A, f_2 = B$ es $$ 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} $$

Este enfoque falla para $f = x y$ (módulo de errores) y tiene éxito para el emparejamiento de Cantor.

Si tienes ejemplos concretos, házmelo saber para probar mi implementación.

Answer 3

Inyectabilidad/surjetividad sobre $\mathbb{R}$ es decidible, véase este artículo de Balreira, Kosheleva, Kreinovich. Para $\mathbb{C}^n$ inyectiva implica biyectiva por Ax-Grothendieck. Nada de esto responde a la pregunta, pero es un comienzo...