Group algebra bug

[trevorkarn]

Discussed
on sage-support
and sage-devel.

There is a coercion bug that causes the example:

H = PermutationGroup([ [(1,2), (3,4)], [(5,6,7),(12,14,18)] ])
kH = H.algebra(GF(2))
[a, b] = H.gens()
x = kH(a) + kH(b) + kH.one(); print(x)
x*x

to fail. It does not recognize in the coercion that the parents of the indexing elements should be the same.

CC: @tscrim @trevorkarn

Component: algebra

Keywords: group-algebra coercion gsoc2022

Author: Trevor K. Karn

Branch/Commit: e6f16a7

Reviewer: Travis Scrimshaw

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

[trevorkarn]

Branch: u/tkarn/group-algebra-34292

[trevorkarn]

Commit: 2f04cff

[trevorkarn]

Author: Trevor K. Karn

[trevorkarn]

New commits:

2f04cff

Fix trac 34292

[tscrim]

comment:2

I am pretty certain this is not the correct fix. The underlying issue comes from the fact that PermutationGroup is a CachedRepresentation, but not a UniqueRepresentation (nor should it be because equality is as as isomorphic groups). In particular, it comes from this:

sage: kH.group() == H
True
sage: kH.group() is H
False
sage: kH(a).leading_support().parent() is H
True
sage: kH(a).leading_support().parent() is kH.group()
False

IMO, it is luck that this makes the code work. The issue is that the coercion H -> G -> kG, where G = kG.group() and H is any group with a coercion into G, does not actually convert the basis index to an element of G like it should. Instead, I think we should change the GroupAlgebra._coerce_map_from_ to something like

         G = self.basis().keys()
         K = self.base_ring()
 
+        G_coercion = G.coerce_map_from(S)
-        if G.has_coerce_map_from(S):
+        if G_coercion is not None:
             from sage.categories.groups import Groups
             # No coercion for additive groups because of ambiguity of +
             #   being the group action or addition of a new term.
-            return self.category().is_subcategory(Groups().Algebras(K))
+            if not self.category().is_subcategory(Groups().Algebras(K)):
+                return None
+            if S is G:
+                return True
+            return self.coerce_map_from(G) * G_coercion
 
         if S in Sets.Algebras:
             S_K = S.base_ring()
             S_G = S.basis().keys()
             hom_K = K.coerce_map_from(S_K)
             hom_G = G.coerce_map_from(S_G)
             if hom_K is not None and hom_G is not None:
                 return SetMorphism(S.Hom(self, category=self.category() | S.category()),
                                    lambda x: self.sum_of_terms( (hom_G(g), hom_K(c)) for g,c in x ))

Unfortunately, this does not solve the problem. There is an even deeper issue:

sage: kH.group()(a)
(5,6,7)(12,14,18)
sage: _.parent() is kH.group()
False
sage: kH.group()._element_constructor_(a).parent() is kH.group()
True

So we see it is getting short-circuited by the coercion system because of equal-but-not-identical-parents. Indeed, this is matched by the coercion map:

sage: phi = kH.group().coerce_map_from(H)
sage: phi(a)
(5,6,7)(12,14,18)
sage: phi(a).parent() is H
True
sage: phi(a).parent() is kH.group()  # Should be True
False
sage: phi._call_(a).parent() is H  # Should be False
True
sage: phi.codomain()._element_constructor_(a).parent() is H  # Should be False
True
sage: phi.codomain() is H
False
sage: phi.codomain() is kH.group()
True

We see a very subtle distinction:

sage: kH.group()._element_constructor_(a).parent() is kH.group()
True
sage: kH.group()._element_constructor(a).parent() is kH.group()
False

This lead me through the UniqueRepresentation framework, but that was a dead-end. Next, I went to H.basis(), which the lazy family has one seemingly innocuous line, but it shows the issue:

sage: Hp = copy(H)
sage: Hp._element_constructor(a).parent() is Hp
False

The default implementation uses __reduce__, which stores the __dict__, which contains the _element_constructor attribute, which points to the original group H. This is the bug!

My proposal to fix this is have copy(H) is H (and deepcopy) since the permutation group is immutable. Adding

    def __copy__(self):
        return self

    __deepcopy__ = __copy__

to sage.groups.perm_gps.permgroup.PermutationGroup_generic fixed the issue in the ticket description for me (without the above change to the coerce map, but I still think we should do that as it would be a general improvement).

[trevorkarn]

comment:4

After making the change to GroupAlgebra_class._coerce_map_from as you suggested, I get the following doctest failure in group_algebras.py:

File "src/sage/algebras/group_algebra.py", line 158, in sage.algebras.group_algebra.GroupAlgebra_class._coerce_map_from_
Failed example:
    ZG.coerce_map_from(H)
Expected:
    Coercion map:
      From: Cyclic group of order 3 as a permutation group
      To:   Algebra of Dihedral group of order 6 as a permutation group over Integer Ring
