When is a number in $\mathbb{Q}(\sqrt{a_1},\ldots,\sqrt{a_n})$?

Question

Given an algebraic number $\alpha$ with minimal polynomial $P(x)$ of degree $2^n$, how can I decide if there are integers $a_1,\ldots,a_n$ such that $\alpha\in\mathbb{Q}(\sqrt{a_1},\ldots,\sqrt{a_n})$?

Answer 1

You are trying to find out if an irreducible polynomial of degree $2^n$ has Galois group $(\Bbb Z/2 \Bbb Z)^n$.

One method to get information about a Galois group is to factorize the polynomial modulo small primes $p$. Except when the extension ramifies at $p$, its factorisation corresponds to the cycle decomposition of the $Frob_p$ automorphism, which according to Cebotarev's theorem, is distributed "uniformly" in the Galois group (in non-abelian Galois group, only the conjugation class of $Frob_p$ is well-defined, but we can act as if this made sense).

The only groups whose nontrivial elements are of order $2$ are isomorphic to $(\Bbb Z/2\Bbb Z)^m$ for some $m$, so it is enough to check that modulo $p$, the polynomial splits completely in linear factors with probability $2^{-m}$, and splits completely in quadratic factors the rest of the time (there is no hybrid case because the extension is Galois : given one root $\alpha$, all the roots are in $\Bbb Q(\alpha)$).

The product of linear factors mod $p$ is $X^p-X$, and the product of irreducible quadratic factors is $(X^{p^2}-X)/(X^p-X)$, so you can compute the greatest common divisor of these polynomials with $P$. There can be repeated factors without the extension being ramified at $p$ (especially for small primes), so be sure to iterate the process until you exhaust the factors of $P$.

The problem becomes guessing at what prime $p$ we should stop checking. There is an aptly named article "A bound for the least prime ideal in the Chebotarev Density Theorem" by J. C. Lagarias, H. L. Montgomery, A. M. Odlyzko

(and surely many others)

I have seen, assuming GRH, bounds of the form $O(\log(d)^2$ where $d$ is the discriminant of the extension (which we don't know). Depending on the constant this could be a very nice upper bound.