Computation of the splitting field of a dihedral polynomial

ABSTRACT

Let g be a univariate separable polynomial of degree n with coefficients in a computable field K and let (α₁, . . . , α_n) be an n-tuple of its roots in an algebraic closure K of K. Obtaining an algebraic representation of the splitting field K(α₁, . . . , α_n) of g is a question of first importance in effective Galois theory. For instance, it allows us to manipulate symbolically the roots of g. In this paper, we focus on the computation of the splitting field of g when its Galois group is a dihedral group. We provide an algorithm for this task which returns a triangular set encoding the relations ideal of g which has degree 2n since the Galois group of g is dihedral. Our algorithm starts from a factorization of g in K[X]/<g> and constructs the searched triangular set by performing n² computations of normal forms modulo an ideal of degree 2n.

REFERENCES

• 1: I. Abdeljaouad-Tej , S. Orange , G. Renault , A. Valibouze, Computation of the Decomposition Group of a Triangular Ideal, Applicable Algebra in Engineering, Communication and Computing, v.15 n.3, p.279-294, November 2004 [doi>10.1007/s00200-004-0160-x]
• 2: H. Anai , M. Noro , K. Yokoyama, Computation of the splitting fields and the Galois groups of polynomials, Algorithms in algebraic geometry and applications, Birkhauser Verlag, Basel, Switzerland, 1996
• 3: Philippe Aubry , Daniel Lazard , Marc Moreno Maza, On the theories of triangular sets, Journal of Symbolic Computation, v.28 n.1-2, p.105-124, July/Aug. 1999 [doi>10.1006/jsco.1999.0269]
• 4: Philippe Aubry , Annick Valibouze, Using Galois ideals for computing relative resolvents, Journal of Symbolic Computation, v.30 n.6, p.635-651, Dec. 2000 [doi>10.1006/jsco.2000.0376]
• 5: Becker, T., and Weispfenning, V. Gröbner bases, vol. 141 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1993. A computational approach to commutative algebra, In cooperation with Heinz Kredel.
• 6: Wieb Bosma , John Cannon , Catherine Playoust, The MAGMA algebra system I: the user language, Journal of Symbolic Computation, v.24 n.3-4, p.235-265, Sept./Oct. 1997 [doi>10.1006/jsco.1996.0125]
• 7: Cox, D., Little, J., and O'Shea, D. Ideals, varieties, and algorithms, second ed. Undergraduate Texts in Mathematics. Springer-Verlag, New York, 1997. An introduction to computational algebraic geometry and commutative algebra.
• 8: Xavier Dahan , Marc Moreno Maza , Eric Schost , Wenyuan Wu , Yuzhen Xie, Lifting techniques for triangular decompositions, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.108-115, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073901]
• 9: Xavier Dahan , Éric Schost, Sharp estimates for triangular sets, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.103-110, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005302]
• 10: Ducos, L. Construction de corps de décomposition grâce aux facteurs de résolvantes. Comm. Algebra 28, 2 (2000), 903--924.
• 11: Jensen, C. U., Ledet, A., and Yui, N. Generic polynomials, vol. 45 of Mathematical Sciences Research Institute Publications. Cambridge University Press, Cambridge, 2002. Constructive aspects of the inverse Galois problem.
• 12: Klüners, J., and Malle, G. A database for field extensions of the rationals. LMS J. Comput. Math. 4 (2001), 182--196 (electronic).
• 13: D. Lazard, Solving zero-dimensional algebraic systems, Journal of Symbolic Computation, v.13 n.2, p.117-131, Feb. 1992 [doi>10.1016/S0747-7171(08)80086-7]
• 14: Lazard, D. Solving quintics by radicals. In The legacy of Niels Henrik Abel. Springer, Berlin, 2004, pp. 207--225.
• 15: John McKay , Richard Stauduhar, Finding relations among the roots of an irreducible polynomial, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.75-77, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258752]
• 16: Orange, S., Renault, G., and Valibouze, A. Calcul efficace d'un corps de dcomposition. LIP6 Research Report 005, LIP6, Laboratoire d'Informatique de Paris 6, 2003. http://www.lip6.fr/reports/lip6.2003.005.html.
• 17: Renault, G. Calcul efficace de corps de décomposition. Thèse de Doctorat, Université Paris 6, 2005.
• 18: Renault, G., and Yokoyama, K. A modular method for computing the splitting field of a polynomial. In Proceedings of the 7th Algorithmic Number Theory Symposium (2006). To appear.
• 19: Spearman, B. K., and Williams, K. S. Dihedral quintic polynomials and a theorem of Galois. Indian J. Pure Appl. Math. 30, 9 (1999), 839--845.
• 20: Tchebotarev, N. Gründzüge des Galois'shen Theorie. P. Noordhoff, 1950.
• 21: The KANT Group. KANT/KASH. TU Berlin, 2005. http://www.math.tu-berlin.de/~kant/kash.html.
• 22: The PARI Group. PARI/GP, version 2.1.7. Bordeaux, 2005. http://pari.math.u-bordeaux.fr/.
• 23: Barry M. Trager, Algebraic factoring and rational function integration, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.219-226, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806338]
• 24: Tschirnhaus, E. W. Methodus auferendi omnes terminos intermedios ex data equatione. Nieuw Arch. Wisk. (4) 11, 1 (1993), 67--83. With translation and commentaries in Dutch by A. W. Grootendorst.
• 25: Valibouze, A. Étude des relations algébriques entre les racines d'un polynôme d'une variable. Bull. Belg. Math. Soc. Simon Stevin 6, 4 (1999), 507--535.
• 26: Yokoyama, K. A modular method for computing the Galois groups of polynomials. J. Pure Appl. Algebra 117/118 (1997), 617--636. Algorithms for algebra (Eindhoven, 1996).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Theory

Keywords:
Galois theory, dihedral group, splitting field, triangular set