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\ge 1$, let $N=2^m$, and let $\mathbb{F}$ be a field. Begin with a coefficient table

$${\lambda }_0:{\mathbb{B}}_m⟶\mathbb{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 ${\rho }_r\in \mathbb{F}$. If

$${\lambda }_r:{\mathbb{B}}_{m-r}⟶\mathbb{F},$$

define

$${\lambda }_{r+1}(z)={\rho }_r{\lambda }_r(0,z)+(1+{\rho }_r){\lambda }_r(1,z)$$

for every $z\in {\mathbb{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

$${\lambda }_{r+1}(z)={\lambda }_r(1,z)+{\rho }_r({\lambda }_r(0,z)+{\lambda }_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 {\mathbb{B}}_r$, define the folding weight

$$w_r(b)=\prod _{i=0}^{r-1}\{\begin{array}{ll}{\rho }_i,& b_i=0,\\ 1+{\rho }_i,& b_i=1.\end{array}$$

The empty product is $1$.

Proposition 6.1 — Partial repeated-fold formula

For every $r\in \{0,\dots ,m\}$ and every $z\in {\mathbb{B}}_{m-r}$,

$${\lambda }_r(z)=\sum _{b\in {\mathbb{B}}_r}{\lambda }_0(b,z)w_r(b).$$

Proof

When $r=0$, the statement is the identity ${\lambda }_0(z)={\lambda }_0(z)$.

Assume the formula holds at round $r$. Then

$${\lambda }_{r+1}(z)={\rho }_r{\lambda }_r(0,z)+(1+{\rho }_r){\lambda }_r(1,z).$$

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

$${\lambda }_{r+1}(z)={\rho }_r\sum _{b\in {\mathbb{B}}_r}{\lambda }_0(b,0,z)w_r(b)+(1+{\rho }_r)\sum _{b\in {\mathbb{B}}_r}{\lambda }_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

$${\lambda }_{r+1}(z)=\sum _{c\in {\mathbb{B}}_{r+1}}{\lambda }_0(c,z)w_{r+1}(c).$$

This completes the induction. $\square$

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

$${\lambda }_m=\sum _{y\in {\mathbb{B}}_m}{\lambda }_0(y)\prod _{i=0}^{m-1}{\rho }_i^{1-y_i}(1+{\rho }_i{)}^{y_i}.$$

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

6.3 Example with two coordinates

Let $m=2$. The first round gives

$${\lambda }_1(y_1)={\rho }_0{\lambda }_0(0,y_1)+(1+{\rho }_0){\lambda }_0(1,y_1).$$

The second round gives

$$\begin{array}{rl}{\lambda }_2=& {\rho }_0{\rho }_1{\lambda }_0(0,0)+(1+{\rho }_0){\rho }_1{\lambda }_0(1,0)\\ & +{\rho }_0(1+{\rho }_1){\lambda }_0(0,1)+(1+{\rho }_0)(1+{\rho }_1){\lambda }_0(1,1).\end{array}$$

Each original entry receives one factor from each folding round.

6.4 Dictionary with the standard multilinear extension

For a table $f:{\mathbb{B}}_m\to \mathbb{F}$, its standard multilinear extension is

$${\mathrm{MLE}}_f(t_0,\dots ,t_{m-1})=\sum _{y\in {\mathbb{B}}_m}f(y)\prod _{i=0}^{m-1}(1-t_i{)}^{1-y_i}{t}_i^{y_i}.$$

A direct substitution $t_i=1+{\rho }_i$ introduces a minus sign whenever $y_i=0$, because

$$1-(1+{\rho }_i)=-{\rho }_i.$$

Therefore the final folded scalar is not, in general, the standard multilinear extension of the unchanged table ${\lambda }_0$.

Define the signed table

$${\tilde{\lambda }}_0(y)=(-1{)}^{m-\mathrm{wt}(y)}{\lambda }_0(y),$$

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

$${\eta }_i=1+{\rho }_i.$$

Theorem 6.2 — Repeated folding as multilinear evaluation

The scalar obtained after all $m$ folding rounds satisfies

$${\lambda }_m={\mathrm{MLE}}_{{\tilde{\lambda }}_0}({\eta }_0,\dots ,{\eta }_{m-1}).$$

Proof

For a fixed $y\in {\mathbb{B}}_m$, the corresponding multilinear basis weight at ${\eta }_i=1+{\rho }_i$ is

$$\prod _{i=0}^{m-1}(1-{\eta }_i{)}^{1-y_i}{\eta }_i^{y_i}=(-1{)}^{m-\mathrm{wt}(y)}\prod _{i=0}^{m-1}{\rho }_i^{1-y_i}(1+{\rho }_i{)}^{y_i}.$$

Multiplying this by ${\tilde{\lambda }}_0(y)=(-1{)}^{m-\mathrm{wt}(y)}{\lambda }_0(y)$ cancels the sign. Summing over $y$ gives the closed repeated-fold formula. $\square$

The notation ${\eta }_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+{\rho }_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

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

multiplications and

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

additions.

More generally, the first $s$ rounds use

$$N\left(1-2^{-s}\right)$$

multiplications and

$$2N\left(1-2^{-s}\right)$$

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\le k\le m$, let $q=m-k$, and suppose ${\lambda }_0\in {\mathsf{CH}}_{m,k}$. By Chapter 4, there is a table $\mu :{\mathbb{B}}_k\to \mathbb{F}$ such that

$${\lambda }_0(x,h)=(-1{)}^{q-\mathrm{wt}(h)}{\mu }_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

$${\lambda }_k(h)=(-1{)}^{q-\mathrm{wt}(h)}{\mu }_{\ast },$$

where ${\mu }_{\ast }$ is the result of applying the first $k$ folds to the table $\mu$.

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

$$\rho (-c)+(1+\rho )c=c.$$

Consequently,

$${\lambda }_m={\mu }_{\ast },$$

and the final scalar is independent of the last $q$ challenges. This is an exact consequence of membership in ${\mathsf{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.