#5250 closed defect (fixed)
[with patch, positive review] Bug in multiplicative_generator function for Z/NZ
Reported by: | was | Owned by: | davidloeffler |
---|---|---|---|
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: | 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 5 years ago by davidloeffler
- Owner changed from was to davidloeffler
- Status changed from new to assigned
- Summary changed from But in multiplicative_generator function for Z/NZ to [with patch, needs review] Bug in multiplicative_generator function for Z/NZ
comment:2 Changed 5 years ago by davidloeffler
- Summary changed from [with patch, needs review] Bug in multiplicative_generator function for Z/NZ to [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 5 years ago by davidloeffler
- Summary changed from [with patch, not ready for review] Bug in multiplicative_generator function for Z/NZ to [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 5 years ago by cremona
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 5 years ago by cremona
- Summary changed from [with patch, needs review] Bug in multiplicative_generator function for Z/NZ to [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 5 years ago by davidloeffler
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.
comment:7 Changed 5 years ago by davidloeffler
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 5 years ago by mabshoff
- Summary changed from [with patch, with positive review] Bug in multiplicative_generator function for Z/NZ to [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 5 years ago by davidloeffler
Ah, I didn't do the long doctests. It is harmless. Patch coming in a couple of seconds.
comment:10 Changed 5 years ago by davidloeffler
- Summary changed from [with patch, needs work] Bug in multiplicative_generator function for Z/NZ to [with patch, positive review] Bug in multiplicative_generator function for Z/NZ
Here it is.
comment:11 follow-up: ↓ 12 Changed 5 years ago by 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.)
comment:12 in reply to: ↑ 11 Changed 5 years ago by cremona
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 5 years ago by mabshoff
- Resolution set to fixed
- Status changed from assigned to closed
Merged all three patches in Sage 4.0.alpha0.
Cheers,
Michael
comment:14 Changed 5 years ago by davidloeffler
- Merged in set to 4.0.alpha0
- Reviewers set to 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 and unit_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.