Information Polar Code Gap From Phi

The gap on the ladder

Polar codes, introduced by Erdal Arıkan in 2009, are error-correcting codes that provably achieve the Shannon capacity of a binary-input memoryless channel as the block length N grows. Their practical importance comes from a finite-length gap-to-capacity: at any finite block length, the code falls short of the theoretical maximum rate by an amount that decays roughly as O(2^{-N^{0.5}}). The smaller this gap, the closer a real code gets to the ideal limit.

The golden ratio φ = (1 + √5)/2 ≈ 1.618 appears here as the step size of a discrete ladder. In Recognition Science, the framework models the finite-length gap as a sequence indexed by rungs k = 0, 1, 2, ... . At rung zero, the reference gap is set to 1. Each step up the ladder multiplies the gap by φ⁻¹ = 1/φ ≈ 0.618, so the gap at rung k is exactly φ^(−k). Consecutive rungs therefore stand in the ratio 1/φ, the same ratio that appears in the quantum-channel-capacity correction and in the LDPC code-rate gap within the framework.

The machine-checked library of formal theorems establishes three properties of this sequence: every gap is positive, each step multiplies the previous gap by φ⁻¹, and the ratio of adjacent gaps is exactly φ⁻¹. These are collected in a certificate structure named PolarCodeCert, which bundles the three facts as a single object. The proofs use only the definition of the gap and the positivity of φ, with no additional axioms.

What this means in plain language: the framework derives a precise, discrete scaling law for how polar codes close in on capacity as block length grows. Instead of a continuous decay curve, the gap descends in fixed multiplicative steps of 1/φ. This is a structural claim about the ladder, not a new bound on real polar codes; the classical Arıkan result remains the operative statement for actual code performance.

theorem gapAt_succ_ratio (k : ℕ) :
    gapAt (k + 1) = gapAt k * phi⁻¹ := by
  unfold gapAt
  have hphi_ne : phi ≠ 0 := Constants.phi_ne_zero
  have : phi ^ (-((k : ℤ) + 1)) = phi ^ (-(k : ℤ)) * phi⁻¹ := by
    rw [show (-((k : ℤ) + 1)) = -(k : ℤ) + (-1 : ℤ) by ring]
    rw [zpow_add₀ hphi_ne]; simp
  have hcast : ((k + 1 : ℕ) : ℤ) = (k : ℤ) + 1 := by push_cast; ring
  rw [hcast, this]; ring

theorem gapAt_adjacent_ratio (k : ℕ) :
    gapAt (k + 1) / gapAt k = phi⁻¹ := by
  rw [gapAt_succ_ratio]
  field_simp [(gapAt_pos k).ne']

/-- Polar-code gap-to-capacity certificate. -/
def polarCodeCert : PolarCodeCert where
  gap_pos := gapAt_pos
  one_step_ratio := gapAt_succ_ratio
  adjacent_ratio := gapAt_adjacent_ratio

What this page does not claim

The module does not prove a new bound on polar-code performance; it derives a scaling law for a framework-internal sequence. The framework does not claim that real polar codes achieve capacity at finite block length. The classical Arıkan result about O(2^{-N^{0.5}}) gap decay is not derived from the φ-ladder.

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