12
$\begingroup$

What algorithms are known to perform the following task?

  • Input: a univariate polynomial over the rationals $f \in \mathbb{Q}[t]$.

  • Output: the factorization of $f$ into irreducible factors over the abelian closure $\mathbb{Q}^{\mathrm{ab}} = \varinjlim_{n\in\mathbb{N}} \mathbb{Q}(\zeta_n)$ (where $\zeta_n := \exp(2i\pi/n)$ is an $n$-th root of unity), where elements of $\mathbb{Q}^{\mathrm{ab}}$ are expressed as combinations of roots of unity.

I can show that this is, indeed, Church-Turing computable by way of the following argument (which yields an exceedingly slow algorithm):

  • One can perform exact computations with elements of the algebraic closure $\mathbb{Q}^{\mathrm{alg}}$ (i.e., perform rational operations, comparisons, factorizations of polynomials, etc.). See, e.g., here and here.

  • One can also compute the Galois group (over $\mathbb{Q}$) of an element of $\mathbb{Q}^{\mathrm{alg}}$ (represented as in the first point through, among other things, its minimal polynomial over $\mathbb{Q}$): see here. This makes it possible to check whether an algebraic number belongs to $\mathbb{Q}^{\mathrm{ab}}$.

  • In particular, one can factor $f$ over $\mathbb{Q}^{\mathrm{alg}}$ into distinct roots and, for every subset of these roots, check whether all of their symmetric functions belong to $\mathbb{Q}^{\mathrm{ab}}$: the smallest possible such subsets provide the desired factorization.

  • Given an element $\alpha\in\mathbb{Q}^{\mathrm{ab}}$ (represented as an algebraic number as in the first point), one can test whether $\alpha \in \mathbb{Q}(\zeta_n)$, so one can find such an $n$ by enumerating all natural numbers until one is found, at which point expressing $\alpha$ as a sum of powers of $\zeta_n$ amounts merely to solving a system of linear equations over $\mathbb{Q}$.

This is… not exactly efficient. I'm hoping one can do better. Is there such an algorithm in the literature?

$\endgroup$
  • 3
    $\begingroup$ For each irreducible factor $g|f$ you can compute and factor the discriminant, giving you constraints on the possible $n$ for which $g$ factorizes over $\mathbb{Q}(\zeta_n)$. $\endgroup$ – Dror Speiser Sep 24 '18 at 9:52
  • 1
    $\begingroup$ You can compute the Galois group of each factor $g$ and its maximal abelian quotient $G$, and then factor $g$ over the corresponding extension. It remains to express the coefficients of these polynomials as explicit elements of $\mathbb{Q}^{\mathrm{ab}}$. But once you have $n$ as in Dror Speiser's comment, there are algorithms to find all subfields of $\mathbb{Q}(\zeta_n)$ with Galois group $G$ e.g. polsubcyclo(n,d) in Pari/GP finds all degree $d$ subfields. $\endgroup$ – François Brunault Sep 25 '18 at 16:09
  • 1
    $\begingroup$ I should add that once you know the abelian extension $L/\mathbb{Q}$ corresponding to $G$, there are algorithms to compute its conductor $m$ and the norm group (the kernel of $(\mathbb{Z}/m\mathbb{Z})^\times \to G$) which gives you $L$ as an explicit subfield of $\mathbb{Q}(\zeta_m)$ (or $\mathbb{Q}(\zeta_m)^+$ if $L$ is real) (so basically no need to use polsubcyclo). The point is that the discriminant only gives an upper bound on the conductor. These things are explained e.g. in Cohen, Advanced topics in computational number theory. $\endgroup$ – François Brunault Sep 25 '18 at 16:44
  • 1
    $\begingroup$ Remark: since you are asking that the coefficients of the output are expressed as polynomials in roots of unity, the size of the output is not polynomial in the size of the input : in the factorisation $X^2-N = (X-\sqrt{N})(X+\sqrt{N})$ with $N$ squarefree, you need a large sum of $4N$-th roots of unity to represent $\sqrt{N}$. $\endgroup$ – Aurel Sep 26 '18 at 9:44
4
$\begingroup$

I will try to sketch an algorithm which avoids the computation of the Galois group, since such a computation is very expensive.

The idea is to look at the factorisations of the reductions of $f$ modulo sufficiently many primes $p$. This is the same idea as in the computation of the Galois group, but the point is that we don't need the whole Galois group, only its maximal abelian quotient, so things should be simpler.

