Even–Odd Folding

Status: Established algebraic identity
Evaluation form: Conditional on a negation-paired domain and $\mathrm{char}\mathbb{F}\ne 2$

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

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

These layers must be kept distinct.

5.1 Even–odd decomposition

Let

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

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

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

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

$$A(Y)=\sum _{j\ge 0}{u}_{2j}{Y}^j.$$

The polynomial $B$ contains the odd coefficients:

$$B(Y)=\sum _{j\ge 0}{u}_{2j+1}{Y}^j.$$

Both satisfy

$$\mathrm{deg}A<\frac{N}{2},\mathrm{deg}B<\frac{N}{2}.$$

5.2 One-round polynomial fold

Let $\rho \in \mathbb{F}$ be a folding challenge.

Definition 5.1 — Polynomial fold

For

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

define

$$\boxed{{\mathrm{Fold}}_{\rho }(U)(Y)=A(Y)+\rho B(Y)}.$$

The folded polynomial belongs to

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

The challenge replaces the active variable $X$ by the field element $\rho$ 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 {\mathbb{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)=\sum _{z\in {\mathbb{B}}_{m-1}}{\lambda }_{(0,z)}{K}_{(0,z)}(X)+\sum _{z\in {\mathbb{B}}_{m-1}}{\lambda }_{(1,z)}{K}_{(1,z)}(X).$$

Substituting the kernel identities gives

$$U(X)=\sum _z{\lambda }_{(1,z)}{K}_z(X^2)+X\sum _z\left({\lambda }_{(0,z)}+{\lambda }_{(1,z)}\right)K_z(X^2).$$

Therefore, the even and odd polynomials are

$$A(Y)=\sum _z{\lambda }_{(1,z)}{K}_z(Y)$$

and

$$B(Y)=\sum _z\left({\lambda }_{(0,z)}+{\lambda }_{(1,z)}\right)K_z(Y).$$

5.4 Folding the kernel coefficient table

The folded polynomial is

$${\mathrm{Fold}}_{\rho }(U)(Y)=A(Y)+\rho B(Y).$$

Its kernel coefficient at $z$ is therefore

$${\lambda }_z^{\prime }={\lambda }_{(1,z)}+\rho \left({\lambda }_{(0,z)}+{\lambda }_{(1,z)}\right).$$

Equivalently,

$$\boxed{{\lambda }_z^{\prime }=\rho {\lambda }_{(0,z)}+(1+\rho ){\lambda }_{(1,z)}}.$$

Definition 5.2 — Coefficient-table fold

Define

$$F_{\rho }:{\mathbb{F}}^{{\mathbb{B}}_m}⟶{\mathbb{F}}^{{\mathbb{B}}_{m-1}}$$

by

$$\boxed{F_{\rho }(\lambda {)}_z=\rho {\lambda }_{(0,z)}+(1+\rho ){\lambda }_{(1,z)}}.$$

The polynomial and coefficient-table folds agree:

$${\mathrm{Fold}}_{\rho }\left(\sum _y{\lambda }_y{K}_y\right)=\sum _z{F}_{\rho }(\lambda {)}_z{K}_z.$$

5.5 Exact arithmetic cost

For each $z\in {\mathbb{B}}_{m-1}$, compute

$$s_z={\lambda }_{(0,z)}+{\lambda }_{(1,z)}$$

and then

$$F_{\rho }(\lambda {)}_z={\lambda }_{(1,z)}+\rho 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

$$\boxed{\frac{N}{2}\text{ field multiplications}+N\text{ 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\le k\le m.$$

Write the kernel index as

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

where

$$b\in {\mathbb{B}}_1,x^{\prime }\in {\mathbb{B}}_{k-1},h\in {\mathbb{B}}_{m-k}.$$

Suppose

$$\lambda \in {\mathsf{CH}}_{m,k}.$$

Then there exists $\mu :{\mathbb{B}}_k\to \mathbb{F}$ such that

$${\lambda }_{(b,x^{\prime },h)}=(-1{)}^{m-k-\mathrm{wt}(h)}{\mu }_{(b,x^{\prime })}.$$

Applying the fold gives

$$F_{\rho }(\lambda {)}_{(x^{\prime },h)}=(-1{)}^{m-k-\mathrm{wt}(h)}\left(\rho {\mu }_{(0,x^{\prime })}+(1+\rho ){\mu }_{(1,x^{\prime })}\right).$$

Define

$${\mu }_{x^{\prime }}^{\prime }=\rho {\mu }_{(0,x^{\prime })}+(1+\rho ){\mu }_{(1,x^{\prime })}.$$

Since

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

we obtain

$$F_{\rho }(\lambda {)}_{(x^{\prime },h)}=(-1{)}^{(m-1)-(k-1)-\mathrm{wt}(h)}{\mu }_{x^{\prime }}^{\prime }.$$

Therefore,

$$\boxed{F_{\rho }({\mathsf{CH}}_{m,k})\subseteq {\mathsf{CH}}_{m-1,k-1}}.$$

5.7 The boundary case $k=0$

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

$${\lambda }_h=(-1{)}^{m-\mathrm{wt}(h)}\mu .$$

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

$${\lambda }_{(0,h^{\prime })}=-(-1{)}^{m-1-\mathrm{wt}(h^{\prime })}\mu$$

and

$${\lambda }_{(1,h^{\prime })}=(-1{)}^{m-1-\mathrm{wt}(h^{\prime })}\mu .$$

Consequently,

$$F_{\rho }(\lambda {)}_{h^{\prime }}=(-1{)}^{m-1-\mathrm{wt}(h^{\prime })}\mu .$$

Thus

$$\boxed{F_{\rho }({\mathsf{CH}}_{m,0})\subseteq {\mathsf{CH}}_{m-1,0}}.$$

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

5.8 Degree reduction

By the low-degree filtration theorem,

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

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

$$F_{\rho }(\lambda )\in {\mathsf{CH}}_{m-1,k-1}.$$

Therefore,

$$\boxed{\mathrm{deg}U<2^k⟹\mathrm{deg}{\mathrm{Fold}}_{\rho }(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 {\mathbb{F}}^{\times }$ satisfy

$$\alpha \in D⟹-\alpha \in D.$$

Assume

$$\mathrm{char}\mathbb{F}\ne 2.$$

Define the squared domain

$$D^{\prime }=\{{\alpha }^2:\alpha \in D\}.$$

Assume every $\beta \in D^{\prime }$ has exactly two preimages $\alpha ,-\alpha$ in $D$.

Let

$$w(\alpha )=U(\alpha )$$

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

From

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

we obtain

$$w(\alpha )=A(\beta )+\alpha B(\beta )$$

and

$$w(-\alpha )=A(\beta )-\alpha B(\beta ),$$

where

$$\beta ={\alpha }^2.$$

Adding and subtracting gives

$$A(\beta )=\frac{w(\alpha )+w(-\alpha )}{2}$$

and

$$B(\beta )=\frac{w(\alpha )-w(-\alpha )}{2\alpha }.$$

5.10 Evaluation-word fold

Definition 5.3 — Evaluation fold

For $\beta ={\alpha }^2$, define

$$\boxed{{\mathrm{fold}}_{\rho }^D(w)(\beta )=\frac{w(\alpha )+w(-\alpha )}{2}+\rho \frac{w(\alpha )-w(-\alpha )}{2\alpha }}.$$

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

Substituting the expressions for $A(\beta )$ and $B(\beta )$ gives

$${\mathrm{fold}}_{\rho }^D(w)(\beta )=A(\beta )+\rho B(\beta ).$$

Therefore,

$$\boxed{{\mathrm{fold}}_{\rho }^D(w)(\beta )={\mathrm{Fold}}_{\rho }(U)(\beta )}.$$

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:

$$\lambda \stackrel{F_{\rho }}{\to }{F}_{\rho }(\lambda )$$

on the coefficient side,

$$U\stackrel{{\mathrm{Fold}}_{\rho }}{\to }{\mathrm{Fold}}_{\rho }(U)$$

on the polynomial side, and

$$w\stackrel{{\mathrm{fold}}_{\rho }^D}{\to }{\mathrm{fold}}_{\rho }^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

$$\boxed{({\lambda }_{(0,z)},{\lambda }_{(1,z)})⟼\rho {\lambda }_{(0,z)}+(1+\rho ){\lambda }_{(1,z)}}.$$

The fold:

• agrees with the even–odd polynomial decomposition;
• preserves the low-degree character condition;
• halves the degree bound when $k\ge 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.