proposition_5_1_random_switching_channel_realization
For any discrete memoryless channels W_G and W_H and any switching probability p ∈ (0, 1), the distinguishability graph of the switched channel W_sw is the categorical product D(W_G) × D(W_H), the maximum number of zero-error messages in n uses is M_0(W_sw, n) = omega((D(W_G) × D(W_H))^{∨n}), and the zero-error capacity rate is R_0(W_sw) = log_2 C_OR(D(W_G) × D(W_H)), with both quantities independent of p.
Statement
theorem proposition_5_1_random_switching_channel_realization {A B Y Z : Type*} [Fintype Y] [Fintype Z] (W_G : DiscreteMemorylessChannel A Y) (W_H : DiscreteMemorylessChannel B Z) (p : ℝ) (hp0 : 0 < p) (hp1 : p < 1) : channel_distinguishability_graph (random_switching_channel W_G W_H p hp0 hp1) = simple_graph_categorical_prod (channel_distinguishability_graph W_G) (channel_distinguishability_graph W_H) ∧ (∀ n : ℕ, channel_zero_error_code_size (random_switching_channel W_G W_H p hp0 hp1) n = (simple_graph_or_power (simple_graph_categorical_prod (channel_distinguishability_graph W_G) (channel_distinguishability_graph W_H)) n).cliqueNum) ∧ channel_zero_error_rate (random_switching_channel W_G W_H p hp0 hp1) = Real.logb 2 (shannon_or_capacity (simple_graph_categorical_prod (channel_distinguishability_graph W_G) (channel_distinguishability_graph W_H)))
- Formalizes
- arXiv:2610.41977 Proposition 5.1 -- Hedetniemi's conjecture for Shannon OR-capacity: counterexamples and asymptotic separation
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- 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…
- random_switching_channelGiven channels W_G and W_H and switching parameter p ∈ (0, 1), the random switching channel has input pairs (a, b) and tagged outputs in Y…
- channel_zero_error_code_sizeThe 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…
- channel_zero_error_rateThe 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…
- random_switching_distinguishability_graphFor any discrete memoryless channels W_G and W_H and switching parameter p ∈ (0, 1), the distinguishability graph of the random switching…
- simple_graph_categorical_prodThe categorical product (tensor product) G × H of two simple graphs G and H has vertex set V(G) × V(H), with an edge between (u₁, v₁) and…
- 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…
- 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…
Read back from the Lean
Let $A, B$ be types, and let $Y, Z$ be finite types. Let $W_G$ be a discrete memoryless channel from $A$ to $Y$, and $W_H$ be a discrete memoryless channel from $B$ to $Z$. Let $p \in \mathbb{R}$ satisfy $0 < p$ and $p < 1$. Then the following three conditions hold simultaneously: 1. The channel distinguishability graph of the random switching channel between $W_G$ and $W_H$ with parameter $p$ is equal to the categorical (tensor) product of the channel distinguishability graph of $W_G$ and the channel distinguishability graph of $W_H$. 2. For all $n \in \mathbb{N}$, the channel zero-error code size of block length $n$ for the random switching channel equals the clique number of the $n$-th OR power of the categorical product of the distinguishability graphs of $W_G$ and $W_H$. 3. The channel zero-error rate of the random switching channel equals $\log_2$ of the Shannon OR-capacity of the categorical product of the distinguishability graphs of $W_G$ and $W_H$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem shows that randomly switching between two discrete memoryless channels W_G and W_H with probability p ∈ (0, 1) realizes the categorical product of their distinguishability graphs D(W_G) × D(W_H), and that both the zero-error block-code sizes and zero-error capacity rate equal the corresponding graph-theoretic invariants of this product. The proof first applies the known graph equivalence for random switching channels, after which the formulas for code sizes and capacity rate hold immediately by expanding the channel definitions and substituting the product graph.
The distinguishability graph of the switched channel is the categorical product D(W_G) × D(W_H), reducing the theorem to evaluating the block-code sizes and zero-error rate.
The first conjunct of the theorem states that the distinguishability graph of the random switching channel is the categorical product of the distinguishability graphs of W_G and W_H. Providing the existing result `random_switching_distinguishability_graph` proves this first conjunct and splits the goal into two remaining subgoals: code sizes for all blocklengths n, and the zero-error capacity rate.
uses
random_switching_distinguishability_graphrefine ⟨random_switching_distinguishability_graph W_G W_H p hp0 hp1, ?_, ?_⟩For every blocklength n, the maximum zero-error code size for the switched channel is the clique number of the n-th OR-power of D(W_G) × D(W_H).
Fixing an arbitrary blocklength n, the definition `channel_zero_error_code_size` expresses the code size as the clique number of the n-th OR-power of the channel's distinguishability graph. Rewriting with `random_switching_distinguishability_graph` replaces this distinguishability graph with the categorical product D(W_G) × D(W_H), making both sides identical.
uses
channel_zero_error_code_size,random_switching_distinguishability_graph· intro n rw [channel_zero_error_code_size, random_switching_distinguishability_graph]
The zero-error capacity rate of the switched channel is the base-2 logarithm of the Shannon OR-capacity of D(W_G) × D(W_H).
By the definition `channel_zero_error_rate`, the rate is log₂ of the Shannon OR-capacity of the channel's distinguishability graph. Rewriting with `random_switching_distinguishability_graph` substitutes the categorical product D(W_G) × D(W_H) for the distinguishability graph, which matches the target expression.
uses
channel_zero_error_rate,random_switching_distinguishability_graph· rw [channel_zero_error_rate, random_switching_distinguishability_graph]
random_switching_distinguishability_graph- The distinguishability graph of the channel formed by randomly switching between W_G and W_H with parameter p ∈ (0, 1) equals the categorical product of the distinguishability graphs D(W_G) × D(W_H).
channel_zero_error_code_size- The maximum size of a zero-error code of length n on channel W is defined as the clique number of the n-th OR-power of the distinguishability graph D(W).
channel_zero_error_rate- The zero-error capacity rate of channel W is defined as the base-2 logarithm of the Shannon OR-capacity of its distinguishability graph D(W).
- The theorem asserts that the block-code sizes and zero-error rate are independent of the switching probability p; formally, this independence is witnessed by the fact that the right-hand sides of the equations depend only on the individual channels W_G and W_H, and the equalities follow purely by unfolding definitions once the distinguishability graph is identified.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Proposition 5.1: Random switching realizes the categorical product of distinguishability graphs, with block-code sizes and rate independent of p. -/theorem proposition_5_1_random_switching_channel_realization {A B Y Z : Type*} [Fintype Y] [Fintype Z] (W_G : DiscreteMemorylessChannel A Y) (W_H : DiscreteMemorylessChannel B Z) (p : ℝ) (hp0 : 0 < p) (hp1 : p < 1) : channel_distinguishability_graph (random_switching_channel W_G W_H p hp0 hp1) = simple_graph_categorical_prod (channel_distinguishability_graph W_G) (channel_distinguishability_graph W_H) ∧ (∀ n : ℕ, channel_zero_error_code_size (random_switching_channel W_G W_H p hp0 hp1) n = (simple_graph_or_power (simple_graph_categorical_prod (channel_distinguishability_graph W_G) (channel_distinguishability_graph W_H)) n).cliqueNum) ∧ channel_zero_error_rate (random_switching_channel W_G W_H p hp0 hp1) = Real.logb 2 (shannon_or_capacity (simple_graph_categorical_prod (channel_distinguishability_graph W_G) (channel_distinguishability_graph W_H))) := by refine ⟨random_switching_distinguishability_graph W_G W_H p hp0 hp1, ?_, ?_⟩ · intro n rw [channel_zero_error_code_size, random_switching_distinguishability_graph] · rw [channel_zero_error_rate, random_switching_distinguishability_graph]