multiplication_table does not work for certain types of groups

[guenterrote]

apparently not for finitely presented groups, although they have such a method, and the documentation says that all that is required is a multiplication operation: (Might be related to an ancient ticket. #7555 about so-called "Cayley tables")

GU.<s,t> = FreeGroup()
gr0 = tetrahedral_group = GU / (s^(-2)*t*s*t, t^(-2)*s*t*s, s*t*s*t)
print(gr0.order())
gr0.multiplication_table()


Error in lines 1-1
Traceback (most recent call last):
  File "/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/matrix/operation_table.py", line 447, in __init__
    r = get_row(result)
KeyError: t^2
...

[guenterrote]

I have updated the documentation.

(Sorry that I did not run the automatic doctests myself. I could not install the development version due to some bug.)

---

New commits:

​15247bc

warning about finitely generated groups

[git]

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

​23a07b9	doctests passed. (generating the html doc files still fails!)
​10b0dbe	now the documentation is also fine!
​7aa8697	final polishing

[guenterrote]

This proposed "fix" is just an update to the documentation. I think it is important to warn users that finitely generated groups might not work as expected in some cases.

(I could not get the doctest with the failed multiplication table to run. Apparently two nested exceptions are beyond doctest's capabilities.)

[tscrim]

I think it would be better to have a more comprehensive solution. In particular, I think the multiplication_table() method should belong to the category of finite magmas. Another thing to consider is a specific implementation for finitely presented groups as it would need to construct the confluent rewriting system and do the reductions upon every multiplication (preferably on the GAP side).

Also, you should fill in your (real) name as the author.

[guenterrote]

Replying to tscrim:

I think it would be better to have a more comprehensive solution. In particular, I think the multiplication_table() method should belong to the category of finite magmas. Another thing to consider is a specific implementation for finitely presented groups as it would need to construct the confluent rewriting system and do the reductions upon every multiplication (preferably on the GAP side).

As far as I see the multiplication_table() method DOES belong to the category of magmas.

On the other hand, the issue with putting group elements into sets is a trap into which unsuspecting users may easily fall, and thus I find it appropriate to issue a warning, regardless of how the multiplication_table issue is eventually resolved. (However, from what I saw from glancing through the sage documentation, "wrong" hashcodes seems to be a fundamental issue of sage. But I did not see anywhere a warning that sets would not work as expected.)

Also, you should fill in your (real) name as the author.

I am not sure I understand. Where should I write my real name? Does a small clarification of the documentation qualify me to add my name to the author list of the package.

[tscrim]

Replying to guenterrote:

Replying to tscrim:

I think it would be better to have a more comprehensive solution. In particular, I think the multiplication_table() method should belong to the category of finite magmas. Another thing to consider is a specific implementation for finitely presented groups as it would need to construct the confluent rewriting system and do the reductions upon every multiplication (preferably on the GAP side).

As far as I see the multiplication_table() method DOES belong to the category of magmas.

I disagree because it only makes computational sense for finite magmas. For general magmas, we have no idea if there is a solution to the word problem. Of course, mathematically, this would be defined, but in order to actual make any computation, you need a solution to the word problem.

On the other hand, the issue with putting group elements into sets is a trap into which unsuspecting users may easily fall, and thus I find it appropriate to issue a warning, regardless of how the multiplication_table issue is eventually resolved. (However, from what I saw from glancing through the sage documentation, "wrong" hashcodes seems to be a fundamental issue of sage. But I did not see anywhere a warning that sets would not work as expected.)

I don't understand. I am not sure if you are making a mathematical or implementation argument. The mathematical one doesn't make sense to me because it is a table, which means we have put some ordering on the magma's elements. For the implementation, again, we want an ordering, so it would be a list and doesn't use hashing.

Also, you should fill in your (real) name as the author.

I am not sure I understand. Where should I write my real name? Does a small clarification of the documentation qualify me to add my name to the author list of the package.

No, here on the ticket.

[git]

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

​bde9ea3

put warnings up front in the documentation, slight changes

[guenterrote]

Replying to tscrim:

Replying to guenterrote:

On the other hand, the issue with putting group elements into sets is a trap into which unsuspecting users may easily fall, and thus I find it appropriate to issue a warning, regardless of how the multiplication_table issue is eventually resolved. (However, from what I saw from glancing through the sage documentation, "wrong" hashcodes seems to be a fundamental issue of sage. But I did not see anywhere a warning that sets would not work as expected.)

I don't understand. I am not sure if you are making a mathematical or implementation argument. The mathematical one doesn't make sense to me because it is a table, which means we have put some ordering on the magma's elements. For the implementation, again, we want an ordering, so it would be a list and doesn't use hashing.

I had updated the documentation to be in line with the current state of the software. You apparently did not notice that, on that occasion, I also adressed an issue with use of finitely generated group elements as set elements and dictionary keys:

The following example shows that two different representations of the
same element can result in two distinct elements of a "set"::

    sage: F.<r,s,t> = FreeGroup()
    sage: G = F / (r^2, s^3, t^3, r*s*t) # the tetrahedral group
    sage: G.order()
    12
    sage: a,b = G(r*s),G(~t) # ~t is an alternative notation for t^-1
    sage: set_of_2 = {a,b}
    sage: print(set_of_2, len(set_of_2)) # two-element set
    {r*s, t^-1} 2
    sage: a==b # a and b are the same element!
    True

I also added the workaround via permutation groups.

Should I open a different ticket for updating the documention? I am afraid fixing the multiplication_table as part of a comprehensive solution will require some fundamental design decisions and will not be done soon.

[tscrim]

Replying to guenterrote:

Replying to tscrim:

Replying to guenterrote:

On the other hand, the issue with putting group elements into sets is a trap into which unsuspecting users may easily fall, and thus I find it appropriate to issue a warning, regardless of how the multiplication_table issue is eventually resolved. (However, from what I saw from glancing through the sage documentation, "wrong" hashcodes seems to be a fundamental issue of sage. But I did not see anywhere a warning that sets would not work as expected.)

I don't understand. I am not sure if you are making a mathematical or implementation argument. The mathematical one doesn't make sense to me because it is a table, which means we have put some ordering on the magma's elements. For the implementation, again, we want an ordering, so it would be a list and doesn't use hashing.

I had updated the documentation to be in line with the current state of the software. You apparently did not notice that, on that occasion, I also adressed an issue with use of finitely generated group elements as set elements and dictionary keys:

No, I saw it. You're asking for a solution to a provably unsolvable problem. We know we cannot be perfect with hashes because of that since there is no canonical normal form for elements in a general finitely presented group.

Please actually respond to what I am saying because the issue here has nothing to do with hashing or constructing a set/dict. Again, a table is a list of elements.

I also added the workaround via permutation groups.

Should I open a different ticket for updating the documention? I am afraid fixing the multiplication_table as part of a comprehensive solution will require some fundamental design decisions and will not be done soon.

Documenting a separate issue (which does deserve to be documented) does not solve the problem of this ticket. So that should be a separate ticket. Fixing the multiplication table for a finitely presented group is not hard if you use list(G) and == checking. Basically you just need to have get_row = self._elts.index in sage.matrix.operation_table.OperationTable.__init__ for FPGs.

[guenterrote]

You're asking for a solution to a provably unsolvable problem.

OK, but this is not specific to the multiplication table. Nearly ALL methods for finitely generated groups are not guaranteed to finish. There is already a warning about this in the documentation. But sometimes they DO finish. (e.g. the order() method in my example). I think if sage (or GAP) is able to figure out the order or the group and the order is reasonably small, it is not unreasonable to expect that it should be possible to construct a multiplication table.

I am unsure whether the error in multiplication_table has "nothing to do with hashing or constructing a set/dict." The KeyError seems to indicate that a dict might be involved. Using == might slow down things, but probably acceptable for those cases where one would want a multiplication table.

I guess this type of conversion and == checking is already done anyway when converting to a permutation group, so it would be the easiest solution to piggyback on the multiplication table for permutation groups.

Anyway, I have opened a new ticket, #31311. (have to figure out how to associate the git branch with a new ticket)

Are there any issues to which I should still respond?

[tscrim]

Replying to guenterrote:

I am unsure whether the error in multiplication_table has "nothing to do with hashing or constructing a set/dict." The KeyError seems to indicate that a dict might be involved. Using == might slow down things, but probably acceptable for those cases where one would want a multiplication table.

This is an implementation detail for optimization that is coming back to bite us in this special case. Here is a proposal for fixing the multiplication table to use the list as a fallback.

I guess this type of conversion and == checking is already done anyway when converting to a permutation group, so it would be the easiest solution to piggyback on the multiplication table for permutation groups.

There would be a disassociation of the FPG with the multiplication table as it wouldn't be able to hold on to that information in a natural way.

Anyway, I have opened a new ticket, #31311. (have to figure out how to associate the git branch with a new ticket)

You just need to put the branch name in the ticket's branch field (if you aren't using the git trac commands).

---

New commits:

​6593805

Use the list of elements index() as a fallback in operation_table.py.

[guenterrote]

For large groups, this is quite slow when compared to the detour via perm-groups.

sage: F4.<r,s,t,z> = FreeGroup() 
sage: G120 = F4 / (r^2*z, s^3*z, t^5*z, r*s*t*z) # the binary icosahedral group                                                                                                                  
sage: time G120p = G120.as_permutation_group()                                                                                                                                                         
CPU times: user 5.94 ms, sys: 74 µs, total: 6.01 ms
Wall time: 5.8 ms
sage: time m2 = G120p.multiplication_table()                                                                                                                                                           
CPU times: user 32.6 ms, sys: 3.87 ms, total: 36.4 ms
Wall time: 35.2 ms
sage: time m1 = G120.multiplication_table()                                                                                                                                                            
CPU times: user 32.5 s, sys: 4.13 ms, total: 32.5 s
Wall time: 32.5 s
sage: G120.order()                                                                                                                                                                                     
120
sage: [G120(x) for x in m2.row_keys()][:10]                                                                                                                                                            
[1, r, r^-1, s, s^-1, t, t^-1, z^-1, r*s, r*s^-1]

But I am not sure whether anyone might ever want to look at such large multiplication tables. So I guess it is tolerable.

[tscrim]

Replying to guenterrote:

For large groups, this is quite slow when compared to the detour via perm-groups.

We loose the association with the elements of the FPG by going to another group. This defeats the purpose of the code. If someone wants to use a perm group, then they can (and should IMO) just convert it themselves.

But I am not sure whether anyone might ever want to look at such large multiplication tables. So I guess it is tolerable.

Then does that constitute a review? The patchbot is green. If so, then you can put your name as the reviewer and set it to a positive review.

[tscrim]

Thank you!