Opened 14 years ago

Closed 12 years ago

#5759 closed defect (fixed)

bug in divides

Reported by: William Stein Owned by: William Stein
Priority: major Milestone: sage-4.6
Component: basic arithmetic Keywords:
Cc: Merged in: sage-4.6.alpha3
Authors: Luis Felipe Tabera Reviewers: John Cremona
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by kkilger)

The function "divides" does not work for generic commutative rings.

  1. it is not checked that the elements are in the same space, i.e.

Zmod(5)(1).divides(Zmod(2)(1)) is "True"

  1. No division by zero checking is done! This gives for example an error if you type

-> Zmod(2).zero_ideal() == Zmod(2).zero_ideal()

-> Zmod(2).zero_ideal() == Zmod(2).unit_ideal()

This patch should fix this. It may not be able to handle all cases but classes who need a more clever function should do their own implementation anyways.

Greetings, Kilian.

Attachments (3)

divides.patch (876 bytes) - added by kkilger 14 years ago.
5759-doctests.patch (699 bytes) - added by kkilger 14 years ago.
trac-5759.patch (3.2 KB) - added by Luis Felipe Tabera Alonso 12 years ago.

Download all attachments as: .zip

Change History (21)

Changed 14 years ago by kkilger

Attachment: divides.patch added

comment:1 Changed 14 years ago by kkilger

Description: modified (diff)
Priority: minormajor

comment:2 Changed 14 years ago by kkilger

Summary: bug in dividesbug in divides [with patch, needs review]

comment:3 Changed 14 years ago by kkilger

Description: modified (diff)

comment:4 Changed 14 years ago by kkilger

Description: modified (diff)

comment:5 Changed 14 years ago by kkilger

Description: modified (diff)

comment:6 Changed 14 years ago by kkilger

Owner: changed from somebody to William Stein

Changed 14 years ago by kkilger

Attachment: 5759-doctests.patch added

comment:7 Changed 14 years ago by kkilger

Summary: bug in divides [with patch, needs review][with patch, needs review] bug in divides

comment:8 Changed 14 years ago by William Stein

Summary: [with patch, needs review] bug in divides[with patch, needs work] bug in divides

This breaks a doctest somewhere else:

wstein@sage:~/build/sage-3.4.1.rc2$ ./sage -t  devel/sage/sage/coding/code_constructions.py
sage -t  "devel/sage/sage/coding/code_constructions.py"
**********************************************************************
File "/scratch/wstein/build/sage-3.4.1.rc2/devel/sage/sage/coding/code_constructions.py", line 530:
    sage: g.divides(f)
Exception raised:
    Traceback (most recent call last):
      File "/scratch/wstein/build/sage-3.4.1.rc2/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/scratch/wstein/build/sage-3.4.1.rc2/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/scratch/wstein/build/sage-3.4.1.rc2/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_7[6]>", line 1, in <module>
        g.divides(f)###line 530:
    sage: g.divides(f)
      File "element.pyx", line 1380, in sage.structure.element.CommutativeRingElement.divides (sage/structure/element.c:12436)
      File "parent_old.pyx", line 334, in sage.structure.parent_old.Parent._coerce_c (sage/structure/parent_old.c:5417)
      File "parent_old.pyx", line 336, in sage.structure.parent_old.Parent._coerce_c (sage/structure/parent_old.c:5186)
      File "parent.pyx", line 374, in sage.structure.parent.Parent.coerce (sage/structure/parent.c:4994)
    TypeError: no canonical coercion from Univariate Polynomial Ring in x over Finite Field in a of size 3^2 to Univariate Polynomial Ring in x over Finite Field of size 3
**********************************************************************
1 items had failures:
   1 of  14 in __main__.example_7
***Test Failed*** 1 failures.
For whitespace errors, see the file /scratch/wstein/build/sage-3.4.1.rc2/tmp/.doctest_code_constructions.py
         [4.2 s]
exit code: 1024

----------------------------------------------------------------------
The following tests failed:


        sage -t  "devel/sage/sage/coding/code_constructions.py"
