Update doc for finitely generated groups: Warn about not normalizing

[50e11902-eb93-4bd9-9430-4325b5a3ab56]

Elements of finitely generated groups may surprise an unsuspecting user. Add a warning and workaround the documentation.

related ticket

31203

CC: @miguelmarco @darijgr

Component: documentation

Author: Günter Rote

Branch/Commit: public/groups/fpg_doc-31311 @ c40e4c8

Reviewer: Travis Scrimshaw

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

[50e11902-eb93-4bd9-9430-4325b5a3ab56]

Branch: u/guenterrote/multiplication_table_does_not_work_for_certain_types_ofgroups

[50e11902-eb93-4bd9-9430-4325b5a3ab56]

Commit: bde9ea3

[50e11902-eb93-4bd9-9430-4325b5a3ab56]

New commits:

15247bc	warning about finitely generated groups
23a07b9	doctests passed. (generating the html doc files still fails!)
10b0dbe	now the documentation is also fine!
7aa8697	final polishing
bde9ea3	put warnings up front in the documentation, slight changes

[tscrim]

comment:3

This warning:

.. WARNING::

    Sage does not completely "normalize" elements
    of finitely generated groups.
    Thus, trying to put group elements into a set or to use them
    as keys for a dictionary may lead to trouble.

is in contradiction to the warning just before it. If you could normalize the elements, you would have a solution to the word problem. However, the comment suggests that it is possible to do such a normalization.

I would recommend tightening up your explanation of the hash and == being inconsistent. In particular, I would just give two elements that are equal and then their hashes being unequal. The "2" element set example is also good. Your conclusion, as stated on #31203, that the multiplication table fails because of this is incorrect.

I don't necessarily agree with an explicit recommendation to convert to a permutation group as that only applies when the group is finite. If something is to be written, which I am not sure I think it should be, then I would instead state that instead of a set or dict, one needs to use a list.

[tscrim]

Reviewer: Travis Scrimshaw

[50e11902-eb93-4bd9-9430-4325b5a3ab56]

comment:4

Replying to @tscrim:

This warning:

.. WARNING::

    Sage does not completely "normalize" elements
    of finitely generated groups.
    Thus, trying to put group elements into a set or to use them
    as keys for a dictionary may lead to trouble.

is in contradiction to the warning just before it.

How about this:

.. WARNING::

    Even if Sage can recognize that the group is finite, it does not
    completely "normalize" elements
    of finitely generated groups.
    Thus, trying to put such group elements into a set or to use them
    as keys for a dictionary may lead to trouble.

Your conclusion, as stated on #31203, that the multiplication table fails because of this is incorrect.

The multiplication table seems to be fixed, so that remark is obsolete.

I don't necessarily agree with an explicit recommendation to convert to a permutation group as that only applies when the group is finite. If something is to be written, which I am not sure I think it should be, then I would instead state that instead of a set or dict, one needs to use a list.

But a list is not a replacement for a set or dict, if a set or dict is what I need. Yes indeed, the recommendation should be conditional on finiteness.

Maybe it should even be explicitly highlighted that elements of the permutation group can be converted back to the free group? This is very useful. Is it already written somewhere?

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from bde9ea3 to f991236

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

f991236

restructured the new doc, eliminated reference to multiplication_table

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

46d8222

clean up obsolete comments

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f991236 to 46d8222

[tscrim]

comment:8

Sorry for taking a while to get to this. I think we are getting close.

Replying to @guenterrote:

Replying to @tscrim:

This warning:

.. WARNING::

    Sage does not completely "normalize" elements
    of finitely generated groups.
    Thus, trying to put group elements into a set or to use them
    as keys for a dictionary may lead to trouble.

is in contradiction to the warning just before it.

How about this:

.. WARNING::

    Even if Sage can recognize that the group is finite, it does not
    completely "normalize" elements
    of finitely generated groups.
    Thus, trying to put such group elements into a set or to use them
    as keys for a dictionary may lead to trouble.

This is better, but I don't really care for it too much. I guess with a confluent rewriting system, you can definite a normalization of an element. However, the finiteness of the group is not the deciding factor, it is that Sage can sometimes recognize when two elements are equal, even in an infinite group:

sage: F.<a,b,c> = FreeGroup() 
sage: G = F / [a^2,b^2,c^2,a*b*c*a*b*c] 
sage: G(a*b*c*a*b*c) == G.one()                                                                                   
True

So I would rather see something like

.. WARNING::

    Sage can sometimes recognize when two words represent the same
    element in a finitely presented group. However, there is typically
    no way to canonically represent the elements. Thus, the hash
    functions of two elements ``a`` and ``b`` may not be equal even
    though ``a == b``. Therefore, there could be issues with the
    elements being used in a `set` or keys of a `dict`.

I don't necessarily agree with an explicit recommendation to convert to a permutation group as that only applies when the group is finite. If something is to be written, which I am not sure I think it should be, then I would instead state that instead of a set or dict, one needs to use a list.

But a list is not a replacement for a set or dict, if a set or dict is what I need. Yes indeed, the recommendation should be conditional on finiteness.

They can be used to replace them, but you do loose (a lot of) speed. Now that it explicitly says finite groups to use permutation groups, I am happier with it. Since you want to include this (again, I don't think this is necessary), you should also include something to cover infinite groups and state that they can still be used in lists.

Maybe it should even be explicitly highlighted that elements of the permutation group can be converted back to the free group? This is very useful. Is it already written somewhere?

That would be something for the permutation group or free group code, not the FPG code.

I think this is an obvious mathematical fact:

+Beware that this conversion to the free group ``F`` is
+not a one-to-one operation::

So I don't see the point in including those tests. (It is possible that the FPG is a free group too.)

Also, please undo this change:

-"""
-Finitely Presented Groups
+"""Finitely Presented Groups

Sage's convention is to start on the next line after a """.

A typo here regognizes -> recognizes.

[50e11902-eb93-4bd9-9430-4325b5a3ab56]

comment:9

Replying to @tscrim:

I think this is an obvious mathematical fact:

+Beware that this conversion to the free group ``F`` is
+not a one-to-one operation::

So I don't see the point in including those tests. (It is possible that the FPG is a free group too.)

But the previous example, which was there before, performs such a conversion (I only changed the group because otherwise the test ==G.one() took too long):

sage: F(rst_G) == r*s/t
True

So what IS the conversion to F? What is this example trying to show? Is the result True merely a coincidence?

Or are elements of finitely generated groups internally represented as elements of the corresponding free groups? And F(..) merely brings out this representation.

[50e11902-eb93-4bd9-9430-4325b5a3ab56]

comment:10

sage: F.<r,s,t> = FreeGroup()
sage: G = F / (r^2, s^3, t^3, r*s*t) # the tetrahedral group
sage: rr = G([1,1])                                                             
sage: rr == r*r                                                                 
False
sage: {rr , r*r}                                                                
{r^2, r^2}
sage: hash(rr)                                                                  
8389048192121911274
sage: hash(r*r)                                                                 
8389048192121911274

Now I am totally confused. same hash values but distinct!

[tscrim]

comment:11

Replying to @guenterrote:

sage: F.<r,s,t> = FreeGroup()
sage: G = F / (r^2, s^3, t^3, r*s*t) # the tetrahedral group
sage: rr = G([1,1])                                                             
sage: rr == r*r                                                                 
False
sage: {rr , r*r}                                                                
{r^2, r^2}
sage: hash(rr)                                                                  
8389048192121911274
sage: hash(r*r)                                                                 
8389048192121911274

Now I am totally confused. same hash values but distinct!

There is no coercion from F -> G, so the equality cannot be computed:

sage: rr * r
...
TypeError: unsupported operand parent(s) for *: 'Finitely presented group < r, s, t | r^2, s^3, t^3, r*s*t >' and 'Free Group on generators {r, s, t}'

I think there should be a coercion from the free group down to the quotient, but that is a separate issue.

[tscrim]

comment:12

Replying to @guenterrote:

Replying to @tscrim:

I think this is an obvious mathematical fact:

+Beware that this conversion to the free group ``F`` is
+not a one-to-one operation::

So I don't see the point in including those tests. (It is possible that the FPG is a free group too.)

But the previous example, which was there before, performs such a conversion (I only changed the group because otherwise the test ==G.one() took too long):

sage: F(rst_G) == r*s/t
True

So what IS the conversion to F? What is this example trying to show? Is the result True merely a coincidence?

The conversion to F is just treat it like an element in the free group with that word. This example is showing that is what actually happens, that we can make the round trip (as conversions), and that the elements are treated as completely different objects. This is different than showing the conversion is not injective.

Or are elements of finitely generated groups internally represented as elements of the corresponding free groups? And F(..) merely brings out this representation.

Kind of. I would say F(...) changes the meaning of that representation; that the word is not in the FPG but the ambient free group.

[50e11902-eb93-4bd9-9430-4325b5a3ab56]

comment:13

Replying to @guenterrote:

sage: F.<r,s,t> = FreeGroup()
sage: G = F / (r^2, s^3, t^3, r*s*t) # the tetrahedral group
sage: rr = G([1,1])                                                             
sage: rr == r*r                                                                 
False
sage: {rr , r*r}                                                                
{r^2, r^2}
sage: hash(rr)                                                                  
8389048192121911274
sage: hash(r*r)                                                                 
8389048192121911274

Now I am totally confused. same hash values but distinct!

Ah. Same hash is only a necessary condition for being regarded as equal in a set. Of course, a == test is always performed when there is a hash collision.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

25de52d

new internal info about representation

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 46d8222 to 25de52d

[50e11902-eb93-4bd9-9430-4325b5a3ab56]

comment:15

Replying to @tscrim:

But a list is not a replacement for a set or dict, if a set or dict is what I need.

They can be used to replace them, but you do loose (a lot of) speed.

And I have to program "by hand" things that are automatic for sets and dicts.

Now that it explicitly says finite groups to use permutation groups, I am happier with it. Since you want to include this (again, I don't think this is necessary), you should also include something to cover infinite groups and state that they can still be used in lists.

Anything can be put in a list. So I would not dwell on that.

[50e11902-eb93-4bd9-9430-4325b5a3ab56]

comment:16

Replying to @guenterrote:

Replying to @tscrim:

But a list is not a replacement for a set or dict, if a set or dict is what I need.

They can be used to replace them, but you do loose (a lot of) speed.

And I have to program "by hand" things that are automatic for sets and dicts.

maybe there should be a SlowSet and SlowDict that is based on == tests. (But that would be another ticket.)

[tscrim]

comment:17

Replying to @guenterrote:

Replying to @tscrim:

But a list is not a replacement for a set or dict, if a set or dict is what I need.

They can be used to replace them, but you do loose (a lot of) speed.

And I have to program "by hand" things that are automatic for sets and dicts.

Most of these are all fairly simple things to implement IMO (and some are already there by default). While there is a code smell from this, there is a mathematical block that cannot be worked around. There is no such thing as a free lunch, but there are multiple kinds of workarounds depending on the use-case.

Now that it explicitly says finite groups to use permutation groups, I am happier with it. Since you want to include this (again, I don't think this is necessary), you should also include something to cover infinite groups and state that they can still be used in lists.

Anything can be put in a list. So I would not dwell on that.

You are missing the points about == and a list working as a container object. The point is you can hold a set of objects and check if another element already belongs to it.

I think it is bad practice to talk about the internal implementations in documentation unless it very explicitly is necessary. Here, that is not the case. Instead, it is a manifestation of the fact there is no canonical way to normalize elements. So it is good point out that they may look the same and we can convert back to the free group (which doesn't have to depend on the internal representation of the element), they are otherwise different objects.

[50e11902-eb93-4bd9-9430-4325b5a3ab56]

comment:18

I think it is bad practice to talk about the internal implementations in documentation unless it very explicitly is necessary. Here, that is not the case. Instead, it is a manifestation of the fact there is no canonical way to normalize elements. So it is good point out that they may look the same and we can convert back to the free group (which doesn't have to depend on the internal representation of the element), they are otherwise different objects.

I agree that talking about internals should be avoided, but I don't agree that the result does not depend on the internal representation.

The conversion from "G" to "F" (referring to the current example) exists in Sage. It is mentioned in one of the examples that are already in the documentation. It is indeed a triviality that it cannot be a uniquely defined operation in the mathematical sense, but then: What IS this conversion?

I think it should be specified what F(x) is when x is an element of G, more precisely than saying "convert from one parent to the other". Can this be done without talking about the representation?

I am inclined to reinsert the example of F(..) not being one-to-one. Sage does provide this conversion even though it is mathematically unsound (in the sense that the result depends on the internal representation), and the user should be warned.

(BTW, already the current doc talks about the representation: "Notice that, even if they are represented in the same way". In some earlier attempt at "improving" the documentation, I changed "represented" to "displayed", precisely for the reason to avoid talking about the internal representation.

[50e11902-eb93-4bd9-9430-4325b5a3ab56]

comment:19

Replying to @tscrim:

I think it is bad practice to talk about the internal implementations in documentation unless it very explicitly is necessary.

For that very reason, I don't want to mention hashes. They ought to be internal details about which the user doesn't have to worry. The user rather worries about sets not working as they should.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

6593805	Use the list of elements index() as a fallback in operation_table.py.
04cf511	Merge branch 'public/groups/mult_table_fpg-31203' of trac.sagemath.org:sage into t/31311/finitely_presented_groups
9577ac8	(Re)inserted warning about conversion not being a mathematical function.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 25de52d to 9577ac8

[tscrim]

comment:21

Replying to @guenterrote:

Replying to @tscrim:

I think it is bad practice to talk about the internal implementations in documentation unless it very explicitly is necessary.

For that very reason, I don't want to mention hashes. They ought to be internal details about which the user doesn't have to worry. The user rather worries about sets not working as they should.

Hashing is not an (internal) implementation detail but a feature and an important aspect of the code (as your example explicitly points out).

[tscrim]

comment:22

Replying to @guenterrote:

I think it is bad practice to talk about the internal implementations in documentation unless it very explicitly is necessary. Here, that is not the case. Instead, it is a manifestation of the fact there is no canonical way to normalize elements. So it is good point out that they may look the same and we can convert back to the free group (which doesn't have to depend on the internal representation of the element), they are otherwise different objects.

I agree that talking about internals should be avoided, but I don't agree that the result does not depend on the internal representation.

There is a difference between mathematical equality (==) and identity (Python is). So in <t|t^2>, the elements t^2 and 1 are distinct but equal. Also another subtle point is the difference between the internal representation and that instances of elements of a FPG are representatives of some element in the FPG. See also the next paragraph.

The conversion from "G" to "F" (referring to the current example) exists in Sage. It is mentioned in one of the examples that are already in the documentation. It is indeed a triviality that it cannot be a uniquely defined operation in the mathematical sense, but then: What IS this conversion?

Perhaps a more formal perspective will help sort this out. We have a set of all words G in an (finite) alphabet A representing the generators of a free group. A FPG is G along with an equivalence relation ==. Thus the conversion is the natural map from G -> F that simply forgets about the equivalence relation.

I think it should be specified what F(x) is when x is an element of G, more precisely than saying "convert from one parent to the other". Can this be done without talking about the representation?

Of course, we really want to think of G as the quotient, elements up to the equivalence relation. However, we cannot implement it in that way in general. We could rework the implementation for finite groups, but I might be slightly worried about efficiency.

I am inclined to reinsert the example of F(..) not being one-to-one. Sage does provide this conversion even though it is mathematically unsound (in the sense that the result depends on the internal representation), and the user should be warned.

It does not depend on the internal representation, but on the element, which is some word that represents some element in the FPG. Internally we could store the element as a list, a free group element, a Sequence, an integer, etc., but that doesn't change that it is a word representing some element in a FPG.

(BTW, already the current doc talks about the representation: "Notice that, even if they are represented in the same way". In some earlier attempt at "improving" the documentation, I changed "represented" to "displayed", precisely for the reason to avoid talking about the internal representation.

I think that actually gets a bit further from the model that is implemented.

[50e11902-eb93-4bd9-9430-4325b5a3ab56]

comment:23

Replying to @tscrim:

There is a difference between mathematical equality (==) and identity (Python is). So in <t|t^2>, the elements t^2 and 1 are distinct but equal.

This is yet another, completely different story:

sage: F = FreeGroup(1)                                                         
sage: F([1])==F([1])                                                            
True
sage: F([1]) is F([1])                                                          
False

The Python "is" comparison is an object-oriented programming-language thing, and nobody expects mathematically meaningful properties from it. That is why Python allows to redefine __equals__ (or ==).

[50e11902-eb93-4bd9-9430-4325b5a3ab56]

comment:24

Replying to @tscrim:

The conversion from "G" to "F" (referring to the current example) exists in Sage. It is mentioned in one of the examples that are already in the documentation. It is indeed a triviality that it cannot be a uniquely defined operation in the mathematical sense, but then: What IS this conversion?

Perhaps a more formal perspective will help sort this out. We have a set of all words G in an (finite) alphabet A representing the generators of a free group. A FPG is G along with an equivalence relation ==. Thus the conversion is the natural map from G -> F that simply forgets about the equivalence relation.

I think it should be specified what F(x) is when x is an element of G, more precisely than saying "convert from one parent to the other". Can this be done without talking about the representation?

Of course, we really want to think of G as the quotient, elements up to the equivalence relation. However, we cannot implement it in that way in general. We could rework the implementation for finite groups, but I might be slightly worried about efficiency.

1.) I am not at all proposing to change the implementation. I am proposing to bring the documentation in line with what Sage does.

2.) There are several levels of implementation details. a) An element may be represented as a word, and b) a word may be internally represented as a tuple or list or whatever.

The lower level is indeed irrelevant for the specification, but the first level is important, in this case.

3.) Maybe to some people it is obvious that the elements of an FPG are words over the generators (modulo the trivial reductions aⁱ*a^j=a^i+j and a⁰=1), and the relations are something extra. To other people, elements of the group are equivalence classes of words.

The == test brings out the second interpretation.

Such different interpretations might cause people to fall into a trap (like me or the original implementors of the multiplication_table function), and therefore I find it important to address this in the documentation.

I will try to find some formulations.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9577ac8 to fea79d7

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

5533f3d	extensive rewording of the intro. also eliminated a few
fea79d7	streamlined examples, renamed variables in examples

[50e11902-eb93-4bd9-9430-4325b5a3ab56]

comment:26

I took the occasion to eliminate a few references to self from the documentation

[mkoeppe]

comment:27

Moving to 9.4, as 9.3 has been released.

[tscrim]

Changed branch from u/guenterrote/multiplication_table_does_not_work_for_certain_types_ofgroups to public/groups/fpg_doc-31311

[tscrim]

comment:28

Sorry for not being able to work on this recently. Here is a version where I incorporated a number of your changes, but I reworded a few things to try to remove some ambiguities and deal with different perspectives. I also added some things I wanted to see included.

There is a non-documentation change: I added the coercion from the ambient free group as a way to help remove issues with accidentally not working in the FPG. I am not convinced this actually helps because it blurs the line more between the two groups. Yet, it is in line with polynomial rings:

sage: R.<x,y> = ZZ[]
sage: Q = R.quo([x^2+y^2])
sage: Q.has_coerce_map_from(R)
True

---

New commits:

c40e4c8

Clarifying the FPG documentation.

[tscrim]

Changed commit from fea79d7 to c40e4c8

[mkoeppe]

comment:29

Setting a new milestone for this ticket based on a cursory review.

[mkoeppe]

comment:30

Stalled in needs_review or needs_info; likely won't make it into Sage 9.5.

[mkoeppe]

Branch has merge conflicts