La BRECHA paquete tiene una función de $\mathtt {GaloisType}$ que toma un polinomio como un argumento y devuelve un número, el índice de la transitivo grupo de orden que el grado del polinomio. Leí en alguna parte que el algoritmo se basa en un teorema por Dedekind basa en cómo el polinomio factores si se toma modulo algunos de los números primos. Pero este teorema sólo da una significativa respuesta acerca de la existencia de un ciclo, si la encuentra, pero esto no da ninguna certeza acerca de lo que el grupo es en realidad. También sé que hay una cierta probabilidad de teoremas relativos a este problema, pero no creo que ahora lo que decían. ¿Cuál es la probabilidad de que la respuesta es incorrecta?
Respuestas
¿Demasiados anuncios?
ahulpke
Puntos
2612
Lo que está sucediendo es un 2-el proceso de la etapa. Primera Dedekind del teorema se utiliza para obtener algunos ciclo de formas. Esto le da un límite inferior para el grupo de Galois.
Después, los polinomios que corresponden a la acción del grupo de Galois de k-sets o k-secuencias son incluidos. (E. g. $$\prod_{i,j} (x-(\alpha_i+\alpha_j))$$ corresponde a la acción en 2 conjuntos.) De esta manera una muestra de que el grupo de Galois no puede ser mayor. El resultado es (modular errores de programación) comprobada la correcta.
SI sólo desea un resultado probabilístico, basado en Chebotarev del teorema de la función $\mathtt {ProbabilityShapes}$ lo hace (y es mucho más rápido).
En el riesgo de la vergüenza de la auto-promoción, http://www.math.colostate.edu/~hulpke/charlas/galoistalk.pdf son diapositivas de una relevante hablar, http://www.math.colostate.edu/~hulpke/papel/gov.pdf una encuesta de papel.
Parece que el comentario de campo es limitada, por lo que una segunda respuesta como ejemplo:
Lo que usted describe es muy posible (y un plausible y pregunta inteligente):
Tome $p(x)=x^3+x^2-2x-1$ (el mínimo polinomio E(7)+E(7)^6, así que uno puede realmente trabajar con raíces). Este es irreducible sobre los racionales y ha Galois grupo A3, por lo que la factorización modulo de los números primos sólo dar irreductible o 3 factores lineales. Ahora ambos A3 y S3 son transitivos en 2 conjuntos, por lo que necesitamos (blanco mentira! ver al final) tomar 2-secuencias. Por lo tanto, forma el polinomio cuyas raíces son de la forma $\alpha_i+2\alpha_j$. Podemos hacerlo mediante el cálculo de la resultante de las $r(x)=res_y(2^3\cdot p(y/2),p(x-y))$, y la división de apagado (el caso de $i=j$) el factor de $3^3p(x/3)$.
gap> r:=Resultant(2^3*Value(p,y/2),Value(p,x-y),y);
x^9+9*x^8+x^7-168*x^6-308*x^5+609*x^4+1463*x^3-363*x^2-1062*x+351
gap> r/3^3/Value(p,x/3);
x^6+6*x^5+x^4-36*x^3-20*x^2+48*x-13
En la práctica, un método basado en la simétrica de las funciones es más fácil
gap> TwoSeqPol(p,2);
x^6+6*x^5+x^4-36*x^3-20*x^2+48*x-13
produce el mismo resultado. Si nos factor de dicho polinomio de grado 6, se obtienen dos factores de grado 3 -- dos órbitas en 2-secuencias. Si el polinomio inicial había tenido Galois grupo S3, se habría quedado irreductible.
Usted puede observar lo que la BRECHA se está haciendo mediante el establecimiento de
SetInfoLevel(InfoGalois,3);
Luego GaloisType imprimirá la información sobre el proceso, por ejemplo,
gap> GaloisType(x^5+x^4-4*x^3-3*x^2+3*x+1);
#I Partitions Test
#I cands:[ 1, 2, 4 ]
#I 2-Set Resolvent
#I trying res nr. 0
#I SumRootsPol 2
#I Candidates :[ 1, 2 ]
#I 2-Seq Resolvent
#I TwoSeqPol 2
#I Candidates :[ 1 ]
1
aquí ciclo de las formas de salir de los grupos 1,2 y 4 a la izquierda. Acción 2-conjuntos (SumRootsPol 2) hojas 1 y 2, y 2-secuencias finalmente uñas del grupo.
Si usted hace esto $x^3+x^2-2x-1$ por encima observa que el 2-secuencia polinomio no se utiliza nunca. Esto es porque podemos distinguir $A_n$/$S_n$ por si el discriminante (por $p$$49$) es un cuadrado.
