Center related classes and methods in Skew Polynomials

[arpitdm]

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.

Depends on #13215
Depends on #29452
Depends on #29517

CC: @tscrim @xcaruso @johanrosenkilde @sagetrac-dlucas

Component: algebra

Author: Xavier Caruso

Branch/Commit: 5929bf9

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/21262

[arpitdm]

Branch: u/arpitdm/centering_methods_skew_polynomials

[arpitdm]

Commit: 3d7cd83

[arpitdm]

comment:2

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:

9a2fad2	merged changes from Tickets 13215 and 21088
eaca253	integrated skew polynomial finite field into sage. removed some compile and doctest errors.
7664060	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.
a6e93e1	added SEEALSO and TODO blocks and made small polishes to the documentation.
130b173	improved documentation for skew_polynomials_finite_field.pyx file
15861b9	documentation builds successfully.
2d67e0e	merging updates
a2c4f06	removed unused imports, signal statements. small fixes to documentation.
5547542	added karatsuba based methods as is, from the original #13215 ticket
3d7cd83	added centering based methods and classes as is, from the original #13215 ticket

[xcaruso]

comment:3

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.

[arpitdm]

Author: Xavier Caruso

[xcaruso]

Changed branch from u/arpitdm/centering_methods_skew_polynomials to u/caruso/centering_methods_skew_polynomials

[xcaruso]

comment:6

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

[xcaruso]

Changed commit from 3d7cd83 to 35f44cb

[xcaruso]

Changed dependencies from #13215, #21088, #21259 to #13215

[cheuberg]

comment:7

branch does not merge.

[sagetrac-git]

Changed commit from 35f44cb to 50e3c5d

[sagetrac-git]

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

[sagetrac-git]

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

cde456e

make things compile and test pass

[sagetrac-git]

Changed commit from 50e3c5d to cde456e

[tscrim]

comment:10

Ready for review again?

[xcaruso]

comment:11

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

[xcaruso]

Changed dependencies from #13215 to #13215, #29452

[sagetrac-git]

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

[sagetrac-git]

Changed commit from cde456e to 75c220a

[xcaruso]

comment:13

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.

[xcaruso]

comment:59

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

[sagetrac-git]

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

f17860f

deterministic choice of variable names

[sagetrac-git]

Changed commit from b78d3ef to f17860f

[tscrim]

comment:61

Okay, that is a reasonable enough thing to happen, and I am okay with this solution. Thank you.

[xcaruso]

comment:62

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.

[xcaruso]

comment:63

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.

[sagetrac-git]

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

0e15a9e	better test in register_coercion
e92febe	Merge branch 'skew_polynomial_finite_order' into skew_polynomial_finite_order_rc0
fddbb5e	explicit check for no coercion

[sagetrac-git]

Changed commit from f17860f to fddbb5e

[xcaruso]

comment:65

So, I added a test to ensure that no coercion map already exists. (See also ticket #29517)

[xcaruso]

Changed dependencies from #13215, #29452 to #13215, #29452, #29517

[xcaruso]

comment:67

Thanks.

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

[sagetrac-git]

Changed commit from fddbb5e to 5929bf9

[sagetrac-git]

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

1b1467b	modify a doctest
5929bf9	Merge branch 'register_coercion' into skew_polynomial_finite_order_rc0

[xcaruso]

comment:69

I give back a positive review to this ticket.

[vbraun]

Changed branch from u/caruso/centering_methods_skew_polynomials to 5929bf9