Arithmetization and the Sum-Check Protocol

Constants and variable leaves have their prescribed Boolean values by the recursive construction. This includes a constant formula on the singleton cube $\{0,1{\}}^0$.

For inputs $u=0,1$, $1-u$ gives respectively $1,0$. For input pairs $(0,0),(0,1),(1,0),(1,1)$, the product $uv$ gives $0,0,0,1$, and $u+v-uv$ gives $0,1,1,1$. These computations hold also in characteristic two.

Assume each immediate subformula has the correct value. The gate calculations then give the correct value for its parent. This proves the parent implication, including when its value is zero or one.

Starting at the leaves and applying the parent implication up the finite formula tree proves agreement for the whole formula, including formulas that are identically false or true.

For a constant leaf all degree bounds are zero; for a variable leaf the individual bound is one in that variable and zero otherwise, and the total bound is one. Each leaf needs no arithmetic operation.

Assume the bounds for the children. Subtracting a polynomial from $1$ does not raise any nonnegative degree bound. At a binary gate with child bounds $a,b$ (individual or total), the product has bound $a+b$ and the sum has bound $\max (a,b)\le a+b$. Thus AND and OR obey the sum of the child occurrence bounds, even if coefficients cancel or a child is zero.

Occurrence counts add over child trees, so the preceding leaf and parent argument proves all degree bounds by structural induction. A bottom-up evaluator visits each syntax node once and applies at most a fixed number of operations to its stored child values; the OR gate reuses those values. Hence its field-operation count is $O(s)$. This includes variable-free formulas and unused variables.

Each factor in ${\lambda }_b$ is $X_i$ when $b_i=1$ and $1-X_i$ when $b_i=0$. Hence ${\lambda }_b$ is multilinear. At a Boolean vector $c$, every factor equals one if $c=b$; if $c\mathrm{\ne }b$, a differing coordinate supplies a zero factor. Thus ${\lambda }_b(c)$ is one for $b=c$ and zero otherwise.

For uniqueness consider a multilinear polynomial $h$ vanishing at all Boolean vertices. In dimension zero it is a constant with value zero, hence is zero. For positive dimension assume the assertion in dimension $n-1$ and write $h=A+X_{n}B$ with $A,B$ multilinear in the other variables. Its restrictions $h_0=A$ and $h_1=A+B$ vanish on that smaller cube, so both are zero by the induction hypothesis.

The displayed finite sum is multilinear and takes value $f(c)$ at $c$. When $n=0$ it is the single constant $f(())$. In particular the zero table extends to zero and the constant-one table extends to one.

The formal identity $h=(1-X_n)h_0+X_n{h}_1$ gives $h=0$. Induction proves the vanishing assertion in every dimension; applying it to the difference of two extensions proves uniqueness. All identities used only field addition and multiplication, with $0\mathrm{\ne }1$, so characteristic two is included.

For each record compute $w_b={\prod }_i(b_i{r}_i+(1-b_i)(1-r_i))$ and add $f(b)w_b$ to an accumulator initially zero. The interpolation formula says that after all records the accumulator equals $\tilde{f}(r)$. This uses no divisions, even if a weight or table entry is zero.

Computing each weight costs $O(n)$ operations; multiplying by its table value and accumulating costs $O(1)$. There are $N$ records. Store $r$, the accumulator, the current value and one running product, using $n+O(1)=O(n)$ field elements since $n\ge 1$. Endpoints $r_i=0,1$ and $n=1$ require the same procedure. The work bound is exponential in $n$ and gives no polynomial-time evaluator from a succinct table specification.

Start with the one-entry array $W_0(())=1$. At stage $i$, replace each entry $W_{i-1}(b)$ by entries $W_i(b,0)=W_{i-1}(b)(1-r_i)$ and $W_i(b,1)=W_{i-1}(b)r_i$. After stage $i$ each entry is the product of the appropriate first $i$ factors, directly by this recurrence. This remains valid for zero or unit coordinates.

After stage $n$, return ${\sum }_{b}f(b)W_n(b)$. The weights equal the interpolation basis evaluated at $r$, so this is $\tilde{f}(r)$. Zero tables or zero weights need no separate treatment.

