Opened 18 months ago
Closed 16 months ago
#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: |
Description (last modified by )
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
- Component changed from PLEASE CHANGE to group theory
- Description modified (diff)
- Keywords multiplication table added
comment:2 Changed 18 months ago by
- Branch set to u/guenterrote/multiplication_table_does_not_work_for_certain_types_of_groups_
comment:3 Changed 18 months ago by
- Commit set to 15247bce27986709088ccc76ff76d47ac01c684f
- Status changed from new to needs_review
comment:4 follow-up: ↓ 5 Changed 18 months ago by
- Commit changed from 15247bce27986709088ccc76ff76d47ac01c684f to 7aa86978206307b19342ad45b534ea1fd32b42d9
comment:5 in reply to: ↑ 4 Changed 18 months ago by
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: ↓ 7 Changed 18 months ago by
- 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: ↓ 8 Changed 18 months ago by
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: ↓ 11 Changed 18 months ago by
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
comment:10 Changed 17 months ago by
- Commit changed from 7aa86978206307b19342ad45b534ea1fd32b42d9 to bde9ea3cfff6c1b2d642b129f0e79630ba1bf29d
Branch pushed to git repo; I updated commit sha1. New commits:
bde9ea3 | put warnings up front in the documentation, slight changes
|
comment:11 in reply to: ↑ 8 ; follow-up: ↓ 12 Changed 17 months ago by
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
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: ↓ 14 Changed 17 months ago by
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?
comment:14 in reply to: ↑ 13 Changed 17 months ago by
- 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:
6593805 | Use the list of elements index() as a fallback in operation_table.py.
|
comment:15 follow-up: ↓ 16 Changed 17 months ago by
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.
comment:16 in reply to: ↑ 15 Changed 17 months ago by
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
- Status changed from needs_review to positive_review
comment:18 Changed 17 months ago by
- 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
Thank you!
comment:20 Changed 16 months ago by
- Branch changed from public/groups/mult_table_fpg-31203 to 65938052495bc436be6fe53691fd207917142a0b
- Resolution set to fixed
- Status changed from positive_review to closed
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:
warning about finitely generated groups