make divides() better

[videlec]

sage: R = Zmod(6)
sage: R(4).divides(R(2))
Traceback (most recent call last):
...
ArithmeticError: reduction modulo 4 not defined

See the relevant discussion on sage-devel.

Component: basic arithmetic

Author: Vincent Delecroix

Branch/Commit: 4a6cbd7

Reviewer: Travis Scrimshaw

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

[videlec]

Commit: 2cf9010

[videlec]

Author: Vincent Delecroix

[videlec]

New commits:

3fa3a95	25277: _test_divides in Rings()
2cf9010	25277: divides for integer mod ring

[videlec]

Branch: u/vdelecroix/25277

[tscrim]

comment:3

IMO, it is better to do

-            S = tester.some_elements()
-            for a in S:
-                for b in S:
+            for a,b in tester.some_elements(repeat=2):

as then it runs max_runs number of times instead of max_runs².

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

cb2a1c3

25277: smarter iteration over pairs of elements

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 2cf9010 to cb2a1c3

[videlec]

comment:5

Replying to @tscrim:

IMO, it is better to do

good suggestion!

[videlec]

comment:6

though some rings are not ready for that yet...

sage -t --long src/sage/combinat/sf/macdonald.py  # 12 doctests failed
sage -t --long src/sage/combinat/ncsf_qsym/ncsf.py  # 10 doctests failed
sage -t --long src/sage/combinat/sf/sfa.py  # 1 doctest failed
sage -t --long src/sage/algebras/steenrod/steenrod_algebra.py  # 11 doctests failed
sage -t --long src/sage/structure/element.pyx  # 1 doctest failed
sage -t --long src/sage/combinat/root_system/root_lattice_realization_algebras.py  # 1 doctest failed
sage -t --long src/sage/combinat/posets/moebius_algebra.py  # 7 doctests failed
sage -t --long src/sage/combinat/sf/k_dual.py  # 6 doctests failed
sage -t --long src/sage/combinat/ncsf_qsym/qsym.py  # 8 doctests failed
sage -t --long src/sage/combinat/sf/llt.py  # 10 doctests failed
sage -t --long src/sage/homology/homology_vector_space_with_basis.py  # 5 doctests failed
sage -t --long src/sage/combinat/grossman_larson_algebras.py  # 2 doctests failed
sage -t --long src/sage/combinat/sf/jack.py  # 10 doctests failed
sage -t --long src/sage/combinat/sf/classical.py  # 5 doctests failed
sage -t --long src/sage/combinat/sf/new_kschur.py  # 5 doctests failed
sage -t --long src/sage/modular/abvar/homspace.py  # 1 doctest failed
sage -t --long src/sage/algebras/yangian.py  # 4 doctests failed
sage -t --long src/sage/manifolds/chart_func.py  # 1 doctest failed
sage -t --long src/sage/algebras/quatalg/quaternion_algebra.py  # 2 doctests failed
sage -t --long src/sage/algebras/iwahori_hecke_algebra.py  # 2 doctests failed
sage -t --long src/sage/combinat/sf/sf.py  # 1 doctest failed
sage -t --long src/sage/algebras/cluster_algebra.py  # 6 doctests failed
sage -t --long src/sage/algebras/quantum_matrix_coordinate_algebra.py  # 3 doctests failed
sage -t --long src/sage/combinat/ncsym/ncsym.py  # 9 doctests failed
sage -t --long src/sage/combinat/sf/schur.py  # 2 doctests failed
sage -t --long src/sage/combinat/free_dendriform_algebra.py  # 2 doctests failed
sage -t --long src/sage/combinat/symmetric_group_algebra.py  # 6 doctests failed
sage -t --long src/sage/combinat/sf/hall_littlewood.py  # 6 doctests failed
sage -t --long src/sage/categories/finite_dimensional_algebras_with_basis.py  # 2 doctests failed
sage -t --long src/sage/combinat/fqsym.py  # 3 doctests failed
sage -t --long src/sage/algebras/rational_cherednik_algebra.py  # 1 doctest failed
sage -t --long src/sage/rings/polynomial/pbori.pyx  # 1 doctest failed
sage -t --long src/sage/manifolds/differentiable/scalarfield_algebra.py  # 3 doctests failed
sage -t --long src/sage/manifolds/scalarfield_algebra.py  # 3 doctests failed
sage -t --long src/sage/algebras/free_algebra.py  # 14 doctests failed
sage -t --long src/sage/algebras/lie_algebras/poincare_birkhoff_witt.py  # 2 doctests failed
sage -t --long src/sage/matrix/matrix_gap.pyx  # 1 doctest failed
sage -t --long src/sage/combinat/diagram_algebras.py  # 5 doctests failed
sage -t --long src/sage/combinat/descent_algebra.py  # 4 doctests failed
sage -t --long src/sage/rings/real_mpfi.pyx  # 1 doctest failed
sage -t --long src/sage/structure/parent.pyx  # 1 doctest failed
sage -t --long src/sage/rings/real_mpfr.pyx  # 1 doctest failed
sage -t --long src/sage/algebras/commutative_dga.py  # 5 doctests failed
sage -t --long src/sage/algebras/nil_coxeter_algebra.py  # 2 doctests failed
sage -t --long src/sage/combinat/posets/incidence_algebras.py  # 2 doctests failed
sage -t --long src/sage/rings/polynomial/polynomial_quotient_ring.py  # 1 doctest failed
sage -t --long src/sage/matrix/matrix_space.py  # 1 doctest failed
sage -t --long src/sage/combinat/sf/character.py  # 2 doctests failed
sage -t --long src/sage/combinat/root_system/weyl_characters.py  # 3 doctests failed
sage -t --long src/sage/algebras/hall_algebra.py  # 6 doctests failed
sage -t --long src/sage/rings/ring.pyx  # 1 doctest failed
sage -t --long src/sage/symbolic/ring.pyx  # 1 doctest failed
sage -t --long src/sage/combinat/ncsym/dual.py  # 2 doctests failed
sage -t --long src/sage/combinat/sf/witt.py  # 2 doctests failed
sage -t --long src/sage/algebras/schur_algebra.py  # 1 doctest failed
sage -t --long src/sage/categories/modules_with_basis.py  # 1 doctest failed
sage -t --long src/sage/combinat/sf/orthotriang.py  # 2 doctests failed
sage -t --long src/sage/algebras/affine_nil_temperley_lieb.py  # 1 doctest failed
sage -t --long src/sage/rings/polynomial/plural.pyx  # 2 doctests failed
sage -t --long src/sage/algebras/shuffle_algebra.py  # 2 doctests failed
sage -t --long src/sage/combinat/sf/dual.py  # 2 doctests failed
sage -t --long src/sage/categories/examples/with_realizations.py  # 4 doctests failed
sage -t --long src/sage/categories/magmas.py  # 1 doctest failed
sage -t --long src/sage/rings/power_series_ring_element.pyx  # 1 doctest failed
sage -t --long src/sage/algebras/yokonuma_hecke_algebra.py  # 1 doctest failed
sage -t --long src/sage/combinat/sf/monomial.py  # 2 doctests failed
sage -t --long src/sage/algebras/clifford_algebra.py  # 2 doctests failed
sage -t --long src/sage/combinat/sf/powersum.py  # 2 doctests failed
sage -t --long src/doc/en/thematic_tutorials/coercion_and_categories.rst  # 4 doctests failed
sage -t --long src/sage/combinat/sf/elementary.py  # 2 doctests failed
sage -t --long src/sage/combinat/sf/homogeneous.py  # 2 doctests failed
sage -t --long src/sage/categories/examples/graded_connected_hopf_algebras_with_basis.py  # 1 doctest failed
sage -t --long src/sage/rings/power_series_ring.py  # 9 doctests failed
sage -t --long src/sage/structure/category_object.pyx  # 2 doctests failed
sage -t --long src/doc/en/thematic_tutorials/tutorial-implementing-algebraic-structures.rst  # 1 doctest failed
sage -t --long src/sage/quivers/algebra.py  # 1 doctest failed
sage -t --long src/sage/rings/multi_power_series_ring.py  # 7 doctests failed
sage -t --long src/sage/rings/quotient_ring.py  # 1 doctest failed
sage -t --long src/sage/categories/hopf_algebras_with_basis.py  # 2 doctests failed
sage -t --long src/sage/algebras/tensor_algebra.py  # 2 doctests failed
sage -t --long src/sage/algebras/letterplace/free_algebra_letterplace.pyx  # 3 doctests failed
sage -t --long src/sage/rings/laurent_series_ring.py  # 7 doctests failed
sage -t --long src/sage/combinat/sf/symplectic.py  # 1 doctest failed
sage -t --long src/sage/combinat/sf/orthogonal.py  # 1 doctest failed
sage -t --long src/sage/combinat/sf/multiplicative.py  # 1 doctest failed
sage -t --long src/sage/rings/polynomial/skew_polynomial_ring.py  # 2 doctests failed
sage -t --long src/sage/algebras/orlik_solomon.py  # 2 doctests failed
sage -t --long src/sage/algebras/weyl_algebra.py  # 1 doctest failed
sage -t --long src/sage/combinat/species/series.py  # 1 doctest failed
sage -t --long src/sage/combinat/combinatorial_algebra.py  # 2 doctests failed
sage -t --long src/sage/categories/algebras_with_basis.py  # 1 doctest failed
sage -t --long src/sage/categories/examples/hopf_algebras_with_basis.py  # 1 doctest failed
sage -t --long src/sage/algebras/free_algebra_quotient.py  # 1 doctest failed
sage -t --long src/sage/algebras/q_system.py  # 2 doctests failed
sage -t --long src/sage/symbolic/callable.py  # 1 doctest failed
sage -t --long src/sage/algebras/associated_graded.py  # 1 doctest failed
sage -t --long src/sage/categories/examples/filtered_algebras_with_basis.py  # 1 doctest failed
sage -t --long src/sage/categories/examples/finite_dimensional_algebras_with_basis.py  # 1 doctest failed
sage -t --long src/sage/categories/examples/lie_algebras_with_basis.py  # 1 doctest failed
sage -t --long src/sage/categories/examples/algebras_with_basis.py  # 1 doctest failed

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from cb2a1c3 to f6ee03a

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

