Symmetric functions, 𝑚-sets, and Galois groups

Casperson, David; McKay, John

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

Symmetric functions, $m$-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.

C. Batut, D. Bernardi, H. Cohen, and M. Olivier, User’s guide to PARI-GP, April 1990.

David W. Boyd, Reciprocal algebraic integers whose Mahler measures are nonreciprocal, Canad. Math. Bull. 30 (1987), no. 1, 3–8. MR 879864, DOI https://doi.org/10.4153/CMB-1987-001-0
Gregory Butler and John McKay, The transitive groups of degree up to eleven, Comm. Algebra 11 (1983), no. 8, 863–911. MR 695893, DOI https://doi.org/10.1080/00927878308822884

---, The transitive groups of degree up to 15, Comm. Algebra, 1994 (to appear).

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.

Lindsay Childs, A concrete introduction to higher algebra, Springer-Verlag, New York-Heidelberg, 1979. Undergraduate Texts in Mathematics. MR 520728
Henri Darmon and David Ford, Computational verification of $M_{11}$ and $M_{12}$ as Galois groups over ${\bf Q}$, Comm. Algebra 17 (1989), no. 12, 2941–2943. MR 1030603, DOI https://doi.org/10.1080/00927878908823887
D. W. Erbach, J. Fisher, and J. McKay, Polynomials with ${\rm PSL}(2,\,7)$ as Galois group, J. Number Theory 11 (1979), no. 1, 69–75. MR 527761, DOI https://doi.org/10.1016/0022-314X%2879%2990020-9

David Ford, On the computation of the maximal order in a Dedekind domain, Ph.D. thesis, Ohio State University, 1978.

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, DOI https://doi.org/10.1007/3-540-51084-2_30
Samuel E. LaMacchia, Polynomials with Galois group ${\rm PSL}(2,\,7)$, Comm. Algebra 8 (1980), no. 10, 983–992. MR 573466, DOI https://doi.org/10.1080/00927878008822503
John D. Lipson, Elements of algebra and algebraic computing, Addison-Wesley Publishing Co., Reading, Mass., 1981. MR 637467
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
G. Malle and B. H. Matzat, Realisierung von Gruppen ${\rm PSL}_2({\bf F}_p)$ als Galoisgruppen über ${\bf Q}$, Math. Ann. 272 (1985), no. 4, 549–565 (German). MR 807290, DOI https://doi.org/10.1007/BF01455866
B. Heinrich Matzat and Andreas Zeh-Marschke, Realisierung der Mathieugruppen $M_{11}$ und $M_{12}$ als Galoisgruppen über ${\bf Q}$, J. Number Theory 23 (1986), no. 2, 195–202 (German, with English summary). MR 845901, DOI https://doi.org/10.1016/0022-314X%2886%2990089-2
Gordon F. Royle, The transitive groups of degree twelve, J. Symbolic Comput. 4 (1987), no. 2, 255–268. MR 922391, DOI https://doi.org/10.1016/S0747-7171%2887%2980068-8
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
Leonard Soicher and John McKay, Computing Galois groups over the rationals, J. Number Theory 20 (1985), no. 3, 273–281. MR 797178, DOI https://doi.org/10.1016/0022-314X%2885%2990022-8

Leonard Soicher, The computation of Galois groups, Master’s thesis, Concordia University, Montréal, Québec, Canada, April 1981.

R. P. Stauduhar, The automatic determination of Galois groups, Ph.D. thesis, University of California, Berkeley, 1969.

Richard P. Stauduhar, The determination of Galois groups, Math. Comp. 27 (1973), 981–996. MR 327712, DOI https://doi.org/10.1090/S0025-5718-1973-0327712-4
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, DOI https://doi.org/10.1007/3-540-51517-8_135

B. L. van der Waerden, Algebra, Vol. 1, Ungar, New York, 1970.