On polynomials with symmetric Galois group which are easy to compute
The paper under review contains proofs for the following results: Theorem 1. Let k be a Hilbertian field and \(F\in k[X]\) be a polynomial with \(\deg(F)=d\), considered as a point in the affine space \(k^{d+1}\), with Zariski topology. Then there exists, in each neighbourhood of F, a polynomial \(G\in k[X]\) with \(\deg(G)=d\), symmetric Galois group, and \(L(G)\leq 5+3L(F)\), where L denotes Ostrowski's complexity measure for evaluating polynomials. In other words, the polynomials over k with symmetric Galois group are dense in each complexity class. - The result above is a complexity-theoretic analogue of \textit{B. L. van der Waerden} [Math. Ann. 109, 13-16 (1934; Zbl 0007.39101)] which states that almost all of the polynomials in \({\mathbb{Z}}[X]\) have symmetric Galois group. Theorem 2. Let k be an infinite field and \(F\in k[X]\) be separable with \(\deg(F)=d\) and splitting field K, such that F has symmetric Galois group. Then, for each \(G\in K[X]\) with \(G| F\), we have \(L(G)\geq (1/7)\sqrt{(1-(\log \deg G)/(\log d))\cdot \deg G}.\) These results show the impossibility of proving interesting lower bounds for the complexity of polynomials by using only the size of the Galois group of the corresponding splitting field.
Ostrowski's complexity measure for evaluating polynomials
scientific article; zbMATH DE number 4037957
scientific article