channel_zero_error_code_size
The zero-error code size M_0(W, n) for a channel W in n channel uses is the clique number of the n-th OR-power of its distinguishability graph D(W).
Statement
noncomputable def channel_zero_error_code_size {A Y : Type*} [Fintype Y] (W : DiscreteMemorylessChannel A Y) (n : ℕ) : ℕ
- 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…
- simple_graph_or_powerThe n-th OR-power (co-normal power) G^{∨n} of a simple graph G has vertex set Fin n → V, with an edge between two functions if they are…
- 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
For types A and Y with Y finite ([Fintype Y]), a discrete memoryless channel W : DiscreteMemorylessChannel A Y, and a block length n : ℕ, channel_zero_error_code_size W n is defined as the clique number (SimpleGraph.cliqueNum) of the $n$-th OR-power (co-normal power) of the distinguishability graph of W.
Specifically:
1. The distinguishability graph of W has vertex set A. Two vertices a, a' : A are adjacent if and only if a ≠ a' and their sets of possible channel outputs {y : Y | 0 < W.prob a y} and {y : Y | 0 < W.prob a' y} are disjoint.
2. The $n$-th OR-power of this graph has vertex set Fin n → A (words of length n over A). Two words 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 the distinguishability graph (i.e., x i ≠ y i and their output supports at coordinate i are disjoint).
3. The function returns the maximum size of a clique in this graph (as a natural number).
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 maximum number of zero-error messages in n uses of a channel W is the clique number of the n-th OR-power of its distinguishability graph. -/ noncomputable def channel_zero_error_code_size {A Y : Type*} [Fintype Y] (W : DiscreteMemorylessChannel A Y) (n : ℕ) : ℕ := (simple_graph_or_power (channel_distinguishability_graph W) n).cliqueNum