fix(polys): don't unify characteristics #25666

oscarbenjamin · 2023-09-09T22:43:59Z

References to other Issues or PRs

Partial fix for #25653 by disallowing any unification of domains with different characteristic.

Brief description of what is fixed or changed

Previously:

>>> GF(3).unify(ZZ)
ZZ

With the PR:

>>> GF(3).unify(ZZ)
...
UnificationFailed: Cannot unify GF(3) with ZZ

Also adds more consistent handling of .has_CharacteristicZero and .characteristic() for different domains.

Other comments

There was one place in the code

Release Notes

polys
- BREAKING CHANGE: Unification of domains like GF(p) with ZZ or other domains would previously result in ZZ (or any other domain). This now results in a UnificationFailed error. Previously unification like e.g. GF(2).unify(GF(3)) would unify to the large characteristic but this now results in UnificationFailed.

sympy-bot · 2023-09-09T22:44:05Z

✅

Hi, I am the SymPy bot. I'm here to help you write a release notes entry. Please read the guide on how to write release notes.

Your release notes are in good order.

Here is what the release notes will look like:

polys
- BREAKING CHANGE: Unification of domains like GF(p) with ZZ or other domains would previously result in ZZ (or any other domain). This now results in a UnificationFailed error. Previously unification like e.g. GF(2).unify(GF(3)) would unify to the large characteristic but this now results in UnificationFailed. (#25666 by @oscarbenjamin)

This will be added to https://github.com/sympy/sympy/wiki/Release-Notes-for-1.13.

Click here to see the pull request description that was parsed.

<!-- Your title above should be a short description of what
was changed. Do not include the issue number in the title. -->

#### References to other Issues or PRs
<!-- If this pull request fixes an issue, write "Fixes #NNNN" in that exact
format, e.g. "Fixes #1234" (see
https://tinyurl.com/auto-closing for more information). Also, please
write a comment on that issue linking back to this pull request once it is
open. -->

Partial fix for #25653 by disallowing any unification of domains with different characteristic.

#### Brief description of what is fixed or changed

Previously:
```python
>>> GF(3).unify(ZZ)
ZZ
```
With the PR:
```python
>>> GF(3).unify(ZZ)
...
UnificationFailed: Cannot unify GF(3) with ZZ 
```

Also adds more consistent handling of `.has_CharacteristicZero` and `.characteristic()` for different domains.

#### Other comments

There was one place in the code

#### Release Notes

<!-- Write the release notes for this release below between the BEGIN and END
statements. The basic format is a bulleted list with the name of the subpackage
and the release note for this PR. For example:

* solvers
  * Added a new solver for logarithmic equations.

* functions
  * Fixed a bug with log of integers. Formerly, `log(-x)` incorrectly gave `-log(x)`.

* physics.units
  * Corrected a semantical error in the conversion between volt and statvolt which
    reported the volt as being larger than the statvolt.

or if no release note(s) should be included use:

NO ENTRY

See https://github.com/sympy/sympy/wiki/Writing-Release-Notes for more
information on how to write release notes. The bot will check your release
notes automatically to see if they are formatted correctly. -->

<!-- BEGIN RELEASE NOTES -->
* polys
    * BREAKING CHANGE: Unification of domains like `GF(p)` with `ZZ` or other domains would previously result in `ZZ` (or any other domain). This now results in a UnificationFailed error. Previously unification like e.g. `GF(2).unify(GF(3))` would unify to the large characteristic but this now results in UnificationFailed.
<!-- END RELEASE NOTES -->

Update

The release notes on the wiki have been updated.

oscarbenjamin · 2023-09-09T22:44:50Z

sympy/polys/numberfields/primes.py

@@ -396,7 +396,7 @@ def _compute_test_factor(p, gens, ZK):
    # predicts that such an element must exist, so nullspace should
    # be non-trivial.
    x = B.nullspace()[0, :].transpose()
-    beta = ZK.parent(ZK.matrix * x, denom=ZK.denom)
+    beta = ZK.parent(ZK.matrix * x.convert_to(ZZ), denom=ZK.denom)


@skieffer this change preserves existing behaviour. Let me know if something else should be done here.

Thanks for the question, and I'm sorry I wasn't able to respond in time. But your fix looks good. Thanks for this.

As the author of the only code in the whole of SymPy that depended on the previous behaviour do you have any opinions about GF(3).unify(ZZ) and the general change in this PR that disallows it?

Good question. I'll comment on the main thread, #25653.

oscarbenjamin · 2023-09-09T23:59:39Z

sympy/simplify/tests/test_ratsimp.py

    a = (x**5 + 2*x**4 + 2*x**3 + 2*x**2 + x + 2/x + x**(-2))
-    assert ratsimpmodprime(a, [x + 1], domain=GF(2)) == 1
-    assert ratsimpmodprime(a, [x + 1], domain=GF(3)) == -1
+    # assert ratsimpmodprime(a, [x + 1], domain=GF(2)) == 1
+    # assert ratsimpmodprime(a, [x + 1], domain=GF(3)) == -1


These examples highlight a problem with disallowing any unification between GF(p) and ZZ:

In [1]: p = Poly(1, x, modulus=2) In [2]: p Out[2]: Poly(1, x, modulus=2) In [3]: p * 2 ... UnificationFailed: Cannot unify GF(2) with ZZ

There are probably ways to work around this but at least it shows why being able to unify GF(p) and ZZ makes sense in some situations. Here the problem is that the 2 is coerced into Poly(2, x, domain=ZZ) before the product is computed. Then the product tries to unify the two Poly and fails if GF(2) cannot unify with ZZ.

In this example I don't think it matters which way the unification happens as long as they do unify to something.

I fixed this by special casing Poly * int/Integer.

github-actions · 2023-09-10T01:18:43Z

Benchmark results from GitHub Actions

Lower numbers are good, higher numbers are bad. A ratio less than 1
means a speed up and greater than 1 means a slowdown. Green lines
beginning with + are slowdowns (the PR is slower then master or
master is slower than the previous release). Red lines beginning
with - are speedups.

Significantly changed benchmark results (PR vs master)

Significantly changed benchmark results (master vs previous release)

| Change   | Before [8059df73] <sympy-1.12^0>   | After [64a48d1a]    |   Ratio | Benchmark (Parameter)                                                |
|----------|------------------------------------|---------------------|---------|----------------------------------------------------------------------|
| -        | 84.5±0.9ms                         | 55.7±0.3ms          |    0.66 | integrate.TimeIntegrationRisch02.time_doit_risch(10)                 |
| +        | 22.2±0.07μs                        | 39.0±0.2μs          |    1.76 | integrate.TimeIntegrationRisch03.time_doit(1)                        |
| -        | 6.89±0.02ms                        | 3.75±0.01ms         |    0.54 | logic.LogicSuite.time_load_file                                      |
| -        | 2.11±0.01ms                        | 653±2μs             |    0.31 | polys.TimePREM_LinearDenseQuadraticGCD.time_op(3, 'sparse')          |
| -        | 10.4±0.04ms                        | 1.95±0ms            |    0.19 | polys.TimePREM_LinearDenseQuadraticGCD.time_op(5, 'sparse')          |
| -        | 368±0.3μs                          | 81.6±0.2μs          |    0.22 | polys.TimePREM_QuadraticNonMonicGCD.time_op(1, 'sparse')             |
| -        | 4.82±0.01ms                        | 362±0.5μs           |    0.08 | polys.TimePREM_QuadraticNonMonicGCD.time_op(3, 'sparse')             |
| -        | 10.6±0.02ms                        | 1.09±0ms            |    0.1  | polys.TimePREM_QuadraticNonMonicGCD.time_op(5, 'sparse')             |
| -        | 6.24±0.01ms                        | 3.94±0.01ms         |    0.63 | polys.TimeSUBRESULTANTS_LinearDenseQuadraticGCD.time_op(2, 'sparse') |
| -        | 27.2±0.07ms                        | 12.0±0.02ms         |    0.44 | polys.TimeSUBRESULTANTS_LinearDenseQuadraticGCD.time_op(3, 'sparse') |
| -        | 6.92±0.02ms                        | 1.17±0ms            |    0.17 | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(1, 'sparse')    |
| -        | 16.3±0.02ms                        | 9.23±0.01ms         |    0.57 | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(2, 'sparse')    |
| -        | 211±0.4ms                          | 70.4±0.09ms         |    0.33 | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(3, 'sparse')    |
| -        | 6.40±0.01ms                        | 534±1μs             |    0.08 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(3, 'sparse')     |
| -        | 27.9±0.1ms                         | 851±2μs             |    0.03 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(5, 'sparse')     |
| -        | 611±3μs                            | 199±0.8μs           |    0.33 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(1, 'sparse') |
| -        | 6.53±0.02ms                        | 202±1μs             |    0.03 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(3, 'sparse') |
| -        | 17.1±0.04ms                        | 207±0.8μs           |    0.01 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(5, 'sparse') |
| -        | 164±0.2μs                          | 90.7±0.2μs          |    0.55 | solve.TimeMatrixOperations.time_rref(3, 0)                           |
| -        | 313±0.6μs                          | 110±0.5μs           |    0.35 | solve.TimeMatrixOperations.time_rref(4, 0)                           |
| -        | 31.9±0.07ms                        | 13.7±0.2ms          |    0.43 | solve.TimeSolveLinSys189x49.time_solve_lin_sys                       |

Full benchmark results can be found as artifacts in GitHub Actions
(click on checks at the top of the PR).

oscarbenjamin · 2023-09-10T21:38:21Z

This is ready for review.

smichr · 2023-09-11T10:59:15Z

sympy/polys/domains/tests/test_domains.py

@@ -570,6 +580,17 @@ def test_Domain_get_exact():
    assert QQ.frac_field(x, y).get_exact() == QQ.frac_field(x, y)


+def test_Domain_characteristic():
+    for F, c in [(FF(3), 3), (FF(5), 5), (FF(7), 7)]:
+        for R in F, F[x], F.frac_field(x), F.old_poly_ring(x), F.old_frac_field(x):


R is not used in this loop interior -- is something missing?

Ah, good point. Fixed.

smichr · 2023-09-11T11:01:22Z

sympy/polys/polytools.py

@@ -71,6 +71,9 @@ def wrapper(f, g):
        g = _sympify(g)
        if isinstance(g, Poly):
            return func(f, g)
+        elif isinstance(g, Integer):


I assume this is where you special cased Integer (as you referred to in how you fixed the previously commented out tests). Can g be an int or is that always sympified before it gets here?

g is sympified 3 lines up from here.

face plant -- thanks for pointing this out LOL

oscarbenjamin · 2023-09-11T15:28:12Z

Thanks!

fix(polys): don't unify characteristics

38693fb

oscarbenjamin added the polys label Sep 9, 2023

oscarbenjamin commented Sep 9, 2023

View reviewed changes

oscarbenjamin added 4 commits September 9, 2023 23:49

Remove redundant declarations

a64ffeb

fix(polys): move characteristic to ZZ_I and QQ_I subclasses

758357d

fix(polys): add characteristic to old poly/frac

f1365e4

comment out two tests in test_ratsimp.py

4cfed0b

oscarbenjamin commented Sep 9, 2023

View reviewed changes

Remove redundant import

c69df85

oscarbenjamin marked this pull request as draft September 10, 2023 01:05

fix(polys): fix unification of Poly with int

a7088be

oscarbenjamin marked this pull request as ready for review September 10, 2023 16:55

smichr reviewed Sep 11, 2023

View reviewed changes

fix characteristic test

2eca594

smichr merged commit ceb5664 into sympy:master Sep 11, 2023

oscarbenjamin deleted the pr_gf_unify branch September 11, 2023 15:28

skieffer mentioned this pull request Sep 12, 2023

Should ZZ_n.unify(ZZ) give ZZ or ZZ_n? #25653

Open

Uh oh!

fix(polys): don't unify characteristics #25666

fix(polys): don't unify characteristics #25666

Uh oh!

Conversation

oscarbenjamin commented Sep 9, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

References to other Issues or PRs

Brief description of what is fixed or changed

Other comments

Release Notes

Uh oh!

sympy-bot commented Sep 9, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

github-actions bot commented Sep 10, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

oscarbenjamin commented Sep 10, 2023

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

oscarbenjamin commented Sep 11, 2023

Uh oh!

Uh oh!

oscarbenjamin commented Sep 9, 2023 •

edited

Loading

sympy-bot commented Sep 9, 2023 •

edited

Loading

github-actions bot commented Sep 10, 2023 •

edited

Loading