Change behavior of the % operator for p-adic integral elements

[roed314]

In padic_generic_element.pyx, the documentation for _mod_ describes two options for implementing a%b and a//b.

(2) If b = pi^k, the series expansion (in terms of pi) of a//b is just the series expansion of a, shifted over by k terms.

(2') The series expansion of a % pi^k has no terms above pi^(k-1).

The conditions (2) and (2') are equivalent. But when we generalize these conditions to arbitrary b they diverge.

(3) For general b, the series expansion of a//b is just the series expansion of a/b, truncating terms with negative exponents of pi.

(4) For general b, the series expansion of a%b has no terms above b.valuation() - 1.

In order to satisfy (3), one defines

a // b = (a / b.unit_part()) >> b.valuation()
a % b = a - (a // b) * b

In order to satisfy (4), one defines

a % b = a.lift() % pi.lift()^b.valuation()
a // b = ((a - a % b) >> b.valuation()) / b.unit_part()

Currently, Sage implements option (3). The justification given is that "it is more easily defined in terms of shifting and thus generalizes more easily to extension rings."

On the other hand, (4) behaves better in terms of precision: the remainder in the definition (4) is always known with the maximal precision (and actually to infinite precision) while in (3) we are loosing precision for the quotient and the remainder at the same
time.

On a related note, when using definition (4), if u has valuation 0 then

a % (bu) = a % b
a // (bu) = (a // b) * u^(-1)

There is no corresponding simple relations if we are using definition (3).

In this ticket, we implement behavior (4) as an option and provide deprecation messages for behavior (3).

CC: @xcaruso @saraedum

Component: padics

Keywords: padicIMA

Author: David Roe

Branch/Commit: 162b44d

Reviewer: Xavier Caruso

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

[xcaruso]

comment:1

Is there some code available somewhere?

[roed314]

comment:2

I don't think I have any code for this.

[roed314]

Changed keywords from none to padicIMA

[roed314]

Branch: u/roed/quo_rem_revision

[sagetrac-git]

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

fda8a55

Remove some lines that should be in 23218

[sagetrac-git]

Commit: fda8a55

[roed314]

Reviewer: Xavier Caruso

[roed314]

Author: David Roe

[roed314]

comment:6

All tests pass, but should still wait for remainder of patchbot report.

[sagetrac-git]

Changed commit from fda8a55 to 2975633

[sagetrac-git]

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

2975633

Add _quo_rem to lattice precision

[xcaruso]

Changed branch from u/roed/quo_rem_revision to u/caruso/quo_rem_revision

[xcaruso]

Changed commit from 2975633 to 9340a8a

[xcaruso]

comment:9

Looks good to me (after my update).
Positive review if the patchbot is happy (but it probably won't...)

---

New commits:

634c8b8	Fix an issue with precision
450d11b	Add a generic implementation of quo_rem
9340a8a	Fix a corner case

[roed314]

Changed branch from u/caruso/quo_rem_revision to u/roed/quo_rem_revision

[sagetrac-git]

Changed commit from 9340a8a to c0da7de

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

c0da7de

Update documentation

[sagetrac-git]

Changed commit from c0da7de to c8ae6a7

[sagetrac-git]

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

c8ae6a7

Move the generic implementation of _quo_rem back from 23218

[sagetrac-git]

Changed commit from c8ae6a7 to 162b44d

[sagetrac-git]

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

634c8b8	Fix an issue with precision
450d11b	Add a generic implementation of quo_rem
9340a8a	Fix a corner case
cabb63e	Merge branch 'u/caruso/quo_rem_revision' of git://trac.sagemath.org/sage into t/21994/quo_rem_revision
9662550	Merge branch 'u/roed/quo_rem_revision' of git://trac.sagemath.org/sage into t/21994/quo_rem_revision
162b44d	Fixing doctests, bad argument in floordiv

[xcaruso]

comment:15

I think that the variables powhelper_oneunit, etc. aren't used in this ticket. (Probably they are in #23218.)

[xcaruso]

comment:16

Patchbot is happy. I give a positive review to this ticket.

[vbraun]

Changed branch from u/roed/quo_rem_revision to 162b44d