Polynomials

Introduction

Polynomials constitute of a rich class of functions. A polynomial in a single variable defined on a field $\mathbb{F}$ is a function of the form:

where the variable $x$ and coefficients $c_i \in \mathbb{F}, \forall i \in [d]$. The integer $d$ is called the degree of $p(x)$.

Properties

Polynomials have two fundamental properties:

1. A non-zero polynomial of degree $d$ has at most $d$ distinct roots.
2. Given $d + 1$ pairs $\{ (a_i, b_i) \in \mathbb{F}^2 : i \in [d + 1] \}$, such that $a_i \neq a_j$ for $i \neq j$, there is a unique polynomial $p(x)$ with degree at most $d$ that goes through all these points.

Number of Distinct Roots

We prove claim 1 by induction.

1. The base case is $d = 0$. As the polynomial is non-zero, it does not have any root.

2. Suppose the claim holds for non-negative integers $\le d$ and $p(x)$ is a polynomial of degree $d + 1$. If $p(x)$ has a root $z$, by polynomial division, we can rewrite $p(x)$ as

   $$p(x) = (x - a)^k q(x)$$

   where $k \ge 1$ is the largest integer such that $(x - a )^k | p(x)$. Hence $q(x)$ has degree $d + 1 - k$. For any $z \neq a$, if $p(z) = (z - a)^k q( z ) = 0$, then $q(z) = 0$, which implies that $z$ is a root of $q(x)$. By the inductive hypothesis, it has at most $d + 1 - k$ distinct roots.

Remark: We don't claim that $p(x)$ must have a root, but it has at most $d$ distinct roots, if it has degree $d$.

Unique Interpolation

We first prove the existence of the interpolation, then prove its uniqueness.

Existence of Interpolation

The method is called Lagrange Interpolation. Our basic building blocks are a collection of special polynomials $\{ \delta_i( x ) : i \in [d + 1] \}$, which we call signal functions, such that $\forall i \in [d + 1]$,

1. The polynomial $\delta_i( x )$ has degree $d$.

2. The polynomial takes value 1 at $a_i$, i.e., $\delta_i(a_i) = 1$.

3. The polynomial takes value 0 at $a_j$ for $j \neq i$, i.e., $\delta_i(a_j) = 0$.

First, define $\delta_i'(x) = \prod_{j \neq i} (x - a_j)$. It equals to $0$ on $a_j, \forall j \neq i$. We normalize its value at $a_i$, to obtain

With proper scaling and summation, $p(x)$ is given by

Uniqueness of Interpolation

Suppose for contradiction that there is another polynomial $q(x)$, s.t., $p(a_i) = q(a_i), \forall i \in [d + 1]$. Let $r(x) = p(x) - q(x)$. If $r(x) \equiv 0$, then the claim holds trivially. Otherwise, $r(x)$ is a non-zero polynomial with degree at most $d$. Claim 1 asserts that $r(x)$ has at most $d$ distinct roots, contradicting that $r(a_i) = 0$ for $i \in [d + 1]$.

Remark: uniqueness can also be proven by showing the following equation has unique solution $[ c_d, c_{d - 1}, ..., c_0]$:

The left matrix is called Vandermonde Matrix, whose determinant is

which is non-zero when $a_i \neq a_j$.

Applications

Pairwise Independent Hash Function.

Assume that we want to map a set of elements $\mathcal{U} \doteq \{0, 1, ..., u - 1\}$ into some set $\mathbb{F}$, by picking a function $h$ uniformly at random from a family of functions $\mathcal{H} \doteq \{ h : \mathcal{U} \rightarrow \mathbb{F} \}$. For an $i \in \mathcal{U}$, the value $Y_i \doteq h(i)$ is a random variable. The $Y_i$'s are called pairwise independent, if for $i, j \in \mathcal{U}, i \neq j$ and $b_i, b_j \in \mathbb{F}$,

Similarly we can define $k$-wise independence. For any $0 \le i_1 < i_2 <... < i_k < u$, and $b_{i_1} , b_{i_2}, ..., b_{i_k} \in \mathbb{F}$, we have

Finite Field $\mathbb{F}_p$

Now we restrict our discussion to the finite field $\mathbb{F}_p = \{0, 1, ..., p - 1\}$, where $p$ is a prime larger than $u$.

Theorem. The set of all possible functions from $\mathcal{U}$ to $\mathbb{F}_p$ is pairwise independent.

Proof:

$\square$

However, each of the functions takes $u \log p$ bits to represent. To reduce the space, we restrict to the family:

which contains all polynomials with degree at most 1 in the field $\mathbb{F}_p$, i.e., all lines in $\mathbb{F}_p$. There are $p^2$ such functions.

We know that, for given $x_1, x_2 \in \mathcal{U}, x_1 \neq x_2$, then $\forall y_1, y_2 \in \mathbb{F}_p$, there is a unique line that goes through $(x_1, y_1), (x_2, y_2)$. If we pick a line uniformly at random from $\mathcal{H}_1$, then the probability that it goes through this pair of points is ${1} / {p^2}$.

This already implies pairwise independence, as

In a similar manner, we can construct a $k$-wise independent family:

Note that $|\mathcal{H}| = p^{k}$. For $0 \le x_1 < x_2 < ... < x_k < u$, and $y_1, y_2, ..., y_k \in \mathbb{F}_p$, there is a unique polynomial that goes through the points $(x_1, y_1), (x_2, y_2), ..., (x_k, y_k)$.

Key-Sharing

Suppose that we have $n$-candidates who knows some information about the key and we require that only when no less than $k$ of them aggragate their information can they figure the actual key. No group of less than $k$ candidates can achieve this. The way we do it is as follows:

1. Select a large prime number $p$.
2. Select $k+1$ random numbers $y_0, y_1, ..., y_k$ from $[p-1]$.
3. Generate the unique polynomial $p(x)$ with degree $k$ that goes through $(0, y_0), (1, y_1), ..., (k, y_k)$.
4. Inform the value of $p(1)$ to the first person, $p(2)$ to the second one, ... and $p(n)$ to the $n$-th person.

If $k - 1$ people pool their keys together, then there are $p$ possible polynomials that goes through all their keys, each has different value at point 0. The probability of guessing the correct key is given by $\frac{1}{p}$.

Reference

[1]. CS 70. Discrete Mathematics and Probability Theory.