Alphabeta MathHow 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.
Interactive Proof Systems and Public Coins: Examples and Counterexamples
1 · Prerequisites
- 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
- Finite Probability Spaces and Random Variables
- Formal Languages, Encodings, and Decision Problems
- Foundations of the Real Numbers for Analysis
- Interactive Proof Systems and Public Coins
- Linear Recurrences and Rational Generating Functions
- 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 · Summary
These examples isolate amplification, the graph-nonisomorphism protocol, and the universal quantifier in soundness.
3 · Logical flowchart
4 · Definitions, theorems and proofs
None yet.
5 · Examples, counterexamples and false statements
Sequential repetition of a constant-gap protocol
Example
For a protocol with completeness and soundness , run independent copies and accept a strict majority.
Verification
Given: the repeated protocol with odd .
Its honest and cheating parameters satisfy the hypotheses of Sequential repetition amplifies completeness and soundness gaps.
Thus each error probability is exponentially small in ; choosing an odd with that bound below gives completeness at least and soundness at most .
The graph-nonisomorphism protocol on a graph pair
Example
Let be the three-vertex path and the three-cycle. They are nonisomorphic, so the challenge graph has either two or three edges and reveals its origin.
Verification
Given: the displayed pair of graphs.
Edge count is invariant under graph isomorphism, and has two edges while has three.
Hence this pair lies in GNI, and its protocol is an IP instance by Graph nonisomorphism is in IP.
A cheating-prover witness to the soundness quantifier
Statement refuted
Checking only an honest prover would suffice for soundness.
Counterexample
Given: a no-instance and a verifier which accepts exactly the message
claim and rejects the message reject.
Let the designated honest prover always send reject; it is rejected, so an honest-only check reports no problem.
A cheating prover sends claim and is accepted with probability . This contradicts soundness and exhibits exactly the defect identified in False: soundness quantifies only over honest provers.