We may assume that $f \in \mathbb{Z}[x]$ is monic and irreducible. Let $K = \mathbb{Q}[x]/(f)$ be the number field defined by $f$ and let $L$ be the Galois closure of $K$. We embed both $L$ and $\mathbb{Q}^{\mathrm{ab}}$ into some algebraic closure $\mathbb{Q}^{\mathrm{alg}}$. Let $K^{\mathrm{ab}} = K \cap \mathbb{Q}^{\mathrm{ab}}$ and $L^{\mathrm{ab}} = L \cap \mathbb{Q}^{\mathrm{ab}}$ be the maximal abelian subfields of $K$ and $L$ (sorry for the unusual notation...). Let $f = g_1 g_2 \cdots g_s$ be the factorisation of $f$ over $\mathbb{Q}^{\mathrm{ab}}$. By Galois theory, we know that each $g_i$ has coefficients in $L^{\mathrm{ab}} \cap K = K^{\mathrm{ab}}$.

Definition. A bound for a finite abelian extension $F$ of $\mathbb{Q}$ is a pair $(N,G)$ where $N \geq 1$ is an integer and $G$ is a subgroup of $(\mathbb{Z}/N\mathbb{Z})^\times$ such that $F \subset \mathbb{Q}(\zeta_N)^G$.

Note that for any abelian $F/\mathbb{Q}$ we always have the trivial bound $(|\Delta_F|,\{1\})$ where $\Delta_F$ is the (absolute) discriminant of $F$. Also, it is not hard to see that among all the bounds for $F$ there is a unique minimal one $(N,G)$. The integer $N$ is the conductor of $F$, and $G$ is the norm group, namely the kernel of $(\mathbb{Z}/N\mathbb{Z})^\times \to \mathrm{Gal}(F/\mathbb{Q})$.

So starting with $f$, we know that $K^{\mathrm{ab}}$ is bounded by $(|\Delta_K|,\{1\})$ (it is possible to simply compute the discriminant of $f$, but this may lead to a worse bound). So we start with $(N,G)=(|\Delta_K|,\{1\})$ and we want to improve the bound. In fact, since $K^{\mathrm{ab}}$ is contained in both $K$ and $\mathbb{Q}(\zeta_N)$, we may take $G$ to be the image of the power map $x \mapsto x^\delta$ in $(\mathbb{Z}/N\mathbb{Z})^\times$, where $\delta= \operatorname{gcd}(\deg(f),\varphi(N))$.

Now we look at the reduction of $f$ modulo some primes, similarly as in Algorithm 4.4.3 in Cohen, Advanced topics in computational number theory. Let $p$ be a prime not dividing $N$. Let $\bar{f}$ be the reduction of $f$ mod $p$, and let $\bar{f}=f_1 f_2 \cdots f_r$ be its factorization in $\mathbb{F}_p[x]$. The $f_i$ are pairwise distinct monic irreducible polynomials, say of degree $d_i$. If $K$ were abelian then we would know that $d_1=\ldots=d_r=d$ where $d$ is the order of $p$ in $\mathrm{Gal}(K/\mathbb{Q})$ (seen as a quotient of $(\mathbb{Z}/N\mathbb{Z})^\times$). We are not in this case, but still know by multiplicativity of the inertia degree that the order $d$ of $p$ in $\mathrm{Gal}(K^{\mathrm{ab}}/\mathbb{Q})$ divides each $d_i$. So we adjoin to the group $G$ the element $p^h$ where $h$ is the gcd of $d_1,\ldots,d_r$.

Doing this for enough primes $p$, we should get a reasonable bound $(N,G)$. Now we can replace $(N,G)$ by a minimal equivalent bound $(N',G')$ where $N'$ divides $N$. (Precisely, $N'$ is the minimal divisor of $N$ such that $G$ contains the kernel of reduction mod $N'$, and $G'$ is the image of $G$ mod $N'$.) At this point it remains to factor $f$ over $K'=\mathbb{Q}(\zeta_N)^G$. By the theory of Gauss sums, we know a primitive element $\alpha$ in $K'$ (written in terms of $\zeta_N$) and its minimal polynomial, so we simply factor $f$ over the number field $\mathbb{Q}(\alpha)$.

A natural question is how many primes to use. In fact, if we are only interested in having an algorithm, this doesn't matter: we could simply have used the trivial bound. To get a more efficient algorithm, we may use some primes but it's not clear to me, for example, how many primes are needed to ensure that we get $K'=K^{\mathrm{ab}}$. In general, it is known that the norm group of an abelian extension is generated by the prime powers $p^d$ as above when $p$ runs through the primes less than an explicit bound $B$, see Algorithm 4.4.5 in Cohen. But the bound $B$ is a priori exponential in the size of the discriminant, while there is a much better polynomial bound assuming GRH, so some choices need to be made.

Another difficulty is that the gcd $h$ used above need not equal $d$. Maybe the Cebotarev theorem (an effective version!) could be used to prove this doesn't matter, but this may be a non-trivial task and I haven't thought about it. So I would make the following compromise: simply use a certain amount of primes without caring whether $K'=K^{\mathrm{ab}}$ or not. At the end, if really needed, one could determine over which minimal extension the factorisation of $f$ actually takes place. The "right" number of primes will depend on the parameters but could be determined experimentally or by finding some heuristics.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.