¿Existe un algoritmo que calcule el grupo de Galois de un polinomio $p(x) \in \mathbb{Z}[x]$ ? Siéntase libre de interpretar esta pregunta de cualquier manera razonable. Por ejemplo, si el grado de $p(x)$ est $n$ entonces el algoritmo podría dar un conjunto de permutaciones $\pi \in Sym(n)$ que generan el grupo de Galois.
Respuestas
¿Demasiados anuncios?
Hay un algoritmo descrito en un antiguo e interesante libro sobre la teoría de Galois de Leonard Eugene Dickson. Aquí hay un breve esquema en el caso de un polinomio irreducible $f\in \mathbb{Q}[x]$ .
Supongamos que $z_1\ldots z_n$ son las raíces de $f$ en algún campo de división de $f$ en $\mathbb{Q}$ . (No necesitamos construir el campo de división. El $z_i$ se mencionan aquí en aras de la explicación). Dejemos que $x_1\ldots x_n$ sean indeterminados. Para una permutación $\sigma\in S_n$ , dejemos que $$E_\sigma=x_1z_{\sigma(1)}+\ldots+ x_n z_{\sigma(n)}.$$ Dejemos que $g(x):=\prod _{\sigma} (x-E_\sigma)$ , donde $\sigma$ recorre todas las permutaciones en $S_n$ . Cada coeficiente $c_i$ de $x^i$ en $g$ es simétrica en $z_1 \ldots z_n$ por lo que (utilizando el teorema de las funciones simétricas) podemos escribir $c_i$ como un polinomio en $x_1\dots x_n$ con coeficientes racionales.
Suponiendo que esto se haya hecho, el factor $g$ en irreducibles sobre el anillo $\mathbb{Q}[x_1 \ldots x_n]$ . Sea $g_0$ sea el factor irreducible de $g$ que se satisface con $E_{Id}$ où $Id$ es la permutación de la identidad. Entonces el grupo de Galois de $f$ consiste en todas las permutaciones de $x_1\ldots x_n$ que arreglar $g_0$ .
La cuestión es que el cálculo de $g_0$ es eficaz (aunque horrenda) y también lo es la determinación de las permutaciones que fijan $g_0$ .
grapefrukt
Puntos
16804
Existe un algoritmo esencialmente diferente de los mencionados anteriormente, debido a N. Durov:
-
N. V. Durov, Cálculo del grupo de Galois de un polinomio con coeficientes racionales. I. (ruso) Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 319 (2004), Vopr.Teor. Predst. Algebr. i Grupp. 11, 117-198, 301; traducción al inglés en J. Math. Sci. (N. Y.) 134 (2006), nº 6, 2511-2548 (MR2006b:12006)
-
N. V. Durov, Computación del grupo de Galois de un polinomio con coeficientes racionales. II. (Ruso) Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 321 (2005), Vopr. Teor. Predst. Algebr. i Grupp. 12, 90-135, 298; traducción al inglés en J. Math. Sci. (N. Y.) 136 (2006), no. 3, 3880-3907 (MR2006e:12004)
el algoritmo es probabilístico, basado en el teorema de la densidad de Chebotarev, y requiere algunos datos aleatorios como entrada; por lo que sé, el algoritmo termina con probabilidad 1 para todas las ecuaciones siempre que la hipótesis de Riemann sea cierta.
sickgemini
Puntos
2001
Frank Sottile me ha dicho que la razón por la que muchos sistemas de álgebra computacional sólo hacen grados bajos es la siguiente: Sea $H$ sea un subgrupo de $S_n$ y supongamos que queremos comprobar si $\mathrm{Gal}(f)$ está contenida en un conjugado de $H$ . Se puede utilizar la siguiente prueba: Como en la respuesta de SJR, dejemos que $z_1$ , $z_2$ , ..., $z_n$ sean las raíces de $f$ . Elige algún monomio de bajo grado $m:=\prod z_i^{a_i}$ y que $q = \sum_{h \in H} h(m)$ . Si el grupo de Galois está contenido en $H$ entonces $q$ será racional. Sea $F(t) = \prod_{g \in G/H} (t-g(q))$ . El polinomio $F$ tiene coeficientes racionales y es calculable mediante polinomios simétricos. Utilizando el teorema de la raíz racional, es "fácil" comprobar si $F$ tiene una raíz racional. ("Fácil" está entre comillas porque implica la factorización de primos, pero tengo entendido que esto no es el cuello de botella). Si lo hace para varias opciones de $m$ Entonces, es muy plausible que $\mathrm{Gal}(f)$ está contenido en un conjugado de $H$ .
Para los pequeños $n$ el entramado de subgrupos de $S_n$ es tal que, ejecutando pruebas de este tipo, se puede acercarse rápidamente a un candidato para $\mathrm{Gal}(f)$ . Una vez que usted golpea $n=11$ , te encuentras con el Grupos Matheiu . Al menos desde hace un año, cuando Frank y yo hablamos de esto, él estaba muy interesado en encontrar buenos algoritmos para comprobar si un grupo de Galois era un subgrupo de un grupo de Matheiu.
x-way
Puntos
196
Los comentarios y la respuesta de SJR demuestran que, efectivamente, existen algoritmos para calcularlo. Pero todas estas sugerencias están tan lejos de ser efectivas que sólo pueden considerarse "pruebas de existencia" de un algoritmo.
De hecho, se trata de un área de investigación muy activa, aunque parece que la mayor parte de este trabajo ha caído completamente bajo el radar de los matemáticos convencionales, pero esto se ha mantenido vivo gracias a una banda de matemáticos sin escrúpulos que a menudo llaman a un departamento de ciencias de la computación su hogar. Basta de polémica, pasemos a los resultados reales. Me parece que Alexander Hulpke Técnicas para el cálculo de grupos de Galois especialmente esclarecedor. Ciertos subcasos, como el de los grupos simétricos y alternos, pueden encontrarse aún más rápidamente (véase Reconocimiento rápido de grupos de Galois alternativos y simétricos ).
Y lo que es mejor, existen excelentes implementaciones de estos algoritmos recientes en GAP . Así, estos cálculos son doblemente efectivos.
Boardy
Puntos
203
Hay otra forma que no parece mencionarse aquí. Esto es sólo algo que se me ocurrió hace unos días; si alguien sabe si esto se ha hecho antes agradecería mucho sus comentarios.
Es bien sabido que, dado un campo $K_0$ y un polinomio $p \in K_0[x]$ el siguiente proceso nos dará finalmente un campo $K_n$ que es un campo de división para $p$ :
-
elija un factor irreducible mónico de $p$ de grado $> 1$ en $K_0[x]$ . Llama a este factor $q_1$ .
-
Dejemos que $K_1 = K[r_1] / (q_1(r_1))$ .
-
elija un factor irreducible mónico de $p$ de grado $> 1$ en $K_1[x]$ . Llama a este factor $q_2$ .
-
Dejemos que $K_2 = K_1[r_2] / (q_2(r_2))$ .
-
elija un factor irreducible mónico de $p$ de grado $> 1$ en $K_2[x]$ etc.
Así que tenemos un campo de división $K_n$ construido explícitamente como un cociente de $K_0[r_1, \ldots r_n]$ . Sea $I$ sea el núcleo del mapa obvio de $K_0[r_1, ... r_n]$ a $K_n$ . El algoritmo anterior también nos da una base de Gröbner para $I$ para cada uno de los polinomios $q_i$ con $2 \leq i \leq n$ dejar $q'_i$ sea una elevación de $q_i$ a un polinomio mónico con coeficientes en el anillo de polinomios $K_0[r_1, ... r_{i - 1}]$ . Entonces es fácil ver que $B:=\{q_1(r_1), q'_2(r_2), ... q'_n(r_n)\}$ es una base de Gröbner para $I$ con la ordenación monomial lexicográfica con $r_n > r_{n-1} > ... > r_1$ .
En general, si tenemos un anillo $R$ con un ideal $J$ , un automorfismo $f: R \rightarrow R$ inducirá un automorfismo de $R/J$ si $J$ est $f$ -invariante, es decir $f(x) \in J$ siempre que $x \in J$ . En particular, si $\sigma$ es una permutación de $\{ r_1 \ldots r_n \}$ y $f_\sigma$ es el correspondiente automorfismo de $K_0[r_1, ... r_n]$ tenemos que $f_\sigma$ induce un automorfismo de $K_n$ si $I$ est $f_\sigma$ -invariante, o de forma equivalente, $f_\sigma(b) \in I$ para cada $b \in B$ . Además, podemos comprobar si $f_\sigma(b) \in I$ con la división multivariada, que es conveniente como $B$ es ya una base de Gröbner para $I$ .
En resumen, podemos comprobar si una permutación $\sigma$ de las raíces de $p$ está en el grupo de Galois comprobando si $f_\sigma(b) \in I$ para cada $b \in B$ y esto se puede hacer con la división multivariada.
