A framework for discrete valuations in Sage

[saraedum]

This is a meta-ticket to keep track of the progress of integrating ​https://github.com/saraedum/mac_lane into Sage.

Review

For your convenience you can review this ticket at ​https://github.com/saraedum/mac_lane/pull/4 (and leave inline comments.)

Please check off [x] the following when you think that a file is in good shape (modulo the comments that you made.) Or put a [-] if it needs substantial work. You can put your name next to file to tell others that you are already having a look at it.

[x] function_field/function_field_valuation.py (Stefan Wewers)
[x] padics/discrete_value_group.py
[ ] padics/padic_valuation.py (David)
[-] valuation/README.md
[x] valuation/__init__.py
[ ] valuation/all.py (David)
[x] valuation/augmented_valuation.py (David)
[x] valuation/developing_valuation.py (Shiva)
[ ] valuation/gauss_valuation.py (Padmavathi)
[ ] valuation/inductive_valuation.py (Padmavathi)
[x] valuation/limit_valuation.py (David)
[x] valuation/mapped_valuation.py (David)
[x] valuation/scaled_valuation.py (David)
[ ] valuation/trivial_valuation.py (David)
[x] valuation/valuation.py (David)
[x] valuation/valuation_space.py (David)
[ ] valuation/valuations_catalog.py
[ ] valuation/value_group.py (Padmavathi)

Testing

Because of all the dependencies of this ticket it is a bit hard to build this. If you have access to k8s, you can use the version in ~/Src/sage-mac_lane/ to try this package out. (Please do not push all the dependencies onto this branch as this is going to make reviewing this much harder.)

Known Issues

Some tests fail because some of the paths broke when moving the code from github into sage. The following are known problems – Julian aka saraedum is working on these:

sage -t --warn-long 39.1 src/sage/rings/function_field/function_field_valuation.py  # 126 doctests failed
sage -t --warn-long 39.1 src/sage/rings/valuation/valuation.py  # 9 doctests failed
sage -t --warn-long 39.1 src/sage/rings/valuation/limit_valuation.py  # 52 doctests failed
sage -t --warn-long 39.1 src/sage/rings/valuation/mapped_valuation.py  # 42 doctests failed
sage -t --warn-long 39.1 src/sage/rings/valuation/inductive_valuation.py  # 13 doctests failed
sage -t --warn-long 39.1 src/sage/rings/valuation/augmented_valuation.py  # 10 doctests failed

Necessary changes

Fix bugs in Sage

There are a number of trivial bugs that get fixed by monkey-patches in ​https://github.com/saraedum/mac_lane/blob/master/__init__.py

1. Conversion from a Function Field to its Constant Field #21872
2. Conversion from a Function Field to its underlying Polynomial Ring #23166
3. Coercions between Function Fields #23167
4. Coercions are injective if the underlying map is #21879
5. Ring homomorphisms from Fields are injective #21879
6. Polynomial rings embed into their fraction fields #23185
7. The embedding of a ring into a polynomial ring over that ring is injective #23203, #23204, #23211
8. p-adic rings embed into their fraction fields #23188
9. Morphisms of number fields are injective #21879
10. ZZ into QQ is injective #21879
11. quotients of polynomial rings are injective/surjective #23190
12. ZZ into a Number Field is injective #21879
13. ZZ into an order of a Number Field is injective #21879
14. ZZ does not map onto QQ #23186
15. ZpCA shifts are broken
16. add default implementation of inverse_of_unit() #23191
17. R[x]→S[x] is injective/surjective if R→S is #23495

Add new features to Sage

New features that the code needs to work

