Checking if an element is in a subgroup can raise 'TypeError'

[sagetrac-bouvier]

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.

CC: @slel

Component: group theory

Author: Maarten Derickx

Branch/Commit: c790824

Reviewer: Dave Morris, Samuel Lelièvre

Issue created by migration from https://trac.sagemath.org/ticket/31507

[mkoeppe]

comment:1

Moving to 9.4, as 9.3 has been released.

[koffie]

comment:3

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__

[DaveWitteMorris]

Branch: public/31507

[DaveWitteMorris]

Author: Maarten Derickx

[DaveWitteMorris]

Reviewer: Dave Morris

[DaveWitteMorris]

Commit: de1d131

[DaveWitteMorris]

comment:5

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

[sagetrac-git]

Changed commit from de1d131 to a384184

[sagetrac-git]

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

a384184

additional doctests

[koffie]

comment:7

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?

[slel]

comment:8

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.

[koffie]

comment:9

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

[koffie]

comment:10

Replying to @slel:

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.

[sagetrac-git]

Changed commit from a384184 to ef7bd6d

[sagetrac-git]

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

ef7bd6d

reviewer suggestions

[sagetrac-git]

Changed commit from ef7bd6d to c790824

[sagetrac-git]

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

c790824

change another ** to ^

[DaveWitteMorris]

comment:13

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.

[koffie]

comment:14

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

[slel]

Changed reviewer from Dave Morris to Dave Morris, Samuel Lelièvre

[slel]

comment:15

Likewise. And green light from a patchbot.

[DaveWitteMorris]

comment:16

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

[vbraun]

Changed branch from public/31507 to c790824