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:

\[\begin{split} \begin{aligned} x^2-1 &= (x-1)(x+1), \\ x^3-1 &= (x-1)(x^2+x+1), \\ x^4-1 &= (x-1)(x+1)(x^2+1). \end{aligned} \end{split}\]

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.