1. Factorization over iterated extensions of finite fields. #21996
2. principal_part() and sides() of a Newton Polygon (patch this in the calling code instead.)
3. (cached_in_argument_method #22034)

Make tests non-trivial

1. (some_elements() should be non-trivial for number fields/orders) #23192
2. (some_elements() should be non-trivial/deterministic for rational function fields and their extensions) #23193
3. (some_elements() should be non-trivial for fraction_fields of polynomial rings) #23194

Add the valuation code to Sage

i.e., add these files ​https://github.com/saraedum/mac_lane to Sage.

[roed]

Last 10 new commits:

​925d8fa	fix typo in comment
​c4a7b1a	Added a tutorial in the README
​20e6110	move to subdirectory for merging with sage tree
​ed206ec	removing gitignore for merge with sage tree
​14799b0	Merge mac_lane infrastructure for discrete valuations into sage
​0767201	remove mac_lane LICENSE
​bd1dcbf	remove obsolete TODOs
​0eb3fff	remove monkey patches
​6c3a301	move valuation code to valuation/
​0f615c7	remove specific valuation code out of valuation/

[git]

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

​8afc361	remove standalone import commands
​4153ef9	Wired up valuations in the Sage library

[git]

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

​c0a81c8

fix function lookup

[saraedum]

New commits:

​c0a81c8

fix function lookup

[padma_sk]

I was reviewing gauss_valuation.py and tried reducing a polynomial using the Gauss valuation induced by the 2-adic valuation, and got an unexpected error message. I thought it would tell me that the polynomial wasn't integral, and instead it gave me a coercion error.

sage: v
Gauss valuation induced by 2-adic valuation
sage: v.domain()
Univariate Polynomial Ring in y over Integer Ring
sage: h
1/2*y^2
sage: v.reduce(h)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-108-4d78566b468b> in <module>()
----> 1 v.reduce(h)
 
/projects/da1818ed-996d-4de6-acc6-361415b7725d/user/padma_sk/mac_lane/gauss_valuation.py in reduce(self, f, check, degree_bound, coefficients, valuations)
    360
    361         """
--> 362         f = self.domain().coerce(f)
    363
    364         if degree_bound is not None:
 
/usr/local/sage/src/sage/structure/parent.pyx in sage.structure.parent.Parent.coerce (/usr/local/sage/src/build/cythonized/sage/structure/parent.c:11229)()
   1166             return False
   1167
-> 1168     cpdef coerce(self, x):
   1169         """
   1170         Return x as an element of self, if and only if there is a canonical
 
/usr/local/sage/src/sage/structure/parent.pyx in sage.structure.parent.Parent.coerce (/usr/local/sage/src/build/cythonized/sage/structure/parent.c:11158)()
   1193                 except Exception:
   1194                     _record_exception()
-> 1195             raise TypeError("no canonical coercion from %s to %s" % (parent(x), self))
   1196         else:
   1197             return (<map.Map>mor)._call_(x)
 
TypeError: no canonical coercion from Univariate Polynomial Ring in y over Rational Field to Univariate Polynomial Ring in y over Integer Ring

[padma_sk]

equivalence_unit from gauss_valuation.py isn't outputting the results shown in the example input -2 as shown in the file.

sage: v
Gauss valuation induced by 2-adic valuation
sage: v.domain()
Univariate Polynomial Ring in y over Integer Ring
sage: v.equivalence_unit(2)
4
sage: v.equivalence_unit(-2)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-128-71aadb857663> in <module>()
----> 1 v.equivalence_unit(-Integer(2))
 
/usr/local/sage/src/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCaller.__call__ (/usr/local/sage/src/build/cythonized/sage/misc/cachefunc.c:1079
2)()
   2036                 return cache[k]
   2037         except KeyError:
-> 2038             w = self._instance_call(*args, **kwds)
   2039             cache[k] = w
   2040             return w
 
/usr/local/sage/src/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCaller._instance_call (/usr/local/sage/src/build/cythonized/sage/misc/cachefunc.
c:10238)()
   1912             True
   1913         """
-> 1914         return self.f(self._instance, *args, **kwds)
   1915
   1916     cdef fix_args_kwds(self, tuple args, dict kwds):
 
/projects/da1818ed-996d-4de6-acc6-361415b7725d/user/padma_sk/mac_lane/gauss_valuation.py in equivalence_unit(self, s, reciprocal)
    474             return self.equivalence_reciprocal(self.equivalence_unit(-s))
    475
--> 476         ret = self._base_valuation.element_with_valuation(s)
    477         return self.domain()(ret)
    478
 
/projects/da1818ed-996d-4de6-acc6-361415b7725d/user/padma_sk/mac_lane/valuation_space.py in element_with_valuation(self, s)
    465             s = QQ.coerce(s)
    466             if s not in self.value_semigroup():
--> 467                 raise ValueError("s must be in the value semigroup of this valuation but %r is not in %r"%(s, self.value_semigroup()))
    468             if s == 0:
    469                 return self.domain().one()
 
ValueError: s must be in the value semigroup of this valuation but -2 is not in Additive Abelian Semigroup generated by 1

[saraedum]

Thanks for reporting this. I think this is ok. The problem here is not that the polynomial is not integral but that the polynomial is not in the domain.

This works:

sage: R.<x> = QQ[]
sage: v = valuations.GaussValuation(R, QQ.valuation(2))
sage: v.reduce(x + 1/2)
ValueError: reduction not defined for non-integral elements and x + 1/2 is not integral over Gauss valuation induced by 2-adic valuation

This does not:

sage: R.<x> = ZZ[]
sage: v = valuations.GaussValuation(R, ZZ.valuation(2))
sage: v.reduce(x + 1/2)
TypeError: no canonical coercion from Univariate Polynomial Ring in x over Rational Field to Univariate Polynomial Ring in x over Integer Ring

Replying to padma_sk:

I was reviewing gauss_valuation.py and tried reducing a polynomial using the Gauss valuation induced by the 2-adic valuation, and got an unexpected error message. I thought it would tell me that the polynomial wasn't integral, and instead it gave me a coercion error.

sage: v
Gauss valuation induced by 2-adic valuation
sage: v.domain()
Univariate Polynomial Ring in y over Integer Ring
sage: h
1/2*y^2
sage: v.reduce(h)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-108-4d78566b468b> in <module>()
----> 1 v.reduce(h)
 
/projects/da1818ed-996d-4de6-acc6-361415b7725d/user/padma_sk/mac_lane/gauss_valuation.py in reduce(self, f, check, degree_bound, coefficients, valuations)
    360
    361         """
--> 362         f = self.domain().coerce(f)
    363
    364         if degree_bound is not None:
 
/usr/local/sage/src/sage/structure/parent.pyx in sage.structure.parent.Parent.coerce (/usr/local/sage/src/build/cythonized/sage/structure/parent.c:11229)()
   1166             return False
   1167
-> 1168     cpdef coerce(self, x):
   1169         """
   1170         Return x as an element of self, if and only if there is a canonical
 
/usr/local/sage/src/sage/structure/parent.pyx in sage.structure.parent.Parent.coerce (/usr/local/sage/src/build/cythonized/sage/structure/parent.c:11158)()
   1193                 except Exception:
   1194                     _record_exception()
-> 1195             raise TypeError("no canonical coercion from %s to %s" % (parent(x), self))
   1196         else:
   1197             return (<map.Map>mor)._call_(x)
 
TypeError: no canonical coercion from Univariate Polynomial Ring in y over Rational Field to Univariate Polynomial Ring in y over Integer Ring

[saraedum]

You are in the wrong domain in this example I think: This is the error you are seeing because there is no element of valuation -2 in ZZ[x].

sage: R.<x> = ZZ[]
sage: v = valuations.GaussValuation(R, ZZ.valuation(2))
sage: v.element_with_valuation(-2)
ValueError: s must be in the value semigroup of this valuation but -2 is not in Additive Abelian Semigroup generated by 1

However, this works in QQ[x].

sage: sage: R.<x> = QQ[]
sage: v = valuations.GaussValuation(R, QQ.valuation(2))
sage: v.element_with_valuation(-2)
1/4

Does that make sense? (Should it be documented more explicitly?)

Replying to padma_sk:

equivalence_unit from gauss_valuation.py isn't outputting the results shown in the example input -2 as shown in the file.

sage: v
Gauss valuation induced by 2-adic valuation
sage: v.domain()
Univariate Polynomial Ring in y over Integer Ring
sage: v.equivalence_unit(2)
4
sage: v.equivalence_unit(-2)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-128-71aadb857663> in <module>()
----> 1 v.equivalence_unit(-Integer(2))
 
/usr/local/sage/src/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCaller.__call__ (/usr/local/sage/src/build/cythonized/sage/misc/cachefunc.c:1079
2)()
   2036                 return cache[k]
   2037         except KeyError:
-> 2038             w = self._instance_call(*args, **kwds)
   2039             cache[k] = w
   2040             return w
 
/usr/local/sage/src/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCaller._instance_call (/usr/local/sage/src/build/cythonized/sage/misc/cachefunc.
c:10238)()
   1912             True
   1913         """
-> 1914         return self.f(self._instance, *args, **kwds)
   1915
   1916     cdef fix_args_kwds(self, tuple args, dict kwds):
 
/projects/da1818ed-996d-4de6-acc6-361415b7725d/user/padma_sk/mac_lane/gauss_valuation.py in equivalence_unit(self, s, reciprocal)
    474             return self.equivalence_reciprocal(self.equivalence_unit(-s))
    475
--> 476         ret = self._base_valuation.element_with_valuation(s)
    477         return self.domain()(ret)
    478
 
/projects/da1818ed-996d-4de6-acc6-361415b7725d/user/padma_sk/mac_lane/valuation_space.py in element_with_valuation(self, s)
    465             s = QQ.coerce(s)
    466             if s not in self.value_semigroup():
--> 467                 raise ValueError("s must be in the value semigroup of this valuation but %r is not in %r"%(s, self.value_semigroup()))
    468             if s == 0:
    469                 return self.domain().one()
 
ValueError: s must be in the value semigroup of this valuation but -2 is not in Additive Abelian Semigroup generated by 1

[gpark]

Ran the test and found the error:

sage -t src/sage/rings/function_field/function_field.py # 7 doctests failed

[saraedum]

Replying to gpark:

Ran the test and found the error:

sage -t src/sage/rings/function_field/function_field.py # 7 doctests failed

Did you run the tests with all the dependencies applied? About 50 tests fail for me. That's expected (since the dependencies are not in yet.)

[saraedum]

The following errors are expected. I am working on them.

----------------------------------------------------------------------
sage -t --warn-long 39.1 src/sage/rings/valuation/limit_valuation.py  # 52 doctests failed
sage -t --warn-long 39.1 src/sage/rings/valuation/gauss_valuation.py  # 1 doctest failed
sage -t --warn-long 39.1 src/sage/rings/valuation/valuation_space.py  # 2 doctests failed
sage -t --warn-long 39.1 src/sage/rings/valuation/mapped_valuation.py  # 42 doctests failed
sage -t --warn-long 39.1 src/sage/rings/valuation/valuation.py  # 9 doctests failed
sage -t --warn-long 39.1 src/sage/rings/valuation/inductive_valuation.py  # 13 doctests failed
sage -t --warn-long 39.1 src/sage/rings/valuation/augmented_valuation.py  # 16 doctests failed
----------------------------------------------------------------------

[saraedum]

Sorry, I somehow reverted some changes to the ticket description. Not sure how this happened.

[swewers]

I have had a look at function_field_valuation. I have already worked with the code a lot, and it is working fine, and the documentation is extensive and clear. But I have only tested the latest standalone version.

[git]

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

​9fd8733

fix import

[git]

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

​e1e65a5

fixed typo

[git]

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

​9c16a1b

undo .valuation() shortcut

[git]

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

​119f245

It is not relevant whether a valuation converts into the valuation space but whether it is already in the valuation space

[git]

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

​7ea9874

fix doctests

[saraedum]

New commits:

​9fd8733	fix import
​e1e65a5	fixed typo
​9c16a1b	undo .valuation() shortcut
​119f245	It is not relevant whether a valuation converts into the valuation space but whether it is already in the valuation space
​7ea9874	fix doctests

[git]

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

​3fd4140	add doctest output
​0c60cb7	fix valuation parameters

[git]

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

​2010014

restricting to ZZ, we need to know the prime

[saraedum]

New commits:

​3fd4140	add doctest output
​0c60cb7	fix valuation parameters
​2010014	restricting to ZZ, we need to know the prime

[git]

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

​e5ef4d8	do not catch everything
​efe2490	Merge branch 'u/saraedum/a_framework_for_discrete_valuations_in_sage' of git://trac.sagemath.org/sage into t/21869/a_framework_for_discrete_valuations_in_sage

[roed]

New commits:

​e5ef4d8	do not catch everything
​9fd8733	fix import
​e1e65a5	fixed typo
​9c16a1b	undo .valuation() shortcut
​119f245	It is not relevant whether a valuation converts into the valuation space but whether it is already in the valuation space
​7ea9874	fix doctests
​3fd4140	add doctest output
​0c60cb7	fix valuation parameters
​2010014	restricting to ZZ, we need to know the prime
​efe2490	Merge branch 'u/saraedum/a_framework_for_discrete_valuations_in_sage' of git://trac.sagemath.org/sage into t/21869/a_framework_for_discrete_valuations_in_sage

[roed]

Oops. Reverting.

[git]

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

​1eace28	Update valuation_space.py
​21b0f68	Update valuation_space.py
​38f3815	Update valuation_space.py
​7c57f68	Update valuation_space.py
​d90afa8	Update valuation_space.py
​1cb8178	Update valuation_space.py
​39cb55b	Update valuation_space.py
​a474ed5	Update valuation_space.py
​ca2089f	Update valuation_space.py
​0fd986f	Merge remote-tracking branch 'remotes/github/sage' into t/21869/a_framework_for_discrete_valuations_in_sage