#26195 closed enhancement (fixed)
Tate algebras
Reported by:  caruso  Owned by:  

Priority:  major  Milestone:  sage8.5 
Component:  padics  Keywords:  
Cc:  TristanVaccon, ghThibautVerron, caruso, roed  Merged in:  
Authors:  Xavier Caruso, Thibaut Verron  Reviewers:  David Roe 
Report Upstream:  N/A  Work issues:  
Branch:  4982c7e (Commits)  Commit:  
Dependencies:  #26479, #26575  Stopgaps: 
Description (last modified by )
This ticket implements Tate algebras over complete discrete valuation rings/fields, together with Gröbner bases for ideals in these algebras.
See the documentation of sage.rings.tate_algebra
for details.
Change History (90)
comment:1 Changed 15 months ago by
 Branch set to u/caruso/tate_algebras
comment:2 Changed 15 months ago by
 Branch changed from u/caruso/tate_algebras to u/ghThibautVerron/TateAlgebras
 Commit set to b8a6ac3ef7ac5f8608e1ff30beb59ced9b85c357
comment:3 Changed 15 months ago by
 Branch changed from u/ghThibautVerron/TateAlgebras to u/caruso/TateAlgebras
comment:4 Changed 15 months ago by
 Commit changed from b8a6ac3ef7ac5f8608e1ff30beb59ced9b85c357 to 9ca2244a01a165e24431e9d58acf5054484d0cb3
comment:5 Changed 15 months ago by
 Commit changed from 9ca2244a01a165e24431e9d58acf5054484d0cb3 to 05cf0414d5afae999fdc1f8000075571d9accd52
Branch pushed to git repo; I updated commit sha1. New commits:
05cf041  Restriction + small fix in inverse_of_unit

comment:6 Changed 15 months ago by
 Commit changed from 05cf0414d5afae999fdc1f8000075571d9accd52 to 5d0e354ec45b362282840aa32d2b4cbd0856285f
Branch pushed to git repo; I updated commit sha1. New commits:
5d0e354  Fix bugs in quo_rem

comment:7 Changed 15 months ago by
 Cc TristanVaccon added; vaccon removed
comment:8 Changed 15 months ago by
 Branch changed from u/caruso/TateAlgebras to u/ghThibautVerron/tate_algebras
 Commit changed from 5d0e354ec45b362282840aa32d2b4cbd0856285f to 5abdb64bf364a1459e1b8e771219274fe1e35172
comment:9 Changed 15 months ago by
 Branch changed from u/ghThibautVerron/tate_algebras to u/caruso/tate_algebras
comment:10 Changed 15 months ago by
 Branch changed from u/caruso/tate_algebras to u/ghThibautVerron/tate_algebras
comment:11 Changed 15 months ago by
 Commit changed from 5abdb64bf364a1459e1b8e771219274fe1e35172 to 78003937e854ba0699ec507d41cd41f7e81d2af8
Branch pushed to git repo; I updated commit sha1. New commits:
7800393  Revert changes to .dirlocals.el

comment:12 Changed 15 months ago by
 Commit changed from 78003937e854ba0699ec507d41cd41f7e81d2af8 to 2383ba0acfb017721ec55ac44d790f0a1aba81f9
Branch pushed to git repo; I updated commit sha1. New commits:
2383ba0  Fixed tests

comment:13 Changed 15 months ago by
 Cc caruso added
comment:14 Changed 15 months ago by
 Branch changed from u/ghThibautVerron/tate_algebras to u/caruso/tate_algebras
comment:15 Changed 15 months ago by
 Commit changed from 2383ba0acfb017721ec55ac44d790f0a1aba81f9 to 8446736d3e9bb14d60b6688f8d258f8a47cb66f6
Branch pushed to git repo; I updated commit sha1. New commits:
8446736  Bug fixed in TateAlgebraTerms & more functionalities for ideals

comment:16 Changed 15 months ago by
 Description modified (diff)
comment:17 Changed 15 months ago by
 Description modified (diff)
comment:18 Changed 15 months ago by
 Commit changed from 8446736d3e9bb14d60b6688f8d258f8a47cb66f6 to fd3bf7b662acc0cebe91f963a8c9057604e69cda
Branch pushed to git repo; I updated commit sha1. New commits:
fd3bf7b  Some improvements in Buchberger algorithm

comment:19 Changed 15 months ago by
 Commit changed from fd3bf7b662acc0cebe91f963a8c9057604e69cda to bfddf6e4dc8670551fd94ae87d4d330890d1b934
Branch pushed to git repo; I updated commit sha1. New commits:
bfddf6e  Rewrite in cython