The weight construction costs $O({\sum }_{i=1}^n{2}^i)=O(2^n)$ operations, and the final weighted sum costs $O(2^n)$. Holding the table, two successive weight arrays and $r$ uses $O(2^n+n)$ storage. For $n=0$, return the sole table entry; for $n=1$, the construction returns $(1-r_1)f(0)+r_{1}f(1)$. The input still has $2^n$ values.

Substituting $0$ or $1$ for $X_i$ does not increase any exponent in another variable. Addition preserves the maximum of the remaining bounds and multiplication adds them. Thus the sum has bound $d_j$ and both expressions containing a product have bound $2d_j$, including when a restriction vanishes or $d_j=0$.

At any remaining Boolean assignment, put $u=p_0$ and $v=p_1$; by hypothesis $u,v\in \{0,1\}$. The AND and OR gate formulas give $uv$ and $u+v-uv$ as the universal and existential truth values. The sum instead gives $2$ when both inputs are one: in characteristic two this is zero, and in other characteristics it is not one. When $n=1$, these are simply operations on two constants.

Actual exponential growth is possible: start with $p=Y$ and eliminate $k$ other variables absent from $p$ using the product operator. Each elimination squares the current polynomial, leaving the formal polynomial $Y^{2^k}$. Hence degree growth is not merely a loose bound.

Use $q_i,S_i,C_i$ from the protocol. Substitution and finite summation cannot raise the degree in the unspecialized variable, so $q_i$ has degree at most $d_i$ and can be sent in the permitted coefficient format, including when $q_i=0$ or $d_i=0$.

Splitting the remaining cube by coordinate $i$ gives $q_i(0)+q_i(1)=S_{i-1}$, while substitution gives $q_i(r_i)=S_i$. Initially $C_0=H=S_0$. If $C_{i-1}=S_{i-1}$ and $h_i=q_i$, the consistency check passes and the update gives $C_i=S_i$. Hence this equality propagates through every round.

At the end $S_n=g(r_1,\dots ,r_n)$, since the remaining cube contains the empty tuple. Thus the terminal check passes. For $n=1$ the same argument uses $q_1=g$. It also covers all-zero or constant polynomials, challenges $0$ or $1$, and characteristic two without any division.

Let $q_i(T)$ be the true partial sum at the fixed prefix. Its degree is at most $d_i$ because specialization and addition preserve degree upper bounds, and $q_i(0)+q_i(1)=S_{i-1}$. Any well-formed consistent $h_i$ instead has $h_i(0)+h_i(1)=C_{i-1}\mathrm{\ne }{S}_{i-1}$, so $h_i-q_i$ is a nonzero formal polynomial of degree at most $d_i$. Messages failing these checks reject immediately.

A field is an integral domain, since $ab=0$ with $a\mathrm{\ne }0$ implies $b=a^{-1}ab=0$. Apply the root bound to $h_i-q_i$: it has at most $d_i$ roots in $F$. The next scalar is true precisely if $h_i(r_i)=q_i(r_i)$, because $S_i=q_i(r_i)$. The fresh $r_i$ is uniform even after conditioning on the fixed message, so this probability is at most $\min (1,d_i\mathrm{/}\mathrm{\mid }F\mathrm{\mid })$.

The bound holds for each allowed message, so averaging its conditional probability over any prover randomness preserves it. If $d_i=0$, the nonzero difference is constant and the probability is zero; if $d_i\ge \mathrm{\mid }F\mathrm{\mid }$, the cap at one is merely trivial. The argument includes $i=n$, $n=1$, characteristic two, and challenges $0,1$. A false updated claim need not be detected in this round; only its becoming true is the exceptional event bounded here.

Let $B_i$ be the event that the protocol reaches round $i$ with all earlier scalar claims false, passes that round’s message checks, and its updated scalar claim becomes true. For each positive-probability prefix with those earlier claims false, the one-round lemma bounds the conditional probability of this transition by $d_i\mathrm{/}\mathrm{\mid }F\mathrm{\mid }$. Averaging over prefixes (and messages) gives $\mathrm{Pr}(B_i)\le d_i\mathrm{/}\mathrm{\mid }F\mathrm{\mid }$.

