division in Zmod(6)

[Vincent Delecroix]

Dear all,

How should be defined division in non-integral domains like Zmod(6)? The
following looks a bit incoherent to me

sage: Z6 = Zmod(6)
sage: a = Z6(4)
sage: b = Z6(2)
sage: b.divides(a)
True
sage: a // b
Traceback (most recent call last):
...
ZeroDivisionError: Inverse does not exist.

The reason for the ZeroDivisionError is because the algorithm tries
to invert b and perform a multiplication.

Reading [wiki] the division is well defined when it is unique. So
raising an error seems appropriate. But I would like to ask what
is the most appropriate

1. do not change anything

2. raise a more meaningful error (eg an ArithmeticError or
ValueError with better message)

3. return an actual quotient

I would vote for 2 and add a method to obtain one quotient or all
possible quotients.

Best
Vincent

[wiki]
https://en.wikipedia.org/wiki/Division_(mathematics)#Abstract_algebra


PS: Maple somehow agrees with [wiki] as it does not define division in
Zmod(6)

> with(Domains);
> show(Zmod(6), operations);

` Signatures for constructor Zmod`
` note: operations prefixed by -- are not available`

` * : (Zmod,Zmod*) -> Zmod`
` * : (Integers,Zmod) -> Zmod`
` + : (Zmod,Zmod*) -> Zmod`
` - : Zmod -> Zmod`
` - : (Zmod,Zmod) -> Zmod`
` 0 : Zmod`
` 1 : Zmod`
` <> : (Zmod,Zmod) -> Boolean`
` = : (Zmod,Zmod) -> Boolean`
` -- Characteristic : Integers`
` Coerce : Integers -> Zmod`
` Index : Integers -> Zmod`
` Input : Expression -> Union(Zmod,FAIL)`
` Inv : Zmod -> Union(Zmod,FAIL)`
` Lookup : Zmod -> Integers`
` Output : Zmod -> Expression`
` Random : () -> Zmod`
` Size : Integers`
` Type : Expression -> Boolean`
` Universe : () -> Zmod*`
` ^ : (Zmod,Integers) -> Zmod`

PPS: people with access to magma are welcome to report!

[Nils Bruin]

On Tuesday, May 1, 2018 at 9:10:27 AM UTC-7, vdelecroix wrote:

Dear all,

How should be defined division in non-integral domains like Zmod(6)? The
following looks a bit incoherent to me

PPS: people with access to magma are welcome to report!

Magma complains about division by a non-unit. It does allow "div", but it also allows 5 div 2 in ZZ/6.

I think the problem for "/" is division by a zero-divisor. Otherwise an answer can be returned in a structure where an inverse has been adjoined.

The ZeroDivisionError is therefore spot-on, if you read it as an abbreviation of ZeroDivisorDivisionError. Using non-unit as abbreviation for zero-divisor in Z/nZ is pretty common too. I don't think a change is necessary.

[Vincent Delecroix]

But there is still something missing in Sage: how do I compute all
possible "quotients" of 5 by 2 in Zmod(6) in my Sage console other than

sage: R = Zmod(6)
sage: a = R(5)
sage: b = R(2)
sage: [c for c in R if c*b == a]
[2, 5]

Vincent

[David Roe]

Such a function would be reasonable to implement, though note that the actual answer in your example is [], not [2, 5].

I agree with Nils that the ZeroDivisionError is correct.  If there's something to be fixed, it's the divides function, which is currently using a generic implementation from element.pyx that falls back on testing whether a % b == 0.  Indeed:

sage: R = Zmod(6)
sage: R(2).divides(R(4))
True
sage: R(4).divides(R(2))
ArithmeticError: reduction modulo 4 not defined

David

Vincent

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscribe@googlegroups.com.
To post to this group, send email to sage-...@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[Vincent Delecroix]

I interverted 5 and 4... my bad. I opened

https://trac.sagemath.org/ticket/25278

