Project

General

Profile

Design #377

IsDivisible -- exact semantics?

Added by John Abbott almost 11 years ago. Updated almost 10 years ago.

Status:
Closed
Priority:
Normal
Assignee:
Category:
Maths Bugs
Start date:
19 Jun 2013
Due date:
% Done:

100%

Estimated time:
3.00 h
Spent time:

Description

While dealing with issue #248 I realised that the exact semantics of IsDivisible are not clear.
The problem is when the ring contains zero-divisors.

Guideline: IsDivisible(a,b) gives true iff a/b will succeed

Let zd be a (non-zero) zero-divisor; let nzd be a non-zero-divisor:
- it is clear that IsDivisible(0,nzd) should produce true
- what should IsDivisible(0,zero(R)) produce?
- what should IsDivisible(0,zd) produce?
- what should IsDivisible(2*zd,zd) produce?

For concreteness, you can take the ring R = NewZZmod(6) and zd = 2 and nzd = 5

Comments?


Related issues

Related to CoCoALib - Feature #248: IsDivisible for RingElem with nice interfaceClosed2012-10-01

Related to CoCoALib - Design #1500: IsDivisible in a field?Closed2020-10-05

History

#1 Updated by John Abbott almost 11 years ago

  • Status changed from New to In Progress
  • Assignee set to John Abbott

The problem with dividing 4/2 in ZZ/6 is that the true answer is 2 in ZZ/3 -- a different ring! The answer could be either 2 or 5 in ZZ/6.

(A) So we could say that 4 is divisible by 2, but when we perform the division we must choose one answer among many.

(B) Or we could say that 4 is not divisible by 2 because the answer is not unique in that ring.

Consequences:

(C) If we adopt approach (A) then presumably we must also say that 0 is divisible by 0; but that implies that one can compute 0/0 and expect to get an answer...

(D) If we adopt approach (B) then IsDivisible(0,zd) should always give false (because the answer is not unique: it could be 0 or any cofactor of zd).

At the moment I favour approach (B).

#2 Updated by John Abbott almost 11 years ago

  • % Done changed from 0 to 10

JAA continues to believe that attempting to compute 0/0 in any ring should give an error. Giving an answer is almost surely going to lead to a nasty surprise sooner or later.

This reinforces my preference for design decision (B).

#3 Updated by Anna Maria Bigatti over 10 years ago

  • Target version changed from CoCoALib-0.99534 Seoul14 to CoCoALib-0.99532

#4 Updated by Anna Maria Bigatti almost 10 years ago

  • Target version changed from CoCoALib-0.99532 to CoCoALib-0.99533 Easter14

#5 Updated by John Abbott almost 10 years ago

  • % Done changed from 10 to 30

Summarising:
IsDivisible(a,b) gives true iff there is a unique c in the ring satisfying a = b*c (assuming ring is commutative). This implies that a/b is well-defined (and so ought to be computable).

As Anna said: this fits in well with CoCoA's "pragmatic philosphy".

Nevertheless the documentation should point out the pecularities of IsDivisible in CoCoA.

Note that IsDivisible throws ERR::DivByZero if b=0; we chose this behaviour because we think that testing for divisibility by 0 is more likely a consequence of a programming error than an intended test.

Note that IsDivisible apparently always gives false if the 2nd arg is a non-zero zero-divisor (agreeing with condition that the quotient be unique).

Action: check & correct documentation, check & correct implementations!

#6 Updated by John Abbott almost 10 years ago

  • % Done changed from 30 to 50

Aldo says that "a is divisible by b" means that there exists at least one c such that a = b*c. He accepted happily that this means that 0 is divisible by 0; this is, of course, quite unacceptable for CoCoA (because 0/0 will cause an error; it'd be too "dangerous" to give a result).

After some discussion the proposal is:
  • if b is a zero-divisor then give error (ERR::DivByZero)
  • otherwise return true or false appropriately

I observe that in comment-5 we had proposed error for b=0 but not for other zero-divisors; this is somewhat inconsistent! The proposal in this comment is more consistent.

#7 Updated by John Abbott almost 10 years ago

  • Status changed from In Progress to Feedback
  • % Done changed from 50 to 90

Implemented the proposal in comment-6; changed several IsZero checks into IsZeroDivisor.

Changed state to feedback

#8 Updated by John Abbott almost 10 years ago

  • Status changed from Feedback to Closed
  • % Done changed from 90 to 100

#9 Updated by Anna Maria Bigatti almost 10 years ago

  • Estimated time set to 3.00 h

#10 Updated by John Abbott over 3 years ago

Also available in: Atom PDF