Polynomials in Algorithm Design

Is this product right?

A library hands back the product of two polynomials, computed with module 25's fast Fourier transform: in floating point, which rounds, or modulo a prime, which wraps large coefficients. You hold three coefficient lists and one question: is $C=A·B$?

Here is a small instance, coefficients listed from $x^0$ up:

$$A=2+7x+x^2+3x^3,B=4+x+5x^2+2x^3,$$

and the claimed product is [8, 29, 21, 53, 22, 17, 6].

A = [2, 7, 1, 3]
B = [4, 1, 5, 2]
C = [8, 29, 21, 53, 22, 17, 6]                     # the claimed product

AB = [sum(A[i] * B[k - i] for i in range(4) if 0 <= k - i < 4) for k in range(7)]
assert AB == [8, 30, 21, 52, 22, 17, 6]            # the true product
assert [c - t for c, t in zip(C, AB)] == [0, -1, 0, 1, 0, 0, 0]
assert sum(C) == sum(AB) == 156                    # the coefficient sums agree

Two coefficients are off by one, in opposite directions, the kind of damage rounding leaves.

The naive approaches. Recomputing the product costs $n^2$ multiplications for polynomials with $n$ coefficients, or $O(n\log n)$ with module 25, and it trusts a second implementation to check the first, when we need one bit. The cheap alternative is a checksum: compare the sum of $C$'s coefficients with the product of the sums of $A$'s and $B$'s. That compares $C(1)$ with $A(1)B(1)$, and here it says $156=13·12$ and passes a wrong answer. A check at a fixed point is blind to every error that vanishes there.

The fix is a random point. This module proves why that works, then uses the same fact to recover lost data and to test a graph for a perfect matching.

Arithmetic in a field

We compute modulo a prime $p$. The set ${𝔽}_p=\{0,1,\dots ,p-1\}$ with addition and multiplication mod $p$ is a field: every nonzero $a$ has an inverse, $a^{-1}=a^{p-2}modp$ by Fermat's little theorem, so division works. Arithmetic is exact, and each number stays below $p$. Costs count field operations (additions, subtractions, multiplications mod $p$), each $O(1)$ on a word-RAM when $p$ fits in a word; an inverse costs $O(\log p)$ of them. Every error bound below holds for every input, over the algorithm's own coins.

A polynomial of degree $d$ is stored as its coefficient list $[c_0,\dots ,c_d]$. Addition costs $O(d)$ field operations, and evaluation costs $d$ multiplications by Horner's rule, $c_0+x(c_1+x(c_2+\dots ))$. Multiplying two polynomials with $n$ coefficients costs $n^2$ multiplications by the schoolbook method. Module 25 does it in $O(n\log n)$ field operations when the field has a primitive $N$-th root of unity for a power of two $N\ge 2n$ (such as its prime 998244353); modulo other primes, one uses a few such primes and the Chinese remainder theorem.

Why a prime? Modulo 8, which is not a field, $2·4=8\equiv 0$: two nonzero numbers multiply to zero. The lemma below then fails.

assert [x for x in range(8) if (x * x - 1) % 8 == 0] == [1, 3, 5, 7]   # degree 2, four roots

The one lemma

Proof. By induction on $d$. A nonzero constant has no roots. If $f$ has degree $d\ge 1$ and a root $a$, divide by $x-a$: $f=(x-a)q+f(a)=(x-a)q$, with $\mathrm{deg}q=d-1$. If $b\ne a$ is another root, then $(b-a)q(b)=0$. In a field a product is zero only if a factor is, and $b-a\ne 0$, so $q(b)=0$. Every root other than $a$ is a root of $q$, which has at most $d-1$ by induction. $◻$

The step not to skip is "a product is zero only if a factor is". Modulo 8 it is false, and $x^2-1=(x-1)(x+1)$ vanishes at 3 because $2·4\equiv 0$.

The consequence every algorithm here uses. If $f\ne g$ and both have degree at most $d$, then $f-g$ is nonzero of degree at most $d$, so $f$ and $g$ agree on at most $d$ points. Draw $r$ uniformly from a set $S$ of field elements:

$$Pr[f(r)=g(r)]\le d/|S|.$$

The error is one-sided. If $f(r)\ne g(r)$, then certainly $f\ne g$. Only "equal" can be wrong.

Tracing the check

