Opened 4 years ago

Closed 5 months ago

Last modified 5 months ago

#21262 closed enhancement (fixed)

Center related classes and methods in Skew Polynomials

Reported by: arpitdm Owned by:
Priority: major Milestone: sage-9.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) Commit: 5929bf9236f0a80e0ac67c87802027698cd406b7
Dependencies: #13215, #29452, #29517 Stopgaps:

Description (last modified by slelievre)

We propose the addition of the following methods and classes to skew polynomials:

  1. class CenterSkewPolynomial_generic_dense
  2. class SectionSkewPolynomialCenterInjection
  3. class SkewPolynomialCenterInjection
  4. class CenterSkewPolynomialRing
  5. 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 4 years ago by arpitdm

  • Branch set to u/arpitdm/centering_methods_skew_polynomials

comment:2 Changed 4 years ago by arpitdm

  • Commit set to 3d7cd832b429c370bc95ffeb798821c07efbe5ba

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:

9a2fad2merged changes from Tickets 13215 and 21088
eaca253integrated skew polynomial finite field into sage. removed some compile and doctest errors.
7664060removed 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.
a6e93e1added SEEALSO and TODO blocks and made small polishes to the documentation.
130b173improved documentation for skew_polynomials_finite_field.pyx file
15861b9documentation builds successfully.
2d67e0emerging updates
a2c4f06removed unused imports, signal statements. small fixes to documentation.
5547542added karatsuba based methods as is, from the original #13215 ticket
3d7cd83added centering based methods and classes as is, from the original #13215 ticket

comment:3 Changed 4 years ago by caruso

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.

Last edited 4 years ago by caruso (previous) (diff)

comment:4 Changed 4 years ago by arpitdm

  • Authors set to Xavier Caruso

comment:5 Changed 4 years ago by caruso

  • Branch changed from u/arpitdm/centering_methods_skew_polynomials to u/caruso/centering_methods_skew_polynomials

comment:6 Changed 4 years ago by caruso

  • 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:

891ccfaMerge branch 't/21262/centering_methods_skew_polynomials' into integration
dd53bd1Remove inplace methods and Karatsuba
a29393aReplace "finite fields" by "fields with automorphism of finite order"
35f44cbAdded a method reduced_trace

comment:7 Changed 4 years ago by cheuberg

  • Status changed from needs_review to needs_work

branch does not merge.

comment:8 Changed 6 months ago by git

  • Commit changed from 35f44cbe04b0e3b9def006660283aea5b93ee28e to 50e3c5d7bc39b160035988e96489b928499964ce

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

50e3c5dMerge branch 'u/caruso/centering_methods_skew_polynomials' of git://trac.sagemath.org/sage into skew_polynomial_finite_order

comment:9 Changed 6 months ago by git

  • Commit changed from 50e3c5d7bc39b160035988e96489b928499964ce to cde456e67a4466b99169aa600f98a237b6a1d0a2

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

cde456emake things compile and test pass

comment:10 Changed 6 months ago by tscrim

Ready for review again?

comment:11 Changed 6 months ago by caruso

  • Dependencies changed from #13215 to #13215, #29452

Not yet. There are issues with pickling, I'm working on this.

Some of these problems come from issues with Frobenius endomorphisms and embeddings which are fixed in ticket #29452. So meanwhile, I encourage you to review #29452 :-)

comment:12 Changed 6 months ago by git

  • Commit changed from cde456e67a4466b99169aa600f98a237b6a1d0a2 to 75c220a22df68f8dcd320ed32782fd305b67c366

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

2c3beddadd doctests
8f40b0afix pickling for Frobenius endomorphisms
9ea7cfbMerge branch 'pickling_frobenius' into skew_polynomial_finite_order
3989e5cpickling for the centre
cb588b8fix pickling for embeddings
16ce9e3add testsuite
318a179Merge branch 'pickling_frobenius' into skew_polynomial_finite_order
1ce658dfix comparison of morphisms
2598cf2implement a factory
75c220askip test_category

comment:13 Changed 6 months ago by caruso

  • 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 6 months ago by git

  • Commit changed from 75c220a22df68f8dcd320ed32782fd305b67c366 to 11fa8eb4686df083717acca5dbf943f38b1fa8cd

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

c7b937cfix pyflakes
9e4ed51fix non ascii and blocks
11fa8eb100% coverage

comment:15 Changed 6 months ago by tscrim

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 follow-up: Changed 6 months ago by caruso

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 6 months ago by tscrim

Replying to caruso:

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__

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)
<ipython-input-22-ca61107e1024> 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 follow-up: Changed 6 months ago by caruso

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 6 months ago by tscrim

Replying to caruso:

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.

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__?) of SkewPolynomialRing 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 6 months ago by git

  • Commit changed from 11fa8eb4686df083717acca5dbf943f38b1fa8cd to a7a177167432f66158532c375a962395270bc573

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

a7a1771switch back to UniqueRepresentation

comment:21 Changed 6 months ago by caruso

OK. I re-read 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 6 months ago by caruso

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 and CenterSkewPolynomial_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 the center 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 and centre): it's not really useful and it appears to be quite annoying for tab-completion

What's your opinion on these points?

comment:23 Changed 6 months ago by tscrim

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 over-indented.

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 6 months ago by git

  • Commit changed from a7a177167432f66158532c375a962395270bc573 to 49c64bbec75e8f56433e34bd9a7acac55f42607a

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

49c64bbremove class CenterSkewPolynomialRing and add doctest

comment:25 Changed 6 months ago by caruso

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 6 months ago by git

  • Commit changed from 49c64bbec75e8f56433e34bd9a7acac55f42607a to dc6995c787caff6f2add2b73ab056da42c9f847e

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

dc6995cremove CenterSkewPolynomial_generic_dense in pxd

comment:27 follow-up: Changed 6 months ago by tscrim

I think that is a little sketchy because it depends on the order the modules are imported. I would make an explicit top-level 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 6 months ago by slelievre

  • Description modified (diff)
  • Milestone changed from sage-7.4 to sage-9.2

comment:29 Changed 6 months ago by git

  • Commit changed from dc6995c787caff6f2add2b73ab056da42c9f847e to 1c513ffccfe4a6203b9435a2424197674771d72e

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

1c513fffix import

comment:30 in reply to: ↑ 27 ; follow-up: Changed 6 months ago by 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 top-level 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.

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 6 months ago by caruso

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 ; follow-up: Changed 6 months ago by tscrim

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 top-level 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.

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 ; follow-up: Changed 6 months ago by 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.

Well, simply adding

from sage.matrix.matrix_dense cimport Matrix_dense

at the top of skew_polynomial_finite_order.pyx, I get this error what I start sage:

home/xcaruso/sage/local/lib/python3.7/site-packages/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/site-packages/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/site-packages/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/site-packages/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).

Version 0, edited 6 months ago by caruso (next)

