Extract cyclotomic factors of a polynomial

[kedlaya]

Add a member function to polynomials that returns the product of all irreducible factors which are cyclotomic polynomials.

sage: P.<x> = PolynomialRing(ZZ)
sage: pol = (x^4+1)^2*(x^4+2)
sage: pol.cyclotomic_part()
x^8 + 2*x^4 + 1

Component: algebra

Keywords: cyclotomic polynomials, days71

Author: Kiran Kedlaya

Branch/Commit: 4340103

Reviewer: Vincent Delecroix

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

[kedlaya]

comment:1

I have code for this which I'm planning to upload shortly. The algorithm is similar to what PARI is using to test whether a polynomial is equal to a product of cyclotomic polynomials (is_cyclotomic_product).

[kedlaya]

Branch: u/kedlaya/extract_cyclotomic_factors_of_a_polynomial

[sagetrac-git]

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

31d88e1

Added cyclotomic_part method

[sagetrac-git]

Commit: 31d88e1

[videlec]

comment:6

hello,

• please, fill the "Authors" field of the ticket with your full name

• avoid the usage of "self" in the docstring. It can be "this polynomial". As it is a method, self is not considered as an argument.

• you should add doctests over the rationals

• what the algorithm should do over non exact rings (like the RR and CC floating points in Sage)? I guess that you might want to raise an error in that case.

[sagetrac-git]

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

6703af9	Added doctest over Q, inexact base rings
131cbb8	Fix typo in cyclotomic_part

[sagetrac-git]

Changed commit from 31d88e1 to 131cbb8

[kedlaya]

Author: Kiran Kedlaya

[kedlaya]

comment:8

Replying to @videlec:

hello,

• please, fill the "Authors" field of the ticket with your full name

Done.

• avoid the usage of "self" in the docstring. It can be "this polynomial". As it is a method, self is not considered as an argument.

Technically, self is an argument of every instance method (otherwise it would be a class method). More importantly, many of the docstrings in this file use self, so I don't want to change the prevailing format (at least not in this ticket). The Sage Developer's Guide doesn't seem to express an opinion here.

• you should add doctests over the rationals

Done.

• what the algorithm should do over non exact rings (like the RR and CC floating points in Sage)? I guess that you might want to raise an error in that case.

Yes, raising an error seems like the most useful outcome.

[nbruin]

comment:9

Replying to @kedlaya:

Technically, self is an argument of every instance method

Hi Kiran! It's an argument the method receives, but it's not an argument the user supplies explicitly. I think that's the argument why (some) people prefer to not use self in user-facing docstrings, and the method you're proposing is a user-facing one. I think it indeeds makes for a more easily understood docstring if you can reasonably avoid explicitly mentioning self.

More importantly, many of the docstrings in this file use self, so I don't want to change the prevailing format

Your observation piqued my interest and a scanned the file. My impression was that "this polynomial" is a tad more common. Some docstrings refer to two polynomials, without being specific about one that is "this".

The thing that struck me was that the use of self was largely (but not exclusively) restricted to "dunder", private, and interfacing methods. These are methods that are hard to look up for users and/or that users will have less interest in looking up.

So when we restrict to "user facing" methods, I think the prevailing style quite solidly favours "this polynomial" over "self".

[tscrim]

comment:10

Replying to @nbruin:

Replying to @kedlaya:

Technically, self is an argument of every instance method

Hi Kiran! It's an argument the method receives, but it's not an argument the user supplies explicitly. I think that's the argument why (some) people prefer to not use self in user-facing docstrings, and the method you're proposing is a user-facing one. I think it indeeds makes for a more easily understood docstring if you can reasonably avoid explicitly mentioning self.

There are two different issues. The first is that it is not a "real" input, so it does not belong in an INPUT: block, although this is moot wrt this ticket. The use of self in docstrings is more of a bikeshedding issue, but IMO self is clear about what it is referring to (and uniquely defined, both in Python and the English). Also, there are many times I feel that if you wanted to do "this blah", the "blah" is either very long or imprecise. Anyways, that's my 2 cents on the issue.

[videlec]

comment:11

Concerning, I agree that it is fine english. But then you should not put it inside backquotes which is a Sage convention for Python or Sage objects. In this form it refers to the argument and not to the common english sense.

[videlec]

comment:12

Could you add a doctest for non exact rings?

[videlec]

comment:13

Instead of dividing by the leading coefficient you can use the monic method.

sage: x = polygen(ZZ)
sage: p = 3*x**2 + 2*x**3 + 5
sage: p.monic()
x^3 + 3/2*x^2 + 5/2

EDIT: this is not a good idea since this method always converts the polynomial to a rational one...

[kedlaya]

comment:14

Replying to @tscrim:

Replying to @nbruin:

Replying to @kedlaya:

Technically, self is an argument of every instance method

Hi Kiran! It's an argument the method receives, but it's not an argument the user supplies explicitly. I think that's the argument why (some) people prefer to not use self in user-facing docstrings, and the method you're proposing is a user-facing one. I think it indeeds makes for a more easily understood docstring if you can reasonably avoid explicitly mentioning self.

There are two different issues. The first is that it is not a "real" input, so it does not belong in an INPUT: block, although this is moot wrt this ticket. The use of self in docstrings is more of a bikeshedding issue, but IMO self is clear about what it is referring to (and uniquely defined, both in Python and the English). Also, there are many times I feel that if you wanted to do "this blah", the "blah" is either very long or imprecise. Anyways, that's my 2 cents on the issue.

Since I only need to refer to the underlying object once, I think I can and should get away with calling it "this polynomial". If I needed to refer to it more than once, I'd stick with self.

[kedlaya]

comment:15

Replying to @videlec:

Could you add a doctest for non exact rings?

There is already a doctest over RR.

[sagetrac-git]

Changed commit from 131cbb8 to 4340103

[sagetrac-git]

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

4340103

Change `self` to "this polynomial" in docstrings

[videlec]

comment:17

Hello,

When a reviewer complain he/she puts the ticket in "needs work". When you are done with the modifications you should set it back to "needs review". Otherwise it might be forgotten.

[kedlaya]

comment:18

Indeed it was forgotten, by me! I must have thought I had something else to do, but apparently not. Flag set.

[videlec]

Reviewer: Vincent Delecroix

[vbraun]

Changed branch from u/kedlaya/extract_cyclotomic_factors_of_a_polynomial to 4340103