Computing Subfields

Abstract

In this work, we consider the problem of computing the sub eld lattice of a separable and nite degree eld extension k( )/k. That is, we wish to nd all elds L such that k L k( ). Until recently, the algorithm used by most Computer Algebraic Systems relied on a combinatorial problem on the roots of the minimal polynomial f of over k, which can be a computationally expensive task. In 2013, another algorithm was presented to nd the sub eld lattice of k( )/k. This method computes a small set of sub elds, called principal sub elds, with the property that any other sub eld of k( )/k is the intersection of some of these principal sub elds. Thus, the problem of computing the sub eld lattice can be split into 2 steps: 1) Find the principal sub elds of k( )/k and 2) Compute all intersections of these sub elds. The rst step can be executed in polynomial time however, the second step can not and thus, dominates the algorithm complexity.Our main goal is to improve the second step, both theoretically and practically. More speci cally, we develop a method to quickly compute all intersections of principal sub elds. While the complexity is still not polynomially bounded (in fact, it can not be for the total number of sub elds is not polynomially bounded), this new method helps to improve the non-polynomial part of the complexity. Practical performance is also improved when the number of intersections is large. We also focus on two special cases: number elds and rational function elds. For the number eld case (i.e., when k = Q), we also present an improvement for the rst step. For the rational function eld case, computing the sub eld lattice of the extension K(t)=K(f(t)) de ned by f(t) 2 K(t) yields all decompositions of the rational function f(t). Our algorithm outperforms previous algorithms for computing rational function decompositions.

Neste trabalho, consideramos o problema de calcular o reticulado de subcorpos de uma extensão separável e de grau nito k( )/k. Isto e, queremos encontrar todos os corpos L tais que k L k( ). Até recentemente, o algoritmo utilizado pela maioria dos Sistemas Algébricos Computacionais baseava-se em um problema combinatorial nas raízes do polinômio minimal f de sobre k. Em 2013, um algoritmo foi apresentado para encontrar tais subcorpos. Este método calcula um pequeno conjunto de subcorpos, chamados de subcorpos principais, com a propriedade de que todo subcorpo de k( )/k e a interseção de alguns destes subcorpos. Assim, calcular o reticulado de subcorpos e dividido em duas etapas: 1) Encontrar os subcorpos principais de k( )/k e 2) Calcular todas as interseções destes subcorpos. A primeira etapa pode ser feita em tempo polinomial. Entretanto, a segunda etapa não pode e assim, domina a complexidade do algoritmo. Nosso objetivo e melhorar a segunda etapa, tanto em teoria quanto na prática. Para isso, mostramos como rapidamente calcular todas as interseções entre os subcorpos principais. Embora a complexidade continue não sendo limitada polinomialmente (e também não poderia ser, pois o número total de subcorpos não o é), conseguimos melhorar a complexidade do algoritmo. Também notamos um melhoramento na prática, principalmente quando o número de subcorpos e grande. Além disso, estudamos dois casos especiais: corpos numéricos e o corpo das funções racionais. Para corpos numéricos (i.e., quando k = Q), também apresentamos um melhoramento para a primeira etapa. No segundo caso, os subcorpos da extensão k(t)=k(f(t)), definida por f(t) 2 k(t), nos fornecem decomposições da função racional f(t). Nosso algoritmo tem uma performance melhor que algoritmos anteriores para calcular as decomposições de funções racionais.