AFTD Auto-Formalizing Theoretical Domains

channel_distinguishability_graph

def

The distinguishability graph D(W) of a discrete memoryless channel W has inputs as vertices, with two distinct inputs adjacent if and only if their output supports are disjoint.

Statement

def channel_distinguishability_graph {A Y : Type*} [Fintype Y]
    (W : DiscreteMemorylessChannel A Y) : SimpleGraph A
Defined in
arXiv:2610.41977, Section 5, Equation (5.1); Shannon 1956
Verified
07 Nov 2026
Axioms
none listed
Built on 1
  • DiscreteMemorylessChannelA discrete memoryless channel from input alphabet A to finite output alphabet Y is defined by non-negative transition probabilities…
Used by 4

Read back from the Lean

Given types A and Y with Y finite, and a discrete memoryless channel W from A to Y (with transition probability function W.prob : A → Y → ℝ), channel_distinguishability_graph W is the simple graph on vertex type A where two vertices a and a' are adjacent if and only if a ≠ a' and the sets {y : Y | 0 < W.prob a y} and {y : Y | 0 < W.prob a' y} are disjoint (i.e., there is no output y : Y that has strictly positive probability under both input a and input a').

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 distinguishability graph of a discrete memoryless channel has input vertices adjacent when their output supports are disjoint. -/
def channel_distinguishability_graph {A Y : Type*} [Fintype Y]
    (W : DiscreteMemorylessChannel A Y) : SimpleGraph A where
  Adj a a' := a ≠ a' ∧ Disjoint {y : Y | 0 < W.prob a y} {y : Y | 0 < W.prob a' y}
  symm := ⟨fun _ _ ⟨hne, hd⟩ => ⟨hne.symm, hd.symm⟩⟩
  loopless := ⟨fun _ ⟨hne, _⟩ => hne rfl⟩
See it in the graphDiscuss this resultChallenge it