Implement the universal cyclotomic field, using Zumbroich basis

[nthiery]

This patch provides the universal cyclotomic field

    sage: UCF.<E> = UniversalCyclotomicField(); 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.

Depends on #13765

CC: @sagetrac-sage-combinat @sagetrac-cwitty

Component: number fields

Keywords: Cyclotomic field, Zumbroich basis

Author: Christian Stump, Simon King

Reviewer: Frédéric Chapoton

Merged: sage-5.7.beta3

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

[craigcitro]

comment:2

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 the n 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 like F = CyclotomicField(n=Infinity)?

[nthiery]

comment:3

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 the n 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 like F = 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.

[craigcitro]

comment:4

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 nth cyclotomic field has roots of unity for all divisors of n, so this would still hold for the universal cyclotomic field and n=0.

[nthiery]

comment:5

Replying to @craigcitro:

True. Maybe it's a bit too "cutesy," but using n=0 might be nice -- after all, the nth cyclotomic field has roots of unity for all divisors of n, so this would still hold for the universal cyclotomic field and n=0.

Mmm, any complex number is a 0-th root of unity, isn't it?

[stumpc5]

comment:6

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.

[stumpc5]

comment:7

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?

[stumpc5]

Author: Christian Stump

[loefflerd]

comment:12

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.

[loefflerd]

Work Issues: Won't build, needs more doctests and Sphinxified docstrings

[loefflerd]

comment:13

I've looked at the patchbot logs, and it gets worse -- the Cython code isn't valid apparently.

[stumpc5]

comment:14

Replying to @loefflerd:

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

[stumpc5]

comment:15

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!

[stumpc5]

comment:16

Can some delete all but the youngest attached patch, the buildbot gets confused.

Thanks, Christian

[loefflerd]

comment:18

Apply trac_8327_universal_cyclotomic_field-cs.patch

[stumpc5]

comment:19

Apply only trac_8327_universal_cyclotomic_field-cs.patch

[stumpc5]

comment:20

Apply only trac_8327_universal_cyclotomic_field-cs.patch

[jdemeyer]

comment:194

Replying to @stumpc5:

I wonder if you could have another look and either rebase the patch

Why should it be rebased? The fact that the patchbot is struggling is a bug with the patchbot, I don't think this ticket is to blame.

Anyway, I don't want to review this ticket (simply because I cannot review every ticket that I put to needs_work), but it should be easy for the original reviewer. Frédéric, can you do it?

[stumpc5]

comment:195

Replying to @jdemeyer:

Replying to @stumpc5:
Anyway, I don't want to review this ticket (simply because I cannot review every ticket that I put to needs_work)

Sorry, I didn't want to say you should actually review the patch again (though my message sounded like that), but only to possibly rebase it in case this would be the only modification needed to finally get this patch merged...

[fchapoton]

comment:196

There remains 2 raise with the old syntax

raise ValueError, "n (=%s) must be a positive integer"%n 

raise TypeError, "Embedding (type %s) must be an element." % type(embedding) 

Please convert them to the Python 3 syntax.

[vbraun]

comment:197

On the topic of raising exceptions: start lower-case (and don't form complete sentences). Moreover, the coercion system will often feed you with invalid data to figure out what you can and cannot do. Hence it is best to avoid unnecessary work like creating string representations and concatenating them to form an exception message. Just raise TypeError('x must be an element').

[jdemeyer]

comment:198

Another possible complaint about this patch is that it uses quite some Cython code but always without sig_on()/sig_off(). As a consequence, this code might not be interruptible on CTRL-C. I don't know to what extent this is a problem, I'm just pointing it out. Anyway, it can't hurt to put some sig_check() calls inside the loops.

[stumpc5]

comment:199

A general comment concerning several complaints on this ticket from various directions: If you ask mathematicians to contribute to Sage, you get mathematicians writing code and code that is not necessarily perfect. This does have disadvantages! But please don't blame them (i.e. me here) for not being perfect programmers!

Beside that, I fixed the complaint concerning error messages and their Python 3 syntax, but I am not going to go into interruption handling in cython. This can be handled in another ticket by someone more advanced.

Finally: I already spent much too much time on this ticket (i.e., I implemented the stuff I actually needed for my research 2 years ago, all further hours and days were not spent anymore for my primary research). I would very much appreciate if we could get this ticket into Sage, and then solve further issues in other patches.

[jdemeyer]

comment:200

Replying to @stumpc5:

I am not going to go into interruption handling in cython.

No problem, note that I purposely did not set the status to needs_work for this. Your code is certainly not the only part of Sage with this problem.

Finally: I already spent much too much time on this ticket (i.e., I implemented the stuff I actually needed for my research 2 years ago, all further hours and days were not spent anymore for my primary research).

It's simply a fact that going from proof-of-concept-research-code to actual good code to be included in Sage is a non-trivial step. You could say it's unfortunate, but that's the way it is.

[vbraun]

comment:201

I actually do think the code here is pretty good, so please don't take everything as a criticism. I think this ticket is good to go, I just wanted to wait and see if the recently updated patchbot fares better at running it...

[jdemeyer]

comment:202

Now that you have changed the exceptions, also the doctests for the exceptions need to changed. I see various failures along the lines of

**********************************************************************
File "/release/merger/sage-5.7.beta3/devel/sage-main/sage/rings/universal_cyclotomic_field/universal_cyclotomic_field.py", line 1755:
    sage: E(6).galois_conjugates(5)
Expected:
    Traceback (most recent call last):
    ...
    ValueError: the given integer (5) is not a multiple of the field order of -E(3)^2
Got:
    Traceback (most recent call last):
      File "/release/merger/sage-5.7.beta3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/release/merger/sage-5.7.beta3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/release/merger/sage-5.7.beta3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_61[10]>", line 1, in <module>
        E(Integer(6)).galois_conjugates(Integer(5))###line 1755:
    sage: E(6).galois_conjugates(5)
      File "/release/merger/sage-5.7.beta3/local/lib/python/site-packages/sage/rings/universal_cyclotomic_field/universal_cyclotomic_field
.py", line 1765, in galois_conjugates
        raise ValueError("The given integer (%s) is not a multiple of the field order of %s"%(m,self))
    ValueError: The given integer (5) is not a multiple of the field order of -E(3)^2
**********************************************************************

[stumpc5]

Attachment: trac_8327-universal_cyclotomic_field-cs.patch.gz

[stumpc5]

comment:203

Replying to @jdemeyer:

Now that you have changed the exceptions, also the doctests for the exceptions need to changed.

Sorry, I exported the patch before qrefreshing...

[fchapoton]

comment:205

ok, bot is happy again. Positive review once more.

[jdemeyer]

Merged: sage-5.7.beta3

[nthiery]

comment:207

Yippee! Congratulations Christian!

And thanks so much for going the extra mile! I agree that all the extra work you did for getting this ticket into Sage involved not only necessary cleanup but also extra features that could have been left aside in a first round!

Thanks!
Nicolas

[stumpc5]

comment:208

Replying to @nthiery:

Yippee!

+1!!!

[kcrisman]

comment:209

Just fyi, #14118 had to be opened regarding this, not that Cygwin is currently supported (yet!). Hopefully this will make it more portable in the long run anyway.