Tate algebras

[caruso]

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.

[git]

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

​9ca2244

First working version

[git]

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

​05cf041

Restriction + small fix in inverse_of_unit

[git]

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

​5d0e354

Fix bugs in quo_rem

[gh-ThibautVerron]

New commits:

​fa4e37a	First docstring
​5abdb64	Merge branch 'u/caruso/TateAlgebras' of git://trac.sagemath.org/sage into t/26195/TateAlgebras

[git]

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

​7800393

Revert changes to .dir-locals.el

[git]

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

​2383ba0

Fixed tests

[git]

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

​8446736

Bug fixed in TateAlgebraTerms & more functionalities for ideals

[git]

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

​fd3bf7b

Some improvements in Buchberger algorithm

[git]

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

​bfddf6e

Rewrite in cython

[git]

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

​bc7c763

Better (?) choice of ordering of S-polynomials

[git]

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

​b00b8e0

Use directly the cython class PolyDict

[git]

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

​100cbb7

Fix bug in creation of elements in Tate algebras

[git]

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

​0f6391a

f.residue() now returns a polynomial over the residue field

[git]

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

​a5b9d36

Partial documentation of Tate algebra term elements

[git]

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

​fc5d3c4	Implement rich comparison for terms
​cfc09d7	Implement monomials() and leading_monomial()

[git]

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

​7c2ac0b

Implement a factory

[git]

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

​2a4044c

Documentation for Tate terms

[git]

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

​439bb96	Behavior for rings
​0cf12c1	Minor changes to docstrings for tests
​892c631	Fixed some doctests

[git]

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

​d10fca9

Doctest for TateAlgebraElement __init__

[git]

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

​7d6d030	Simplify doctests for Tate terms
​0a49fbb	Fix doctest

[git]

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

​0576cde

Shorten doctests

[git]

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

​53c7ed3

Typo

[git]

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

​fa9b86b

Merge branch 'develop' into t/26195/tate_algebras

[git]

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

​ef8799f

Partial documentation for the Tate algebra monoid class

[git]

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

​317c782	Documentation on Tate terms
​44ba970	Fixed doctests

[caruso]

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 2-adic Field with capped relative precision 20
sage: T = A.monoid_of_terms(); T
Monoid of terms in x (val >= 0), y (val >= 0) over 2-adic 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.

[tscrim]

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.

[git]

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

​4af77f3	Documentation of Buchberger, without examples
​cf2afe6	Deduplicate coercion + recover parent algebra from monoid of terms
​c559f14	Documentation of the new function

[git]

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

​46d8bd1	Documentation for ideals
​298c253	Moved coercion code back in the algebra class

[git]

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

​52b9ad1

Documentation of Buchberger's function

[git]

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

​c1acf5c	Add doctest in polydict
​af6ddbe	Add licence
​66844ad	Add tutorial
​fc2d6a7	Add LaTeX representations
​a433e9c	Add evaluation and composition

[git]

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

​408512d

Normalize output of groebner_basis

[git]

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

​65e7edb

Add doctest to the method dotprod

[git]

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

​4966e04

Uncapitalize error messages

[git]

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

​0c8f801

Small fixes after patchbot's review

[git]

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

​7c4b4ae

Address David's comments on Zulip

[git]

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

​d65ffe0	Add log, exp and their friends
​30b25af	Merge branch 'u/caruso/tate_algebras' of git://trac.sagemath.org/sage into t/26195/tate_algebras

[git]

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

​6227937

Accelerate (?) square roots and nth roots

[git]

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

​6a1d76a	Discard terms which are indistinguishable from zero in quo_rem
​2323508	Change "AA" to "Ao" for the ring of integers
​dcd4c5a	Add definition of S-polynomial

[git]

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

​5f64c3a

Small improvement

[git]

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

[git]

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

​d5cd2bd	Add documentation to lift_to_precision()
​679a426	Fix pyflakes

[git]

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

​8419d2c	fix latex printing
​a351051	let latex_variable_name handle numeric names
​8b18164	Add doctest
​1ada3fc	Merge branch 'padic_printer_latex' into t/26195/tate_algebras

[git]

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

​5ca2bd0	Replace back \Bold{Z} by \ZZ, etc. in the documentation
​83b48e3	Replace \mathbb{Z}, \mathbb{Q} by \ZZ, \QQ respectively
​008d7fc	Replace \mathbb{f} by \Bold{F}
​e48860c	Merge branch 'padic_printer_latex' into t/26195/tate_algebras

[caruso]

I wanted to point out a couple of points:

• for the methods log and exp, I essentially copy the code in sage.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 class pAdicElementGeneric into two parts (e.g pAdicElementGeneric and pAdicNumberGeneric), 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 function lift_without_error but I think it would be better to add a keyword argument no_error (or something like that) to lift_to_precision (for p-adic number); what's your opinion?

[git]

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

​e83713c	Revert "Replace \mathbb{f} by \Bold{F}"
​2e41efd	Revert "Replace \mathbb{Z}, \mathbb{Q} by \ZZ, \QQ respectively"
​9e85f91	Small fixes
​1ac31a9	Merge branch 'padic_printer_latex' into t/26195/tate_algebras

[git]

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

​fb3bbaa	Fix doctests
​adec937	Merge branch 'padic_printer_latex' into t/26195/tate_algebras

[git]

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

[git]

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

​4151b7e	Fix doctest
​4982c7e	Merge branch 't/26575/ellipses' into t/26195/tate_algebras

[roed]

Looks good!

[chapoton]

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

[chapoton]

python3 problems are fixed in #26692, please review

[roed]

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.

[jdemeyer]

This should be fixed:

[288/306] Cythonizing sage/rings/tate_algebra_element.pyx
warning: sage/rings/tate_algebra_element.pyx:301:10: Compatible but non-identical 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

[jdemeyer]

Essentially, you're missing a declaration for cpdef _mul_ in tate_algebra_element.pxd

[jdemeyer]

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

[jdemeyer]

And isn't _pushout_family() really just coercion_model.common_parent()?

[jdemeyer]

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

[caruso]

Thanks Jeroen for your useful comments!

I addressed all of them except this one:

And isn't _pushout_family() really just coercion_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.

[caruso]

cf ticket #26807