Information Error Correction Bounds Threshold Majority Voting

The majority voting threshold

Error correction is the art of adding redundancy so that noise can be detected and undone. A simple scheme is majority voting: repeat each bit several times, and let the most common value win. The scheme works only if the noise rate stays below a threshold. For a code that repeats a bit three times, for instance, voting corrects any single flipped bit, so the threshold is one error per three symbols.

The Recognition Science framework's machine-checked library of formal theorems contains a declaration named threshold_majority_voting. The framework models an eight-tick cycle, a discrete record of eight phases, as a natural code: a codeword of length eight with one message bit, so the redundancy is eightfold. The theorem states two facts about this code. First, the number of errors it can correct, which is three, is strictly less than the codeword length, eight. Second, that correctable count equals three. The declaration therefore establishes, in the framework's own terms, that majority voting on this eight-symbol code corrects up to three errors, and that three is below the length of the code. The proof is a direct computation from the definitions, not an empirical claim.

The same library also records the classical context. A Hamming bound, which limits how many errors a code of given length can correct, is checked for this code. The rate of the code, one message bit per eight symbols, is 0.125, and the library notes a separate bound of 7/8 for a single-error-correcting code. The framework's summary strings say that majority voting corrects 3/8 errors, meaning three errors per eight symbols, which matches the theorem. The library also defines a falsifier structure: a proposition that the framework's error correction claims fail would be a contradiction, so the claims are internally consistent.

What the declaration does not claim is worth stating plainly. It does not prove that any real communication channel behaves this way. It does not derive the threshold from Shannon's channel capacity theorem, which appears only as a definition and a named concept. It does not establish that the eight-tick cycle is the optimal code, nor that it outperforms any other code. The theorem is a statement about a specific formal object, the eight-symbol code defined in the library, and its error-correcting capability under majority voting. It is a piece of internal structure, not a result about the physical world.

The practical lesson a reader can take is about the logic of error correction itself. The threshold for majority voting is set by the code's minimum distance, the smallest number of symbol changes that turns one codeword into another. The framework's theorem computes that distance for its eight-symbol code and shows the voting threshold follows. That is the same arithmetic that governs any repetition code, whether in a textbook or in the framework's formal library.

/-- For majority voting on 8 phases, the threshold is p < 3/8.
    Below this error rate, the majority is always correct. -/
theorem threshold_majority_voting :
    (eightTickCode.d - 1) / 2 < eightTickCode.n ∧
    (eightTickCode.d - 1) / 2 = 3 := by
  unfold eightTickCode; constructor <;> norm_num

/-- For majority voting on 8 phases, the threshold is p < 3/8.
    Below this error rate, the majority is always correct. -/
theorem threshold_majority_voting :
    (eightTickCode.d - 1) / 2 < eightTickCode.n ∧
    (eightTickCode.d - 1) / 2 = 3 := by
  unfold eightTickCode; constructor <;> norm_num

/-- The Hamming bound (sphere-packing bound):

    For t-error-correcting code:
    2^k × Σᵢ₌₀ᵗ C(n,i) ≤ 2ⁿ

    Codes meeting this bound are "perfect" (e.g., Hamming codes).

    Formalized as: for our 8-tick code with d=8, t=3,
    the volume of radius-3 balls around 2^1 codewords fits inside {0,1}^8. -/
theorem hamming_bound_8tick :
    2 ^ 1 * (Nat.choose 8 0 + Nat.choose 8 1 +
      Nat.choose 8 2 + Nat.choose 8 3)
    ≤ 2 ^ 8 := by
  native_decide

/-- The derivation would be falsified if:
    1. Error correction exceeds Shannon limit
    2. 8-tick doesn't support redundancy
    3. Majority voting doesn't work in quantum regime -/
structure ErrorCorrectionFalsifier where
  exceeds_shannon : Prop
  no_8tick_redundancy : Prop
  qec_fails : Prop
  falsified : exceeds_shannon → False

What this page does not claim

This does not claim that any real communication channel has an eight-tick structure or a 3/8 error threshold. This does not claim that the eight-tick code is optimal or that it outperforms any other error-correcting code. This does not claim that Shannon's channel capacity theorem is derived within the framework.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Information/ErrorCorrectionBounds.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: