Opened 3 years ago

Closed 3 years ago

Last modified 3 years ago

#17740 closed defect (fixed)

Division of modules by basering elements should not pass to the fraction field.

Reported by: robertwb Owned by:
Priority: major Milestone: sage-6.5
Component: coercion Keywords:
Cc: Merged in:
Authors: Robert Bradshaw Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 2075e2e (Commits) Commit:
Dependencies: Stopgaps:

Description (last modified by robertwb)

sage: cm = sage.structure.element.get_coercion_model()
sage: cm.bin_op(GF(5)['x'].gen(), 7, operator.div).parent()
Fraction Field of Univariate Polynomial Ring in x over Finite Field of size 5

The problem is that we are not finding the inverse because we are passing to the fraction field of ZZ before coercing to GF(5).

Change History (33)

comment:1 Changed 3 years ago by robertwb

  • Description modified (diff)

comment:2 Changed 3 years ago by robertwb

  • Branch set to u/robertwb/coerce-div

comment:3 Changed 3 years ago by nbruin

  • Commit set to 6a507b79f14c7db4f28ac841996cc2ef3d1ba71d

Can we also address here why asking the coercion system to do this operation does not lead to the same result as when we just do the computation?

sage: parent(GF(5)['x'].gen()/7)
Univariate Polynomial Ring in x over Finite Field of size 5

There may be good reasons for this (performance?) so I'm not immediately suggesting that we change the code to use the same path in both cases, but we should document that and why we're not.


New commits:

6a507b7Better inversion of module actions for correct division coercions.

comment:4 Changed 3 years ago by robertwb

  • Status changed from new to needs_review

It was probably added because coercion simply didn't used to do the right thing. I've filed #17741 about removing the redundant div which may uncover surprises.

comment:5 Changed 3 years ago by vdelecroix

My main concern is that your solution ignore iteration

sage: cm.get_action(GF(5)['x']['y'], ZZ, operator.div)
Right inverse action by Fraction Field of Univariate Polynomial Ring in x over Finite Field of size 5 on Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Finite Field of size 5
with precomposition on right by Composite map:
  From: Integer Ring
  To:   Fraction Field of Univariate Polynomial Ring in x over Finite Field of size 5
  Defn:   Natural morphism:
          From: Integer Ring
          To:   Finite Field of size 5
        then
          Polynomial base injection morphism:
          From: Finite Field of size 5
          To:   Univariate Polynomial Ring in x over Finite Field of size 5
        then
          Ring Coercion morphism:
          From: Univariate Polynomial Ring in x over Finite Field of size 5
          To:   Fraction Field of Univariate Polynomial Ring in x over Finite Field of size 5

I think that GF(5)['x,y'] and GF(5)['x']['y'] should behave similarly.

Vincent

comment:6 Changed 3 years ago by robertwb

Yes, I've actually been thinking about that as well, and I'm not sure exactly how best to handle this. GF(5)x?y? is a GF(5)-module but represented as a GF(5)x?-module. Or, put otherwise, (most) elements of ZZ have an inverse in GF(5); we want to take the most conservative inverse possible.

I used to be very against partial coercions like QQ -> GF(p), but I'm not as sure anymore.

comment:7 Changed 3 years ago by robertwb

Note that this behavior is not new

sage: parent(GF(5)['x']['y'].gen() / 2)
Univariate Polynomial Ring in y over Fraction Field of Univariate Polynomial Ring in x over Finite Field of size 5

More generally, given an R-module M and an element in R0 such that R0 -> R1 -> ... -> Rn -> R, where along this chain should the multiplicative inverse be calculated? Maybe the first (last?) Ri that is already field? Starts to feel a bit ad-hoc...

comment:8 Changed 3 years ago by git

  • Commit changed from 6a507b79f14c7db4f28ac841996cc2ef3d1ba71d to 1e88c72687b89713e3ca79e435c509c0d99bece2

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

7744207Better behavior for polynomial division.
1e88c72Another polynomial division action test.

comment:9 Changed 3 years ago by robertwb

OK, I've implemented the above behavior.

comment:10 Changed 3 years ago by vdelecroix

  • Branch changed from u/robertwb/coerce-div to u/vdelecroix/17440
  • Commit changed from 1e88c72687b89713e3ca79e435c509c0d99bece2 to 96c1a0348964c4edbd42f3fc52e93b9e76f26156
  • Status changed from needs_review to needs_info

I wrote trivial commits while I was reading the code. One thing to mention: in the documentation you should use :trac:`17440` instead of #17440.

One last question: in coerce.pyx, you wrote

