Polynomials

Property 1: A non-zero polynomial of degree \(d\) has at most \(d\) roots.

Proof: Let \(a_1, \dots, a_d\) be the distinct roots of \(p\). It can be shown that \(p\) can be written as:

\begin{align} p(x) = c(x-a_1)(x-a_2)\cdots (x-a_d) \notag \end{align}

for some constant \(c\).° Then, if we have another root \(a \neq a_1, \dots, a_d\), then \(p(a) \neq 0\), so no other \(a\) can be a root. \(\square\)

Property 2: Given \(d+1\) points \((x_1, y_1), (x_2, y_2), \dots , (x_{d+1},y_{d+1})\) with all \(x_i\) distinct, there exists a unique polynomial of degree \(\leq d\) such that \(p(x_i) = y_i\) for \(1 \leq i \leq d+1\).

Proof: We introduce the Lagrange interpolation algorithm to construct \(p(x)\). Suppose we can construct basis polynomials \(\Delta_i(x)\) for \(1 \leq i \leq d+1\) such that:

\begin{align} \Delta_i(x) = \begin{cases} 1 & x=x_i \\ 0 & x=x_j, \; j\neq i \end{cases} \notag \end{align}

Then, the following Lagrange polynomial fits the points given:

\begin{align} \boxed{p(x) = \sum_{i=1}^{d+1} y_i \Delta_i(x)} \end{align}

Realize that for some \(x_i\), \(p(x_i) = y_1\Delta_1(x_i) + y_2\Delta_2(x_i) + \cdots + y_{d+1}\Delta_{d+1}(x_i)\) has \(\Delta_k = 0\) for all \(k\) except when \(k=i\), so \(p(x_i) = y_i\Delta_i(x_i)=y_i\). Therefore, it is sufficient to prove that such basis polynomials \(\Delta_i\) exist.

Let \(q_i(x)=(x-x_1)(x-x_2)\cdots (x-x_{i-1})(x-x_{i+1})\cdots (x-x_{d+1})\). Then, the degree of \(q_i\) is \(d\), \(q_i(x_j)=0 \; \forall j \neq i\), but \(q_i(x_i)=\prod_{j\neq i} (x_i-x_j) \neq 0\). So, we can define the basis polynomials as:

\begin{align} \boxed{\Delta_i(x) = \frac{q_i(x)}{q_i(x_i)}} \end{align}

We see that \(\Delta_i(x_j) = \frac{q_i(x_j)}{q_i(x_i)} = 0 \; \forall j \neq i\), and \(\Delta_i(x_i) = \frac{q_i(x_i)}{q_i(x_i)} = 1\), so we are done.

Now, it remains to prove that such a polynomial is unique. Suppose for contradiction that there exists two different polynomials \(p_1(x), p_2(x)\) of degree \(\leq d\) that both go through the \(d+1\) points.

Then \(q(x) = p_1(x)-p_2(x)\) is a non-zero polynomial of degree \(\leq d\). But \(q(x_i) = p_1(x_i)-p_2(x_i)=0\) for \(x_1,x_2,\dots , x_{d+1}\). So \(q\) is a polynomial of degree \(\leq d\) with \(d+1\) roots, which is a contradiction, and we are done. \(\square\)

Let \(p\) be prime. Then integers modulo \(p\) behave like real numbers in that they support \(0\) and \(1\), as well as the operators of addition, subtraction, multiplication, and division (all numbers have an inverse when \(p\) is prime).

Technically, integers modulo \(p\) is a field \(\mathbb{Z}_p\) or \(\text{GF}[p]\). Unlike \(\mathbb{Z}, \mathbb{N}\), etc., \(\text{GF}[p]\) is a finite field or Galois field. The key is that polynomials over \(\text{GF}[p]\) behave like real polynomials in that they satisfies the two properties defined above.

Say we want to protect against \(k\) erasure errors. Then, we wish to be able to reconstruct \(m_1m_2\dots m_n\) from the codeword \(c_1c_2\dots c_{n+k}\).

Let \(q > n+k\) be a large prime such that packets are integers modulo \(q\). Let \(p(x)\) be the unique degree \(n-1\) polynomial modulo \(q\) through the points \((i, m_i)\) for \(1 \leq i \leq n\).

The idea is simple: we send \(k\) more points than we actually need. The codeword \(c_1c_2\dots c_{n+k}\) is built where \(c_j =p(j)\) for \(1 \leq j \leq n+k\). We can now reconstruct \(p(x)\) from any \(n\) of the \(c_i\) using Lagrange interpolation, and we are protected against up to \(k\) erasures.

Let \(q > n+2k\) be prime and let \(p(x)\) be the unique degree \(n-1\) polynomial modulo \(q\) through the points \((i, m_i)\) where \(1 \leq i \leq n\). Then, we want to construct a codeword \(c_1c_2 \dots c_{n+2k}\) where \(c_j=p(j)\) for \(1 \leq j \leq n+2k\).

We want to show that we can reconstruct \(p(x)\) given \(n+2k\) points where up to \(k\) of the points can be corrupted (and we don’t know which ones).

First, we introduce the error-locator polynomial \(E(x)\) that is defined as:

\begin{align} E(x) = (x-e_1)(x-e_2)\cdots (x-e_k) \end{align}

where \(e_i\) is the x-position of an error. Note that for now, we don’t actually know the values of \(e_i\).

The key is that:

\begin{align} \boxed{P(i)E(i) = r_iE(i)} \end{align}

for all \(1 \leq i \leq n+2k\). To see why this is true, consider two cases. When \(P(i) = r_i\), it is accurate, and the equality holds. However, when there is an error, \(P(i) \neq r_i\), but then since it is an error \(E(i)=0\), and the equality becomes \(0=0\) which is true.

Now, let \(Q(x)=P(x)E(x)\). Then \(Q\) has degree \(n+k-1\), and (5) becomes \(Q(i) = r_iE(i)\). We can write:

\begin{align} Q(x) &= a_{n+k-1}x^{n+k-1} + a_{n+k-2}x^{n+k-2} + \cdots + a_1x + a_0 \notag \\ E(x) &= x^k + b_{k-1}x^{k-1} + \cdots + b_1x + b_0 \notag \end{align}

plugging in the \(n+2k\) points \((i, r_i)\) gives us a system of \(n+2k\) equations in \(n+2k\) unknowns, which is sufficient to solve for the polynomials \(Q\) and \(E\). Then, we can find the original polynomial \(P(x) = \frac{Q(x)}{E(x)}\).