#21262 closed enhancement (fixed)
Center related classes and methods in Skew Polynomials
Reported by:  arpitdm  Owned by:  

Priority:  major  Milestone:  sage9.1 
Component:  algebra  Keywords:  
Cc:  tscrim, caruso, jsrn, dlucas  Merged in:  
Authors:  Xavier Caruso  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  5929bf9 (Commits, GitHub, GitLab)  Commit:  5929bf9236f0a80e0ac67c87802027698cd406b7 
Dependencies:  #13215, #29452, #29517  Stopgaps: 
Description (last modified by )
We propose the addition of the following methods and classes to skew polynomials:
 class
CenterSkewPolynomial_generic_dense
 class
SectionSkewPolynomialCenterInjection
 class
SkewPolynomialCenterInjection
 class
CenterSkewPolynomialRing
 def center in class
SkewPolynomialRing_general
In addition, we designed a special class SkewPolynomial_finite_order_dense
for dense skew polynomial over fields when the twisting endomorphism has finite order (in which case the centre has finite index). It includes the following methods:
reduced_trace
reduced_norm
is_central
bound
optimal_bound
Note: The original ticket #13215 first introduced this functionality (only for finite fields). That was subsequently modified to support the basic implementation of skew polynomials and the center based methods from that ticket that were removed are being reintroduced here.
Change History (71)
comment:1 Changed 5 years ago by
 Branch set to u/arpitdm/centering_methods_skew_polynomials
comment:2 Changed 5 years ago by
 Commit set to 3d7cd832b429c370bc95ffeb798821c07efbe5ba
comment:3 Changed 5 years ago by
The methods is_central
and optimal_bound
make sense for skew polynomials over any ring, right? So it is a bit weird (according to me) to define them only in the class SkewPolynomial_finite_field_dense
(through *I* very probably do this first).
Similarly the reduced norm makes sense as soon as the twist map has finite order (and in addition I am very interested in using it over a finite extension of Qp). So, I would suggest to move it to the class SkewPolynomial_generic_dense
and to raise ValueError
or TypeError
when the twist map has not finite order.
comment:4 Changed 5 years ago by
comment:5 Changed 5 years ago by
 Branch changed from u/arpitdm/centering_methods_skew_polynomials to u/caruso/centering_methods_skew_polynomials
comment:6 Changed 5 years ago by
 Commit changed from 3d7cd832b429c370bc95ffeb798821c07efbe5ba to 35f44cbe04b0e3b9def006660283aea5b93ee28e
 Dependencies changed from #13215, #21088, #21259 to #13215
 Description modified (diff)
 Status changed from new to needs_review
As I said before, the features provided by this ticket do not only make sense for finite fields but more generally for fields on which the twisting endomorphism has finite order. I then renamed the class SkewPolynomial_finite_field_dense
and called it SkewPolynomial_finite_order_dense
.
Moreover, I polished the code and made all methods work (e.g. some imports were missing).
Ticket ready for review.
New commits:
891ccfa  Merge branch 't/21262/centering_methods_skew_polynomials' into integration

dd53bd1  Remove inplace methods and Karatsuba

a29393a  Replace "finite fields" by "fields with automorphism of finite order"

35f44cb  Added a method reduced_trace

comment:7 Changed 5 years ago by
 Status changed from needs_review to needs_work
branch does not merge.
comment:8 Changed 20 months ago by
 Commit changed from 35f44cbe04b0e3b9def006660283aea5b93ee28e to 50e3c5d7bc39b160035988e96489b928499964ce
Branch pushed to git repo; I updated commit sha1. New commits:
50e3c5d  Merge branch 'u/caruso/centering_methods_skew_polynomials' of git://trac.sagemath.org/sage into skew_polynomial_finite_order

comment:9 Changed 20 months ago by
 Commit changed from 50e3c5d7bc39b160035988e96489b928499964ce to cde456e67a4466b99169aa600f98a237b6a1d0a2
Branch pushed to git repo; I updated commit sha1. New commits:
cde456e  make things compile and test pass

comment:10 Changed 20 months ago by
Ready for review again?
comment:11 Changed 20 months ago by
 Dependencies changed from #13215 to #13215, #29452
comment:12 Changed 20 months ago by
 Commit changed from cde456e67a4466b99169aa600f98a237b6a1d0a2 to 75c220a22df68f8dcd320ed32782fd305b67c366
Branch pushed to git repo; I updated commit sha1. New commits:
2c3bedd  add doctests

8f40b0a  fix pickling for Frobenius endomorphisms

9ea7cfb  Merge branch 'pickling_frobenius' into skew_polynomial_finite_order

3989e5c  pickling for the centre

cb588b8  fix pickling for embeddings

16ce9e3  add testsuite

318a179  Merge branch 'pickling_frobenius' into skew_polynomial_finite_order

1ce658d  fix comparison of morphisms

2598cf2  implement a factory

75c220a  skip test_category

comment:13 Changed 20 months ago by
 Status changed from needs_work to needs_review
There are still some issues with _test_category
for the embedding Z(K[X;theta]) > K[X;theta]
and its section. But I don't know how to fix it (I poorly understand the mecanism of categories), so I skip the test :). If you know how one has to fix this, please teach me.
comment:14 Changed 20 months ago by
 Commit changed from 75c220a22df68f8dcd320ed32782fd305b67c366 to 11fa8eb4686df083717acca5dbf943f38b1fa8cd