Acceptance forces the final scalar claim to equal the trusted value $g(r)$, hence to be true. The initial claim is false. There is therefore a first transition from false to true, so acceptance is contained in ${\bigcup }_{i=1}^n{B}_i$. Pointwise, the indicator of this union is at most the sum of its event indicators; averaging gives acceptance probability at most ${\sum }_i{d}_i\mathrm{/}\mathrm{\mid }F\mathrm{\mid }$. This requires no independence between the $B_i$.

Probabilities are also at most one, giving the stated cap, and ${\sum }_i{d}_i\le nd$ gives the uniform-degree bound. The reasoning works for $n=1$ and for zero degree bounds (all-zero bounds force zero acceptance of a false claim). Randomized adaptive strategies were already covered by conditional averaging.

At round $i$ a well-formed coefficient list has at most $d_i+1$ entries. Under streaming reception, read at most $d_i+2$ field elements and reject immediately upon receiving the first excess coefficient; an explicit valid length prefix can make this detection cheaper. For a well-formed list, evaluate $h_i$ at $0,1,r_i$ by the recurrence $v\leftarrow Tv+a_j$ from highest coefficient downwards. Each evaluation costs $O(d_i+1)$ field operations, also for a zero or constant message.

Summing the per-round work for a well-formed transcript gives $O(D)$ operations and at most $D$ received field elements. If the first overlength message occurs in round $i$, the earlier rounds contribute at most ${\sum }_{j<i}(d_j+1)$ elements and that round contributes at most $d_i+2$, for a total at most $D+1$; other malformed messages stop no later. The protocol uses one fresh sample per completed round and sends at most one field element per round; the last need not be sent. It makes its only call to $g$ at the terminal comparison. Encoding checks and reading cost $O(Db)$, and arithmetic costs $O(DA(b))$; adding evaluation and sampling costs gives the stated bit bound. This includes $n=1$ and every zero bound $d_i=0$.

For indexed sampling put $c=\lceil {\log }_{2}q\rceil$. Draw $c$ fair bits as an integer $J$ and retry if $J\ge q$. The acceptance probability is $q\mathrm{/}{2}^c>1\mathrm{/}2$ (or one if $q$ is a power of two), and conditional on acceptance every valid index has probability $1\mathrm{/}q$. The expected number of trials is ${\sum }_{k\ge 0}(1-q\mathrm{/}{2}^c{)}^k=2^c\mathrm{/}q<2$. Thus expected random-bit use is less than $2c$ per sample; for $q=2^b$ every trial succeeds and exactly $nb$ bits suffice for all rounds. Efficient index conversion is part of the sampling assumption, not a consequence of arbitrary encodings.

The soundness theorem bounds the false-claim acceptance probability by $\min (1,{\sum }_i{d}_i\mathrm{/}\mathrm{\mid }F\mathrm{\mid })$.

Since $\mathrm{\mid }F\mathrm{\mid }>0$ and $\epsilon >0$, the size hypothesis implies ${\sum }_i{d}_i\mathrm{/}\mathrm{\mid }F\mathrm{\mid }\le \epsilon$. Combining gives the result, including ${\sum }_i{d}_i=0$ (zero error) and $\epsilon \ge 1$ (a possibly trivial guarantee). Equality in the field-size inequality is allowed.

Each satisfying Boolean input contributes $1_F$ and each other input contributes $0_F$ by Boolean agreement. Adding the $2^n$ values gives $M{1}_F$, including $M=0$ and $M=2^n$.

The formula degree lemma supplies the individual bounds $t_i$ and an $O(s)$ point evaluator. Since ${\sum }_i{t}_i\le s$, we have $D=n+{\sum }_i{t}_i\le n+s$; the verifier resource lemma therefore gives $O(s+n)$ field operations including that evaluator.

