One-use capacity of the route/survival channel, uniquely at
ProvedTranscendenceTower.InformationTheory.one_use_channel_capacityConsider the finite channel in which a fact transferred directly between contexts always survives, and a fact transferred through an intermediate context survives with probability one half. Let be the probability that the routed input is used. Because the input alphabet has exactly two elements, this single parameter is exhaustive: every input probability distribution on the route alphabet equals for exactly one , so optimizing over really is optimizing over all input distributions rather than over a convenient sub-family.
The result has five parts.
- The parameterized law is a distribution. For each the four-cell joint mass on input/output pairs is nonnegative and sums to one.
- Exhaustive parameterization. For every finite distribution on the route alphabet there is a unique with that distribution equal to .
- The finite sum equals the closed form. On , the project's finite Shannon sum — the actual summation over the four cells, with zero-mass cells contributing zero — equals . Separately, that closed form is the difference of the output entropy and the channel conditional entropy. The endpoints and are handled on their own, since cells vanish there and the logarithms of the interior argument are undefined.
- Capacity and its unique optimizer. For every both quantities are bounded above by , with equality if and only if ; both attain at . The one-use capacity of this channel is therefore exactly nats, and the optimizing input distribution is unique.
- Memoryless repeated use. For every and every fixed input word, the coordinatewise product channel is a probability distribution over output words. The degenerate cases agree with expectation: is the unit mass on the empty word, and is the original one-use channel.
The bound is stated for both the closed form and the finite sum, so the capacity claim certifies the project's own definition rather than a hand-chosen expression that merely looks like it.
Limits. Part 5 supplies the memoryless finite channel that a coding theorem would presuppose, and nothing more. It constructs no encoder and no decoder, and proves no achievability, converse, or asymptotic statement; is proved here as the maximum of the one-use mutual information, not as an operational rate. Entropies are in nats.
import Definitions.Def_TranscendenceTowerChannelCapacity set_option autoImplicit false open scoped BigOperators open TranscendenceTower TranscendenceTower.ContextTheories TranscendenceTower.Lifting open TranscendenceTower.InformationTheoryPlatform open TranscendenceTower.InformationTheoryCapacityPlatform
theorem TranscendenceTower.InformationTheory.one_use_channel_capacity :
(∀ q : ℝ, 0 ≤ q → q ≤ 1 →
IsFiniteDistribution
(fun x : Route × Bool => routedInputJointMass q x.1 x.2))
∧ (∀ prior : Route → ℝ, IsFiniteDistribution prior →
∃! q : ℝ, 0 ≤ q ∧ q ≤ 1 ∧ prior = routedInputPrior q)
∧ (∀ q : ℝ, 0 ≤ q → q ≤ 1 →
oneUseJointMutualInformation q = oneUseMutualInformation q)
∧ (∀ q : ℝ, oneUseMutualInformation q =
routedInputOutputEntropy q - routedInputConditionalEntropy q)
∧ (∀ q : ℝ, 0 ≤ q → q ≤ 1 →
oneUseMutualInformation q ≤ Real.log (5 / 4)
∧ (oneUseMutualInformation q = Real.log (5 / 4) ↔ q = 2 / 5))
∧ (∀ q : ℝ, 0 ≤ q → q ≤ 1 →
oneUseJointMutualInformation q ≤ Real.log (5 / 4)
∧ (oneUseJointMutualInformation q = Real.log (5 / 4) ↔ q = 2 / 5))
∧ oneUseMutualInformation (2 / 5) = Real.log (5 / 4)
∧ oneUseJointMutualInformation (2 / 5) = Real.log (5 / 4)
∧ ((∀ n : ℕ, ∀ input : Fin n → Route,
IsFiniteDistribution (blockChannel n input))
∧ (∀ input : Fin 0 → Route, ∀ output : Fin 0 → Bool,
blockChannel 0 input output = 1)
∧ ∀ input : Fin 1 → Route, ∀ output : Fin 1 → Bool,
blockChannel 1 input output = routeChannel (input 0) (output 0)) := by sorry