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
HTML articles powered by AMS MathViewer

by David Casperson and John McKay PDF

Math. Comp. 63 (1994), 749-757 Request permission

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.

References

User’s guide to PARI-GP

David W. Boyd, Reciprocal algebraic integers whose Mahler measures are nonreciprocal, Canad. Math. Bull. 30 (1987), no. 1, 3–8. MR 879864, DOI 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 10.1080/00927878308822884

The transitive groups of degree up to

Maple library reference manual

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

On the computation of the maximal order in a Dedekind domain

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 10.1007/3-540-51084-2_{3}0
Samuel E. LaMacchia, Polynomials with Galois group $\textrm {PSL}(2,\,7)$, Comm. Algebra 8 (1980), no. 10, 983–992. MR 573466, DOI 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 $\textrm {PSL}_2(\textbf {F}_p)$ als Galoisgruppen über $\textbf {Q}$, Math. Ann. 272 (1985), no. 4, 549–565 (German). MR 807290, DOI 10.1007/BF01455866
B. Heinrich Matzat and Andreas Zeh-Marschke, Realisierung der Mathieugruppen $M_{11}$ und $M_{12}$ als Galoisgruppen über $\textbf {Q}$, J. Number Theory 23 (1986), no. 2, 195–202 (German, with English summary). MR 845901, DOI 10.1016/0022-314X(86)90089-2
Gordon F. Royle, The transitive groups of degree twelve, J. Symbolic Comput. 4 (1987), no. 2, 255–268. MR 922391, DOI 10.1016/S0747-7171(87)80068-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 10.1016/0022-314X(85)90022-8

The computation of Galois groups

The automatic determination of Galois groups

Richard P. Stauduhar, The determination of Galois groups, Math. Comp. 27 (1973), 981–996. MR 327712, DOI 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 10.1007/3-540-51517-8_{1}35

Algebra