Opened 4 years ago
Last modified 2 years ago
#21869 closed enhancement
A framework for discrete valuations in Sage — at Version 60
Reported by:  saraedum  Owned by:  

Priority:  major  Milestone:  sage7.5 
Component:  commutative algebra  Keywords:  discrete valuations, valuations, padics, function fields, number fields, smooth projective curves, Mac Lane algorithm, Montes algorithm, sd87 
Cc:  Merged in:  
Authors:  Julian Rüth  Reviewers:  GaYee Park, Stefan Wewers 
Report Upstream:  N/A  Work issues:  move references to references file, move README to sage documentation, make sure that valuation() has a lot of the documentation and the factory just references it, remove optional: integrated bits, check that discrete_value_group is still available the same way it was under padics, 252 failing doctests 
Branch:  u/saraedum/a_framework_for_discrete_valuations_in_sage (Commits)  Commit:  c0a81c8285b47f6fc89aa34bc125ac474c75f2e9 
Dependencies:  #21782, #23166, #23167, #21879, #23185, #23203, #23204, #23211, #23188, #21879, #23186, #23191, #21996, #23190, #23495  Stopgaps: 
Description (last modified by )
This is a metaticket 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 (Stefan Wewers) [x] padics/discrete_value_group.py [ ] padics/padic_valuation.py [] valuation/README.md [x] valuation/__init__.py [ ] valuation/all.py [ ] valuation/augmented_valuation.py [ ] valuation/developing_valuation.py [ ] valuation/gauss_valuation.py (Padmavathi) [ ] valuation/inductive_valuation.py (Padmavathi) [ ] valuation/limit_valuation.py [ ] valuation/mapped_valuation.py [ ] valuation/scaled_valuation.py [ ] valuation/trivial_valuation.py [ ] valuation/valuation.py [ ] 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/sagemac_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 warnlong 39.1 src/sage/rings/function_field/function_field_valuation.py # 126 doctests failed sage t warnlong 39.1 src/sage/rings/valuation/valuation.py # 9 doctests failed sage t warnlong 39.1 src/sage/rings/valuation/limit_valuation.py # 52 doctests failed sage t warnlong 39.1 src/sage/rings/valuation/mapped_valuation.py # 42 doctests failed sage t warnlong 39.1 src/sage/rings/valuation/inductive_valuation.py # 13 doctests failed sage t warnlong 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 monkeypatches in https://github.com/saraedum/mac_lane/blob/master/__init__.py
 Conversion from a Function Field to its Constant Field #21872
 Conversion from a Function Field to its underlying Polynomial Ring #23166
 Coercions between Function Fields #23167
 Coercions are injective if the underlying map is #21879
 Ring homomorphisms from Fields are injective #21879
 Polynomial rings embed into their fraction fields #23185
 The embedding of a ring into a polynomial ring over that ring is injective #23203, #23204, #23211
 padic rings embed into their fraction fields #23188
 Morphisms of number fields are injective #21879
 ZZ into QQ is injective #21879
 quotients of polynomial rings are injective/surjective #23190
 ZZ into a Number Field is injective #21879
 ZZ into an order of a Number Field is injective #21879
 ZZ does not map onto QQ #23186
ZpCA shifts are broken add default implementation of inverse_of_unit() #23191
 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
 Factorization over iterated extensions of finite fields. #21996
principal_part() and sides() of a Newton Polygon(patch this in the calling code instead.) (cached_in_argument_method #22034)
Make tests nontrivial
 (some_elements() should be nontrivial for number fields/orders) #23192
 (some_elements() should be nontrivial/deterministic for rational function fields and their extensions) #23193
 (some_elements() should be nontrivial 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.
Change History (60)
comment:1 Changed 4 years ago by
 Description modified (diff)
comment:2 Changed 4 years ago by
 Description modified (diff)
comment:3 Changed 4 years ago by
 Description modified (diff)
comment:4 Changed 4 years ago by
 Description modified (diff)
comment:5 Changed 4 years ago by
 Description modified (diff)
comment:6 Changed 4 years ago by
 Description modified (diff)
comment:7 Changed 4 years ago by
 Description modified (diff)
comment:8 Changed 4 years ago by
 Description modified (diff)
comment:9 Changed 4 years ago by
 Description modified (diff)
comment:10 Changed 4 years ago by
 Description modified (diff)
comment:11 Changed 4 years ago by
 Description modified (diff)
comment:12 Changed 4 years ago by
 Description modified (diff)
comment:13 Changed 4 years ago by
 Description modified (diff)
comment:14 Changed 4 years ago by
 Description modified (diff)
comment:15 Changed 4 years ago by
 Description modified (diff)
comment:16 Changed 4 years ago by
 Description modified (diff)
comment:17 Changed 4 years ago by
 Description modified (diff)
comment:18 Changed 4 years ago by
 Description modified (diff)
comment:19 Changed 4 years ago by
 Description modified (diff)
comment:20 Changed 4 years ago by
 Description modified (diff)
comment:21 Changed 4 years ago by
 Description modified (diff)
comment:22 Changed 4 years ago by
 Description modified (diff)
comment:23 Changed 4 years ago by
 Description modified (diff)
comment:24 Changed 4 years ago by
 Description modified (diff)
comment:25 Changed 4 years ago by
 Description modified (diff)
comment:26 Changed 4 years ago by
 Description modified (diff)
comment:27 Changed 4 years ago by
 Branch set to u/saraedum/a_framework_for_discrete_valuations_in_sage
comment:28 Changed 4 years ago by
 Commit set to 0f615c771cac39a2cce4d54b4fd190f1c84992de
 Keywords sd87 added
comment:29 Changed 4 years ago by
 Commit changed from 0f615c771cac39a2cce4d54b4fd190f1c84992de to 4153ef9b3a920d079437825960d904205fc2ae53
comment:30 Changed 4 years ago by
 Commit changed from 4153ef9b3a920d079437825960d904205fc2ae53 to c0a81c8285b47f6fc89aa34bc125ac474c75f2e9
Branch pushed to git repo; I updated commit sha1. New commits:
c0a81c8  fix function lookup

comment:31 Changed 4 years ago by
 Description modified (diff)
New commits:
c0a81c8  fix function lookup

comment:32 Changed 4 years ago by
 Description modified (diff)
 Work issues set to move references to references file, move README to sage documentation, make sure that valuation() has a lot of the documentation and the factory just references it, remove optional: integrated bits
comment:33 Changed 4 years ago by
 Status changed from new to needs_review
comment:34 Changed 4 years ago by
 Description modified (diff)
comment:35 Changed 4 years ago by
 Description modified (diff)
comment:36 followup: ↓ 38 Changed 4 years ago by
I was reviewing gauss_valuation.py and tried reducing a polynomial using the Gauss valuation induced by the 2adic 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 2adic 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) <ipythoninput1084d78566b468b> in <module>() > 1 v.reduce(h) /projects/da1818ed996d4de6acc6361415b7725d/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
comment:37 followup: ↓ 39 Changed 4 years ago by
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 2adic 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) <ipythoninput12871aadb857663> 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/da1818ed996d4de6acc6361415b7725d/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/da1818ed996d4de6acc6361415b7725d/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
comment:38 in reply to: ↑ 36 Changed 4 years ago by
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 nonintegral elements and x + 1/2 is not integral over Gauss valuation induced by 2adic 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 2adic 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 2adic 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) <ipythoninput1084d78566b468b> in <module>() > 1 v.reduce(h) /projects/da1818ed996d4de6acc6361415b7725d/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
comment:39 in reply to: ↑ 37 Changed 4 years ago by
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 2adic 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) <ipythoninput12871aadb857663> 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/da1818ed996d4de6acc6361415b7725d/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/da1818ed996d4de6acc6361415b7725d/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
comment:40 Changed 4 years ago by
 Description modified (diff)
comment:41 Changed 4 years ago by
 Dependencies set to #21782, #23166, #23167, #21879, #23185, #23203, #23204, #23211, #23188, #21879, #23186, #23191, #21996
comment:42 Changed 4 years ago by
 Dependencies changed from #21782, #23166, #23167, #21879, #23185, #23203, #23204, #23211, #23188, #21879, #23186, #23191, #21996 to #21782, #23166, #23167, #21879, #23185, #23203, #23204, #23211, #23188, #21879, #23186, #23191, #21996, #23190
comment:43 Changed 4 years ago by
 Description modified (diff)
comment:44 Changed 4 years ago by
 Description modified (diff)
comment:45 followup: ↓ 48 Changed 4 years ago by
 Reviewers set to GaYee Park
 Status changed from needs_review to needs_work
Ran the test and found the error:
sage t src/sage/rings/function_field/function_field.py # 7 doctests failed
comment:46 Changed 4 years ago by
 Description modified (diff)
comment:47 Changed 4 years ago by
 Description modified (diff)
 Work issues changed from move references to references file, move README to sage documentation, make sure that valuation() has a lot of the documentation and the factory just references it, remove optional: integrated bits to move references to references file, move README to sage documentation, make sure that valuation() has a lot of the documentation and the factory just references it, remove optional: integrated bits, check that discrete_value_group is still available the same way it was under padics
comment:48 in reply to: ↑ 45 Changed 4 years ago by
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.)
comment:49 Changed 4 years ago by
 Description modified (diff)
 Reviewers changed from GaYee Park to GaYee Park, Stefan Wewers
comment:50 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:51 Changed 4 years ago by
 Description modified (diff)
comment:52 Changed 4 years ago by
 Description modified (diff)
comment:53 Changed 4 years ago by
The following errors are expected. I am working on them.
 sage t warnlong 39.1 src/sage/rings/valuation/limit_valuation.py # 52 doctests failed sage t warnlong 39.1 src/sage/rings/valuation/gauss_valuation.py # 1 doctest failed sage t warnlong 39.1 src/sage/rings/valuation/valuation_space.py # 2 doctests failed sage t warnlong 39.1 src/sage/rings/valuation/mapped_valuation.py # 42 doctests failed sage t warnlong 39.1 src/sage/rings/valuation/valuation.py # 9 doctests failed sage t warnlong 39.1 src/sage/rings/valuation/inductive_valuation.py # 13 doctests failed sage t warnlong 39.1 src/sage/rings/valuation/augmented_valuation.py # 16 doctests failed 
comment:54 Changed 4 years ago by
 Work issues changed from move references to references file, move README to sage documentation, make sure that valuation() has a lot of the documentation and the factory just references it, remove optional: integrated bits, check that discrete_value_group is still available the same way it was under padics to move references to references file, move README to sage documentation, make sure that valuation() has a lot of the documentation and the factory just references it, remove optional: integrated bits, check that discrete_value_group is still available the same way it was under padics, 135 failing doctests
comment:55 Changed 4 years ago by
 Dependencies changed from #21782, #23166, #23167, #21879, #23185, #23203, #23204, #23211, #23188, #21879, #23186, #23191, #21996, #23190 to #21782, #23166, #23167, #21879, #23185, #23203, #23204, #23211, #23188, #21879, #23186, #23191, #21996, #23190, #23495
 Description modified (diff)
 Work issues changed from move references to references file, move README to sage documentation, make sure that valuation() has a lot of the documentation and the factory just references it, remove optional: integrated bits, check that discrete_value_group is still available the same way it was under padics, 135 failing doctests to move references to references file, move README to sage documentation, make sure that valuation() has a lot of the documentation and the factory just references it, remove optional: integrated bits, check that discrete_value_group is still available the same way it was under padics
comment:56 Changed 4 years ago by
 Work issues changed from move references to references file, move README to sage documentation, make sure that valuation() has a lot of the documentation and the factory just references it, remove optional: integrated bits, check that discrete_value_group is still available the same way it was under padics to move references to references file, move README to sage documentation, make sure that valuation() has a lot of the documentation and the factory just references it, remove optional: integrated bits, check that discrete_value_group is still available the same way it was under padics, 135 failing doctests
comment:57 Changed 4 years ago by
 Description modified (diff)
Sorry, I somehow reverted some changes to the ticket description. Not sure how this happened.
comment:58 Changed 4 years ago by
 Work issues changed from move references to references file, move README to sage documentation, make sure that valuation() has a lot of the documentation and the factory just references it, remove optional: integrated bits, check that discrete_value_group is still available the same way it was under padics, 135 failing doctests to move references to references file, move README to sage documentation, make sure that valuation() has a lot of the documentation and the factory just references it, remove optional: integrated bits, check that discrete_value_group is still available the same way it was under padics, 252 failing doctests
comment:59 Changed 4 years ago by
 Description modified (diff)
comment:60 Changed 4 years ago by
 Description modified (diff)
Last 10 new commits:
fix typo in comment
Added a tutorial in the README
move to subdirectory for merging with sage tree
removing gitignore for merge with sage tree
Merge mac_lane infrastructure for discrete valuations into sage
remove mac_lane LICENSE
remove obsolete TODOs
remove monkey patches
move valuation code to valuation/
remove specific valuation code out of valuation/