try:
    return ~right_mul
except TypeError: # action may not be invertible
    self._record_exception()

Shouldn't we catch only CoercionException?


New commits:

a60134ctrac #17740: review 1 (documentation)
728811dtrac #17740: review 2 (clean Errors)
96c1a03trac #17740: review 3 (less in try/except block)

comment:11 follow-up: Changed 3 years ago by vdelecroix

  • Status changed from needs_info to needs_work

And something is broken:

sage -t schemes/toric/divisor.py
**********************************************************************
File "schemes/toric/divisor.py", line 35, in sage.schemes.toric.divisor
Failed example:
    (1/2)*Dx + Dy/3 - Dz
Exception raised:
    Traceback (most recent call last):
    ...
    TypeError: unsupported operand parent(s) for '/': 'Group of toric ZZ-Weil divisors on 2-d CPR-Fano toric variety covered by 6 affine patches' and 'Integer Ring'
**********************************************************************
File "schemes/toric/divisor.py", line 40, in sage.schemes.toric.divisor
Failed example:
    (Dx/2).parent()
Exception raised:
    Traceback (most recent call last):
    ...
    TypeError: unsupported operand parent(s) for '/': 'Group of toric ZZ-Weil divisors on 2-d CPR-Fano toric variety covered by 6 affine patches' and 'Integer Ring'
**********************************************************************
File "schemes/toric/divisor.py", line 866, in sage.schemes.toric.divisor.ToricDivisor_generic.is_Weil
Failed example:
    (D/2).is_Weil()
Exception raised:
    Traceback (most recent call last):
    ...
    TypeError: unsupported operand parent(s) for '/': 'Group of toric ZZ-Weil divisors on 2-d CPR-Fano toric variety covered by 3 affine patches' and 'Integer Ring'
**********************************************************************
File "schemes/toric/divisor.py", line 893, in sage.schemes.toric.divisor.ToricDivisor_generic.is_QQ_Weil
Failed example:
    (D/2).is_QQ_Weil()
Exception raised:
    Traceback (most recent call last):
    ...
    TypeError: unsupported operand parent(s) for '/': 'Group of toric ZZ-Weil divisors on 2-d CPR-Fano toric variety covered by 3 affine patches' and 'Integer Ring'
**********************************************************************
3 items had failures:
   2 of  42 in sage.schemes.toric.divisor
   1 of   5 in sage.schemes.toric.divisor.ToricDivisor_generic.is_QQ_Weil
   1 of   5 in sage.schemes.toric.divisor.ToricDivisor_generic.is_Weil
    [363 tests, 4 failures, 2.53 s]
----------------------------------------------------------------------
sage -t schemes/toric/divisor.py  # 4 doctests failed
----------------------------------------------------------------------

comment:12 in reply to: ↑ 11 Changed 3 years ago by vdelecroix

Replying to vdelecroix:

And something is broken:

sage -t schemes/toric/divisor.py

The problematic line is module_action = type(self)(K, self.codomain()) in coerce_action.pyx

sage: dP6 = toric_varieties.dP6()
sage: Dx,Du,Dy,Dv,Dz,Dw = dP6.toric_divisor_group().gens()
sage: A = RightModuleAction(ZZ, Dx.parent())
sage: ~A
Traceback (most recent call last):
...
    472             print "self.codomain = {}".format(self.codomain())
--> 473             module_action = type(self)(K, self.codomain())
    474             connecting = K.coerce_map_from(self.G)
...
CoercionException: No common base

comment:13 Changed 3 years ago by robertwb

  • Branch changed from u/vdelecroix/17440 to u/robertwb/17440

comment:14 Changed 3 years ago by robertwb

  • Commit changed from 96c1a0348964c4edbd42f3fc52e93b9e76f26156 to 2cb51c095e0e3375dead95c194febd5873ba5e06

Fixed these failing tests.

Also, no, we don't want to only catch CoercionException there.


New commits:

2cb51c0Re-introduce action of fraction field as fallback for division action.

comment:15 Changed 3 years ago by vdelecroix

Still some failing doctests... (the last one only concerns the more recent 6-5.rc0)

File rings/quotient_ring_element.py

line 360, in sage.rings.quotient_ring_element.QuotientRingElement._div_
Failed example:
    1/cuberoot
Exception raised:
    Traceback (most recent call last):
    ...
    TypeError: self must be an integral domain.
**********************************************************************
line 362, in sage.rings.quotient_ring_element.QuotientRingElement._div_
Failed example:
    1/a
Exception raised:
    Traceback (most recent call last):
    ...
    TypeError: self must be an integral domain.
