shifting issue in padic _set_from_list functions

Question

shifting issue in padic _set_from_list functions

Closed this issue 4 years ago · 23 comments

Using version 9.1 of sage, the function _set_from_list_both(), implemented in: /sage/src/sage/rings/padics/padic_ZZ_pX_element.pyx, crashes or returns wrong results for some inputs.

Example for wrong results:

sage: T.<a> = Qp(5).extension(x^2-5)
sage: W.<w> = Qp(5).extension(x^2-5)
sage: W(a^-41)
O(w^-1)

Example for a crash (full output is availabale in the attached file):

sage: T.<a> = Qp(5).extension(x^2-5)
sage: T([5^-2], absprec=-1)
------------------------------------------------------------------------
/home/noa/workspace/padic_project/sage/local/lib/python3.7/site-packages/cysignals/signals.cpython-37m-x86_64-linux-gnu.so(+0x828b)[0x7f250e49428b]
/home/noa/workspace/padic_project/sage/local/lib/python3.7/site-packages/cysignals/signals.cpython-37m-x86_64-linux-gnu.so(+0x8348)[0x7f250e494348]
/home/noa/workspace/padic_project/sage/local/lib/python3.7/site-packages/cysignals/signals.cpython-37m-x86_64-linux-gnu.so(+0xb323)[0x7f250e497323]
/lib/x86_64-linux-gnu/libc.so.6(+0x3ef20)[0x7f251cc46f20]
/home/noa/workspace/padic_project/sage/local/lib/python3.7/site-packages/sage/rings/padics/padic_ZZ_pX_CR_element.cpython-37m-x86_64-linux-gnu.so(+0x34d62)[0x7f2455837d62]
/home/noa/workspace/padic_project/sage/local/lib/python3.7/site-packages/sage/rings/padics/padic_ZZ_pX_element.cpython-37m-x86_64-linux-gnu.so(+0x1f27d)[0x7f2455c9027d]
/home/noa/workspace/padic_project/sage/local/lib/python3.7/site-packages/sage/rings/padics/padic_ZZ_pX_CR_element.cpython-37m-x86_64-linux-gnu.so(+0x2fee9)[0x7f2455832ee9]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(+0x105972)[0x7f251d0fe972]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(PyObject_Call+0x68)[0x7f251d096538]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyEval_EvalFrameDefault+0x4fc5)[0x7f251d067d65]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyEval_EvalCodeWithName+0xa81)[0x7f251d181af1]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyFunction_FastCallDict+0x14a)[0x7f251d093cda]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyObject_Call_Prepend+0xcc)[0x7f251d094ecc]
/home/noa/workspace/padic_project/sage/local/lib/python3.7/site-packages/sage/structure/coerce_maps.cpython-37m-x86_64-linux-gnu.so(+0x7c7c)[0x7f25074c2c7c]
/home/noa/workspace/padic_project/sage/local/lib/python3.7/site-packages/sage/structure/coerce_maps.cpython-37m-x86_64-linux-gnu.so(+0x13bec)[0x7f25074cebec]
/home/noa/workspace/padic_project/sage/local/lib/python3.7/site-packages/sage/structure/parent.cpython-37m-x86_64-linux-gnu.so(+0x1dfa9)[0x7f250d533fa9]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyObject_FastCallKeywords+0xc3)[0x7f251d094503]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyEval_EvalFrameDefault+0x5132)[0x7f251d067ed2]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyEval_EvalCodeWithName+0xa81)[0x7f251d181af1]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(PyEval_EvalCodeEx+0x3e)[0x7f251d181bde]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(PyEval_EvalCode+0x1b)[0x7f251d181c0b]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(+0x185e4d)[0x7f251d17ee4d]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyMethodDef_RawFastCallKeywords+0x23d)[0x7f251d09433d]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyCFunction_FastCallKeywords+0x25)[0x7f251d094425]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyEval_EvalFrameDefault+0x8ffe)[0x7f251d06bd9e]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyEval_EvalCodeWithName+0xa81)[0x7f251d181af1]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyFunction_FastCallKeywords+0x8f)[0x7f251d093eef]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyEval_EvalFrameDefault+0x7219)[0x7f251d069fb9]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyEval_EvalCodeWithName+0xa81)[0x7f251d181af1]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyFunction_FastCallKeywords+0x8f)[0x7f251d093eef]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyEval_EvalFrameDefault+0x6cae)[0x7f251d069a4e]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyEval_EvalCodeWithName+0xa81)[0x7f251d181af1]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyFunction_FastCallKeywords+0x8f)[0x7f251d093eef]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyEval_EvalFrameDefault+0x6cae)[0x7f251d069a4e]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyEval_EvalCodeWithName+0xa81)[0x7f251d181af1]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyFunction_FastCallKeywords+0x8f)[0x7f251d093eef]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyEval_EvalFrameDefault+0x7219)[0x7f251d069fb9]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyEval_EvalCodeWithName+0xa81)[0x7f251d181af1]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyFunction_FastCallKeywords+0x8f)[0x7f251d093eef]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyEval_EvalFrameDefault+0x7219)[0x7f251d069fb9]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(+0x68c8f)[0x7f251d061c8f]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyEval_EvalFrameDefault+0x7219)[0x7f251d069fb9]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_PyEval_EvalCodeWithName+0xa81)[0x7f251d181af1]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(PyEval_EvalCodeEx+0x3e)[0x7f251d181bde]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(PyEval_EvalCode+0x1b)[0x7f251d181c0b]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(PyRun_FileExFlags+0xaa)[0x7f251d1b6f3a]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(PyRun_SimpleFileExFlags+0xfd)[0x7f251d1b70ad]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(+0x1e25e0)[0x7f251d1db5e0]
/home/noa/workspace/padic_project/sage/local/lib/libpython3.7m.so.1.0(_Py_UnixMain+0x49)[0x7f251d1db859]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xe7)[0x7f251cc29b97]
/home/noa/workspace/padic_project/sage/local/bin/python3(_start+0x2a)[0x558e97ef478a]
------------------------------------------------------------------------

