Information Polar Code Gap From Phi Gap At

The gap sequence

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 block length grows. Their finite-length gap to capacity decays as O(2^(-N^0.5)) in block length N. The Recognition Science framework models this gap on a discrete ladder: at each rung k of the ladder, the gap is a specific positive number.

The declaration gapAt, a definition in the framework's machine-checked library of formal theorems, sets the gap at rung k to be phi raised to the power -k, where phi is the golden ratio (1 + sqrt(5))/2. At rung 0, the reference gap equals 1. At rung 1, the gap is 1/phi, approximately 0.618. At rung 2, it is 1/phi squared, approximately 0.382. The sequence is positive at every rung, and each step multiplies the previous gap by 1/phi. In symbols: gapAt(k+1) = gapAt(k) * phi^(-1), so adjacent rungs always have the same ratio.

This structure mirrors the framework's treatment of quantum channel capacity corrections and LDPC code-rate gaps, which also follow the same 1/phi ratio. The framework's library proves these properties with zero axioms and zero unfinished proofs, meaning the arithmetic is machine-verified. The sequence is a model, not a measurement: it defines a ladder of gaps, it does not claim that real polar codes follow this exact ladder.

What the declaration does not claim: it does not assert that Arıkan's original polar code construction achieves this exact phi-ladder gap. It does not claim that the framework derives the Shannon capacity or the polar code gap from first principles. The O(2^(-N^0.5)) decay rate is a classical result, not a framework theorem. The phi-ladder is a framework-internal model of the gap's shape, a definitional choice for how the gap scales across block lengths, not a derivation of that scaling from the framework's axioms.

/-- Gap-to-capacity at φ-ladder rung `k`. -/
def gapAt (k : ℕ) : ℝ := referenceGap * phi ^ (-(k : ℤ))

theorem gapAt_pos (k : ℕ) : 0 < gapAt k := by
  unfold gapAt referenceGap
  have : 0 < phi ^ (-(k : ℤ)) := zpow_pos Constants.phi_pos _
  linarith [this]

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

/-- 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 phi-ladder is not a derivation of the polar code gap from the framework's axioms; it is a definitional model. The declaration does not claim that real polar codes achieve this exact gap sequence. The classical O(2^(-N^0.5)) decay rate is not proved by the framework; it is a standard result from information theory.

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: