On polynomials with symmetric Galois group which are easy to compute
type: Item
instance of: scholarly article
title: On polynomials with symmetric Galois group which are easy to compute
zbMATH Open document ID: 0637.12013
DOI: 10.1016/0304-3975(86)90137-4
author: Joos Heintz
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 12E05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 12-04
Mathematics Subject Classification ID: 12F10
zbMATH DE Number: 4037957
zbMATH Keywords: Hilbertian field
zbMATH Keywords: Ostrowski's complexity measure for evaluating polynomials
zbMATH Keywords: symmetric Galois group
zbMATH Keywords: complexity class
reviewed by: Şerban A. Basarab
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90137-4
OpenAlex ID: W2064613553
cites work: Q3313974
cites work: Lower bounds for polynomials with algebraic coefficients
cites work: Q5724382
cites work: Q4158480
cites work: On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
cites work: Die Seltenheit der Gleichungen mit Affekt
cites work: Q3259734
Recommended article: Lower bounds for the complexity of polynomials
Recommended article: Lower bounds of complexity for polarized polynomials over finite fields
Recommended article: Q3974849
Recommended article: Specht modules and resolvents of algebraic equations
Recommended article: Additive Complexity and Zeros of Real Polynomials
Recommended article: Q5090425
Recommended article: Algorithms and Computation
Recommended article: Q3002833
Recommended article: Q3698311
Recommended article: The complexity of factors of multivariate polynomials
description: scientific article; zbMATH DE number 4037957