> I agree with Nils that the ZeroDivisionError is correct. If there's
> something to be fixed, it's the divides function, which is currently using
> a generic implementation from element.pyx that falls back on testing
> whether a % b == 0. Indeed:
>
> sage: R = Zmod(6)
> sage: R(2).divides(R(4))
> True
> sage: R(4).divides(R(2))
> ArithmeticError: reduction modulo 4 not defined

Indeed

https://trac.sagemath.org/ticket/25277

Vincent

[Samuel Lelievre]

For comparison, Nemo gives an error.

    $ julia

                   _

       _       _ _(_)_     |  A fresh approach to technical computing

      (_)     | (_) (_)    |  Documentation: https://docs.julialang.org

       _ _   _| |_  __ _   |  Type "?help" for help.

      | | | | | | |/ _` |  |

      | | |_| | | | (_| |  |  Version 0.6.2 (2017-12-13 18:08 UTC)

     _/ |\__'_|_|_|\__'_|  |  Official http://julialang.org/ release

    |__/                   |  x86_64-pc-linux-gnu

     

    julia> using Nemo

     

    Welcome to Nemo version 0.7.3

     

    Nemo comes with absolutely no warranty whatsoever

     

     

    julia> R = ResidueRing(ZZ, 6)

    Integers modulo 6

     

    julia> a = R(5)

    5

     

    julia> b = R(4)

    4

     

    julia> c = a * b

    2

     

    julia> c / a

    ERROR: MethodError: no method matching /(::Nemo.nmod, ::Nemo.nmod)

     

    julia> c / b

    ERROR: MethodError: no method matching /(::Nemo.nmod, ::Nemo.nmod)

     

    julia>  

[William Stein]

And just for fun, a Jupyter notebook version (just curious if this
would "just work", and it does):

https://cocalc.com/share/4a5f0542-5873-4eed-a85c-a18c706e8bcd/support/2018-05-02-nemo.ipynb?viewer=share

> --
> You received this message because you are subscribed to the Google Groups
> "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an

> email to sage-devel+...@googlegroups.com.

> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

--
William (http://wstein.org)

[Samuel Lelièvre]

Oh, I also had shared a Jupyter Notebook version, but forgot

to post the link:

https://cocalc.com/share/fc94de41-6af4-4ee1-a684-c33a9e56b2b0/nemo-zmod-division.ipynb?viewer=share

​

[Bill Hart]

In Julia and Nemo, the slash operator is floating point division. For example, 1/2 is 0.5 not a half. For division in a ring, you want divexact (there is also a separate operator, div, for Euclidean division).

At the moment, the code in Nemo for this is actually incorrect, so it only gives you an answer in one of the two examples in this thread and an exception in the other case. It's not a difficult fix. It should be in the next version of Nemo.

In AbstractAlgebra (pure Julia, no Flint), we get:

julia> using AbstractAlgebra

Welcome to AbstractAlgebra version 0.0.6

AbstractAlgebra comes with absolutely no warranty whatsoever

julia> R = ResidueRing(ZZ, 6)

Residue ring of Integers modulo 6

julia> a = R(5)

5

julia> b = R(4)

4

julia> c = a*b

2

julia> divexact(c, a)

4

julia> divexact(c, b)

2

[Bill Hart]

Correction: the corresponding issue in the Nemo.jl project will be fixed in Nemo 0.8.4, not the next release 0.8.3, which apparently has already been tagged and is already in the Julia METADATA queue. We will of course tag 0.8.4 as soon as 0.8.3 clears the queue. The issue has been fixed in Nemo/master today, of course.

Thanks Samuel and William for trying this out in our project. It's nice when this sort of cross-comparison happens and shakes loose more bugs. In this case the code to deal with this was there in Nemo.jl, but had a typo, and the test code restricted to the easy case (because that is all the old code handled).

(We also took the opportunity to replace the implementation with a simpler faster one.)

[Johan Bosman]

Of course, the quotient is well defined as an element of Z/3Z.