Throughout this section F denotes a field. The section constructs the ring F [X] with its division, gcd and factorisation theory, and proves that a nonzero polynomial of degree d over a field has at most d roots. From this bound it derives Lagrange interpolation (§5.7) and the Schwartz–Zippel lemma (§5.10), which justifies the polynomial identity testing of the later volumes: two polynomials encoding a computation are compared by evaluating both at one random α , not coefficient by coefficient at the cost of reading the computation. Halo 2 and Zcash Orchard use these results in their polynomial commitment schemes and their arithmetisation, the encoding of a computation as identities between polynomials; polynomials also underlie finite fields and error-correcting codes.
A polynomial is a formal expression, a finite list of coefficients, and not a function: evaluating it yields a function, which over a finite field carries less information than the polynomial (§5.9).
A polynomial over F in the indeterminate X is a formal expression
| f = a 0 + a 1 X + a 2 X 2 + ⋯ + a n X n = ∑ i = 0 n a i X i, |
where
| ∑ i a i X i = ∑ i b i X i ⟺ a i = b i for every i ∈ N . |
The symbol X is an indeterminate (a formal variable): it is not an element of F and denotes no particular value; it is a placeholder organising the coefficients. The set of all polynomials over F in X is denoted F [X] .
In the rigorous form of 5.1, F [X] is
the set of all functions
Let
| f + g = ∑ i ≥ 0 (a i + b i) X i, f g = ∑ k ≥ 0 c k X k where c k = ∑ i + j = k a i b j = ∑ i = 0 k a i b k − i . |
The coefficient c k is the convolution of the two coefficient sequences. Both defining sums are finite—only finitely many a i and b j are nonzero, hence only finitely many c k are nonzero—so the sum and the product are again polynomials.
The convolution formula results from multiplying out the product
(∑ i a i X i) (∑ j b j X j) and collecting like powers of X
using
With the operations of 5.3, the set
F [X] is a commutative ring whose additive identity is the zero
polynomial
Additive structure. Addition is coordinatewise, so its
commutativity and associativity are inherited directly from the
corresponding laws of the additive group of F , the sequence
(0, 0, ...) is an additive identity, and
(− a 0, − a 1, ...) is an additive inverse of (a 0, a 1, ...) .
Hence
Commutativity of multiplication. The coefficient of X k in
f g is ∑ i + j = k a i b j ; reindexing the sum by
| ∑ i + j = k a i b j = ∑ i + j = k b i a j, |
which is the coefficient of X k in g f .
Associativity of multiplication. Write
| ∑ k + l = m (∑ i + j = k a i b j) c l = ∑ i + j + l = m a i b j c l, |
and expanding f (g h) instead produces
∑ i + j + l = m a i (b j c l) , the same symmetric triple sum by
associativity in F . Hence
Distributivity. The coefficient of X k in
Identity. With
Embedding. Let
Multiplying
Let
The convention
For all
| deg (f + g) ≤ max { deg f, deg g }, | (1) |
with equality whenever
| deg (f g) = deg f + deg g . | (2) |
If either polynomial is zero, both statements reduce to the − ∞ conventions of 5.6. So let f and g be nonzero, of degrees m and n with leading coefficients a m and b n .
Sum. The coefficient of X k in
Product. The coefficient
The product formula (2) is the first result to use the field hypothesis, through the absence of zero divisors in F ; the next three results and the rest of the section depend on it.
The ring F [X] has no zero divisors: if
If f and g are both nonzero, then
Let
From
A polynomial
A nonzero constant c has the inverse
Two polynomials
Every nonzero polynomial f has exactly one monic associate, lc (f) − 1 f . Choosing the monic representative, as below, makes the greatest common divisor and the irreducible factor unique.
Division with remainder, with degree in the role of absolute value on Z , carries the arithmetic of Z (§2) over to F [X] : greatest common divisors, the Euclidean algorithm, Bézout’s identity, irreducibles in place of primes, and unique factorisation.
Let
| f = q g + r and deg r < deg g . |
We call q the quotient and r the remainder, and
write
Existence. Fix g , of degree n with leading coefficient
b n , and induct on deg f . If
| f 1 = f − a m b n X m − n g . |
The subtracted term has degree m and leading coefficient
Uniqueness. Suppose
The existence proof is constructive: it is polynomial long
division, which repeatedly eliminates the current leading term by
subtracting a monomial multiple of g . Each step strictly lowers the
degree of the running remainder, so the process terminates after at most
For example, let
| X 3 + 2 X + 1 = X (X 2 + 1) + (X + 1) . |
For
This subsection defines evaluation, where a polynomial first gives rise to a function, and proves the root bound (5.18). Every later construction of the volume on polynomials rests on that bound, including the cyclicity of the multiplicative group of a finite field.
Let
| f (α) = ∑ i = 0 n a i α i ∈ F, |
obtained by substituting α for the indeterminate X . An
element
Fix
| (f + g) (α) = f (α) + g (α), (f g) (α) = f (α) g (α), 1 (α) = 1 |
for all
Additivity is immediate from the coordinatewise definition of addition.
For multiplicativity, with
| (f g) (α) = ∑ k c k α k = ∑ k ∑ i + j = k a i b j α i + j = (∑ i a i α i) (∑ j b j α j) = f (α) g (α), |
the middle equality because expanding the product of the two finite sums
and grouping terms by
Let
(Remainder theorem.) The remainder of f upon division
by the linear polynomial
(Factor theorem.) The element α is a root of
f if and only if
(1) Divide f by
(2) By (1) and the uniqueness of the remainder,
A nonzero polynomial
We induct on
| 0 = f (β) = (β − α) q (β) ; |
since
Both ingredients of the proof, the absence of zero divisors and the
degree bookkeeping, are necessary. Over a ring with zero divisors the
bound fails: in Z / 8 Z the degree- 2 polynomial
Let
Let
every common divisor c of f and g satisfies
A greatest common divisor is determined only up to multiplication by a
unit; the unique monic one (5.23) is
singled out and denoted gcd (f, g) . When
Let
If
Let
| gcd (f, g) = s f + t g . | (3) |
Concretely: set
| r i − 1 = q i r i + r i + 1, deg r i + 1 < deg r i . |
The degrees strictly decrease, so some
Termination. If
The gcd property. 5.22, applied at each division, preserves the set of common divisors:
| { common divisors of (f, g) } | = { common divisors of (r 1, r 2) } | ||
| = ⋯ = { common divisors of (r N, 0) }, |
and the last set is exactly the set of divisors of r N , since every polynomial divides 0 . Thus r N divides both f and g , and every common divisor of f and g divides r N : the monic associate lc (r N) − 1 r N is a monic greatest common divisor.
Uniqueness. Two monic greatest common divisors divide each other,
so they differ by a unit
Bézout. We show by induction on i that each remainder
r i is an F [X] -linear combination of f and g . The bases
Carrying the linear-combination coefficients along with the remainders,
as in the integer case (Theorem 2.13), produces
s and t alongside the gcd. The standard application is inversion
in a quotient F [X] / (m) for irreducible m : if
Let
If
If p is irreducible and
Here irreducible is the polynomial analogue of prime, made precise in 5.26 below.
(1) Multiplying the Bézout identity
(2) Suppose
A polynomial
The polynomial
Every nonconstant
| f = c p 1 p 2 ⋯ p k |
with
The proof is modelled on the fundamental theorem of arithmetic (Theorem 2.18), with degree in place of absolute value.
Existence, by induction on
Uniqueness. Comparing leading coefficients in the two
factorisations gives
The degree function and 5.12 make F [X] a
Euclidean
domain—an integral domain with division with
remainder relative to a size measure—and every Euclidean domain is a
principal ideal domain (PID): each ideal
(4.17) of F [X] is
| Euclidean ⟹ PID ⟹ UFD |
for F [X] , ending at 5.28.
Lagrange interpolation, the constructive converse of 5.20, underlies secret sharing, Reed–Solomon error-correcting codes, and the polynomial encodings in Halo 2.
Let
| f (X) = ∑ i = 0 d y i l i (X), where l i (X) = ∏ j ≠ i X − x j x i − x j |
are the Lagrange basis polynomials for the nodes.
The l i are polynomials. Each denominator
The delta property. Writing δ i m for the Kronecker
symbol (equal to 1 if
| l i (x m) = δ i m (0 ≤ i, m ≤ d) : | (4) |
at
Uniqueness. Two interpolants of degree at most d agree at the
This example computes the polynomial of degree at most 2 with
| l 0 | = (X − 1) (X − 2) (0 − 1) (0 − 2) = (X − 1) (X − 2) 2, | ||
| l 1 | = (X − 0) (X − 2) (1 − 0) (1 − 2) = − X (X − 2), | ||
| l 2 | = (X − 0) (X − 1) (2 − 0) (2 − 1) = X (X − 1) 2 . |
Hence
| f = 1 ⋅ l 0 + 3 ⋅ l 1 + 7 ⋅ l 2 = 1 2 (X 2 − 3 X + 2) + 3 (2 X − X 2) + 7 2 (X 2 − X) = X 2 + X + 1, |
which satisfies
Fix
| ev : V → F d + 1, f ⟼ (f (x 0), ..., f (x d)), |
is F -linear. Its surjectivity is the existence half of
5.30, and its injectivity the uniqueness half;
so ev is a linear isomorphism
Alongside the Lagrange basis, the node set { x 0, ..., x d } determines its vanishing polynomial
| Z (X) = ∏ i = 0 d (X − x i), |
the unique monic polynomial of degree
A linear factor may divide a polynomial more than once, as in
Let
The largest such m exists: the powers (X − α) m have
strictly increasing degrees, so only finitely many can divide the fixed
f , and at least one does by the factor theorem. In an equivalent
characterisation,
The number of roots counted with multiplicity is also bounded by the degree; the proof uses the following lemma.
Let
First let
| f = s f 1 f + t f 2 f = s f 1 (f 2 v) + t f 2 (f 1 u) = f 1 f 2 (s v + t u), |
and
Let
| f = (X − α 1) m 1 ⋯ (X − α r) m r g |
for some
We first check that the powers (X − α i) m i are pairwise
coprime. Each
Each (X − α i) m i divides f by the definition of
multiplicity, so 5.35 gives
| m 1 + ⋯ + m r + deg g = d, |
so
The formal derivative is the map
| f ′ = D f = ∑ i = 1 n i a i X i − 1 = a 1 + 2 a 2 X + ⋯ + n a n X n − 1, |
where the coefficient i a i means a i added to itself i
times in F —that is, a i multiplied by the image of the
integer i under the canonical map
For all
(Linearity.)
(Product rule.)
(Power rule.)
(1) Linearity is immediate from the coordinatewise definition of D , which is linear in the coefficients.
(2) Both sides are bilinear in the pair (f, g) : by part (1),
each is linear in f with g fixed and linear in g with f
fixed. It therefore suffices to verify the identity on monomials
| (X a X b) ′ = (X a + b) ′ = (a + b) X a + b − 1 = a X a − 1 X b + X a b X b − 1 = (X a) ′ X b + X a (X b) ′, |
with the convention that a term carrying the integer coefficient 0
(the case
(3) Induct on m . The base is
| ((X − α) m) ′ | = ((X − α) (X − α) m − 1) ′ | ||
| = (X − α) m − 1 + (X − α) (m − 1) (X − α) m − 2 | |||
| = m (X − α) m − 1 . ∎ |
The proof of part (3) of the next theorem needs a repeated root in an extension field not given in advance. The following lemma constructs that extension by applying the quotient construction of Example 4.22 to polynomial rings; its proof transposes the argument that made Z / p Z a field (4.26) from Z to F [X] .
Let
The principal ideal
Every nonzero class is a unit. Let
The map
Finally, write
| h (α) = ∑ i ι (c i) (X + (h)) i = (∑ i c i X i) + (h) = h + (h) = 0 + (h), |
so α is a root of h in K . □
Let
The element α is a repeated root of f —a root of
multiplicity at least 2 —if and only if
If f has a repeated root in F , then
Call f separable if it has no repeated root in any
field containing F . Then f is separable if and only if
(1) Let α be a root of multiplicity
| f ′ = m (X − α) m − 1 g + (X − α) m g ′ = (X − α) m − 1 [m g + (X − α) g ′] . |
If
(2) A repeated root
(3) The argument rests on the fact that gcds are stable under
field extension: for an extension field K of F
(4.25), the Euclidean algorithm of
5.23 run on
Suppose
Conversely, suppose
The integer coefficient i in
| X p − 1 = (X − 1) p in F p [X], |
a factorisation the finite-fields section establishes through the
freshman’s-dream identity
This subsection determines when a polynomial may be identified with the function it induces.
Every
| f ~ : F → F, α ⟼ f (α) . |
The assignment
Let
If F is infinite, then
If F is finite, the map is not injective. Over
F p , the nonzero polynomial
(1) Let
(2) Let F be finite, with
| w (X) = ∏ α ∈ F (X − α), |
a monic polynomial of degree q —in particular nonzero as a formal
object—which vanishes at every point of F by construction. Thus
Part (2) of 5.43 is the reason polynomials are defined as coefficient sequences and not as functions. Cryptography works over finite fields, where the functional view loses information: the polynomials X and X p induce the same function on F p , yet have degrees 1 and p . The security of polynomial commitment schemes rests on the degree, a property of the formal object invisible to the induced function over a finite field. A prover commits to a low-degree formal polynomial, and the verifier tests it by evaluation. The Schwartz–Zippel lemma quantifies the gap between agreement at the tested points and identity to the claimed formal polynomial.
To draw α uniformly at random from a finite nonempty set
S means to select each element with equal likelihood 1 / | S | ;
the probability of an event is then the fraction of elements of
S producing it, so that
Let
| Pr [f (α) = 0] ≤ d | S | . | (5) |
More generally, if
By 5.18, the nonzero f has at most d roots in F , hence at most d in the subset S . Under the uniform draw,
| Pr [f (α) = 0] = | { α ∈ S : f (α) = 0 } | | S | ≤ d | S | . |
For the general form, apply this to
Inequality (5) is the probabilistic
refinement of 5.20: a
single random evaluation point detects unequal polynomials of
degree at most d , except with probability at most d / | S | .
With | S | exponentially large (
The full Schwartz–Zippel lemma extends to polynomials in several
indeterminates
Over a 255-bit field F q , distinct polynomials f and g of
degree at most d agree on a uniformly random challenge