comment:20 Changed 15 months ago by
 Commit changed from bfddf6e4dc8670551fd94ae87d4d330890d1b934 to bc7c7637e5d43c612a4137747b1d2d9d2b58d699
Branch pushed to git repo; I updated commit sha1. New commits:
bc7c763  Better (?) choice of ordering of Spolynomials

comment:21 Changed 15 months ago by
 Branch changed from u/caruso/tate_algebras to u/ghThibautVerron/tate_algebras
comment:22 Changed 15 months ago by
 Branch changed from u/ghThibautVerron/tate_algebras to u/caruso/tate_algebras
comment:23 Changed 15 months ago by
 Commit changed from bc7c7637e5d43c612a4137747b1d2d9d2b58d699 to b00b8e042c46adde4d0887feb0394293eee50f13
Branch pushed to git repo; I updated commit sha1. New commits:
b00b8e0  Use directly the cython class PolyDict

comment:24 Changed 15 months ago by
 Commit changed from b00b8e042c46adde4d0887feb0394293eee50f13 to 100cbb727e64017ae940f5c4612a646092c1215a
Branch pushed to git repo; I updated commit sha1. New commits:
100cbb7  Fix bug in creation of elements in Tate algebras

comment:25 Changed 15 months ago by
 Branch changed from u/caruso/tate_algebras to u/ghThibautVerron/tate_algebras
comment:26 Changed 15 months ago by
 Branch changed from u/ghThibautVerron/tate_algebras to u/caruso/tate_algebras
comment:27 Changed 15 months ago by
 Commit changed from 100cbb727e64017ae940f5c4612a646092c1215a to 0f6391a172c79ac5620b32f1e323e407ee135016
Branch pushed to git repo; I updated commit sha1. New commits:
0f6391a  f.residue() now returns a polynomial over the residue field

comment:28 Changed 15 months ago by
 Branch changed from u/caruso/tate_algebras to u/ghThibautVerron/tate_algebras
comment:29 Changed 15 months ago by
 Commit changed from 0f6391a172c79ac5620b32f1e323e407ee135016 to a5b9d368190ce600023393f846a43918cd9533fb
Branch pushed to git repo; I updated commit sha1. New commits:
a5b9d36  Partial documentation of Tate algebra term elements

comment:30 Changed 15 months ago by
 Branch changed from u/ghThibautVerron/tate_algebras to u/caruso/tate_algebras
comment:31 Changed 15 months ago by
 Commit changed from a5b9d368190ce600023393f846a43918cd9533fb to cfc09d771fab2b7abb49f130913668324969602f
comment:32 Changed 15 months ago by
 Commit changed from cfc09d771fab2b7abb49f130913668324969602f to 7c2ac0bc86198f09c364c5151a275f3ad08dcc9c
Branch pushed to git repo; I updated commit sha1. New commits:
7c2ac0b  Implement a factory

comment:33 Changed 15 months ago by
 Branch changed from u/caruso/tate_algebras to u/ghThibautVerron/tate_algebras
comment:34 Changed 15 months ago by
 Commit changed from 7c2ac0bc86198f09c364c5151a275f3ad08dcc9c to 2a4044c42980e116e157de9749237f83b08e8058
Branch pushed to git repo; I updated commit sha1. New commits:
2a4044c  Documentation for Tate terms

comment:35 Changed 15 months ago by
 Commit changed from 2a4044c42980e116e157de9749237f83b08e8058 to 892c63163df8a1bd0805e6d0e593ac46103ce27d
comment:36 Changed 15 months ago by
 Commit changed from 892c63163df8a1bd0805e6d0e593ac46103ce27d to d10fca9e1b2d78e7ce7c9403a272cfd2a93cb31c
Branch pushed to git repo; I updated commit sha1. New commits:
d10fca9  Doctest for TateAlgebraElement __init__

comment:37 Changed 15 months ago by
 Branch changed from u/ghThibautVerron/tate_algebras to u/caruso/tate_algebras
comment:38 Changed 15 months ago by
 Commit changed from d10fca9e1b2d78e7ce7c9403a272cfd2a93cb31c to 0a49fbb4679a41a7c0a2595bae43ca291516f5a4
comment:39 Changed 15 months ago by
 Commit changed from 0a49fbb4679a41a7c0a2595bae43ca291516f5a4 to 0576cde54aa26aa7af7d8e2edd68b1c51f4946ba
Branch pushed to git repo; I updated commit sha1. New commits:
0576cde  Shorten doctests

comment:40 Changed 15 months ago by
 Commit changed from 0576cde54aa26aa7af7d8e2edd68b1c51f4946ba to 53c7ed32c004b8177a5991c7e2d7ea3e160f8119
