Alphabeta MathArithmetization and the Sum-Check Protocol
About this page
Pipeline-generated
How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
1 · Prerequisites
- Algebraic Extensions, Extension Degree, and Finite Fields
- Binary Operations, Monoids, Groups and Subgroups
- Construction of the Natural Numbers
- Construction of the Real Numbers via Cauchy Sequences
- Construction of the Real Numbers via Dedekind Cuts
- Countability and Uncountability
- Finite Counting, Factorials and Binomial Coefficients
- Formal Languages, Encodings, and Decision Problems
- Foundations of the Real Numbers for Analysis
- Interactive Proof Systems and Public Coins
- Linear Algebra Methods in Combinatorics
- Linear Recurrences and Rational Generating Functions
- Polynomial Rings, the Division Algorithm and Roots
- Relations, Functions, and Quotients
- Rings, Subrings, Integral Domains and Fields
- Roots, Rational Powers, and Classical Inequalities
- The ZFC Axioms and the Basic Set Constructions
- Turing Machines, Configurations, and Computation
2 · Logical flowchart
3 · Items
Definition
Arithmetization of Boolean formulas
Lemma
Arithmetization preserves Boolean values
Lemma
Formula degree and point-evaluation cost
Definition
Multilinear extension of a Boolean-cube table
Theorem
Boolean-cube interpolation
Lemma
Streaming evaluation from a full cube table
Lemma
Linear-time evaluation from a full cube table
Lemma
Degree under Boolean elimination operators
Remark
Existing polynomial identity bounds
Definition
Sum-check with explicit degree bounds
Lemma
Perfect completeness of sum-check
Lemma
A false sum-check claim rarely becomes true
Theorem
Adaptive-prover soundness of sum-check
Lemma
Sum-check verifier resources
Corollary
Choosing a sum-check error budget
Proposition
Verifying formula counts over a supplied field
Definition
The BLR linearity test over F₂
Definition
Characters and normalized Fourier coefficients
Lemma
Character orthogonality, inversion and Parseval
Lemma
The cubic Fourier identity for BLR
Theorem
BLR acceptance implies agreement with a linear function
Definition
Two-query linear self-correction
Theorem
Pointwise correctness under less than quarter noise
False statement
False: the sum-check verifier enumerates the cube
Sources
- Arora and Barak, Computational Complexity, January 2007 web draft, §8.5.1, printed p.158 (PDF p.174)
- Arora and Barak, Computational Complexity, January 2007 web draft, §8.5.1, p.158
- Arora and Barak, Computational Complexity, January 2007 web draft, §8.5.1, p.158, 3CNF construction generalized by the same gate induction
- Justin Thaler, Proofs, Arguments, and Zero-Knowledge (2023), §3.5, Definition 3.4 and Fact 3.5, pp.28–29
- Justin Thaler, Proofs, Arguments, and Zero-Knowledge (2023), §3.5, Fact 3.5 and Lemma 3.6, pp.29–30
- Justin Thaler, Proofs, Arguments, and Zero-Knowledge (2023), Lemma 3.7, pp.30–31
- Justin Thaler, Proofs, Arguments, and Zero-Knowledge (2023), Lemma 3.8, pp.31–32
- Arora and Barak, Computational Complexity, January 2007 web draft, §8.5.1 p.158 and §8.5.3 opening degree-growth paragraph p.160
- Justin Thaler, Proofs, Arguments, and Zero-Knowledge (2023), §3.4, Lemma 3.3, p.28
- Justin Thaler, Proofs, Arguments, and Zero-Knowledge (2023), §4.1 protocol box pp.33–36
- Justin Thaler, Proofs, Arguments, and Zero-Knowledge (2023), Proposition 4.1, p.36
- Justin Thaler, Proofs, Arguments, and Zero-Knowledge (2023), Proposition 4.1 non-inductive proof, pp.36–37
- Justin Thaler, Proofs, Arguments, and Zero-Knowledge (2023), §4.1 Discussion of costs, Table 4.1 and Remark 4.2, pp.37–39
- Justin Thaler, Proofs, Arguments, and Zero-Knowledge (2023), Proposition 4.1 and degree/field-size discussion pp.35–38
- Arora and Barak, Computational Complexity, January 2007 web draft, §8.5.1–8.5.2, Theorem 8.18 proof pp.158–160 (field supplied variant)
- Arora and Barak, Computational Complexity, January 2007 web draft, §18.4.1, Definition 18.22, pp.363–364
- Arora and Barak, Computational Complexity, January 2007 web draft, §19.3.1, pp.388–389
- Arora and Barak, Computational Complexity, January 2007 web draft, §19.3.1 and Lemma 19.7 pp.388–389; §18.4.1 p.363
- Arora and Barak, Computational Complexity, January 2007 web draft, Theorem 19.9 proof pp.390–391
- Arora and Barak, Computational Complexity, January 2007 web draft, Theorems 18.23 and 19.9, pp.364 and 390–391
- Arora and Barak, Computational Complexity, January 2007 web draft, §18.4.1 Local decoding of Walsh-Hadamard code pp.364–365
- Arora and Barak, Computational Complexity, January 2007 web draft, §18.4.1 Local decoding pp.364–365
- Justin Thaler, Proofs, Arguments, and Zero-Knowledge (2023), §4.1 pp.33–38