431c27e	25277: _test_divides in Rings()
e09a5f3	25277: two better divides and one better _mod_
eb2ea8a	25277: doctests fix
f6ee03a	25277: skip _test_divides in the symbolic

[videlec]

comment:8

This ticket fixes several problem with the divides method

First of all, a custom one is implemented on zmod rings

sage: R = Zmod(6)
sage: R(4).divides(R(2))
Traceback (most recent call last):
...
ArithmeticError: reduction modulo 4 not defined

(see the relevant discussion on sage-devel).

Secondly, make divides return NotImplementedError always when not available.

Finally, test this with a test method.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

7682bc2	25277: _test_divides in CommutativeRings()
722a965	25277: two better divides and one better _mod_
a03f964	25277: doctests fix
765598f	25277: skip _test_divides in the symbolic

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f6ee03a to 765598f

[tscrim]

comment:11

In comment:6, is "that" referring to comment:3 or this extra test?

[videlec]

comment:12

"that" meant "the extra _test_divides" included in this ticket.

[videlec]

comment:13

But I managed to find a solution with the latest commits.

[tscrim]

comment:14

Thank you. Yep, I see the difference. So the only thing that I am unsure of are these sorts of doctest changes:

             sage: subspace.change_ring(CC)
-            Subspace of dimension 2 of ModularForms(n=6, k=20, ep=1) over Complex Field with 53 bits of precision
+            Traceback (most recent call last):
+            ...
+            NotImplementedError