The soundness theorem gives the stated false-claim error bound with $d_i=t_i$. For a true claim the honest partial sums have these degree bounds, their values at $0,1$ sum to the preceding true value, and their value at each challenge is the next true value. Starting from $M{1}_F$, these identities propagate to the terminal value, so every honest execution accepts.

If $K=M$, their field images are equal, proving the reverse implication. Conversely, equality of the images in ${\mathbb{F}}_p$ implies $p$ divides $K-M$. As $\mathrm{\mid }K-M\mathrm{\mid }\le 2^n<p$, the only possible multiple is zero, so $K=M$. This includes both allowed endpoints for each count. In a field of characteristic $p$ the integer image depends on reduction modulo $p$, regardless of the field cardinality; for example a constant-one formula on one variable has count two and field sum zero in characteristic two.

From the definitions, ${\chi }_a{\chi }_b={\chi }_{a+b}$ and ${\chi }_a(x+y)={\chi }_a(x){\chi }_a(y)$. If $a=b$, their product is one everywhere. If $a\mathrm{\ne }b$, some coordinate $j$ of $a+b$ equals one. Pair $x$ with $x+e_j$: the pairing is a fixed-point-free involution and reverses the sign of ${\chi }_{a+b}$. Its sum is zero. This proves orthogonality.

For fixed $x,y$, sum ${\chi }_a(x){\chi }_a(y)={\chi }_a(x+y)$ over $a$. If $x=y$, this sum is $2^n$. Otherwise pair $a$ with $a+e_j$ at a nonzero coordinate of $x+y$ to get zero. Thus ${\sum }_a{\chi }_a(x){\chi }_a(y)=2^n{\mathbf{1}}_{x=y}$. Substituting the coefficient definition gives ${\sum }_a\widehat{h}(a){\chi }_a(x)=2^{-n}{\sum }_{y}h(y){\sum }_a{\chi }_a(y){\chi }_a(x)=h(x)$.

Expand both $h$ and $k$ by the preceding identity and average their product. All sums are finite, so rearrangement gives $\mathbb{E}hk={\sum }_{a,b}\widehat{h}(a)\widehat{k}(b)\mathbb{E}{\chi }_a{\chi }_b={\sum }_a\widehat{h}(a)\widehat{k}(a)$. Taking $k=h$ proves Parseval, also when either function is zero.

For $a\mathrm{\ne }b$, the character ${\chi }_{a+b}$ is one where ${\mathrm{\ell }}_a={\mathrm{\ell }}_b$ and minus one where they differ. Its zero mean therefore forces equal counts of agreement and disagreement. For $n=0$, there are no distinct indices; the sole character is one and every displayed Fourier identity is an equality of one-term sums. For $n=1$, the pairing interchanges the two cube points.

The product $h(x)h(y)h(x+y)$ is one exactly when $f(x)+f(y)+f(x+y)=0$ modulo two, and minus one otherwise. Thus its expectation is $\alpha -(1-\alpha )=2\alpha -1$, including $\alpha =0,1$.

Apply Fourier inversion to each of the three factors. The expectation of the resulting finite sum is ${\sum }_{a,b,c}\widehat{h}(a)\widehat{h}(b)\widehat{h}(c){\mathbb{E}}_{x,y}{\chi }_a(x){\chi }_b(y){\chi }_c(x+y)$.

Using ${\chi }_c(x+y)={\chi }_c(x){\chi }_c(y)$ and independence of $x,y$, each expectation factors as $({\mathbb{E}}_x{\chi }_a(x){\chi }_c(x))({\mathbb{E}}_y{\chi }_b(y){\chi }_c(y))$. Orthogonality makes this one exactly when $a=b=c$ and zero otherwise. The sum is therefore ${\sum }_a\widehat{h}(a{)}^3$, as asserted. This is also valid for $n=0$, where every sum has one term, and for constant $f$, where $h$ is the constant sign $1$ or $-1$.

