Alphabeta Math
TheoremStatement: AI-adaptedProof: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)
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 C≤Fn have distance parameter d=d(C) and let t=⌊(d−1)/2⌋. Then:

  1. Every nonzero error e of weight less than d is detected by a parity-check matrix: He≠0.
  2. If r=c+e for c∈C and wt⁡(e)≤t, then c is the unique codeword c′∈C with wt⁡(r−c′)≤t; moreover distinct errors of weight at most t have distinct syndromes.
  3. If the erased coordinate set S⊆{0,…,n−1} is known and ∣S∣<d, at most one codeword agrees with the received word outside S.

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 C≤Fn with distance d(C), its parity-check matrix H, and t=⌊(d(C)−1)/2⌋.

[L1]

Hamming weight and distance of a finite-field linear code: Every nonzero codeword has weight at least d(C); for the zero code d(C)=n+1.

[L2]

Hamming balls below half the code distance are disjoint: Hamming balls of radius t around distinct codewords are disjoint.

[L3]

Syndrome of a received word over a finite field: The syndrome map on a received word is s(r)=Hr.

[L4]

A received-word syndrome depends only on the error vector: If r=c+e with c∈C, then s(r)=He.

[L5]

Equal classical syndromes imply a codeword difference: Equal syndromes force errors to differ by a codeword; errors of weight at most t with 2t<d(C) are equal.

[L6]

Syndrome of a received word over a finite field: Its hypothesis makes H a parity-check matrix of C; the matrix convention in that definition's prerequisites is ker⁡H=C.

Proof

1.1L1L6givenalgebra

The floor formula gives 2t<d. If He=0, [L6] gives e∈C; if e≠0 and wt⁡(e)<d, [L1] is contradicted. Hence every such nonzero error is detected.

1.2L2given

The transmitted codeword c lies in the radius-t ball around r. Any other codeword c′ in that ball would put r in two distinct radius-t balls, contradicting [L2]; therefore c is the unique such word.

1.3L3L4L5given

If two errors e,f of weight at most t have the same syndrome, [L5] gives e=f. For a received word r=c+e, [L3] and [L4] identify the measured syndrome as He, so it uniquely identifies the error within that weight range.

2.1L1givenalgebra∎

If c,c′∈C both agree with the received word outside the known set S, then c−c′ is supported in S, so wt⁡(c−c′)≤∣S∣<d. If c≠c′, this is a nonzero codeword contradicting [L1]. Thus at most one codeword is compatible. For C={0}, the only candidate is already unique and d=n+1.

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

Used by

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