¿Cómo podemos comprobar si un polinomio es un cuadrado perfecto?

Question

A menudo nos encontramos con el polinomio de diophantine ecuaciones de la forma $y^2 = x^2 + x+ 1$ y hay dos maneras de refutar la existencia de soluciones a tales ecuaciones:

1) Por la delimitación entre consecutivos cuadrados perfectos.

2) Mediante la lectura de las ecuaciones en $\mathbb{Z}_n$ y el uso de la reciprocidad cuadrática leyes en $\mathbb{Z}_n$.

Sin embargo, estas técnicas no cuando hay infinitamente muchas soluciones para la diophantine. Por ejemplo, el diophantine $y^2 = x^4 + 6x^3 + 7x^2 - 6x + 1$ tiene una infinidad de soluciones, ya que es equivalente a $y^2 = (x^2+ 3x -1)^2$. Además, parece que la generación de un problema es fácil, pero 'identificar' la raíz cuadrada es duro.

Así que mi pregunta es:

1) ¿hay una forma en la que uno puede saber si un polinomio es un cuadrado perfecto utilizando un criterio simple de los coeficientes?

2) ¿hay una forma en la que uno puede recuperar la raíz cuadrada por un simple algoritmo?

Gracias!

P. S: tenga en cuenta que no me refiero a decir que la única manera de $y^2 = f(x)$ puede tener una infinidad de soluciones es al $f(x)$ es un cuadrado perfecto. Sé que $y^2 = 2x^2 + 1$ $y^2 = x^3$ tiene una infinidad de soluciones. Sólo estoy interesado en el caso particular de los cuadrados perfectos.

Answer 1

Deje $p=p_0+p_1x+\ldots+p_{2n}x^{2n}\in\mathbb{Z}[x]$ ser un polinomio de grado $2n$$p_0=k^2\neq 0$. Tomando la raíz cuadrada de $p$ es un procedimiento directo hacia adelante, se detalla a continuación. En general, esto se traducirá en una potencia de la serie en lugar de un polinomio (por supuesto, no todos los polinomios son cuadrados perfectos).

$$\sqrt{p(x)}=\sum_{m=0}^{\infty}a_mx^m.$$

A continuación, $p$ es un cuadrado perfecto si y sólo si $a_m=0$ todos los $n<m\leq 2n$. Esto se desprende de la recursividad para los coeficientes:

$$\begin{eqnarray} a_0&=&k\\ a_{n+1}&=&\frac{p_{n+1}-\sum_{m=1}^na_ma_{n+1-m}}{2k} \end{eqnarray}$$

Vamos a tratar de esto en uno de sus ejemplos: $p=1-6x+7x^2+6x^3+x^4$. Comenzando con $a_0=1$ encontramos los coeficientes $$1, -3, -1, 0, 0$$ en que punto podemos concluir que el $p=(1-3x-x^2)^2$.

Answer 2

Me gustaría destacar la idea de la repetición de las raíces. Un polinomio sobre, digamos, los enteros, pero con raíces considerado en $\mathbb C,$ ha repetido raíces bajo condiciones muy específicas, y que pueden ser utilizados; para cada raíz real $\alpha,$ sabemos que $(x-\alpha)$ divide $f(x)$ a un grado de al menos 2, por lo que se divide la derivada de, al menos, de grado 1. Con un complejo de raíz de $\beta,$ el mismo hecho de que el producto $(x - \beta)(x - \bar{\beta}).$ Como resultado de ello, si hay una raíz cuadrada $s(x),$ $$ s(x) | \gcd(f(x), f'(x)). $$ The magical part is that the $\mcd$ ha entero y los coeficientes de la parte superior grado coeficiente puede ser forzado a ser 1.
Yo diría que esta idea no ayuda con el general de factoraje, pero es definitivo para plazas: podemos decir que el polinomio no es un cuadrado perfecto o encontrar la raíz cuadrada.

Pausa... Aquí, tomando $f(x) = x^4 + 6 x^3 + 7 x^2 - 6 x + 1,$ $f'(x) = 4 x^3 + 18 x^2 + 14 x,$ $g = \gcd(f(x), f'(x)),$ tenemos $$ g | h = (4f - x f') = 6 x^3 +14 x^2 - 18 x + 4. $$ Entonces $$ g | (3f' - 2 h) = 26 x^2 + 76 x + -26 = 26 (x^2 + 3 x - 1). $$ Y que funciona.

Siguiente: más altos (incluso) que los poderes involucrados

He hecho un ejemplo; tengo la esperanza de demostrar que uno puede abordar esta cuestión con dos operaciones, teniendo formales derivadas de polinomios y de tomar mcd de dos polinomios.

