channel_zero_error_rate
The zero-error capacity rate R_0(W) of a channel W in bits per use is the base-2 logarithm of the Shannon OR-capacity of its distinguishability graph D(W).
Statement
noncomputable def channel_zero_error_rate {A Y : Type*} [Fintype Y] (W : DiscreteMemorylessChannel A Y) : ℝ
- Defined in
- arXiv:2610.41977, Section 5, Equation (5.1); Shannon 1956
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Built on 3
- DiscreteMemorylessChannelA discrete memoryless channel from input alphabet A to finite output alphabet Y is defined by non-negative transition probabilities…
- channel_distinguishability_graphThe distinguishability graph D(W) of a discrete memoryless channel W has inputs as vertices, with two distinct inputs adjacent if and only…
- shannon_or_capacityThe Shannon OR-capacity C_OR(G) of a simple graph G is defined as the supremum over n ≥ 1 of (omega(G^{∨n}))^{1/n}, where omega denotes…
- Used by 1
- proposition_5_1_random_switching_channel_realizationFor any discrete memoryless channels W_G and W_H and any switching probability p ∈ (0, 1), the distinguishability graph of the switched…
Read back from the Lean
Given types A and Y with [Fintype Y], and a discrete memoryless channel W : DiscreteMemorylessChannel A Y (specified by transition probabilities W.prob : A → Y → ℝ that are non-negative and sum to 1 over Y for each a : A), channel_zero_error_rate W is defined as the base-2 logarithm of the Shannon OR-capacity of the channel's distinguishability graph.
Specifically:
1. The distinguishability graph channel_distinguishability_graph W is the simple graph with vertex set A, where two vertices a, a' : A are adjacent if and only if a ≠ a' and their output supports {y : Y | 0 < W.prob a y} and {y : Y | 0 < W.prob a' y} are disjoint.
2. The $n$-th OR-power simple_graph_or_power G n of a graph G is the simple graph on Fin n → A where two sequences x, y are adjacent if and only if there exists some coordinate i : Fin n such that x i and y i are adjacent in G.
3. The Shannon OR-capacity shannon_or_capacity G is the supremum over all n : ℕ satisfying 1 ≤ n of (cliqueNum (simple_graph_or_power G n) : ℝ) ^ (1 / n).
4. channel_zero_error_rate W is Real.logb 2 of this Shannon OR-capacity.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The zero-error capacity rate in bits per use of a discrete memoryless channel W. -/ noncomputable def channel_zero_error_rate {A Y : Type*} [Fintype Y] (W : DiscreteMemorylessChannel A Y) : ℝ := Real.logb 2 (shannon_or_capacity (channel_distinguishability_graph W))