Polinomios primitivos $P$ con $\gcd(P(x),P(y))=1$ para infinitos $x, y$

Question

Caracteriza todos los polinomios primitivos $P$ que tienen coeficientes enteros tales que existen infinitos números naturales $x, y$ con $\gcd(P(x),P(y))=1$

NOTA: Un polinomio primitivo se define como un polinomio cuyos coeficientes son coprimos.

CONTEXTO:

Me encontré con el siguiente problema hace un tiempo.

Sea $P$ un polinomio con coeficientes enteros tal que $P(0)=0$ y

$\gcd(P(0), P(1), P(2), \ldots ) = 1.$

Demuestra que existen infinitos $n$ tales que

$\gcd(P(n)- P(0), P(n+1)-P(1), P(n+2)-P(2), \ldots) = n.$

Pensé que el siguiente lema podría ser útil.

LEMA: Si un polinomio $P$ es primitivo, entonces existen infinitos números naturales $x, y$ con $(P(x),P(y))=1$.

Por supuesto, como pronto descubrí, el lema anterior es incorrecto. Se puede dar un contraejemplo fácil usando el pequeño teorema de Fermat. Simplemente toma $P(x)=x^p-x$, con $p$ primo. El polinomio es primitivo pero tiene un factor común $p$ para todo $x$.

Estoy bastante seguro de que este es un resultado famoso, pero no puedo encontrarlo. Cualquier ayuda al respecto será apreciada.

Gracias.

Answer 1

Essentially encontraste todos los contraejemplos, en un cierto sentido. La respuesta precisa a tu pregunta es: un polinomio satisface tus condiciones si y solo si no es divisible por $x^p-x$ en ${\mathbb Z}[x]$ para ningún primo $p$ (basta con verificar los $p\leq {\textsf{deg}}(P)$, por supuesto). Esto se sigue de

TEOREMA. Sea $P$ un polinomio (no necesariamente primitivo) en ${\mathbb Z}[x]$. Entonces las siguientes afirmaciones son equivalentes para $P:

(1) Solo hay un número finito de pares $(x,y)\in{\mathbb Z}^2$ con ${\textsf{gcd}}(P(x),P(y))=1$.

(2) No hay ningún par $(x,y)\in{\mathbb Z}^2$ con ${\textsf{gcd}}(P(x),P(y))=1$.

(3) Existe un primo fijo $p$ tal que $P(x)$ es divisible por $p$, para cualquier $x\in{\mathbb Z}$.

(4) Existe un primo fijo $p$ tal que $P(x)$ es divisible por $x^p-x$ en ${\mathbb Z}[x]$.

(nota: Gracias a las congruencias, es irrelevante en tu problema si permitimos que $x,y$ sean enteros naturales o enteros con signo. Estos últimos serán más convenientes para mí).

Prueba del teorema. Demostraré $(1)\Leftrightarrow (2),(3)\Leftrightarrow (4)$ y $(2)\Rightarrow(3),(4)\Rightarrow(1)

-Demostración de $(1)\Leftrightarrow (2)$: la única dirección no trivial es $(1) \Rightarrow (2)$, que demostraremos por contrapositiva. Así que supongamos que $(x,y)$ es un par "bueno" (es decir, tal que ${\textsf{gcd}}(P(x),P(y))=1$). Si uno de $P(x)$ o $P(y)$ (digamos $P(x)$) es $\pm 1$, entonces cualquier par $(x,y')$ es bueno. De lo contrario, tanto $P(x)$ como $P(y)$ son distintos de cero, y cualquier par $(x,y+tP(x))$ (con $t\in{\mathbb Z}$) es bueno.

-Demostración de $(3)\Leftrightarrow (4)$: Realiza una división euclidiana de $P(x)$ por $x^p-x$, luego utiliza el ejercicio clásico de álgebra lineal que establece que la familia $1,x,x^2,\ldots,x^{p-1}$ es independiente sobre ${\mathbb F}_p$ (usa un determinante de Van der Monde).

-Demostración de $(2)\Rightarrow (3)$: nuevamente razonamos por contrapositiva: supongamos que (3) es falsa, es decir, para cada primo $p$, hay un valor $t_p\in{\mathbb Z}$ tal que $p\not| P(t_p)$. Sea $x$ tal que $P(x)\neq 0$, y sean $q_1,q_2,\ldots,q_r$ los divisores primos de $x$. Por la hipótesis recién hecha, existen enteros $t_1,t_2,\ldots,t_r$ con $q_i\not| P(t_i)$. Por el teorema del resto chino, existe un $y$ que satisface $y\equiv t_j \ ({\textsf{mod}}\ q_j)$ para cada $j$. Entonces $P(x)$ y $P(y)$ deben ser coprimos.

-Finalmente, $(4)\Rightarrow (1)$ es obvio: si (4) se cumple entonces $p|{\textsf{gcd}}(P(x),P(y))$ para cualquier $x,y$.