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) |