comment:15 Changed 20 months ago by
I am a strong 1 on using UniqueFactory
in place of UniqueRepresentation
. All of that code should be in SkewPolynomialRing_general
, and it would be better to make it a __classcall_private__
so you don't have to handle the element_class
in the key and the input data is only normalized on the main entry point. Actually, I don't immediately see the need for this and why it cannot just be set in subclasses...
You can also do away with the self._polynomial_class
attribute in place of self.Element
.
For the coercions, it probably would be better to use
center_inject.register_as_coercion()
There also is a new mechanism for doing base ring injections. See #29247 and #19225. So you should use
def _coerce_map_from_base_ring(self):
comment:16 followup: ↓ 17 Changed 20 months ago by
I have no problem with switching back to UniqueRepresentation
but why don't you like UniqueFactory
? It seems that it offers more flexibility and, at least for me, it is more comprehensible than __classcall__
comment:17 in reply to: ↑ 16 Changed 20 months ago by
Replying to caruso:
I have no problem with switching back to
UniqueRepresentation
but why don't you likeUniqueFactory
? It seems that it offers more flexibility and, at least for me, it is more comprehensible than__classcall__
Many reasons. You don't need the flexibility of UniqueFactory
. It spreads out the implementation, entry point, and functionality. For instance, the entry point is a separate class from the actual object, and the unpickling is not handled within either object. Since the implementation is separate from the entry point, you get this:
sage: F.<x,y> = FreeAlgebra(QQ) sage: isinstance(F, FreeAlgebra)  TypeError Traceback (most recent call last) <ipythoninput22ca61107e1024> in <module>() > 1 isinstance(F, FreeAlgebra) TypeError: isinstance() arg 2 must be a type or tuple of types
This makes code maintenance harder since there is no indication within the particular class that it should have the unique representation behavior. I find more black magic is involved with UniqueFactory
than UniqueRepresentation
. I don't see what is harder to comprehend either; both require someone telling you about the magic. You have to implement a __reduce__
, which if you are not careful and feed back into the factory could make copies (which is a bug IMO, but an easy one to introduce). The behavior is not inherited by subclasses automatically.
TL;DR: IMHO it makes it more complicated than it needs to be for no benefit.
comment:18 followup: ↓ 19 Changed 20 months ago by
Before this ticket, SkewPolynomialRing
was a function (the constructor) and not the class. So, the behaviour you reported with FreeAlgebra
also applies to skew polynomials. So, do you mean that we should put all the code normalizing entries in the method __classcall__
(or __new__
?) of SkewPolynomialRing
and, especially, let this code return an instance of a subclass if necessary?
comment:19 in reply to: ↑ 18 Changed 20 months ago by
Replying to caruso:
Before this ticket,
SkewPolynomialRing
was a function (the constructor) and not the class. So, the behaviour you reported withFreeAlgebra
also applies to skew polynomials.
I don't like the previous code with it being a separate function and would want to change that.
So, do you mean that we should put all the code normalizing entries in the method
__classcall__
(or__new__
?) ofSkewPolynomialRing
and, especially, let this code return an instance of a subclass if necessary?
Yes that is correct, and make it a __classcall_private__
so there is only one normalization (which will also let the subclasses do their own normalization independently). You don't need to modify anything with __new__
. You can return a subclass object. This is done in a number of places in the combinatorics code.
comment:20 Changed 20 months ago by
 Commit changed from 11fa8eb4686df083717acca5dbf943f38b1fa8cd to a7a177167432f66158532c375a962395270bc573
Branch pushed to git repo; I updated commit sha1. New commits:
a7a1771  switch back to UniqueRepresentation

