×

Symmetric functions, \(m\)-sets, and Galois groups. (English) Zbl 0839.05094

Summary: Given the elementary symmetric functions in \(\{r_i\}\) \((i= 1,\dots, 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.

MSC:

05E05 Symmetric functions and generalizations
12F10 Separable extensions, Galois theory
12Y05 Computational aspects of field theory and polynomials (MSC2010)

Software:

PARI/GP
Full Text: DOI