Equality, hashability of Factorizations

[xcaruso]

Currently, two Factorization object are considered to be equal if they have the same value, but a Factorization object is not equal to its value:

sage: P.<x> = QQ[]
sage: a = x+1; b = x+2; c = x+3
sage: F = Factorization([(a,1),(b,1),(c,1)]); F
(x + 1) * (x + 2) * (x + 3)
sage: F1 = Factorization([(a*b,1),(c,1)]); F1
(x + 3) * (x^2 + 3*x + 2)
sage: F2 = Factorization([(a,1),(b*c,1)]); F2
(x + 1) * (x^2 + 5*x + 6)
sage: F == F1
True
sage: F == F2
True
sage: F1 == F2
True
sage: F == a*b*c
False

Is this normal? (It seems to me really weird.)

PS: Am I supposed to ask this kind of questions here or is there a better place?

CC: @xcaruso @tscrim

Component: factorization

Keywords: equality factorization

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

[fchapoton]

comment:3

The methods __eq__ and __ne__ seems not to be implemented in the class.

[xcaruso]

comment:4

I would happily implement them but I'm wondering what should be the correct behaviour of these methods. Do you have an opinion? (Don't forget that a Factorization object can be "non commutative" as well.)

[fchapoton]

comment:5

well, one could try the following in the comparison of self and other

1) look if other is in self.parent (or maybe do that for the first factors)

2) if not compare (the value of self) and other

3) if yes, ask if self.parent is_commutative

4) if yes, sort and compare ; if not compare without sorting ?

[fchapoton]

Attachment: trac_13186_v1.patch.gz

[fchapoton]

comment:6

here is a patch with a proposal for __eq__

[xcaruso]

comment:7

The patch looks ok to me (but I also think that I'm not a good reviewer).

I'm just wondering whether we really want this:

sage: factor(691*(x-4)*(x+6)) == factor(691*(y-4)*(y+6)) 
False 

Indeed, even if 691 is a unit in one case and is not in the other case, the factorizations are the same, aren't they?

[fchapoton]

comment:8

Well, one must choose the meaning of equality.

One precise meaning would be

• a factorisation is made of a unit and a set/list of factors
• two factorisations are equal if they have the same unit and the same factors (up to order maybe)

Another possible solution would be to consider the unit as just any other factor. I do no like this solution, and I prefer the previous (current) behavior

If you want, you can maybe ask for opinions on sage-devel.

Something else: I have just thought that it would sometimes be good to separate factors in the center of the ring (commuting) and other factors, and to implement "partially commutative factorisations". But this is something for the wishlist.

[fchapoton]

Commit: 84b36a2

[fchapoton]

Branch: u/chapoton/13186

[fchapoton]

New commits:

84b36a2

trac 13186 comparison of factorisations

[videlec]

comment:13

Hello,

Please add specifications to the doc! It is not clear to me (and to you as well looking at comment:8) what should be an equality between element.

I really found weird the begining

if not isinstance(other, Factorization):
    return self.value() == other

how can you compare a factorization with something else. Would you like that

sage: [1,2,3] == (1,2,3)
True

Instead of using Sequence, what about

sage: from sage.structure.element import get_coercion_model
sage: cm = get_coercion_model()
sage: cm.common_parent(1,1/2)
Rational field

(not so important, as at the end of the day the same code is called)

If the ring is commutative your test is wrong as the elements of the underlying universe are not necessarily sortable... you can not assume that the order is the same based on the fact that you call sorted. It might also depend on the specification you will add...

You need to define a __ne__ if you want that != works as well. Basically it would be

def __ne__(self, other):
    return not (self == other)

Vincent

[nbruin]

comment:14

There are other problems too:

sage: R.<x>=QQ[]
sage: hash(x^2)
15360174650385708
sage: hash(factor(x^2))
-5999452984666080493
sage: factor(x^2).value()==x^2
True

If you want to equate factorizations with their values (a reasonable thing to do) then their hashes should be equal too. I'd think a reasonable thing to do is to set

factor(A) == B iff factor(A).value() == B
hash(factor(A)) == hash(factor(A).value())

and in fact to implement them by punting to the tests on values.

Note that if "factorizations" are ever returned in domains that do not have unique factorizations, this might be confusing: after all, there are supposed to be factorizations of the same value into irreducibles there that are not mutually equal.

[fchapoton]

Changed branch from u/chapoton/13186 to none

[fchapoton]

comment:15

There is now a __richcmp__ method in this class. One needs to check if the issue still stands.

[fchapoton]

Changed commit from 84b36a2 to none

[mkoeppe]

comment:16

The example from the ticket description gives the following in 9.7.rc0:

sage: F == F1
False
sage: F == F2
False
sage: F1 == F2
False
sage: F == a*b*c
False

Also:

sage: hash(F)
TypeError: <class 'sage.structure.factorization.Factorization'> is not hashable

(see also #33932, example 1)

[mkoeppe]

comment:17

Factorization has implementations of __copy__ and __deepcopy__ that include examples with mutable prime factors.

Do we have a use case for this, or should we just make Factorizations immutable and give it an implementation of _hash_?

[tscrim]

comment:18

Given that its __setitem__ explicitly states a factorization is immutable, I think we should have the (deep)copy be idempotent and implement a __hash__.