#11598: Congruence testing for odd modular subgroups
---------------------------------+------------------------------------------
Reporter: davidloeffler | Owner: craigcitro
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.7.2
Component: modular forms | Keywords: modular congruence subgroup
Work_issues: | Upstream: N/A
Reviewer: Vincent Delecroix | Author: David Loeffler
Merged: | Dependencies: #11422
---------------------------------+------------------------------------------
Comment(by vdelecroix):
Replying to [comment:8 davidloeffler]:
> I've done some tests.
> [...]
> but it's not totally clear to me what the advantage of using a set type
for the {{{bucket}}} variable is.
To check if an element is in a list is linear in the size of the list, but
checking if an element is in a set is constant time (up to a critical
size). The reason is that Python set are implemented using a hash table.
Now, the test "if HH not in bucket" is made exactly "n" times in your
algorithm and bucket grows quite fast if the centralizer of G is small.
The gain of complexity is dramatic.
> why keep the list as well -- why not just {{{return list(bucket)}}} at
the end?
The way you generate the odd subgroups is somewhat canonical and the
output is sorted that way. If the returned value is "list(bucket)" then
the output is randomized. But, I'm not too much convinced by having at the
same time a list and a set containing exactly the same values. It's up to
you to make the change.
> it seems odd not to disable the check parameter in
{{{one_odd_subgroup}}};
It is not time critical if the function is called once. But if somebody
want 100 random odd subgroups then it would be better to disable the check
parameter (done in the reviewer patch).
> and the third and fourth lines in the "Testing randomness" doctest in
{{{one_odd_subgroup}}} seem slightly pointless -- with a random routine,
checking that it works is sensible, but running a test on the output and
ignoring the result seems bizarre.
Thanks, I changed the test (see the reviewer patch). I am not so familiar
with how is tested the random stuff in Sage.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11598#comment:9>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
