Algorizk Research Notes

Algorizk Research Notes is a curated technical publication from Algorizk Labs. It presents selected mathematical foundations, algorithms, implementation methods, and research directions related to efficient cryptographic proof systems.

These notes are intended for researchers, protocol designers, and implementation engineers. They complement Algorizk Labs’ formal papers and technical case studies without replacing peer-reviewed or archival publications.

Editorial approach

Material is selected from a broader private research programme and rewritten for public technical communication. The notes are not a reproduction of internal notebooks, preliminary calculations, or confidential project records.

Results are classified according to their maturity. Established statements, conditional constructions, computational observations, research directions, and open problems are identified explicitly where necessary.

Initial scope

The first collection will focus on:

Kernel polynomials and structured polynomial bases
Boolean folding and multilinear evaluation
Connections between Sumcheck-style reductions and FRI-style folding
Affine butterfly domains and conditional fast evaluation
Hardware-oriented proof-system implementation

Only material approved for disclosure will be included. Unpublished collaborative details, confidential information, and results awaiting appropriate scientific release will remain private.

Relationship to Algorizk Labs

For company capabilities, project inquiries, and concise technical case studies, visit Algorizk Labs.

Publication Status

Current status: Pre-release public working draft — July 2026. This edition is publicly accessible but has not been externally peer reviewed, formally released, or deposited as an archival publication.

Algorizk Research Notes distinguishes between different levels of research maturity. A result’s status should be read together with its assumptions, proof, experimental evidence, and cited sources.

Status labels

Established result

A mathematical or algorithmic statement supported by a complete argument in these notes or by an explicitly cited source. This label does not by itself mean that the material has undergone external peer review.

Conditional construction

A construction or complexity result that holds only when its stated hypotheses are satisfied. The hypotheses form part of the result and must not be omitted when it is described.

Computational observation

A result verified for particular parameters, finite fields, implementations, or experiments. Such evidence does not establish a general theorem.

Research direction

A structured approach under active investigation. It may combine established components with steps that remain incomplete.

Open problem

A question for which these notes do not claim a complete solution.

Scientific publication

These notes complement, but do not replace, journal articles, conference papers, or formally released preprints. When a corresponding paper is available, its definitions, theorem statements, authorship, and citation information should be treated as authoritative.

Until a stable version is formally released and deposited in an archival repository, references to this working draft should identify Algorizk Labs, its pre-release status and date, the page title, and the public page URL.

Collaborators and institutional relationships may remain unnamed until disclosure is appropriate under the relevant research and publication process.

Disclosure policy

Internal notebooks, confidential project material, client information, incomplete proofs, security-sensitive details, implementation-specific intellectual property, and results awaiting appropriate scientific release are excluded from the public edition.

Copyright

No licence to reproduce, redistribute, modify, or create derivative works is granted unless Algorizk Labs states otherwise for particular material.

Binary Exponents and Polynomial Coordinates

Status: Established

This chapter introduces the binary notation used throughout the book. It provides the coordinate system connecting Boolean vectors, integer exponents, and polynomials of degree less than a power of two.

1.1 Basic setting

Let $F$ be a field and let $m \geq 1$ . Define

$N = 2^{m}$

and

$B_{m} = {0, 1}^{m} .$

An element of $B_{m}$ is written

$a = (a_{0}, \dots, a_{m - 1}) .$

The coordinates are ordered from the least significant bit to the most significant bit. Thus $a_{0}$ has weight $1$ , $a_{1}$ has weight $2$ , and $a_{m - 1}$ has weight $2^{m - 1}$ .

1.2 Binary value of a Boolean vector

For every $a \in B_{m}$ , define

$∣ a ∣_{2} = i = 0 \sum m - 1 a_{i} 2^{i} .$

The map

$a ⟼ ∣ a ∣_{2}$

is a bijection from $B_{m}$ to

${0, \dots, 2^{m} - 1} .$

Consequently, every exponent $j$ satisfying $0 \leq j < N$ has a unique binary representation $j = ∣ a ∣_{2}$ for some $a \in B_{m}$ .

1.3 Boolean indexing of polynomial coefficients

Let

$F [X]_{< N} = {U (X) \in F [X] : de g U < N} .$

Every polynomial $U \in F [X]_{< N}$ has a unique monomial expansion

$U (X) = j = 0 \sum N - 1 u_{j} X^{j} .$

Using binary exponent coordinates, the same polynomial can be written as

$U (X) = a \in B_{m} \sum u_{a} X^{∣ a ∣_{2}},$

where $u_{a}$ denotes the coefficient of $X^{∣ a ∣_{2}}$ . This is a reindexing of the ordinary monomial basis, not a new polynomial representation.

1.4 Example with three bits

Let $m = 3$ . Then $N = 8$ , and the Boolean vectors correspond to exponents as follows:

Boolean vector $a$	Binary value $∣ a ∣_{2}$	Monomial
$(0, 0, 0)$	$0$	$1$
$(1, 0, 0)$	$1$	$X$
$(0, 1, 0)$	$2$	$X^{2}$
$(1, 1, 0)$	$3$	$X^{3}$
$(0, 0, 1)$	$4$	$X^{4}$
$(1, 0, 1)$	$5$	$X^{5}$
$(0, 1, 1)$	$6$	$X^{6}$
$(1, 1, 1)$	$7$	$X^{7}$

Therefore, a polynomial of degree less than $8$ can be written as

$U (X) = u_{(0, 0, 0)} + u_{(1, 0, 0)} X + u_{(0, 1, 0)} X^{2} + u_{(1, 1, 0)} X^{3} + u_{(0, 0, 1)} X^{4} + u_{(1, 0, 1)} X^{5} + u_{(0, 1, 1)} X^{6} + u_{(1, 1, 1)} X^{7} .$

1.5 Low and high coordinates

Fix an integer $k$ satisfying

$0 \leq k \leq m .$

Every $a \in B_{m}$ can be decomposed uniquely as

$a = (r, s),$

where

$r = (a_{0}, \dots, a_{k - 1}) \in B_{k}$

contains the low coordinates and

$s = (a_{k}, \dots, a_{m - 1}) \in B_{m - k}$

contains the high coordinates. The binary value satisfies

$∣ a ∣_{2} = ∣ r ∣_{2} + 2^{k} ∣ s ∣_{2} .$

1.6 Degree and high-coordinate support

Proposition 1.1 — Monomial low-degree condition

Let

$U (X) = (r, s) \in B_{k} \times B_{m - k} \sum u_{(r, s)} X^{∣ r ∣_{2} + 2^{k} ∣ s ∣_{2}} .$

Then

$de g U < 2^{k}$

if and only if

$u_{(r, s)} = 0$

for every $r \in B_{k}$ and every nonzero $s \in B_{m - k}$ .

Proof

Suppose first that $de g U < 2^{k}$ . If $s \neq = 0$ , then $∣ s ∣_{2} \geq 1$ and

$∣ r ∣_{2} + 2^{k} ∣ s ∣_{2} \geq 2^{k} .$

The corresponding monomial cannot occur in $U$ , so $u_{(r, s)} = 0$ .

Conversely, suppose that $u_{(r, s)} = 0$ whenever $s \neq = 0$ . Then

$U (X) = r \in B_{k} \sum u_{(r, 0)} X^{∣ r ∣_{2}} .$

For every $r \in B_{k}$ , we have $∣ r ∣_{2} \leq 2^{k} - 1$ . It follows that $de g U < 2^{k}$ .

This proves both directions.

1.7 Why this coordinate system matters

Binary exponent coordinates expose the recursive structure of $F [X]_{< 2^{m}}$ . They will allow us to:

define kernel polynomials indexed by Boolean vectors;
describe their coefficients through Boolean relations;
separate low-degree and high-degree components;
express polynomial folding coordinate by coordinate;
connect univariate polynomials with multilinear evaluation.

The next chapter introduces the kernel polynomials

$K_{y} (X) = i = 0 \prod m - 1 (X^{2^{i}} + y_{i}), y \in B_{m} .$

Kernel Polynomials

Status: Established

This chapter introduces the Boolean kernel polynomials and determines their monomial coefficients and support exactly.

2.1 Definition

Let $m \geq 1$ , let

$N = 2^{m},$

and let

$B_{m} = {0, 1}^{m} .$

For every Boolean vector

$y = (y_{0}, \dots, y_{m - 1}) \in B_{m},$

we define the associated kernel polynomial by

$K_{y} (X) = i = 0 \prod m - 1 (X^{2^{i}} + y_{i}) .$

The vector $y$ is called the kernel index.

2.2 Degree and leading coefficient

Every factor $X^{2^{i}} + y_{i}$ is monic and has degree $2^{i}$ . Consequently,

$de g K_{y} = i = 0 \sum m - 1 2^{i} = 2^{m} - 1 = N - 1.$

Therefore every kernel polynomial is monic of degree $N - 1$ .

Proposition 2.1 — Degree of a kernel polynomial

For every $y \in B_{m}$ ,

$de g K_{y} = N - 1,$

and the coefficient of $X^{N - 1}$ is $1$ .

Proof

The leading term of the product is obtained by selecting $X^{2^{i}}$ from every factor. Hence the leading monomial is

$i = 0 \prod m - 1 X^{2^{i}} = X^{\sum_{i = 0}^{m - 1} 2^{i}} = X^{N - 1} .$

Its coefficient is $1$ .

2.3 Boolean complement

For

$a = (a_{0}, \dots, a_{m - 1}) \in B_{m},$

define its Boolean complement by

$\overline{a} = (1 - a_{0}, \dots, 1 - a_{m - 1}) .$

For two Boolean vectors $a, y \in B_{m}$ , we write

$y \geq a$

when

$y_{i} \geq a_{i}$

for every $i$ .

2.4 Exact coefficient formula

Write

$K_{y} (X) = a \in B_{m} \sum [K_{y}]_{a} X^{∣ a ∣_{2}},$

where $[K_{y}]_{a}$ denotes the coefficient of $X^{∣ a ∣_{2}}$ .

Proposition 2.2 — Coefficient formula

For every $a, y \in B_{m}$ ,

$[K_{y}]_{a} = i : a_{i} = 0 \prod y_{i} .$

Because $y$ is Boolean, this is equivalent to