comment:34 in reply to: ↑ 33 ; follow-up: Changed 6 months ago by tscrim

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/site-packages/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:

  1. Make the skew polynomial rings a lazy import.
  2. Change the sage.matrix.args to import from the specific files that define ZZ, 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 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.)

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: F5[x][y,\sigma] and then the center is F5[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 6 months ago by git

  • Commit changed from 1c513ffccfe4a6203b9435a2424197674771d72e to 253200fa47a4b1047958f47271ce15af310ba4f5

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

253200fremove obsolete import

comment:36 Changed 6 months ago by git

  • Commit changed from 253200fa47a4b1047958f47271ce15af310ba4f5 to 7e4f15e76f6c52e8eec40f42487451d8dade661d

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

7e4f15echange coercion defaults

comment:37 in reply to: ↑ 34 ; follow-up: Changed 6 months ago by caruso

Replying to tscrim:

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:

  1. Make the skew polynomial rings a lazy import.
  2. Change the sage.matrix.args to import from the specific files that define ZZ, 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: F5[x][y,\sigma] and then the center is F5[x]?

I think not. Because F5[x] coerces to F5[x][y,\sigma] and therefore creation another coercion or conversion map from F5[x] to F5[x][y,\sigma] will raise an error in both cases.

comment:38 in reply to: ↑ 37 ; follow-up: Changed 6 months ago by tscrim

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: F5[x][y,\sigma] and then the center is F5[x]?

I think not. Because F5[x] coerces to F5[x][y,\sigma] and therefore creation another coercion or conversion map from F5[x] to F5[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):

F5[x] => F5[y,\sigma] -> F5[y,\sigma][z,\tau] <= F5[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 6 months ago by git

  • Commit changed from 7e4f15e76f6c52e8eec40f42487451d8dade661d to 1eee2b486e0e18041d5ecc2f1020487f5ad12e28

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

1eee2b4improve error message when coercion/conversion fails for the center

comment:40 in reply to: ↑ 38 ; follow-up: Changed 6 months ago by 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 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 ; follow-up: Changed 6 months ago by tscrim

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 use MatrixSpace, 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 methods order and fixed_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 Fq[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 6 months ago by git

  • Commit changed from 1eee2b486e0e18041d5ecc2f1020487f5ad12e28 to 19c9e67696ab748f00c06cf8628eea18a0fb72b7

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

19c9e67add doctests

comment:43 in reply to: ↑ 41 ; follow-up: Changed 6 months ago by caruso

Replying to tscrim:

Can you also add a test first showing that the conversion to the center Fq[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 ; follow-up: Changed 6 months ago by tscrim

  • 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 Fq[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 ; follow-up: Changed 6 months ago by caruso

  • 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 6 months ago by git

  • Commit changed from 19c9e67696ab748f00c06cf8628eea18a0fb72b7 to 5f3188c5c98a0bd3799f31e3f5178b111ff960be

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

5f3188cdefault variable name for the center

comment:47 in reply to: ↑ 45 Changed 6 months ago by caruso

  • 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 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.

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 6 months ago by tscrim

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 5 months ago by git

  • Commit changed from 5f3188c5c98a0bd3799f31e3f5178b111ff960be to a171b19e873a3f27ce193450ac181884f8e3d74b

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

a171b19typos

comment:50 Changed 5 months ago by caruso

Done.

comment:51 Changed 5 months ago by git

  • Commit changed from a171b19e873a3f27ce193450ac181884f8e3d74b to e8f2b329e126d482fa9d2ea6fe4f17cac8b5f1b2

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

e8f2b32working_center

comment:52 Changed 5 months ago by caruso

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 5 months ago by git

  • Commit changed from e8f2b329e126d482fa9d2ea6fe4f17cac8b5f1b2 to 3db3ff2fc11ef6708f77576573cb94c5b8dbfe78

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

3db3ff2reduced norm of a constant polynomial

comment:54 follow-up: Changed 5 months ago by 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).

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 5 months ago by git

  • Commit changed from 3db3ff2fc11ef6708f77576573cb94c5b8dbfe78 to 329fcad67e4cef699c39f9e93de577111a01d53f

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

329fcaduse tuple instead of list

comment:56 in reply to: ↑ 54 ; follow-up: Changed 5 months ago by 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.)

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 5 months ago by git

  • Commit changed from 329fcad67e4cef699c39f9e93de577111a01d53f to b78d3ef78e1e04ad207b424f2d5fa704c9921185

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

b78d3effix small bug

comment:58 in reply to: ↑ 56 Changed 5 months ago by tscrim

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 try-except? One extra parent for each instance isn't going to make much difference in terms of memory.

comment:59 Changed 5 months ago by caruso

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 5 months ago by git

  • Commit changed from b78d3ef78e1e04ad207b424f2d5fa704c9921185 to f17860f7341273c7528e3e6c1f575e8898c44a76

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

f17860fdeterministic choice of variable names

comment:61 Changed 5 months ago by tscrim

  • 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 5 months ago by caruso

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.

Last edited 5 months ago by caruso (previous) (diff)

comment:63 Changed 5 months ago by caruso

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 5 months ago by git

  • Commit changed from f17860f7341273c7528e3e6c1f575e8898c44a76 to fddbb5e5c4b2af04453c3f1dc993e9a6800f78bd
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

0e15a9ebetter test in register_coercion
e92febeMerge branch 'skew_polynomial_finite_order' into skew_polynomial_finite_order_rc0
fddbb5eexplicit check for no coercion

comment:65 Changed 5 months ago by caruso

  • 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 5 months ago by tscrim

  • Status changed from needs_review to positive_review

comment:67 Changed 5 months ago by caruso

Thanks.

Could you please also give a positive review to #29517 so that all of this could be merged.

comment:68 Changed 5 months ago by git

  • Commit changed from fddbb5e5c4b2af04453c3f1dc993e9a6800f78bd to 5929bf9236f0a80e0ac67c87802027698cd406b7
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

1b1467bmodify a doctest
5929bf9Merge branch 'register_coercion' into skew_polynomial_finite_order_rc0

comment:69 Changed 5 months ago by caruso

  • Status changed from needs_review to positive_review

I give back a positive review to this ticket.

comment:70 Changed 5 months ago by vbraun

  • 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 5 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.1
Note: See TracTickets for help on using tickets.