Information Error Correction Bounds Error Bound From 8 Tick

The 3/8 error 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 majority decide. The question is how much noise such a scheme can survive. The Recognition Science library, a machine-checked collection of formal theorems, contains a declaration named error_bound_from_8_tick that pins down one answer: majority voting works below a 3/8 error rate, which is 0.375 as a decimal.

The bound comes from a specific code structure. The library defines an eight-tick code, a discrete record of events arranged in eight phases, with codeword length 8, message length 1, and minimum distance 8. The minimum distance is the smallest number of positions in which two valid codewords differ. A code with distance 8 can detect up to 7 errors and correct up to 3, since the correction radius is (d - 1) / 2. The theorem error_bound_from_8_tick states that 3/8 equals 0.375, which is the fraction of errors this code can correct relative to its length.

The library also proves supporting facts. The Hamming bound for this code checks that 2^1 times the sum of binomial coefficients up to 3 is at most 2^8, confirming the code does not exceed the sphere-packing limit. The rate bound shows the maximum rate for single-error correction is 7/8. A separate theorem confirms the code corrects up to 3 errors, and another distinguishes detection (up to 7 errors) from correction (up to 3 errors). These are all formal statements in the machine-checked library, not empirical measurements.

In Recognition Science, the eight phases provide natural redundancy for encoding information. The framework models each bit as encoded across phases, and error correction emerges from phase correlations. The eight-tick syndrome is a list of phase values used for error detection. The library also contains definitions for quantum error correction and topological codes, though these are descriptive strings, not formal theorems.

What the declaration does not claim is just as important. The theorem proves an arithmetic equality: 3/8 = 0.375. It does not prove that any real channel with error probability below 0.375 can be corrected, nor does it establish a capacity result in the Shannon sense. The library does define a binary symmetric capacity function, but the error bound theorem does not connect to it. The bound holds for the specific eight-tick code, not for all codes or all noise models.

theorem error_bound_from_8_tick :
    -- Majority voting works below 3/8 error rate
    3 / 8 = (0.375 : ℝ) := by norm_num

/-- 8-tick: detect up to d-1 = 7 errors, correct up to ⌊(d-1)/2⌋ = 3. -/
theorem detect_vs_correct :
    (eightTickCode.d - 1 = 7) ∧ ((eightTickCode.d - 1) / 2 = 3) := by
  constructor <;> rfl

/-- 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 8-tick structure implies natural bounds:

    **Rate bound**: R ≤ 7/8 for single-error correction
    (Need 1 redundant bit per 8 for parity)

    **Error bound**: p < 3/8 = 37.5% for majority voting
    (Need majority of 8 to be correct)

    These match classical coding theory! -/
theorem rate_bound_from_8_tick :
    -- Maximum rate 7/8 for SEC
    7 / 8 = (0.875 : ℝ) := by norm_num

What this page does not claim

The theorem does not prove that any real channel with error probability below 0.375 can be corrected. The bound does not establish a Shannon capacity result for the eight-tick code. The library's quantum error correction and topological code entries are descriptive strings, not formal theorems.

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: