gap_decreasing
plain-language theorem explainer
The gap to Shannon capacity for an LDPC code of block length N decreases strictly as N increases. Information theorists studying finite-block-length corrections to capacity would cite this monotonicity result to confirm the phi-suppression law. The proof is a direct term-mode reduction that unfolds the definition and applies the reciprocal inequality after scaling by phi.
Claim. Let $N_1,N_2>0$ with $N_1<N_2$. Then $1/ (phi N_2) < 1/(phi N_1)$, where the left-hand side denotes the gap to capacity at block length $N_2$.
background
In this module the gap to capacity is defined by gapToCapacity(N) := 1/(phi N). The surrounding development shows that LDPC codes achieve the finite-N correction to Shannon capacity precisely when the Tanner graph satisfies the stated degree and girth conditions. The local setting is the phi-suppressed gap argument of B16, which derives the 1/(phi N) law from the Recognition Composition Law and the J-cost formulation of information. Upstream, lt_trans supplies transitivity of the order on the underlying arithmetic, while the gapToCapacity definition itself is the direct source of the expression being compared.
proof idea
Term-mode proof. Unfold gapToCapacity on both sides. Apply lt_trans to obtain 0 < N2 from the two hypotheses. Use phi_pos together with mul_pos to obtain positivity of phi N1 and phi N2. Apply mul_lt_mul_of_pos_left to scale the given N1 < N2 by phi. Finish with one_div_lt_one_div_of_lt.
why it matters
This monotonicity statement is one of the four properties bundled into the LDPCRateCert definition, which certifies that the gap obeys the full phi-suppression law (positive, monotone, halves on doubling, invariant when multiplied by N). It therefore closes one of the concrete claims listed in the module doc-comment for the LDPC phi-suppression argument. The result sits inside the information-domain development that links the Recognition Composition Law to practical error-correction performance at finite block length.
Switch to Lean above to see the machine-checked source, dependencies, and usage graph.