Opened 23 months ago
Closed 14 months ago
#31507 closed defect (fixed)
Checking if an element is in a subgroup can raise 'TypeError'
Reported by:  bouvier  Owned by:  

Priority:  major  Milestone:  sage9.5 
Component:  group theory  Keywords:  groups 
Cc:  slelievre  Merged in:  
Authors:  Maarten Derickx  Reviewers:  Dave Morris, Samuel Lelièvre 
Report Upstream:  N/A  Work issues:  
Branch:  c790824 (Commits, GitHub, GitLab)  Commit:  c790824d16de58c00c2a3361e0cbe19d5ae432d1 
Dependencies:  Stopgaps: 
Description (last modified by )
In Sage 9.2, after defining:
sage: G = AbelianGroup(2, gens_orders=[16, 16]) sage: f0, f1 = G.gens() sage: H = G.subgroup ([f0*f1^3])
the following correctly determines nonmembership:
sage: f0*f1^2 in H False
but the following gives a type error:
sage: f0 in H TypeError: no conversion of this rational to integer
The error seems to come from the __contains__
method
of src/sage/groups/abelian_gps/abelian_group.py
(around line 1715), in particular the ifelse
statements of lines 17401743.
Change History (17)
comment:1 Changed 21 months ago by
Milestone:  sage9.3 → sage9.4 

comment:2 Changed 18 months ago by
Milestone:  sage9.4 → sage9.5 

comment:3 Changed 15 months ago by
From #32910:
Ok, I don't have a development version of sage yet. And I have trouble getting one. But here is some code I wrote that I used to monkey patch
sage.groups.abelian_gps.abelian_group.AbelianGroup_subgroup.__contains__
and it seems to work like a charm for my application.
def __contains__(self, x): """ Test whether ``x`` is an element of this subgroup. EXAMPLES:: sage: G.<a,b> = AbelianGroup(2) sage: A = G.subgroup([a]) sage: a in G True sage: a in A True TESTS: Check that :trac:`32910` is fixed:: sage: Zmstar.<a,b> = AbelianGroup(2,[4,576]) sage: Hgens = [a**2,a*b**2] sage: H = Zmstar.subgroup(Hgens) sage: g = Zmstar.gen(1)**3 sage: g in H True """ amb_inv = self.ambient_group().gens_orders() inv_basis = diagonal_matrix(ZZ,amb_inv) gens_basis = matrix( ZZ, len(self._gens), len(amb_inv), [g.list() for g in self._gens] ) return vector(ZZ, x.list()) in inv_basis.stack(gens_basis).row_module() sage.groups.abelian_gps.abelian_group.AbelianGroup_subgroup.__contains__ = __contains__
comment:4 Changed 15 months ago by
Branch:  → public/31507 

comment:5 Changed 15 months ago by
Authors:  → Maarten Derickx 

Commit:  → de1d131ddcc64a22086bd51d8c4755c9ae1d47ae 
Reviewers:  → Dave Morris 
Status:  new → needs_review 
Here is a branch that implements the patch. I made a few reviewer changes: I kept some of the original code at the start of the method, I added some import statements, and I think the doctest was wrong (the correct answer is False
, not True
).
The other option would be to fix the bug in the original code. However, I think it makes sense to use this simpler code (which delegates the work to ZZmodule methods), because it is easier to understand and to maintain.
The example from this ticket should probably be added as an additional doctest, but I forgot to do that. I am setting to "needs review" to start getting comments from humans and patchbots. I will do the review myself if we don't hear from anyone.
New commits:
de1d131  trac 31507 subgroup contains

comment:6 Changed 15 months ago by
Commit:  de1d131ddcc64a22086bd51d8c4755c9ae1d47ae → a384184c6e8edccb2cc5c1e0b8c75d6e394ef635 

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

comment:7 Changed 15 months ago by
Hi Dave,
Thanks for turning this into a git branch and making sure that the non algorithmic part of the code like the is_instance
check are still there. And indeed you are right it should return False.
Is there a reason to do the imports inside of the function and not at the top of the file? Was there a problem with circular imports?
comment:8 followup: 10 Changed 15 months ago by
Cc:  slelievre added 

Description:  modified (diff) 
The following suggestions are to
 use Sage preparsing of
