#5250 closed defect (fixed)
[with patch, positive review] Bug in multiplicative_generator function for Z/NZ
Reported by: | William Stein | Owned by: | David Loeffler |
---|---|---|---|
Priority: | major | Milestone: | sage-4.0 |
Component: | number theory | Keywords: | |
Cc: | Merged in: | 4.0.alpha0 | |
Authors: | David Loeffler | Reviewers: | John Cremona, Craig Citro |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Notice that (ZZ/162ZZ)^{* *is* cyclic: }
sage: R = Integers(162) sage: R(5).multiplicative_order() 54 sage: euler_phi(162) 54
However, Sage gets this totally wrong:
sage: R.multiplicative_generator() Traceback (most recent call last): ... ValueError: multiplicative group of this ring is not cyclic
This bug came up for me today while doing some research. I'm glad I didn't believe Sage :-).
Attachments (3)
Change History (17)
comment:1 Changed 13 years ago by
Owner: | changed from William Stein to David Loeffler |
---|---|
Status: | new → assigned |
Summary: | But in multiplicative_generator function for Z/NZ → [with patch, needs review] Bug in multiplicative_generator function for Z/NZ |
comment:2 Changed 13 years ago by
Summary: | [with patch, needs review] Bug in multiplicative_generator function for Z/NZ → [with patch, not ready for review] Bug in multiplicative_generator function for Z/NZ |
---|
Oops, just realised that this breaks one or two doctests (because various functions expect the list of unit gens to contain 1's).
comment:3 Changed 13 years ago by
Summary: | [with patch, not ready for review] Bug in multiplicative_generator function for Z/NZ → [with patch, needs review] Bug in multiplicative_generator function for Z/NZ |
---|
Here's a patch that fixes the (relatively easy) bug in multiplicative_generator and the (much deeper) bug in multiplicative_subgroups. The latter is written in such a way that it should be very easy to transplant into was's new framework for Abelian groups based on 5882.
comment:4 Changed 13 years ago by
A valiant job: if I come against something which depends on adding functionality to abelian groups I just give up, but you did it. (In my ideal world every finite abelian group would internally be stored and work with elementary divisors, which would make the code simpler. Never mind).
Expecting to review this over the weekend.
comment:5 Changed 13 years ago by
Summary: | [with patch, needs review] Bug in multiplicative_generator function for Z/NZ → [with patch, with positive review] Bug in multiplicative_generator function for Z/NZ |
---|
Positive review. The code looks ok to me, applies to 3.4.2 and tests pass (I tested abelian_groups and all modular).
No doubt the subgroups function in abelian groups will be superseded one day (after #5882) but that's no reason to stop this. And both the original bugs are fixed.
comment:6 Changed 13 years ago by
Michael: don't merge this one quite yet -- it breaks one of the new doctests I added as part of #4357, so if you apply both patches you will get a doctest failure in sage/modular/modform/ambient_eps.py. I will do yet another patch to sort this out.
Changed 13 years ago by
Attachment: | trac_5250_doctest_fix.patch added |
---|
fix doctest from #4357 which this breaks
comment:7 Changed 13 years ago by
Right, that should fix it. (I'm trying to ensure that the tickets of mine for which I have patches up right now apply without conflicts if they are all applied *in order of ticket number*.)
comment:8 Changed 13 years ago by
Summary: | [with patch, with positive review] Bug in multiplicative_generator function for Z/NZ → [with patch, needs work] Bug in multiplicative_generator function for Z/NZ |
---|
I am observing one more doctest failure in ambient.py with -long:
sage -t -long "devel/sage/sage/modular/modsym/ambient.py" ********************************************************************** File "/scratch/mabshoff/sage-4.0.alpha0/devel/sage/sage/modular/modsym/ambient.py", line 1104: sage: M.factorization() # long time (about 8 seconds) Expected: (Modular Symbols subspace of dimension 1 of Modular Symbols space of dimension 7 and level 38, weight 2, character [1, zeta3], sign 1, over Cyclotomic Field of order 3 and degree 2) * (Modular Symbols subspace of dimension 2 of Modular Symbols space of dimension 7 and level 38, weight 2, character [1, zeta3], sign 1, over Cyclotomic Field of order 3 and degree 2) * (Modular Symbols subspace of dimension 2 of Modular Symbols space of dimension 7 and level 38, weight 2, character [1, zeta3], sign 1, over Cyclotomic Field of order 3 and degree 2) * (Modular Symbols subspace of dimension 2 of Modular Symbols space of dimension 7 and level 38, weight 2, character [1, zeta3], sign 1, over Cyclotomic Field of order 3 and degree 2) Got: (Modular Symbols subspace of dimension 1 of Modular Symbols space of dimension 7 and level 38, weight 2, character [zeta3], sign 1, over Cyclotomic Field of order 3 and degree 2) * (Modular Symbols subspace of dimension 2 of Modular Symbols space of dimension 7 and level 38, weight 2, character [zeta3], sign 1, over Cyclotomic Field of order 3 and degree 2) * (Modular Symbols subspace of dimension 2 of Modular Symbols space of dimension 7 and level 38, weight 2, character [zeta3], sign 1, over Cyclotomic Field of order 3 and degree 2) * (Modular Symbols subspace of dimension 2 of Modular Symbols space of dimension 7 and level 38, weight 2, character [zeta3], sign 1, over Cyclotomic Field of order 3 and degree 2) **********************************************************************
Cheers,
Michael
comment:9 Changed 13 years ago by
Ah, I didn't do the long doctests. It is harmless. Patch coming in a couple of seconds.
Changed 13 years ago by
Attachment: | trac_5250_doctest_fix_2.patch added |
---|
fix borken -long doctest in modsym/ambient.py
comment:10 Changed 13 years ago by
Summary: | [with patch, needs work] Bug in multiplicative_generator function for Z/NZ → [with patch, positive review] Bug in multiplicative_generator function for Z/NZ |
---|
Here it is.
comment:11 follow-up: 12 Changed 13 years ago by
Just as a double-check, I'll be another voice to say the last two doctest patches look good. (The old code had 1 as one of the multiplicative generators of Z/38
... pretty funny.)
comment:12 Changed 13 years ago by
Replying to craigcitro:
Just as a double-check, I'll be another voice to say the last two doctest patches look good. (The old code had 1 as one of the multiplicative generators of
Z/38
... pretty funny.)
I agree that the new output looks good (and the old one very bad for the reasons stated).
comment:13 Changed 13 years ago by
Resolution: | → fixed |
---|---|
Status: | assigned → closed |
Merged all three patches in Sage 4.0.alpha0.
Cheers,
Michael
comment:14 Changed 13 years ago by
Authors: | → David Loeffler |
---|---|
Merged in: | → 4.0.alpha0 |
Reviewers: | → John Cremona, Craig Citro |
This comes up whenever n is twice a power of an odd prime. In these cases,
multiplicative_group_is_cyclic
would wrongly return False,multiplicative_generator
would throw an error andunit_gens
would return a list of length 2 one of whose elements is 1.The attached patch fixes this. It also streamlines the code a bit by using the is_prime_power function; this is more readable, and in theory should be quicker than factorisation. At the moment it is actually a tiny fraction slower, but this is a consequence of an awkward workaround for a Pari bug (see #4777) and it will presumably be fixed in the future.