Alphabeta MathGap Amplification and Assignment Testing
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.
✓ 22 results · all verified · 13 also independently AI-judged
Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 9 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.
1 · Prerequisites
Abstract Algebra
- Algebraic Closure, Embeddings, and Separability
- Algebraic Extensions, Extension Degree, and Finite Fields
- Binary Operations, Monoids, Groups and Subgroups
- Composition Series, the Jordan–Hölder Theorem and Solvable Groups
- Cosets, Index and Lagrange's Theorem
- Cyclic Groups and Direct Products
- Divisibility, Euclidean Domains, Principal Ideal Domains and Unique Factorisation
- Group Actions, Orbits, Stabilisers and Cayley's Theorem
- Group Homomorphisms and the Isomorphism Theorems
- Ideals, Quotient Rings and the Isomorphism Theorems for Rings
- Normal Subgroups and Quotient Groups
- Polynomial Rings, the Division Algorithm and Roots
- Rings, Subrings, Integral Domains and Fields
- Simple Field Extensions and the Construction of the Complex Numbers
- Splitting Fields
- Sylow's Theorems, p-Groups and Nilpotent Groups
- The Fundamental Theorem of Algebra
- The Fundamental Theorem of Finite Abelian Groups
- The Galois Correspondence
Combinatorics
Computability Theory
Linear Algebra
- Determinants of Matrices over a Commutative Ring
- Diagonalisation and the Minimal Polynomial
- Dual Spaces, Bilinear and Quadratic Forms, and Sylvester's Law of Inertia
- Eigenvalues, Eigenvectors and the Characteristic Polynomial
- Inner Product Spaces, Gram-Schmidt, Projections and Adjoints
- Linear Independence, Bases and Dimension
- Linear Transformations, Rank-Nullity and Quotient Spaces
- Matrices, the Matrix of a Linear Map, and Change of Basis
- The Determinant of a Linear Operator, Cofactors and Cramer's Rule
- The Spectral Theorem, Positive Operators and Singular Value Decomposition
- Triangularisation, Generalised Eigenspaces and Jordan Canonical Form
- Vector Spaces, Linear Subspaces, Span and Direct Sums
Measure Theory
Number Theory
Probability
Real Analysis
- Absolute and Conditional Convergence; Rearrangement; Products
- Construction of the Real Numbers via Cauchy Sequences
- Construction of the Real Numbers via Dedekind Cuts
- Continuity, IVT, EVT, and Uniform Continuity
- Countability and Uncountability
- Foundations of the Real Numbers for Analysis
- Limits of Real Functions
- limsup, liminf, and Subsequential Limits
- Monotone Functions, Discontinuities, and Continuity Sets
- Monotone Sequences, Bolzano-Weierstrass, and Cauchy Completeness
- pi: the Equivalent Characterizations
- Power Series and Real-Analytic Functions
- Properties of the Integral and the Working FTC
- Roots, Rational Powers, and Classical Inequalities
- Sequences and Limits
- Sequences and Series of Functions; Uniform Convergence
- Series: Convergence and the Nonnegative Tests
- Sine, Cosine, and the Definition of Pi
- Suprema and Infima
- The Derivative and the Mean Value Theorems
- The Riemann Integral: Definition and Integrability
- Topology of ℝ
Set Theory
2 · Logical flowchart
3 · Items
Definition
Complete uniform gap-preserving CSP reductions
Lemma
Complete linear-blowup reductions compose
Definition
Degree reduction by expander incidence clouds
Lemma
Cloud violations control distance to plurality labels
Theorem
Degree reduction preserves unsatisfaction quantitatively
Definition
Constraint graph powering with local-view labels
Lemma
Canonical local views preserve perfect satisfiability
Definition
Plurality decoding of powered local views
Lemma
Nearby lazy-walk lengths have close endpoint and claim laws
Lemma
Plurality opinions agree with local views in middle positions
Lemma
Violated-edge positions have controlled collisions
Lemma
Overlap control gives a union lower bound
Lemma
Powering preserves perfect satisfiability
Lemma
Powering amplifies a small unsatisfaction gap
Theorem
A complete uniform graph gap-amplification step
Definition
Explicit binary codes of constant rate and distance
Definition
Reed-Solomon outer code and binary linear inner code
Lemma
Reed-Solomon outer code has constant rate and distance
Lemma
A random inner linear code has fewer than one bad word in expectation
Lemma
Conditional expectation constructs the inner code deterministically
Lemma
Concatenation multiplies rate and relative distance
Theorem
A polynomial-time explicit constant-rate constant-distance code
Definition
Assignment tester and rejection ratio
Definition
Hadamard linearity constraint system
Theorem
BLR rejection is proportional to distance from linearity
Definition
Quadratic tensor consistency test
Lemma
Quadratic tensor test rejects an inconsistent tensor
Lemma
Circuit satisfiability becomes linear-quadratic consistency
Lemma
An exponential-size constant-query base assignment tester
Lemma
Gate constraints are a weak assignment tester
False statement
Repeating constraints amplifies the gap
Sources
- Irit Dinur, The PCP theorem by gap amplification, §1.2-§1.3; Definition 1.2, Theorem 1.5 and Lemmas 1.6-1.8, pp. 4-7.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.5 Definition 18.27 and Lemma 18.28, author-hosted draft.
- Irit Dinur, The PCP theorem by gap amplification, §1.3 and §3: the composed reduction (prep)ᵗ∘P, pp. 6-7 and 11-12.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.5 Definition 18.27 (complete linear-blowup reductions).
- Irit Dinur, The PCP theorem by gap amplification, §4 Definitions 4.1-4.2 and Corollary 4.3, pp. 13-15.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.5.1 the 'nice' instances and the preprocessing of Lemma 18.29.
- Irit Dinur, The PCP theorem by gap amplification, §4 proof of Lemma 4.1, pp. 13-14.
- Irit Dinur, The PCP theorem by gap amplification, §1.3 Lemma 1.7 and §4 Corollary 4.3, pp. 6 and 15.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.5.1: preprocessing to a regular expander, author-hosted draft.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.5.1 Lemma 18.31 (powering), author-hosted draft.
- Irit Dinur, The PCP theorem by gap amplification, §1.2 graph powering and §6 Definition 6.1, pp. 5 and 20.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.5.1 Lemma 18.31 part 2 (canonical assignment satisfies the powered instance).
- Irit Dinur, The PCP theorem by gap amplification, §1.2: UNSAT(G)=0 implies UNSAT(Gᵗ)=0, p. 5.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.5.1 (plurality assignment), printed p. 373.
- Irit Dinur, The PCP theorem by gap amplification, §6 (popular opinion), printed pp. 19-20.
- Irit Dinur, The PCP theorem by gap amplification, §6.1 Lemma 6.4 and Appendix A (binomial weight ratios), printed pp. 22-23 and 41.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.5.1, printed p. 374 (endpoint distributions of t-step and (t+δ√t)-step walks are within statistical distance 10δ).
- Arora and Barak, Computational Complexity: A Modern Approach, §18.5.1 Claim 18.32, printed pp. 374-375.
- Irit Dinur, The PCP theorem by gap amplification, §6 first-moment estimate (Lemma 6.2), printed pp. 21-23.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.5.1 Claim 18.33, printed p. 376.
- Irit Dinur, The PCP theorem by gap amplification, §6.2 Proposition 6.5 and Lemma 6.3, printed pp. 23-24.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.5.1 Claim 18.34 and its counting proof, printed pp. 376-377.
- Irit Dinur, The PCP theorem by gap amplification, §6 equation (7) and Fact 2.6, printed pp. 21-22.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.5.1 Lemma 18.31 part 2, printed p. 373.
- Irit Dinur, The PCP theorem by gap amplification, §1.2 (UNSAT(G)=0 implies UNSAT(Gᵗ)=0), printed p. 5.
- Irit Dinur, The PCP theorem by gap amplification, §6 Lemma 6.1 and its proof (Lemmas 6.2-6.4), printed pp. 19-24.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.5.1 Lemma 18.29 part 3 with Claims 18.32-18.34, printed pp. 372-377.
- Irit Dinur, The PCP theorem by gap amplification, §1.3 Lemmas 1.6-1.7 and §1.2, printed pp. 5-7.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.5.1 Lemma 18.29 (graph gap amplification), printed pp. 371-373.
- Arora and Barak, Computational Complexity: A Modern Approach, §17.5.2 Definitions 17.16-17.17 (code distance, Reed-Solomon), printed pp. 346-347.
- Irit Dinur, The PCP theorem by gap amplification, §2.4 and §9 (codes used in the tester composition), printed pp. 10 and 30.
- Arora and Barak, Computational Complexity: A Modern Approach, §17.5.2 Definition 17.17 (Reed-Solomon code) and §17.5.3 Definition 17.19 (concatenation), printed pp. 347-348.
- Irit Dinur, The PCP theorem by gap amplification, §9 (Reed-Solomon concatenated with a binary inner code), printed pp. 29-30.
- Arora and Barak, Computational Complexity: A Modern Approach, §17.5.2 Lemma 17.18 (Reed-Solomon distance), printed p. 347.
- Arora and Barak, Computational Complexity: A Modern Approach, §17.5.2 Definition 17.17, printed p. 347.
- Irit Dinur, The PCP theorem by gap amplification, §9 (binary inner code with a probabilistic existence argument), printed pp. 29-30.
- Arora and Barak, Computational Complexity: A Modern Approach, §17.5.2 (distance of a code, counting bound), printed pp. 346-347.
- Irit Dinur, The PCP theorem by gap amplification, §9 (explicit binary inner code obtained by derandomizing the counting argument), printed pp. 29-30.
- Arora and Barak, Computational Complexity: A Modern Approach, §7.4 and §17.5.2 (method of conditional expectations; code distance), printed pp. 123-125 and 346-347.
- Arora and Barak, Computational Complexity: A Modern Approach, §17.5.3 Definition 17.19 and Claim 17.20 (concatenation multiplies distance), printed p. 348.
- Irit Dinur, The PCP theorem by gap amplification, §9 (Reed-Solomon outer code concatenated with a binary inner code), printed pp. 29-30.
- Arora and Barak, Computational Complexity: A Modern Approach, §17.5.2-17.5.3 (Reed-Solomon and concatenated codes) and §19.2 (explicit codes), printed pp. 346-348 and 405-407.
- Irit Dinur, The PCP theorem by gap amplification, §9 (explicit binary code of constant rate and constant distance), printed pp. 29-31.
- Irit Dinur, The PCP theorem by gap amplification, §2 Definition 2.2 (assignment tester), printed p. 9.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.3 Corollary 18.25 and §18.5 Definition 18.27, printed pp. 368-369.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.1 Definition 18.22 and Theorem 18.23, printed pp. 363-364.
- Irit Dinur, The PCP theorem by gap amplification, §5 (Hadamard encoding and linearity tests), printed pp. 17-18.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.1 Theorem 18.23 and §19.3 Theorem 19.9, printed pp. 364 and 390-391.
- Irit Dinur, The PCP theorem by gap amplification, §5 (distance of a table from linearity), printed pp. 17-18.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.2 Step 2 of the verifier, printed pp. 382-383.
- Irit Dinur, The PCP theorem by gap amplification, §5 (tensor and consistency tests), printed pp. 17-18.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.2 Step 2 (rejection probability 1/4), printed pp. 382-383.
- Irit Dinur, The PCP theorem by gap amplification, §5 (consistency test), printed pp. 17-18.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.2 QUADEQ and Step 3 of the verifier, printed pp. 382-383.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.3 proof of Corollary 18.25, printed pp. 384-385.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.4.3 Corollary 18.25 (exponential-sized PCP of proximity), printed pp. 384-385.
- Irit Dinur, The PCP theorem by gap amplification, §5 Theorem 5.1, printed pp. 17-18.
- Irit Dinur, The PCP theorem by gap amplification, §9 proof of Corollary 9.3 (trivial assignment tester of rejection probability 1/|G_0|), printed p. 33.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.5 (constraint graphs of bounded arity), printed pp. 369-371.
- Irit Dinur, The PCP theorem by gap amplification, §1.5 and the weight normalisation of constraints, printed pp. 4-6.
- Arora and Barak, Computational Complexity: A Modern Approach, §18.5, printed pp. 370-375.