**********************************************************************
File "src/sage/rings/quotient_ring_element.py", line 370, in sage.rings.quotient_ring_element.QuotientRingElement._div_
Failed example:
    1 / S(x1 + x2)
Expected:
    Traceback (most recent call last):
    ...
    ArithmeticError: Division failed. The numerator is not a multiple of the denominator.
Got:
    Traceback (most recent call last):
    ...
    TypeError: self must be an integral domain.

File rings/padics/local_generic_element.pyx

line 63, in sage.rings.padics.local_generic_element.LocalGenericElement._div_
Failed example:
    R = Zp(7, 4, 'fixed-mod'); 1/R(7)
Expected:
    Traceback (most recent call last):
    ...
    ValueError: cannot invert non-unit
Got:
    Traceback (most recent call last):
    ...
    TypeError: This implementation of the p-adic ring does not support fields of fractions.

File rings/padics/padic_ZZ_pX_FM_element.pyx

line 88, in sage.rings.padics.padic_ZZ_pX_FM_element
Failed example:
    1/a
Exception raised:
    Traceback (most recent call last):
    ...
    TypeError: This implementation of the p-adic ring does not support fields of fractions.
**********************************************************************
line 875, in sage.rings.padics.padic_ZZ_pX_FM_element.pAdicZZpXFMElement._div_
Failed example:
    1 / W(14) == ~W(14)
Exception raised:
    Traceback (most recent call last):
    ...
    TypeError: This implementation of the p-adic ring does not support fields of fractions.
**********************************************************************
line 877, in sage.rings.padics.padic_ZZ_pX_FM_element.pAdicZZpXFMElement._div_
Failed example:
    1 / w
Expected:
    Traceback (most recent call last):
    ...
    ValueError: cannot invert non-unit
Got:
    Traceback (most recent call last):
    ...
    TypeError: This implementation of the p-adic ring does not support fields of fractions.
**********************************************************************
line 885, in sage.rings.padics.padic_ZZ_pX_FM_element.pAdicZZpXFMElement._div_
Failed example:
    1/(t+t^2)
Exception raised:
    Traceback (most recent call last):
    ...
    TypeError: This implementation of the p-adic ring does not support fields of fraction.

In modular/modform_hecketriangle/graded_ring_element.py:

sage -t --long src/sage/modular/modform_hecketriangle/graded_ring_element.py
**********************************************************************
line 887, in sage.modular.modform_hecketriangle.graded_ring_element.FormsRingElement._div_
Failed example:
    ((E4.as_ring_element())^(-2)).parent() == (E4^(-2)).parent()
Exception raised:
    Traceback (most recent call last):
    ...
    NotImplementedError: No way to prove that ModularFormsRing(n=8) over Integer Ring is an integral domain!
**********************************************************************
line 889, in sage.modular.modform_hecketriangle.graded_ring_element.FormsRingElement._div_
Failed example:
    (MR(x)^(-3)).parent()
Exception raised:
    Traceback (most recent call last):
    ...
    NotImplementedError: No way to prove that QuasiMeromorphicModularFormsRing(n=8) over Integer Ring is an integral domain!

comment:16 Changed 3 years ago by vdelecroix

  • Branch changed from u/robertwb/17440 to u/vdelecroix/17740
  • Commit changed from 2cb51c095e0e3375dead95c194febd5873ba5e06 to d1fc166516e7574fceda32a828402c31586bed01

Hello Robert,

Here is a one-line commit that fixes all doctest issues. I am wondering why these did not appear in the first time... Tell me what you think.

Vincent


New commits:

16ca39dtrac #17440: merge 6.5.rc3
d1fc166trac #17440: better _pseudo_fraction_field

comment:17 Changed 3 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:18 Changed 3 years ago by vdelecroix

  • Authors set to Robert Bradshaw
  • Reviewers set to Vincent Delecroix

comment:19 Changed 3 years ago by robertwb

  • Branch changed from u/vdelecroix/17740 to u/robertwb/17740

comment:20 Changed 3 years ago by robertwb

  • Commit changed from d1fc166516e7574fceda32a828402c31586bed01 to bff474b33f681de5d51ebf1be5c95dc7ac7f2f03

I don't think self is the right thing to return by default, but here's a similar fix.


New commits:

bff474bBetter _pseudo_fraction_field default implementation.

comment:21 Changed 3 years ago by vdelecroix

  • Status changed from needs_review to positive_review

comment:22 Changed 3 years ago by vdelecroix

  • Status changed from positive_review to needs_info

