Polynomials

A polynomial over a ring ^2.5$F$ is an expression of the form

$$p(x)=a_0+a_1x+...+a_{n-1}x^{n-1}+a_nx^n,$$

where $x$ is an independent variable and $a_0,a_1,...,a_n\in F$ . We sometimes say that $p$ is a polynomial ``over'' $F$ . If $a_n\not= 0$ then $n$ is called the degree and we write deg$(p)=n$ and call $a_n$ the leading coefficient. A polynomial with leading coefficient equal to $1$ is called a monic polynomial. The collection of all such polynomials is denoted by $F[x]$ .

Let's slow down and think about this for a second. How is this expression for $p(x)$ rigorously defined? For example, we could assume that the possible values of $x$ range over $F$ , so the expression $p(x)$ is well-defined. Unfortunately, if $F$ were a finite field (or finite ring) then the set of values of $p(x)$ , for $x\in F$ , does not uniquely determine the coefficients $a_i$ of $p$ . (See Exercise 2.2.20 below.) This is not what we we want, since we want to say that two polynomials are equal if and only if the coefficients are all equal. Since we might be in a situation where $F$ is finite, we cannot define a polynomial in terms of its values.

Instead, we simply assume that a polynomial is a formal expression where $x^i$ is a ``place-marker'' for its coefficients $a_i$ .

A sequence $\{a_i\}_{i=0}^\infty$ of elements of $F$ will be called finite if there are only finitely many non-zero terms in the sequence. Let ${\cal S}_F$ denote the set of all such finite sequences. Note that there is a map

$$C:F[x]\rightarrow {\cal S}_F$$

given by sending $p(x)=a_0+a_1x+...+a_{n-1}x^{n-1}+a_nx^n$ to the sequence $\{a_0,a_1,...,a_n,0,0,...\}$ .

We define the addition and multiplication of two such formal polynomial expressions in the usual way ^2.6: addition is ``coefficient-wise'',

$$\begin{array}{c} (a_0+a_1x+...+a_nx^n)+(b_0+b_1x+...+b_nx^n)=\\ a_0+b_0+(a_1+b_1)x+...+(a_n+b_n)x^n, \end{array}$$

and multiplication is defined by

$$\begin{array}{c} (a_0+a_1x+...)\cdot +(b_0+b_1x+...)=\\ c_0+c_1x+..., \end{array}$$

where $c_n=\sum_{i=0}^na_ib_{n-i}$ . With this definition, two polynomials are equal if and only if the coefficients are all equal.

This contrast and distinction of formal expressions versus the idea of a polynomial being an $F$ -valued function is a moot point for polynomials with coefficients in $\mathbb{R}$ or $\mathbb{C}$ (or in any infinite field, for that matter), but it is important for polynomials with coefficients in a finite field because of the phenomenon illustrated in the following example.

Let $F$ be any field. First, we observe that any finite set of points in the ``plane'' $F^2$ may be ``interpolated'' using a polynomial (which depends on these points and is of of suitably high degree). The precise statement is the following result.

Theorem 2.2.1 (Lagrange interpolation formula)   Let $x_1,x_2,...,x_n\in F$ be $n$ distinct elements and let $f:F\rightarrow F$ be any function. Then there is a polynomial function $p(x)$ of degree $n$ such that $p(x_i)=f(x_i)$ , for $1\leq i\leq n$ . In fact,

$$\begin{array}{c} p(x)={\prod_{1\leq i\leq n, i\not= 1}(x-x_... ... \prod_{1\leq i\leq n, i\not= n}(x_n-x_i)}f(x_n). \end{array}$$

proof: ``By inspection.'' $\Box$

Example 2.2.2  

We will see that if $F$ is a finite field, every function $f:F\rightarrow F$ may be written down as a polynomial with coefficients in $F$ using the Lagrange interpolation formula. Let $F$ have elements $F=\{x_1,x_2,...,x_n\}$ and let $f:F\rightarrow F$ be any function. Let $p(x)$ be as in the Lagrange interpolation formula. Then $f(x)=p(x)$ for all $x\in F$ . In other words, over a finite field, any function many be represented as a polynomial function. Furthermore, this representation is not unique.

This is why it is important not to assume that ``$x$ '' is a ``variable with values in $F$ '', as is commonly done in calculus. It is better to think of the powers $x^i$ of a polynomial over a finite field as ``placeholders'' for the coefficients ^2.7.