The Geometry of the Sumcheck Protocol: Shadows, Chords, and the Secant That Makes a Protocol Necessary

Sumcheck is normally met as a sequence of algebraic manipulations that somehow amount to a proof. You are shown a univariate polynomial per round, two evaluation checks, a random challenge, and a final query, and the induction closes. It is correct and it is unilluminating, and the reason it is unilluminating is that the algebra hides a geometry which is almost entirely elementary: one surface, some lines drawn on it, some lines drawn above it, and a rigidity theorem about how two surfaces pinned through the same lattice points must pull apart everywhere else.

Two functions carry the entire exposition. The first,

f(x₁, x₂) = 2x₁² + 3x₂ + x₁x₂,

is quadratic in one variable and affine in the other. The second,

f₂(x₁, x₂) = 2x₁ + 3x₂ + x₁x₂,

is multilinear — degree one in each variable separately — and is built to agree with f on all four vertices of the Boolean square. Same corner values, same sum, wildly different behaviour off the cube. That contrast is the engine of everything below.

The quantity the protocol certifies is that bottom row: H = 11, the sum of f over {0,1}². A verifier who could simply add four numbers would not need a protocol; the point is to reach the same certainty while evaluating f at exactly one unpredictable point. Throughout, F is the field, q = |F|, and we assume char F ≠ 2 except where characteristic two is the subject — it turns out to be geometrically interesting in its own right (§7).

1 · The object in space, and what the protocol is allowed to touch

Before any protocol, look at the object. Over the reals, f is a saddle, not a bowl. Its Hessian is constant,

Hess f = [[4, 1], [1, 0]],    det = −1 < 0,

and a negative determinant forces one positive and one negative eigenvalue (4.236… and −0.236…). The surface curves up along one direction and down along another everywhere. Setting the gradient to zero gives 4x₁ + x₂ = 0 and x₁ + 3 = 0, so there is a single critical point at (−3, 12) with f = 18 — the warm dot in the box below.

drag to rotate

Tilt

Spin

Window±6

Two features to carry forward. Along x₂ alone the function is affine — ∂f/∂x₂ = 3 + x₁ does not depend on x₂ — so every section at fixed x₁ is a straight line, and the contours are parabolas rather than closed ellipses. The sign of that slope flips at x₁ = −3: to the right, raising x₂ lifts f; to the left it lowers it. That flip is exactly what makes the critical point a saddle.

Now the constraint that governs the entire protocol, and which is easy to lose sight of in the algebra. Sumcheck may only move along coordinate directions. Its rounds fix variables one at a time and leave exactly one free; the free axis is always an axis of the ambient coordinate system, never a diagonal. Every geometric object the protocol can name — every round polynomial, every check, every challenge point — is built from axis-parallel lines through the domain. Much of what looks like arbitrary bookkeeping is the cost of that restriction, and §5 shows a case where the surface has a perfectly good straight line through every point that the protocol is nonetheless forbidden to use.

2 · What a round polynomial is: restrict, then integrate the fibre

For f in v variables, the round-i polynomial is

g_i(X) = Σ_{(xi+1, …, xv) ∈ {0,1}^v−i}  f(r₁, …, r_i−1, X, x_i+1, …, x_v).

Every variable is in exactly one of three states, and each round moves one variable from summed to frozen. Variables before i are frozen at past challenges — field elements, generically not in {0,1}. Variable i is left symbolic; that is what makes g_i a polynomial rather than a number. Variables after i are still summed over the Boolean cube.

Stated functorially, which is worth doing once because it makes the shadow/slice distinction of §4 a triviality: let ι be the inclusion of the affine line {(r₁, …, r_i−1, X, y) : X ∈ F, y ∈ F^v−i} — really the inclusion of an (v−i+1)-plane — and let π be the projection of that plane onto its first coordinate. Then

g_i = π_∗(ι^∗f),restrict, then push forward along the fibre

where the pushforward integrates against the counting measure on {0,1}^v−i. So g_i is not a factor or a term of f. It is f itself, with some coordinates collapsed by summation and others pinned to points, leaving a single free axis. That is why it is univariate, and why the verifier can check it in a handful of field operations: its degree is the individual degree of that one variable, never anything like 2^v. That is the entire source of the compression, and it is worth being blunt that the compression is degree-driven, not sum-driven.

the two rounds at a glance

x₁

x₂

claimed

start

summed over {0,1}

summed over {0,1}

H = 11

round 1

X — free

summed over {0,1}

g₁(X) = 4X² + X + 3degree 2

r₁ = 4

frozen at 4

summed over {0,1}

g₁(4) = 71new claim

round 2

frozen at 4

X — free

g₂(X) = 32 + 7Xdegree 1

r₂ = 7

frozen at 4

frozen at 7

g₂(7) = 81check against f(4, 7)

summed away symbolic — this round's variable pinned to a challenge

3 · The protocol, with numbers you can check by hand

We run the honest protocol on f with H = 11, choosing challenges (r₁ = 4, r₂ = 7) that keep every intermediate a small integer so nothing hides inside a modular reduction. Read the challenges as elements of a large prime field that happen to be small integers; nothing depends on their smallness.

Round 1

The prover sums out x₂ while holding x₁ symbolic:

f(X, 0) = 2X² + 3·0 + X·0  =  2X²
f(X, 1) = 2X² + 3·1 + X·1  =  2X² + X + 3
--------------------------------------------
g₁(X)   =                     4X² + X + 3