The bug occurs because the element is set to the desirable absolute precision before it is shifted by p^min_val.

To fix this, I subtracted (min_val * ramification-index) from the absolute precision to which the element is set, so that after shifting it will hopefully reach the desirable precision.

However, this does not completely solve the problem, because in case p is not a power of the uniformizer, shifting doesn't necessarily increase the absolute precision by exactly (min_val * ramification-index). So perhaps it would be best to set the absolute precision to the desirable value, only after the shifting (I didn't figure out how to do this correctly).

However, if it isn't necessary to have the exact desirable precision, the above solution could be enough.

The issue of shifting after setting the precision, is also relevant to _set_from_list_abs(), which I changed similarly.

Note: The first example given in this ticket requires fixing not only this bug, but also tickets #29925, #29926. After those bugs are all fixed, we get the result: w^-41 + O(w^-2).

CC: @xcaruso @roed314

Component: padics

Keywords: precision, set_from_list, shifting

Author: Noa Viner

Branch/Commit: a97b2a6

Reviewer: Julian Rüth

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

Answer 1 · 2020-06-21T21:05:49.000Z

Attachment: set_from_list_both_crash_log.gz

Answer 2 · 2020-06-21T23:49:58.000Z

Branch: u/gh-n-vi/shifting_issue_in_padic__set_from_list_functions

Answer 3 · 2020-06-22T00:01:52.000Z

Commit: 34df5e2

Answer 4 · 2020-06-22T00:01:52.000Z

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-Using version 9.1 of sage, the function _set_from_list_both(), which is written in the file: /sage/src/sage/rings/padics/padic_ZZ_pX_element.pyx, crashes or returns wrong results for some inputs.
+Using version 9.1 of sage, the function _set_from_list_both(), implemented in: /sage/src/sage/rings/padics/padic_ZZ_pX_element.pyx, crashes or returns wrong results for some inputs.
 
 Example for wrong results:
 
@@ -8,7 +8,7 @@
 sage: W(a^-41)
 O(w^-1)
 ```
-Example for a crash (see full output in attached file):
+Example for a crash (full output is availabale in the attached file):
 
 ```
 sage: T.<a> = Qp(5).extension(x^2-5)