For the product, $f=C$ and $g=A·B$, both of degree at most 6. Take $p=13$ so the whole field fits in a picture. The check draws $r$, computes $A(r)$, $B(r)$ and $C(r)$ with three evaluations, and compares $C(r)$ with $A(r)B(r)$. With $r=5$: $A(5)\equiv 8$, $B(5)\equiv 7$, $8·7=56\equiv 4$, but $C(5)\equiv 7$. The claim is wrong, and $r=5$ proves it.

def ev(c, x, p):                         # a stand-in: the lab asks for Horner's rule
    return sum(ci * pow(x, i, p) for i, ci in enumerate(c)) % p

p = 13
row_AB = [ev(A, r, p) * ev(B, r, p) % p for r in range(p)]
row_C = [ev(C, r, p) for r in range(p)]
assert row_AB == [8, 0, 2, 5, 6, 4, 0, 1, 2, 11, 0, 3, 10]
assert row_C == [8, 0, 8, 3, 1, 7, 2, 12, 12, 3, 2, 10, 10]
fooled = [r for r in range(p) if row_AB[r] == row_C[r]]
assert fooled == [0, 1, 12]
assert all((r ** 3 - r) % p == 0 for r in fooled)          # C − AB = x³ − x

The points that fool the check are exactly the roots of $C-AB=x^3-x=x(x-1)(x+1)$. There are three of them in every field, whatever $p$ is: 0 (which compares constant terms), 1 (the checksum) and $-1$. With $p=2^{31}-1$ the check misses with probability $3/p<1.5·{10}^{-9}$, and the lemma promises at most $6/p$ for any wrong $C$ of degree at most 6. Three evaluations cost $4n-3$ multiplications for $n$ coefficients in $A$ and $B$: $n-1$ each for $A$ and $B$, $2n-2$ for $C$, and one for the product.

Many variables: Schwartz–Zippel and Freivalds

Proof sketch. Induct on $n$; $n=1$ is the root bound. Write $f$ as a polynomial in $x_1$ whose coefficients are polynomials in the other variables, and let $x_1^k{f}_k(x_2,\dots ,x_n)$ be the top term with $f_k\ne 0$, so $\mathrm{deg}{f}_k\le d-k$. Either $f_k(r_2,\dots )=0$, with probability at most $(d-k)/|S|$ by induction, or it is nonzero, and then $f(x_1,r_2,\dots )$ is a nonzero polynomial of degree $k$ in $x_1$, which vanishes at $r_1$ with probability at most $k/|S|$. Add the two. $◻$

Freivalds' check. A service claims $C=AB$ for $n\times n$ matrices. Recomputing takes $n^3$ multiplications by the schoolbook method, and no known algorithm multiplies matrices in $O(n^2)$. Instead draw $r\in {𝔽}_p^n$ and compare $A(Br)$ with $Cr$: three matrix–vector products, $3n^2$ multiplications. If $D=AB-C\ne 0$, some row $d_i$ of $D$ is nonzero, and $(Dr{)}_i=d_i·r$ is a nonzero polynomial of degree 1 in $r_1,\dots ,r_n$. By Schwartz–Zippel it vanishes with probability at most $1/p$, so a wrong $C$ passes with probability at most $1/p$ per round, and $t$ independent rounds miss with probability at most $p^{-t}$. A correct $C$ always passes.

M = [[2, 1, 3], [0, 4, 1], [5, 2, 2]]
N = [[1, 3, 0], [2, 1, 4], [3, 0, 1]]
claimed = [[13, 7, 7], [11, 4, 18], [15, 17, 10]]      # row 1, column 2 (from 0) is wrong
times = lambda X, v: [sum(a * b for a, b in zip(row, v)) for row in X]
true = [[sum(M[i][k] * N[k][j] for k in range(3)) for j in range(3)] for i in range(3)]
assert true[1][2] == 17 and claimed[1][2] == 18

r = [1, 2, 3]
assert times(N, r) == [7, 16, 6]
assert times(M, times(N, r)) == [48, 70, 79] and times(claimed, r) == [48, 73, 79]
assert times(M, times(N, [5, 1, 0])) == times(claimed, [5, 1, 0])   # r[2] = 0 misses it

Counting rows, columns and coordinates from 0, the wrong entry is in row 1, column 2, and row 1 of the results differs by 3: the error times $r_2=3$. Any $r$ with $r_2=0$ misses it, which is why $r$ must be drawn from a large set: from $\{0,1{\}}^n$ the miss probability can be $1/2$. At $n=2000$ the check costs $1.2·{10}^7$ multiplications per round, against $8·{10}^9$ to recompute.