Prover → Verifier: the coefficients (4, 1, 3), or equivalently three evaluations g₁(0) = 3, g₁(1) = 8, g₁(2) = 21 — either determines a degree-2 polynomial. (In practice one sends two, not three: the verifier's own check supplies the missing datum. §9 makes that precise.)

Verifier checks g₁(0) + g₁(1) = 3 + 8 = 11 = H ✓. Notice what this check is: g₁(0) = f(0,0) + f(0,1) and g₁(1) = f(1,0) + f(1,1), so their sum reassembles the four-corner total. Round 1 sums each column of the 2×2 table; the check sums the columns. The verifier never sees the four values, yet their total is pinned.

Verifier → Prover: random challenge r₁ = 4, producing a new claim g₁(4) = 4·16 + 4 + 3 = 71. Both parties now believe “Σ_x2 f(4, x₂) = 71” — a one-dimensional sum, with x₁ pinned to a point that is not a cube vertex.

Round 2

Nothing is left to sum, so g₂ is a plain restriction:

g₂(X) = f(4, X) = 2·4² + 3X + 4X = 32 + 7X

Verifier checks g₂(0) + g₂(1) = 32 + 39 = 71 = g₁(4) ✓, then sends r₂ = 7, giving g₂(7) = 32 + 49 = 81.

The final check

Nothing so far ties any of this to f: the checks link each round only to the one before. The verifier closes the loop by evaluating f once, itself:

f(4, 7) = 2·16 + 3·7 + 4·7 = 32 + 21 + 28 = 81 = g₂(7) ✓   Accept.

Total verifier work: two additions, two univariate evaluations, one evaluation of f. It never touched the hypercube. What actually happened is a controlled collapse in how many points the claim is about:

4 · Shadow and slice — and the chord that unifies them

The two round polynomials feel arbitrary until you see that they are two geometrically different objects living in the same picture. One is a shadow. The other is a slice.

drag to rotate

rails on the surface — f(x₁,0) and f(x₁,1) g₁ — their sum, floating off the surface g₂ — a cut through the surface at x₁ = 4 a ruling the protocol cannot use (§5)

Tilt

Spin

show the forbidden ruling

g₁ is a shadow, not a slice

The cube's x₂ values, 0 and 1, pick out two parallel lines in the domain. Above each, the surface carves a curve — the two rails f(x₁,0) = 2x₁² and f(x₁,1) = 2x₁² + x₁ + 3. Then g₁ is their pointwise sum, 4x₁² + x₁ + 3: at every x₁ you stack the two heights. That dashed curve lives above the surface, touching nothing. There is no x₂ making f(x₁, x₂) = g₁(x₁) identically, because the required x₂ = (2x₁² + x₁ + 3)/(x₁ + 3) is not constant.

The precise word is marginal — exactly as in summing a joint distribution over one variable: one axis is collapsed by summation, the other stays continuous. And the round-1 check now reads geometrically: the two lattice points on the free axis are x₁ ∈ {0,1}, and g₁(0) + g₁(1) = 3 + 8 = 11 stacks the column sums back into the grand total.

g₂ is a genuine slice

Choosing r₁ = 4 picks the line x₁ = 4 in the domain, and g₂ is f restricted to it — a curve carved directly on the surface. Every point of it is a point of f. Watch where the two rail heights 32 and 39 sit: they are f(4,0) and f(4,1), whose sum is g₁(4) = 71. The slice passes exactly through them, so the check g₂(0) + g₂(1) = 71 is literally re-adding the two heights that made the previous claim.

The chord: one reading of the check that survives every degree

Now the reformulation that the rest of this article runs on. Take any round polynomial g, of any degree, and any claimed value C. The verifier's check is g(0) + g(1) = C. Divide by two and read it as a statement about a line:

g(0) + g(1) = C   ⟺   the chord joining (0, g(0)) to (1, g(1)) has midpoint (½, C/2).

That is trivially true and unusually productive. The sum-check does not test the curve; it tests the chord of the curve over the unit edge, and it tests exactly one point of that chord — its midpoint. Everything else about g is unconstrained by the check.

Two consequences worth separating. First, when g is affine, the chord is the curve, and the check becomes “the curve passes through (½, C/2)” — a condition on g itself, visible as a single pinned point. That is the multilinear world of §5–§6, and it is why the pictures there are so clean. Second, when deg g ≥ 2, the chord is a genuinely different object from the curve: the curve may pass anywhere at x = ½, and the gap between the chord's midpoint and the curve's own value there is a quantity we will meet again in §7, where it turns out to be a variance. Concretely for our g₁ = 4X² + X + 3: chord midpoint (½, 5.5), curve value g₁(½) = 4.5, gap exactly 1 — which is the leading coefficient 4 times ¼.

So the answer to “what does the verifier actually learn each round?” is: one point of one chord. It learns nothing else, ever. The entire soundness of the protocol has to be manufactured from that, plus the order in which the prover and verifier speak.

5 · The multilinear case: coordinate rulings, and a correction

Now run the identical protocol — same challenges (r₁ = 4, r₂ = 7) — on f₂ = 2x₁ + 3x₂ + x₁x₂, the multilinear extension of the same four corner values. Every number is directly comparable to §3.

f₂(X, 0) = 2X + 0 + 0   =  2X
f₂(X, 1) = 2X + 3 + X   =  3X + 3
------------------------------------
g₁(X)    =                 5X + 3        check: 3 + 8 = 11 ✓   r₁=4 → g₁(4) = 23

g₂(X) = f₂(4, X) = 8 + 3X + 4X = 8 + 7X   check: 8 + 15 = 23 ✓   r₂=7 → g₂(7) = 57

final:  f₂(4, 7) = 8 + 21 + 28 = 57 = g₂(7)  ✓  Accept.

drag to rotate

rails f₂(x₁,0), f₂(x₁,1) — now straight g₁ = 5x₁ + 3 — straight, off the surface g₂ — now a ruling of the surface

Tilt

Spin

1 · The correction: both surfaces are doubly ruled

It is often said — and it is the natural thing to say — that the quadratic f is a “singly ruled” surface while the multilinear f₂ is “doubly ruled,” and that multilinearity is what buys the second family of lines. That is false, and the way in which it is false is the most useful geometric fact in this section.

Homogenise the graph of f in P³ — multiply z/w − f(x/w, y/w) by w² — to get the quadric 2x² + xy + 3yw − zw = 0. Its Gram matrix has determinant +1/16 ≠ 0, so the closure is a smooth quadric; and its eigenvalues are ≈ 2.218, 1.408, −0.012, −1.613, so the signature is (2,2). f₂'s closure, xy + 2xw + 3yw − zw = 0, has the same determinant and the same signature (2,2) — as does the Segre form xy − zw, so by Sylvester's law both are projectively equivalent to P¹ × P¹ over the reals, not merely over C. Both surfaces are doubly ruled. Nothing about multilinearity creates a second ruling.

You can write f's second family down. Through the point (p, q, f(p,q)) there are exactly two lines lying in the surface:

direction (0, 1, 3 + p)the coordinate ruling x₁ = p; note 3 + p = ∂f/∂x₂

direction (1, −2, 2p + q − 6)the ruling the protocol may not use

“Exactly two” is a one-line computation: substituting (p+tu, q+tv) leaves a t²-coefficient of u(2u+v), which has precisely two projective roots — the two factors of the top form again — after which the height slope is forced. The second family is the family of plane sections 2x₁ + x₂ = c, on which f becomes the affine function 3c + (c−6)x₁. You can check one instance by hand: f(t, 8 − 2t) = 2t² + 3(8 − 2t) + t(8 − 2t) = 24 + 2t, dead straight, running from (0, 8, 24) to (4, 0, 32) across the surface. That is the green line in the widget of §4.

2 · Every axis-parallel curve straightens, and that is the cost saving

f was affine in x₂ but quadratic in x₁, so only one family of axis-parallel sections was straight and the rails were parabolas. f₂ has no square terms at all — the only nonlinear piece is the bilinear x₁x₂ — so every axis-parallel section in both directions is straight. Substituting u = x₁ + 3, w = x₂ + 2 gives f₂ = uw − 6: the textbook hyperbolic paraboloid, in coordinates that are still axis-parallel.

Round 1's message drops from three field elements to two, and the soundness error from 3/q to 2/q. Two elements per round is the floor — a nonconstant polynomial needs at least two points to pin down — and this is exactly why GKR and its descendants arithmetise everything into multilinear extensions: multilinearity is the degree-minimal representation of a table of values.

3 · g₁ is still a shadow, but a rigid translate of a mid-edge ruling

Whenever the summed variable enters affinely, the two-point sum is a midpoint evaluation:

g₁(X) = f(X, 0) + f(X, 1) = 2 · f(X, ½).

So g₁ is the mid-edge section f₂(X, ½) = 2.5X + 1.5, scaled by 2 — a ruling of the surface, lifted off the ground plane by a factor. For f₂ this holds in every round and for every variable order; that is precisely what multilinearity guarantees. For f it happens to hold in round 1, because f is affine in the variable being summed — and it breaks the moment you reverse the order: Σ_x1∈{0,1} f(x₁, X) = 2 + 7X, whereas 2·f(½, X) = 1 + 7X. The identity is not about the protocol; it is about the degree in the variable you happen to be eliminating.

4 · Two surfaces through the same four points, peeling apart off the cube

Their difference is

f − f₂ = 2x₁² − 2x₁ = 2x₁(x₁ − 1),

which vanishes exactly when x₁ ∈ {0, 1}. The two surfaces do not merely touch at the four corners — they coincide along two entire coordinate rulings, the full lines x₁ = 0 and x₁ = 1 — and then separate quadratically the instant x₁ leaves that strip. At x₁ = 4 the gap is 2·16 − 2·4 = 24 per rail, hence 48 between the two shadows: g₁(4) = 71 against 23. Same H, identical in-round checks at 0 and 1, wildly different the instant the verifier steps off the cube.

The general statement is the reason this matters. The set of polynomials with a prescribed restriction to {0,1}^v is a coset of the vanishing ideal I({0,1}^v) = ⟨x₁² − x₁, …, x_v² − x_v⟩ — the cube is a complete intersection of v quadrics — and here f − f₂ = 2(x₁² − x₁) is a generator times a constant, which is why the agreement locus is as large as two whole lines rather than just four points. A prover choosing which coset representative to commit to is choosing the protocol's entire off-cube behaviour.

5 · The saddle relocates and becomes symmetric

f's critical point was (−3, 12, 18) with Hessian [[4,1],[1,0]] — eigenvalues 4.236… and −0.236…, a lopsided saddle nearly flat in one direction. f₂'s is (−3, −2, −6) with Hessian [[0,1],[1,0]] — eigenvalues exactly ±1, principal directions at 45° to the axes. A perfectly balanced saddle, and the balance is not cosmetic: a multilinear polynomial in two variables has zero diagonal Hessian entries by definition, so whenever its bilinear coefficient is nonzero the principal curvature directions are the two diagonals, never the axes. The axes are where the surface is flat. That is the same fact as “the coordinate sections are lines,” read in differential rather than algebraic language.

6 · Canonicity: the multilinear extension is a normal form

f₂ is the unique multilinear polynomial through those four values; f is one of infinitely many polynomials through them. The clean way to say it: {x_i² − x_i} is a universal Gröbner basis of I({0,1}^v) — its leading terms x_i² are pairwise coprime, so Buchberger's first criterion kills every S-pair under every monomial order^[21] — so reduction modulo it terminates in the multilinear monomials, and the multilinear extension is exactly the normal form of the coset. The ideal is moreover the full radical vanishing ideal of the cube over any field, characteristic two included: the 2^v × 2^v matrix evaluating squarefree monomials at cube points is unitriangular, so dim k[x]/I = 2^v = #points. That is what makes “the MLE of a table” a well-defined object you can commit to, and why the protocol's off-cube behaviour becomes determinate rather than something the prover gets to choose.

6 · The barycentre walk: what an honest transcript actually is

Everything so far has been about single rounds. Now assemble them, in the multilinear case, and something unexpectedly rigid falls out — a closed form for the entire honest transcript that we have not seen written down, and which turns the protocol into a picture you can point at.

Start from §5.3 and iterate it. If f is multilinear in v variables, then summing over any set of variables is the same as evaluating at ½ in each of them, times 2 per variable. Applied to the round-i polynomial, where v − i variables are still being summed:

Read the second display as a list of points, not numbers. The honest transcript is the sequence of values of f at

(½, ½, …, ½) → (r₁, ½, …, ½) → (r₁, r₂, ½, …, ½) → ⋯ → (r₁, …, r_v),

Call these points P₀, …, P_v. Consecutive ones differ in exactly one coordinate, so they form an axis-parallel path from the barycentre of the Boolean cube to the challenge point, releasing one coordinate per round; and the round polynomial g_i is, up to the factor 2^v−i, exactly f restricted to the whole line through P_i−1 in direction e_i — with P_i−1 at parameter X = ½ and P_i at X = r_i. So:

Note precisely what has and has not become a continuity condition. The domain path is automatic: line i passes through P_i−1 by construction, whatever the prover sends. What the check tests is the height — that the lift is continuous over the joint. So the intermediate rounds read: the prover asserts a lifted path; the verifier checks the joints; the graph of f is consulted once, at the far end. A cheating prover proposes a lift whose joints agree with each other but whose first vertex sits at the wrong height, and must commit to each piece before learning where the next joint will be. That last clause is the intuition, not the proof — the actual argument is §8, and it needs the randomness of r_i, which the path picture is silent about.

drag to rotate · move the challenges

the Boolean cube {0,1}³, corner values marked barycentre (½,½,½) the walk, one coordinate released per round

r₁1.45

r₂−0.35

r₃1.60

Tilt

Spin

H = Σ over {0,1}³

23

barycentre value c₀ = H/8

2.875

final claim C₃ = g₃(r₃)

—

oracle answer f(r₁,r₂,r₃)

—

Order matters for the path; not for its ends

Nothing forces the coordinates to be released in the order 1, 2, …, v. Any permutation gives a valid protocol, and the Proposition holds verbatim with the coordinates renamed. Different orders trace different paths between the same two endpoints: the barycentre and (r₁, …, r_v). There are v! such routes — axis-parallel staircases that change each coordinate exactly once — and the sumcheck's variable order chooses one of them. Soundness is order-independent; prover cost is not, which is why real systems care about the order in which they bind variables.

The corollary that should be unsettling

Set i = 0 in the Proposition and read it as an identity rather than a step of a protocol:

H = Σ_{x ∈ {0,1}^v} f(x) = 2^v · f(½, …, ½)   multilinear f, char ≠ 2

Check it on our example: 4 · f₂(½, ½) = 4 · 2.75 = 11 ✓, while for the quadratic f it fails outright, 4 · f(½,½) = 9 ≠ 11. So if f is multilinear and the verifier has oracle access to it, the sumcheck protocol is unnecessary: one deterministic query at the barycentre settles H exactly, with zero soundness error and zero interaction.

The identity is not special to {0,1} or to 2. Over any product domain S^v and any multilinear f,

Σ_{x ∈ S^v} f(x) = |S|^v · f(μ, …, μ),  μ = mean of S,whenever char F ∤ |S|

and the obstruction is char | |S|, not characteristic two as such. A converse is provable and worth stating because it is what §7 will make geometric: the system c · z^j = Σ_x∈S x^j for all j ≤ d is solvable only at d = 1, where c = |S| and z = μ.

None of this is a defect in the protocol; it is a precise localisation of what the protocol is for. Sumcheck is never actually run on a bare multilinear polynomial. It is run where the barycentre identity fails — on products of multilinear extensions (GKR's layer relation, Spartan's A·B − C), on higher-degree custom gates, on lookup arguments. Already in one variable: Σ_x∈{0,1} x² = 1, while 2 · (½)² = ½.

The rest of the interaction exists to cover the gap between summation and evaluation that opens as soon as the sum functional stops being an evaluation. The next section measures that gap and finds it has a name.

7 · Why a protocol is necessary at all: the sum functional is a secant

Fix a degree bound d and let V_d be the space of univariate polynomials of degree ≤ d, a vector space of dimension d + 1. On it live two linear functionals the protocol cares about:

S(g) = g(0) + g(1)    and    E_t(g) = g(t).

The question that decides whether a protocol is needed is embarrassingly simple to state: is S a scalar multiple of some E_t? If yes, summation over the Boolean edge is evaluation somewhere, and a verifier with an oracle needs no interaction. If no, summation is a strictly richer functional, and the gap between them is what the round message has to pay for.

Moments, and the answer

Normalise both to unit mass and read them as measures: the Boolean sum is 2μ where μ = ½(δ₀ + δ₁), and E_t is δ_t. A linear functional given by a measure acts on V_d through exactly its first d moments, so two measures induce the same functional on V_d if and only if their moments agree up to order d. Line them up:

The first moment can be matched, and only by t = ½. The second cannot be matched at all, and the size of the failure is

m₂ − m₁² = ½ − ¼ = ¼ = Var(μ).the whole obstruction, in one number

The projective statement: a rational normal curve and its secant

The same fact has a classical name, and the name is worth having because it puts the protocol's two cost parameters — message size and soundness error — into one picture.

Coordinatise the dual space V_d^∗ by the coefficient basis, so that E_t ↦ (1, t, t², …, t^d). As t ranges over the field, that traces the rational normal curve C_d ⊂ P(V_d^∗) — the moment curve, of degree d, closed up by the point at infinity (0, …, 0, 1). And

S = E₀ + E₁ ↦ (2, 1, 1, …, 1).

Is that on the curve? It would need λ = 2, λt = 1, and λt^k = 1 for every k ≤ d — so t = ½ from the second condition and t² = ½ from the third. For d = 1 the third condition is absent and S = 2E_½. For d ≥ 2 the two conditions give 1 = 2, which is false in every field — characteristic 3 included — and no field extension can rescue it. But S is visibly on the line joining E₀ to E₁, so:

S lies on the secant variety of C_d, off the curve itself, for every d ≥ 2.

Its C_d-rank — the least number of evaluation functionals whose linear combination is S — is therefore exactly 2. Three points of care, because this is where a specialist will push. First, say C_d-rank and not Waring or symmetric rank: E_t corresponds to a d-th power of a linear form only after rescaling by binomial coefficients, so the two notions coincide only when no binom(d,i) vanishes in F — in characteristic 2 with d = 2 the locus of squares is not C₂ at all — and the lower bound worth citing is the symmetric-tensor one.^[16] Second, the statement needs d ≥ 1, and at d = 1 “on the curve” is vacuous, since C₁ is the whole of P(V₁^∗). The formulation that carries the content is the one we started from: S is proportional to some evaluation functional E_t — with t in F or in any extension — if and only if d ≤ 1 and char F ≠ 2.

Third, and this one is a small delight rather than a caveat: at d = 2 the representation by two evaluations is not unique, because the secant variety of a conic in P² fills the plane. The Boolean sum can be computed by two-point quadratures having nothing to do with {0,1} —

g(0) + g(1) = ⅕ g(−1) + ⁹⁄₅ g(⅔)for every g with deg g ≤ 2

— which you can verify on 1, X, X² in three lines. There is a one-parameter family of such rewritings, and it collapses at d ≥ 3, where {0,1} becomes the unique two-node representation. So the Boolean cube is not distinguished among two-point quadratures until degree three.

Now the cost structure, stated so as not to conflate two different things. The rank of S is 2 for every d ≥ 2: it is two evaluations, exactly and minimally, and the verifier reads only three numbers per round — g(0), g(1), g(r) — whatever d is. The d + 1 field elements of a round message come from somewhere else entirely: the verifier must evaluate an unknown polynomial at a point of its own choosing, and pinning down an unknown element of a (d+1)-dimensional space takes d + 1 numbers, one of which its own check supplies (§9). Rank governs whether a protocol is needed at all; dimension governs how wide each round message is. Meanwhile the soundness error takes on a purely geometric reading:

move the summation nodes and the curvature

node a0.00

node b1.00

curvature α4.0

mean of the two nodes

0.500

variance (b−a)²/4

0.250

chord midpoint − g(mean)

1.000

α × variance

1.000

Characteristic two, where the barycentre runs off to infinity

The clean statement S = 2E_½ uses ½, so it has something to say about small-characteristic fields — a live concern, since proving over F_2^k and its towers is exactly where much recent work sits.^[10] In characteristic 2 there is no ½, and the geometry adjusts in a way that is more interesting than “the formula breaks”: for g = a₁X + a₀,

g(0) + g(1) = a₀ + (a₀ + a₁) = a₁,

so S becomes the leading-coefficient functional — which is the point at infinity of the curve C₁. Summation is still a single evaluation in the degree-1 case, but the point being evaluated at has left the affine line: the barycentre of the Boolean edge sits at infinity rather than at ½. For d ≥ 2 in characteristic 2, S ↦ (0, 1, 1, …, 1) is neither on the affine curve nor its point at infinity, and the secant story returns unchanged.

8 · Soundness as geometry: the liar's hyperplane

The natural worry about sumcheck is that one random challenge per round is flimsy. If you picture the proof as accumulating evidence forward — each check adding a little confidence — one point looks like far too little. The checks accumulate nothing, and it is worth seeing exactly how little they do.

Fix the round. The prover's message lives in V_d ≅ F^d+1. The verifier's check “g(0) + g(1) = C” is one inhomogeneous linear condition, so it cuts out an affine hyperplane of codimension 1. If the standing claim C′ is false, the true round polynomial g is not on the liar's hyperplane, and the liar must choose some ĝ that is. The differences then range over

D = ĝ − g ∈ { D ∈ V_d : D(0) + D(1) = Δ },   Δ = C′ − C ≠ 0,

an affine hyperplane that misses the origin. That is the entire content of the round lemma: the liar's difference can be anything except zero, because zero does not satisfy the constraint. A nonzero element of V_d has at most d roots, so at most d challenges escape detection — and in fact at most min(d, q−1), because D cannot vanish on all of F either: that would force (X^q − X) | D and hence Δ = 0. The worst-case per-round error is min(d, q−1)/q, which is the familiar d/q exactly when d ≤ q−1. Note also that the whole distribution of escape counts depends only on (q, d) — not on the true polynomial and not on the size of the lie — since D ranges over one coset and scaling D preserves its roots.

What the liar actually gets to choose

Parameterise the difference by its roots rather than its coefficients, and the adversary's real freedom becomes visible. For d = 2, put D = α(X − ρ₁)(X − ρ₂) and solve the constraint for α:

α = Δ / [ ρ₁ρ₂ + (1 − ρ₁)(1 − ρ₂) ].

So the liar names the two challenges it wants to survive and the sum-check constraint fixes the rest of the lie. There is one forbidden choice, and it is the interesting one: the denominator vanishes precisely when the two planted roots are {0, 1} themselves, in which case no α works at all. In slogan form: a liar may plant its escapes anywhere in the field except at the two points the verifier checks. The same computation at d = 1 gives D = α(X − ρ) with α = Δ/(1 − 2ρ), forbidden exactly at ρ = ½ — and ½ is the barycentre, the point where §7 told us summation is evaluation. The two facts are the same fact.

The d = 1 case is worth describing exactly, because its liar family is completely concrete and the description is easy to get wrong. Since h(0) + h(1) = C′ is equivalent to h(½) = C′/2, the degree-≤1 liars are the non-vertical lines through the fixed point (½, C′/2): take the pencil through that point and delete the vertical line X = ½. What remains is an affine line's worth of liars — exactly q of them, matching |L| = q^d — not a P¹. The map sending a liar to its unique surviving challenge is then the restriction to A¹ ⊂ P¹ of a Möbius automorphism of P¹ (matrix [[−1, 0], [−2, Δ]], determinant −Δ ≠ 0), and it is a bijection onto (F ∖ {½}) ∪ {∞}, where ∞ records “this liar survives no challenge at all” — the unique liar whose slope matches the truth's. Two corollaries fall straight out: r = ½ is the one field element no degree-1 liar survives, and every other field element is exactly one liar's escape.

move the liar's slope

liar's slope2.0

the one r₁ this liar survives

−0.33

challenges that expose it

q − 1

the challenge no liar survives

r = ½

So the intermediate checks verify nothing about f. A committed liar passes every round-consistency check deterministically; a one-parameter family of lying lines sails through round 1. Soundness cannot be coming from the sum-checks. It runs the other way — backward, from the one place the prover does not get to write.

There is exactly one true fact in the whole transcript: the final evaluation, which the verifier obtains itself. Everything above it is a chain the prover controls. What the protocol does is force any single lie to propagate down that chain until it collides with that one true value, using two rigidity facts:

(a) A false number becomes a false polynomial. The prover cannot answer with a number; the consistency check demands a whole low-degree polynomial whose chord passes through a fixed point. To keep lying it must commit to an entire curve that is wrong.

(b) A random challenge turns that false polynomial back into a false number. Two distinct degree-d polynomials agree at ≤ d points — Bézout on the moment curve — so a uniform challenge lands on their disagreement with probability ≥ 1 − d/q. The lie is re-exposed as a bad number one level down, and the cycle repeats until it hits f(r₁, …, r_v) and dies.

How many challenges does a committed liar actually survive? Exactly one, on average

The bound d/q is worst-case, and it is the right bound for a security claim, because the prover chooses the lie. But it is natural to ask what the adversary's landscape looks like, and the answer is sharper than the bound suggests. Count the incidence set

I = { (D, r) : D(0) + D(1) = Δ,  D(r) = 0 }.

For a fixed r, the two conditions are inhomogeneous linear conditions on V_d, and they are independent unless E_r is a scalar multiple of S — which by §7 happens only when d = 1 and r = ½. So for d ≥ 2 each of the q choices of r admits exactly q^d−1 lies, giving |I| = q^d against a liar population of q^d:

The mean is not the whole story, and it would be a mistake to read it as “the worst case is rare.” At small d the distribution is strikingly spread. Enumerating every lie over F₁₃:

At d = 2 the counts of “no escape” and “maximum escapes” are exactly equal — a quadratic difference either splits over F or it does not, in equal measure — and the mean of 1 is forced by that symmetry rather than by any concentration. The exact counts, with χ the quadratic character, are #{|E| = 1} = 2q − 2 − χ(−1) and #{|E| = 0} = #{|E| = 2} = (q² − 2q + 2 + χ(−1))/2, so only about 2/q of quadratic lies escape exactly once, and nearly half attain the worst case. The picture changes with degree: as q grows at fixed d, the fraction of lies escaping nothing tends to Σ_k≤d (−1)^k/k! — the classical density of degree-d polynomials with no linear factor — which is ½ at d = 2, ⅓ at d = 3, ⅜ at d = 4, and the lies attaining the full d escapes become a vanishing minority (about 1.9% at q = 11, d = 4). None of this is a Poisson heuristic and the limit is not 1/e for fixed d.

So what buys security is not that evasive lies are rare — at d = 2 they are half the field of play. It is that a lie planting d escape points is still planting only d of them out of q, and must do so before the coin is flipped.

Drive the adversary yourself

The widget below is the complete two-round cheating game on f = 2x₁² + 3x₂ + x₁x₂, with the adversary parameterised the way §8 says it should be: by the size of its lie and by where it plants its escapes. Everything else — the actual lying polynomials — is then forced by the verifier's own checks.

drive the adversary

Round 1 — the lie and its two planted escapes

lie Δ = Ĥ − H−5

escape ρ₁−0.80

escape ρ₂1.75

challenge r₁2.60

Round 2 — one degree, so one planted escape

escape ρ₃0.30

challenge r₂1.90

snap r₁ onto an escape

9 · The protocol as a walk between rank-one functionals

§7 looked at one variable. Put the variables back and the picture that emerges is the one that explains why the protocol has rounds at all — and why certain generalisations are free while others are expensive.

Let V be the space of polynomials with individual degree ≤ d_i in variable i. It factors as a tensor product of v single-variable spaces, and so does its dual. In those coordinates the two endpoints of the protocol are

S = (E₀ + E₁) ⊗ (E₀ + E₁) ⊗ ⋯ ⊗ (E₀ + E₁),

E_r = E_r1 ⊗ E_r2 ⊗ ⋯ ⊗ E_rv,

and both are rank-one tensors in the dual space — points of the Segre variety P^d₁ × ⋯ × P^d_v ⊂ P(V^∗). The claim standing after round i corresponds to

E_r1 ⊗ ⋯ ⊗ E_ri ⊗ (E₀+E₁) ⊗ ⋯ ⊗ (E₀+E₁),

also rank one. So the protocol is a walk along the Segre variety from the summation point to the evaluation point, replacing one tensor factor per round, and never leaving the rank-one locus. That is the structural reason a round is a coherent unit of work: each round is one factor's worth of the problem, and the factors do not interact.

Two hypotheses hold this together and are easy to skip past. The individual-degree (box) constraint is essential — a total-degree space is not a tensor product of univariate spaces, as one can see from dimensions alone: total degree ≤ 1 in two variables has dimension 3, and 3 does not factor. And this is a completeness-and-bookkeeping statement, not a soundness argument: the protocol's state is a pair (functional, claimed value), and against a cheating prover the claimed value is not the functional's value at all. Soundness is v applications of the univariate root bound, about which the tensor picture says nothing.

What the product weight does buy, and what batching really costs

eq(x, τ) = ∏_i (1 − x_i − τ_i + 2x_iτ_i) is a rank-one weight, and for multilinear p the eq-weighted sum functional is the evaluation functional in disguise: Σ_x∈{0,1}^v eq(x,τ) p(x) = p̃(τ) exactly. What its product structure buys is verifier-side, not round structure and not degree: the verifier can evaluate eq(r, τ) itself in O(v), so the reduction terminates in a single evaluation claim about p alone, whereas a weight the verifier cannot evaluate unaided would need an oracle of its own. And rank one is not even required for that: Σ_j c_j eq(·, τ_j) is verifier-evaluable in O(kv). Note too that product structure does not lower the round degree — with eq it is deg_i(p) + 1 = 2, exactly as for a generic multilinear weight.

Batching costs a factor of k, not a factor of rank. This is worth stating flatly because the rank story is seductive and wrong. Combining k claims produces a weight Σ_j c_j eq(·, τ_j) of tensor rank at most k, and the rounds still work — but three things break the cost argument. Rank saturates: a v-way 2 × ⋯ × 2 tensor has CP rank at most 2^v−1, so at v = 2 every batched weight with k ≥ 2 already has rank 2. No prover computes a CP decomposition, so it could not pay in rank even if it wanted to. And low rank is not what makes proving cheap in the first place: a generic full-rank multilinear weight folds at exactly the same per-round cost as eq. The k in batched-prover costs comes from carrying k witnesses, and the batching real systems perform — one τ and a random linear combination of the k polynomials, Spartan/HyperPlonk style^[13] — keeps the weight rank one throughout.

The prover is a contraction schedule

For multilinear f the prover holds the table of 2^v cube values. It enters round i with a table of 2^v−i+1 entries and leaves with 2^v−i: binding the challenge contracts one tensor factor against (1 − r_i, r_i) by A′[j] = A[j] + r_i(A[h+j] − A[j]) with h = 2^v−i, and the last surviving entry is f(r). Total work is Θ(2^v) — linear in the size of the object, the result that made sumcheck practical rather than merely asymptotic. Read geometrically: the prover's algorithm is the walk of this section executed on the primal side, and each round's cost is the size of the tensor factor being consumed.

Since the constant is where implementations live, it is worth being exact rather than saying “about 2^v+1 operations,” which counts only the folding additions. The folds cost 2(2^v − 1) additions and 2^v − 1 multiplications; forming the messages costs a further 2^v+1 − 2 − 2v additions if both g_i(0) and g_i(1) are summed, or 2^v − 1 − v if only one is and the other is recovered from C_i−1. So roughly 5 · 2^v field operations naively and 4 · 2^v with that saving — a 2–2.5× correction to the usual shorthand.

Attribution here should be a lineage rather than a first. Sumcheck is LFKN^[1]; the streaming evaluation of a multilinear extension from its cube values is Cormode–Mitzenmacher–Thaler^[9], improved to an O(2^v) memoised table by Vu–Setty–Blumberg–Walfish; the first log-factor-free linear-time prover in the GKR setting is Thaler^[8], and general wiring came with Libra. Thaler's monograph^[7] traces the chain properly. Note also that the pure-multilinear case here is a toy: by §6 it needs no sumcheck at all.

Why a round message can carry d elements instead of d + 1

Because the verifier already knows C_i−1 — C₀ = H is part of the claim and C_i−1 = g_i−1(r_i−1) thereafter — the round-i message can carry d_i field elements, the constraint g_i(0) + g_i(1) = C_i−1 supplying the missing degree of freedom. Soundness is not merely preserved but identical: (d_i values, C_i−1) ↔ {g : deg g ≤ d_i, g(0) + g(1) = C_i−1} is a bijection, so accepting transcripts correspond one to one and the consistency check becomes structural rather than tested. This is folklore — universal in implementations, exercise-level in the monograph^[7], used without attribution in current papers — and no primary source exists for it, so we attach no name. (Gruen's eq-factor optimisation^[11] is a different and stronger thing, and the live line of sumcheck-proving optimisations^[12] is where the real constants are now being fought over.)

Two conditions, and the first has a clean statement we have not seen made. Suppose the message is g_i on a node set E with |E| = d_i. Then g_i is recoverable if and only if

∏_e∈E (0 − e)  +  ∏_e∈E (1 − e)  ≠  0,

because the annihilator of {E_e : e ∈ E} is spanned by ∏_e(X − e), and S lies in the retained span exactly when it kills that annihilator. Within the usual nodes {0, …, d_i} this reduces to the familiar rule — do not retain both 0 and 1, i.e. omit one of them, and do not omit a top evaluation. But the criterion is genuinely sharper: E = {2, 3, 4} at d = 3 is fine although it contains neither 0 nor 1, while E = {½} at d = 1 fails although it also contains neither, precisely because g(0) + g(1) = 2g(½) for affine g — the §7 identity, resurfacing as an implementation hazard. Second condition: characteristic. In coefficient form the constraint is 2a₀ + a₁ + ⋯ + a_d = C_i−1, so omitting a₀ requires dividing by 2 and fails in characteristic 2, while omitting any higher coefficient is characteristic-free; in evaluation form, omitting g(0) or g(1) is characteristic-free. And under Fiat–Shamir both sides must hash the same canonical object — either the d_i transmitted elements or the reconstructed polynomial, never one on each side.

And the Segre picture closes the loop with §5

The multilinear extension is usually written in the Lagrange (or eq) basis:

f̃(x) = Σ_{b ∈ {0,1}^v} f(b) · ∏_i (b_i x_i + (1 − b_i)(1 − x_i)),

and that basis is exactly the Segre basis ⊗_i (1 − x_i, x_i). The multilinear extension of a table is the Segre parametrisation of the table, and for v = 2 the graph is the Segre quadric in P³ — the very doubly ruled surface of §5, with the two rulings being the two P¹ factors. The pretty picture and the general theory are the same object at different v.

10 · The code underneath: rigidity is minimum distance

Everything above has leaned on one word — rigidity — and it has a precise coding-theoretic meaning worth spelling out, because it is where the geometry stops being a metaphor.

The multilinear extension map, from tables on {0,1}^v to evaluation vectors on F^v, is an encoder. The code it produces, M_v = { (f̃(a))_{a ∈ F^v} }, is the v-fold tensor power of the full-length Reed–Solomon code of degree-≤1 univariate polynomials — evaluation at all of F, a [q, 2, q−1] code^[20] — or equivalently the set of v-dimensional arrays every axis-parallel line of which is an RS codeword. Tensor products multiply minimum distances^[19], so

M_v = [q^v, 2^v, (q − 1)^v],   relative distance δ = (1 − 1/q)^v.

One terminological warning before anything else, because it is a trap: do not call this a Reed–Muller code. Total-degree Reed–Muller codes are not tensor product codes, and the individual-degree bound below is not the total-degree bound. Say “the multilinear (individual-degree-one) evaluation code.”

Equivalently, a nonzero multilinear polynomial vanishes on at most q^v − (q−1)^v points, so Pr[f̃(x) = 0] ≤ 1 − (1 − 1/q)^v ≤ v/q. This is not a new bound: it is the standard individual-degree estimate #zeros ≤ q^v − ∏_i(q − d_i) of DeMillo–Lipton and Zippel^[4] at d_i = 1, and the tensor-code argument reproves it via minimum distance. State the comparison carefully: it is sharper than Schwartz–Zippel instantiated at total degree v, in the worst case over nonzero multilinear f, and the improvement is second order — 1 − (1 − 1/q)^v = (v/q)(1 − (v−1)/2q + ⋯), hence irrelevant at cryptographic q. It is not uniformly better than SZ applied to a particular f's true total degree: f = x₁ with v = 2 over F₅ has zero-fraction exactly 1/5, matching SZ, while the tensor bound gives a weaker 9/25.

Now the extremal case, which is where the intuition lives. Take a single Boolean point b and consider the message that is 1 at b and 0 elsewhere. Its multilinear extension is

δ̃_b(x) = ∏_i (x_i if b_i = 1, else 1 − x_i),

a product of v nonzero affine forms, each vanishing on one hyperplane. Its zero set is a union of v hyperplanes and its weight is exactly (q − 1)^v. So:

Watch it in our two-variable example. Change one corner, f₂(1,1) from 6 to 5. The new multilinear extension is 2x₁ + 3x₂ — the bilinear term vanishes entirely — and the error is the codeword x₁x₂.

drag to rotate

Tilt

Spin

Sumcheck is spot-checking this codeword, and the schedule of the checks is the walk of §9. That is also the honest place to say where the geometry ends and cryptography begins: in a deployed system the final evaluation is not computed by the verifier from a polynomial it holds, but delivered by a polynomial-commitment opening. The code's distance is what makes that opening meaningful — a prover that committed to a different table committed to a codeword far from this one — and the commitment scheme is what makes it binding. The geometry gets you to the last query; it does not answer it.

11 · Summation is evaluation — precisely when

We can now settle the question that motivates the whole subject and is usually answered with a gesture. It can feel as though a cumulative act — add 2^v numbers — has been mysteriously converted into a pointwise one. There is no conversion and no mystery, but there is a precise boundary, and both sides of it matter.

Start with the trivial half:

Σ_{x ∈ {0,1}} g(x) = g(0) + g(1).

A sum over a Boolean variable already is two evaluations; a sum over the cube is 2^v evaluations glued by additions. Sharper: on the (d+1)-dimensional space V_d, both S and E_r are linear functionals, and in a (d+1)-dimensional space every functional is a combination of any d+1 independent evaluations. Sum and evaluation are two vectors in the same small dual space — the same kind of object, with different coefficients. Read our g₁ = 4X² + X + 3 through the nodes {0,1,2}, where it takes values (3, 8, 21):

Same three numbers, two weightings. Nothing is converted; the coefficients change, that is all. And in the multilinear case the sum is literally one evaluation — the barycentre identity of §6, Σ_cube f₂ = 4 · f₂(½,½) = 4 · 2.75 = 11, which fails for the quadratic f at 4 · f(½,½) = 9.

So “how does a cumulative act become a point evaluation?” has a literal answer in the simplest case: it already was one. And §7 says exactly how far that answer extends: as far as individual degree 1, and no further, with the obstruction at degree 2 equal to the variance of the Boolean edge.

Then what is the protocol actually for?

Not to bridge a mathematical gap. Two other gaps, both real. First, computational: the verifier cannot evaluate a marginal, because computing g₁(4) honestly means summing over the remaining cube — the very cost it is escaping. Second, trust: it cannot take the prover's word for a polynomial it never sees in full. Here is how you would invent the fix, and the third attempt is the one that matters.

Attempt 1 — split the sum. H = A(0) + A(1) with A(x₁) = Σ_{x2, …} f. Send both numbers; the verifier adds. But now there are two sub-claims, each splitting again: a binary tree with 2^v leaves. Strictly worse than adding the numbers yourself.

Attempt 2 — check one branch at random. Cost drops to v. But a cheater lies in exactly one leaf, and a random root-to-leaf walk finds it with probability 2^−v. Catastrophic.

The actual move. The failure in attempt 2 is that a lie can be local — confined to one branch. So refuse to let a level be two independent numbers, and require it to be a single low-degree polynomial whose values at 0 and 1 are those numbers. Now a lie cannot be local: two distinct degree-d polynomials disagree at all but ≤ d points, so testing one random point tests the whole level. That is the leap, and it is not about sums. It is about degrees of freedom. The Boolean tree has local ones; the polynomial extension has none — which is §10's minimum distance, arrived at from the other direction.

12 · Provenance: what is standard, what is new, what is a correction

The historical order matches the logic, and three ingredients predated the protocol. Schwartz–Zippel — DeMillo–Lipton 1978, Zippel 1979, Schwartz 1980^[4] — a nonzero low-degree polynomial has few roots, so identity testing works by random sampling; §7 recasts the univariate case as Bézout for the moment curve. Arithmetisation: replacing Boolean connectives with field arithmetic, so a counting question becomes a summation of a polynomial over the hypercube. This is the step that manufactures a low-degree object out of thin combinatorial air, and it is where all the geometry in this article comes from. Random self-reducibility — Lipton 1991, Beaver–Feigenbaum 1990^[5] — evaluating the permanent at a specific point reduces to evaluating it at random points on a line through the target; the “escape onto a random line” move was already in the water.

In late 1989 these fused. Lund, Fortnow, Karloff and Nisan assembled the sumcheck protocol and used it to show that the permanent, and all of #P, has an interactive proof^[1]; within weeks Shamir extended the technique to IP = PSPACE^[2], and Babai–Fortnow–Lund pushed the multi-prover case to MIP = NEXP^[3]. The results shocked people because oracle separations had suggested interactive proofs should be weak; arithmetisation broke that intuition by refusing to stay inside the Boolean world where the oracle results lived. Everything since — GKR's delegation^[6], the linear-time prover^[8], the multilinear-PIOP designs that dominate current proving systems — has kept the same geometric skeleton and changed the objects it is applied to.

Attribution of the framings used above

A specialist reader is entitled to know which parts of this article are a repackaging and which are a claim. Our accounting:

13 · What to keep

The one-line correction to the usual picture: sumcheck does not convert summation into evaluation. It relocates the summation. Three things happen at once — the verifier's 2^v additions become v rounds of one-point chord checks; the prover absorbs the actual summing work into producing the round polynomials; and the irreducible residue, the one quantity that genuinely certifies contact with f, is deposited into a single evaluation f(r₁, …, r_v), which the verifier either computes directly or, in a real system, obtains from a commitment opening.

Four things worth carrying away, in the order they were earned:

The transcript is a path. In the multilinear case an honest transcript is f read along an axis-parallel walk from the barycentre of the cube to the challenge point, and the verifier's checks say only that the walk is connected. The sum lives at the start of that walk; the truth lives at its end.

The protocol exists because of a variance. Summation over a Boolean edge and evaluation at a point agree on mass and mean and part company at the second moment, by exactly the variance of the edge. Where the summand's space is small enough not to see that second moment — individual degree one, odd characteristic — there is nothing to bridge and no protocol is needed. Every round of every real sumcheck is paying for a space large enough to see it.

Soundness is rigidity, not accumulation. The intermediate checks establish nothing about f; a committed liar passes all of them. What the protocol does is force a false number to become a false polynomial, and a random challenge to turn it back into a false number one level down, until it collides with the single value the prover did not get to write. The escape set of any one committed lie is at most d points; the union of escape sets over all lies is the entire field. That gap between “any one” and “all” is the whole security argument, and it is why the order of speaking is not a technicality.

Coordinates are the constraint. The protocol may only travel along coordinate lines. Multilinearity is not a geometric enrichment of the surface — f's graph is just as ruled as f₂'s, and its extra ruling family is perfectly real; it is simply skew to the frame the protocol is obliged to use. The condition that matters is that every coordinate direction be a ruling direction, which is per-variable degree one, which is exactly what each round certifies. That is why the multilinear extension is a normal form rather than a stroke of luck, and it is the cleanest available answer to the question of why arithmetisation targets multilinear objects specifically.

What began as “add four numbers” ends as “evaluate once, at a point nobody could predict.” Not because summation and evaluation are different things bridged by a trick, but because they are two readings of one rigid object, separated by a single second moment — and the protocol's only real work is choosing where, and in what order, to take the reading.

References

1. Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan — Algebraic Methods for Interactive Proof Systems. FOCS 1990, pp. 2–10; Journal of the ACM 39(4):859–868, October 1992. doi:10.1145/146585.146605. The origin of the sumcheck protocol.
2. Adi Shamir — IP = PSPACE. FOCS 1990, pp. 11–15; Journal of the ACM 39(4):869–877, October 1992. doi:10.1145/146585.146609. (Not to be confused with Shen's simplified proof in the same JACM issue, pp. 878–880.)
3. László Babai, Lance Fortnow, Carsten Lund — Non-deterministic exponential time has two-prover interactive protocols. FOCS 1990, pp. 16–25; Computational Complexity 1(1):3–40, 1991. doi:10.1007/BF01200056
4. Jacob T. Schwartz — Fast Probabilistic Algorithms for Verification of Polynomial Identities. Journal of the ACM 27(4):701–717, 1980. doi:10.1145/322217.322225. Richard Zippel — Probabilistic algorithms for sparse polynomials. EUROSAM '79, LNCS 72, Springer, pp. 216–226. doi:10.1007/3-540-09519-5_73. Richard A. DeMillo, Richard J. Lipton — A probabilistic remark on algebraic program testing. Information Processing Letters 7(4):193–195, 1978. doi:10.1016/0020-0190(78)90067-4. The individual-degree form of the zero bound used in §10 comes from the latter two.
5. Richard J. Lipton — New Directions In Testing. Distributed Computing and Cryptography (DIMACS Workshop, Princeton, October 1989), DIMACS Series vol. 2, AMS, 1991, pp. 191–202. doi:10.1090/dimacs/002/13. Donald Beaver, Joan Feigenbaum — Hiding Instances in Multioracle Queries. STACS 1990, LNCS 415, Springer, pp. 37–48. doi:10.1007/3-540-52282-4_30. Random self-reducibility: the “escape onto a random line” move that predated sumcheck.
6. Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum — Delegating computation: interactive proofs for muggles. STOC 2008, pp. 113–122, doi:10.1145/1374376.1374396; journal version Journal of the ACM 62(4), Article 27, 2015, doi:10.1145/2699436.
7. Justin Thaler — Proofs, Arguments, and Zero-Knowledge. Foundations and Trends in Privacy and Security 4(2–4):117–660, 2022. people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf. The background text assumed throughout; §3.5 for the multilinear-extension mean-value identity, §4.1 for the round check, Lemmas 3.7/3.8/4.5 for the prover lineage. Internal numbering shifts between drafts.
8. Justin Thaler — Time-Optimal Interactive Proofs for Circuit Evaluation. CRYPTO 2013, pp. 71–89. eprint.iacr.org/2013/351. The first log-factor-free linear-time prover in the GKR setting; credit for the linear-time sumcheck prover is joint with Vu–Setty–Blumberg–Walfish (S&P 2013), and §9 gives the lineage rather than a single origin.
9. Graham Cormode, Michael Mitzenmacher, Justin Thaler — Practical verified computation with streaming interactive proofs. ITCS 2012, pp. 90–112. doi:10.1145/2090236.2090245
10. Suyash Bagad, Yuval Domb, Justin Thaler — The Sum-Check Protocol over Fields of Small Characteristic. Cryptology ePrint Archive 2024/1046. eprint.iacr.org/2024/1046. Why characteristic two is a different problem, as §6 and §7 note.
11. Angus Gruen — Some Improvements for the PIOP for ZeroCheck. Cryptology ePrint Archive 2024/108. eprint.iacr.org/2024/108. §3.2 for the eq-factor (“Gruen”) optimisation and the univariate skip — not a source for the omit-one-evaluation folklore of §9.
12. Quang Dao, Justin Thaler — More Optimizations to Sum-Check Proving. ePrint 2024/1210, eprint.iacr.org/2024/1210. Suyash Bagad, Quang Dao, Yuval Domb, Justin Thaler — Speeding Up Sum-Check Proving. ePrint 2025/1117, eprint.iacr.org/2025/1117. Quang Dao, Zachary DeStefano, Suyash Bagad, Yuval Domb, Justin Thaler — Speeding Up Sum-Check Proving (Extended Version). ePrint 2026/587, eprint.iacr.org/2026/587. The current state of the art on prover constants.
13. Srinath Setty — Spartan: Efficient and General-Purpose zkSNARKs Without Trusted Setup. CRYPTO 2020, pp. 704–737. eprint.iacr.org/2019/550. Binyi Chen, Benedikt Bünz, Dan Boneh, Zhenfei Zhang — HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates. EUROCRYPT 2023, pp. 499–530. eprint.iacr.org/2022/1355. The multilinear-PIOP designs whose batching §9 describes.
14. Joe Harris — Algebraic Geometry: A First Course. Springer GTM 133, 1992. doi:10.1007/978-1-4757-2189-8. Ex. 1.14 (the rational normal curve; no three points collinear); Ex. 2.11 (the Segre variety Σ_1,1 as a quadric with two rulings); Ex. 3.3 (classification of quadrics by rank); Ex. 9.6 and Prop. 9.7 (catalecticant rank as membership in a secant variety — note that this is border rank, so it is not the citation for symmetric rank). Hypotheses matter here: the base field is algebraically closed and Ex. 3.3 assumes char ≠ 2, so none of it transfers verbatim to F_q, where nondegenerate quadrics in P³ fall into two classes.
15. Robin Hartshorne — Algebraic Geometry. Springer GTM 52, 1977. doi:10.1007/978-1-4757-3849-0. Ex. I.2.14 (the Segre embedding) and Ex. I.2.15 (the quadric surface in P³ and its double ruling).
16. Pierre Comon, Gene Golub, Lek-Heng Lim, Bernard Mourrain — Symmetric Tensors and Symmetric Tensor Rank. SIAM Journal on Matrix Analysis and Applications 30(3):1254–1279, 2008. doi:10.1137/060661569. Cor. 4.4 is the rank-2 lower bound §7 needs — the “d ≥ 2” condition in disguise. Open access: hal.science/hal-00327599v1
17. J. M. Landsberg — Tensors: Geometry and Applications. AMS GSM 128, 2012. doi:10.1090/gsm/128. Chapters 4–5 for the multi-factor Segre variety Seg(PA₁ × ⋯ × PA_n) and the modern rank/secant dictionary that §9's walk lives in.
18. Anthony Iarrobino, Vassil Kanev — Power Sums, Gorenstein Algebras, and Determinantal Loci. Springer LNM 1721, 1999. doi:10.1007/BFb0093426. Chapter 1 for the catalecticant/Hankel and apolarity machinery.
19. F. J. MacWilliams, N. J. A. Sloane — The Theory of Error-Correcting Codes. North-Holland, 1977, Ch. 18 §2 (“Direct product codes”), p. 568: the product-of-distances fact and its minimum-weight codewords. Eli Ben-Sasson, Madhu Sudan — Robust locally testable codes and products of codes. Random Structures & Algorithms 28(4):387–402, 2006, doi:10.1002/rsa.20120 (§2, and Prop. 2.5 for the rows/columns characterisation). Sumegha Garg, Madhu Sudan, Gabriel Wu — Testing Tensor Products of Algebraic Codes. APPROX/RANDOM 2025, arXiv:2410.22606. Venkatesan Guruswami, Atri Rudra, Madhu Sudan — Essential Coding Theory (draft), Ex. 2.20 for the tensor-code parameters.
20. Alessandro Chiesa, Peter Manohar, Igor Shinkar — On Axis-Parallel Tests for Tensor Product Codes. Theory of Computing 16(5):1–34, 2020. doi:10.4086/toc.2020.v016a005. §1 states outright that the individual-degree evaluation code is the m-th tensor power of the univariate code — the identification §10 rests on, and the reason not to call it Reed–Muller.
21. Bruno Buchberger — A criterion for detecting unnecessary reductions in the construction of Gröbner-bases. EUROSAM '79, LNCS 72, pp. 3–21. doi:10.1007/3-540-09519-5_52. The first criterion (coprime leading monomials ⇒ the S-polynomial reduces to zero), which is why {x_i² − x_i} is a Gröbner basis under every order; see also David A. Cox, John Little, Donal O'Shea — Ideals, Varieties, and Algorithms, 4th ed., Springer, 2015, Ch. 2 §9, doi:10.1007/978-3-319-16721-3, and Tamás Mészáros — Standard monomials and extremal point sets, Discrete Mathematics 343(4):111785, 2020, arXiv:1908.03045, §2, for the standard-monomial count.