@@ -72,8 +72,10 @@
 
 To fix this, I subtracted (min_val * ramification-index) from the absolute precision to which the element is set, so that **after** shifting it will hopefully reach the desirable precision.
 
-However, this does not completely solve the problem, because in case p is not a power of the uniformizer, it's not necessary that shifting increases the absolute precision in exactly (min_val * ramification-index). So perhaps it would be best to set the absolute precision to the desirable value, only **after** the shifting (I didn't figure out how to do this correctly).
+However, this does not completely solve the problem, because in case p is not a power of the uniformizer, shifting doesn't necessarily increase the absolute precision by exactly (min_val * ramification-index). So perhaps it would be best to set the absolute precision to the desirable value, only **after** the shifting (I didn't figure out how to do this correctly).
 
 However, if it isn't necessary to have the exact desirable precision, the above solution could be enough.
 
-Note: The issue of shifting after setting the precision, is also relevant for _set_from_list_abs(), which I changed similarly.
+The issue of shifting after setting the precision, is also relevant to _set_from_list_abs(), which I changed similarly.
+
+Note: The first example given in this ticket requires fixing not only this bug, but also tickets #29925, #29926. After those bugs are all fixed, we get the result: w<sup>-41</sup> + O(w<sup>-2</sup>).

Answer 5 · 2020-06-22T00:01:52.000Z

New commits:

`34df5e2`	`Fix precision in shifting`

Answer 6 · 2020-09-08T10:07:09.000Z

comment:3

this looks simple enough, but needs people that know the padics code

Answer 7 · 2020-09-08T15:43:24.000Z

comment:4

gh-n-vi: I don't know a better way of contacting you. So, we're meeting every Thursday 3pm US/Eastern = 9pm CEST on Zulip (and then maybe in Zoom.) Feel free to join us if you want to discuss p-adics :)
https://zulip.sagemath.org/#narrow/stream/15-padics

Answer 8 · 2020-09-08T19:38:28.000Z

comment:5

Replying to @saraedum:

gh-n-vi: I don't know a better way of contacting you. So, we're meeting every Thursday 3pm US/Eastern = 9pm CEST on Zulip (and then maybe in Zoom.) Feel free to join us if you want to discuss p-adics :)
https://zulip.sagemath.org/#narrow/stream/15-padics

Thanks saraedum, I would be glad to join the discussion!

Answer 9 · 2020-09-17T23:09:41.000Z

comment:6

Would you mind adding the first example to the doctests as well? (I read that it did not work originally, but it should now, right?)

Answer 10 · 2020-09-17T23:31:36.000Z

Reviewer: Julian Rüth

Answer 11 · 2020-09-17T23:31:36.000Z

comment:7

However, this does not completely solve the problem, because in case p is not a power of the uniformizer, shifting doesn't necessarily increase the absolute precision by exactly (min_val * ramification-index).

True. It's been a while since I looked at this. But isn't it at most off by one?

Is this correct when min_val is positive?

self._set_from_ZZ_pX_abs(&(<ntl_ZZ_pX>ntl_ZZ_pX(L, ctx)).x, ctx, absprec - (min_val * self.parent().e()))

When min_val is large, wouldn't x be 0 modulo the precision then?

It seems to me that you have to do the shift (probably depending on the sign of min_val) and then reduce the precision to absprec explicitly again for this to be really correct. Is that what you tried originally? Feel free to ask on Zulip if you are not sure how to do this.

Answer 12 · 2020-09-21T17:50:06.000Z

Changed commit from 34df5e2 to 41856e4

Answer 13 · 2020-09-21T17:50:06.000Z

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

`41856e4`	`Add first doctest`

Answer 14 · 2020-09-21T18:10:41.000Z

comment:9

Hi Julian, thank you for the review!

I have added the first example as you suggested.
Regarding the question of the increase in the absolute-precision when shifting by p^min_val :
Rethinking about the subject, it seems to me that perhaps the absolute-precision is actually increased by exactly (min_val * ramification-index).
Here is a proof (if anything in the process is wrong, I will appreciate any corrections!):
Denote the original number by x, the uniformizer by u, the ramification index by e, and min_val by n.

