Information Polar Code Gap From Phi Gap At Pos

The gap stays positive

In coding theory, a polar code (Arıkan 2009) is a linear block code that provably achieves the Shannon capacity of a binary-input memoryless channel as the block length grows. The gap-to-capacity is the difference between the channel capacity and the rate the code actually achieves at a finite block length. For polar codes this gap decays as O(2^{-N^{0.5}}) in block length N, a result due to Arıkan.

The Recognition Science framework places this finite-length gap on a discrete ladder indexed by nonnegative integers k, called the phi-ladder because each step multiplies the gap by the reciprocal of the golden ratio φ ≈ 1.618. The gapAt function defines the gap at rung k as φ^{-k}, starting from a reference gap of 1 at rung 0. The declaration gapAt_pos is a machine-checked theorem in the framework's library of formal theorems stating that for every nonnegative integer k, the value of gapAt k is strictly greater than zero.

In plain terms, the theorem proves that the gap-to-capacity on this ladder is always positive: it never reaches zero at any finite rung. The proof is short and direct. It unfolds the definition of gapAt, uses the fact that φ is positive (so any power of it is positive), and concludes with a linear arithmetic step. The library also proves two companion facts: the gap at rung k+1 equals the gap at rung k times φ^{-1}, and the ratio of adjacent gaps is exactly φ^{-1}. These three facts together form a certificate that the ladder has the stated geometric structure.

In Recognition Science, this positive-gap result is one small piece of a larger forcing chain that derives constants like φ from first principles. But the theorem itself does not claim that polar codes are optimal, that the phi-ladder matches actual polar-code performance measurements, or that the gap decays to zero in the limit. It only establishes a formal property of the defined sequence. The empirical question of whether real polar codes follow this exact ladder remains a separate check, not a proved consequence.

/-- 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

What this page does not claim

The theorem does not claim polar codes achieve capacity at any finite block length. The theorem does not claim the phi-ladder matches any measured polar-code performance data. The theorem does not claim the gap decays to zero, only that it is positive at every finite rung.

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: