Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Capacity and memoryless repeated use for the route/survival channel

Definition
TranscendenceTowerChannelCapacity

by mateoej12 · Sep 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

contextformalizationinformation-theorylogicnonmonotonic-reasoning

This bundle extends the finite route/survival channel of the companion information-theory bundle with the ingredients needed to state a capacity result and a memoryless repeated-use model. It adds no theorems; every claim about these objects is proved in the theorem that imports it.

The underlying one-use channel has input alphabet {direct,viaMid}\{\mathsf{direct},\mathsf{viaMid}\}{direct,viaMid} and Boolean output, with

K(direct,true)=1,K(direct,false)=0,K(viaMid,true)=K(viaMid,false)=12.K(\mathsf{direct},\mathsf{true})=1,\qquad K(\mathsf{direct},\mathsf{false})=0,\qquad K(\mathsf{viaMid},\mathsf{true})=K(\mathsf{viaMid},\mathsf{false})=\tfrac12 .K(direct,true)=1,K(direct,false)=0,K(viaMid,true)=K(viaMid,false)=21​.

A fact transferred directly always survives; a fact transferred through the intermediate context survives with probability one half. This is a Z-channel with crossover 1/21/21/2.

The bundle introduces the following. Let q∈Rq\in\mathbb{R}q∈R.

  • The parameterized input prior pqp_qpq​, assigning probability qqq to viaMid\mathsf{viaMid}viaMid and 1−q1-q1−q to direct\mathsf{direct}direct. Because the input alphabet has exactly two elements, this one-parameter family is exhaustive: every input distribution is pqp_qpq​ for exactly one q∈[0,1]q\in[0,1]q∈[0,1].
  • The induced joint law Jq(r,b)=pq(r) K(r,b)J_q(r,b)=p_q(r)\,K(r,b)Jq​(r,b)=pq​(r)K(r,b) on input/output pairs, together with its output marginal mq(b)=∑rJq(r,b)m_q(b)=\sum_r J_q(r,b)mq​(b)=∑r​Jq​(r,b), the output entropy H(mq)H(m_q)H(mq​), and the channel conditional entropy ∑rpq(r) H(K(r,⋅))\sum_r p_q(r)\,H(K(r,\cdot))∑r​pq​(r)H(K(r,⋅)).
  • Two mutual informations. The closed form
I(q)=Hbin(q/2)−qlog⁡2,I(q)=H_{\mathrm{bin}}(q/2)-q\log 2,I(q)=Hbin​(q/2)−qlog2,

and the operative quantity Ijoint(q)I_{\mathrm{joint}}(q)Ijoint​(q), defined as the project's finite Shannon sum over the four cells of JqJ_qJq​, in which a cell of zero mass contributes zero. The two are separate definitions on purpose: proving they agree on [0,1][0,1][0,1] is part of the theorem, not built into the statement.

  • The memoryless product channel Kn(x,y)=∏iK(xi,yi)K_n(x,y)=\prod_{i}K(x_i,y_i)Kn​(x,y)=∏i​K(xi​,yi​) over input words x:Fin n→{direct,viaMid}x:\mathrm{Fin}\,n\to\{\mathsf{direct},\mathsf{viaMid}\}x:Finn→{direct,viaMid} and output words y:Fin n→By:\mathrm{Fin}\,n\to\mathbb{B}y:Finn→B. This is a conditional mass function only; it is not a code, an encoder, or a decoder.

All entropies and informations are measured in nats, matching Mathlib's Real.binEntropy, which uses natural logarithms. One bit is log⁡2\log 2log2 nats.

Formalization note. The definitions are stated over all of R\mathbb{R}R rather than over a subtype of [0,1][0,1][0,1]; the range hypotheses 0≤q≤10\le q\le 10≤q≤1 appear on the theorems instead. This keeps the objects computable to state and avoids carrying coercions through every sum.

Definition code
/-
Definitions for the capacity and repeated-use extension of the finite
route/survival channel.  This imports the immutable information-theory bundle
and adds only the parameterized prior, its induced joint law, and the
memoryless product channel.
-/

import Definitions.Def_TranscendenceTowerInformationTheory

set_option autoImplicit false

open scoped BigOperators
open TranscendenceTower TranscendenceTower.ContextTheories
  TranscendenceTower.Lifting
open TranscendenceTower.InformationTheoryPlatform

namespace TranscendenceTower.InformationTheoryCapacityPlatform

noncomputable section

/-- The input prior for one use: `q` is the probability of the routed input
and `1 - q` is the probability of the direct input. -/
def routedInputPrior (q : ℝ) : Route → ℝ
  | .direct => 1 - q
  | .viaMid => q

/-- The one-use joint route/output law induced by `routedInputPrior` and the
existing route channel. -/
def routedInputJointMass (q : ℝ) (route : Route) (output : Bool) : ℝ :=
  routedInputPrior q route * routeChannel route output

/-- The output marginal obtained from the parameterized one-use joint law. -/
def routedInputOutputMarginal (q : ℝ) (output : Bool) : ℝ :=
  ∑ route : Route, routedInputJointMass q route output

/-- Entropy of the output marginal of the parameterized one-use joint law,
measured in nats. -/
def routedInputOutputEntropy (q : ℝ) : ℝ :=
  finiteEntropy (routedInputOutputMarginal q)

/-- Channel conditional entropy under the parameterized input prior, measured
in nats. -/
def routedInputConditionalEntropy (q : ℝ) : ℝ :=
  ∑ route : Route, routedInputPrior q route * finiteEntropy (routeChannel route)

/-- Closed form for the one-use route/output mutual information in nats.  The
solution proves that the finite mutual-information sum of the explicit joint
law agrees with this expression. -/
def oneUseMutualInformation (q : ℝ) : ℝ :=
  Real.binEntropy (q / 2) - q * Real.log 2

/-- One-use mutual information as the project's finite sum for the
parameterized route/output joint law and its induced marginals. -/
def oneUseJointMutualInformation (q : ℝ) : ℝ :=
  finiteMutualInformation (routedInputJointMass q) (routedInputPrior q)
    (routedInputOutputMarginal q)

/-- The memoryless product channel for `n` independently used route channels.
This gives a probability mass to each output word conditional on an input
word; it is not a code or a coding-theorem assertion. -/
def blockChannel (n : ℕ) (input : Fin n → Route) (output : Fin n → Bool) : ℝ :=
  ∏ i, routeChannel (input i) (output i)

end

end TranscendenceTower.InformationTheoryCapacityPlatform
Source
Mateo Estrada, Harmless and Pointless: Consistency, rigidity, and the indeterminacy of context transfer in McCarthy's formalization of context, 7 September 2026, Section 8.1 (Capacity and memoryless repeated use), Theorem 15.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me