Opened 4 years ago

Closed 4 years ago

#20263 closed enhancement (fixed)

Extract cyclotomic factors of a polynomial

Reported by: kedlaya Owned by: kedlaya
Priority: minor Milestone: sage-7.2
Component: algebra Keywords: cyclotomic polynomials, days71
Cc: Merged in:
Authors: Kiran Kedlaya Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 4340103 (Commits) Commit: 43401035fd66aade5bf22bde89b0dc52edcfe5c9
Dependencies: Stopgaps:

Description

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

Change History (20)

comment:1 Changed 4 years ago by kedlaya

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

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

comment:2 Changed 4 years ago by kedlaya

  • Priority changed from major to minor

comment:3 Changed 4 years ago by kedlaya

  • Branch set to u/kedlaya/extract_cyclotomic_factors_of_a_polynomial

comment:4 Changed 4 years ago by git

  • Commit set to 31d88e1d7f67a8b58a10db518877f561c9e3ad22

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

31d88e1Added cyclotomic_part method

comment:5 Changed 4 years ago by kedlaya

  • Status changed from new to needs_review

comment:6 follow-up: Changed 4 years ago by vdelecroix

  • Status changed from needs_review to needs_work

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.

comment:7 Changed 4 years ago by git

  • Commit changed from 31d88e1d7f67a8b58a10db518877f561c9e3ad22 to 131cbb87a80b12cd9628bc34fc408be19e1d9c31

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

6703af9Added doctest over Q, inexact base rings
131cbb8Fix typo in cyclotomic_part

comment:8 in reply to: ↑ 6 ; follow-up: Changed 4 years ago by kedlaya

  • Authors set to Kiran Kedlaya

Replying to vdelecroix:

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.

comment:9 in reply to: ↑ 8 ; follow-up: Changed 4 years ago by 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.

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

comment:10 in reply to: ↑ 9 ; follow-up: Changed 4 years ago by 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.

comment:11 Changed 4 years ago by vdelecroix

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.

comment:12 follow-up: Changed 4 years ago by vdelecroix

Could you add a doctest for non exact rings?

comment:13 Changed 4 years ago by vdelecroix

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

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

comment:14 in reply to: ↑ 10 Changed 4 years ago by kedlaya

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.

comment:15 in reply to: ↑ 12 Changed 4 years ago by kedlaya

Replying to vdelecroix:

Could you add a doctest for non exact rings?

There is already a doctest over RR.

comment:16 Changed 4 years ago by git

  • Commit changed from 131cbb87a80b12cd9628bc34fc408be19e1d9c31 to 43401035fd66aade5bf22bde89b0dc52edcfe5c9

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

4340103Change `self` to "this polynomial" in docstrings

comment:17 Changed 4 years ago by vdelecroix

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.

comment:18 Changed 4 years ago by kedlaya

  • Status changed from needs_work to needs_review

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

comment:19 Changed 4 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

comment:20 Changed 4 years ago by vbraun

  • Branch changed from u/kedlaya/extract_cyclotomic_factors_of_a_polynomial to 43401035fd66aade5bf22bde89b0dc52edcfe5c9
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.