Two representations

A polynomial of degree less than $k$ is fixed by its $k$ coefficients, or by its values at any $k$ distinct points. Lagrange interpolation goes from values back to coefficients:

$$f(x)=\sum _i{y}_i{L}_i(x),L_i(x)=\prod _{j\ne i}\frac{x-x_j}{x_i-x_j}.$$

Each $L_i$ is 1 at $x_i$ and 0 at the other points, so the sum takes the value $y_i$ at $x_i$. It is the only such polynomial: two of them would differ by a polynomial of degree less than $k$ with $k$ roots, which the root bound forces to be zero.

Costs, in field operations: Lagrange takes $O(k^2)$ if you form ${\prod }_j(x-x_j)$ once and divide out one factor per basis polynomial, plus $k$ inverses; building each $L_i$ from scratch costs $O(k^3)$. Evaluating at $k$ points by Horner is $O(k^2)$. At the $N$-th roots of unity, module 25 goes both ways in $O(N\log N)$; at arbitrary points $O(k{\log }^{2}k)$ is known when module 25's transform is available, with a tree of products and fast division (cited). In value form, multiplication is pointwise.

Reed–Solomon codes: lose half, lose nothing

Store a message $(42,7,19)$ over ${𝔽}_{97}$ as the polynomial $m(x)=42+7x+19x^2$, and hand out six shares $(x,m(x))$ for $x=1,\dots ,6$. That is a Reed–Solomon code with $k=3$ and $n=6$. The shares need distinct points, so $n<p$.

Suppose shares 2, 4 and 5 are lost. From the kept points $x=1,3,6$ the Lagrange denominators are $(1-3)(1-6)=10$, $(3-1)(3-6)=-6\equiv 91$ and $(6-1)(6-3)=15$, with inverses 68, 16 and 13 mod 97. The basis polynomials come out as [60, 67, 68], [96, 82, 16] and [39, 45, 13], and $68L_1+40L_3+89L_6$ is [42, 7, 19].

q = 97
shares = [(x, ev([42, 7, 19], x, q)) for x in range(1, 7)]
assert shares == [(1, 68), (2, 35), (3, 40), (4, 83), (5, 67), (6, 89)]
kept = {1: 68, 3: 40, 6: 89}
basis = {1: [60, 67, 68], 3: [96, 82, 16], 6: [39, 45, 13]}
assert [10 * 68 % q, 91 * 16 % q, 15 * 13 % q] == [1, 1, 1]      # the inverses
assert all(ev(basis[i], j, q) == (i == j) for i in kept for j in kept)
message = [sum(kept[i] * basis[i][t] for i in kept) % q for t in range(3)]
assert message == [42, 7, 19]
assert all(ev(message, x, q) == y for x, y in shares)            # the lost shares return too

Three properties follow from the lemma.

• Erasures. Any $k$ shares determine $m$, so up to $n-k$ lost shares are recovered.
• Distance. Two different messages agree on at most $k-1$ points, so their share lists differ in at least $n-k+1$ places. Here that is 4.
• Errors. With distance $n-k+1$, up to $\lfloor (n-k)/2\rfloor$ corrupted shares can be corrected: only one message is that close. Here that is one share. Berlekamp and Welch's algorithm does it in polynomial time (stated, not proved here).

If $n$ is a power of two dividing $p-1$ and the points are the $n$-th roots of unity, encoding is one transform of module 25, $O(n\log n)$.

Polynomials and matchings

Module 30 decided whether a graph has a perfect matching with Edmonds' blossom algorithm. A determinant does it too. For a graph on vertices $0,\dots ,n-1$, give each edge $\{i,j\}$ with $i<j$ a variable $x_{ij}$, and build the Tutte matrix $T$: $T_{ij}=x_{ij}$, $T_{ji}=-x_{ij}$, and 0 where there is no edge. It is skew-symmetric, $T^{\mathsf{T}}=-T$.