$$ f = x^8 - 10 x^7 + 35 x^6 - 56 x^5 + 91 x^4 - 210 x^3 + 189 x^2 - 108 x + 324 $$

$$ f' = 8 x^7 - 70 x^6 + 210x^5 - 280x^4 + 364x^3 - 630x^2 + 378x - 108 $$

$$ g_{01} = \gcd(f,f') = x^5 - 8 x^4 + 20x^3 - 18x^2 + 27x - 54 $$

Ahora, el grado de $g_{01}$ es de 5, más de la mitad de 8, así que esto es alentador, pero dice que algunos de los exponentes son más de 2. Por lo tanto hacemos otra dos de los derivados para comprobar exponente 4.

$$ f'' = 56x^6 - 420x^5 + 1050x^4 - 1120x^3 + 1092x^2 - 1260x + 378, $$ $$ f''' = 336x^5 - 2100x^4 + 4200x^3 - 3360x^2 + 2184x - 1260, $$ y $$ g_{23} = \gcd(f'',f''') = 56 x - 168 = 56 (x-3). $$

Esto funciona: tomar $$ h = f / (x-3)^4 = x^4 + 2x^3 + 5x^2 + 4x + 4, $$ $$ h' = 4x^3 + 6x^2 + 10x + 4, $$ $$ g_h = \gcd(h,h') = x^2 + x + 2. $$ Esta vez, nos hacen llegar a la mitad de la licenciatura, y el éxito con $h = (x^2 + x + 2)^2.$ por lo Tanto $$ f = (x^2 + x + 2)^2 (x-3)^4 $$

En fin, yo quería ver lo que sucede con los no racionales de las raíces y no cuadrática factores. Ejemplo $$ f= x^{12} - 4x^{10} + 4x^9 + 6x^8 - 12x^7 + 2x^6 + 12x^5 - 11x^4 + 6x^2 - 4x + 1, $$ $$ f' = 12x^{11} - 40x^9 + 36x^8 + 48x^7 - 84x^6 + 12x^5 + 60x^4 - 44x^3 + 12x - 4, $$ $$ g_{01}= \gcd(f,f') = x^9 - 3x^7 + 3x^6 + 3x^5 - 6x^4 + 2x^3 + 3x^2 - 3x + 1. $$

Una vez más, que es más de la mitad de la licenciatura, así que seguimos adelante.

$$ f'' = 132x^{10} - 360x^8 + 288x^7 + 336x^6 - 504x^5 + 60x^4 + 240x^3 - 132x^2 + 12, $$ $$ f''' = 1320x^9 - 2880x^7 + 2016x^6 + 2016x^5 - 2520x^4 + 240x^3 + 720x^2 - 264x, $$ $$ g_{23}= \gcd(f'',f''') = 132x^3 - 132x + 132 = 132 ( x^3 - x + 1) . $$ Este es exactamente un cuarto de la de los títulos originales, y de hecho $$ f = ( x^3 - x + 1)^4. $$

Answer 3

Usted puede diseñar algunas pruebas bastante facilidad para la cuártica caso. Suponga que desea saber si $a_4x^4+a_3x^3+a_2x^2+a_1x+a_0$ es un cuadrado.

(1) $a_4,a_0$ deben ser cuadrados. Supongamos que las raíces cuadradas se $a,c$.

(2) debemos tener $a_3/a$ $a_1/c$ igual y uniforme. Supongo que es $2b$.

(3) $a_2$ debe $b^2\pm2ac$.

Así, en el ejemplo, se pasa a (1) $a=c=1$. Así que pasa por (2) y $b=3$. Así que pasa a (3) $7=3^2-2\times1\times1$.

Entonces la raíz cuadrada es $ax^2\pm bx\pm c$. Usted tiene que comprobar que los signos de trabajo.

Pero en la práctica dudo si que es particularmente útil, excepto tal vez (1).

Answer 4

Generalmente, uno puede comprobar rápidamente si un polinomio es una $n$'th poder de la siguiente manera. Primero hacer algunas pruebas probabilísticas a través de las evaluaciones en la $\,\Bbb Z\,$ y el número limitado de campos. Si pasa estas pruebas, aplicar iteración de Newton (método de Newton) para calcular cualquier $n$'th raíz.

Para una visión general de la complejidad de este y de los problemas relacionados con ver a Daniel Roche 2011 tesis Cálculo Eficiente con Escasa y Densa Polinomios. Aquí es un enlace directo a la pertinente capítulo 6: Escasa perfecto poderes.