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

Status badges

Description (last modified by slelievre)

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 mkoeppe

Milestone: sage-9.3sage-9.4

Moving to 9.4, as 9.3 has been released.

comment:2 Changed 18 months ago by mkoeppe

Milestone: sage-9.4sage-9.5

comment:3 Changed 15 months ago by mderickx

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 gh-DaveWitteMorris

Branch: public/31507

comment:5 Changed 15 months ago by gh-DaveWitteMorris

Authors: Maarten Derickx
Commit: de1d131ddcc64a22086bd51d8c4755c9ae1d47ae
Reviewers: Dave Morris
Status: newneeds_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:

de1d131trac 31507 subgroup contains

comment:6 Changed 15 months ago by git

Commit: de1d131ddcc64a22086bd51d8c4755c9ae1d47aea384184c6e8edccb2cc5c1e0b8c75d6e394ef635

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

a384184additional doctests

comment:7 Changed 15 months ago by mderickx

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?

Last edited 15 months ago by mderickx (previous) (diff)

comment:8 Changed 15 months ago by slelievre

Cc: slelievre added
Description: modified (diff)

The following suggestions are to

  • use Sage preparsing of ^ to ** in doctests,
  • use b rather than Zmstar.gen(1),
  • rename Zmstar to G,
  • 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 mderickx

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 in reply to:  8 Changed 15 months ago by mderickx

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 git

Commit: a384184c6e8edccb2cc5c1e0b8c75d6e394ef635ef7bd6d93085c81ca52aa96170429e7b2697d51e

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

ef7bd6dreviewer suggestions

comment:12 Changed 15 months ago by git

Commit: ef7bd6d93085c81ca52aa96170429e7b2697d51ec790824d16de58c00c2a3361e0cbe19d5ae432d1

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

c790824change another ** to ^

comment:13 Changed 15 months ago by gh-DaveWitteMorris

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:14 Changed 15 months ago by mderickx

Thanks for this! Form my part it looks good to go.

comment:15 Changed 15 months ago by slelievre

Reviewers: Dave MorrisDave Morris, Samuel Lelièvre
Status: needs_reviewpositive_review

Likewise. And green light from a patchbot.

comment:16 Changed 15 months ago by gh-DaveWitteMorris

Thanks to both of you for the code, the comments and suggestions, and the review!

comment:17 Changed 14 months ago by vbraun

Branch: public/31507c790824d16de58c00c2a3361e0cbe19d5ae432d1
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.