I would prefer someone who understands this code to see if they agree with these changes or not.

[videlec]

comment:15

Replying to @tscrim:

Thank you. Yep, I see the difference. So the only thing that I am unsure of are these sorts of doctest changes:

             sage: subspace.change_ring(CC)
-            Subspace of dimension 2 of ModularForms(n=6, k=20, ep=1) over Complex Field with 53 bits of precision
+            Traceback (most recent call last):
+            ...
+            NotImplementedError

I would prefer someone who understands this code to see if they agree with these changes or not.

There is nowhere a modular form with coefficients in CC that is constructed. And for a good reason: it would be completely broken (because it does use the % operator). These tests have been written only to test the change_ring method.

[tscrim]

comment:16

Replying to @videlec:

There is nowhere a modular form with coefficients in CC that is constructed. And for a good reason: it would be completely broken (because it does use the % operator). These tests have been written only to test the change_ring method.

Thank you for the explanation. If they are bogus tests, then why not remove them altogether? I also am not sure I like the inconsistency with QQ:

sage: CC(2,1).divides(CC(1,2))
True
sage: QQ(1/2).divides(QQ(2))
True
sage: 2 % (1/2)
...
TypeError: no conversion of this rational to integer

(this was tested on vanilla).

[slel]

comment:17

What is the relation with #25278?

[videlec]

comment:18

I am happy removing the tests. Will do it.

divides is not intended to be compatible with % but with *. Whether % means "remainder of the division" is not universally true as (1/2) % 3 shows. And for (exact) fields a.divides(b) should always return True unless a is zero. I don't think it is meaningful at all for non exact rings.

What kind of consistency would you require with %? The fact that it is the default implementation of divides is kind of error prone.

[videlec]

comment:19

Replying to @slel:

What is the relation with #25278?

your comment?

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

4a6cbd7

25277: remove useless tests

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 765598f to 4a6cbd7

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:21

Replying to @videlec:

I am happy removing the tests. Will do it.

Thank you.

divides is not intended to be compatible with % but with *. Whether % means "remainder of the division" is not universally true as (1/2) % 3 shows. And for (exact) fields a.divides(b) should always return True unless a is zero. I don't think it is meaningful at all for non exact rings.

What kind of consistency would you require with %? The fact that it is the default implementation of divides is kind of error prone.

I was mostly trying to compare CC and QQ to better understand why it only still works for the latter. I am not sure I actually do since you said it was because the % operator is used. However, such tests also fail for QQ generically; a % b only works if b is an integer, in which case it treats a as in Zmod(b). I'm going to set a positive review because it does not make the QQ test any less artificial than before this ticket, but it doesn't seem like a good test from my (uneducated) perspective.

[videlec]

comment:22

Thanks for the review!

About %: #21745 and #21747

[vbraun]

Changed branch from u/vdelecroix/25277 to 4a6cbd7