Arithmetization and the Sum-Check Protocol: Examples and Counterexamples

The interpolation formula gives $(1-X)(1-Y)+2(1-X)Y+X(1-Y)+4XY$. Expanding and combining coefficients yields $1+Y+2XY$, which has degree at most one in each variable.

Its values at $(0,0),(0,1),(1,0),(1,1)$ are respectively $1,2,1,4$, so it agrees with the table; uniqueness follows from the interpolation theorem. At $(2,3)$ its integer expression is $1+3+2\cdot 2\cdot 3=16$, which reduces to one modulo five.

Sum $g$ over Boolean $Y,Z$ to obtain $q_1(X)=8X^3+2X+1$. Then $q_1(0)+q_1(1)=1+11=12$ and $q_1(2)=64+4+1=69$. This also computes the cube sum by splitting over $X$.

After $r_1=2$, sum $g(2,Y,Z)$ over $Z=0,1$: $q_2(Y)=16+(16+2+Y)=34+Y$. Its endpoint sum is $34+35=69$, and its value at $r_2=3$ is $37$.

With that prefix $q_3(Z)=g(2,3,Z)=16+5Z$. Its endpoint sum is $16+21=37$. At $r_3=6$ its value is $46$, also $g(2,3,6)=16+12+18=46$. The coefficient lists have lengths $4,2,2$ and the degrees meet $(3,1,1)$, so all checks pass modulo 101.

For any false initial claim the soundness theorem applies to the fixed polynomial and trusted degree bounds, giving error at most $(3+1+1)\mathrm{/}101=5\mathrm{/}101$ over fresh independent challenges. It asserts this for all adaptive provers, separately from the honest transcript just computed.

There are eight cube points, with precisely the zero point corrupted, so $\delta =1\mathrm{/}8<1\mathrm{/}4$. The self-correction theorem gives a unique nearby linear function and success at least $1-2\delta =3\mathrm{/}4$ at each point.

For fixed $x\mathrm{\ne }0$, the query $y$ is corrupted exactly when $y=0$, and the query $x+y$ is corrupted exactly when $y=x$. These are distinct seeds. At either seed exactly one summand is flipped, so the output is wrong; at the other six seeds neither is flipped and linearity gives the right answer. At $x=0$, the sum $f(y)+f(y)$ is zero for every seed, equal to $\mathrm{\ell }(0)$. Thus the lower bound is attained for nonzero requests and exceeded for the zero request.

At the all-one vertex the product equals one, and at every other Boolean vertex a zero coordinate makes it zero. Hence the cube sum is one. There are two independent choices per coordinate, giving $2^n$ vertices, also when $n=1$.

The specified protocol uses one terminal evaluation. Implement it by multiplying the $n$ supplied coordinates starting from one, at a cost of at most $n$ multiplications. Here $D={\sum }_i(1+1)=2n$, so the resource lemma bounds all verifier field work, including this evaluation, by $O(n)$. Zeros among the challenge coordinates simply make the product zero, without any division.

The soundness theorem gives the stated false-claim bound from ${\sum }_i{d}_i=n$, including the cap at one when the field is small. Thus the verifier does not need $2^n$ separate evaluations of $g$. The claim concerns verifier work with a supplied evaluator and imposes no general efficiency assertion on the prover.