AFTD Auto-Formalizing Theoretical Domains

channel_zero_error_code_size

def

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

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