Branch pushed to git repo; I updated commit sha1. New commits:
53c7ed3  Typo

comment:41 Changed 15 months ago by
 Commit changed from 53c7ed32c004b8177a5991c7e2d7ea3e160f8119 to fa9b86b913d1526120c1956cb3848798331598eb
Branch pushed to git repo; I updated commit sha1. New commits:
fa9b86b  Merge branch 'develop' into t/26195/tate_algebras

comment:42 Changed 15 months ago by
 Branch changed from u/caruso/tate_algebras to u/ghThibautVerron/tate_algebras
comment:43 Changed 15 months ago by
 Commit changed from fa9b86b913d1526120c1956cb3848798331598eb to ef8799f583ef84cadbcec3226b9691ea1b5d3f9b
Branch pushed to git repo; I updated commit sha1. New commits:
ef8799f  Partial documentation for the Tate algebra monoid class

comment:44 Changed 15 months ago by
 Commit changed from ef8799f583ef84cadbcec3226b9691ea1b5d3f9b to 44ba97030b04cbc846ab44897b6185bbfa90d7ee
comment:45 Changed 15 months ago by
 Cc roed added
I cc roed because, David, you might know the answer at the following question.
In this ticket, we have implemented two parents, the first one for the Tate algebra itself and the second one for the monoid of terms of the Tate Algebra. Here is a basic example:
sage: A.<x,y> = TateAlgebra(Zp(2)); A Tate Algebra in x (val >= 0), y (val >= 0) over 2adic Field with capped relative precision 20 sage: T = A.monoid_of_terms(); T Monoid of terms in x (val >= 0), y (val >= 0) over 2adic Field with capped relative precision 20
We now want to add a method for recovering A
(the Tate algebra) from T
(the monoid of terms). However a method algebra
already exists: it is inherited from sage.categories.sets_cat.Sets
and provides a very general construction of an algebra over an arbitrary set.
We believe that this general construction is not very relevant in our setting and that T.algebra()
should instead output A
. So our question is: is it allowed/appropriate to override the method algebra
(keeping in mind that it comes from the category machinery)?
In any case, we will create a method tate_algebra
but we think that having algebra
at the same time (with a different behavior) could be confusing.
comment:46 Changed 15 months ago by
Yes, you are allowed (maybe even encouraged) to override algebra
, and in this case, you should because you have a specialized implementation of the algebra.
Also, I want to just point out a common idiom that we've used is to define the monoid of monomials, then use CombinatorialFreeModule
and the category of AlgebrasWithBasis
to construct the corresponding algebra by implementing product_on_basis
. Although this has been known to have some issues with overhead due to the number of indirections (which can be mitigated by directly implementing the multiplication in the element class), and this might not work for what you need.
comment:47 Changed 15 months ago by
 Commit changed from 44ba97030b04cbc846ab44897b6185bbfa90d7ee to c559f1487c26ba91644d2fbf83333c66a91c8ac0
comment:48 Changed 15 months ago by
 Commit changed from c559f1487c26ba91644d2fbf83333c66a91c8ac0 to 298c253bb13e147604e91781f30bf9402fbacae5
comment:49 Changed 15 months ago by
 Commit changed from 298c253bb13e147604e91781f30bf9402fbacae5 to 52b9ad10d6e0b8c8901556090715f9944f594ee5
Branch pushed to git repo; I updated commit sha1. New commits:
52b9ad1  Documentation of Buchberger's function

comment:50 Changed 15 months ago by
 Branch changed from u/ghThibautVerron/tate_algebras to u/caruso/tate_algebras
comment:51 Changed 15 months ago by
 Commit changed from 52b9ad10d6e0b8c8901556090715f9944f594ee5 to a433e9c22e2a0693a78c851f5b0de615516fd546
comment:52 Changed 15 months ago by
 Commit changed from a433e9c22e2a0693a78c851f5b0de615516fd546 to 408512dee2f068e87131cf118b59ffb52882bd2e
Branch pushed to git repo; I updated commit sha1. New commits:
408512d  Normalize output of groebner_basis

comment:53 Changed 15 months ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:54 Changed 15 months ago by
 Commit changed from 408512dee2f068e87131cf118b59ffb52882bd2e to 65e7edb02da7421ecbda770e4f437d41ffc33830
Branch pushed to git repo; I updated commit sha1. New commits:
65e7edb  Add doctest to the method dotprod

comment:55 Changed 15 months ago by
 Commit changed from 65e7edb02da7421ecbda770e4f437d41ffc33830 to 4966e04a1646b80749c653e9c937be95726d3b72
