Opened 9 years ago

Closed 5 years ago

#15341 closed defect (fixed)

Hashing of GammaH congruence groups is broken

Reported by: Maarten Derickx Owned by:
Priority: major Milestone: sage-8.1
Component: modular forms Keywords:
Cc: Thierry Monteil Merged in:
Authors: Maarten Derickx Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: b2c15d3 (Commits, GitHub, GitLab) Commit: b2c15d3b200aee1c9658e39d75bdc67fbe59db88
Dependencies: Stopgaps:

Status badges

Description (last modified by Maarten Derickx)

To quote the python reference manual: http://docs.python.org/2/reference/datamodel.html#object.__hash

The only required property is that objects which compare equal have the same hash value;

However:

G1=GammaH(21,[4])
G2=GammaH(21,[4,16])
print G1==G2
print hash(G1)
print hash(G2)

prints:

True
1170799062851396877
8309769839484863814

Change History (20)

comment:1 Changed 9 years ago by Maarten Derickx

Description: modified (diff)

comment:2 Changed 9 years ago by For batch modifications

Milestone: sage-6.1sage-6.2

comment:3 Changed 8 years ago by For batch modifications

Milestone: sage-6.2sage-6.3

comment:4 Changed 8 years ago by For batch modifications

Milestone: sage-6.3sage-6.4

comment:5 Changed 5 years ago by Maarten Derickx

Branch: u/mderickx/15341
Commit: b96aa08b6fe8cd1809fd514a37cc48bb6c144e99
Dependencies: 23656
Status: newneeds_review

It will fail on 32bit systems, this ticket is reviewable if one just keeps in the back of your mind that a doctest needs to be changed for 32bit systems.

Hopefully the patchbot will provide the correct value (otherwise we should find someone with a 32 bit system).


New commits:

35109f2slightly better normalize for gamma_H congruence groups
dc152c5trac 23656 fixing doctests
581adefMerge branch 'u/chapoton/23656' in 8.1.b3
2bd3819trac 23656 reviewer's suggested changes
32208f4trac 23656 detail (set)
b96aa08Make ArithmeticSubgroup.__hash__ compatible with __eq__: trac #15341

comment:6 Changed 5 years ago by Maarten Derickx

Dependencies: 23656#23656

comment:7 Changed 5 years ago by Vincent Delecroix

Author name.

comment:8 Changed 5 years ago by Vincent Delecroix

Why not

if xK in L:
    rts_L.append((L(xK), mult))

comment:9 Changed 5 years ago by Maarten Derickx

Authors: Maarten Derickx

Hi thanks for looking at this,

Sorry, I should have been more clear. Only commmit b96aa08b6fe8cd1809fd514a37cc48bb6c144e99 is new. Al the other commits are just #23656 so your comment only makes sense for that ticket, and doesn't relate to the code under review here.

Do you happen to know a way to only show the new commits at this ticket? I tried setting #23656 as a dependency. But that doesn't work.

comment:10 Changed 5 years ago by Vincent Delecroix

My comment does not apply to anything, it was intended for #23726

comment:11 Changed 5 years ago by Maarten Derickx

Cc: Thierry Monteil added

comment:12 in reply to:  10 ; Changed 5 years ago by Maarten Derickx

Hi Thierry Monteil,

I saw at https://wiki.sagemath.org/buildbot/owners that you have a 32bit patchbot. Could you test this ticket so that I know what hashes are returned on a 32bit machine.

Thanks in advance, Maarten

Last edited 5 years ago by Maarten Derickx (previous) (diff)

comment:13 Changed 5 years ago by Thierry Monteil

I am compiling your branch on a 32bit VM running Debian stretch. Which files chould i doctest ?

comment:14 Changed 5 years ago by Maarten Derickx

Thanks, the file is src/sage/modular/arithgroup/arithgroup_generic.py

comment:15 Changed 5 years ago by git

Commit: b96aa08b6fe8cd1809fd514a37cc48bb6c144e99b2c15d3b200aee1c9658e39d75bdc67fbe59db88

Branch pushed to git repo; I updated commit sha1. New commits:

b2c15d3trac #15341 fixed 32bit doctest

comment:16 Changed 5 years ago by Thierry Monteil

I got :

sagemath@tmonteil-debian-stretch-32:/opt/sagemath/sage-8.0$ ./sage -t src/sage/modular/arithgroup/arithgroup_generic.py
Forcing sage-location, probably because a new package was installed.
Cleaning up, do not interrupt this.
Done cleaning.
Running doctests with ID 2017-08-29-22-50-23-b6ae0811.
Git branch: develop
Using --optional=4ti2,benzene,bliss,buckygen,cbc,ccache,cmake,coxeter3,cryptominisat,csdp,d3js,database_gap,database_pari,frobby,gambit,gap_jupyter,gap_packages,gdb,giacpy_sage,gmpy2,gp2c,igraph,latte_int,libbraiding,libhomfly,libogg,lidia,lrslib,mcqd,meataxe,mpir,normaliz,ore_algebra,pandoc_attributes,pandocfilters,pari_jupyter,plantri,pynormaliz,pysingular,python2,python_igraph,qepcad,rst2ipynb,saclib,sage,scons,singular_jupyter,sip,sirocco,tdlib,termcap,tides,topcom
Doctesting 1 file.
sage -t --warn-long 47.4 src/sage/modular/arithgroup/arithgroup_generic.py
**********************************************************************
File "src/sage/modular/arithgroup/arithgroup_generic.py", line 199, in sage.modular.arithgroup.arithgroup_generic.ArithmeticSubgroup.__hash__
Failed example:
    Gamma0(11).__hash__()
Expected:
    -545929996 
Got:
    118770652
**********************************************************************
File "src/sage/modular/arithgroup/arithgroup_generic.py", line 202, in sage.modular.arithgroup.arithgroup_generic.ArithmeticSubgroup.__hash__
Failed example:
    Gamma1(11).__hash__()
Expected:
    -830809815 
Got:
    201042552
**********************************************************************
1 item had failures:
   2 of   8 in sage.modular.arithgroup.arithgroup_generic.ArithmeticSubgroup.__hash__
    [159 tests, 2 failures, 5.60 s]
----------------------------------------------------------------------
sage -t --warn-long 47.4 src/sage/modular/arithgroup/arithgroup_generic.py  # 2 doctests failed
----------------------------------------------------------------------
Total time for all tests: 5.7 seconds
    cpu time: 3.5 seconds
    cumulative wall time: 5.6 seconds

Which is consistent with your latest commit.

comment:17 Changed 5 years ago by Maarten Derickx

Milestone: sage-6.4sage-8.1

comment:18 in reply to:  12 Changed 5 years ago by Vincent Delecroix

Replying to mderickx:

Hi Thierry Monteil,

I saw at https://wiki.sagemath.org/buildbot/owners that you have a 32bit patchbot. Could you test this ticket so that I know what hashes are returned on a 32bit machine.

Hashing on a 32 bit is just the same thing but modulo 2^32

sage: 3713075136762760156 % (2**32)
118770652

(though the result are in (-231, 231])

comment:19 Changed 5 years ago by Frédéric Chapoton

Dependencies: #23656
Reviewers: Frédéric Chapoton
Status: needs_reviewpositive_review

ok

comment:20 Changed 5 years ago by Volker Braun

Branch: u/mderickx/15341b2c15d3b200aee1c9658e39d75bdc67fbe59db88
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.