Matrix groups are not uniquely represented, why?

312 views
Skip to first unread message

Simon Brandhorst

unread,
May 25, 2018, 2:08:45 AM5/25/18
to sage-devel
sage: G = MatrixGroup([Matrix(GF(17),2,[1,1,1,0])])
Matrix group over Finite Field of size 17 with 1 generators (
[1 1]
[1 0]
)
sage
: H = MatrixGroup([Matrix(GF(17),2,[1,1,1,0])])
sage
: G is H
False


The reason is probably that there is no unique representation in gap.
Is this intended or to be considered a bug?

Simon Brandhorst

unread,
May 25, 2018, 2:40:56 AM5/25/18
to sage-devel
Update:

sage: S = SymmetricGroup(4)
sage
: S1 = S.subgroup(S.gens()[:1])
sage
: S2 = S.subgroup(S.gens()[:1])
sage
: S1 is S2
False

Since the same is true for subgroups of permutation groups, I wonder if this is intended?

The reason I am asking is that I implemented abelian groups and their automorphisms with gap

sage.groups.abelian_gps.abelian_group_gap sage.groups.abelian_gps.abelian_aut


using unique representations for subgroups. I did I miss something?

Travis Scrimshaw

unread,
May 25, 2018, 4:00:22 AM5/25/18
to sage-devel
I believe the matrix and permutation groups are quite old code, so UniqueRepresentation may not have been available at that time. The permutation group code does need updating; in particular, it is still an old-style parent:

sage: S.__class__.__mro__
(<class 'sage.groups.perm_gps.permgroup_named.SymmetricGroup_with_category'>,
 
<class 'sage.groups.perm_gps.permgroup_named.SymmetricGroup'>,
 
<class 'sage.groups.perm_gps.permgroup_named.PermutationGroup_symalt'>,
 
<class 'sage.groups.perm_gps.permgroup_named.PermutationGroup_unique'>,
 
<class 'sage.structure.unique_representation.CachedRepresentation'>,
 
<class 'sage.groups.perm_gps.permgroup.PermutationGroup_generic'>,
 
<type 'sage.groups.old.FiniteGroup'>,
 
<type 'sage.groups.old.Group'>,
 
<type 'sage.structure.parent_gens.ParentWithGens'>,
 
<type 'sage.structure.parent_base.ParentWithBase'>,
 
<type 'sage.structure.parent_old.Parent'>,
 
<type 'sage.structure.parent.Parent'>,
...

(Side note: We also should not be importing things like PermutationGroup_generic and PermutationGroupMorphism_id into the global namespace.)

I don't see a reason off-hand why these should not be UniqueRepresentation subclasses.

Best,
Travis

Nils Bruin

unread,
May 25, 2018, 12:55:38 PM5/25/18
to sage-devel
There is a very good reason why they should NOT'. Equality between subgroups is not uniquely determined by the construction parameters. It's part of the API of UniqueRepresentation that equality is identity on them.

Also, UniqueRepresentation objects make it much harder to write predictable code: because they're global objects they really MUST be immutable. No cheating! That's often quite inconvenient. Also, the processing of the construction parameters is possibly more expensive than the construction itself, so they may degrade performance. Furthermore, they have proven time and again to be very prone to memory leaks, to the point where I'd now work on the assumption that if you change an object to UniqueRepresentation, you're introducing memory leaks various places.


Simon King

unread,
May 25, 2018, 3:17:35 PM5/25/18
to sage-...@googlegroups.com
Hi!

On 2018-05-25, Nils Bruin <nbr...@sfu.ca> wrote:
>> I don't see a reason off-hand why these should not be UniqueRepresentation
>> subclasses.
>>
>
> There is a very good reason why they should NOT'. Equality between
> subgroups is not uniquely determined by the construction parameters. It's
> part of the API of UniqueRepresentation that equality is identity on them.

But they could still be CachedRepresentation. Then, if the same subgroup
is given by the same generators, it is identical, but if the same
subgroup is given by different generators, it is just equal but not
identical.

Best regards,
Simon

Nils Bruin

unread,
May 25, 2018, 3:53:15 PM5/25/18
to sage-devel


On Friday, May 25, 2018 at 12:17:35 PM UTC-7, Simon King wrote:
But they could still be CachedRepresentation. Then, if the same subgroup
is given by the same generators, it is identical, but if the same
subgroup is given by different generators, it is just equal but not
identical.

But before doing so, you would need to show that in common scenarios it produces a benefit. It has three significant draw-backs:
 - you'd slow down the creation of matrix groups in general, because you're requiring the system to first go and look if there already is an object like it.
 - because the object you get *may* be shared with other code, you're at the mercy of that other code to not mutate it. (and you have to behave yourself too)
 - it would likely introduce memory leaks (because it's the CachedRepresentation part of UniqueRepresentation that makes these leaks likely).
 

Travis Scrimshaw

unread,
May 26, 2018, 12:24:10 AM5/26/18
to sage-devel
MatrixGroups are immutable and their comparison is by checking the generators (and not isomorphism), which are essentially the construction parameters (in reality, they are the corresponding GAP group). For permutation groups, the equality seems to be isomorphism. So there is no problem for MatrixGroups being UniqueRepresentation in terms of behavior.

Best,
Travis

Erik Bray

unread,
May 28, 2018, 7:56:35 AM5/28/18
to sage-devel
On Sat, May 26, 2018 at 6:24 AM, Travis Scrimshaw <tsc...@ucdavis.edu> wrote:
> MatrixGroups are immutable and their comparison is by checking the
> generators (and not isomorphism), which are essentially the construction
> parameters (in reality, they are the corresponding GAP group). For
> permutation groups, the equality seems to be isomorphism. So there is no
> problem for MatrixGroups being UniqueRepresentation in terms of behavior.

+1 in principle. Nils has said to me as well that UniqueRepresention
(or even simply CachedRepresentation) is known for introducing memory
leaks. I certainly believe that--one doesn't come to such a
conclusion without hard-earned experience. But I'm skeptical that
that's something inherent to its design that can't be overcome with
correct use. Obviously it should not be used with classes that are
not truly immutable. I think Sage could use a better way to keep
track of and/or enforce immutability of classes (that is, instances of
classes). For example, have some base class which can be used as a
mix-in (or an ABC) that designates something as immutable, and
disallow assigning any attributes to its dict that aren't also
immutable (including of course support for all the common built-in
types).

Of course, getting something like that right is not completely trivial
and would require a lot of overhaul. I'm just surprised that it isn't
already something that is considered more systematically.


> On Saturday, May 26, 2018 at 5:53:15 AM UTC+10, Nils Bruin wrote:
>>
>>
>>
>> On Friday, May 25, 2018 at 12:17:35 PM UTC-7, Simon King wrote:
>>>
>>> But they could still be CachedRepresentation. Then, if the same subgroup
>>> is given by the same generators, it is identical, but if the same
>>> subgroup is given by different generators, it is just equal but not
>>> identical.
>>>
>> But before doing so, you would need to show that in common scenarios it
>> produces a benefit. It has three significant draw-backs:
>> - you'd slow down the creation of matrix groups in general, because
>> you're requiring the system to first go and look if there already is an
>> object like it.
>> - because the object you get *may* be shared with other code, you're at
>> the mercy of that other code to not mutate it. (and you have to behave
>> yourself too)
>> - it would likely introduce memory leaks (because it's the
>> CachedRepresentation part of UniqueRepresentation that makes these leaks
>> likely).
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

Simon King

unread,
May 28, 2018, 10:24:31 AM5/28/18
to sage-...@googlegroups.com
Hi Erik

On 2018-05-28, Erik Bray <erik....@gmail.com> wrote:
> I think Sage could use a better way to keep
> track of and/or enforce immutability of classes (that is, instances of
> classes). For example, have some base class which can be used as a
> mix-in (or an ABC) that designates something as immutable, and
> disallow assigning any attributes to its dict that aren't also
> immutable (including of course support for all the common built-in
> types).

I don't think this could possibly work. But actually that's not a Sage
problem but a Python problem: Perhaps somewhere in the Python ecosystem
such a mix-in class exists?

However, I find your notion of immutability ("do not allow assigning
attributes and make all existing attributes immutable") far too narrow.
IIRC, immutable means that once the object is created, its equivalence
class with respect to the "==" operator will be preserved no matter what
of its (no-underscore?) methods are called.

Thus, I believe it must be allowed to assign to an attribute of object X,
as long as the behaviour of X==Y remains unchanged for all objects Y
(and of course hash(X) doesn't change either).

Best regards,
Simon

Nils Bruin

unread,
May 28, 2018, 12:11:41 PM5/28/18
to sage-devel
On Monday, May 28, 2018 at 7:24:31 AM UTC-7, Simon King wrote:
However, I find your notion of immutability ("do not allow assigning
attributes and make all existing attributes immutable") far too narrow.
IIRC, immutable means that once the object is created, its equivalence
class with respect to the "==" operator will be preserved no matter what
of its (no-underscore?) methods are called.

Thus, I believe it must be allowed to assign to an attribute of object X,
as long as the behaviour of X==Y remains unchanged for all objects Y
(and of course hash(X) doesn't change either).

That's a definition of "immutable" that suffices for using things as keys in dictionaries. However, if the object you created might be referenced elsewhere, in totally unrelated code (because that code happens to have called PolynomialRing(Rationals(),names=['x','y']) as well) then you need to be a *lot* more careful. I'm not sure that locking some objects completely from mutation would be a feasible solution (it will be nearly impossible to enforce in python, and  we might not be able to get proper performance with it), but  if programmers don't take this very seriously we'll end up with a code base that is very difficult to reason about.

The conflation of the two notions of immutability, and the different levels of enforcement required for them, is what worries me about UniqueRepresentation. Originally, the use of UniqueRepresentation was required to ensure the system could *repeatedly* produce identical objects automatically, based on input parameters, see https://trac.sagemath.org/ticket/25388#comment:10 . It has the side-effect of allowing quick equality-by-identity checking. So it may *look* like UniqueRepresentation is a great way of speeding up "==" and "hash" for things that are immutable, but it requires a much higher level of immutability than required for hash.

(and in practice, the memory leaks caused by UniqueRepresentation bite us with clockwork regularity)

chris wuthrich

unread,
May 29, 2018, 7:01:51 AM5/29/18
to sage-devel

As a simple-minded user I stumbled over exactly this last week. I don't understand much of what this thread is discussing, but I know what a simple-minded user wants.

sage: G = GL(2,13)
sage: G = G.as_matrix_group()
sage: H = G.subgroup([ matrix(GF(13),[[1,0],[1,1]]) ])
sage: H2 = G.subgroup([ matrix(GF(13),[[1,1],[0,1]]) ])
sage: H3 = G.subgroup([ matrix(GF(13),[[1,0],[2,1]]) ])

I expect H == H3 to say True as they are the same subgroup.
I expect H = H2 to say False, since they are not the same subgroup, even though they are isomorphic.
Instead

sage: H == H3
False
sage: matrix(GF(13),[[1,0],[1,1]]) in H3
True
sage: matrix(GF(13),[[1,0],[2,1]]) in H
True
sage: H.is_isomorphic(H3)
True
sage: H.is_isomorphic(H2)
True
sage: matrix(GF(13),[[1,0],[1,1]]) in H2
False

I though of working around it by checking if they are the same as sets, but to my surprise:

sage: Set( h for h in H ) == Set( h for h in H3 )
False
sage: Set( h.matrix() for h in H ) == Set( h.matrix() for h in H3 )
True

In short: I consider this a bug. No matter how this is done at the back, the user expects == to mean mathematical equality, here equality of subgroups. Otherwise the function should be called subgroups_with_given_generators.

Chris

John Cremona

unread,
May 29, 2018, 7:15:30 AM5/29/18
to SAGE devel
This is not the only place in Sage where there is hidden structure which equality testing uses.

sage: QuadraticField(2) == QuadraticField(8)
False

This looks wrong if you naively think that you are defining a subset of CC or RR.  But number fields in Sage are all defined with a fixed generating element, i.e. they are not just QQ-algebras but QQ[X]-algebras.

In the matrix subgroup case it is hard to see how H and the other subgroups are intended to be viewed if not as subsets of G.  (By the way, your code raises an error for me in the assignment to H I get

AttributeError: 'sage.matrix.matrix_modn_dense_float.Matrix_modn_dense_float' object has no attribute 'gap'

)
 


Chris

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscribe@googlegroups.com.

Erik Bray

unread,
May 29, 2018, 8:34:07 AM5/29/18
to sage-devel
To be clear, I'm not even talking about *enforcing* immutability; in
Python that is impossible. I'm just talking about bookkeeping
indicating that objects of a class should be considered immutable, and
this fact discoverable through introspection (possibly with a small
amount of intelligence where possible, but certainly not guaranteeing
protection from programmer error).

Travis Scrimshaw

unread,
May 30, 2018, 2:14:20 AM5/30/18
to sage-devel
I think it is a bad thing in this case for == to be equality as sets. Imagine if these are two really big, equal, but differently constructed subgroups. This would be a really long and expensive check, whereas in most cases, checking the defining objects are sufficient. I believe we have other places in Sage where == is not strict mathematical equality for similar reasons. -1 on changing the == semantics here.

Now I would say the equality as sets (which really comes down to equality of elements) is a bug. Two matrix group elements should compare by their matrices and not have the coercion system involved otherwise. My guess is the coercion system tries to convert the elements of H into H3 and vice versa, which is cannot do, and hence, results in a False for equality. This probably requires a reimplementation of the comparison method of matrix group elements.

Best,
Travis

John Cremona

unread,
May 30, 2018, 4:07:06 AM5/30/18
to SAGE devel
We should then admit that users will regularly be surprised.  Perhaps this is similar to the situation for evaluating boolean expressions, where (I seem to remember) False is returned in case of "don't know".  Any subgroup constructor (e.g. from generators) which results in a subgroup for which testing membership is impossible (or worse, silently returns False for every element of the ambient group) is surely not going to be very useful; and if there is a membership test then testing two subgroups for equality is easy (though of course possibly slow).

In summary, if we implement subgroups in such a way that testing equality is not implemented then it is very misleading to return False every time.
 

Now I would say the equality as sets (which really comes down to equality of elements) is a bug. Two matrix group elements should compare by their matrices and not have the coercion system involved otherwise. My guess is the coercion system tries to convert the elements of H into H3 and vice versa, which is cannot do, and hence, results in a False for equality. This probably requires a reimplementation of the comparison method of matrix group elements.

+1 to that.
 

Best,
Travis

David Loeffler

unread,
May 30, 2018, 4:30:04 AM5/30/18
to SAGE devel
> In summary, if we implement subgroups in such a way that testing equality is not implemented then it is very misleading to return False every time.

I've run into this issue before (that two subgroups of the same ambient matrix group can compare as unequal, despite having the same elements). See https://trac.sagemath.org/ticket/24301, where there is some discussion between Travis and me whether this should be considered a bug. 

(Of course, however one feels about that matter, there is no question that testing Set( h for h in H ) == Set( h for h in H3 ) should return True and anything else is a definite bug.)

David

chris wuthrich

unread,
May 30, 2018, 4:35:43 AM5/30/18
to sage-devel

I think it is a bad thing in this case for == to be equality as sets. Imagine if these are two really big, equal, but differently constructed subgroups. This would be a really long and expensive check, whereas in most cases, checking the defining objects are sufficient. I believe we have other places in Sage where == is not strict mathematical equality for similar reasons. -1 on changing the == semantics here.


I am strongly in favour of changing all the other instances of wrong ==; or, at least, that they are well documented aberations. Or that we rename things (like subgroups_with_generator) to make it mathematically correct again.
If ever a user wants to check that the two subgroups were given by the same generators then he will check if .gens() are equal. Otherwise he will know that it may take time to test equality, just like with any other function.

I am happy with John's example of quadratic fields. The QQ-algebras QuadraticField(2) and QuadraticField(8) are not equal in any canonical thing they are contained in as there are two isomorphisms between them.
 
Now I would say the equality as sets (which really comes down to equality of elements) is a bug. Two matrix group elements should compare by their matrices and not have the coercion system involved otherwise. My guess is the coercion system tries to convert the elements of H into H3 and vice versa, which is cannot do, and hence, results in a False for equality. This probably requires a reimplementation of the comparison method of matrix group elements.

Yes, fully agree. In fact elements should not have a "matrix" at all, since they are matrices by definition to the user. The element class, like many other group things, may want to be worked over completely. I am also often unhappy about PGL, which returns a permutation group, by the way.

 Chris

Nils Bruin

unread,
May 30, 2018, 12:10:35 PM5/30/18
to sage-devel
On Wednesday, May 30, 2018 at 1:35:43 AM UTC-7, chris wuthrich wrote:
 I am also often unhappy about PGL, which returns a permutation group, by the way.
 
Well, that's not a matrix group in a canonical way, so there's a good reason for that (and, if you're interested in the abstract group it may well be that the permutation representation is the fastest to work with).

chris wuthrich

unread,
May 30, 2018, 12:26:54 PM5/30/18
to sage-devel
> Well, that's not a matrix group in a canonical way, so there's a good reason for that (and, if you're interested in the abstract group it may well be that the permutation representation is the fastest to work with).

Agree, but it would be nice to say G = PGL(2,13) and then G(some matrix) to get its class or backwards to represent an element by a matrix, etc. But that is a different stroy than what this tread was about.

Erik Bray

unread,
May 31, 2018, 6:05:26 AM5/31/18
to sage-devel
Could you actually point me to one of those memory leaks? I'm sure
they exist but I'm still not clear on how this happens. I suspect it
could be improved, and I would like to look into how...

Erik Bray

unread,
May 31, 2018, 6:07:11 AM5/31/18
to sage-devel
"mathematical equality" is also a red herring being that there are
many possible definitions thereof. Are we talking equality up to
isomorphism? Etc...

Nils Bruin

unread,
May 31, 2018, 11:40:38 AM5/31/18
to sage-devel
On Thursday, May 31, 2018 at 3:07:11 AM UTC-7, Erik Bray wrote:

"mathematical equality" is also a red herring being that there are
many possible definitions thereof.  Are we talking equality up to
isomorphism? Etc...

In this case it is not: presenting a group as a matrix groups means giving the group as a subgroup of GL(n,k). you could argue over WHICH GL(n,k) because we could have many isomorphic copies of those lying around, but we don't:

sage: G1=GL(2,GF(7))
sage: G2=GL(2,GF(7))
sage: G1 is G2
True

so in Sage there is one copy of GL(n,k) that is canonized. After that it is completely clear what equality must mean: equality as subgroup. Of course, we can look at conjugacy and (for the GL's that have outer automorphisms) more generally isomorphism, but those are different questions. Presently, matrix groups are really just "generator lists" for their equality test:

sage: H1=G1.subgroup([G1.1,G1.1^2])
sage: H2=G1.subgroup([G1.1^2,G1.1])
sage: H1 == H2
False

I'm suspicious that, although defining equality like that makes it easy to do some basic algorithmic stuff with them, such as stuffing them in a set etc., it doesn't actually help with actually working with the objects. But perhaps there are convincing examples that show that having a very cheap but wrong equality test must available for infrastructure reasons.

David Loeffler

unread,
May 31, 2018, 11:41:55 AM5/31/18
to SAGE devel
On 31 May 2018 at 11:07, Erik Bray <erik....@gmail.com> wrote:

"mathematical equality" is also a red herring being that there are
many possible definitions thereof.  Are we talking equality up to
isomorphism? Etc...

In the example posted by Chris Wuthrich, all the objects invoved were, by construction, subgroups of a common ambient group (in this case G = GF(2, 13)). In this case there is one and only one notion of equality which makes sense, and that is "having the same elements".

David

Nils Bruin

unread,
May 31, 2018, 12:24:57 PM5/31/18
to sage-devel


On Thursday, May 31, 2018 at 3:05:26 AM UTC-7, Erik Bray wrote:

Could you actually point me to one of those memory leaks?  I'm sure
they exist but I'm still not clear on how this happens.  I suspect it
could be improved, and I would like to look into how...

Simon Brandhorst

unread,
Jun 1, 2018, 5:24:01 AM6/1/18
to sage-devel
Suggestion:

(1) Use unique representation for "ambient" objects ( GL(n,k), O(n,k,e), QQ^n).
(2) Do not use unique representation for subobjects.
(3) Give the .subobject(self, gens) method a (weak?) cache.
(4) Modify == to test equality as subobjects/subsets.

Simon King

unread,
Jun 3, 2018, 3:58:41 AM6/3/18
to sage-...@googlegroups.com
Hi Simon,

On 2018-06-01, Simon Brandhorst <sbran...@web.de> wrote:
> (1) Use unique representation for "ambient" objects ( GL(n,k), O(n,k,e),
> QQ^n).

+1, unless you say that each set (including a subset of something)
is an ambient object.

> (2) Do not use unique representation for subobjects.

+1, except for subobjects that can be considered "ambient" themselves
(such as: The set of prime numbers in the set of integers; or GL(n,k) in
MatrixSpace(k,n))

> (3) Give the .subobject(self, gens) method a (weak?) cache.

+1, provided that it doesn't add memory leaks.

> (4) Modify == to test equality as subobjects/subsets.

-1, as I tend to think of "==" as a QUICK test.

If testing equality has a potential to hit decision problems (which
certainly is the case for subgroups), then "==" should give a swift
"True" if the two objects are easily seen to be equal (by equality of
the set of generators, say), and should return "False" otherwise.

In these cases, there ought to be a special method that the user will only
call if s/he really is prepared to wait for the answer for a couple of hours.

Note that in a way it would be nice if "==" had a ternary logic
"True/False/Unknown". But Python isn't there yet (although I do recall
that there used to be a PEP for it).

Best regards,
Simon


Travis Scrimshaw

unread,
Jun 3, 2018, 4:54:48 AM6/3/18
to sage-devel

> (4) Modify == to test equality as subobjects/subsets.

-1, as I tend to think of "==" as a QUICK test.

If testing equality has a potential to hit decision problems (which
certainly is the case for subgroups), then "==" should give a swift
"True" if the two objects are easily seen to be equal (by equality of
the set of generators, say), and should return "False" otherwise.

In these cases, there ought to be a special method that the user will only
call if s/he really is prepared to wait for the answer for a couple of hours.

Note that in a way it would be nice if "==" had a ternary logic
"True/False/Unknown". But Python isn't there yet (although I do recall
that there used to be a PEP for it).

I am also generally in favor of having == being a (generally) fast check. However, the symbolics code takes the opposite approach: it has the method is_trivial_equal()  for quick checks but == fires up the proof engine. In terms of surprise, the fast == is clearly worse, but using is_trivially_equal() makes the code harder to read and maintain (often because of inconsistent use in regards to speed regressions).

Best,
Travis

Vincent Delecroix

unread,
Jun 3, 2018, 6:11:23 AM6/3/18
to sage-...@googlegroups.com


On 26/05/2018 06:24, Travis Scrimshaw wrote:
> MatrixGroups are immutable and their comparison is by checking the
> generators (and not isomorphism), which are essentially the construction
> parameters (in reality, they are the corresponding GAP group). For
> permutation groups, the equality seems to be isomorphism. So there is no
> problem for MatrixGroups being UniqueRepresentation in terms of behavior.

And IMHO this is a problem: https://trac.sagemath.org/ticket/24535

Vincent Delecroix

unread,
Jun 3, 2018, 6:26:46 AM6/3/18
to sage-...@googlegroups.com
It is urgent to decide clear semantics for equality *globally* in Sage.
That is

1. what Python `==` means in Sage and state it clearly in the
developer's guide and documentation

2. alternative function/operator for other kind of equalities

Note that Python == is used in non-trivial operation such as
constructing hash tables (set, dictionaries). It would be a bad
design to set == to be something else than mathematical equality
(ie equality of the subgroups).

Note also that it is perfectly fine for "==" to raise an error such as
NotImplementedError. If some algorithm is not able to decide whether
H1 and H2 are equal it can just give up.

Vincent

Vincent Delecroix

unread,
Jun 3, 2018, 6:38:58 AM6/3/18
to sage-...@googlegroups.com
But what if you *do* want to compare the subgroups (as Chris does). When
I ask "How many apples in my basket?" to Sage I don't want an answer
like "red bikes are nicer than blue ones" because it is faster to do so.
The problem here is definitely *not* to discuss whether equality of
subgroups is decidable or fast but what "==" should be.

Volker Braun

unread,
Jun 3, 2018, 6:45:40 AM6/3/18
to sage-devel
On Sunday, June 3, 2018 at 12:26:46 PM UTC+2, vdelecroix wrote:
Note also that it is perfectly fine for "==" to raise an error such as
NotImplementedError. If some algorithm is not able to decide whether
H1 and H2 are equal it can just give up. 

The problem isn't that the computer will ever run out of things to try to show that two groups are isomorphic. In fact, quite the opposite: All RAM will be consumed while trying to show equality, and eventually the oomkiller will terminate the process.

Simon King

unread,
Jun 3, 2018, 7:33:16 AM6/3/18
to sage-...@googlegroups.com
Hi Travis,

On 2018-06-03, Travis Scrimshaw <tsc...@ucdavis.edu> wrote:
> I am also generally in favor of having == being a (generally) fast check.
> However, the symbolics code takes the opposite approach: it has the method
> is_trivial_equal() for quick checks but == fires up the proof engine.

No, that's not correct.

For symbolics, "==" only does trivial checks and leaves the equality
unevaluated otherwise, so that you need an explicit evaluation as a
bool in order to force a non-trivial computation.

Such as:

sage: (x+1)^2 == x^2+2*x+1
(x + 1)^2 == x^2 + 2*x + 1
sage: bool(_)
True

Best regards,
Simon

Samuel Lelievre

unread,
Jun 3, 2018, 7:54:24 AM6/3/18
to sage-devel
Sun 2018-06-03 11:33:16 UTC, Simon King:

>
> For symbolics, "==" only does trivial checks and leaves the equality
> unevaluated otherwise, so that you need an explicit evaluation as a
> bool in order to force a non-trivial computation.
>
> Such as:
>
>   sage: (x+1)^2 == x^2+2*x+1
>   (x + 1)^2 == x^2 + 2*x + 1
>   sage: bool(_)
>   True

Actually, for symbolics, "==" always creates an equation,
and never tries to evaluate it!

A lot of confusion stems from the fact that what "==" does
depends on whether both sides are symbolic:

- if neither side is symbolic, it tests equality
if either side is symbolic, it creates an equation

Once an equation has been created, to evaluate
whether the equation holds, one can use "bool".

Compare:

    sage: 0 == 1
    False
    sage: SR(0) == 1
    0 == 1
    sage: 0 == SR(1)
    0 == 1
    sage: SR(0) == SR(1)
    0 == 1

Simon King

unread,
Jun 3, 2018, 7:56:01 AM6/3/18
to sage-...@googlegroups.com
On 2018-06-03, Simon King <simon...@uni-jena.de> wrote:
> Hi Travis,
>
> On 2018-06-03, Travis Scrimshaw <tsc...@ucdavis.edu> wrote:
>> I am also generally in favor of having == being a (generally) fast check.
>> However, the symbolics code takes the opposite approach: it has the method
>> is_trivial_equal() for quick checks but == fires up the proof engine.
>
> No, that's not correct.
>
> For symbolics, "==" only does trivial checks

That's not correct either. "==" apparently always returns an equation,
not a bool.


Marc Mezzarobba

unread,
Jun 3, 2018, 8:40:30 AM6/3/18
to sage-...@googlegroups.com
Travis Scrimshaw wrote:
> In terms of surprise, the fast == is clearly worse,

It is not that clear to me! (What I think I'd expect if I didn't know
Sage would be for == to compare the representation of the objects, not
their mathematical semantics, even when that semantics is unambiguous.)

--
Marc

Travis Scrimshaw

unread,
Jun 3, 2018, 8:47:01 PM6/3/18
to sage-devel
Sorry, I was thinking of in the context of evaluating a boolean statement (such as "if x == y"). However, when checking the truth value of an expression, it does fire up the full engine:

sage: x = var('x')
sage
: f = sin(x)^2 + cos(x)^2
sage
: f
cos
(x)^2 + sin(x)^2
sage
: %timeit bool(f == 1)
10 loops, best of 3: 22.2 ms per loop
sage
: %timeit f.is_trivially_equal(1)
The slowest run took 11394.28 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.67 µs per loop
sage
: bool(f == 1)
True
sage
: f.is_trivially_equal(1)
False

If it was doing something trivial, both outputs would be the same and there would be far less time taken to evaluate the bool.

Best,
Travis

Travis Scrimshaw

unread,
Jun 3, 2018, 8:51:34 PM6/3/18
to sage-devel

> I think it is a bad thing in this case for == to be equality as sets.
> Imagine if these are two really big, equal, but differently constructed
> subgroups. This would be a really long and expensive check, whereas in most
> cases, checking the defining objects are sufficient. I believe we have
> other places in Sage where == is not strict mathematical equality for
> similar reasons. -1 on changing the == semantics here.

But what if you *do* want to compare the subgroups (as Chris does). When
I ask "How many apples in my basket?" to Sage I don't want an answer
like "red bikes are nicer than blue ones" because it is faster to do so.
The problem here is definitely *not* to discuss whether equality of
subgroups is decidable or fast but what "==" should be.

So we have moved from bikeshedding to bikecoloring? :P However, that is not the correct analogy. I would say a better analogy with the apple basket is "are the trees these apples came from the same." IMO, these two issues are coupled (in part due to limitations of Python not allowing an Unknown return). One option on the table is to allow == to check a potential undecidable or very slow test.

Best,
Travis

Nils Bruin

unread,
Jun 11, 2018, 4:10:02 PM6/11/18
to sage-devel
And to illustrate with what frequency you can expect to discover these things in our code base:



Jeroen Demeyer

unread,
Jun 12, 2018, 11:13:54 AM6/12/18
to sage-...@googlegroups.com
On 2018-05-25 10:00, Travis Scrimshaw wrote:
> I believe the matrix and permutation groups are quite old code, so
> UniqueRepresentation may not have been available at that time. The
> permutation group code does need updating; in particular, it is still an
> old-style parent:

See https://trac.sagemath.org/ticket/24612 for that. It's sort-of on my
radar since I did that for intervals (#24371), matrix spaces (#23719)
and I'm working on multi-variate polynomials (#25558).

Unfortunately, in all 3 cases above I discovered a huge mess when
looking at the code. They all involved quite a bit of work to clean that up.


Jeroen.
Reply all
Reply to author
Forward
0 new messages