.is_galois Computation

asked 2020-01-21 16:04:23 +0200

nmbthr gravatar image

Given an irreducible polynomial $f$, Sage computes whether a given field $K= \mathbb{Q}(f)$ is Galois with $K$.is_galois. This works well if $f$ is of low degree, say 1-20. But when $f$ is large, say degree 100 or more, this is very time consuming.

For $K$ to be Galois, it must have the same degree as $f$ and because we would expect (at random) $f$ to have Galois group $S_n$, $\text{Gal}(K/\mathbb{Q})$ will be very large. So in theory, determining 'Is Galois Y/N' should run much faster than actually computing the Galois group - which is very hard.

How does Sage .is_galois work? Does it try to compute the Galois group and compare sizes, or does it use some other method? If in computing $\text{Gal}(K/\mathbb{Q})$ you find a group with size at least $> \deg f$, does it automatically stop and give 'False'? If not, is there a way to force such a feature using features already built into Sage?

edit retag flag offensive close merge delete


This might be better addressed in sage-devel...

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2020-01-21 18:24:38 +0200 )edit

I notice that SageMath is calling PARI to do e.g. nfgaloisconj(nfinit(x^29 - 10*x + 13)), which is much slower than nfgaloisconj(x^29 - 10*x + 13). If they give the same result, then we can improve the code... Edit: Yes. I'll prepare a ticket. Edit 2: trac ticket #29064. Edit 3: thread on sage-devel.

rburing gravatar imagerburing ( 2020-01-21 19:42:29 +0200 )edit