AFTD Auto-Formalizing Theoretical Domains

channel_zero_error_rate

def

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

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))
See it in the graphDiscuss this resultChallenge it