Opened 14 years ago

Closed 13 years ago

Last modified 13 years ago

#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:

Status badges

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)

trac_5250.patch (22.9 KB) - added by David Loeffler 13 years ago.
patch against 3.4.2.final
trac_5250_doctest_fix.patch (878 bytes) - added by David Loeffler 13 years ago.
fix doctest from #4357 which this breaks
trac_5250_doctest_fix_2.patch (2.3 KB) - added by David Loeffler 13 years ago.
fix borken -long doctest in modsym/ambient.py

Download all attachments as: .zip

Change History (17)

comment:1 Changed 13 years ago by David Loeffler

Owner: changed from William Stein to David Loeffler
Status: newassigned
Summary: But in multiplicative_generator function for Z/NZ[with patch, needs review] Bug in multiplicative_generator function for Z/NZ

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.

comment:2 Changed 13 years ago by David Loeffler

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

Changed 13 years ago by David Loeffler

Attachment: trac_5250.patch added

patch against 3.4.2.final

comment:3 Changed 13 years ago by David Loeffler

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 John 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 13 years ago by John Cremona

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 David Loeffler

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 David Loeffler

Attachment: trac_5250_doctest_fix.patch added

fix doctest from #4357 which this breaks

comment:7 Changed 13 years ago by David Loeffler

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 Michael Abshoff

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 David Loeffler

Ah, I didn't do the long doctests. It is harmless. Patch coming in a couple of seconds.

Changed 13 years ago by David Loeffler

fix borken -long doctest in modsym/ambient.py

comment:10 Changed 13 years ago by David Loeffler

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 Changed 13 years ago by Craig Citro

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 13 years ago by John 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 13 years ago by Michael Abshoff

Resolution: fixed
Status: assignedclosed

Merged all three patches in Sage 4.0.alpha0.

Cheers,

Michael

comment:14 Changed 13 years ago by David Loeffler

Authors: David Loeffler
Merged in: 4.0.alpha0
Reviewers: John Cremona, Craig Citro
Note: See TracTickets for help on using tickets.