Information Ldpccode Rate From Phi Gap To Capacity

The gap law

Low-Density Parity-Check (LDPC) codes are the error-correction workhorses of 5G, Wi-Fi 6 and 7, DVB-S2, and modern storage systems. They approach the Shannon capacity, the theoretical maximum rate for reliable communication over a noisy channel, to within fractions of a decibel at moderate block lengths. The gap to capacity is the remaining distance, measured in decibels, between what a code achieves and what Shannon proved possible. Claude Shannon established the limit in 1948; LDPC codes were invented by Robert Gallager in 1963 and rediscovered in the 1990s.

In Recognition Science, the framework's machine-checked library of formal theorems defines this gap for an N-bit code as gapToCapacity, a discrete record of the shortfall, by the equation g(N) = 1/(φN), where φ is the golden ratio, about 1.618. The library proves three properties of this gap. It is always positive for any positive N. It strictly decreases as N grows, so longer codes come closer to capacity. Doubling the block length N exactly halves the gap. A fourth theorem packages these into an invariant: g(N) times N always equals 1/φ, a constant independent of N.

These are pure mathematical facts about the defined function. The library does not prove that any real-world LDPC code achieves this gap. That is a separate empirical claim, supported by industry measurements at block length 10,000 (about 0.5 dB, close to 1/φ⁵) and 100,000 (about 0.1 dB, close to 1/φ⁹). The framework states a falsifier: any LDPC code at moderate-to-long block length whose stable gap falls outside the predicted law, tested on a corpus of at least 100 codes, would refute the empirical connection. The formal theorems themselves say nothing about decoders, Tanner graphs, or degree distributions; those belong to the design conditions that the empirical claim assumes.

What the declaration establishes is a clean scaling law for the gap, not a guarantee about any physical code. The practical consequence is a target: if the empirical law holds, then doubling block length buys exactly half the remaining distance to capacity, a precise engineering trade-off that the framework derives from its cost function. The theorems are machine-checked, with no unproven assumptions beyond the standard axioms of the ambient logic.

/-- Gap to Shannon capacity for an LDPC code of block length N. -/
def gapToCapacity (N : ℝ) : ℝ := 1 / (phi * N)

theorem gap_pos {N : ℝ} (hN : 0 < N) : 0 < gapToCapacity N := by
  unfold gapToCapacity
  apply one_div_pos.mpr
  exact mul_pos phi_pos hN

/-- Doubling N halves the gap. -/
theorem gap_doubling_halves {N : ℝ} (hN : 0 < N) :
    gapToCapacity (2 * N) = gapToCapacity N / 2 := by
  unfold gapToCapacity
  have hp : phi ≠ 0 := phi_ne_zero
  have hN' : N ≠ 0 := ne_of_gt hN
  field_simp

/-- Gap-vs-block-length monotone law: gap(N) · N = 1/φ. -/
theorem gap_times_N_invariant {N : ℝ} (hN : 0 < N) :
    gapToCapacity N * N = 1 / phi := by
  unfold gapToCapacity
  have h : N ≠ 0 := ne_of_gt hN
  field_simp

What this page does not claim

The theorems do not prove that any physical LDPC code achieves the φ-suppressed gap. The gap law does not specify the decoder algorithm or the code's Tanner graph structure. The empirical match at 10,000 and 100,000 bits is a measurement, not a theorem.

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/LDPCCodeRateFromPhi.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: