On polynomials with symmetric Galois group which are easy to compute (Q1098889)

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.