Opened 7 years ago

Closed 10 months ago

#2217 closed enhancement (fixed)

splitting field function for number fields

Reported by: jason Owned by: davidloeffler
Priority: major Milestone: sage-6.1
Component: number fields Keywords:
Cc: abrochard Merged in:
Authors: Jeroen Demeyer Reviewers: John Cremona, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: u/jdemeyer/ticket/2217 (Commits) Commit: c50eb3e1c340702e06b3ecfabbf29e1aa9da7a44
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

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

Attachments (2)

2217_splitting_field.patch (26.0 KB) - added by jdemeyer 3 years ago.
Add splitting_field() function
trac_2217_correction.patch (2.7 KB) - added by chapoton 15 months ago.

Download all attachments as: .zip

Change History (39)

comment:1 Changed 7 years ago by cwitty

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).

comment:2 Changed 5 years ago by davidloeffler

  • Component changed from number theory to number fields
  • Owner changed from was to davidloeffler

comment:3 Changed 3 years ago by jdemeyer

  • Dependencies set to #11904, #11995
  • Report Upstream set to N/A

comment:4 Changed 3 years ago by jdemeyer

  • Description modified (diff)

Changed 3 years ago by jdemeyer

Add splitting_field() function

comment:5 Changed 2 years ago by abrochard

  • Cc abrochard added

comment:6 Changed 2 years ago by roed

Jeroen, what is the status of the patch here?

comment:7 Changed 2 years ago by jdemeyer

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

comment:8 Changed 2 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Dependencies #11904, #11995 deleted
  • Status changed from new to needs_review

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

comment:9 Changed 20 months ago by mmanes

  • Status changed from needs_review to needs_work

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

Changed 15 months ago by chapoton

comment:10 Changed 15 months ago by chapoton

  • Description modified (diff)

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​

comment:11 Changed 15 months ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:12 Changed 15 months ago by chapoton

  • Status changed from needs_work to needs_review

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

comment:13 Changed 10 months ago by cremona

I am about to test and review this, which will also involve converting the patches to a git branch. And rebasing, since the patches do not apply cleanly to the develop branch
(6.1.beta2).

Last edited 10 months ago by cremona (previous) (diff)

comment:14 follow-up: Changed 10 months ago by jdemeyer

Hang on John, I was planning to do that and make some simplifications also.

comment:15 in reply to: ↑ 14 ; follow-up: Changed 10 months ago by cremona

Replying to jdemeyer:

Hang on John, I was planning to do that and make some simplifications also.

I did not see this comment until after I had finished, so I may have been wasting my time. I had to apply the changes manually since I could not get the patches to apply. Shall I still upload my new branch? I have a commit which includes both the patches and passes all tests -- but have not yet started the real review process, i.e. reading the code.

Last edited 10 months ago by cremona (previous) (diff)

comment:16 in reply to: ↑ 15 Changed 10 months ago by jdemeyer

Replying to cremona:

Shal I still upload by new branch?

Of course you should. My point was mainly that I wanted to make some changes to my patch, so you should wait to review it.

comment:17 Changed 10 months ago by cremona

  • Branch set to u/cremona/ticket/2217
  • Commit set to 7585353e14aba12cc3b1907f3a9068392703e4c6
  • Reviewers set to John Cremona

New commits:

7585353trac 2217: implement splitting field function

comment:18 Changed 10 months ago by cremona

OK, so here is a branch which implements your two patches. I will not do any more until asked, and hope that this will save you effort! I also hope that this will not hide your genuine authorship of the new code.

comment:19 Changed 10 months ago by jdemeyer

  • Status changed from needs_review to needs_work

comment:20 Changed 10 months ago by jdemeyer

  • Reviewers changed from John Cremona to John Cremona, Frédéric Chapoton
  • Status changed from needs_work to needs_review

comment:21 Changed 10 months ago by jdemeyer

  • Branch changed from u/cremona/ticket/2217 to u/jdemeyer/ticket/2217
  • Modified changed from 01/02/14 15:27:46 to 01/02/14 15:27:46

comment:22 Changed 10 months ago by jdemeyer

  • Commit changed from 7585353e14aba12cc3b1907f3a9068392703e4c6 to 9b5558e8c0e78343d059ce3c47da3c1ded4cb74c
  • Status changed from needs_review to needs_work

New commits:

9b5558eImplement splitting fields for number fields

comment:23 Changed 10 months ago by git

  • Commit changed from 9b5558e8c0e78343d059ce3c47da3c1ded4cb74c to 9e2dd448b2093e9c6e64d33685900f85ab1ede7c

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

9e2dd44Make q monic before computing cubic resolvent

comment:24 Changed 10 months ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:25 Changed 10 months ago by jdemeyer

  • Description modified (diff)

comment:26 follow-up: Changed 10 months ago by cremona

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! ;)

comment:27 in reply to: ↑ 26 Changed 10 months ago by jdemeyer

Replying to cremona:

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.

comment:28 Changed 10 months ago by cremona

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.

comment:29 Changed 10 months ago by git

  • Commit changed from 9e2dd448b2093e9c6e64d33685900f85ab1ede7c to 6df69b67e67a135b5e9417716fbad11b1d9fee49

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

6df69b6Add comments, small cosmetic changes

comment:30 Changed 10 months ago by git

  • Commit changed from 6df69b67e67a135b5e9417716fbad11b1d9fee49 to c50eb3e1c340702e06b3ecfabbf29e1aa9da7a44

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

c50eb3eNo need to specify caller_name in verbose()

comment:31 Changed 10 months ago by cremona

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

comment:32 Changed 10 months ago by cremona

  • Status changed from needs_review to positive_review

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...

comment:33 follow-up: Changed 10 months ago by jdemeyer

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

Am I allowed to add more examples/doctests?

comment:34 in reply to: ↑ 33 ; follow-up: Changed 10 months ago by cremona

  • Status changed from positive_review to needs_work

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!

comment:35 in reply to: ↑ 34 Changed 10 months ago by jdemeyer

  • Status changed from needs_work to positive_review

Replying to cremona:

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.

comment:36 Changed 10 months ago by jdemeyer

  • Description modified (diff)

comment:37 Changed 10 months ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.