normalization (and hash) for Laurent polynomials is broken

[videlec]

sage: R.<t> = LaurentPolynomialRing(ZZ)
sage: hash(R.zero())
0
sage: hash(t - t)
1

Original report:

https://groups.google.com/forum/#!topic/sage-support/HqP8dXYNDTU

see also: #21284

Component: algebra

Author: Vincent Delecroix

Branch/Commit: 85b064e

Reviewer: Julian Rüth

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

[nbruin]

comment:2

Fixing __normalize should be pretty easy: laurent polynomials are represented as u*xⁿ, where u is a unit or 0. Normalize should simply force n to be a particular value (probably n=0) if u=0.

[videlec]

comment:3

Sure but there are other things I want to do:

• the hash should coincide with polynomials when valuation is >= 0
• the hash should be non-trivial enough to avoid simple collisions

[videlec]

Commit: 388fb53

[videlec]

Branch: u/vdelecroix/21272

[videlec]

Author: Vincent Delecroix

[videlec]

New commits:

388fb53

Trac 21272: fix normalize and hash of Laurent polynomials

[bgrenet]

comment:6

• How did you choose the value 700005?
• You should replace TESTS: by TESTS:: in __hash__.

[saraedum]

Work Issues: reviewer comments

[saraedum]

comment:8

vdelecroix: Can you somehow push this branch again? For me, all it shows in trac is that the laurent_polynomial.pyx file has been deleted.

[sagetrac-git]

Changed commit from 388fb53 to 16b6633

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

16b6633

Trac 21272: fix normalize and hash of Laurent polynomials

[videlec]

comment:10

Rebased on 7.5.beta6!

[sagetrac-git]

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

6439a4e

21272: forgot a colon

[sagetrac-git]

Changed commit from 16b6633 to 6439a4e

[videlec]

comment:12

Replying to @bgrenet:

• How did you choose the value 700005?

A fairly random number.

• You should replace TESTS: by TESTS:: in __hash__.

Done. Thanks.

[saraedum]

Changed work issues from reviewer comments to none

[saraedum]

Changed branch from u/vdelecroix/21272 to u/saraedum/21272

[saraedum]

comment:15

If you agree with my change, feel free to set this to positive review.

[saraedum]

Reviewer: Julian Rüth

[saraedum]

Changed branch from u/saraedum/21272 to u/vdelecroix/21272

[saraedum]

Changed branch from u/vdelecroix/21272 to u/saraedum/21272

[saraedum]

Changed commit from 6439a4e to 85b064e

[saraedum]

New commits:

85b064e

fix grammar

[saraedum]

comment:17

Have you considered turning __u into a sparse polynomial, shifting it, and computing the hash from there? I guess that would be my only proposal here to remove a duplication of code. But it is probably not worth it. Your tests should catch any changes in the implementation of the hash function of polynomials…

[videlec]

comment:18

Replying to @saraedum:

Have you considered turning __u into a sparse polynomial, shifting it, and computing the hash from there? I guess that would be my only proposal here to remove a duplication of code. But it is probably not worth it. Your tests should catch any changes in the implementation of the hash function of polynomials…

Converting the data structure at the time of the hash is not a good idea (time costly). Is this what you were proposing? On the other hand, modifying the internal data structure of laurent polynomials is beyond the scope of this ticket.

[vbraun]

Changed branch from u/saraedum/21272 to 85b064e