Characteristic polynomial of a linear recurrence Created 2026-10-20 Updated 2026-11-05
For the constant-coefficient homogeneous linear recurrence relation , its characteristic polynomial is
A nonzero root gives the solution . Over a field of characteristic zero, a root of multiplicity contributes when . The Fibonacci sequence has , whose roots give its familiar closed formula.
Equivalently, annihilates the shift on every solution. Reducing modulo therefore expresses the distant term as a linear combination of . Repeated squaring in the polynomial quotient ring gives this combination using logarithmically many multiplications in .
Polynomial quotient ring Created 2026-10-20 Updated 2026-11-05
A polynomial quotient ring is a quotient ring of by an ideal of relations. Two polynomials define the same class exactly when their difference belongs to that ideal. Arithmetic is ordinary polynomial arithmetic followed by imposing the relations.
For a field and monic of degree , every element of has a unique representative of degree below . The classes of form a basis. For example, is isomorphic to , with the class of playing the role of . The quotient is a field exactly when is irreducible; a relation alone does not ensure this.