Total time for all tests: 4.2 seconds

comment:9 Changed 14 years ago by kkilger

Summary: [with patch, needs work] bug in divides[with patch, needs work] class CommutativeRingElement

The whole divides function is broken (nearly irreparable) with the effect that "divides" failes or gives *wrong* answers if and only if the ring is no polynomial ring or ZZ (which have their own (buggy) implementation).

The reason is that not all commutative rings are euclidean domains and "modulo" operation does not do what it is supposed to do in general commutative rings, for example in finite integer rings: Zmod(12)(3) % Zmod(12)(4) gives Zmod(3)(0) (which is also broken, by the way).

The only correct behaviour would be:

  1. to raise a NotImplementedError? in element.py and let all subclasses implemenent their own divides.

or:

  1. define divides as "inclusion of ideals" and give errors if the subclasses can't check the inclusion of ideals.

Also: all doctests in element.py and other files are for polynomial rings only, with the effect that many functions in SAGE fail or give *wrong* answers if the ring is no polynomial ring.

Greetings, Kilian.

comment:10 Changed 14 years ago by kkilger

Summary: [with patch, needs work] class CommutativeRingElement[with patch, needs work] bug in divides

comment:11 Changed 13 years ago by John Cremona

I would have thought that even in this generality (element of a commutative ring) it would be worth adding the following special cases:

  1. if self=1 return True
  2. if x =0 return True; else if self =0 return False
  3. if self.is_unit() return True

where in each case the test is wrapped in a try/except block so that if (for example) self.is_unit() is not implemented then it just passes. Finally, if none of the above works then default to code as it is now.

Any individual ring where the x%self computation will not work but where there is an easy alternative direct test (such as in Integers(n)) can have their own specific implementations. If there is any support for this I'm willing to try to do it.

comment:12 Changed 13 years ago by John Cremona

Summary: [with patch, needs work] bug in divides[with patch, needs rebase] bug in divides

Note that #5347 (merged in 4.1.2.alpha2) fixes the easy cases I listed above. We still have

sage: Zmod(5)(1).divides(Zmod(2)(1))
True

but this looks fine to me:

sage: Zmod(2).zero_ideal() == Zmod(2).zero_ideal()
True
sage: Zmod(2).zero_ideal() == Zmod(2).unit_ideal()
False

Hence the patches here need to be rebased and simplified to cater for the first one.

comment:13 Changed 13 years ago by John Cremona

In fact the original patches can be discarded since they only fixed things that have been fixed anyway in #5347. What we do not have is a check the self and other are in "the same ring", which is not so obvious -- the simplest would be to throw an error if the parents were not identical, but that seems to harsh (it would cause 1.divides(1/2) to fail). Better would be to coerce into a common parent first -- the sort of thing which is done for __add___().

comment:14 Changed 13 years ago by Alex Ghitza

Report Upstream: N/A
Summary: [with patch, needs rebase] bug in dividesbug in divides

comment:15 Changed 12 years ago by Luis Felipe Tabera Alonso

Status: needs_workneeds_review

I add a patch to solve this problem. This patch is applied alone. Previous patches are discarded due to changes in the function during these months. See #5347

The algorithm first checks if parents coincide. If so, it runs the existing code. In other case, coerces both element to a common parent using the coercion model an runs the existing code on the coerced elements.

The patch works on 4.5.3

Changed 12 years ago by Luis Felipe Tabera Alonso

Attachment: trac-5759.patch added

comment:16 Changed 12 years ago by John Cremona

Status: needs_reviewpositive_review

The patch applies fine to 4.6.alpha1, and all test pass (I tested the whole sage library on account of earlier difficulties). No generic function can deliver everything, but this deals with simple generic cases, as the new doctests show.

comment:17 Changed 12 years ago by Mitesh Patel

Authors: Luis Felipe Tabera
Reviewers: John Cremona

comment:18 Changed 12 years ago by Mitesh Patel

Merged in: sage-4.6.alpha3
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.