12
$\begingroup$

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})$?

$\endgroup$
  • $\begingroup$ Can you say anything about where this problem arises? $\endgroup$ – Carl Mummert May 22 '14 at 11:28
  • 1
    $\begingroup$ @CarlMummert: In studying arxiv.org/abs/math-ph/9812019, and also as a simplification of the question "is $\alpha$ constructible?". $\endgroup$ – Charles May 22 '14 at 11:31
  • 2
    $\begingroup$ I would try to see if $P$ always factors in degree $1$ or degree $2$ irreducible factors modulo primes $p$. Maybe with a conjectural effective lower bound on Cebotarev's theorem this would be enough. $\endgroup$ – mercio May 23 '14 at 17:14
  • $\begingroup$ @mercio: Interesting. Can you expand this into an answer? $\endgroup$ – Charles May 24 '14 at 4:40
  • 2
    $\begingroup$ It may be possible to speed up mercio's approach as follows. All the quadratic and linear irreducible polynomials modulo $p$ are factors of $x^{p^2}-x$. So a modulo $p$ test can begin with a calculation of $\gcd(x^{p^2}-x,P(x))$ in $\Bbb{F}_p[x]$. You do need to check the presence of multiple factors. Also I'm not positive if that leads to something faster than factoring modulo $p$. $\endgroup$ – Jyrki Lahtonen May 26 '14 at 5:36
3
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you, this is enormously helpful. So it's enough to find that the polynomial splits into quadratic factors or occasionally linear factors mod $p$ for lots of $p$, and I can either pick lots of primes and get a result with high probability, or else use some bound. Question: what happens if I choose a prime $p$ where the extension ramifies? What kind of factorization do I get? Can I bound the number of times this will happen? $\endgroup$ – Charles May 28 '14 at 19:36
  • $\begingroup$ @Charles : when $p$ ramifies I think the polynomial is a perfect square (or more) and should still factorize completely linearly or completely quadratically. Also I wanted to try and see what an algebraic approach would look like. $\endgroup$ – mercio May 28 '14 at 21:08
  • $\begingroup$ Question/clarification: I tried implementing this with $P=x^8 - 640x^6 + 116872x^4 - 6359040x^2 + 52359696$ which is the minimal polynomial of $2\sqrt2+3\sqrt3+5\sqrt5$ if I'm not mistaken. It factors as $x^4(x^2+1)^2$ mod 3 which seems to be the hybrid case. Am i doing something wrong? $\endgroup$ – Charles Jun 3 '14 at 17:32
  • $\begingroup$ @Charles you are not doing anything wrong, I was thinking wrong in that comment. The Galois group of the extension is made of transformations $\alpha \mapsto f(\alpha)$ where $f(\alpha)$ is an algebraic integer, so has coefficient in $1/\delta \Bbb Z$ where $\delta$ should be something like the discriminant of $P$ divided by the discriminant of the extension. If $p$ doesn't divide $\delta$, those automorphisms make sense modulo $p$ (even if $p$ ramifies) so either every root is in $\Bbb F_p$ either they are all in $\Bbb F_{p^2}$. When $p$ divides $\delta$, well you just saw things can go wrong $\endgroup$ – mercio Jun 3 '14 at 18:56
  • $\begingroup$ OK, so let me check my understanding. If $P$ is of this special type (polyquadratic = Galois group $(\mathbb{Z}/2\mathbb{Z})^n$) then it factors mod $p$ into linear and quadratic factors, and if $p$ does not divide the discriminant of $P$ then it will be all one or the other. Is that correct? $\endgroup$ – Charles Jun 3 '14 at 19:33

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.