ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 21 Jan 2020 19:42:29 +0100.is_galois Computationhttps://ask.sagemath.org/question/49620/is_galois-computation/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?Tue, 21 Jan 2020 16:04:23 +0100https://ask.sagemath.org/question/49620/is_galois-computation/Comment by Emmanuel Charpentier for <p>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. </p>
<p>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. </p>
<p>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?</p>
https://ask.sagemath.org/question/49620/is_galois-computation/?comment=49623#post-id-49623This might be better addressed in [sage-devel](https://groups.google.com/forum/#!forum/sage-devel)...Tue, 21 Jan 2020 18:24:38 +0100https://ask.sagemath.org/question/49620/is_galois-computation/?comment=49623#post-id-49623Comment by rburing for <p>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. </p>
<p>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. </p>
<p>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?</p>
https://ask.sagemath.org/question/49620/is_galois-computation/?comment=49624#post-id-49624I 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](https://pari.math.u-bordeaux.fr/archives/pari-users-2001/msg00002.html). I'll prepare a ticket. Edit 2: [trac ticket #29064](https://trac.sagemath.org/ticket/29064). Edit 3: [thread on sage-devel](https://groups.google.com/forum/#!topic/sage-devel/q2vVpqxy-Ls).Tue, 21 Jan 2020 19:42:29 +0100https://ask.sagemath.org/question/49620/is_galois-computation/?comment=49624#post-id-49624