Evaluation Codes and Coordinate Changes

Status: Established

The preceding chapters described polynomials through their Boolean kernel coefficients. This chapter passes from coefficient tables to evaluations on a set of distinct field points.

The main result is an exact vector-space identification: the low-degree character space maps onto a Reed–Solomon evaluation code. The identification does not imply that Hamming distance in coefficient coordinates equals Hamming distance in evaluation coordinates.

7.1 Evaluation on distinct points

Let $m\ge 1$ and let

$$N=2^m.$$

Let $\mathbb{F}$ be a field containing at least $N$ elements, and fix an ordered tuple of pairwise distinct points

$$D=({\alpha }_0,\dots ,{\alpha }_{N-1})\in {\mathbb{F}}^N.$$

For an integer $d$ with $1\le d\le N$, write

$$\mathbb{F}[X{]}_{<d}=\{f\in \mathbb{F}[X]:\mathrm{deg}f<d\}.$$

Define the evaluation map

$${\mathrm{Ev}}_D:\mathbb{F}[X{]}_{<N}⟶{\mathbb{F}}^N$$

by

$${\mathrm{Ev}}_D(f)=(f({\alpha }_0),\dots ,f({\alpha }_{N-1})).$$

Proposition 7.1 — Evaluation is an isomorphism

The map ${\mathrm{Ev}}_D$ is a linear isomorphism.

Proof

Linearity is immediate. Suppose $f\in \mathbb{F}[X{]}_{<N}$ satisfies ${\mathrm{Ev}}_D(f)=0$. Then $f$ vanishes at all $N$ distinct points of $D$. A nonzero polynomial of degree less than $N$ cannot have $N$ distinct roots, so $f=0$.

Thus ${\mathrm{Ev}}_D$ is injective. Its domain and codomain both have dimension $N$, so it is an isomorphism. $\square$

Equivalently, the Vandermonde matrix

$$V_D=({\alpha }_j^e{)}_{0\le j,e<N}$$

is invertible.

7.2 Evaluation from kernel coordinates

Recall the Boolean kernel polynomials

$$K_y(X)=\prod _{i=0}^{m-1}\left(X^{2^i}+y_i\right),y\in {\mathbb{B}}_m.$$

By Chapter 3, the family

$$\{K_y:y\in {\mathbb{B}}_m\}$$

is a basis of $\mathbb{F}[X{]}_{<N}$. Therefore every coefficient table $\lambda :{\mathbb{B}}_m\to \mathbb{F}$ determines a unique polynomial

$$U_{\lambda }(X)=\sum _{y\in {\mathbb{B}}_m}{\lambda }_y{K}_y(X).$$

Define the kernel-evaluation map

$${\Phi }_D:{\mathbb{F}}^{{\mathbb{B}}_m}⟶{\mathbb{F}}^N$$

by

$${\Phi }_D(\lambda )={\mathrm{Ev}}_D(U_{\lambda }).$$

Proposition 7.2 — Kernel evaluation is an isomorphism

The map ${\Phi }_D$ is a linear isomorphism.

Proof

The kernel-synthesis map

$$\lambda ⟼U_{\lambda }$$

is an isomorphism because the kernel polynomials form a basis. Proposition 7.1 shows that ${\mathrm{Ev}}_D$ is also an isomorphism. Their composition ${\Phi }_D$ is therefore an isomorphism. $\square$

In matrix form,

$${\Phi }_D(\lambda )=M_D\lambda ,$$

where, after fixing the Boolean ordering of Chapter 1,

$$(M_D{)}_{j,y}=K_y({\alpha }_j).$$

The matrix $M_D$ is invertible.

7.3 Reed–Solomon evaluation spaces

For $1\le d\le N$, define

$$\mathrm{RS}(D,d)={\mathrm{Ev}}_D(\mathbb{F}[X{]}_{<d}).$$

This is the Reed–Solomon evaluation space of degree bound $d$. Since ${\mathrm{Ev}}_D$ is injective on $\mathbb{F}[X{]}_{<N}$,

$$\dim \mathrm{RS}(D,d)=d.$$

For the dyadic degree bound $d=2^k$, Chapter 4 identified the corresponding kernel coefficient space as

$${\mathsf{CH}}_{m,k}=\{\lambda :\mathrm{deg}{U}_{\lambda }<2^k\}.$$

Theorem 7.3 — Character-space/Reed–Solomon correspondence

For every $k\in \{0,\dots ,m\}$,

