A Polynomial Conjecture¶
SymPy for Polynomials¶
Polynomials can be factored in SymPy with sy.factor().
The sy.factor_list() function computes the factorization and returns a tuple containing a constant and a list of (factor, exponent) pairs.
import sympy as sy
x = sy.symbols("x")
f = x**3 - 3 * x + 2
print(sy.factor(f))
print(sy.factor_list(f)) # The constant 1, then each factor with its exponent.
(x - 1)**2*(x + 2)
(1, [(x + 2, 1), (x - 1, 2)])
Wrapping an expression in sy.Poly() creates a polynomial object with methods for inspecting its terms.
The coeffs() method lists the nonzero coefficients from the highest-degree term to the lowest, while all_coeffs() also includes the zeros.
g = sy.Poly(x**3 - 4 * x + 1)
print(g.coeffs()) # Skips the missing x^2 term.
print(g.all_coeffs()) # Includes 0 for the x^2 term.
[1, -4, 1]
[1, 0, -4, 1]
Cyclotomic Polynomials¶
Problem 6
Factoring \(x^n - 1\) over the integers seems to produce a pattern:
Irreducible integer-coefficient polynomial factors of \(x^n - 1\), such as \((x-1)\), \((x+1)\), \((x^2+1)\), and \((x^2+x+1)\), are called cyclotomic polynomials. Writing these polynomials as \(c_2 x^2 + c_1 x + c_0\), in each case the coefficients \(c_2,c_1,c_0\) are in \(\{-1,0,1\}\) (unlike, for example, \(2x + 1\), which has a coefficient \(c_1 = 2\)).
Disprove: For every positive integer \(n\in\mathbb{N}\), every coefficient of every cyclotomic polynomial that is a factor of \(x^n - 1\) is in the set \(\{1,0,-1\}\).
Write a function named cyclotomic() that accepts a positive integer \(n\in\mathbb{N}\).
Find the distinct coefficients that appear in the irreducible factors of \(x^n - 1\).
Return True if all coefficients are in \(\{-1,0,1\}\); return False otherwise.
Use cyclotomic() to find the smallest counterexample.
That is, find \(n_0\) such that \(x^{n_0} - 1\) has a cyclotomic polynomial factor with a coefficient not in \(\{-1,0,1\}\).
Store the value of \(n_0\) as the variable problem6_counterexample.