splitting field function for number fields

[jasongrout]

We should add splitting_field() function: given a polynomial, compute the number field generated by all the roots.

See the thread at http://groups.google.com/group/sage-devel/browse_thread/thread/32fe12de12d5f6a5/c91753b5e65fe7b9#c91753b5e65fe7b9

Follow-up tickets: #11905, #15626

CC: @abrochard

Component: number fields

Author: Jeroen Demeyer

Branch/Commit: u/jdemeyer/ticket/2217 @ c50eb3e

Reviewer: John Cremona, Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/2217

[sagetrac-cwitty]

comment:1

Note that this approach does not give the splitting field. It gives a field containing at least one root of each factor of the original polynomial, but that still might not be the splitting field.

Later in the thread mentioned above, I give a technique using internals of qqbar which I believe does give the splitting field (perhaps inefficiently).

[jdemeyer]

Dependencies: #11904, #11995

[jdemeyer]

Add splitting_field() function

[abrochard]

comment:5

Attachment: 2217_splitting_field.patch.gz

[roed314]

comment:6

Jeroen, what is the status of the patch here?

[jdemeyer]

comment:7

I totally forgot about this. I might be good to revisit this.

[jdemeyer]

comment:8

I originally had plans for some speed-ups, but since the code works fine, I guess it can be reviewed.

[jdemeyer]

Author: Jeroen Demeyer

[jdemeyer]

Changed dependencies from #11904, #11995 to none

[sagetrac-mmanes]

comment:9

I ran all standard tests, and everything passed.

I was trying to test functionality, but I'm confused by the differences file. All of the old examples seem to work, and none of the new ones work.

In the first example, I get:

sage: G = NumberField(x^3 - x - 1,'a').galois_closure('b').galois_group(); G

Galois group of Number Field in b with defining polynomial x^6 - 14*x^4
+ 20*x^3 + 49*x^2 - 140*x + 307

The expected output seems to have been changed from this result to

Number Field in b with defining polynomial x^6 - 6*x^4 + 9*x^2 + 23 

These fields are isomorphic, but I've tried the example on three machines, and all of them give the first thing as the output.

Similarly, the second example doesn't work:

sage: G.subgroup([ G(1), G([(1,2,3),(4,5,6)]), G([(1,3,2),(4,6,5)]) ]) 

Traceback (click to the left of this block for traceback)
...
TypeError: permutation [(1, 2, 3), (4, 5, 6)] not in Galois group of
Number Field in b with defining polynomial x^6 - 14*x^4 + 20*x^3 +
49*x^2 - 140*x + 307

But the original example (now deleted) does work:

sage: G.subgroup([ G(1), G([(1,5,2),(3,4,6)]), G([(1,2,5),(3,6,4)])])

Subgroup [(), (1,5,2)(3,4,6), (1,2,5)(3,6,4)] of Galois group of Number
Field in b with defining polynomial x^6 - 14*x^4 + 20*x^3 + 49*x^2 -
140*x + 307

[fchapoton]

comment:10

Attachment: trac_2217_correction.patch.gz

here is a patch to correct the failing doctest

let us see if the bot is happy

apply 2217_splitting_field.patch​ trac_2217_correction.patch​

[fchapoton]

comment:12

ok, the bot is happy. Now the ticket needs review.

[sagetrac-git]

Changed commit from 9b5558e to 9e2dd44

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

9e2dd44

Make q monic before computing cubic resolvent

[JohnCremona]

comment:26

I am looking at your new commits. At first I assumed that your commits were based on mine uploaded earlier, but when pulling yours on top of mine failed I guessed the truth. This is of course fine -- except that some people might now argue otherwise: during the time when my commit was attached to this ticket, it is possible that other people pulled it and based further work, new tickets etc, all on my unreviewed commit. That would have been stupid of them, but some of the comments on the recent sage-devel thread make it clear that git purists would never so this. I won't tell anyone if you do not! ;)

[jdemeyer]

comment:27

Replying to @JohnCremona:

during the time when my commit was attached to this ticket, it is possible that other people pulled it and based further work, new tickets etc, all on my unreviewed commit.

I absolutely understand your point, but I think I indicated that this was work in progress so I felt it was safe to "rewrite history". Now that it's needs_review, I will no longer rewrite history.

Concerning authorship: I did indeed reset the author name back to myself (git commit --amend --author Demeyer), and that's already rewriting history.

[JohnCremona]

comment:28

Understood. I am happy (and quite impressed!) with the new code and am just testing, using the verbose option so I can see what is happening.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

6df69b6

Add comments, small cosmetic changes

[sagetrac-git]

Changed commit from 9e2dd44 to 6df69b6

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

c50eb3e

No need to specify caller_name in verbose()

[sagetrac-git]

Changed commit from 6df69b6 to c50eb3e

[JohnCremona]

comment:31

Still needs-review or will you be making more commits?!

[JohnCremona]

comment:32

Code looks very good, and I am happy with the results of testing. I have looked at the commits on branch u/jdemeyer/ticket/2217 up to commit c50eb3e...

[jdemeyer]

comment:33

Thanks, I didn't expect such a quick review.

Am I allowed to add more examples/doctests?

[JohnCremona]

comment:34

Replying to @jdemeyer:

Thanks, I didn't expect such a quick review.

Am I allowed to add more examples/doctests?

Of course! I think there are already a lot of examples, which I liked. If you are going to make some more changes I would be happy to look at them, so I'll now mark the ticket as needs work, and when you are ready put it back to needs review. While you are at it, the description of the class containing a pair (polynomial, degree multiple) is slightly confusing since it refers to other polynomials in the class, whereas you actually deal with lists of instances of these.

I am currently working on another branch so the next review will not be so quick!

[jdemeyer]

comment:35

Replying to @JohnCremona:

I am currently working on another branch so the next review will not be so quick!

In that case, perhaps I prefer to leave this ticket and continue on a new ticket. Sorry for the mess.