#31203 closed defect (fixed)

multiplication_table does not work for certain types of groups

Reported by: guenterrote Owned by:
Priority: minor Milestone: sage-9.3
Component: group theory Keywords: groups, multiplication table
Cc: Merged in:
Authors: Travis Scrimshaw Reviewers: Günter Rote
Report Upstream: N/A Work issues:
Branch: 6593805 (Commits, GitHub, GitLab) Commit: 65938052495bc436be6fe53691fd207917142a0b
Dependencies: Stopgaps:

Status badges

Description (last modified by 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
...

Change History (20)

comment:1 Changed 18 months ago by guenterrote

  • Component changed from PLEASE CHANGE to group theory
  • Description modified (diff)
  • Keywords multiplication table added

comment:2 Changed 18 months ago by guenterrote

  • Branch set to u/guenterrote/multiplication_table_does_not_work_for_certain_types_of_groups_

comment:3 Changed 18 months ago by guenterrote

  • Commit set to 15247bce27986709088ccc76ff76d47ac01c684f
  • Status changed from new to needs_review

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:

15247bcwarning about finitely generated groups

comment:4 follow-up: Changed 18 months ago by git

  • Commit changed from 15247bce27986709088ccc76ff76d47ac01c684f to 7aa86978206307b19342ad45b534ea1fd32b42d9

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

23a07b9doctests passed. (generating the html doc files still fails!)
10b0dbenow the documentation is also fine!
7aa8697final polishing

comment:5 in reply to: ↑ 4 Changed 18 months ago by 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.)

comment:6 follow-up: Changed 18 months ago by tscrim

  • Status changed from needs_review to needs_work

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.

comment:7 in reply to: ↑ 6 ; follow-up: Changed 18 months ago by 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.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 18 months ago by 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.

comment:9 Changed 18 months ago by guenterrote

  • Authors set to Günter Rote

comment:10 Changed 17 months ago by git

  • Commit changed from 7aa86978206307b19342ad45b534ea1fd32b42d9 to bde9ea3cfff6c1b2d642b129f0e79630ba1bf29d

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

bde9ea3put warnings up front in the documentation, slight changes

comment:11 in reply to: ↑ 8 ; follow-up: Changed 17 months ago by 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.

comment:12 in reply to: ↑ 11 Changed 17 months ago by 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.

comment:13 follow-up: Changed 17 months ago by 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?

Last edited 17 months ago by guenterrote (previous) (diff)

comment:14 in reply to: ↑ 13 Changed 17 months ago by tscrim

  • Authors changed from Günter Rote to Travis Scrimshaw
  • Branch changed from u/guenterrote/multiplication_table_does_not_work_for_certain_types_of_groups_ to public/groups/mult_table_fpg-31203
  • Commit changed from bde9ea3cfff6c1b2d642b129f0e79630ba1bf29d to 65938052495bc436be6fe53691fd207917142a0b
  • Status changed from needs_work to needs_review

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:

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

comment:15 follow-up: Changed 17 months ago by 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.

Last edited 17 months ago by guenterrote (previous) (diff)

comment:16 in reply to: ↑ 15 Changed 17 months ago by 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.

comment:17 Changed 17 months ago by gh-guenterrote

  • Status changed from needs_review to positive_review

comment:18 Changed 17 months ago by mkoeppe

  • Reviewers set to Günter Rote
  • Summary changed from multiplication_table does not work for certain types of groups. to multiplication_table does not work for certain types of groups

comment:19 Changed 17 months ago by tscrim

Thank you!

comment:20 Changed 16 months ago by vbraun

  • Branch changed from public/groups/mult_table_fpg-31203 to 65938052495bc436be6fe53691fd207917142a0b
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.