Proof sketch. Expand $detT$ as a sum over permutations $\sigma$ of $sgn(\sigma ){\prod }_i{T}_{i\sigma (i)}$. A fixed point contributes a zero diagonal entry. Take a permutation with an odd cycle, and reverse the odd cycle through the smallest vertex that lies on any odd cycle. The result has the same sign, and skew-symmetry turns its product into the original times $(-1{)}^{\text{odd}}=-1$, so the two terms cancel, and reversing again gives back the first. Every surviving term uses only even cycles, and the edges of an even cycle split into two matchings of its vertices, so a nonzero $detT$ yields a perfect matching. Conversely, a perfect matching $M$ gives the permutation that swaps each pair of $M$. Its term is $\pm {\prod }_{e\in M}{x}_e^2$, and no other permutation produces that monomial, so nothing cancels it. $◻$

$detT$ has degree $n$. Lovász's test substitutes values drawn uniformly from ${𝔽}_p$ and computes the determinant by Gaussian elimination, $O(n^3)$ field operations. A nonzero value proves that a perfect matching exists. A zero is wrong with probability at most $n/p$, by Schwartz–Zippel.

The graph $G_1$ below is two triangles joined by the edge 2–3. Its only perfect matching is $\{01,23,45\}$. Remove the edge 2–3 to get $G_2$: two triangles, odd pieces, no perfect matching, and $detT=0$ for every substitution.

The block below computes determinants by the permutation expansion itself (a stand-in, fine for six vertices; the test uses elimination), and checks both the numbers and the cancellation:

from itertools import permutations
import random

def sign(s):
    seen, flips = set(), 0
    for i in range(len(s)):
        j, length = i, 0
        while j not in seen:
            seen.add(j)
            j, length = s[j], length + 1
        flips += max(length - 1, 0)
    return -1 if flips % 2 else 1

def odd_cycle(s):
    seen = set()
    for i in range(len(s)):
        j, length = i, 0
        while j not in seen:
            seen.add(j)
            j, length = s[j], length + 1
        if length % 2:
            return True
    return False

def tutte(n, values, p):
    T = [[0] * n for _ in range(n)]
    for (i, j), x in values.items():
        T[i][j], T[j][i] = x % p, -x % p
    return T

def det_terms(T, p, keep=lambda s: True):
    total = 0
    for s in permutations(range(len(T))):
        if keep(s):
            term = sign(s)
            for i in range(len(T)):
                term = term * T[i][s[i]]
            total += term
    return total % p

G1 = {(0, 1): 3, (0, 2): 5, (1, 2): 7, (2, 3): 2, (3, 4): 4, (3, 5): 6, (4, 5): 8}
assert det_terms(tutte(6, G1, 101), 101) == 82 == (3 * 2 * 8) ** 2 % 101

rng = random.Random(2401)
for _ in range(20):
    vals = {e: rng.randrange(101) for e in G1}
    T = tutte(6, vals, 101)
    assert det_terms(T, 101, keep=odd_cycle) == 0                   # odd cycles cancel
    assert det_terms(T, 101) == (vals[0, 1] * vals[2, 3] * vals[4, 5]) ** 2 % 101
    G2 = {e: x for e, x in vals.items() if e != (2, 3)}
    assert det_terms(tutte(6, G2, 101), 101) == 0

The second-to-last assert tests an identity between two polynomials, $detT$ and $(x_{01}{x}_{23}{x}_{45}{)}^2$, at twenty random points: the method of this module, used on itself.

Which answer can be wrong. "Yes" is always right. "No" can be wrong: for $G_1$ the determinant is zero exactly when one of $x_{01},x_{23},x_{45}$ is 0. Module 30's final forest proves a "no" with a Tutte–Berge set $U$ that anyone can check; a zero determinant proves nothing, and it does not name a matching either. One way to find one: delete each edge in turn and keep the deletion whenever the determinant stays nonzero. A nonzero value is never wrong, so no needed edge is deleted, and with probability at least $1-En/p$ (a union bound over the $E$ tests) the edges left are exactly a perfect matching. Faster algebraic methods run in $O(n^{\omega })$ with fast matrix multiplication (Mucha and Sankowski, 2004, cited). The rank of $T$ at a random point is twice the size of a maximum matching with probability at least $1-n/p$ (Lovász, 1979, cited).

Complexity

All costs count field operations mod $p$, worst case over inputs; error bounds are over the algorithm's coins, for every input.

