Fast calculation of cyclotomic polynomials

This module provides a function cyclotomic_coeffs(), which calculates the coefficients of cyclotomic polynomials. This is not intended to be invoked directly by the user, but it is called by the method cyclotomic_polynomial() method of univariate polynomial ring objects and the top-level cyclotomic_polynomial() function.

sage.rings.polynomial.cyclotomic.bateman_bound(nn)

Reference:

Bateman, P. T.; Pomerance, C.; Vaughan, R. C. On the size of the coefficients of the cyclotomic polynomial.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.cyclotomic import bateman_bound
sage: bateman_bound(2**8 * 1234567893377)                                       # needs sage.libs.pari
66944986927

Sage Live

from sage.rings.polynomial.cyclotomic import bateman_bound
bateman_bound(2**8 * 1234567893377)                                       # needs sage.libs.pari

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.cyclotomic import bateman_bound
>>> bateman_bound(Integer(2)**Integer(8) * Integer(1234567893377))                                       # needs sage.libs.pari
66944986927

sage.rings.polynomial.cyclotomic.cyclotomic_coeffs(nn, sparse=None)

Return the coefficients of the $n$-th cyclotomic polynomial by using the formula

$${\mathrm{\Phi }}_n(x)=\prod _{d|n}(1-x^{n/d}{)}^{\mu (d)}$$

where $\mu (d)$ is the Möbius function that is 1 if $d$ has an even number of distinct prime divisors, $-1$ if it has an odd number of distinct prime divisors, and $0$ if $d$ is not squarefree.

Multiplications and divisions by polynomials of the form $1-x^n$ can be done very quickly in a single pass.

If sparse is True, the result is returned as a dictionary of the non-zero entries, otherwise the result is returned as a list of python ints.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.cyclotomic import cyclotomic_coeffs
sage: cyclotomic_coeffs(30)
[1, 1, 0, -1, -1, -1, 0, 1, 1]
sage: cyclotomic_coeffs(10^5)
{0: 1, 10000: -1, 20000: 1, 30000: -1, 40000: 1}
sage: R = QQ['x']
sage: R(cyclotomic_coeffs(30))
x^8 + x^7 - x^5 - x^4 - x^3 + x + 1

Sage Live

from sage.rings.polynomial.cyclotomic import cyclotomic_coeffs
cyclotomic_coeffs(30)
cyclotomic_coeffs(10^5)
R = QQ['x']
R(cyclotomic_coeffs(30))

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.cyclotomic import cyclotomic_coeffs
>>> cyclotomic_coeffs(Integer(30))
[1, 1, 0, -1, -1, -1, 0, 1, 1]
>>> cyclotomic_coeffs(Integer(10)**Integer(5))
{0: 1, 10000: -1, 20000: 1, 30000: -1, 40000: 1}
>>> R = QQ['x']
>>> R(cyclotomic_coeffs(Integer(30)))
x^8 + x^7 - x^5 - x^4 - x^3 + x + 1

Check that it has the right degree:

Sage

sage: euler_phi(30)                                                             # needs sage.libs.pari
8
sage: R(cyclotomic_coeffs(14)).factor()                                         # needs sage.libs.pari
x^6 - x^5 + x^4 - x^3 + x^2 - x + 1

Sage Live

euler_phi(30)                                                             # needs sage.libs.pari
R(cyclotomic_coeffs(14)).factor()                                         # needs sage.libs.pari

Python

>>> from sage.all import *
>>> euler_phi(Integer(30))                                                             # needs sage.libs.pari
8
>>> R(cyclotomic_coeffs(Integer(14))).factor()                                         # needs sage.libs.pari
x^6 - x^5 + x^4 - x^3 + x^2 - x + 1

The coefficients are not always +/-1:

Sage

sage: cyclotomic_coeffs(105)
[1, 1, 1, 0, 0, -1, -1, -2, -1, -1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, -1,
 0, -1, 0, -1, 0, -1, 0, -1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, -1, -1, -2,
 -1, -1, 0, 0, 1, 1, 1]

Sage Live

cyclotomic_coeffs(105)

Python

>>> from sage.all import *
>>> cyclotomic_coeffs(Integer(105))
[1, 1, 1, 0, 0, -1, -1, -2, -1, -1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, -1,
 0, -1, 0, -1, 0, -1, 0, -1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, -1, -1, -2,
 -1, -1, 0, 0, 1, 1, 1]

In fact the height is not bounded by any polynomial in $n$ (Erdos), although takes a while just to exceed linear:

Sage

sage: v = cyclotomic_coeffs(1181895)
sage: max(v)
14102773

Sage Live

v = cyclotomic_coeffs(1181895)
max(v)

Python

>>> from sage.all import *
>>> v = cyclotomic_coeffs(Integer(1181895))
>>> max(v)
14102773

The polynomial is a palindrome for any n:

Sage

sage: n = ZZ.random_element(50000)
sage: v = cyclotomic_coeffs(n, sparse=False)
sage: v == list(reversed(v))
True

Sage Live

n = ZZ.random_element(50000)
v = cyclotomic_coeffs(n, sparse=False)
v == list(reversed(v))

Python

>>> from sage.all import *
>>> n = ZZ.random_element(Integer(50000))
>>> v = cyclotomic_coeffs(n, sparse=False)
>>> v == list(reversed(v))
True

AUTHORS:

• Robert Bradshaw (2007-10-27): initial version (inspired by work of Andrew Arnold and Michael Monagan)

REFERENCE:

• http://www.cecm.sfu.ca/~ada26/cyclotomic/

sage.rings.polynomial.cyclotomic.cyclotomic_value(n, x)

Return the value of the $n$-th cyclotomic polynomial evaluated at $x$.

INPUT:

• n – an Integer, specifying which cyclotomic polynomial is to be evaluated

• x – an element of a ring

OUTPUT:

• the value of the cyclotomic polynomial ${\mathrm{\Phi }}_n$ at $x$

ALGORITHM:

• Reduce to the case that $n$ is squarefree: use the identity

$${\mathrm{\Phi }}_n(x)={\mathrm{\Phi }}_q(x^{n/q})$$

where $q$ is the radical of $n$.

• Use the identity

$${\mathrm{\Phi }}_n(x)=\prod _{d|n}(x^d-1{)}^{\mu (n/d)},$$

where $\mu$ is the Möbius function.

• Handles the case that $x^d=1$ for some $d$, but not the case that $x^d-1$ is non-invertible: in this case polynomial evaluation is used instead.

EXAMPLES:

Sage

sage: cyclotomic_value(51, 3)
1282860140677441
sage: cyclotomic_polynomial(51)(3)
1282860140677441

Sage Live

cyclotomic_value(51, 3)
cyclotomic_polynomial(51)(3)

Python

>>> from sage.all import *
>>> cyclotomic_value(Integer(51), Integer(3))
1282860140677441
>>> cyclotomic_polynomial(Integer(51))(Integer(3))
1282860140677441

It works for non-integral values as well:

Sage

sage: cyclotomic_value(144, 4/3)
79148745433504023621920372161/79766443076872509863361
sage: cyclotomic_polynomial(144)(4/3)
79148745433504023621920372161/79766443076872509863361

Sage Live

cyclotomic_value(144, 4/3)
cyclotomic_polynomial(144)(4/3)

Python

>>> from sage.all import *
>>> cyclotomic_value(Integer(144), Integer(4)/Integer(3))
79148745433504023621920372161/79766443076872509863361
>>> cyclotomic_polynomial(Integer(144))(Integer(4)/Integer(3))
79148745433504023621920372161/79766443076872509863361

Make live