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: | sage-9.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 non-membership:
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 if-else
statements of lines 1740-1743.
Change History (17)
comment:1 Changed 21 months ago by
Milestone: | sage-9.3 → sage-9.4 |
---|
comment:2 Changed 18 months ago by
Milestone: | sage-9.4 → sage-9.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 ZZ-module 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 follow-up: 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 multi-line constructs may either line up under the first non-whitespace character of the last line of list ... or it may be lined up under the first character of the line that starts the multi-line 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.