The valuation of p always equals e. Therefore the valuation of pⁿ is en.
Denote: pⁿ = a0(u^en) + a1(u^en+1) + a2(u^e*n+2) +...
xpⁿ = (xa0*(u^en)) + (xa1*(u^en+1)) + (xa2*(u^e*n+2)) +...
The absolute-precision of x*pⁿ equals the absolute-precision of the element which has the lowest absolute-precision among those in the sum.
For each i>=0, (xai(u^en+i)).absolute_precision() = x.absolute_precision() + en+i.
1. and 4. imply that: (xpⁿ).absolute_precision() = (xa0*(u^en)).absolute_precision() = x.absolute_precision() + en.
  Therefore, the absolute-precision has indeed been increased by exactly e*n.

Correctness in case min_val is positive:
Denote the valuation of x by v, and: x = a0*(u^v) + a1*(u^v+1) + ...
If the i-th element in this sum is truncated when setting the precision of x to (absprec - (min_val * e)), it means that i >= (absprec - (min_val * e)).
Now, I claim that this element would also be truncated if we set the precision after the shifting. Let's assume for simplicity that p is a power of the uniformizer: p=u^e, which implies that: p^min_val=u^min_vale.
We need to shift x by p^min_val and then truncate its precision to absprec.
So the i-th element is shifted by min_vale entries, and now equals: ai*(u^v+i+min_vale).
Now we set the result (xp^min_val) to precision absprec. We assumed that i >= (absprec - (min_val * e)). Therefore i+min_vale >= absprec, which implies that this element (ai(u^{v+i+min_val*e})) is truncated.
Therefore I think that if min_val is large enough so that x is 0 modolu (absprec - (min_val * e)), it is O.K because x would be truncated either way. Am I right in this deduction?
The problem I had with changing the precision after the shifting, is that I don't know how to increase precision of elements (the only method I found to be relevant is lift_to_precision, but it does not guarantee that the new entries that are added to the element are zero-entries). So if I wanted to do this, I would have to make sure that the precision needs to be decreased rather than increased.

Answer 15 · 2021-03-24T02:04:25.000Z

comment:12

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.

Answer 16 · 2021-05-03T22:58:39.000Z

comment:13

Therefore I think that if min_val is large enough so that x is 0 modolu (absprec - (min_val * e)), it is O.K because x would be truncated either way. Am I right in this deduction?

It was my understanding that this code also used for capped-relative p-adics? In that case I don't think that this is correct.

Answer 17 · 2021-07-19T00:44:56.000Z

comment:15

Setting a new milestone for this ticket based on a cursory review.

Answer 18 · 2022-02-01T10:17:19.000Z

comment:17

Replying to @saraedum:

It was my understanding that this code also used for capped-relative p-adics? In that case I don't think that this is correct.

Hi Julian!
Sorry about the very-long-delay in answering your comment.

Can you please explain, or give an example, why there should be a problem with the capped-relative case? I tried to think about it but didn't manage to figure out myself.

Thank you!

Answer 19 · 2022-02-23T06:19:59.000Z

Changed branch from u/gh-n-vi/shifting_issue_in_padic__set_from_list_functions to u/saraedum/shifting_issue_in_padic__set_from_list_functions

Answer 20 · 2022-02-23T06:22:20.000Z

Changed commit from 41856e4 to a97b2a6

Answer 21 · 2022-02-23T06:22:20.000Z

comment:19

I made some minor modifications to the documentation. If these look good to you, feel free to set this to positive review.

Sorry, for getting you wrong the first time and delaying this forever in doing so. The relprec in the docstring confused me when it should have been absprec.

New commits:

`c76d35e`	`Merge remote-tracking branch 'trac/develop' into HEAD`
`4203fd1`	`Merge remote-tracking branch 'trac/develop' into HEAD`
`a97b2a6`	`Improve set_from_list documentation`

Answer 22 · 2022-02-23T06:47:52.000Z

comment:20

This is great, thank you Julian! The documentation was indeed misleading here...

Answer 23 · 2022-02-27T22:00:52.000Z

Changed branch from u/saraedum/shifting_issue_in_padic__set_from_list_functions to a97b2a6