Put $h=(-1{)}^f$ and $M={\max }_a\widehat{h}(a)$. The finite nonempty index set has $2^n$ elements, so a maximizing index exists. Parseval and $h^2=1$ give ${\sum }_a\widehat{h}(a{)}^2=1$. Hence ${\sum }_a\widehat{h}(a{)}^3\le M{\sum }_a\widehat{h}(a{)}^2=M$, since each coefficient is at most $M$ and every square is nonnegative. This is a signed maximum, not a maximum absolute value.

If $\alpha$ is the actual acceptance probability, the cubic identity gives $M\ge 2\alpha -1\ge 2\rho -1$. At a maximizing index $a$, $\widehat{h}(a)=\mathbb{E}(-1{)}^{f(x)+a\cdot x}=2\mathrm{Pr}[f(x)=a\cdot x]-1$. Therefore agreement is at least $\rho$. Substituting $\rho =1-\epsilon$ proves the rejection formulation; conversely setting $\epsilon =1-\rho$ in that formulation gives the agreement formulation. These are equivalent parametrizations of a guarantee, not a claim that distance determines acceptance exactly.

For $f={\mathrm{\ell }}_a$, distributivity modulo two gives ${\mathrm{\ell }}_a(x)+{\mathrm{\ell }}_a(y)={\mathrm{\ell }}_a(x+y)$ for every pair, so completeness is perfect. This includes $a=0$ and the sole linear function in dimension zero. At $\rho =1$ or $\epsilon =0$, the guarantee in the previous step likewise gives exact agreement.

If $f$ is farther than $\delta$ from every linear function, its acceptance probability cannot exceed $1-\delta$: otherwise it is greater than $1\mathrm{/}2$, and step 2.1 applied with $\rho =\alpha$ would give distance at most $1-\alpha <\delta$. Independent trials of a fixed function have all-accept probability ${\alpha }^k\le (1-\delta {)}^k$. Taking complements proves the repetition bound. For $k=0$ the always-accept empty repetition has rejection probability zero, equal to the bound; for $k=1$ this is the single-test bound.

If another linear function $m\mathrm{\ne }\mathrm{\ell }$ had distance less than $1\mathrm{/}4$ from $f$, each point where $\mathrm{\ell }\mathrm{\ne }m$ would be a disagreement of at least one of them with $f$. Counting these points gives $\mathrm{dist}(\mathrm{\ell },m)\le \mathrm{dist}(\mathrm{\ell },f)+\mathrm{dist}(f,m)<1\mathrm{/}2$, contradicting their exact half-distance. Thus the nearby linear function is unique.

Let $E=\{z:f(z)\mathrm{\ne }\mathrm{\ell }(z)\}$, of size $\delta 2^n$. For fixed $x$, both $y$ and $x+y$ are uniform, since translation is a bijection. Thus each event $y\in E$, $x+y\in E$ has probability $\delta$. The indicator of their union is at most their indicator sum, so with probability at least $1-2\delta$ neither event occurs. Independence of these two locations is unnecessary.

On that event the output is $\mathrm{\ell }(y)+\mathrm{\ell }(x+y)=\mathrm{\ell }(x)$ by linearity. The sampling and calls are exactly those of the corrector. For $x=0$, the two queried values are identical and their sum is always zero, which equals $\mathrm{\ell }(0)$. For $n=0$, the hypothesis forces $\delta =0$ on the singleton cube; the same algorithm uses zero random bits. Zero noise gives success one for every point; the excluded endpoint $\delta =1\mathrm{/}4$ would give only the lower bound one half.

The protocol performs coefficient checks and evaluations of the received univariate messages; its only trusted evaluation of $g$ is at the final challenge vector. The resource bound is $O(D)$ field operations plus that single evaluation, for a complete execution.

For a concrete family take $g={\prod }_{i=1}^n{X}_i$, $n\ge 1$, and $d_i=1$. A trusted evaluator starts at one and multiplies the $n$ coordinates, so it costs at most $n$ multiplications. Since $D=2n$, verifier work is $O(n)$, with one evaluation of $g$, not separate evaluations at the $2^n>1$ vertices. The cube sum is one because only the all-one vertex contributes; this includes n=1 and fields of characteristic two. This refutes the asserted necessity. The prover and the trusted evaluator in other instances may have much larger costs.