Got:
    Composite map:
      From: Cyclic group of order 3 as a permutation group
      To:   Algebra of Dihedral group of order 6 as a permutation group over Integer Ring
      Defn:   Coercion map:
              From: Cyclic group of order 3 as a permutation group
              To:   Dihedral group of order 6 as a permutation group
            then
              Coercion map:
              From: Dihedral group of order 6 as a permutation group
              To:   Algebra of Dihedral group of order 6 as a permutation group over Integer Ring

I think this makes sense given the change you propose and seems mathematically correct, so I am inclined to change the doctest to the Got:, but want to confirm that this is right.

[tscrim]

comment:5

That is correct. While it seems like it adds an extra layer of indirection, it avoids a second call to the coercion system.

[sagetrac-git]

Changed commit from 2f04cff to 383d273

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

4417ed2	Fix trac 34292
e19ec8e	Revert changes
383d273	Change copy and fix _coerce_map_from

[trevorkarn]

comment:8

Awesome, thanks!

Replying to @tscrim:

That is correct. While it seems like it adds an extra layer of indirection, it avoids a second call to the coercion system.

[tscrim]

comment:9

Can you also quickly remove the added blankline to coerce.pyx?

Once the patchbot comes back green, positive review.

[tscrim]

Reviewer: Travis Scrimshaw

[sagetrac-git]

Changed commit from 383d273 to e6f16a7

[sagetrac-git]

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

e6f16a7

Remove blankline

[trevorkarn]

Changed keywords from group-algebra coercion to group-algebra coercion gsoc2022

[tscrim]

comment:12

Thanks. Now to wait for the bot.

[trevorkarn]

comment:13

The bot seems to not like this branch. In the log I see

sage -t --long --random-seed=41802771627995745478796096008933185838 src/sage/combinat/root_system/root_lattice_realizations.py  # Timed out
sage -t --long --random-seed=41802771627995745478796096008933185838 src/sage/geometry/polyhedron/base6.py  # Timed out
sage -t --long --random-seed=41802771627995745478796096008933185838 src/sage/plot/animate.py  # Timed out
sage -t --long --random-seed=41802771627995745478796096008933185838 src/sage/plot/plot3d/base.pyx  # Timed out
sage -t --long --random-seed=41802771627995745478796096008933185838 src/sage/plot/plot3d/list_plot3d.py  # Timed out
sage -t --long --random-seed=41802771627995745478796096008933185838 src/sage/plot/plot3d/implicit_plot3d.py  # Timed out
sage -t --long --random-seed=41802771627995745478796096008933185838 src/sage/plot/plot3d/parametric_plot3d.py  # Timed out
sage -t --long --random-seed=41802771627995745478796096008933185838 src/sage/plot/plot3d/platonic.py  # Timed out
sage -t --long --random-seed=41802771627995745478796096008933185838 src/sage/plot/plot3d/plot3d.py  # Timed out
sage -t --long --random-seed=41802771627995745478796096008933185838 src/sage/plot/plot3d/shapes.pyx  # Timed out
sage -t --long --random-seed=41802771627995745478796096008933185838 src/sage/plot/plot3d/shapes2.py  # Timed out
sage -t --long --random-seed=41802771627995745478796096008933185838 src/sage/combinat/root_system/plot.py  # Timed out

Are these the tests that fail? When I ctrl-f "fail" I only get the lines:

/Users/jpalmier/Desktop/Sage/git/patchbot/sage-9.7.beta5/sage -tp 10  --all --long
too many failed tests, not using stored timings
Running doctests with ID 2022-08-12-11-13-54-8c783f1e.
Git branch: patchbot/ticket_merged

and

Traceback (most recent call last):
  File "/Users/jpalmier/Library/Python/3.9/lib/python/site-packages/sage_patchbot/patchbot.py", line 1155, in test_a_ticket
    raise exc
  File "/Users/jpalmier/Library/Python/3.9/lib/python/site-packages/sage_patchbot/patchbot.py", line 1152, in test_a_ticket
    do_or_die(test_cmd, exn_class=TestsFailed)
  File "/Users/jpalmier/Library/Python/3.9/lib/python/site-packages/sage_patchbot/util.py", line 203, in do_or_die
    raise exn_class("{} {}".format(res, cmd))
sage_patchbot.util.TestsFailed: 1024 /Users/jpalmier/Desktop/Sage/git/patchbot/sage-9.7.beta5/sage -tp 10  --all --long

which don't seem to tell me about which tests failed.

[trevorkarn]

comment:14

Doctesting 1 file.
sage -t --random-seed=143715605125059368434100954485457792264 src/sage/combinat/root_system/plot.py
    [249 tests, 62.99 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 63.2 seconds
    cpu time: 14.0 seconds
    cumulative wall time: 63.0 seconds
Features detected for doctesting: 
pytest is not installed in the venv, skip checking tests that rely on it

sage -t --random-seed=247281136949444531994464403334771066369 src/sage/combinat/root_system/root_lattice_realizations.py
    [635 tests, 81.60 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 81.9 seconds
    cpu time: 10.2 seconds
    cumulative wall time: 81.6 seconds

[tscrim]

comment:15

The bot is morally green. Those timed out tests show up on many different tickets. Something needs to be tweaked on that patchbot.

[vbraun]

Changed branch from u/tkarn/group-algebra-34292 to e6f16a7