Polynomial Spaces Over Finite Fields

Polynomials with Coefficients in a Prime Field

Polynomials are familiar from calculus and algebra, but their coefficients need not be real numbers. For a prime number \(p\), the field \(\mathbb{F}_p\) consists of residue classes of integers modulo \(p\). Its addition and multiplication are performed modulo \(p\); for example, in \(\mathbb{F}_5\), \(3+4=2\) and \(2\cdot 4=3\). The prime condition matters because every nonzero element of \(\mathbb{F}_p\) has a multiplicative inverse, so the scalars form a field.

A polynomial over \(\mathbb{F}_p\) is a formal expression whose coefficients belong to that field. Equality of polynomials means equality of corresponding coefficients; it is not defined by comparing their values at inputs. For a nonnegative integer \(d\), we collect all polynomials whose powers of \(x\) are at most \(d\) into one space. This provides a concrete example of a finite-dimensional vector space over a field other than \(\mathbb{R}\).

The zero polynomial belongs to every \(\mathcal{P}_d(\mathbb{F}_p)\), with all coefficients equal to zero. A polynomial may have a zero coefficient on its highest listed power; for example, \(2+x+0x^2\) is in \(\mathcal{P}_2(\mathbb{F}_5)\) and is the same polynomial as \(2+x\). Consequently, the condition is “degree at most \(d\),” not “degree exactly \(d\).”

Adding, Scaling, and Reading Coordinates

Write two elements of \(\mathcal{P}_d(\mathbb{F}_p)\) as \(f(x)=\sum_{i=0}^d a_ix^i\) and \(g(x)=\sum_{i=0}^d b_ix^i\). Their sum is found by adding coefficients of matching powers, and a scalar multiple is found by multiplying each coefficient by the scalar. Both calculations take place in the field.

The powers \(1,x,\dots,x^d\) give a natural ordered list for recording coefficients. With this order, the coordinate vector of \(f\) is the column whose entries are its coefficients from the constant term upward. The order matters: the first entry records the coefficient of \(1\), not the coefficient of \(x^d\).

The Standard Basis and the Vector-Space Structure

For each \(i\) from \(0\) to \(d\), the monomial \(x^i\) has coefficient \(1\) on its own power and \(0\) on every other power. These monomials span the polynomial space because every allowed polynomial is built by multiplying them by coefficients and adding. They are also independent: a linear combination of them is the zero polynomial only when every coefficient is zero.

Proof. Each polynomial in the set has \(d+1\) coefficients in \(\mathbb{F}_p\). Adding two such polynomials adds corresponding coefficients in \(\mathbb{F}_p\), so the result again has \(d+1\) coefficients in that field. Multiplying by a scalar in \(\mathbb{F}_p\) also leaves every coefficient in the field. The zero polynomial and additive inverses are obtained by taking all coefficients to be zero or by negating each coefficient. The vector-space laws for addition and scalar multiplication hold coefficient by coefficient because they hold in \(\mathbb{F}_p\). Thus this set, with the stated operations, is a vector space.

Now let \(f(x)=a_0+a_1x+\cdots+a_dx^d\). Then \(f=\sum_{i=0}^d a_ix^i\), so the listed monomials span the space. If \(\sum_{i=0}^d c_ix^i\) is the zero polynomial, equality of formal polynomials says its coefficient on every power is zero. Hence \(c_i=0\) for every \(i\), proving independence. Since the coefficients \(a_i\) in the defining expression for \(f\) are uniquely determined by the polynomial, its coefficient column is unique as well. Therefore the list is a basis and the stated coordinates are well-defined. \(\square\)

This proof also explains how polynomial calculations translate directly into coordinate calculations: addition of polynomials becomes addition of their columns, and scalar multiplication of a polynomial becomes scalar multiplication of its column. No extra conversion rule is needed after the coefficient order has been fixed.

Common Pitfall: Forgetting That Coefficients Are Field Elements

A frequent error is to do the polynomial algebra over the integers and reduce only after the full expression is finished. For example, a student might write \(2x+3x=5x\) in \(\mathbb{F}_5[x]\), then conclude that the sum is a nonzero polynomial. That conclusion treats the coefficient \(5\) as an integer coefficient rather than as an element of \(\mathbb{F}_5\).

The correction is to reduce the coefficient in the field: \(2+3=0\) in \(\mathbb{F}_5\), so \(2x+3x=0x\), the zero polynomial. The corresponding coordinate calculation is \(\begin{bmatrix}0\\2\end{bmatrix}+\begin{bmatrix}0\\3\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix}\) in \(\mathbb{F}_5^2\), using the ordered list \((1,x)\). Keeping the field visible in each calculation prevents integer arithmetic from slipping into a finite-field problem.

The coordinate description is useful because it turns every polynomial in \(\mathcal{P}_d(\mathbb{F}_p)\) into a column of \(d+1\) field elements. The basis theorem guarantees that this representation loses no information: each polynomial has exactly one such column, and every column in \(\mathbb{F}_p^{d+1}\) gives one polynomial. The degree bound sets the number of coordinates, while the field determines the arithmetic applied to them.