$[K_{y}]_{a} = {1, 0, if y \geq \overline{a}, otherwise .$

Proof

To obtain the monomial $X^{∣ a ∣_{2}}$ , we select $X^{2^{i}}$ from the $i$ -th factor when $a_{i} = 1$ , and select $y_{i}$ when $a_{i} = 0$ .

The resulting coefficient is therefore

$i : a_{i} = 0 \prod y_{i} .$

Since every $y_{i}$ belongs to ${0, 1}$ , this product equals $1$ exactly when

$y_{i} = 1$

for every coordinate satisfying $a_{i} = 0$ . This condition is precisely

$y \geq \overline{a} .$

2.5 Monomial support

Define the monomial support of $K_{y}$ by

$Supp (K_{y}) = {a \in B_{m} : [K_{y}]_{a} \neq = 0} .$

The coefficient formula gives

$Supp (K_{y}) = {a \in B_{m} : y \geq \overline{a}} .$

Equivalently, if $y_{i} = 0$ , then every exponent index in the support must satisfy $a_{i} = 1$ . If $y_{i} = 1$ , then $a_{i}$ is free.

Let

$wt (y) = i = 0 \sum m - 1 y_{i}$

denote the Hamming weight of $y$ .

Corollary 2.3 — Support size

For every $y \in B_{m}$ ,

$∣ Supp (K_{y}) ∣ = 2^{wt (y)} .$

Proof

Each coordinate with $y_{i} = 0$ forces $a_{i} = 1$ . Each coordinate with $y_{i} = 1$ leaves $a_{i}$ free. There are $wt (y)$ free coordinates, giving

$2^{wt (y)}$

possible exponent indices.

2.6 Two extremal kernels

Let

$0_{m} = (0, \dots, 0)$

and

$1_{m} = (1, \dots, 1) .$

For the all-zero index,

$K_{0_{m}} (X) = i = 0 \prod m - 1 X^{2^{i}} = X^{N - 1} .$

For the all-one index,

$K_{1_{m}} (X) = i = 0 \prod m - 1 (X^{2^{i}} + 1) .$

Using the binary factorization of the geometric sum,

$K_{1_{m}} (X) = 1 + X + \dots + X^{N - 1} .$

Equivalently,

$(X - 1) K_{1_{m}} (X) = X^{N} - 1.$

2.7 Examples for $m = 1$

When $m = 1$ , the two kernels are

$K_{(0)} (X) = X$

and

$K_{(1)} (X) = X + 1.$

2.8 Examples for $m = 2$

When $m = 2$ , we have

$K_{(0, 0)} (X) = X^{3},$

$K_{(1, 0)} (X) = X^{3} + X^{2},$

$K_{(0, 1)} (X) = X^{3} + X,$

and

$K_{(1, 1)} (X) = X^{3} + X^{2} + X + 1.$

2.9 Examples for $m = 3$

When $m = 3$ , the eight kernel polynomials are

$K_{(0, 0, 0)} (X) = X^{7},$

$K_{(1, 0, 0)} (X) = X^{7} + X^{6},$

$K_{(0, 1, 0)} (X) = X^{7} + X^{5},$

$K_{(1, 1, 0)} (X) = X^{7} + X^{6} + X^{5} + X^{4},$

$K_{(0, 0, 1)} (X) = X^{7} + X^{3},$

$K_{(1, 0, 1)} (X) = X^{7} + X^{6} + X^{3} + X^{2},$

$K_{(0, 1, 1)} (X) = X^{7} + X^{5} + X^{3} + X,$

and

$K_{(1, 1, 1)} (X) = X^{7} + X^{6} + X^{5} + X^{4} + X^{3} + X^{2} + X + 1.$

These examples illustrate the exact support formula:

$[K_{y}]_{a} = 1 ⟺ y \geq \overline{a} .$

2.10 What comes next

The family

${K_{y} (X) : y \in B_{m}}$

contains exactly $N = 2^{m}$ polynomials in the $N$ -dimensional space

$F [X]_{< N} .$

The next chapter proves that these polynomials are linearly independent and therefore form a basis of $F [X]_{< N}$ .

The Boolean Kernel Basis

Status: Established

This chapter proves that the $2^{m}$ Boolean kernel polynomials form a basis of

$F [X]_{< 2^{m}} .$

It also gives the exact transformation between monomial coefficients and kernel coefficients.

3.1 The kernel family

Let

$N = 2^{m}$

and

$B_{m} = {0, 1}^{m} .$

For every $y \in B_{m}$ , recall that

$K_{y} (X) = i = 0 \prod m - 1 (X^{2^{i}} + y_{i}) .$

There are exactly

$∣ B_{m} ∣ = 2^{m} = N$

kernel polynomials.

The polynomial space

$F [X]_{< N}$

also has dimension $N$ . Therefore, it is enough to prove that the kernel polynomials are linearly independent.

3.2 Recursive decomposition

Write a Boolean vector as

$y = (b, z),$

where

$b = y_{0} \in {0, 1}$

and

$z = (y_{1}, \dots, y_{m - 1}) \in B_{m - 1} .$

Define the smaller kernel polynomial

$K_{z} (Y) = i = 0 \prod m - 2 (Y^{2^{i}} + z_{i}) .$

Substituting $Y = X^{2}$ , we obtain

$K_{(0, z)} (X) = X K_{z} (X^{2})$

and

$K_{(1, z)} (X) = (X + 1) K_{z} (X^{2}) .$

Therefore,

$K_{(1, z)} (X) = K_{z} (X^{2}) + X K_{z} (X^{2}) .$

This separates every kernel into an even part and an odd part.

3.3 Linear independence

Theorem 3.1 — Boolean kernel basis

The family

${K_{y} (X) : y \in B_{m}}$

is a basis of

$F [X]_{< 2^{m}} .$

Proof

We proceed by induction on $m$ .

For $m = 1$ , the kernel family is

$K_{(0)} (X) = X$

and

$K_{(1)} (X) = X + 1.$

These two polynomials are linearly independent and therefore form a basis of

$F [X]_{< 2} .$

Now suppose the result holds for $m - 1$ . Consider a linear relation

$z \in B_{m - 1} \sum α_{0, z} K_{(0, z)} (X) + z \in B_{m - 1} \sum α_{1, z} K_{(1, z)} (X) = 0.$

Using the recursive identities, this becomes

$z \sum α_{1, z} K_{z} (X^{2}) + X z \sum (α_{0, z} + α_{1, z}) K_{z} (X^{2}) = 0.$

The first sum contains only even powers of $X$ , while the second contains only odd powers. The even and odd parts must therefore vanish separately:

$z \sum α_{1, z} K_{z} (X^{2}) = 0$

and

$z \sum (α_{0, z} + α_{1, z}) K_{z} (X^{2}) = 0.$

By the induction hypothesis, the polynomials $K_{z}$ are linearly independent. Hence

$α_{1, z} = 0$

for every $z$ , and

$α_{0, z} + α_{1, z} = 0.$

It follows that

$α_{0, z} = 0$

for every $z$ .

Thus the kernel family is linearly independent. Since it contains $2^{m}$ elements in a vector space of dimension $2^{m}$ , it is a basis.

3.4 Unique kernel expansion

The basis theorem implies that every polynomial

$U (X) \in F [X]_{< N}$

has a unique representation

$U (X) = y \in B_{m} \sum λ_{y} K_{y} (X) .$

The function

$λ : B_{m} ⟶ F$

is called the Boolean kernel coefficient table of $U$ .

The entries $λ_{y}$ are coordinates in a basis. They are not evaluations of $U$ .

3.5 From kernel coefficients to monomial coefficients

Write

$U (X) = a \in B_{m} \sum u_{a} X^{∣ a ∣_{2}}$

and

$U (X) = y \in B_{m} \sum λ_{y} K_{y} (X) .$

From the coefficient formula of Chapter 2,

$[K_{y}]_{a} = {1, 0, y \geq \overline{a}, otherwise .$

Therefore,

$u_{a} = y \geq \overline{a} \sum λ_{y} .$

This is the Boolean zeta transform, followed by the complement permutation.

3.6 Zeta-matrix representation

Define the coefficient matrix $Z_{m}$ by

$Z_{m} (a, y) = [K_{y}]_{a} .$

Then

$Z_{m} (a, y) = 1 [y \geq \overline{a}],$

where $1 [P]$ equals $1$ when $P$ is true and $0$ otherwise.

If $u$ and $λ$ are written as column vectors, then

$u = Z_{m} λ .$

For one coordinate,

$Z_{1} = (0111) .$

With the compatible Boolean ordering, the full matrix has a Kronecker structure obtained from $Z_{1}$ , up to the ordering of the Boolean indices.

Since

$det Z_{1} = - 1,$

the one-coordinate matrix is invertible over every field. Its Kronecker powers are also invertible.

This gives a second proof of the Boolean kernel basis theorem.

3.7 Möbius inversion

Define

$g (b) = u_{\overline{b}} .$

The coefficient relation becomes

$g (b) = y \geq b \sum λ_{y} .$

Boolean Möbius inversion gives

$λ_{y} = b \geq y \sum (- 1)^{wt (b) - wt (y)} g (b) .$

Equivalently,

$λ_{y} = b \geq y \sum (- 1)^{wt (b) - wt (y)} u_{\overline{b}} .$

These formulas remain valid in characteristic $2$ , where subtraction and addition coincide.

3.8 Exact transformation cost

The Boolean zeta transform can be computed coordinate by coordinate.

For each of the $m$ coordinates, there are

$2^{m - 1} = \frac{N}{2}$

pair updates. Therefore, conversion from kernel coefficients to monomial coefficients uses exactly

$\frac{m N}{2}$

field additions, apart from index permutations.

The inverse Möbius transform uses exactly

$\frac{m N}{2}$

field subtractions, apart from index permutations.

Thus both transformations have complexity

$O (N lo g N),$

with exact arithmetic count

$\frac{N lo g _{2} N}{2} .$

Chapter 9 shows that the affine kernel basis has the same Boolean coefficient transform. The same butterfly network and arithmetic count therefore apply in affine monomial coordinates.

3.9 Summary

We have established the linear isomorphism

$F^{B_{m}} ⟶ F [X]_{< 2^{m}},$

defined by

$λ ⟼ y \in B_{m} \sum λ_{y} K_{y} (X) .$

The monomial and kernel coefficient tables are related by an invertible Boolean zeta transform.

The next chapter studies how an ordinary polynomial degree bound appears in the Boolean kernel coefficient table.

Low-Degree Filtration

Status: Established

This chapter characterizes ordinary polynomial degree directly in the Boolean kernel coefficient table.

The central result is that a degree bound does not correspond to sparse kernel coefficients. Instead, it imposes an alternating character structure on the high coordinates.

4.1 Setting

Let

$N = 2^{m},$

and write a polynomial $U \in F [X]_{< N}$ in the Boolean kernel basis:

$U (X) = y \in B_{m} \sum λ_{y} K_{y} (X) .$

Fix an integer $k$ satisfying

$0 \leq k \leq m .$

Set

$q = m - k .$

We split every kernel index as

$y = (x, h),$

where

$x = (y_{0}, \dots, y_{k - 1}) \in B_{k}$

contains the low coordinates, and

$h = (y_{k}, \dots, y_{m - 1}) \in B_{q}$

contains the high coordinates.

The kernel coefficient table is therefore written as

$λ_{(x, h)} .$

4.2 The high-coordinate sign character

For $h \in B_{q}$ , define

$σ_{q} (h) = (- 1)^{q - wt (h)} .$

Equivalently,

$σ_{q} (h) = j = 0 \prod q - 1 (- 1)^{1 - h_{j}} .$

The value changes sign whenever one high coordinate is flipped.

Up to the constant factor $(- 1)^{q}$ , this is the Boolean character

$h ⟼ (- 1)^{wt (h)} .$

4.3 Main theorem

Theorem 4.1 — Low-degree filtration

Let

$U (X) = (x, h) \in B_{k} \times B_{q} \sum λ_{(x, h)} K_{(x, h)} (X) .$

Then

$de g U < 2^{k}$

if and only if there exists a unique function

$μ : B_{k} ⟶ F$

such that

$λ_{(x, h)} = (- 1)^{q - wt (h)} μ_{x}$

for every $x \in B_{k}$ and every $h \in B_{q}$ .

The free coefficient is

$μ_{x} = λ_{(x, 1_{q})},$

where

$1_{q} = (1, \dots, 1) .$

4.4 Proof: degree implies the character condition

Write the monomial expansion of $U$ as

$U (X) = (r, t) \in B_{k} \times B_{q} \sum u_{(r, t)} X^{∣ r ∣_{2} + 2^{k} ∣ t ∣_{2}} .$

By Chapter 1,

$de g U < 2^{k}$

if and only if

$u_{(r, t)} = 0$

for every $r \in B_{k}$ and every nonzero $t \in B_{q}$ .

By the coefficient formula from Chapter 3,

$u_{(r, t)} = x \geq \overline{r} \sum h \geq \overline{t} \sum λ_{(x, h)} .$

Fix a nonzero $t$ . Since the Boolean zeta transform over the low coordinates is invertible, the identities

$u_{(r, t)} = 0 for every r \in B_{k}$

imply

$h \geq \overline{t} \sum λ_{(x, h)} = 0$

for every $x \in B_{k}$ .

Because $t \neq = 0_{q}$ , its complement satisfies

$\overline{t} \neq = 1_{q} .$

For fixed $x$ , define

$G_{x} (b) = h \geq b \sum λ_{(x, h)} .$

We have shown that

$G_{x} (b) = 0$

for every $b \neq = 1_{q}$ .

At the all-one vector,

$G_{x} (1_{q}) = λ_{(x, 1_{q})} .$

Define

$μ_{x} = λ_{(x, 1_{q})} .$

Boolean Möbius inversion gives

$λ_{(x, h)} = b \geq h \sum (- 1)^{wt (b) - wt (h)} G_{x} (b) .$

Only $b = 1_{q}$ can contribute. Therefore,

$λ_{(x, h)} = (- 1)^{q - wt (h)} μ_{x} .$

This proves the first direction.

4.5 Proof: the character condition implies low degree

Assume that

$λ_{(x, h)} = (- 1)^{q - wt (h)} μ_{x} .$

Let $t \in B_{q}$ be nonzero and set

$b = \overline{t} .$

Since $t \neq = 0_{q}$ , we have

$b \neq = 1_{q} .$

For every $x \in B_{k}$ ,

$h \geq b \sum λ_{(x, h)} = μ_{x} h \geq b \sum (- 1)^{q - wt (h)} .$

There is at least one free coordinate in the sum because $b \neq = 1_{q}$ . The alternating Boolean sum therefore vanishes:

$h \geq b \sum (- 1)^{q - wt (h)} = 0.$

Consequently,

$h \geq \overline{t} \sum λ_{(x, h)} = 0.$

It follows that

$u_{(r, t)} = 0$

for every $r \in B_{k}$ and every nonzero $t \in B_{q}$ .

By the monomial low-degree condition,

$de g U < 2^{k} .$

This proves the converse direction.

4.6 Collapse of the high coordinates

For $x \in B_{k}$ , define the truncated kernel

$K_{x}^{[k]} (X) = i = 0 \prod k - 1 (X^{2^{i}} + x_{i}) .$

The character condition gives

$U (X) = x \in B_{k} \sum μ_{x} h \in B_{q} \sum (- 1)^{q - wt (h)} K_{(x, h)} (X) .$

The high-coordinate sum factors coordinate by coordinate. For every $i \geq k$ ,

$(X^{2^{i}} + 1) - X^{2^{i}} = 1.$

Therefore,

$h \in B_{q} \sum (- 1)^{q - wt (h)} K_{(x, h)} (X) = K_{x}^{[k]} (X) .$

Hence every polynomial satisfying $de g U < 2^{k}$ has the reduced expression

$U (X) = x \in B_{k} \sum μ_{x} K_{x}^{[k]} (X) .$

This formula makes the collapse of the high coordinates explicit.

4.7 The character-side low-degree space

Define

$CH_{m, k} = {λ \in F^{B_{m}} : λ_{(x, h)} = (- 1)^{q - wt (h)} μ_{x} for some μ : B_{k} \to F} .$

The low-degree theorem gives the exact correspondence

$de g U < 2^{k} ⟺ λ \in CH_{m, k} .$

The table $μ$ has $2^{k}$ independent entries. Therefore,

$dim CH_{m, k} = 2^{k} .$

This agrees with

$dim F [X]_{< 2^{k}} = 2^{k} .$

4.8 Example: $m = 3$ and $k = 1$

Here,

$q = m - k = 2.$

For each $x \in B_{1}$ , the four coefficients in the high-coordinate fiber are

High index $h$	Character value $σ_{2} (h)$	Kernel coefficient
$(0, 0)$	$1$	$μ_{x}$
$(1, 0)$	$- 1$	$- μ_{x}$
$(0, 1)$	$- 1$	$- μ_{x}$
$(1, 1)$	$1$	$μ_{x}$

Thus the full kernel coefficient table has the form

$λ_{(x, 0, 0)} = μ_{x}, λ_{(x, 1, 0)} = - μ_{x}, λ_{(x, 0, 1)} = - μ_{x}, λ_{(x, 1, 1)} = μ_{x} .$

The polynomial collapses to

$U (X) = μ_{0} K_{(0)}^{[1]} (X) + μ_{1} K_{(1)}^{[1]} (X) .$

Since

$K_{(0)}^{[1]} (X) = X$

and

$K_{(1)}^{[1]} (X) = X + 1,$

we obtain

$U (X) = μ_{0} X + μ_{1} (X + 1) .$

This polynomial has degree less than $2$ , as required.

4.9 Boundary cases

When $k = m$ , we have $q = 0$ . There are no high coordinates, and the character condition imposes no restriction. This agrees with the fact that every polynomial in $F [X]_{< 2^{m}}$ has degree less than $2^{m}$ .

When $k = 0$ , the table $μ$ contains one scalar. The kernel coefficients must follow the complete alternating character

$λ_{h} = (- 1)^{m - wt (h)} μ .$

The corresponding polynomial is constant.

4.10 Summary

The Boolean kernel basis converts an ordinary degree condition into an exact character condition:

$de g U < 2^{k} ⟺ λ_{(x, h)} = (- 1)^{m - k - wt (h)} μ_{x} .$

The next chapter studies how even–odd polynomial folding acts directly on the kernel coefficient table.

Even–Odd Folding

Status: Established algebraic identity
Evaluation form: Conditional on a negation-paired domain and $char F \neq = 2$

This chapter studies one round of polynomial folding in three different representations:

the polynomial representation;
the Boolean kernel coefficient table;
evaluations on a paired domain.

These layers must be kept distinct.

5.1 Even–odd decomposition

Let

$U (X) = j = 0 \sum N - 1 u_{j} X^{j} \in F [X]_{< N} .$

There exist unique polynomials $A$ and $B$ such that

$U (X) = A (X^{2}) + XB (X^{2}) .$

The polynomial $A$ contains the even coefficients of $U$ :

$A (Y) = j \geq 0 \sum u_{2 j} Y^{j} .$

The polynomial $B$ contains the odd coefficients:

$B (Y) = j \geq 0 \sum u_{2 j + 1} Y^{j} .$

Both satisfy

$de g A < \frac{N}{2}, de g B < \frac{N}{2} .$

5.2 One-round polynomial fold

Let $ρ \in F$ be a folding challenge.

Definition 5.1 — Polynomial fold

For

$U (X) = A (X^{2}) + XB (X^{2}),$

define

$Fold_{ρ} (U) (Y) = A (Y) + ρB (Y) .$

The folded polynomial belongs to

$F [Y]_{< N /2} .$

The challenge replaces the active variable $X$ by the field element $ρ$ after the even–odd decomposition.

5.3 Kernel decomposition

Write the kernel index as

$y = (b, z),$

where

$b = y_{0} \in {0, 1}$

and

$z = (y_{1}, \dots, y_{m - 1}) \in B_{m - 1} .$

The kernel identities from Chapter 3 are

$K_{(0, z)} (X) = X K_{z} (X^{2})$

and

$K_{(1, z)} (X) = (X + 1) K_{z} (X^{2}) .$

The second identity can be written as

$K_{(1, z)} (X) = K_{z} (X^{2}) + X K_{z} (X^{2}) .$

Now let

$U (X) = z \in B_{m - 1} \sum λ_{(0, z)} K_{(0, z)} (X) + z \in B_{m - 1} \sum λ_{(1, z)} K_{(1, z)} (X) .$

Substituting the kernel identities gives

$U (X) = z \sum λ_{(1, z)} K_{z} (X^{2}) + X z \sum (λ_{(0, z)} + λ_{(1, z)}) K_{z} (X^{2}) .$

Therefore, the even and odd polynomials are

$A (Y) = z \sum λ_{(1, z)} K_{z} (Y)$

and

$B (Y) = z \sum (λ_{(0, z)} + λ_{(1, z)}) K_{z} (Y) .$

5.4 Folding the kernel coefficient table

The folded polynomial is

$Fold_{ρ} (U) (Y) = A (Y) + ρB (Y) .$

Its kernel coefficient at $z$ is therefore

$λ_{z}^{'} = λ_{(1, z)} + ρ (λ_{(0, z)} + λ_{(1, z)}) .$

Equivalently,

$λ_{z}^{'} = ρ λ_{(0, z)} + (1 + ρ) λ_{(1, z)} .$

Definition 5.2 — Coefficient-table fold

Define

$F_{ρ} : F^{B_{m}} ⟶ F^{B_{m - 1}}$

$F_{ρ} (λ)_{z} = ρ λ_{(0, z)} + (1 + ρ) λ_{(1, z)} .$

The polynomial and coefficient-table folds agree:

$Fold_{ρ} (y \sum λ_{y} K_{y}) = z \sum F_{ρ} (λ)_{z} K_{z} .$

5.5 Exact arithmetic cost

For each $z \in B_{m - 1}$ , compute

$s_{z} = λ_{(0, z)} + λ_{(1, z)}$

and then

$F_{ρ} (λ)_{z} = λ_{(1, z)} + ρ s_{z} .$

Each output uses:

one field multiplication;
two field additions.

There are

$2^{m - 1} = \frac{N}{2}$

outputs. Therefore, one complete coefficient fold uses exactly

$\frac{N}{2} field multiplications + N field additions .$

The memory requirement is one input table of length $N$ and one output table of length $N /2$ . An in-place implementation may overwrite one half of the input table.

5.6 Preservation of the low-degree character condition

Assume first that

$1 \leq k \leq m .$

Write the kernel index as

$y = (b, x^{'}, h),$

where

$b \in B_{1}, x^{'} \in B_{k - 1}, h \in B_{m - k} .$

Suppose

$λ \in CH_{m, k} .$

Then there exists $μ : B_{k} \to F$ such that

$λ_{(b, x^{'}, h)} = (- 1)^{m - k - wt (h)} μ_{(b, x^{'})} .$

Applying the fold gives

$F_{ρ} (λ)_{(x^{'}, h)} = (- 1)^{m - k - wt (h)} (ρ μ_{(0, x^{'})} + (1 + ρ) μ_{(1, x^{'})}) .$

Define

$μ_{x^{'}}^{'} = ρ μ_{(0, x^{'})} + (1 + ρ) μ_{(1, x^{'})} .$

Since

$(m - 1) - (k - 1) = m - k,$

we obtain

$F_{ρ} (λ)_{(x^{'}, h)} = (- 1)^{(m - 1) - (k - 1) - wt (h)} μ_{x^{'}}^{'} .$

Therefore,

$F_{ρ} (CH_{m, k}) \subseteq CH_{m - 1, k - 1} .$

5.7 The boundary case $k = 0$

When $k = 0$ , the entire coefficient table is determined by one scalar $μ$ :

$λ_{h} = (- 1)^{m - wt (h)} μ .$

Write $h = (b, h^{'})$ . Then

$λ_{(0, h^{'})} = - (- 1)^{m - 1 - wt (h^{'})} μ$

and

$λ_{(1, h^{'})} = (- 1)^{m - 1 - wt (h^{'})} μ .$

Consequently,

$F_{ρ} (λ)_{h^{'}} = (- 1)^{m - 1 - wt (h^{'})} μ .$

Thus

$F_{ρ} (CH_{m, 0}) \subseteq CH_{m - 1, 0} .$

In this boundary case, the folded table is independent of $ρ$ .

5.8 Degree reduction

By the low-degree filtration theorem,

$λ \in CH_{m, k} ⟺ de g U < 2^{k} .$

For $k \geq 1$ , preservation of the character condition gives

$F_{ρ} (λ) \in CH_{m - 1, k - 1} .$

Therefore,

$de g U < 2^{k} ⟹ de g Fold_{ρ} (U) < 2^{k - 1} .$

This is the algebraic degree-halving property used in FRI-style folding.

5.9 Evaluation on a paired domain

We now introduce an evaluation layer. This requires additional assumptions.

Let $D \subseteq F^{\times}$ satisfy

$α \in D ⟹ - α \in D .$

Assume

$char F \neq = 2.$

Define the squared domain

$D^{'} = {α^{2} : α \in D} .$

Assume every $β \in D^{'}$ has exactly two preimages $α, - α$ in $D$ .

Let

$w (α) = U (α)$

be the evaluation word of $U$ on $D$ .

From

$U (X) = A (X^{2}) + XB (X^{2}),$

we obtain

$w (α) = A (β) + α B (β)$

and

$w (- α) = A (β) - α B (β),$

where

$β = α^{2} .$

Adding and subtracting gives

$A (β) = \frac{w ( α ) + w ( - α )}{2}$

and

$B (β) = \frac{w ( α ) - w ( - α )}{2 α} .$

5.10 Evaluation-word fold

Definition 5.3 — Evaluation fold

For $β = α^{2}$ , define

$fold_{ρ}^{D} (w) (β) = \frac{w ( α ) + w ( - α )}{2} + ρ \frac{w ( α ) - w ( - α )}{2 α} .$

This value is independent of the choice between $α$ and $- α$ , provided the same orientation is used in the odd term.

Substituting the expressions for $A (β)$ and $B (β)$ gives

$fold_{ρ}^{D} (w) (β) = A (β) + ρB (β) .$

Therefore,

$fold_{ρ}^{D} (w) (β) = Fold_{ρ} (U) (β) .$

This proves that polynomial folding and evaluation-word folding commute.

5.11 Three-layer diagram

The one-round folding operation can now be summarized as follows:

$λ F_{ρ} F_{ρ} (λ)$

on the coefficient side,

$U Fold_{ρ} Fold_{ρ} (U)$

on the polynomial side, and

$w fold_{ρ}^{D} fold_{ρ}^{D} (w)$

on the evaluation side.

When all assumptions are satisfied, the three objects represent the same folded polynomial.

This is an algebraic commutation statement. It does not, by itself, prove a proximity gap or protocol soundness.

5.12 Summary

One fold removes the first Boolean coordinate and transforms each coefficient pair by

$(λ_{(0, z)}, λ_{(1, z)}) ⟼ ρ λ_{(0, z)} + (1 + ρ) λ_{(1, z)} .$

The fold:

agrees with the even–odd polynomial decomposition;
preserves the low-degree character condition;
halves the degree bound when $k \geq 1$ ;
commutes with evaluation on a suitable paired domain;
costs exactly $N /2$ multiplications and $N$ additions.

The next chapter studies repeated folding and its connection with multilinear evaluation.

Repeated Folding and Multilinear Evaluation

Status: Established algebraic identity

Chapter 5 studied one even–odd fold. This chapter iterates that operation, derives its closed form, and identifies the final scalar with a multilinear evaluation of a signed coefficient table.

The results here are algebraic. They do not, by themselves, establish an interactive proof, a proximity guarantee, or a soundness bound.

6.1 Indexed coefficient tables

Let $m \geq 1$ , let $N = 2^{m}$ , and let $F$ be a field. Begin with a coefficient table

$λ_{0} : B_{m} ⟶ F .$

We fold the coordinates in the fixed order

$y_{0}, y_{1}, \dots, y_{m - 1} .$

For each round $r \in {0, \dots, m - 1}$ , choose a challenge $ρ_{r} \in F$ . If

$λ_{r} : B_{m - r} ⟶ F,$

define

$λ_{r + 1} (z) = ρ_{r} λ_{r} (0, z) + (1 + ρ_{r}) λ_{r} (1, z)$

for every $z \in B_{m - r - 1}$ .

The pair $(0, z), (1, z)$ differs only in the first coordinate remaining at round $r$ . Thus one round removes one Boolean coordinate and halves the table length.

For implementation, the same update can be written as

$λ_{r + 1} (z) = λ_{r} (1, z) + ρ_{r} (λ_{r} (0, z) + λ_{r} (1, z)) .$

This form uses one multiplication and two additions per output entry.

6.2 Closed formula after several rounds

For $b = (b_{0}, \dots, b_{r - 1}) \in B_{r}$ , define the folding weight

$w_{r} (b) = i = 0 \prod r - 1 {ρ_{i}, 1 + ρ_{i}, b_{i} = 0, b_{i} = 1.$

The empty product is $1$ .

Proposition 6.1 — Partial repeated-fold formula

For every $r \in {0, \dots, m}$ and every $z \in B_{m - r}$ ,

$λ_{r} (z) = b \in B_{r} \sum λ_{0} (b, z) w_{r} (b) .$

Proof

When $r = 0$ , the statement is the identity $λ_{0} (z) = λ_{0} (z)$ .

Assume the formula holds at round $r$ . Then

$λ_{r + 1} (z) = ρ_{r} λ_{r} (0, z) + (1 + ρ_{r}) λ_{r} (1, z) .$

Applying the induction hypothesis to the two tables on the right gives

$λ_{r + 1} (z) = ρ_{r} b \in B_{r} \sum λ_{0} (b, 0, z) w_{r} (b) + (1 + ρ_{r}) b \in B_{r} \sum λ_{0} (b, 1, z) w_{r} (b) .$

The first sum contains all indices whose next bit is $0$ , and the second contains all indices whose next bit is $1$ . Their additional factors are exactly the two possible factors in $w_{r + 1}$ . Hence

$λ_{r + 1} (z) = c \in B_{r + 1} \sum λ_{0} (c, z) w_{r + 1} (c) .$

This completes the induction. $□$

At $r = m$ , no Boolean coordinate remains, so the table has become the scalar

$λ_{m} = y \in B_{m} \sum λ_{0} (y) i = 0 \prod m - 1 ρ_{i}^{1 - y_{i}} (1 + ρ_{i})^{y_{i}} .$

This expression is multilinear in the challenges $ρ_{0}, \dots, ρ_{m - 1}$ .

6.3 Example with two coordinates

Let $m = 2$ . The first round gives

$λ_{1} (y_{1}) = ρ_{0} λ_{0} (0, y_{1}) + (1 + ρ_{0}) λ_{0} (1, y_{1}) .$

The second round gives

$λ_{2} = ρ_{0} ρ_{1} λ_{0} (0, 0) + (1 + ρ_{0}) ρ_{1} λ_{0} (1, 0) + ρ_{0} (1 + ρ_{1}) λ_{0} (0, 1) + (1 + ρ_{0}) (1 + ρ_{1}) λ_{0} (1, 1) .$

Each original entry receives one factor from each folding round.

6.4 Dictionary with the standard multilinear extension

For a table $f : B_{m} \to F$ , its standard multilinear extension is

$MLE_{f} (t_{0}, \dots, t_{m - 1}) = y \in B_{m} \sum f (y) i = 0 \prod m - 1 (1 - t_{i})^{1 - y_{i}} t_{i}^{y_{i}} .$

A direct substitution $t_{i} = 1 + ρ_{i}$ introduces a minus sign whenever $y_{i} = 0$ , because

$1 - (1 + ρ_{i}) = - ρ_{i} .$

Therefore the final folded scalar is not, in general, the standard multilinear extension of the unchanged table $λ_{0}$ .

Define the signed table

$λ_{0} (y) = (- 1)^{m - wt (y)} λ_{0} (y),$

where $wt (y)$ is the Hamming weight of $y$ . Also define the transformed challenges

$η_{i} = 1 + ρ_{i} .$

Theorem 6.2 — Repeated folding as multilinear evaluation

The scalar obtained after all $m$ folding rounds satisfies

$λ_{m} = MLE_{λ_{0}} (η_{0}, \dots, η_{m - 1}) .$

Proof

For a fixed $y \in B_{m}$ , the corresponding multilinear basis weight at $η_{i} = 1 + ρ_{i}$ is

$i = 0 \prod m - 1 (1 - η_{i})^{1 - y_{i}} η_{i}^{y_{i}} = (- 1)^{m - wt (y)} i = 0 \prod m - 1 ρ_{i}^{1 - y_{i}} (1 + ρ_{i})^{y_{i}} .$

Multiplying this by $λ_{0} (y) = (- 1)^{m - wt (y)} λ_{0} (y)$ cancels the sign. Summing over $y$ gives the closed repeated-fold formula. $□$

The notation $η_{i}$ is reserved here for transformed folding challenges. Later affine chapters will use a different symbol for a quadratic nonresidue, preventing a notation collision.

6.5 Exact arithmetic cost

At round $r$ , the input table has $N / 2^{r}$ entries and the output table has $N / 2^{r + 1}$ entries. Using

$b + ρ_{r} (a + b),$

each output entry requires one multiplication and two additions. Therefore round $r$ uses

$\frac{N}{2 ^{r + 1}}$

multiplications and

$\frac{N}{2 ^{r}}$

additions.

Proposition 6.3 — Cost of all folding rounds

Folding a table of length $N = 2^{m}$ to one scalar uses exactly

$r = 0 \sum m - 1 \frac{N}{2 ^{r + 1}} = N - 1$

multiplications and

$r = 0 \sum m - 1 \frac{N}{2 ^{r}} = 2 N - 2$

additions.

More generally, the first $s$ rounds use

$N (1 - 2^{- s})$

multiplications and

$2 N (1 - 2^{- s})$

additions.

These counts exclude challenge generation, memory movement, hashing, commitments, and any evaluation-domain operations.

6.6 Interaction with the low-degree character space

Let $0 \leq k \leq m$ , let $q = m - k$ , and suppose $λ_{0} \in CH_{m, k}$ . By Chapter 4, there is a table $μ : B_{k} \to F$ such that

$λ_{0} (x, h) = (- 1)^{q - wt (h)} μ_{x} .$

Assume that the first $k$ folding rounds remove the low coordinates $x$ . Repeated application of the one-round preservation theorem from Chapter 5 shows that after those rounds the remaining table has the form

$λ_{k} (h) = (- 1)^{q - wt (h)} μ_{*},$

where $μ_{*}$ is the result of applying the first $k$ folds to the table $μ$ .

Every subsequent high-coordinate fold removes one alternating-sign pair:

$ρ (- c) + (1 + ρ) c = c .$

Consequently,

$λ_{m} = μ_{*},$

and the final scalar is independent of the last $q$ challenges. This is an exact consequence of membership in $CH_{m, k}$ .

6.7 Evaluation-layer interpretation

Suppose a sequence of evaluation domains is paired so that each round admits the evaluation-fold identity from Chapter 5. Then the coefficient tables and the evaluation tables can be folded in parallel, and both describe the same successive polynomials.

This statement is conditional on the required domain pairing and on the chosen polynomial decomposition. It is not a soundness theorem. Turning the algebraic identities into a proof protocol additionally requires commitment, query, consistency, and probability analyses.

6.8 What has been established

This chapter establishes:

the exact table recurrence for repeated folding;
the closed formula after any number of rounds;
the signed-table dictionary with a standard multilinear extension;
exact arithmetic counts for partial and complete folding; and
the behavior of repeated folding on the low-degree character space.

No proximity or protocol-soundness conclusion is asserted.

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 \geq 1$ and let

$N = 2^{m} .$

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

$D = (α_{0}, \dots, α_{N - 1}) \in F^{N} .$

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

$F [X]_{< d} = {f \in F [X] : de g f < d} .$

Define the evaluation map

$Ev_{D} : F [X]_{< N} ⟶ F^{N}$

$Ev_{D} (f) = (f (α_{0}), \dots, f (α_{N - 1})) .$

Proposition 7.1 — Evaluation is an isomorphism

The map $Ev_{D}$ is a linear isomorphism.

Proof

Linearity is immediate. Suppose $f \in F [X]_{< N}$ satisfies $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 $Ev_{D}$ is injective. Its domain and codomain both have dimension $N$ , so it is an isomorphism. $□$

Equivalently, the Vandermonde matrix

$V_{D} = (α_{j}^{e})_{0 \leq j, e < N}$

is invertible.

7.2 Evaluation from kernel coordinates

Recall the Boolean kernel polynomials

$K_{y} (X) = i = 0 \prod m - 1 (X^{2^{i}} + y_{i}), y \in B_{m} .$

By Chapter 3, the family

${K_{y} : y \in B_{m}}$

is a basis of $F [X]_{< N}$ . Therefore every coefficient table $λ : B_{m} \to F$ determines a unique polynomial

$U_{λ} (X) = y \in B_{m} \sum λ_{y} K_{y} (X) .$

Define the kernel-evaluation map

$Φ_{D} : F^{B_{m}} ⟶ F^{N}$

$Φ_{D} (λ) = Ev_{D} (U_{λ}) .$

Proposition 7.2 — Kernel evaluation is an isomorphism

The map $Φ_{D}$ is a linear isomorphism.

Proof

The kernel-synthesis map

$λ ⟼ U_{λ}$

is an isomorphism because the kernel polynomials form a basis. Proposition 7.1 shows that $Ev_{D}$ is also an isomorphism. Their composition $Φ_{D}$ is therefore an isomorphism. $□$

In matrix form,

$Φ_{D} (λ) = M_{D} λ,$

where, after fixing the Boolean ordering of Chapter 1,

$(M_{D})_{j, y} = K_{y} (α_{j}) .$

The matrix $M_{D}$ is invertible.

7.3 Reed–Solomon evaluation spaces

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

$RS (D, d) = Ev_{D} (F [X]_{< d}) .$

This is the Reed–Solomon evaluation space of degree bound $d$ . Since $Ev_{D}$ is injective on $F [X]_{< N}$ ,

$dim RS (D, d) = d .$

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

$CH_{m, k} = {λ : de g U_{λ} < 2^{k}} .$

Theorem 7.3 — Character-space/Reed–Solomon correspondence

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

$Φ_{D} (CH_{m, k}) = RS (D, 2^{k}) .$

Moreover, the restricted map

$Φ_{D}_{CH_{m, k}} : CH_{m, k} ⟶ RS (D, 2^{k})$

is a linear isomorphism.

Proof

By the low-degree characterization from Chapter 4,

$λ \in CH_{m, k} ⟺ U_{λ} \in F [X]_{< 2^{k}} .$

Applying $Ev_{D}$ to both sides gives

$Φ_{D} (CH_{m, k}) = Ev_{D} (F [X]_{< 2^{k}}) = RS (D, 2^{k}) .$

The restriction is injective because $Φ_{D}$ is injective, and it is surjective by the displayed equality. $□$

As a consistency check,

$dim CH_{m, k} = 2^{k} = dim RS (D, 2^{k}) .$

7.4 Minimum distance in evaluation coordinates

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

$d_{m i n} (C) = 0 \neq = c \in C min wt_{H} (c) .$

Proposition 7.4 — Reed–Solomon minimum distance

For $1 \leq d \leq N$ ,

$d_{m i n} (RS (D, d)) = N - d + 1.$

Proof

Let $0 \neq = f \in F [X]_{< d}$ . The polynomial $f$ has at most $d - 1$ roots in $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 $de g f = d - 1$ , and $f$ vanishes at exactly those selected evaluation points. Its evaluation vector has Hamming weight $N - d + 1$ . $□$

Consequently,

$d_{m i n} (Φ_{D} (CH_{m, k})) = N - 2^{k} + 1.$

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

7.5 Coordinate equivalence is not proximity equivalence

The map $Φ_{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

$dist_{H} (λ, CH_{m, k}) = dist_{H} (Φ_{D} (λ), 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:

fold the kernel coefficient table and then evaluate the folded polynomial;
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 $CH_{m, k}$ and $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.

The Affine Butterfly Identity

Status: Established locally; global tower existence is conditional

The classical even–odd butterfly pairs the points $α$ and $- α$ through their common square. The same local reconstruction works when the square is followed by an invertible affine change of coordinate.

This chapter proves that local identity and defines the domain structure needed to iterate it. It does not assert that a tower of every desired size exists over every field.

8.1 Assumptions and notation

Let $F$ be a field of characteristic different from $2$ . Choose $u \in F^{\times}$ and $v \in F$ , and define the affine quadratic map

$π_{u, v} (x) = \frac{x ^{2} - v}{u} .$

For every $α \in F$ ,

$π_{u, v} (α) = π_{u, v} (- α) .$

If $α \neq = 0$ , the two points $α$ and $- α$ are distinct. This is the local two-to-one structure used by the affine butterfly.

The assumptions $u \neq = 0$ and $char (F) \neq = 2$ are essential for the formulas below: the map contains division by $u$ , and the reconstruction formulas contain division by $2$ .

8.2 Even–odd decomposition

Let

$f (X) = a = 0 \sum d c_{a} X^{a} .$

Separating its even and odd powers gives unique polynomials $f_{even}$ and $f_{odd}$ such that

$f (X) = f_{even} (X^{2}) + X f_{odd} (X^{2}),$

where

$f_{even} (T) = j \sum c_{2 j} T^{j}$

and

$f_{odd} (T) = j \sum c_{2 j + 1} T^{j} .$

To express this decomposition in the affine coordinate

$Y = \frac{X ^{2} - v}{u},$

define

$A (Y) = f_{even} (u Y + v)$

and

$B (Y) = f_{odd} (u Y + v) .$

Since $X^{2} = u Y + v$ , we obtain

$f (X) = A (Y) + XB (Y) .$

Proposition 8.1 — Affine even–odd decomposition

For every $f \in F [X]$ , there are unique polynomials $A, B \in F [Y]$ satisfying

$f (X) = A (\frac{X ^{2} - v}{u}) + XB (\frac{X ^{2} - v}{u}) .$

Proof

Existence follows from the construction above. For uniqueness, suppose

$A (\frac{X ^{2} - v}{u}) + XB (\frac{X ^{2} - v}{u}) = 0.$

The first term contains only even powers of $X$ , while the second contains only odd powers. Both terms must therefore vanish. The substitution $T \mapsto (X^{2} - v) / u$ is injective on $F [T]$ , so $A = B = 0$ . $□$

8.3 Local evaluation butterfly

Let $α \in F^{\times}$ and set

$β = π_{u, v} (α) = \frac{α ^{2} - v}{u} .$

Evaluating the affine decomposition at the paired points gives

$f (α) = A (β) + α B (β)$

and

$f (- α) = A (β) - α B (β) .$

Theorem 8.2 — Affine butterfly identity

For every nonzero $α \in F$ ,

$A (β) = \frac{f ( α ) + f ( - α )}{2}$

and

$B (β) = \frac{f ( α ) - f ( - α )}{2 α},$

where $β = (α^{2} - v) / u$ .

Proof

Add the two evaluation identities to obtain

$f (α) + f (- α) = 2 A (β) .$

Subtract them to obtain

$f (α) - f (- α) = 2 α B (β) .$

Because $2 \neq = 0$ and $α \neq = 0$ , both denominators are invertible. $□$

The reconstruction formula is locally identical to the classical butterfly. The parameters $u$ and $v$ determine which parent point $β$ is associated with the pair ${α, - α}$ , but they do not change the two-point linear reconstruction.

8.4 Degree reduction

If $f = 0$ , then $A = B = 0$ and every degree-bound statement below is immediate. Assume henceforth that $f \neq = 0$ and let $n = de g f$ . From the ordinary even–odd decomposition,

$de g f_{even} \leq ⌊ \frac{n}{2} ⌋$

and

$de g f_{odd} \leq ⌊ \frac{n - 1}{2} ⌋ .$

Composition with the nonconstant affine polynomial $u Y + v$ preserves degree. Therefore

$de g A \leq ⌊ \frac{n}{2} ⌋$

and

$de g B \leq ⌊ \frac{n - 1}{2} ⌋ .$

In particular, if $de g f < N$ with even $N$ , then

$de g A < \frac{N}{2} and de g B < \frac{N}{2} .$

Thus the affine change of coordinate preserves the local degree-halving property of the classical butterfly.

8.5 Affine quadratic domain towers

The local identity can be iterated only when the evaluation domains are compatible across rounds.

Definition 8.3 — Affine quadratic domain tower

An affine quadratic domain tower of depth $m$ over $F$ consists of finite sets

$D_{0}, D_{1}, \dots, D_{m} \subseteq F$

and parameters

$u_{i} \in F^{\times}, v_{i} \in F, 0 \leq i < m,$

such that:

$∣ D_{i} ∣ = 2^{m - i}$ for every $i$ ;
the map

$π_{i} (x) = \frac{x ^{2} - v _{i}}{u _{i}}$

sends $D_{i}$ onto $D_{i + 1}$ ; and
every $β \in D_{i + 1}$ has exactly two preimages in $D_{i}$ .

Since the two solutions of

$x^{2} = u_{i} β + v_{i}$

are $α$ and $- α$ , each valid fiber has the form

${α, - α}$

with $α \neq = 0$ . Consequently, no valid two-point fiber contains zero.

Proposition 8.4 — One evaluation layer

Suppose $D_{i} \to D_{i + 1}$ is one level of an affine quadratic domain tower. Given the evaluations of $f$ on $D_{i}$ , the butterfly formulas determine the evaluations of both affine components $A$ and $B$ on $D_{i + 1}$ .

Proof

For each $β \in D_{i + 1}$ , choose either element $α$ of its two-point fiber. Both $f (α)$ and $f (- α)$ are available in the evaluation table on $D_{i}$ . Theorem 8.2 determines $A (β)$ and $B (β)$ . Repeating this for every fiber fills both evaluation tables on $D_{i + 1}$ . $□$

The result is independent of which member of the fiber is named $α$ : replacing $α$ by $- α$ changes both the numerator and denominator in the formula for $B (β)$ by a minus sign.

8.6 Local theorem versus global existence

The affine butterfly identity holds for every choice of $u \neq = 0$ , $v$ , and nonzero paired point $α$ over a field of odd characteristic. This is a local algebraic theorem.

By contrast, constructing a complete tower

$D_{0} ⟶ D_{1} ⟶ \dots ⟶ D_{m}$

requires simultaneous quadratic-residue and cardinality conditions at every level. The local theorem does not guarantee that such a tower exists for a specified field and depth.

Accordingly, later algorithms using an affine tower must state tower existence as an explicit assumption unless a separate construction theorem has been proved for the field in question.

8.7 What has been established

This chapter establishes:

the unique affine even–odd decomposition;
the two-point affine butterfly reconstruction formulas;
local degree halving;
the precise definition of an affine quadratic domain tower; and
one evaluation-layer reduction on any valid tower level.

It does not establish universal or maximal tower existence, an FFT complexity bound, or a protocol-soundness result.

Affine Coordinates and the Affine Kernel Basis

Status: Established

The affine butterfly replaces repeated squaring by repeated affine quadratic maps. This chapter constructs polynomial coordinates adapted to those maps and proves that the resulting affine kernel family is a basis.

The basis theorem is purely algebraic. It does not require the existence of an evaluation-domain tower, although such a tower is needed for the evaluation algorithms developed later.

9.1 Recursive affine coordinates

Let $F$ be a field and let $m \geq 1$ . Choose parameters

$u_{i} \in F^{\times}, v_{i} \in F, 0 \leq i < m .$

Define the recursive affine coordinates

$X_{0} (X) = X$

and

$X_{i + 1} (X) = \frac{X _{i} ( X ) ^{2} - v _{i}}{u _{i}}$

for $0 \leq i < m$ .

These are polynomial identities in the original variable $X$ . The notation $X_{i}$ names the polynomial coordinate at level $i$ ; it does not introduce an independent variable.

Proposition 9.1 — Degree doubling

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

$de g X_{i} = 2^{i} .$

Moreover, each $X_{i}$ has a nonzero leading coefficient.

Proof

The statement holds for $X_{0} = X$ . Suppose $X_{i}$ has degree $2^{i}$ and nonzero leading coefficient $c_{i}$ . Then $X_{i}^{2} - v_{i}$ has degree $2^{i + 1}$ and leading coefficient $c_{i}^{2}$ . Division by $u_{i} \neq = 0$ preserves the degree and gives the nonzero leading coefficient

$c_{i + 1} = \frac{c _{i}^{2}}{u _{i}} .$

The result follows by induction. $□$

9.2 Affine monomials

For $e = (e_{0}, \dots, e_{m - 1}) \in B_{m}$ , define

$M_{e}^{aff} (X) = i = 0 \prod m - 1 X_{i} (X)^{e_{i}} .$

Because each $e_{i}$ is Boolean,

$de g M_{e}^{aff} = i = 0 \sum m - 1 e_{i} 2^{i} = ∣ e ∣_{2} .$

As $e$ ranges over $B_{m}$ , these degrees are exactly

$0, 1, \dots, 2^{m} - 1.$

Theorem 9.2 — Affine monomial basis

The family

${M_{e}^{aff} : e \in B_{m}}$

is a basis of $F [X]_{< 2^{m}}$ .

Proof

The affine monomials have pairwise distinct degrees. In a nontrivial linear combination, choose a term of largest degree having a nonzero coefficient. No other term has the same degree, so its leading term cannot be cancelled. Thus the family is linearly independent.

It contains $2^{m}$ polynomials, equal to the dimension of $F [X]_{< 2^{m}}$ . Therefore it is a basis. $□$

With the affine monomials ordered by $∣ e ∣_{2}$ , their coefficient matrix in the ordinary monomial basis is triangular with nonzero diagonal.

9.3 Affine kernel polynomials

For $y = (y_{0}, \dots, y_{m - 1}) \in B_{m}$ , define

$K_{y}^{aff} (X) = i = 0 \prod m - 1 (X_{i} (X) + y_{i}) .$

There are exactly $2^{m}$ affine kernel polynomials. Expanding the product in the affine monomial basis gives

$K_{y}^{aff} (X) = e \in B_{m} \sum (i : e_{i} = 0 \prod y_{i}) M_{e}^{aff} (X) .$

The coefficient of $M_{e}^{aff}$ is $1$ exactly when every coordinate with $e_{i} = 0$ also has $y_{i} = 1$ ; otherwise it is $0$ .

This Boolean incidence relation is identical to the relation between the ordinary kernel polynomials and the binary monomials in Chapter 3.

Theorem 9.3 — Affine kernel basis

The family

${K_{y}^{aff} : y \in B_{m}}$

is a basis of $F [X]_{< 2^{m}}$ .

Proof

The expansion from affine kernels to affine monomials is the tensor product of the one-coordinate transformation

$X_{i} and X_{i} + 1.$

Relative to the local monomial pair $1, X_{i}$ , its matrix is

$(0111) .$

Its determinant is $- 1$ , which is nonzero over every field. Therefore its $m$ -fold tensor product is invertible. Hence the affine kernel family is obtained from the affine monomial basis by an invertible change of basis.

Theorem 9.2 shows that the affine monomials form a basis, so the affine kernels also form a basis. $□$

The conclusion depends only on the degree-doubling property and not on the existence of finite sets $D_{0}, \dots, D_{m}$ forming an affine domain tower.

9.4 Small example

Let $m = 2$ . Then

$X_{0} = X$

and

$X_{1} = \frac{X ^{2} - v _{0}}{u _{0}} .$

The four affine monomials are

$1, X_{0}, X_{1}, X_{0} X_{1},$

with respective degrees $0, 1, 2, 3$ . The affine kernels are

$K_{(0, 0)}^{aff} = X_{0} X_{1},$

$K_{(1, 0)}^{aff} = (X_{0} + 1) X_{1},$

$K_{(0, 1)}^{aff} = X_{0} (X_{1} + 1),$

and

$K_{(1, 1)}^{aff} = (X_{0} + 1) (X_{1} + 1) .$

Their affine-monomial expansions are

Kernel	Affine-monomial expansion
$K_{(0, 0)}^{aff}$	$M_{(1, 1)}^{aff}$
$K_{(1, 0)}^{aff}$	$M_{(0, 1)}^{aff} + M_{(1, 1)}^{aff}$
$K_{(0, 1)}^{aff}$	$M_{(1, 0)}^{aff} + M_{(1, 1)}^{aff}$
$K_{(1, 1)}^{aff}$	$M_{(0, 0)}^{aff} + M_{(1, 0)}^{aff} + M_{(0, 1)}^{aff} + M_{(1, 1)}^{aff}$

The table is the same Boolean transform seen in the ordinary kernel basis; only the monomial coordinates have changed.

9.5 Exact coefficient conversion

Write a polynomial in affine kernel coordinates as

$U (X) = y \in B_{m} \sum λ_{y} K_{y}^{aff} (X)$

and in affine monomial coordinates as

$U (X) = e \in B_{m} \sum c_{e} M_{e}^{aff} (X) .$

The relation between $λ$ and $c$ is exactly the Boolean zeta-type relation from Chapter 3:

$c_{e} = y_{i} = 1 whenever e_{i} = 0 \sum λ_{y} .$

The same butterfly network therefore converts between the two tables. It uses exactly

$\frac{m 2 ^{m}}{2}$

additions for the forward transform and the same number of additions or subtractions for its inverse.

These counts concern conversion between affine kernel coefficients and affine monomial coefficients. They do not include expansion of the recursive coordinates $X_{i}$ into ordinary monomials.

9.6 Low-degree filtration remains Boolean

The affine monomial $M_{e}^{aff}$ has degree $∣ e ∣_{2}$ , and these degrees are distinct. Consequently,

$de g U < 2^{k}$

if and only if

$c_{e} = 0 for every e with ∣ e ∣_{2} \geq 2^{k} .$

Since the kernel-to-monomial Boolean transform is unchanged, the proof of Chapter 4 applies verbatim.

Corollary 9.4 — Affine low-degree character condition

Let $0 \leq k \leq m$ , let $q = m - k$ , and write $y = (x, h)$ with $x \in B_{k}$ and $h \in B_{q}$ . Then

$de g y \in B_{m} \sum λ_{y} K_{y}^{aff} < 2^{k}$

if and only if there exists a table $μ : B_{k} \to F$ such that

$λ_{(x, h)} = (- 1)^{q - wt (h)} μ_{x}$

for every $x \in B_{k}$ and $h \in B_{q}$ .

Thus the character space $CH_{m, k}$ describes the degree filtration in both the ordinary and affine kernel bases.

9.7 What has been established

This chapter establishes:

degree doubling for recursive affine coordinates;
the affine monomial basis theorem;
the affine kernel basis theorem over any field;
the exact Boolean coefficient transform and its arithmetic cost; and
the unchanged low-degree character condition in affine kernel coordinates.

It does not establish the existence of a compatible evaluation-domain tower or the complexity of evaluating this basis on such a tower.

Fast Evaluation on an Affine Tower

Status: Conditional algorithmic theorem

This chapter gives a recursive algorithm for evaluating a polynomial written in the affine kernel basis. If a compatible affine quadratic domain tower of size $N = 2^{m}$ is supplied, the algorithm uses $O (N lo g N)$ field operations.

The recursion and its operation count are established. The conclusion is conditional because the existence of a tower of the requested size is a separate arithmetic question.

10.1 Compatible algebraic and domain data

Let $F$ be a field of characteristic different from $2$ . Fix $m \geq 0$ and let $N = 2^{m}$ .

Assume that we are given an affine quadratic domain tower

$D_{0} ⟶ D_{1} ⟶ \dots ⟶ D_{m}$

with

$∣ D_{i} ∣ = 2^{m - i} .$

At level $i$ , the tower map is

$π_{i} (x) = \frac{x ^{2} - v _{i}}{u _{i}}, u_{i} \in F^{\times},$

and every point of $D_{i + 1}$ has a fiber ${α, - α} \subseteq D_{i}$ with $α \neq = 0$ .

Use the same parameters to define the affine coordinates

$X_{0} = X, X_{i + 1} = \frac{X _{i}^{2} - v _{i}}{u _{i}} .$

The compatibility between the coordinate recursion and the domain maps is essential: when $α \in D_{0}$ , the value $X_{i} (α)$ lies in $D_{i}$ .

10.2 Input representation

Let

$f (X) = y \in B_{m} \sum λ_{y} K_{y}^{aff} (X),$

where

$K_{y}^{aff} (X) = i = 0 \prod m - 1 (X_{i} + y_{i}) .$

The input is the table of $N$ affine kernel coefficients

$(λ_{y})_{y \in B_{m}} .$

The output is the ordered evaluation table

$(f (α))_{α \in D_{0}} .$

The algorithm assumes that every domain level is stored together with its two-point fibers. Searching for fibers is not included in the evaluation cost.

10.3 First coefficient split

Write each Boolean index as

$y = (y_{0}, z), y_{0} \in B_{1}, z \in B_{m - 1} .$

Define the tail kernel

$K_{z}^{tail} (X_{1}) = i = 1 \prod m - 1 (X_{i} + y_{i}) .$

Then

$f (X_{0}) = z \sum λ_{0, z} X_{0} K_{z}^{tail} (X_{1}) + z \sum λ_{1, z} (X_{0} + 1) K_{z}^{tail} (X_{1}) .$

Define two tail polynomials

$A (X_{1}) = z \sum A_{z} K_{z}^{tail} (X_{1})$

and

$B (X_{1}) = z \sum B_{z} K_{z}^{tail} (X_{1}),$

with coefficient tables

$A_{z} = λ_{1, z}$

and

$B_{z} = λ_{0, z} + λ_{1, z} .$

It follows that

$f (X_{0}) = A (X_{1}) + X_{0} B (X_{1}) .$

Proposition 10.1 — Affine-kernel coefficient split

For each $z \in B_{m - 1}$ , the first recursive split is

$(λ_{0, z}, λ_{1, z}) ⟼ (A_{z}, B_{z}) = (λ_{1, z}, λ_{0, z} + λ_{1, z}) .$

The complete split uses exactly $N /2$ field additions and no field multiplications.

This inexpensive update is the reason for using affine kernel coordinates. In the ordinary monomial basis, the affine substitution would introduce binomial expansions of shifted powers.

10.4 One value butterfly

Let ${α, - α}$ be the fiber over $β \in D_{1}$ . Since $X_{1} (α) = X_{1} (- α) = β$ ,

$f (α) = A (β) + α B (β)$

and

$f (- α) = A (β) - α B (β) .$

Given $A (β)$ and $B (β)$ , computing both outputs uses exactly:

one multiplication, to form $α B (β)$ ; and
two additions or subtractions.

The result does not depend on which member of the fiber is named $α$ .

10.5 Recursive algorithm

The two tail polynomials $A$ and $B$ are expressed in the affine kernel basis associated with the shortened coordinate sequence

$X_{1}, X_{2}, \dots, X_{m - 1} .$

They can therefore be evaluated recursively on $D_{1}$ using the remaining tower levels.

The recursive procedure is:

AffineKernelEval(level i, coefficient table lambda):
    n := length(lambda)

    if n = 1:
        return the one constant value

    for each tail index z:
        A[z] := lambda[1,z]
        B[z] := lambda[0,z] + lambda[1,z]

    values_A := AffineKernelEval(level i+1, A)
    values_B := AffineKernelEval(level i+1, B)

    for each stored fiber {alpha,-alpha} over beta in D_(i+1):
        t := alpha * values_B[beta]
        values_f[alpha]  := values_A[beta] + t
        values_f[-alpha] := values_A[beta] - t

    return values_f

The base case contains the empty tail kernel, which is the constant polynomial $1$ . Hence the sole remaining coefficient is already the value on the one-point final domain.

Theorem 10.2 — Correctness

Given compatible affine coordinates and an affine quadratic domain tower, the algorithm returns $f (α)$ for every $α \in D_{0}$ .

Proof

Proceed by induction on $m$ . The claim is immediate when $m = 0$ .

For $m > 0$ , Proposition 10.1 gives the polynomial identity

$f (X_{0}) = A (X_{1}) + X_{0} B (X_{1}) .$

The induction hypothesis correctly evaluates $A$ and $B$ on $D_{1}$ . For each fiber ${α, - α}$ over $β$ , the value butterfly then computes $f (α)$ and $f (- α)$ . The fibers partition $D_{0}$ , so every requested evaluation is returned. $□$

10.6 Exact arithmetic cost

Let $M (N)$ be the number of field multiplications and let $A (N)$ be the number of field additions or subtractions.

At a problem of size $N > 1$ :

the coefficient split uses $N /2$ additions;
the two recursive calls have size $N /2$ ;
the value butterflies use $N /2$ multiplications and $N$ additions or subtractions.

Therefore

$M (N) = 2 M (N /2) + \frac{N}{2}, M (1) = 0,$

and

$A (N) = 2 A (N /2) + \frac{3 N}{2}, A (1) = 0.$

Theorem 10.3 — Exact evaluation cost

For $N = 2^{m}$ , the recursive affine-kernel evaluation uses exactly

$M (N) = \frac{m N}{2}$

field multiplications and

$A (N) = \frac{3 m N}{2}$

field additions or subtractions.

Proof

At every recursion depth, the subproblem sizes sum to $N$ . Thus each of the $m$ nontrivial depths uses $N /2$ multiplications and $3 N /2$ additions or subtractions. Summing over all depths gives the formulas. $□$

Consequently, the arithmetic complexity is

$O (N lo g N) .$

These counts exclude:

construction or discovery of the affine tower;
validation and ordering of its fibers;
conversion from another polynomial basis;
memory movement and indexing; and
hashing, commitments, or proof-protocol operations.

Multiplication by a precomputed domain element is counted as one field multiplication.

10.7 What the condition replaces

A classical radix-two FFT usually assumes a multiplicative subgroup or coset supporting the required chain of squaring maps. The affine algorithm does not require $D_{0}$ itself to be such a subgroup.

However, the subgroup assumption is not removed without replacement. It is replaced by the requirement that compatible sets

$D_{0}, D_{1}, \dots, D_{m}$

and two-to-one affine quadratic maps between them are available. Whether that requirement can be met is field- and size-dependent.

Thus the correct implication is:

$valid compatible affine tower ⟹ affine-kernel evaluation in O (N lo g N) .$

The converse is not asserted, and universal tower existence is not assumed.

10.8 Relation to interpolation and protocols

The evaluation map is invertible because the points of $D_{0}$ are distinct and the affine kernels form a basis. Therefore interpolation exists as a linear operation.

This chapter does not yet provide or count a recursive interpolation algorithm. It also does not prove a proximity property, an error-correction guarantee, or protocol soundness. Those questions require separate analysis.

10.9 What has been established

Conditional on a supplied compatible affine tower, this chapter establishes:

the affine-kernel coefficient split;
the recursive evaluation algorithm and its correctness;
an exact cost of $m N /2$ multiplications;
an exact cost of $3 m N /2$ additions or subtractions; and
total arithmetic complexity $O (N lo g N)$ .

No universal tower-construction, interpolation-complexity, proximity, or soundness theorem is asserted.

Research Frontier and Open Problems

Status: Open research map

The preceding chapters establish the current algebraic core of the Algorizk Research Notes. This chapter marks the boundary between what has been proved, what holds under explicit hypotheses, what may be supported computationally, and what remains open.

Its purpose is not to announce conclusions prematurely. It provides a stable map for future proofs, experiments, implementations, and protocol work.

11.1 Status vocabulary

Every substantial future claim should use one of the following labels.

Established

An established result has a complete proof under the assumptions stated in the result. Its dependencies must also be established or explicitly cited.

Conditional

A conditional result has a complete implication of the form

$stated hypotheses ⟹ stated conclusion .$

The implication is proved, but one or more hypotheses may not be known to hold in every field or parameter regime of interest.

Computational

A computational result is verified for a finite, explicitly recorded set of inputs by a reproducible program. It is evidence, not a universal theorem.

Open

An open item is a question, conjecture, missing proof, missing construction, or unresolved complexity or soundness analysis.

These labels describe the logical status of a claim, not its perceived importance.

11.2 Established algebraic core

The following results have been established in Chapters 1–9:

Boolean vectors index the ordinary monomial degrees below $2^{m}$ ;
the Boolean kernel polynomials form a basis of $F [X]_{< 2^{m}}$ ;
the kernel-to-monomial coefficient map is an invertible Boolean transform;
low degree is characterized exactly by the character space $CH_{m, k}$ ;
one-round and repeated coefficient folding satisfy exact algebraic identities;
repeated folding is a standard multilinear evaluation after the necessary sign correction;
evaluation on $N$ distinct field points is an isomorphism;
$CH_{m, k}$ maps exactly onto the corresponding Reed–Solomon evaluation space;
the local affine butterfly identity preserves degree halving; and
recursive affine coordinates produce an affine kernel basis with the same Boolean low-degree filtration.

These statements do not require a cryptographic protocol interpretation.

11.3 Established conditional algorithm

Chapter 10 proves the following conditional implication:

$a compatible affine quadratic domain tower of size N = 2^{m}$

$⟹$

$affine-kernel evaluation using \frac{m N}{2} multiplications and \frac{3 m N}{2} additions or subtractions .$

The recursion, correctness proof, and operation counts are established. The existence of a compatible tower for an arbitrary field and target size is not assumed.

11.4 Results not established by coordinate equivalence

The invertible map

$Φ_{D} : F^{B_{m}} ⟶ F^{N}$

identifies kernel coefficient tables with evaluation tables. It also maps $CH_{m, k}$ onto $RS (D, 2^{k})$ .

However, invertible linear maps do not generally preserve Hamming distance. Therefore none of the following follows from invertibility alone:

equality of coefficient-space and evaluation-space distances;
transfer of sparse errors between the two coordinate systems;
preservation of relative distance under $Φ_{D}$ ;
a proximity gap for folded coefficient tables; or
robust soundness of a proof protocol.

Any future result of this kind requires a separate theorem with a valid metric argument.

11.5 Open Problem A — Affine tower existence

Let $p$ be an odd prime. Define $M (p)$ to be the largest integer $m$ for which $F_{p}$ contains an affine quadratic domain tower whose first domain has size $2^{m}$ .

Basic cardinality gives

$2^{M (p)} \leq p - 1,$

because the first domain is partitioned into nonzero pairs ${α, - α}$ .

The main questions are:

How can $M (p)$ be characterized arithmetically?
Which primes attain the largest power of two allowed by cardinality?
What lower bounds on $M (p)$ hold for every prime or for a positive density of primes?
How does the answer change for finite extension fields?

Finite searches may suggest patterns, but they do not by themselves answer these questions.

11.6 Open Problem B — Constructing towers efficiently

Even when a tower exists, an evaluation algorithm needs the domains, affine parameters, and fiber ordering explicitly.

The constructive problem is to design an algorithm that, given a field and a target depth, either:

outputs a valid tower with a machine-checkable certificate; or
certifies that no tower exists within a precisely specified search class.

Relevant complexity measures include:

field operations;
quadratic-residuosity tests;
memory usage;
deterministic versus randomized running time; and
preprocessing cost relative to repeated evaluations on the same tower.

A heuristic search is useful computational evidence, but it is not a general construction theorem.

11.7 Open Problem C — Metric comparison

For a coefficient table $λ$ , define the relative coefficient distance

$δ_{coef} (λ) = \frac{1}{N} dist_{H} (λ, CH_{m, k})$

and the relative evaluation distance

$δ_{eval} (λ) = \frac{1}{N} dist_{H} (Φ_{D} (λ), RS (D, 2^{k})) .$

The open problem is to determine whether useful inequalities between these quantities hold under additional structure on:

the evaluation domain $D$ ;
the error model;
the coefficient support;
the affine or ordinary kernel transform; or
a metric better adapted to the transform.

No universal constant-factor Hamming comparison is currently asserted.

11.8 Open Problem D — Robustness under folding

Chapters 5 and 6 prove exact identities for correctly formed tables. A proximity protocol must additionally analyze corrupted tables.

The central questions are:

If a table is far from $CH_{m, k}$ , how often can a random fold be close to $CH_{m - 1, k - 1}$ ?
Which metric should be used before and after folding?
How do exceptional challenges depend on the error pattern?
Can the analysis be iterated without treating a different nearest codeword independently at every round?
What list-size or agreement bounds are required?

An algebraic folding identity is not sufficient to answer these robustness questions.

11.9 Open Problem E — List decoding and proximity gaps

The evaluation image of $CH_{m, k}$ is a Reed–Solomon code, whose evaluation-space distance is known. The desired research direction is to understand proximity tests that respect the kernel and folding structure.

A complete result would need to specify:

the received-word space;
the code and metric;
the agreement or distance threshold;
the list size;
the challenge distribution;
the number of rounds and queries; and
the final soundness error.

Until all these components are proved together, a claimed proximity gap must remain open or conditional.

11.10 Open Problem F — Transparent post-quantum protocol

The algebraic results suggest a transparent protocol architecture combining:

kernel or affine-kernel coefficient folding;
evaluation consistency checks;
collision-resistant hash commitments;
random field challenges; and
a final low-dimensional verification step.

A complete protocol theorem must still provide:

precise prover and verifier algorithms;
completeness;
binding assumptions;
proximity or knowledge soundness;
concrete parameters for the target security level;
round, query, proof-size, and arithmetic counts; and
a post-quantum security interpretation.

No pairing-based commitment or trusted setup is assumed in this research direction.

11.11 Open Problem G — Interpolation and implementation

Chapter 10 establishes fast forward evaluation on a supplied affine tower. The next algorithmic tasks are:

derive and verify the inverse recursive interpolation algorithm;
give exact multiplication, addition, and inversion counts;
determine which inverses can be precomputed;
design an iterative memory layout for the fibers;
compare in-place and out-of-place implementations; and
benchmark against classical FFT, additive FFT, and general multipoint evaluation baselines.

These are concrete development tasks. They should not be described as completed until code, tests, and reproducible benchmarks are available.

11.12 Open Problem H — Hardware-oriented evaluation

The butterfly structure exposes regular pairs of additions and one multiplication by a domain element. This suggests a hardware pipeline, but an operation count alone is not a hardware performance result.

A credible FPGA or accelerator study must report:

the target field and representation;
multiplier and reduction architecture;
memory bandwidth and layout;
pipeline depth and initiation interval;
clock frequency;
latency and throughput;
resource utilization;
power or energy when available; and
comparisons under matched security and parameter assumptions.

Until such an implementation exists, hardware advantages remain a research and engineering hypothesis.

11.13 Computational-evidence standard

A computational claim may be promoted into these notes only when its record contains:

the exact field and parameter range;
the definition of the searched object;
whether the search was exhaustive or sampled;
deterministic code or recorded randomness;
independent validity checks for every reported object;
software and dependency versions; and
a statement limited to the tested range.

For example, an exhaustive search may establish that no object exists inside the enumerated finite search space. It does not establish a general nonexistence theorem for untested primes, depths, or construction families.

Internal notebooks are source material for this process. They are not copied directly into the book.

11.14 Publication gates

Before a result changes status, it should pass the corresponding gate.

Proposed status	Minimum publication gate
Established	Complete proof, notation check, dependency check, and independent proof audit
Conditional	Complete implication with every hypothesis stated explicitly
Computational	Reproducible code, exact finite scope, validation checks, and recorded environment
Open	Precise question with no language implying that the answer is known

Protocol results additionally require a complete security model and soundness analysis. Performance results additionally require reproducible implementation and benchmark methodology.

11.15 Current boundary

The current book provides a working mathematical foundation:

$Boolean kernel algebra ⟶ low-degree character space ⟶ folding identities ⟶ evaluation correspondence$

and, conditionally,

$compatible affine tower ⟶ fast affine-kernel evaluation .$

The next research phase begins at tower construction, metric robustness, proximity soundness, interpolation, and implementation. These directions are recorded as open until their required proofs or reproducible evidence are complete.