Reed-Solomon Code Definition

A Reed-Solomon code is a specific type of error-correcting code that consists of the evaluations of a polynomial $p(x)$ over a set of elements from a finite field. For a Reed-Solomon code to be defined, the following must hold:

• $p(x)$ is a polynomial of degree $\leq k-1$, where $k$ is the message length.
• The evaluations of $p(x)$ are performed over a domain $D$, which is typically a subset of the finite field $\mathbb{F}$, such as a multiplicative subgroup.

The result of evaluating $p(x)$ over $D$ forms the codeword for the polynomial $p(x)$.

Structure of $D$

In the FRI protocol, $D$ is a multiplicative subgroup of a finite field $\mathbb{F}$. This ensures:

1. $|D| = n$, where $n$ is a power of 2.
2. $D$ is closed under multiplication (i.e., $x \cdot y \in D$ for $x, y \in D$).
3. $D$ is evenly distributed in the field, which ensures uniform spacing for evaluations.

Evaluating $p(x)$

When $p(x)$ is evaluated over $D$ it generates a sequence of $n$ field elements:

$\text{Codeword} = [p(x_0), p(x_1), \dots, p(x_{n-1})]$,

where $x_i \in D$.

This sequence has the following key properties:

1. Low-Degree Polynomial Property: Since $p(x)$ is of degree $≤d$, the resulting codeword satisfies the defining property of Reed-Solomon codes, which require the polynomial to have a degree less than $k−1$ (with $k$ being the designed message length).
2. Unique Mapping: The evaluations uniquely represent the polynomial $p(x)$, as $p(x)$ is uniquely defined by $d+1$ coefficients, and $|D| > d+1$ ensures sufficient redundancy.
3. Linear Code: The code formed by all possible evaluations of polynomials $p(x)$ of degree $≤d$ over $D$ forms a linear code, a defining characteristic of Reed-Solomon codes.

Rate $\rho$

In the FRI context, the rate $\rho$ determines the fraction of the domain $D$ that the evaluations "fill." For $\rho = 1/2$, the polynomial degree $d$ satisfies: $d+1 = \frac{|D|}{2}$.