Branch pushed to git repo; I updated commit sha1. New commits:
4966e04  Uncapitalize error messages

comment:56 Changed 14 months ago by
 Commit changed from 4966e04a1646b80749c653e9c937be95726d3b72 to 0c8f8019641d90ebb09add1e4c06a64f24840986
Branch pushed to git repo; I updated commit sha1. New commits:
0c8f801  Small fixes after patchbot's review

comment:57 Changed 14 months ago by
 Branch changed from u/caruso/tate_algebras to u/roed/tate_algebras
comment:58 Changed 14 months ago by
 Branch changed from u/roed/tate_algebras to u/caruso/tate_algebras
comment:59 Changed 14 months ago by
 Commit changed from 0c8f8019641d90ebb09add1e4c06a64f24840986 to 7c4b4ae4bcda06deac867ae089814a96cc7d1cca
Branch pushed to git repo; I updated commit sha1. New commits:
7c4b4ae  Address David's comments on Zulip

comment:60 Changed 14 months ago by
 Commit changed from 7c4b4ae4bcda06deac867ae089814a96cc7d1cca to 30b25af2653550bf07b0bd46bb7d5af1bf74e6aa
comment:61 Changed 14 months ago by
 Commit changed from 30b25af2653550bf07b0bd46bb7d5af1bf74e6aa to 62279371230826c7d4e6c221ce0d00b9620838ff
Branch pushed to git repo; I updated commit sha1. New commits:
6227937  Accelerate (?) square roots and nth roots

comment:62 Changed 14 months ago by
 Commit changed from 62279371230826c7d4e6c221ce0d00b9620838ff to dcd4c5a005822b6615b41c72c04aa0779e64ac59
comment:63 Changed 14 months ago by
 Commit changed from dcd4c5a005822b6615b41c72c04aa0779e64ac59 to 5f64c3aa69a013f880c2565a4a20a069aba643a7
Branch pushed to git repo; I updated commit sha1. New commits:
5f64c3a  Small improvement

comment:64 Changed 14 months ago by
 Commit changed from 5f64c3aa69a013f880c2565a4a20a069aba643a7 to a064d262d34d375d332597b8d56e67a967d4ccf0
Branch pushed to git repo; I updated commit sha1. New commits:
a064d26  Add a special case in __pow__ when the exponent is a rational number

comment:65 Changed 14 months ago by
 Commit changed from a064d262d34d375d332597b8d56e67a967d4ccf0 to 679a4267af30aac8c4e38911345e90cb0285092d
comment:66 Changed 14 months ago by
 Commit changed from 679a4267af30aac8c4e38911345e90cb0285092d to 1ada3fc97636a19a6824a0976777dbd033ee4a25
comment:67 Changed 14 months ago by
 Dependencies set to 26479
comment:68 Changed 14 months ago by
 Dependencies changed from 26479 to #26479
comment:69 Changed 14 months ago by
 Commit changed from 1ada3fc97636a19a6824a0976777dbd033ee4a25 to e48860caec0f9095b37229f01051350fc09a78a6
comment:70 Changed 14 months ago by
I wanted to point out a couple of points:
 for the methods
log
andexp
, I essentially copy the code insage.rings.padics.padic_element_generic
; so I wonder if it would be a good idea to factorize this code. One solution would be to split the current classpAdicElementGeneric
into two parts (e.gpAdicElementGeneric
andpAdicNumberGeneric
), the second one inheriting from the first one, and let Tate series derive from the most general one.
 in the method
lift_to_precision
, I defined a nested functionlift_without_error
but I think it would be better to add a keyword argumentno_error
(or something like that) tolift_to_precision
(for padic number); what's your opinion?
comment:71 Changed 14 months ago by
 Commit changed from e48860caec0f9095b37229f01051350fc09a78a6 to 1ac31a95865b61d494b9f42b924d2c112d5c204d
comment:72 Changed 14 months ago by
 Commit changed from 1ac31a95865b61d494b9f42b924d2c112d5c204d to adec9377c4d7b6e25ea2dcb4d7afe083a2ba2f8e
comment:73 Changed 14 months ago by
 Branch changed from u/caruso/tate_algebras to u/roed/tate_algebras
comment:74 Changed 14 months ago by
 Branch changed from u/roed/tate_algebras to u/caruso/tate_algebras
 Commit changed from adec9377c4d7b6e25ea2dcb4d7afe083a2ba2f8e to 9bae27371b3ceb1b5ffc258d2de6cbdad7df3075
comment:75 Changed 13 months ago by
 Dependencies changed from #26479 to #26479, #26575