• Product check for polynomials with $n$ coefficients and a claimed $C$ of degree at most $2n-2$: $4n-3$ multiplications per round, false "equal" with probability at most $(2n-2)/p$. Recomputing: $n^2$, or $O(n\log n)$ with module 25.
• Freivalds: $3n^2$ multiplications per round, false "equal" at most $1/p$ per round. Recomputing: $n^3$ by the schoolbook method; the best known exponent is below 2.372, still above 2.
• Interpolation of $k$ points: $O(k^2)$, plus $k$ inverses.
• Tutte test: $O(n^3)$ per trial, false "no" at most $n/p$; "yes" is never wrong.

A deterministic checker must read all $n^2$ entries of $C$ on a correct input: changing an unread entry would leave its run, and its "yes", unchanged. Freivalds reads each entry once per round.

Measure the claim

How close is the $n/p$ bound for $G_1$? Its determinant is $(x_{01}{x}_{23}{x}_{45}{)}^2$, which is zero exactly when one of three independent uniform values is 0:

def false_no(p):             # triples of values for the matching edges with a zero product
    return sum(a * b * c % p == 0 for a in range(p) for b in range(p) for c in range(p)) / p ** 3

assert false_no(5) == 61 / 125 == 0.488
assert round(false_no(11), 4) == 0.2487 and round(false_no(101), 4) == 0.0294
P = 2 ** 31 - 1
assert round((P ** 3 - (P - 1) ** 3) / P ** 3 * 1e9, 2) == 1.40 and round(6 / P * 1e9, 2) == 2.79
assert all(false_no(p) <= 3 / p for p in (5, 11, 101)) and (200 / P) ** 2 < 1e-14

At $p=5$ the bound exceeds 1 and says nothing; the lemma needs $|S|$ well above the degree. Here the truth is below half the bound. That is no accident: $detT$ is the square of a polynomial of degree $n/2$, the Pfaffian of $T$ (cited, not proved here), so Schwartz–Zippel applied to the Pfaffian gives $(n/2)/p$, which is 0.6 at $p=5$. The bound is a guarantee for every graph, not a prediction for this one. Two trials at $p=2^{31}-1$ push the error for any 200-vertex graph below ${10}^{-14}$.

A problem that looks different

A vault code must be split among five officers so that any three of them can open the vault together, while any two, pooling everything they hold, learn nothing at all about the code. What should each officer be given, and where in it would the code live? The lab's last problem is a different one.

Practise

In the lab you write the polynomial operations and count roots with and without a field; trace the recovery of a message from three shares; test graphs for perfect matchings and extract one; count Freivalds' multiplications and how often it misses; and settle a question between two sites that doesn't say what it is.

Recap

You can now: prove the root bound and say where it needs a field; bound the one-sided error of a random-evaluation test with Schwartz–Zippel; check a polynomial or matrix product without recomputing it; recover Reed–Solomon shares by interpolation; and test for a perfect matching with one random determinant.

Invariant: two different polynomials of degree at most $d$ over a field agree on at most $d$ points, so a uniform point of a set $S$ exposes the difference with probability at least $1-d/|S|$.

Complexity achieved: a product of $n\times n$ matrices checked in $3n^2$ multiplications per round (error at most $1/p$) instead of $n^3$; a polynomial product in $O(n)$ instead of $O(n\log n)$; perfect matching in $O(n^3)$ field operations per trial, false "no" at most $n/p$.

Failure mode: arithmetic modulo a composite, a random set too small for the degree, or a check that shares the computation's modulus.

In real software: QR codes carry Reed–Solomon error correction; the ZXing library's QR encoder computes it with ReedSolomonEncoder over the field GenericGF.QR_CODE_FIELD_256. Linux software RAID 6 computes its second parity block (Q) by evaluating the data blocks as a polynomial over ${𝔽}_{2^8}$ at the point 2 by Horner's rule (lib/raid/raid6/int.uc), so any two lost disks can be rebuilt.

Retrieval (module 05): Karp–Rabin compared two $n$-bit numbers $x\ne y$ through their residues modulo a random prime. What bounded the error there, and what is random in today's test instead?

Check yourself

1. Why does Freivalds' check miss a wrong $C$ with probability at most $1/p$? Which coordinate of $r$ carries the randomness in the lesson's example?
2. Do all the arithmetic modulo $2^{32}$ instead of a prime, because it is faster. Which step of the root bound breaks, and how often could Freivalds' check then miss an error of $2^{31}$?
3. A 200-vertex graph: compare Lovász's determinant test with module 30's blossom algorithm. What does each return, how can each be wrong, and when does the difference matter?

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.