Symmetric functions, 𝑚-sets, and Galois groups

Casperson, David; McKay, John

doi:10.1090/S0025-5718-1994-1234424-5

Symmetric functions, -sets, and Galois groups

Authors: David Casperson and John McKay
Journal: Math. Comp. 63 (1994), 749-757
MSC: Primary 12-04; Secondary 05-04, 05E15, 12F10
DOI: https://doi.org/10.1090/S0025-5718-1994-1234424-5
MathSciNet review: 1234424
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Given the elementary symmetric functions in $\{ {r_i}\} \;(i = 1, \ldots ,n)$ , we describe algorithms to compute the elementary symmetric functions in the products $\{ {r_{{i_1}}}{r_{{i_2}}} \cdots {r_{{i_m}}}\} \;(1 \leq {i_1} < \cdots < {i_m} \leq n)$ and in the sums $\{ {r_{{i_1}}} + {r_{{i_2}}} + \cdots + {r_{{i_m}}}\} \;(1 \leq {i_1} < \cdots < {i_m} \leq n)$ . The computation is performed over the coefficient ring generated by the elementary symmetric functions. We apply FFT multiplication of series to reduce the complexity of the algorithm for sums. An application to computing Galois groups is given.

[1] C. Batut, D. Bernardi, H. Cohen, and M. Olivier, User's guide to PARI-GP, April 1990.
[2] David W. Boyd, Reciprocal algebraic integers whose Mahler measures are nonreciprocal, Canad. Math. Bull. 30 (1987), no. 1, 3–8. MR 879864, https://doi.org/10.4153/CMB-1987-001-0
[3] Gregory Butler and John McKay, The transitive groups of degree up to eleven, Comm. Algebra 11 (1983), no. 8, 863–911. MR 695893, https://doi.org/10.1080/00927878308822884
[4] -, The transitive groups of degree up to 15, Comm. Algebra, 1994 (to appear).
[5] B. W. Char, K. O. Geddes, G. H. Gonnet, B. L. Leong, M. B. Monagan, and S. M. Watt, Maple library reference manual, Springer-Verlag, New York, 1991.
[6] Lindsay Childs, A concrete introduction to higher algebra, Springer-Verlag, New York-Heidelberg, 1979. Undergraduate Texts in Mathematics. MR 520728
[7] Henri Darmon and David Ford, Computational verification of 𝑀₁₁ and 𝑀₁₂ as Galois groups over 𝑄, Comm. Algebra 17 (1989), no. 12, 2941–2943. MR 1030603, https://doi.org/10.1080/00927878908823887
[8] D. W. Erbach, J. Fisher, and J. McKay, Polynomials with 𝑃𝑆𝐿(2,7) as Galois group, J. Number Theory 11 (1979), no. 1, 69–75. MR 527761, https://doi.org/10.1016/0022-314X(79)90020-9
[9] David Ford, On the computation of the maximal order in a Dedekind domain, Ph.D. thesis, Ohio State University, 1978.
[10] Marc Giusti, Daniel Lazard, and Annick Valibouze, Algebraic transformations of polynomial equations, symmetric polynomials and elimination, Symbolic and algebraic computation (Rome, 1988) Lecture Notes in Comput. Sci., vol. 358, Springer, Berlin, 1989, pp. 309–314. MR 1034742, https://doi.org/10.1007/3-540-51084-2_30
[11] Samuel E. LaMacchia, Polynomials with Galois group 𝑃𝑆𝐿(2,7), Comm. Algebra 8 (1980), no. 10, 983–992. MR 573466, https://doi.org/10.1080/00927878008822503
[12] John D. Lipson, Elements of algebra and algebraic computing, Addison-Wesley Publishing Co., Reading, Mass., 1981. MR 637467
[13] John McKay, Advances in computational Galois theory, Computers in algebra (Chicago, IL, 1985) Lecture Notes in Pure and Appl. Math., vol. 111, Dekker, New York, 1988, pp. 99–101. MR 1060761
[14] G. Malle and B. H. Matzat, Realisierung von Gruppen 𝑃𝑆𝐿₂(𝐹_{𝑝}) als Galoisgruppen über 𝑄, Math. Ann. 272 (1985), no. 4, 549–565 (German). MR 807290, https://doi.org/10.1007/BF01455866
[15] B. Heinrich Matzat and Andreas Zeh-Marschke, Realisierung der Mathieugruppen 𝑀₁₁ und 𝑀₁₂ als Galoisgruppen über 𝑄, J. Number Theory 23 (1986), no. 2, 195–202 (German, with English summary). MR 845901, https://doi.org/10.1016/0022-314X(86)90089-2
[16] Gordon F. Royle, The transitive groups of degree twelve, J. Symbolic Comput. 4 (1987), no. 2, 255–268. MR 922391, https://doi.org/10.1016/S0747-7171(87)80068-8
[17] Charles C. Sims, Computational methods in the study of permutation groups, Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) Pergamon, Oxford, 1970, pp. 169–183. MR 0257203
[18] Leonard Soicher and John McKay, Computing Galois groups over the rationals, J. Number Theory 20 (1985), no. 3, 273–281. MR 797178, https://doi.org/10.1016/0022-314X(85)90022-8
[19] Leonard Soicher, The computation of Galois groups, Master's thesis, Concordia University, Montréal, Québec, Canada, April 1981.
[20] R. P. Stauduhar, The automatic determination of Galois groups, Ph.D. thesis, University of California, Berkeley, 1969.
[21] Richard P. Stauduhar, The determination of Galois groups, Math. Comp. 27 (1973), 981–996. MR 327712, https://doi.org/10.1090/S0025-5718-1973-0327712-4
[22] Annick Valibouze, Fonctions symétriques et changements de bases, EUROCAL ’87 (Leipzig, 1987) Lecture Notes in Comput. Sci., vol. 378, Springer, Berlin, 1989, pp. 323–332 (French, with English summary). MR 1033311, https://doi.org/10.1007/3-540-51517-8_135
[23] B. L. van der Waerden, Algebra, Vol. 1, Ungar, New York, 1970.