We have to fix div, rem, divrem, mod throughout our packages

[wbhart]

In Julia, div, rem and divrem are a triple of functions that return q, r such that

a = qb + r

I have opened a PR to make our mod agree with Julia. The problem is, our div, divrem and rem already agree with Julia.

This is fine, except that absolutely everywhere else, div, mod and divrem are the functions for Euclidean division that return values q, r such that

a = qb + r

This is obviously no good for generic code, since this causes incorrect results and inconsistency even if we restrict to positive modulus:

mod(-2, 3) = 1
rem(-2, 3) = -2

We have to do one of the following two things:

1. make div, rem and divrem the functions for Euclidean division, throughout Oscar
2. introduce functions quo, mod and quomod and use those for Euclidean division throughout Oscar

I'm not sure I like 1 because that implies there is not a set of n fixed residues mod n. The Julia people already made this decision for us, and it's not the decision we want.

This all sucks quite a lot, but I see no other way around it.

[wbhart]

Also, note that this has absolutely nothing to do with symmetric mod vs mod, nor does it have anything to do with getting unique answers from hnf. Both of those are distinct problems dealt with in another way.

[wbhart]

@fieker @rfourquet @thofma

[wbhart]

An independent issue that we should think about is whether or not we want mod(2, -3) to return a positive result. If so, we'd have to call it something else.

Probably this is irrelevant and we can just suggest that the division algorithm for the integers actually doesn't work for negative divisor. Most likely no one will care.

[wbhart]

I have had a think about this over lunch and discussed with a few people. Here is what I now see as the only way forward.

Euclidean division should only guarantee what the Euclidean property guarantees, even for Z. This means no canonical set of representatives (neither mod nor rem provide such anyway).

div, rem and divrem should go together and should be defined for Z as per Julia (my PR #688 fixes this in Nemo).

Note that for Z rem returns a remainder with the same sign as the dividend.

Obviously div, rem and divrem should be the functions for Euclidean division throughout Oscar.

For people who want a nonnegative remainder over Z we define mod which returns a positive remainder if the modulus is positive.

The upshot of this is that we need to change mod everywhere (except Z) to rem, throughout all our packages, since this is the only one (of mod and rem) that will be defined for all Euclidean domains.

This means we will be able to have consistent generic code for Euclidean domains.

Hopefully @fieker will like this, as rem and % are synonymous. So % will now be Euclidean remainder.

I will now document Oscar as though this has been fixed everywhere. I don't intend to implement it myself anywhere, so if someone wants to volunteer that would be helpful.

[wbhart]

This ticket is invalid. If we use div, rem and divrem everywhere for Euclidean division we will get non-unique representatives in HNF and ResidueRing/ResidueField and the results will disagree with Flint.

We must continue to use mod and our hacked versions of div and divrem everywhere. We are just going to have to explain this to users of Oscar and put up with endless tickets and revert wars in the distant future between developers who think it should be "fixed".

[fieker]

On Tue, Jun 09, 2020 at 12:47:17AM -0700, wbhart wrote: This ticket is invalid. If we use div, rem and divrem everywhere for Euclidean division we will get non-unique representatives in HNF and ResidueRing/ResidueField and the results will disagree with Flint. We must continue to use mod and our hacked versions of div and divrem everywhere. We are just going to have to explain this to users of Oscar and put up with endless tickets and revert wars in the distant future between developers who think it should be "fixed". -- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: #699 (comment)

Option 105: where uniqness is required, add a unique_mod function

[wbhart]

Where is uniqueness required? There's no consistent answer to this.

You can't have some generic Euclidean functions use one definition of divrem and others use another. Eventually someone will combine them and get nonsense.

[wbhart]

There is another problem of course: our ResidueRing code currently assumes reduction mod n always gives a unique set of residues. For rings where this is not the case, the current code will tell you two different representatives of the same value mod n are not equal. It's quite the performance problem to fix this, not to mention that you can't use rem or mod for it, because as we said, there are non-equal representatives and rem and mod won't fix that.

We can't rely on there always being a unique representative either. So unique_mod wouldn't help with that problem.

If we want to be serious about Euclidean domains with non-unique choice of representatives, we are going to have to cripple the performance of our current generic code and do a subtraction and divisibility test instead of an equality test. Happy days.

[fieker]

OK, trying my 2 pennies. There are a complete mixture of problems hidden here

• in mathematics, in contrast to CS and programming, "mod" is actually not a function - and not used as such. "mod" is an argument to a comparison, (a = b mod c is defined as c | a-b or a-b in ). Similarly, ab = 1 mod c does not define an element in R, but identifies a class of elements
• our implementation assumes properties that are not coming from maths, like the unique, positive, remainder
• the problems with comparison could be adressed by checking (a-b) % c == 0 which might be guaranteed everywhere - or by isdivisible(a-b, c) where mathematics would reign
• in most algorithms (that I have implemented) the uniqueness is internally only "required" in comparison, otherwise, "mod" is used to make intermediate results small, thus for performence, in fact, whenever I need uniqueness, I ensure it by selecting signs, lifts, ...
• I am not sure that using rem or mod is the best (fastest) way of doing arithmetic either. If we assume that on input we have normalised pos. residues, then at most we need to add or subtract n to make sums and differences work. Prod has no sign issues then
• so far, to me, I have yet to see a case where comparison is critical for speed. It might spill over into hashing though
• I am not sure how gneric we can (or want to) make this. Is it clear that even on the euclidean side we can (and want) to insisit on unique reps? Looking at quotients of (maximal) orders, I can make them either unique or small, both options have merit
• the doc in AA talks about "the" euclidean division - which is also not part of maths - or not stated there

[wbhart]

Oops, forgot to press send on this, which I wrote earlier:

Unlike mathematics, which is not done on a computer, a computer algebra system is done on a computer, and there mod is a function which has to return a particular result.

You cannot rely on our developers to assume that the output of Euclidean division functions (over Z) is random so that they had better write their code defensively making the assumption that nothing can be taken for granted anywhere.

Developers will (and I thought I demonstrated that they have) at least made the assumption that the answers they get will be consistent!