Generating subfields
type: Item
instance of: scholarly article
title: Generating subfields
zbMATH Open document ID: 1278.11111
author: Mark van Hoeij
author: Jürgen Klüners
author: Andrew Novocin
published in: Journal of Symbolic Computation
publication date: 2013-03-11T00:00:00Z
review text: The authors develop a new method for computing all intermediate fields of a separable field extension \(K/k\) of degree \(n\). They assume \(K=k(\alpha)\) and denote the minimal polynomial of \(\alpha\) by \(f\). Since there can exist more than polynomially many such subfields they introduce a new concept of so-called ``generating subfields''. This is a set \(S\) of less than \(n\) special subfields from which any other subfield can be obtained as the intersection of all elements of a suitable subset of \(S\). Section 1 of the paper contains the introduction. In Section 2 principal subfields \(L_1,\ldots,L_r\) of \(K/k\) are introduced as follows. Let \(f=f_1\cdots f_r\) be the factorization of \(f\) in \(K\) (or any extension \(\tilde{K}\) of \(K\)). Let \(g\in k[x]\) be a polynomial of degree less than \(n\). Then \(L_i\) is defined as \(L_i=\{ g(\alpha) \mid g(x) \equiv g(\alpha) \bmod f_i\}\) for \(i=1,\ldots,r\). It is easily seen that the set \(S\) of generating subfields of \(K/k\) is a proper subset of \(\{L_1,\ldots,L_r\}\). Several properties of \(S\) are demonstrated and an algorithm for the computation of all subfields is presented. There is also a subsection on the computation of all quadratic subfields. Section 3 treats the case of number fields, i.e. \(k=\mathbb{Q}\). This case is quite well understood and lattice basis reduction techniques yield fast algorithms in practice. The paper contains several illustrative examples. Also, the running times of the new method are compared with those of previous methods in Magma in the number field case. The new method was always faster when the number \(r\) of factors of \(f\) was larger than 12, where \(r\) is assumed to be minimal for all \(p\)-adic fields \(\tilde{K}={\mathbb{Q}}_p\) for which \(p\) does not divide the discriminant nor the leading coefficient of \(f\). A table contains running times for \(n\) up to 100 and \(r\) up to 20.
Mathematics Subject Classification ID: 11Y40
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11R32
zbMATH DE Number: 6143067
zbMATH Keywords: subfield computation
reviewed by: Michael E. Pohst
MaRDI profile type: Publication
full work available at URL: j.jsc.2012.05.010
OpenAlex ID: W2911871489
DOI: 10.1016/J.JSC.2012.05.010
description: scientific article; zbMATH DE number 6143067