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.

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

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

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