Generating subfields (Q1940927)

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.