comment:76 Changed 13 months ago by
 Commit changed from 9bae27371b3ceb1b5ffc258d2de6cbdad7df3075 to d8c17c992b07579524b454daf29f3b5cf8627f81
Branch pushed to git repo; I updated commit sha1. New commits:
724bc71  Allow ... at beginning of doctest output

0fa318f  No longer substitute for ... inside ....:, fix doctests

f02ffa1  Merge branch 'develop' into t/26575/ellipses

fc8df57  Replace back <ELLIPSIS_TAG> by ... in exc_msg

bad89d2  Merge branch 't/26575/ellipses' into t/26195/tate_algebras

d8c17c9  Remove parentheses and fix bigoh notation in doctests

comment:77 Changed 13 months ago by
 Commit changed from d8c17c992b07579524b454daf29f3b5cf8627f81 to 4982c7e44bb87706362b18c981b1f4646203d5b5
comment:78 Changed 13 months ago by
 Reviewers set to David Roe
 Status changed from needs_review to positive_review
Looks good!
comment:79 Changed 13 months ago by
 Milestone changed from sage8.4 to sage8.5
comment:80 Changed 13 months ago by
 Branch changed from u/caruso/tate_algebras to 4982c7e44bb87706362b18c981b1f4646203d5b5
 Resolution set to fixed
 Status changed from positive_review to closed
comment:81 Changed 13 months ago by
 Commit 4982c7e44bb87706362b18c981b1f4646203d5b5 deleted
Tate algebras elements are now among the 10 files having the most failures with python3. See #26212.
EDIT: And this is also bad:
sage t long src/sage/rings/tate_algebra_ideal.pyx # 29 doctests failed
One example of failure: bad use of range:
File "sage/rings/tate_algebra_ideal.pyx", line 83, in sage.rings.tate_algebra_ideal._groebner_basis_buchberger (build/cythonized/sage/rings/tate_algebra_ideal.c:3488) indices = range(l) TypeError: Expected list, got range
Other failure: change dict while iterating over this dict:
File "sage/rings/tate_algebra_element.pyx", line 1151, in sage.rings.tate_algebra_element.TateAlgebraElement._normalize (build/cythonized/sage/rings/tate_algebra_element.c:12421) for (e,c) in self._poly.__repn.items(): RuntimeError: dictionary changed size during iteration
comment:82 Changed 13 months ago by
python3 problems are fixed in #26692, please review
comment:83 Changed 13 months ago by
Sorry about that! I didn't see any py3 failures on the patchbot, so I thought it was okay. I've got a py3 build, so I'll try to check big tickets there from now on.
comment:84 Changed 12 months ago by
This should be fixed:
[288/306] Cythonizing sage/rings/tate_algebra_element.pyx warning: sage/rings/tate_algebra_element.pyx:301:10: Compatible but nonidentical C method '_mul_' not redeclared in definition part of extension type 'TateAlgebraTerm'. This may cause incorrect vtables to be generated. warning: sage/structure/element.pxd:188:15: Previous declaration is here
comment:85 Changed 12 months ago by
Essentially, you're missing a declaration for cpdef _mul_
in tate_algebra_element.pxd
comment:86 Changed 12 months ago by
There are also some thing I consider bad style, for example
@coerce_binop def __floordiv__(self, other):
Why not use _floordiv_
from the coercion model?
There is also the inefficient
from sage.structure.richcmp import op_EQ, op_NE, op_LT, op_GT, op_LE, op_GE
which should be
from cpython.object cimport Py_LT, Py_LE, Py_EQ, Py_NE, Py_GT, Py_GE
comment:87 followup: ↓ 89 Changed 12 months ago by
And isn't _pushout_family()
really just coercion_model.common_parent()
?
comment:88 Changed 12 months ago by
This is reinventing sage.structure.richcmp.rich_to_bool
:
if op == op_LT: return c < 0 if op == op_LE: return c <= 0 if op == op_GT: return c > 0 if op == op_GE: return c >= 0
comment:89 in reply to: ↑ 87 Changed 12 months ago by
Thanks Jeroen for your useful comments!
I addressed all of them except this one:
And isn't
_pushout_family()
really justcoercion_model.common_parent()
?
because I'm not sure that _pushout_family()
and coercion_model.common_parent()
do the same job. At least if I replace the code of _pushout_family()
by:
elements = [initial] + list(elements) return coercion_model.common_parent(*elements)
I get many doctest failures.
comment:90 Changed 12 months ago by
cf ticket #26807
Branch pushed to git repo; I updated commit sha1. New commits:
First working version