Opened 3 months ago

Closed 2 months ago

#27914 closed defect (fixed)

py3: hash collisions of Laurent polynomials

Reported by: gh-mwageringel Owned by:
Priority: major Milestone: sage-8.8
Component: python3 Keywords:
Cc: Merged in:
Authors: Markus Wageringel Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: 26eb5fd (Commits) Commit: 26eb5fdb2a00b442b289eeced0648993957c0fd9
Dependencies: Stopgaps:

Description

This ticket adjusts the hash of multivariate Laurent polynomials, so that it agrees with the hash of univariate Laurent polynomials.

This solves the following problem: Using Python 3, this doctest in laurent_polynomial.pyx fails about 1 out of 4 times.

            sage: L.<w,z> = LaurentPolynomialRing(QQ)
            sage: len({hash(w^i*z^j) for i in [-2..2] for j in [-2..2]})
            25

Due to hash collisions, the result can be smaller than 25 (such as 23 or 21). This gets even worse when using a larger range of monomials.

Regardless of that, it is desirable that univariate and multivariate Laurent polynomials have the same hash anyway. The univariate hash implementation does not seem to have these collisions, so adopting that implementation solves this problem.

For reference, the univariate and multivariate hashes were implemented in #21272 and #23864.

Change History (3)

comment:1 Changed 3 months ago by gh-mwageringel

  • Authors set to Markus Wageringel
  • Branch set to u/gh-mwageringel/py3_hash_laurent
  • Commit set to 26eb5fdb2a00b442b289eeced0648993957c0fd9
  • Status changed from new to needs_review

New commits:

26eb5fdTrac #27914. py3: fix hash of multivariate Laurent polynomials

comment:2 Changed 3 months ago by chapoton

  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, let it be

comment:3 Changed 2 months ago by vbraun

  • Branch changed from u/gh-mwageringel/py3_hash_laurent to 26eb5fdb2a00b442b289eeced0648993957c0fd9
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.