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.
Classical distance gives error detection, unique decoding, and erasure recovery
Statement
Let have distance parameter and let . Then:
- Every nonzero error of weight less than is detected by a parity-check matrix: .
- If for and , then is the unique codeword with ; moreover distinct errors of weight at most have distinct syndromes.
- If the erased coordinate set is known and , at most one codeword agrees with the received word outside .
These are detection, unique-decoding, and erasure-uniqueness guarantees. They do not assert an efficient decoder or a complexity bound.
Facts & Assumptions
Given: A finite-field linear code with distance , its parity-check matrix , and .
Hamming weight and distance of a finite-field linear code: Every nonzero codeword has weight at least ; for the zero code .
Hamming balls below half the code distance are disjoint: Hamming balls of radius around distinct codewords are disjoint.
Syndrome of a received word over a finite field: The syndrome map on a received word is .
A received-word syndrome depends only on the error vector: If with , then .
Equal classical syndromes imply a codeword difference: Equal syndromes force errors to differ by a codeword; errors of weight at most with are equal.
Syndrome of a received word over a finite field: Its hypothesis makes a parity-check matrix of ; the matrix convention in that definition's prerequisites is .
Proof
The floor formula gives . If , [L6] gives ; if and , [L1] is contradicted. Hence every such nonzero error is detected.
The transmitted codeword lies in the radius- ball around . Any other codeword in that ball would put in two distinct radius- balls, contradicting [L2]; therefore is the unique such word.
If two errors of weight at most have the same syndrome, [L5] gives . For a received word , [L3] and [L4] identify the measured syndrome as , so it uniquely identifies the error within that weight range.
If both agree with the received word outside the known set , then is supported in , so . If , this is a nonzero codeword contradicting [L1]. Thus at most one codeword is compatible. For , the only candidate is already unique and .
Remarks
The theorem is an information-theoretic uniqueness statement, not an algorithm or complexity claim. A decoder's representation of field elements, search procedure, termination proof, and cost would be separate algorithmic content.
Depends on
- Syndrome of a received word over a finite field
- Classical linear code over a finite field
- Hamming weight and distance of a finite-field linear code
- Hamming balls below half the code distance are disjoint
- A received-word syndrome depends only on the error vector
- Equal classical syndromes imply a codeword difference
- Every finite-field linear code has generator and parity-check matrices
Used by
- A short Reed–Solomon code over F₅ and its symbol-error syndromes Example
- Binary three-bit repetition code and its syndrome table Example
- Repetition-code syndrome, known erasures, and unlocated errors Example
- The binary [7,4,3] Hamming code and its single-error syndromes Example
- CSS syndrome correction Theorem
Dependency tree · two levels
23 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Richard Cleve, Quantum Information Processing course notes, §§37.1–37.1.3 (standard reference, not scraped)
- John Preskill, Quantum Computation, Chapter 7, §7.6 (standard reference, not scraped)