Throughout this section denotes a field. The section constructs the ring with its division, gcd and factorisation theory, and proves that a nonzero polynomial of degree over a field has at most 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 in the indeterminate is a formal expression
where
The symbol is an indeterminate (a formal variable): it is not an element of and denotes no particular value; it is a placeholder organising the coefficients. The set of all polynomials over in is denoted .
In the rigorous form of 5.1, is
the set of all functions
Let
The coefficient is the convolution of the two coefficient sequences. Both defining sums are finite—only finitely many and are nonzero, hence only finitely many are nonzero—so the sum and the product are again polynomials.
The convolution formula results from multiplying out the product
and collecting like powers of
using
With the operations of 5.3, the set
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 , the sequence
is an additive identity, and
is an additive inverse of .
Hence
Commutativity of multiplication. The coefficient of in
is ; reindexing the sum by
which is the coefficient of in .
Associativity of multiplication. Write
and expanding instead produces
, the same symmetric triple sum by
associativity in . Hence
Distributivity. The coefficient of in
Identity. With
Embedding. Let
Multiplying
Let
The convention
For all
| (1) |
with equality whenever
| (2) |
If either polynomial is zero, both statements reduce to the conventions of 5.6. So let and be nonzero, of degrees and with leading coefficients and .
Sum. The coefficient of in
Product. The coefficient
The product formula (2) is the first result to use the field hypothesis, through the absence of zero divisors in ; the next three results and the rest of the section depend on it.
The ring has no zero divisors: if
If and are both nonzero, then
Let
From
A polynomial
A nonzero constant has the inverse
Two polynomials
Every nonzero polynomial has exactly one monic associate, . 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 , carries the arithmetic of (§2) over to : greatest common divisors, the Euclidean algorithm, Bézout’s identity, irreducibles in place of primes, and unique factorisation.
Let
We call the quotient and the remainder, and
write
Existence. Fix , of degree with leading coefficient
, and induct on . If
The subtracted term has degree and leading coefficient
The existence proof is constructive: it is polynomial long
division, which repeatedly eliminates the current leading term by
subtracting a monomial multiple of . Each step strictly lowers the
degree of the running remainder, so the process terminates after at most
For example, let
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
obtained by substituting for the indeterminate . An
element
Fix
for all
Additivity is immediate from the coordinatewise definition of addition.
For multiplicativity, with
the middle equality because expanding the product of the two finite sums
and grouping terms by
Let
(Remainder theorem.) The remainder of upon division
by the linear polynomial
(Factor theorem.) The element is a root of
if and only if
(1) Divide by
(2) By (1) and the uniqueness of the remainder,
A nonzero polynomial
We induct on
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 the degree- polynomial
Let
Let
every common divisor of and 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 . When
Let
If
Let
| (3) |
Concretely: set
The degrees strictly decrease, so some
Termination. If
The gcd property. 5.22, applied at each division, preserves the set of common divisors:
and the last set is exactly the set of divisors of , since every polynomial divides . Thus divides both and , and every common divisor of and divides : the monic associate 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 that each remainder
is an -linear combination of and . The bases
Carrying the linear-combination coefficients along with the remainders,
as in the integer case (Theorem 2.13), produces
and alongside the gcd. The standard application is inversion
in a quotient for irreducible : if
Let
If
If 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
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 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 is
for , 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
are the Lagrange basis polynomials for the nodes.
The are polynomials. Each denominator
The delta property. Writing for the Kronecker
symbol (equal to if
| (4) |
at
Uniqueness. Two interpolants of degree at most agree at the
This example computes the polynomial of degree at most with
Hence
which satisfies
Fix
is -linear. Its surjectivity is the existence half of
5.30, and its injectivity the uniqueness half;
so is a linear isomorphism
Alongside the Lagrange basis, the node set determines its vanishing polynomial
the unique monic polynomial of degree
A linear factor may divide a polynomial more than once, as in
Let
The largest such exists: the powers have
strictly increasing degrees, so only finitely many can divide the fixed
, 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
Let
for some
We first check that the powers are pairwise
coprime. Each
Each divides by the definition of
multiplicity, so 5.35 gives
so
The formal derivative is the map
where the coefficient means added to itself
times in —that is, multiplied by the image of the
integer under the canonical map
For all
(Linearity.)
(Product rule.)
(Power rule.)
(1) Linearity is immediate from the coordinatewise definition of , which is linear in the coefficients.
(2) Both sides are bilinear in the pair : by part (1),
each is linear in with fixed and linear in with
fixed. It therefore suffices to verify the identity on monomials
with the convention that a term carrying the integer coefficient
(the case
(3) Induct on . The base is
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 a field (4.26) from to .
Let
The principal ideal
Every nonzero class is a unit. Let
The map
Finally, write
so is a root of in . □
Let
The element is a repeated root of —a root of
multiplicity at least —if and only if
If has a repeated root in , then
Call separable if it has no repeated root in any
field containing . Then is separable if and only if
(1) Let be a root of multiplicity
If
(2) A repeated root
(3) The argument rests on the fact that gcds are stable under
field extension: for an extension field of
(4.25), the Euclidean algorithm of
5.23 run on
Suppose
Conversely, suppose
The integer coefficient in
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
The assignment
Let
If is infinite, then
If is finite, the map is not injective. Over
, the nonzero polynomial
(1) Let
(2) Let be finite, with
a monic polynomial of degree —in particular nonzero as a formal
object—which vanishes at every point of 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 and induce the same function on , yet have degrees and . 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
means to select each element with equal likelihood ;
the probability of an event is then the fraction of elements of
producing it, so that
Let
| (5) |
More generally, if
Inequality (5) is the probabilistic
refinement of 5.20: a
single random evaluation point detects unequal polynomials of
degree at most , except with probability at most .
With exponentially large (
The full Schwartz–Zippel lemma extends to polynomials in several
indeterminates
Over a 255-bit field , distinct polynomials and of
degree at most agree on a uniformly random challenge