^
to**
in doctests,  use
b
rather thanZmstar.gen(1)
,  rename
Zmstar
toG
,  increase test density.
 sage: Zmstar.<a,b> = AbelianGroup(2, [4, 576]) + sage: G.<a,b> = AbelianGroup(2, [4, 576])  sage: Hgens = [a**2,a*b**2] + sage: Hgens = [a^2, a*b^2]  sage: g = Zmstar.gen(1)**3  sage: g in H  False  sage: a^3*b^2 in H  True + sage: [g in H for g in (a^3, b^2, b^3, a^3*b^2)] + [False, False, False, True]
 sage: f0*f1^2 in H  False  sage: f0 in H  False + sage: [g in H for g in (f0, f0*f1^2, f0*f1^3, f0*f1^4)] + [False, False, True, False]
Another cosmetic change I would make, but maybe my pep8 is off:
 gens_basis = matrix(  ZZ, len(self._gens), len(amb_inv), [g.list() for g in self._gens]  ) + gens_basis = matrix(ZZ, len(self._gens), len(amb_inv), + [g.list() for g in self._gens])
Feel free to ignore these minor comments.
comment:9 Changed 15 months ago by
I went for this simpler implementation because I had trouble understanding what the original code was trying to do. I am guessing that maybe the divisions had to be integer divisions //
. And I also had the feeling that the original code was relying on the self._gens being in some sort of standard form so that the algorithm is able to reduce x
to 1 if and only if x is in self. However as the code below shows, there is nothing guaranteeing that H._gens is in any sort of standard from. It is just what was passed during construction.
sage: Zmstar.<a,b> = AbelianGroup(2) ....: Hgens = [a**5*b, a**3, a*b, b**7] ....: H = Zmstar.subgroup(Hgens) ....: H._gens (a^5*b, a^3, a*b, b^7)
The following piece of code show a more subtle (i.e. not even raising an error) way that the old code can fail.
sage: G.<a,b> = AbelianGroup(2) ....: Hgens = [a*b, a*b^1] ....: H = G.subgroup(Hgens) ....: b**2 in H False sage: H.gen(0)/H.gen(1)==b**2 True
comment:10 Changed 15 months ago by
Replying to slelievre:
Another cosmetic change I would make, but maybe my pep8 is off:
 gens_basis = matrix(  ZZ, len(self._gens), len(amb_inv), [g.list() for g in self._gens]  ) + gens_basis = matrix(ZZ, len(self._gens), len(amb_inv), + [g.list() for g in self._gens])
I actually let my code be formatted by black whose output is guaranteed to be pep8 compatible. And black proposed the above linebreak so at least the original is pep8 compatible. Although black does put the closing parenthesis unindented.
comment:11 Changed 15 months ago by
Commit:  a384184c6e8edccb2cc5c1e0b8c75d6e394ef635 → ef7bd6d93085c81ca52aa96170429e7b2697d51e 

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

comment:12 Changed 15 months ago by
Commit:  ef7bd6d93085c81ca52aa96170429e7b2697d51e → c790824d16de58c00c2a3361e0cbe19d5ae432d1 

Branch pushed to git repo; I updated commit sha1. New commits:
c790824  change another ** to ^

comment:13 Changed 15 months ago by
I think this update implements all of the suggestions.
I also broke two lines that were more than 80 characters, and added a check for whether "junk" is in H in the first test, because the method should not choke on stupid input.
And I added the last example of comment:9 as another test. I think that example is very strong evidence that this ticket takes the right approach by getting rid of code duplication.
I apologize for the python style errors  I am not fluent. PEP8 says "Imports are always put at the top of the file..." so I moved them there. It also says "The closing brace/bracket/parenthesis on multiline constructs may either line up under the first nonwhitespace character of the last line of list ... or it may be lined up under the first character of the line that starts the multiline construct ...". So (regarding comment:10) I left the closing parenthesis on its own line (but reduced the indent to match the author's original code that black liked).
Further comments or corrections (or corrections to my implementations of the corrections) are welcome, of course. If there aren't any, and the patchbot comes back green again, then I think we are done.
comment:15 Changed 15 months ago by
Reviewers:  Dave Morris → Dave Morris, Samuel Lelièvre 

Status:  needs_review → positive_review 
Likewise. And green light from a patchbot.
comment:16 Changed 15 months ago by
Thanks to both of you for the code, the comments and suggestions, and the review!
comment:17 Changed 14 months ago by
Branch:  public/31507 → c790824d16de58c00c2a3361e0cbe19d5ae432d1 

Resolution:  → fixed 
Status:  positive_review → closed 
Moving to 9.4, as 9.3 has been released.