Opened 6 years ago

Closed 5 years ago

Last modified 5 years ago

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

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

Download all attachments as: .zip

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

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

Changed 5 years ago by davidloeffler

patch against 3.4.2.final

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.

Changed 5 years ago by davidloeffler

fix doctest from #4357 which this breaks

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.

Changed 5 years ago by davidloeffler

fix borken -long doctest in modsym/ambient.py

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

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