comment:21 Changed 20 months ago by
OK. I reread the documentation in sage.strcture.unique_representation
and I now understand better the mecanism behind __classcall__
and __classcall_private__
. I'm still not entirely convinced that it's better/simpler than UniqueFactory
(especially I'm still not that confortable with using metaclasses), but I followed your recommandations.
comment:22 Changed 20 months ago by
Also, today, I don't completely agree with the design choices I made about 8 years ago, e.g.:
 now, I don't think that it's a good idea to have specific classes for the centre (namely
CenterSkewPolynomialRing
andCenterSkewPolynomial_generic_dense
) because they don't inherit extra methods when the base ring has extra structures (for example, if we are working over a finite field, the center is a polynomial ring over a finite field for which more functionalities are available); on the other hand, the benefit of having a separate class is (I think) to provide tools to handle coercion properly (since currently the center remembers the skew ring); a solution could be to let thecenter
method return a classical polynomial ring together with the embedding into the skew ring, I don't know  on a related note, I don't think that it's a good idea either to use the name
(x^r)
for the name of the central variable because it is not alphanumeric, which could be the source of many problems, e.g.:sage: k.<a> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: Z = S.center() sage: Z.change_ring(k) Traceback (most recent call last): ... ValueError: variable name '(x^3)' is not alphanumeric
 I'm not sure that it's a good idea to have two spellings for the same method (
center
andcentre
): it's not really useful and it appears to be quite annoying for tabcompletion
What's your opinion on these points?
comment:23 Changed 20 months ago by
Thank you. I appreciate you going back to UniqueRepresentation
here. Actually, below reminded me of another good thing: you don't get either duplicate or two separate documentations for the same object. Here are my answers to your questions.
1  It might be worthwhile to make a façade parent for the center, which can have some extra methods attached to it by the elements are just normal polynomials. I guess it depends on how much extra features you want the center to have. If it is just about how they retract to the full skew polynomial ring, then I would just do as you suggest and return a normal polynomial ring over a finite field and implement the to/from maps in the skew poly ring.
2  I concur. Maybe xpr
for the variables?
3  I agree. We generally use the American spellings in Sage.
Some of these comments below might not apply as you refactor the code.
Another suggestion I have would be moving the doc from SkewPolynomial_finite_order_dense.__init__
to the class level. This way you could also add a test for the __init__
that runs the TestSuite(foo).run()
. This also makes it easier in the compiled doc and using ?
.
We check that the reduced trace is additive: +We check that the reduced trace is additive::
`K[X,\sigma] / K[X,\sigma]*P` (which is a `K`vector space +`K[X,\sigma] / K[X,\sigma] P` (which is a `K`vector space
(At least, I think you don't want the *
here in the latex result, but maybe you do.)
The EXAMPLES of VARIABLE NAME CONTEXT::
block is overindented.
The __classcall_private__
will need some doctests that check that it handles the uniqueness well or raises errors in cases you want it to.
A good option might be
category = Algebras(base_ring).or_subcategory(category)
as this handles None
as an input in the way you'd expect and makes sure nobody passes something strange like Manifolds()
.
You still have self._polynomial_class
in the center class.
See comment:15 with _coerce_map_from_base_ring
. This could simplify your CenterSkewPolynomialRing.__init__
implementation.
comment:24 Changed 20 months ago by
 Commit changed from a7a177167432f66158532c375a962395270bc573 to 49c64bbec75e8f56433e34bd9a7acac55f42607a
Branch pushed to git repo; I updated commit sha1. New commits:
49c64bb  remove class CenterSkewPolynomialRing and add doctest

comment:25 Changed 20 months ago by
OK, I addressed all your comments. I finally decided to remove the class CenterSkewPolynomialRing
and to add the keyword argument coerce
to the method center
to let the user choose if he/she wants to set a coercion map or not.
I don't understand why:
Element = sage.rings.polynomial.skew_polynomial_finite_order.SkewPolynomial_finite_order_dense
fails (see line 1301 of skew_polynomial_ring.py
), giving the error
AttributeError: module 'sage.rings.polynomial' has no attribute 'skew_polynomial_finite_order'
Any idea?
comment:26 Changed 20 months ago by
 Commit changed from 49c64bbec75e8f56433e34bd9a7acac55f42607a to dc6995c787caff6f2add2b73ab056da42c9f847e
Branch pushed to git repo; I updated commit sha1. New commits:
dc6995c  remove CenterSkewPolynomial_generic_dense in pxd

comment:27 followup: ↓ 30 Changed 20 months ago by
I think that is a little sketchy because it depends on the order the modules are imported. I would make an explicit toplevel import of
from sage.rings.polynomial.skew_polynomial_finite_order import SkewPolynomial_finite_order_dense
and then do Element = SkewPolynomial_finite_order_dense
. There shouldn't be a circular dependency as the element classes (usually) do not need to know generically about the precise parent class, and the methods that do can just import it locally.
Beyond that, it looks good. Thank you. I do have one last question: Why is the default for the center to not have it as a coercion map?
comment:28 Changed 20 months ago by
 Description modified (diff)
 Milestone changed from sage7.4 to sage9.2
comment:29 Changed 20 months ago by
 Commit changed from dc6995c787caff6f2add2b73ab056da42c9f847e to 1c513ffccfe4a6203b9435a2424197674771d72e
Branch pushed to git repo; I updated commit sha1. New commits:
1c513ff  fix import

comment:30 in reply to: ↑ 27 ; followup: ↓ 32 Changed 20 months ago by
Replying to tscrim:
I think that is a little sketchy because it depends on the order the modules are imported. I would make an explicit toplevel import of
from sage.rings.polynomial.skew_polynomial_finite_order import SkewPolynomial_finite_order_denseand then do
Element = SkewPolynomial_finite_order_dense
. There shouldn't be a circular dependency as the element classes (usually) do not need to know generically about the precise parent class, and the methods that do can just import it locally.
There was actually circular dependencies passing through sage.matrix.matrix_dense.Matrix_dense
but I removed this import and rewrote the methods _matphir_c
and _matmul_c
accordingly.
Beyond that, it looks good. Thank you. I do have one last question: Why is the default for the center to not have it as a coercion map?
I've hesitated but I think it's safer like this. The reason is that if the user has already created (in the same session) a polynomial ring over the fixed field with the same variable name, then his ring will be automatically endowed with my coercion map, which could be not desired.
comment:31 Changed 20 months ago by
Another question: the patchbot reports:
startup_modules Failed
I don't know what it means exactly (is it annoying?) but I was wondering if using __classcall__
(instead of a constructor or a factory) couldn't slow down the startup since it a priori makes more imports.
comment:32 in reply to: ↑ 30 ; followup: ↓ 33 Changed 20 months ago by
Replying to caruso:
Replying to tscrim:
I think that is a little sketchy because it depends on the order the modules are imported. I would make an explicit toplevel import of
from sage.rings.polynomial.skew_polynomial_finite_order import SkewPolynomial_finite_order_denseand then do
Element = SkewPolynomial_finite_order_dense
. There shouldn't be a circular dependency as the element classes (usually) do not need to know generically about the precise parent class, and the methods that do can just import it locally.There was actually circular dependencies passing through
sage.matrix.matrix_dense.Matrix_dense
but I removed this import and rewrote the methods_matphir_c
and_matmul_c
accordingly.
Can you explain a bit more about the circular import you got? It seems like there shouldn't be one and I would think removing the matrix_dense
import is not the best strategy.
Beyond that, it looks good. Thank you. I do have one last question: Why is the default for the center to not have it as a coercion map?
I've hesitated but I think it's safer like this. The reason is that if the user has already created (in the same session) a polynomial ring over the fixed field with the same variable name, then his ring will be automatically endowed with my coercion map, which could be not desired.
I don't see why they would reasonably have a separate polynomial ring that would not behave like the center, call the center, but then do something coerce into the skew polynomial ring. That sounds like a logic bug. Being able to turn off the coercion is good to find this and fix it, but I don't see how this would be applied incorrectly and not be a true bug. Plus I would naively expect this coercion map to be there as it is suppose to represent a subobject.
You can ignore the startup modules as that is not always the most reliable patchbot module. (It passed on one of the patchbot reports.) The bigger issue is the docbuild failure.
comment:33 in reply to: ↑ 32 ; followup: ↓ 34 Changed 20 months ago by
Replying to tscrim:
Can you explain a bit more about the circular import you got? It seems like there shouldn't be one and I would think removing the
matrix_dense
import is not the best strategy.
Well, simply adding
from sage.matrix.matrix_dense cimport Matrix_dense
at the top of skew_polynomial_finite_order.pyx
, I get this error when I start sage:
home/xcaruso/sage/local/lib/python3.7/sitepackages/sage/rings/polynomial/skew_polynomial_ring.py in SkewPolynomialRing_finite_order() 1292 :mod:`sage.rings.polynomial.skew_polynomial_finite_order` 1293 """ > 1294 import sage.rings.polynomial.skew_polynomial_finite_order global sage.rings.polynomial.skew_polynomial_finite_order = undefined 1295 Element = sage.rings.polynomial.skew_polynomial_finite_order.SkewPolynomial_finite_order_dense 1296 /home/xcaruso/sage/local/lib/python3.7/sitepackages/sage/matrix/matrix0.pxd in init sage.rings.polynomial.skew_polynomial_finite_order (build/cythonized/sage/rings/polynomial/skew_polynomial_finite_order.c:9134)() 16 cimport sage.structure.mutability 17 > 18 cdef class Matrix(sage.structure.element.Matrix): global cdef = undefined global Matrix = undefined global sage.structure.element.Matrix = undefined 19 # Properties of any matrix (plus _parent, inherited from base class) 20 cdef public object _subdivisions /home/xcaruso/sage/local/lib/python3.7/sitepackages/sage/matrix/__init__.py in <module>() 1 # Resolve a cyclic import > 2 import sage.matrix.args global sage.matrix.args = undefined /home/xcaruso/sage/local/lib/python3.7/sitepackages/sage/matrix/args.pyx in init sage.matrix.args (build/cythonized/sage/matrix/args.c:21255)() 22 23 from .matrix_space import MatrixSpace > 24 from sage.rings.all import ZZ, RDF, CDF global sage.rings.all = undefined global ZZ = Integer Ring global RDF = Real Double Field global CDF = undefined 25 from sage.structure.coerce cimport (coercion_model, 26 is_numpy_type, py_scalar_parent) ImportError: cannot import name CDF
I don't see why they would reasonably have a separate polynomial ring that would not behave like the center, call the center, but then do something coerce into the skew polynomial ring.
Well, it's a common operator to create a polynomial ring over a finite field (at least for me). So I easily imagine I create a polynomial ring over GF(5)
for some reason and, later on in the same session (for some related reason), create a skew polynomial ring over GF(5^3)
and compute its center. In that case, I won't probably want the two constructions to implicitely interfere.
(But I confess that coercion into the skew ring won't probably cause many troubles.)
You can ignore the startup modules as that is not always the most reliable patchbot module. (It passed on one of the patchbot reports.) The bigger issue is the docbuild failure.
It's fixed (hopefully).
comment:34 in reply to: ↑ 33 ; followup: ↓ 37 Changed 20 months ago by
Replying to caruso:
Replying to tscrim:
Can you explain a bit more about the circular import you got? It seems like there shouldn't be one and I would think removing the
matrix_dense
import is not the best strategy.[snip] /home/xcaruso/sage/local/lib/python3.7/sitepackages/sage/matrix/args.pyx in init sage.matrix.args (build/cythonized/sage/matrix/args.c:21255)() 22 23 from .matrix_space import MatrixSpace > 24 from sage.rings.all import ZZ, RDF, CDF global sage.rings.all = undefined global ZZ = Integer Ring global RDF = Real Double Field global CDF = undefined 25 from sage.structure.coerce cimport (coercion_model, 26 is_numpy_type, py_scalar_parent) ImportError: cannot import name CDF
So the issue comes from the call to sage.rings.all
rather than the individual files that define these fields. The sage.rings.all
calls sage.rings.polynomials.all
, which then tries to import the skew polynomial ring, and hence the cycle. So to me there are two "good" ways to break this:
 Make the skew polynomial rings a lazy import.
 Change the
sage.matrix.args
to import from the specific files that defineZZ, RDF, CDF
:from sage.rings.integer_ring import ZZ from sage.rings.real_double import RDF from sage.rings.complex_double import CDF
I don't see why they would reasonably have a separate polynomial ring that would not behave like the center, call the center, but then do something coerce into the skew polynomial ring.
Well, it's a common operator to create a polynomial ring over a finite field (at least for me). So I easily imagine I create a polynomial ring over
GF(5)
for some reason and, later on in the same session (for some related reason), create a skew polynomial ring overGF(5^3)
and compute its center. In that case, I won't probably want the two constructions to implicitely interfere. (But I confess that coercion into the skew ring won't probably cause many troubles.)
That is the point. This will not cause any problems in the computations that you would do. This wouldn't create some strange different coercion path or override an action that otherwise would be there. Could this be a problem though: F_{5}[x][y,\sigma] and then the center is F_{5}[x]?
You can ignore the startup modules as that is not always the most reliable patchbot module. (It passed on one of the patchbot reports.) The bigger issue is the docbuild failure.
It's fixed (hopefully).
Seems like you got it.
comment:35 Changed 20 months ago by
 Commit changed from 1c513ffccfe4a6203b9435a2424197674771d72e to 253200fa47a4b1047958f47271ce15af310ba4f5
Branch pushed to git repo; I updated commit sha1. New commits:
253200f  remove obsolete import

comment:36 Changed 20 months ago by
 Commit changed from 253200fa47a4b1047958f47271ce15af310ba4f5 to 7e4f15e76f6c52e8eec40f42487451d8dade661d
Branch pushed to git repo; I updated commit sha1. New commits:
7e4f15e  change coercion defaults

comment:37 in reply to: ↑ 34 ; followup: ↓ 38 Changed 20 months ago by
Replying to tscrim:
So the issue comes from the call to
sage.rings.all
rather than the individual files that define these fields. Thesage.rings.all
callssage.rings.polynomials.all
, which then tries to import the skew polynomial ring, and hence the cycle. So to me there are two "good" ways to break this:
 Make the skew polynomial rings a lazy import.
 Change the
sage.matrix.args
to import from the specific files that defineZZ, RDF, CDF
:from sage.rings.integer_ring import ZZ from sage.rings.real_double import RDF from sage.rings.complex_double import CDF
If you agree, I prefer delaying this for another ticket as it touches other parts of sage.
(But I confess that coercion into the skew ring won't probably cause many troubles.)
That is the point. This will not cause any problems in the computations that you would do. This wouldn't create some strange different coercion path or override an action that otherwise would be there.
Yes, probably; I let coerce=True
to be the default.
Could this be a problem though: F_{5}[x][y,\sigma] and then the center is F_{5}[x]?
I think not. Because F_{5}[x] coerces to F_{5}[x][y,\sigma] and therefore creation another coercion or conversion map from F_{5}[x] to F_{5}[x][y,\sigma] will raise an error in both cases.
comment:38 in reply to: ↑ 37 ; followup: ↓ 40 Changed 20 months ago by
Replying to caruso:
Replying to tscrim: If you agree, I prefer delaying this for another ticket as it touches other parts of sage.
I would rather do it either on this ticket or as a dependency. I can do this as a dependency if you agree.
(But I confess that coercion into the skew ring won't probably cause many troubles.)
That is the point. This will not cause any problems in the computations that you would do. This wouldn't create some strange different coercion path or override an action that otherwise would be there.
Yes, probably; I let
coerce=True
to be the default.
Thank you.
Could this be a problem though: F_{5}[x][y,\sigma] and then the center is F_{5}[x]?
I think not. Because F_{5}[x] coerces to F_{5}[x][y,\sigma] and therefore creation another coercion or conversion map from F_{5}[x] to F_{5}[x][y,\sigma] will raise an error in both cases.
Ah, right, very good point. However, that would be a strange error message for the uninformed, so there probably should be a .. WARNING::
about this and to tell the user that they should choose a different variable name than one in the base ring. Here is another potential situation (although more contrived):
F_{5}[x] => F_{5}[y,\sigma] > F_{5}[y,\sigma][z,\tau] <= F_{5}[x]
where > denotes base ring injection and => is the center coercion. Perhaps this is impossible because I have forgotten a requirement of the base ring, but I don't think this is a likely enough thing to happen to warrant changing the default.
comment:39 Changed 20 months ago by
 Commit changed from 7e4f15e76f6c52e8eec40f42487451d8dade661d to 1eee2b486e0e18041d5ecc2f1020487f5ad12e28
Branch pushed to git repo; I updated commit sha1. New commits:
1eee2b4  improve error message when coercion/conversion fails for the center

comment:40 in reply to: ↑ 38 ; followup: ↓ 41 Changed 20 months ago by
Replying to tscrim:
If you agree, I prefer delaying this for another ticket as it touches other parts of sage.
I would rather do it either on this ticket or as a dependency. I can do this as a dependency if you agree.
Actually, I'm happier with my new implementation of _matphir_c
and _matmul_c
which doesn't use MatrixSpace
, and so the faulty import is no longer required.
Ah, right, very good point. However, that would be a strange error message for the uninformed, so there probably should be a
.. WARNING::
about this and to tell the user that they should choose a different variable name than one in the base ring.
I changed the error message if the creation of the coercion/conversion map fails (although I think that this case won't happen shortly because the method center
is only available when the twisting map implements the methods order
and fixed_points
, which is only the case for Frobenius endomorphisms so far).
comment:41 in reply to: ↑ 40 ; followup: ↓ 43 Changed 20 months ago by
Replying to caruso:
Replying to tscrim:
If you agree, I prefer delaying this for another ticket as it touches other parts of sage.
I would rather do it either on this ticket or as a dependency. I can do this as a dependency if you agree.
Actually, I'm happier with my new implementation of
_matphir_c
and_matmul_c
which doesn't useMatrixSpace
, and so the faulty import is no longer required.
Okay...but I don't really understand why. However, this is your code, so if this is what you want, then so be it.
Ah, right, very good point. However, that would be a strange error message for the uninformed, so there probably should be a
.. WARNING::
about this and to tell the user that they should choose a different variable name than one in the base ring.I changed the error message if the creation of the coercion/conversion map fails (although I think that this case won't happen shortly because the method
center
is only available when the twisting map implements the methodsorder
andfixed_points
, which is only the case for Frobenius endomorphisms so far).
Thank you. Sorry, just a few more tests I would like to see added. This should be it. Can you also add a test first showing that the conversion to the center F_{q}[x] followed by a coercion works to the same center, as well as a similar test in the other way? Also, can you also add one to the same polynomial ring from a different skew polynomial ring (with, say, a different variable)?
comment:42 Changed 20 months ago by
 Commit changed from 1eee2b486e0e18041d5ecc2f1020487f5ad12e28 to 19c9e67696ab748f00c06cf8628eea18a0fb72b7
Branch pushed to git repo; I updated commit sha1. New commits:
19c9e67  add doctests

comment:43 in reply to: ↑ 41 ; followup: ↓ 44 Changed 20 months ago by
Replying to tscrim:
Can you also add a test first showing that the conversion to the center F_{q}[x] followed by a coercion works to the same center
Actually it doesn't because it's not allowed (for safety, as explained in the documention of the method sage.structure.parent.Parent.register_coercion
) by the general coercion mecanism.
So, I added a doctest showing that this raises an error.
as well as a similar test in the other way? Also, can you also add one to the same polynomial ring from a different skew polynomial ring (with, say, a different variable)?
Done.
comment:44 in reply to: ↑ 43 ; followup: ↓ 45 Changed 20 months ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
Replying to caruso:
Replying to tscrim:
Can you also add a test first showing that the conversion to the center F_{q}[x] followed by a coercion works to the same center
Actually it doesn't because it's not allowed (for safety, as explained in the documention of the method
sage.structure.parent.Parent.register_coercion
) by the general coercion mecanism. So, I added a doctest showing that this raises an error.
I am not too surprised it does that, but I would have thought Sage would allow the promotion of a conversion map to a coercion. Well, at least it is documented so users are aware of it.
as well as a similar test in the other way? Also, can you also add one to the same polynomial ring from a different skew polynomial ring (with, say, a different variable)?
Done.
Thank you.
comment:45 in reply to: ↑ 44 ; followup: ↓ 47 Changed 20 months ago by
 Status changed from positive_review to needs_work
Replying to tscrim:
I am not too surprised it does that, but I would have thought Sage would allow the promotion of a conversion map to a coercion.
I agree that it could be nice to have this in sage; a possibility could be to implement a new method promote_to_coercion(self, ring)
in the Parent
class.
If you agree, I propose to open another ticket to discuss this.
Also, thinking again at all of this, I am worried by the following: if the default variable name z
leads to an error for some reason, then the methods reduced_trace
and reduced_norm
won't work. At least, I think we should add a keyword argument var
in those methods to let the user specify the variable name he wants. Going further, I also think that it would be nice to allow for customizing the default central variable name. Maybe, we can have a method for this and/or update it each time a new center (i.e. with a new variable name) is created.
comment:46 Changed 20 months ago by
 Commit changed from 19c9e67696ab748f00c06cf8628eea18a0fb72b7 to 5f3188c5c98a0bd3799f31e3f5178b111ff960be
Branch pushed to git repo; I updated commit sha1. New commits:
5f3188c  default variable name for the center

comment:47 in reply to: ↑ 45 Changed 20 months ago by
 Status changed from needs_work to needs_review
Replying to caruso:
Also, thinking again at all of this, I am worried by the following: if the default variable name
z
leads to an error for some reason, then the methodsreduced_trace
andreduced_norm
won't work. At least, I think we should add a keyword argumentvar
in those methods to let the user specify the variable name he wants. Going further, I also think that it would be nice to allow for customizing the default central variable name. Maybe, we can have a method for this and/or update it each time a new center (i.e. with a new variable name) is created.
I just pushed an implementation of this.
And I also deciced to abandon the option coerce=False
because it causes too much troubles (especially in the methods reduced_norm
and reduced_trace
which are both calling center
, it was not clear which value should be passed in).
comment:48 Changed 20 months ago by
I agree that it is causing too many problems.
You can get rid of the gender issue by
However, the user can speciy a different variable name if he/she wish:: +However, the user can specify a different variable name if desired::
(Note also the typo.)
I think you should explain a little bit more about default
in the INPUT:
block, perhaps saying something like if ``True`` then set the default variable name for the cener to be ``name``
comment:49 Changed 20 months ago by
 Commit changed from 5f3188c5c98a0bd3799f31e3f5178b111ff960be to a171b19e873a3f27ce193450ac181884f8e3d74b
Branch pushed to git repo; I updated commit sha1. New commits:
a171b19  typos

comment:50 Changed 20 months ago by
Done.
comment:51 Changed 20 months ago by
 Commit changed from a171b19e873a3f27ce193450ac181884f8e3d74b to e8f2b329e126d482fa9d2ea6fe4f17cac8b5f1b2
Branch pushed to git repo; I updated commit sha1. New commits:
e8f2b32  working_center

comment:52 Changed 20 months ago by
Hmm, there was still a problem:
sage: k.<a> = GF(7^4) sage: phi = k.frobenius_endomorphism() sage: S.<x> = k['x', phi] sage: (x^4).is_central() True sage: Z.<u> = S.center(); Z Univariate Polynomial Ring in u over Finite Field of size 7 sage: S.center() Univariate Polynomial Ring in z over Finite Field of size 7
On the last line, the variable name is z
but it should be u
. The reason is that the call to is_central
creates a center and then sets the default variable name.
My last commit fixes this.
comment:53 Changed 20 months ago by
 Commit changed from e8f2b329e126d482fa9d2ea6fe4f17cac8b5f1b2 to 3db3ff2fc11ef6708f77576573cb94c5b8dbfe78
Branch pushed to git repo; I updated commit sha1. New commits:
3db3ff2  reduced norm of a constant polynomial

comment:54 followup: ↓ 56 Changed 20 months ago by
This is dangerous:
sage: a.reduced_norm(var=False) [4, 0, 4, 1]
You could modify a cached value. Either return a copy or make the _norm
a tuple (I would do the latter).
Perhaps instead of a random variable name, you choose something specific that is likely not to be used (except by the most heinous of users), like DUMMY_SKEW_CENTER_VAR
?
comment:55 Changed 20 months ago by
 Commit changed from 3db3ff2fc11ef6708f77576573cb94c5b8dbfe78 to 329fcad67e4cef699c39f9e93de577111a01d53f
Branch pushed to git repo; I updated commit sha1. New commits:
329fcad  use tuple instead of list

comment:56 in reply to: ↑ 54 ; followup: ↓ 58 Changed 20 months ago by
Replying to tscrim:
This is dangerous:
sage: a.reduced_norm(var=False) [4, 0, 4, 1]You could modify a cached value. Either return a copy or make the
_norm
a tuple (I would do the latter).
Good point. I made _norm
a tuple as you suggested. (But then I return a tuple instead of a list, I don't know whether it's good or bad.)
Perhaps instead of a random variable name, you choose something specific that is likely not to be used (except by the most heinous of users), like
DUMMY_SKEW_CENTER_VAR
?
I can certainly do it. But what's the benefit?
comment:57 Changed 20 months ago by
 Commit changed from 329fcad67e4cef699c39f9e93de577111a01d53f to b78d3ef78e1e04ad207b424f2d5fa704c9921185
Branch pushed to git repo; I updated commit sha1. New commits:
b78d3ef  fix small bug

comment:58 in reply to: ↑ 56 Changed 20 months ago by
Replying to caruso:
Replying to tscrim:
This is dangerous:
sage: a.reduced_norm(var=False) [4, 0, 4, 1]You could modify a cached value. Either return a copy or make the
_norm
a tuple (I would do the latter).Good point. I made
_norm
a tuple as you suggested. (But then I return a tuple instead of a list, I don't know whether it's good or bad.)
I don't think it makes a difference other than 1 line for other users if they want to modify it.
Perhaps instead of a random variable name, you choose something specific that is likely not to be used (except by the most heinous of users), like
DUMMY_SKEW_CENTER_VAR
?I can certainly do it. But what's the benefit?
It won't have random failures. For example, it could choose a variable that is already used one time then work the next. With a specific variable like this, there is almost surely no chance of it being selected. Granted, 10 random letters is highly unlikely to produce something used. The other argument would be consistency across sessions.
Also, don't you want to actually create the _working_center
in this case? Actually, why not just use this fixed (dummy) variable as _working_center
instead of the current tryexcept? One extra parent for each instance isn't going to make much difference in terms of memory.
comment:59 Changed 20 months ago by
Actually, I see a problem with always using the same variable name for the "working" center.
Assume that, for some reason, somebody needs to implement a method like this in the class SkewPolynomialRing
(or one of its derivative):
def my_method(self): center = self._working_center z = center.gen() # z = DUMMY_SKEW_VAR_CENTER ring = center.quo(z^2 + 1) twist = ring.hom([z]) skew.<T> = SkewPolynomialRing(ring, twist) ...
and assume that the user runs the following session:
sage: k.<a> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x', Frob] sage: S.my_method()
Then, when S
is defined, Sage creates the ring GF(5)[DUMMY_SKEW_CENTER_VAR]
together with a coercion map into S
. Now when we call my_method
, the fixed point of twist
is again GF(5)
and so the call to SkewPolynomialRing
recreates the ring GF(5)[DUMMY_SKEW_CENTER_VAR]
and now set a coercion map into skew
, taking DUMMY_SKEW_CENTER_VAR
to T^2
. But we also have coercion maps GF(5)[DUMMY_SKEW_CENTER_VAR] > ring > skew
where the composite maps DUMMY_SKEW_CENTER_VAR
to z
...
I confess that, currently, this bug can't happen because twist
does not have a method order
but it clearly shows that using always the same variable name for the center may cause subtle troubles.
Below, I propose a new implementation avoiding random choices of variable names (and thus being more canonical and reproducible in some sense).
comment:60 Changed 20 months ago by
 Commit changed from b78d3ef78e1e04ad207b424f2d5fa704c9921185 to f17860f7341273c7528e3e6c1f575e8898c44a76
Branch pushed to git repo; I updated commit sha1. New commits:
f17860f  deterministic choice of variable names

comment:61 Changed 20 months ago by
 Status changed from needs_review to positive_review
Okay, that is a reasonable enough thing to happen, and I am okay with this solution. Thank you.
comment:62 Changed 20 months ago by
I made some experiments, demonstrating that the coercion system in Sage does not perform all basic checks. Indeed, compare the two following sessions (I've just permuted the two last lines):
sage: A.<t> = GF(3)[] sage: P = t^5 + 2*t^3 + 2*t^2 + 3*t + 2 sage: K = A.quo(P) sage: L.<a> = K.extension(x^2 + 1) sage: phi = A.hom([a]) sage: phi.register_as_coercion() sage: L.coerce_map_from(A) Ring morphism: From: Univariate Polynomial Ring in t over Finite Field of size 3 To: Univariate Quotient Polynomial Ring in a over Univariate Quotient Polynomial Ring in tbar over Finite Field of size 3 with modulus t^5 + 2*t^3 + 2*t^2 + 2 with modulus a^2 + 1 Defn: t > a
sage: A.<t> = GF(3)[] sage: P = t^5 + 2*t^3 + 2*t^2 + 3*t + 2 sage: K = A.quo(P) sage: L.<a> = K.extension(x^2 + 1) sage: phi = A.hom([a]) sage: L.coerce_map_from(A) Coercion map: From: Univariate Polynomial Ring in t over Finite Field of size 3 To: Univariate Quotient Polynomial Ring in a over Univariate Quotient Polynomial Ring in tbar over Finite Field of size 3 with modulus t^5 + 2*t^3 + 2*t^2 + 2 with modulus a^2 + 1 sage: phi.register_as_coercion() Traceback (most recent call last): ... AssertionError: coercion from Univariate Polynomial Ring in t over Finite Field of size 3 to Univariate Quotient Polynomial Ring in a over Univariate Quotient Polynomial Ring in tbar over Finite Field of size 3 with modulus t^5 + 2*t^3 + 2*t^2 + 2 with modulus a^2 + 1 already registered or discovered
I don't know if it's a bug in register_as_coercion
or if the user is supposed to check by himself consistency of the coercion model before calling it.
comment:63 Changed 20 months ago by
Maybe the right thing to do is to use to construction over
I've introduced in ticket #21413. However, if so, I perfer delaying this for another ticket.
comment:64 Changed 20 months ago by
 Commit changed from f17860f7341273c7528e3e6c1f575e8898c44a76 to fddbb5e5c4b2af04453c3f1dc993e9a6800f78bd
 Status changed from positive_review to needs_review
comment:65 Changed 20 months ago by
 Dependencies changed from #13215, #29452 to #13215, #29452, #29517
So, I added a test to ensure that no coercion map already exists. (See also ticket #29517)
comment:66 Changed 20 months ago by
 Status changed from needs_review to positive_review
comment:67 Changed 20 months ago by
Thanks.
Could you please also give a positive review to #29517 so that all of this could be merged.
comment:68 Changed 20 months ago by
 Commit changed from fddbb5e5c4b2af04453c3f1dc993e9a6800f78bd to 5929bf9236f0a80e0ac67c87802027698cd406b7
 Status changed from positive_review to needs_review
comment:69 Changed 20 months ago by
 Status changed from needs_review to positive_review
I give back a positive review to this ticket.
comment:70 Changed 20 months ago by
 Branch changed from u/caruso/centering_methods_skew_polynomials to 5929bf9236f0a80e0ac67c87802027698cd406b7
 Resolution set to fixed
 Status changed from positive_review to closed
comment:71 Changed 19 months ago by
 Milestone changed from sage9.2 to sage9.1
Please also note that the current code is more or less just what was in the original patch for #13215 related to Center related methods and classes. No effort has e.g. been made yet to accommodate for changes in #13215 since this addition was factored out.
Last 10 new commits:
merged changes from Tickets 13215 and 21088
integrated skew polynomial finite field into sage. removed some compile and doctest errors.
removed leftpow and rightpow methods from SkewPolynomial_finite_field_dense class because they require the 'bound' method which in turn requires 'center'. this will be added in another separate ticket with the rest of the center stuff.
added SEEALSO and TODO blocks and made small polishes to the documentation.
improved documentation for skew_polynomials_finite_field.pyx file
documentation builds successfully.
merging updates
removed unused imports, signal statements. small fixes to documentation.
added karatsuba based methods as is, from the original #13215 ticket
added centering based methods and classes as is, from the original #13215 ticket