Now, I am not sure anymore that your solution is better. The implementation of division_parent tries to execute ~parent.one(). But the default implementation of __invert__ of an element x in sage.structure.element is precisely to call 1/x (and soonly x.parent().one()/x with #17692). Hence using division_parent should lead to some infinite recursions that we curiously do not see here. No?

EDIT: This is fine, because in x.parent().one()/x the numerator and denominator have the same type... and so no coercion is involved and __div__ is called directly.

Last edited 3 years ago by vdelecroix (previous) (diff)

comment:23 Changed 3 years ago by vdelecroix

  • Status changed from needs_info to positive_review

comment:24 Changed 3 years ago by robertwb

Yes, indeed this should go in with #17692 to prevent possible infinite recursion. Thanks for the review!

comment:25 Changed 3 years ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict, possibly #17694

comment:26 Changed 3 years ago by vdelecroix

  • Branch changed from u/robertwb/17740 to u/vdelecroix/17740
  • Commit changed from bff474b33f681de5d51ebf1be5c95dc7ac7f2f03 to 52cc62d92f8bed38aab6e2a9a8cfb785493a69bf
  • Status changed from needs_work to needs_review

Hi Robert,

There was only a trivial conflict in sage/rings/ring.pyx. I did merge with sage-6.6.beta0 in my last commit. I let you set the positive review if this is fine.

Vincent


New commits:

52cc62dtrac #17740: merge sage-6.6.beta0

comment:27 Changed 3 years ago by git

  • Commit changed from 52cc62d92f8bed38aab6e2a9a8cfb785493a69bf to 9c970ae1c2ef9516f61a3c6cc737e6d0c644565e

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

9c970aetrac #17740: merge sage-6.6.beta1

comment:28 Changed 3 years ago by vdelecroix

  • Status changed from needs_review to positive_review

All long tests pass. Put back in positive review.

comment:29 Changed 3 years ago by vbraun

  • Status changed from positive_review to needs_work

I'm getting this on OSX:

sage -t --long src/sage/structure/coerce_actions.pyx
**********************************************************************
File "src/sage/structure/coerce_actions.pyx", line 419, in sage.structure.coerce_actions.ModuleAction.__invert__
Failed example:
    A = ~RightModuleAction(ZZ, GF(5)['x']); A
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 488, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 850, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.structure.coerce_actions.ModuleAction.__invert__[10]>", line 1, in <module>
        A = ~RightModuleAction(ZZ, GF(Integer(5))['x']); A
      File "sage/structure/coerce_actions.pyx", line 464, in sage.structure.coerce_actions.ModuleAction.__invert__ (build/cythonized/sage/structure/coerce_actions.c:7385)
        module_action = type(self)(K, self.codomain())
      File "sage/structure/coerce_actions.pyx", line 376, in sage.structure.coerce_actions.ModuleAction.codomain (build/cythonized/sage/structure/coerce_actions.c:6711)
        return self.underlying_set()
      File "sage/categories/action.pyx", line 186, in sage.categories.action.Action.underlying_set (build/cythonized/sage/categories/action.c:4087)
        raise RuntimeError, "This action acted on a set that became garbage collected"
    RuntimeError: This action acted on a set that became garbage collected
**********************************************************************
File "src/sage/structure/coerce_actions.pyx", line 424, in sage.structure.coerce_actions.ModuleAction.__invert__
Failed example:
    A(x, 2)
Expected:
    3*x
Got:
    1/2*x
**********************************************************************
1 item had failures:
   2 of  15 in sage.structure.coerce_actions.ModuleAction.__invert__
    [90 tests, 2 failures, 0.47 s]

In all these doctests you need to hold domain/codomain explicitly alive.

comment:30 Changed 3 years ago by git

  • Commit changed from 9c970ae1c2ef9516f61a3c6cc737e6d0c644565e to 2075e2e68f6e6fc981096948ad4ffc61c47cfa46

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

2075e2etrac #17740: avoid parent deaths

comment:31 Changed 3 years ago by vdelecroix

  • Status changed from needs_work to positive_review

Right. We should not kill our parents ;-)

It is strange that I did not get these in the first place... All doctest pass.

Vincent

comment:32 Changed 3 years ago by vbraun

  • Branch changed from u/vdelecroix/17740 to 2075e2e68f6e6fc981096948ad4ffc61c47cfa46
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:33 Changed 3 years ago by robertwb

  • Commit 2075e2e68f6e6fc981096948ad4ffc61c47cfa46 deleted

Thanks for following up on this. Looks good to me.

Note: See TracTickets for help on using tickets.