$${\Phi }_D\left({\mathsf{CH}}_{m,k}\right)=\mathrm{RS}(D,2^k).$$

Moreover, the restricted map

$${\Phi }_D{|}_{{\mathsf{CH}}_{m,k}}:{\mathsf{CH}}_{m,k}⟶\mathrm{RS}(D,2^k)$$

is a linear isomorphism.

Proof

By the low-degree characterization from Chapter 4,

$$\lambda \in {\mathsf{CH}}_{m,k}⟺U_{\lambda }\in \mathbb{F}[X{]}_{<2^k}.$$

Applying ${\mathrm{Ev}}_D$ to both sides gives

$${\Phi }_D\left({\mathsf{CH}}_{m,k}\right)={\mathrm{Ev}}_D(\mathbb{F}[X{]}_{<2^k})=\mathrm{RS}(D,2^k).$$

The restriction is injective because ${\Phi }_D$ is injective, and it is surjective by the displayed equality. $\square$

As a consistency check,

$$\dim {\mathsf{CH}}_{m,k}=2^k=\dim \mathrm{RS}(D,2^k).$$

7.4 Minimum distance in evaluation coordinates

For $v\in {\mathbb{F}}^N$, let ${\mathrm{wt}}_H(v)$ denote its Hamming weight. The minimum distance of a nonzero linear code $C\subseteq {\mathbb{F}}^N$ is

$$d_{\min }(C)=\underset{0\ne c\in C}{\min }{\mathrm{wt}}_H(c).$$

Proposition 7.4 — Reed–Solomon minimum distance

For $1\le d\le N$,

$$d_{\min }(\mathrm{RS}(D,d))=N-d+1.$$

Proof

Let $0\ne f\in \mathbb{F}[X{]}_{<d}$. The polynomial $f$ has at most $d-1$ roots in $\mathbb{F}$. Hence its evaluation vector has at least $N-(d-1)=N-d+1$ nonzero coordinates.

To attain this bound, choose any $d-1$ points from $D$ and let $f$ be the product of the corresponding linear factors. Then $\mathrm{deg}f=d-1$, and $f$ vanishes at exactly those selected evaluation points. Its evaluation vector has Hamming weight $N-d+1$. $\square$

Consequently,

$$d_{\min }({\Phi }_D({\mathsf{CH}}_{m,k}))=N-2^k+1.$$

This distance statement concerns the image inside the evaluation-coordinate space ${\mathbb{F}}^N$.

7.5 Coordinate equivalence is not proximity equivalence

The map ${\Phi }_D$ is invertible and linear, but a general invertible linear map does not preserve Hamming weight or Hamming distance.

In particular, one must not infer that

$${\mathrm{dist}}_H(\lambda ,{\mathsf{CH}}_{m,k})={\mathrm{dist}}_H({\Phi }_D(\lambda ),\mathrm{RS}(D,2^k)).$$

This equality is generally false. The two sides measure distance in different coordinate systems:

• the left side changes entries of a kernel coefficient table;
• the right side changes values at evaluation points.

An invertible monomial matrix, consisting of a coordinate permutation and nonzero coordinate scalings, preserves Hamming weight. The matrix $M_D$ need not be monomial, so invertibility alone supplies no such guarantee.

Therefore Theorem 7.3 establishes vector-space correspondence, not a coefficient-space proximity theorem.

7.6 Interaction with folding

Coefficient folding is defined for every table in kernel coordinates. An evaluation-side folding identity additionally requires a paired evaluation domain and the compatibility conditions described in Chapter 5.

When those conditions hold, the following operations describe the same folded polynomial:

1. fold the kernel coefficient table and then evaluate the folded polynomial;
2. evaluate the original polynomial and apply the compatible evaluation fold.

This commutation statement is algebraic and conditional on the domain structure. It does not establish that arbitrary evaluation errors correspond to sparse coefficient errors, nor does it provide a protocol-soundness bound.

7.7 What has been established

This chapter establishes:

• invertibility of evaluation on $N$ distinct field points;
• invertibility of the kernel-coefficient-to-evaluation map;
• exact correspondence between ${\mathsf{CH}}_{m,k}$ and $\mathrm{RS}(D,2^k)$;
• the Reed–Solomon minimum distance in evaluation coordinates; and
• the distinction between vector-space equivalence and Hamming-proximity equivalence.

No coefficient-space proximity transfer or protocol-soundness conclusion is asserted.