Opened 10 years ago
Last modified 7 years ago
#8327 closed enhancement
Implement the universal cyclotomic field, using Zumbroich basis — at Version 36
Reported by: | nthiery | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-5.7 |
Component: | number fields | Keywords: | Cyclotomic field, Zumbroich basis |
Cc: | sage-combinat, cwitty | Merged in: | |
Authors: | Christian Stump, Simon King | Reviewers: | |
Report Upstream: | N/A | Work issues: | Find dependency or rebase first patch. Fix doctests. Needs more doctests and Sphinxified docstrings. |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This patch provides the universal cyclotomic field
sage: UCF Universal Cyclotomic Field endowed with the Zumbroich basis
in sage. This field is the smallest field extension of QQ which contains all roots of unity.
sage: E(3); E(3)^3 E(3) 1 sage: E(6); E(6)^2; E(6)^3; E(6)^6 -E(3)^2 E(3) -1 1
It comes equipped with a distinguished basis, called the Zumbroich basis, which gives, for any n, A basis of QQ( E(n) ) over QQ, where (n,k) stands for E(n)^{k. }
sage: UCF.zumbroich_basis(6) [(6, 2), (6, 4)]
As seen for E(6), every element in UCF is expressed in terms of the smallest cyclotomic field in which it is contained.
sage: E(6)*E(4) -E(12)^11
It provides arithmetics on UCF as addition, multiplication, and inverses:
sage: E(3)+E(4) E(12)^4 - E(12)^7 - E(12)^11 sage: E(3)*E(4) E(12)^7 sage: (E(3)+E(4)).inverse() E(12)^4 + E(12)^8 + E(12)^11 sage: (E(3)+E(4))*(E(3)+E(4)).inverse() 1
And also things like Galois conjugates.
sage: (E(3)+E(4)).galois_conjugates() [E(12)^4 - E(12)^7 - E(12)^11, -E(12)^7 + E(12)^8 - E(12)^11, E(12)^4 + E(12)^7 + E(12)^11, E(12)^7 + E(12)^8 + E(12)^11]
The ticket does not use the gap interface; it depends on #9651 (Addition of combinatorial free module).
Apply
Change History (36)
comment:1 Changed 10 years ago by
- Cc sage-combinat added
comment:2 follow-up: ↓ 3 Changed 10 years ago by
comment:3 in reply to: ↑ 2 ; follow-up: ↓ 4 Changed 10 years ago by
Replying to craigcitro:
So this seems interesting (I'd never heard of the Zumbrioch basis before). I don't have anything useful to say about the utility of this, or implementing it.
However, I'd like to suggest we might want to use a different convention for the constructor -- I don't like the idea of
CyclotomicField()
working. That seems like something that's too easy for a user to accidentally do (leave out then
they intended to use), and I'd much rather they see an error than have it quietly succeed, only to discover that their cyclotomic field isn't quite what they expected (and likely slower to boot). Maybe something likeF = CyclotomicField(n=Infinity)
?
I indeed take any better suggestion! In Gap that would be Cyclotomics, but it does sound good in Field in the name. n=infinity might be misleading, since it's not about infinite roots of unity.
comment:4 in reply to: ↑ 3 ; follow-up: ↓ 5 Changed 10 years ago by
Replying to nthiery:
I indeed take any better suggestion! In Gap that would be Cyclotomics, but it does sound good in Field in the name. n=infinity might be misleading, since it's not about infinite roots of unity.
True. Maybe it's a bit too "cutesy," but using n=0
might be nice -- after all, the n
th cyclotomic field has roots of unity for all divisors of n
, so this would still hold for the universal cyclotomic field and n=0
.
comment:5 in reply to: ↑ 4 Changed 10 years ago by
Replying to craigcitro:
True. Maybe it's a bit too "cutesy," but using
n=0
might be nice -- after all, then
th cyclotomic field has roots of unity for all divisors ofn
, so this would still hold for the universal cyclotomic field andn=0
.
Mmm, any complex number is a 0-th root of unity, isn't it?
comment:6 Changed 10 years ago by
- Status changed from new to needs_work
Does anyone have a pdf copy of Zumbroich's thesis where the algorithms are described?
There is a nice version of a modified Zumbroich basis in the article I used (both are implemented in the attached file) but I don't see how the author expresses any root of unity in terms of the basis (probably just due to my lack of knowledge). But Zumbroich should describe it in more detail in his thesis.
comment:7 Changed 10 years ago by
The attached class NewCyclotomicField? uses the modified Zumbroich basis and behaves already somehow as it should (beside pretty printing).
If people think the Zumbroich basis itself is nicer, it's easy to change. I personally think the modified version as defined in Breuer - "Integral bases for subfields of cyclotomic fields" AAECC8, 279--289 (1997) has nicer properties (see the definition of the set S_n and Remark 1).
Here are some implementation problems I have:
- how can I replace CombinatorialAlgebra? by a new field constructor (I haven't found a description how to define a field)?
- how can I embed a CombinatorialAlgebra? into another one (here: NewCyclotomicField?(m) into NewCyclotomicField?(n) for m | n)?
- how can I define a new class UniversalCyclotomicField? containing all cyclotomic fields?
- how can I define the attribute self._one in the constructor of NewCyclotomicField? properly?
comment:8 Changed 10 years ago by
- Cc cwitty added
comment:9 Changed 10 years ago by
- Status changed from needs_work to needs_review
comment:10 Changed 10 years ago by
comment:11 Changed 10 years ago by
- Description modified (diff)
comment:12 Changed 10 years ago by
- Milestone set to sage-feature
- Status changed from needs_review to needs_work
Apply trac_8327_universal_cyclotomic_field-cs.2.patch
(for patchbot -- I hope that's right!).
This doesn't quite look ready to me. I haven't tried applying the patch, but just on a visual check, I can see that lots of methods aren't documented or have no tests (*every* function added to Sage must be doctested, even those whose entire body is "raise NotImplementedError"
). Also, the new module should be added to the reference manual, and the formatting should be valid ReST markup.
I very much hope you can get this code into shape -- it'd be a great thing to have in Sage -- but for now I'm afraid it's a thumbs down.
comment:13 follow-up: ↓ 14 Changed 10 years ago by
- Work issues set to Won't build, needs more doctests and Sphinxified docstrings
I've looked at the patchbot logs, and it gets worse -- the Cython code isn't valid apparently.
comment:14 in reply to: ↑ 13 Changed 10 years ago by
Replying to davidloeffler:
I've looked at the patchbot logs, and it gets worse -- the Cython code isn't valid apparently.
This was only as cython booleans changed in the meantime. Beside that, the code was always working properly. I changed this minor problem, and it should be working now again.
I improved the documentation but there are still some things to be done...
comment:15 Changed 9 years ago by
- Status changed from needs_work to needs_review
For the buildbot:
Apply trac_8327_universal_cyclotomic_field-cs.patch
All other files are obsolete, but I cannot delete them. Some documentation is still missing, but only for methods which are helper functions for others.
Would be nice to get some feedback!
comment:16 Changed 9 years ago by
Can some delete all but the youngest attached patch, the buildbot gets confused.
Thanks, Christian
comment:17 Changed 9 years ago by
- Description modified (diff)
comment:18 Changed 9 years ago by
Apply trac_8327_universal_cyclotomic_field-cs.patch
comment:19 Changed 9 years ago by
Apply only trac_8327_universal_cyclotomic_field-cs.patch
comment:20 Changed 9 years ago by
- Work issues changed from Won't build, needs more doctests and Sphinxified docstrings to needs more doctests and Sphinxified docstrings
Apply only trac_8327_universal_cyclotomic_field-cs.patch
comment:21 Changed 9 years ago by
Apply only trac_8327_universal_cyclotomic_field-cs.patch
comment:22 Changed 9 years ago by
Apply trac_8327_universal_cyclotomic_field-cs.patch
comment:23 Changed 9 years ago by
- Dependencies set to #10963
- Owner changed from davidloeffler to (none)
comment:24 Changed 9 years ago by
- Milestone changed from sage-feature to sage-4.7.2
comment:25 Changed 9 years ago by
- Dependencies #10963 deleted
comment:26 follow-up: ↓ 27 Changed 9 years ago by
- Status changed from needs_review to needs_work
When applying the sage-combinat queue on sage 4.8.alpha0, we got a compilation error on universal_cyclotomic_field_c.pyx, most likely due to the updated cython (#11761)
comment:27 in reply to: ↑ 26 Changed 9 years ago by
- Status changed from needs_work to needs_review
Replying to nthiery:
When applying the sage-combinat queue on sage 4.8.alpha0, we got a compilation error on universal_cyclotomic_field_c.pyx, most likely due to the updated cython (#11761)
My patch seems to fix the problem. At least, when one uses the new Cython spkg and applies the combinat queue up to and including Christian's patch and adds my patch as well (which is also in the combinat queue, I think), then sage builds and starts.
Note that the my patch does not add the new Cython as a dependency - it should run with the old Cython as well.
However, I already get a doctest error in devel/sage-combinat/doc/en/thematic_tutorials/sandpile.rst
. Now it is needed to test whether this error is due to the patches from here, or due to some other patch in the combinat queue.
Since it is not sure whether THIS ticket is the culprit, and since it builds with the new cython, I am promiting it to "needs review".
Apply trac_8327_universal_cyclotomic_field-cs.patch trac_8327_universal_cyclotomic_field_new_cython-sk.patch
comment:28 Changed 9 years ago by
- Description modified (diff)
Sorry, I forgot to change the ticket description.
comment:29 Changed 9 years ago by
- Status changed from needs_review to needs_work
- Work issues changed from needs more doctests and Sphinxified docstrings to needs more doctests and Sphinxified docstrings, rebase first patch
Note that the first patch does not apply on a clean sage-4.8.alpha0: The hunk that adds from sage.misc.lazy_import import lazy_import
to sage/categories/all.py does not match.
But is importing lazy_import really needed? If I see that correctly, it is not used in sage/categories/all.py
comment:30 follow-up: ↓ 31 Changed 9 years ago by
- Work issues changed from needs more doctests and Sphinxified docstrings, rebase first patch to Find dependency. Needs more doctests and Sphinxified docstrings.
Gosh. And my patch fails to apply as well, in both hunks.
So, apparently there is a dependency in the combinat queue. It should be named as a dependency for this ticket.
comment:31 in reply to: ↑ 30 Changed 9 years ago by
- Work issues changed from Find dependency. Needs more doctests and Sphinxified docstrings. to Find dependency or rebase first patch. Needs more doctests and Sphinxified docstrings.
Replying to SimonKing:
Gosh. And my patch fails to apply as well, in both hunks.
O dear, where is my mind? I had accidentally reverted the order of the patches when I tried to apply my patch.
So, for the record: The first patch does need to be rebased (or a dependency must be given). The second patch applies cleanly.
comment:32 Changed 9 years ago by
- Work issues changed from Find dependency or rebase first patch. Needs more doctests and Sphinxified docstrings. to Find dependency or rebase first patch. Fix doctests. Needs more doctests and Sphinxified docstrings.
There are several doctest errors, even when one just has
11761-cython-0.15-rebased.patch trac12029_clonable_int_array_2_list.patch trac_8327_universal_cyclotomic_field-cs.patch trac_8327_universal_cyclotomic_field_new_cython-sk.patch
with the obvious modification on trac_8327_universal_cyclotomic_field-cs.patch
.
Namely:
sage -t devel/sage-main/sage/matrix/matrix2.pyx # 25 doctests failed sage -t devel/sage-main/sage/modules/free_module.py # 2 doctests failed sage -t devel/sage-main/sage/modular/modsym/p1list_nf.py # 5 doctests failed sage -t devel/sage-main/sage/tests/startup.py # 1 doctests failed sage -t devel/sage-main/sage/rings/universal_cyclotomic_field/universal_cyclotomic_field_c.pyx # 1 doctests failed
This one here
File "/mnt/local/king/SAGE/rebase/sage-4.8.alpha0/devel/sage-main/sage/rings/universal_cyclotomic_field/universal_cyclotomic_field_c.pyx", line 239: sage: ZumbroichDecomposition_list( 6, 1 ) Expected: array([1, 1]) Got: [1, 1]
could be caused by my patch, which touches ZumbroichDecomposition
. However, I have no idea about the other errors.
comment:33 follow-up: ↓ 34 Changed 9 years ago by
Thanks for working in this patch -- I will have a look at it this morning and see what the issues are...
Best, Christian
comment:34 in reply to: ↑ 33 ; follow-up: ↓ 35 Changed 9 years ago by
Replying to stumpc5:
Thanks for working in this patch -- I will have a look at it this morning and see what the issues are...
I guess, I should first compile 4.7.2; that will take a while first...
comment:35 in reply to: ↑ 34 Changed 9 years ago by
Thanks for working in this patch -- I will have a look at it this morning and see what the issues are...
Cool!
I guess, I should first compile 4.7.2; that will take a while first...
4_8 alpha0 actually
Cheers,
comment:36 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
I found the bug and fixed it, all the above doctests now work (but only on 4.7.1, the other version is still building and will take more time).
What about "needs more doctests and Sphinxified docstrings"? I agree that the cython part is still not well documented. Could you be specific where I should explain better what's going on? Part of the problem is that computing the Zumbroich basis is something that is not simple to understand without really looking at the paper. And even after understanding that, everything becomes unreadable after implementing it in a (hopefully fairly) fast way in cython...
So this seems interesting (I'd never heard of the Zumbrioch basis before). I don't have anything useful to say about the utility of this, or implementing it.
However, I'd like to suggest we might want to use a different convention for the constructor -- I don't like the idea of
CyclotomicField()
working. That seems like something that's too easy for a user to accidentally do (leave out then
they intended to use), and I'd much rather they see an error than have it quietly succeed, only to discover that their cyclotomic field isn't quite what they expected (and likely slower to boot). Maybe something likeF = CyclotomicField(n=Infinity)
?