AFTD Auto-Formalizing Theoretical Domains

random_switching_distinguishability_graph

theoremverified

For any discrete memoryless channels W_G and W_H and switching parameter p ∈ (0, 1), the distinguishability graph of the random switching channel is the categorical product D(W_G) × D(W_H).

Statement

theorem random_switching_distinguishability_graph {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)
Source
arXiv:2610.41977, Proposition 5.1, Equation (5.2)
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • 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…
Used by 1

Read back from the Lean

For any types A and B, and any finite types Y and Z, let W_G be a discrete memoryless channel from A to Y and W_H be a discrete memoryless channel from B to Z. For any real number p satisfying 0 < p and p < 1, the 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 distinguishability graph of W_G and the distinguishability graph of 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

To show that the distinguishability graph of a random switching channel W is the categorical product D(W_G) × D(W_H), we reduce graph equality to the equivalence of adjacency by extensionality. Adjacency in the switching channel requires distinct inputs with disjoint output distributions. Since the output support of W on (a, b) is the union of the injected supports of W_G(a) and W_H(b), two pairs have disjoint supports in W if and only if both component pairs have disjoint supports in W_G and W_H. Finally, nonemptiness of channel supports ensures that disjoint supports imply distinctness of the component inputs, matching the definition of the categorical product graph.

  1. Every channel input has at least one output symbol with strictly positive probability.

    Suppose, for contradiction, that no output symbol has positive transition probability for an input a, so W(y | a) ≤ 0 for all y. Since transition probabilities are non-negative, every W(y | a) must equal 0 by le_antisymm. By Finset.sum_eq_zero, the sum of probabilities over all outputs is 0, which contradicts the channel requirement that probabilities sum to 1.

    lines 6–12

    uses Finset.sum_eq_zero, le_antisymm

      by_contra h
      push Not at h
      have h0 : ∑ y, W.prob a y = 0 := by
        apply Finset.sum_eq_zero
        intro y _
        exact le_antisymm (h y) (W.prob_nonneg a y)
      linarith [W.prob_sum a]
  2. An output of the form inl(y) has positive probability under the switching channel for input (a, b) if and only if y is in the support of W_G(a).

    We inspect an output x in the sum type Y ⊕ Z. When x = inl(y), the switching channel assigns probability p * W_G(a, y). Since p > 0, mul_pos_iff_of_pos_left shows this product is positive exactly when W_G(a, y) > 0. Hence inl(y) belongs to the support of the switching channel if and only if it belongs to the inl-image of the support of W_G(a). The inr-image component cannot contain inl(y) because the constructors inl and inr are disjoint.

    lines 20–36

    uses mem_ofPred_eq, mem_union, mul_pos_iff_of_pos_left, mem_image_of_mem, Set.mem_image

      ext x
      cases x with
      | inl y =>
        rw [mem_ofPred_eq, mem_union]
        constructor
        · intro h
          left
          simp only [random_switching_channel, mul_pos_iff_of_pos_left hp0] at h
          exact mem_image_of_mem Sum.inl h
        · rintro (h | h)
          · rcases (Set.mem_image Sum.inl _ _).mp h with ⟨y', hy', hEq⟩
            injection hEq with hEq'
            rw [hEq'] at hy'
            simp only [random_switching_channel, mul_pos_iff_of_pos_left hp0]
            exact hy'
          · rcases (Set.mem_image Sum.inr _ _).mp h with ⟨z, hz, hz'⟩
            exact absurd hz' (by simp)
  3. An output of the form inr(z) has positive probability under the switching channel for input (a, b) if and only if z is in the support of W_H(b).

    When x = inr(z), the switching channel assigns probability (1 - p) * W_H(b, z). Since p < 1, 1 - p > 0, so the probability is positive exactly when W_H(b, z) > 0. Thus inr(z) is in the support of the switching channel if and only if it belongs to the inr-image of the support of W_H(b). Combining this with the inl case establishes that the full support for input (a, b) is the union of the inl-image of supp(W_G(a)) and the inr-image of supp(W_H(b)).

    lines 38–56

    uses mem_ofPred_eq, mem_union, mem_image_of_mem, mul_pos_iff_of_pos_left, Set.mem_image

        rw [mem_ofPred_eq, mem_union]
        constructor
        · intro h
          right
          simp only [random_switching_channel] at h
          exact mem_image_of_mem Sum.inr (by
            rw [mul_pos_iff_of_pos_left] at h
            · exact h
            · linarith)
        · rintro (h | h)
          · rcases (Set.mem_image Sum.inl _ _).mp h with ⟨y', hy', hy'⟩
            exact absurd hy' (by simp)
          · rcases (Set.mem_image Sum.inr _ _).mp h with ⟨z', hz', hEq⟩
            injection hEq with hEq'
            rw [hEq'] at hz'
            simp only [random_switching_channel]
            rw [mul_pos_iff_of_pos_left]
            · exact hz'
            · linarith
  4. Two input pairs have disjoint output supports in the random switching channel if and only if both component inputs have disjoint supports in W_G and W_H.

    Rewriting both supports using random_switching_distinguishability_graph_support_eq expresses each support as a union of an inl-image and an inr-image. Distributing disjointness over unions produces four pairwise conditions via Set.disjoint_union_left and Set.disjoint_union_right. The cross terms between inl and inr images are disjoint by Set.disjoint_image_inl_image_inr, and the remaining terms simplify by injectivity of inl and inr (Set.disjoint_image_iff) to disjointness of the original supports in W_G and W_H.

    lines 66–70

    uses random_switching_distinguishability_graph_support_eq, Set.disjoint_union_left, Set.disjoint_union_right, Set.disjoint_image_iff, Sum.inl_injective, Sum.inr_injective, Set.disjoint_image_inl_image_inr, and_true, true_and

      rw [random_switching_distinguishability_graph_support_eq W_G W_H p hp0 hp1 ab,
        random_switching_distinguishability_graph_support_eq W_G W_H p hp0 hp1 ab']
      rw [Set.disjoint_union_left, Set.disjoint_union_right, Set.disjoint_union_right]
      rw [Set.disjoint_image_iff Sum.inl_injective, Set.disjoint_image_iff Sum.inr_injective]
      simp only [Set.disjoint_image_inl_image_inr, Set.disjoint_image_inl_image_inr.symm, and_true, true_and]
  5. To show graph equality, it suffices to prove that two input pairs u, v are adjacent in the switching channel distinguishability graph if and only if they are adjacent in the categorical product graph.

    By graph extensionality (SimpleGraph.ext) and functional extensionality, two graphs are identical if their adjacency relations agree on all pairs u, v. Unfolding the definitions of channel_distinguishability_graph and simple_graph_categorical_prod, the goal reduces via propext to showing that (u ≠ v with disjoint switching channel supports) is equivalent to (u.1 ≠ v.1 with disjoint supports in W_G) and (u.2 ≠ v.2 with disjoint supports in W_H).

    lines 79–83

    uses SimpleGraph.ext, propext

      apply SimpleGraph.ext
      funext u v
      apply propext
      simp only [channel_distinguishability_graph, simple_graph_categorical_prod]
      constructor
  6. Adjacency in the switching channel distinguishability graph implies adjacency in the categorical product graph.

    Given u ≠ v and disjoint switching channel supports, random_switching_distinguishability_graph_disj yields disjoint supports in both W_G and W_H. If u.1 = v.1, the support of W_G(u.1) would be disjoint from itself; but by random_switching_distinguishability_graph_support_nonempty, this support is nonempty, which would mean an element is both in the set and not in the set (Set.disjoint_left.mp), a contradiction. The same nonemptiness argument shows u.2 ≠ v.2, proving adjacency in the categorical product.

    lines 84–94

    uses random_switching_distinguishability_graph_disj, random_switching_distinguishability_graph_support_nonempty, Set.disjoint_left.mp

      · rintro ⟨hne, hdisj⟩
        obtain ⟨hdG, hdH⟩ := (random_switching_distinguishability_graph_disj W_G W_H p hp0 hp1 u v).mp hdisj
        refine ⟨⟨?_, hdG⟩, ⟨?_, hdH⟩⟩
        · intro h
          rw [← h] at hdG
          obtain ⟨y, hy⟩ := random_switching_distinguishability_graph_support_nonempty W_G u.1
          exact (Set.disjoint_left.mp hdG hy) hy
        · intro h
          rw [← h] at hdH
          obtain ⟨z, hz⟩ := random_switching_distinguishability_graph_support_nonempty W_H u.2
          exact (Set.disjoint_left.mp hdH hz) hz
  7. Adjacency in the categorical product graph implies adjacency in the switching channel distinguishability graph.

    Assuming adjacency in both components, we have u.1 ≠ v.1, u.2 ≠ v.2, and disjoint supports in both W_G and W_H. By random_switching_distinguishability_graph_disj, the switching channel output supports are disjoint. Furthermore, u ≠ v must hold because if u = v, projecting to the first component via congrArg Prod.fst would give u.1 = v.1, contradicting u.1 ≠ v.1.

    lines 95–98

    uses random_switching_distinguishability_graph_disj, congrArg

      · rintro ⟨⟨hne1, hdG⟩, ⟨hne2, hdH⟩⟩
        refine ⟨?_, (random_switching_distinguishability_graph_disj W_G W_H p hp0 hp1 u v).mpr ⟨hdG, hdH⟩⟩
        intro h
        exact hne1 (congrArg Prod.fst h)
Finset.sum_eq_zero
A finite sum of terms is zero if every term in the sum is zero.
le_antisymm
If a ≤ b and b ≤ a in a partial order, then a = b.
mem_ofPred_eq
An element belongs to a set-builder comprehension if and only if it satisfies the defining predicate.
mem_union
An element belongs to the union of two sets if and only if it belongs to at least one of them.
mul_pos_iff_of_pos_left
Multiplying by a strictly positive number preserves whether a quantity is strictly positive.
mem_image_of_mem
If an element belongs to a set, its image under a function belongs to the image of the set.
Set.mem_image
An element is in the image of a set under a function if and only if it is the value of the function at some element of the set.
random_switching_distinguishability_graph_support_eq
The support of the output distribution of the random switching channel on an input pair is the union of the left-injected support of the first channel and the right-injected support of the second channel.
Set.disjoint_union_left
A union of two sets is disjoint from a third set if and only if both sets are individually disjoint from the third.
Set.disjoint_union_right
A set is disjoint from a union of two sets if and only if it is disjoint from each of them individually.
Set.disjoint_image_iff
An injective function preserves and reflects disjointness of sets under forward images.
Sum.inl_injective
The left injection Sum.inl into a sum type is injective.
Sum.inr_injective
The right injection Sum.inr into a sum type is injective.
Set.disjoint_image_inl_image_inr
The image of any set under Sum.inl is disjoint from the image of any set under Sum.inr.
and_true
Conjunction of a proposition with True simplifies to the proposition itself.
true_and
Conjunction of True with a proposition simplifies to the proposition itself.
SimpleGraph.ext
Two simple graphs on the same vertex type are equal if their adjacency relations are equal.
propext
Propositional extensionality: two propositions are equal if and only if they are logically equivalent.
random_switching_distinguishability_graph_disj
Two inputs to a random switching channel have disjoint output supports if and only if their respective component inputs have disjoint supports in both underlying channels.
random_switching_distinguishability_graph_support_nonempty
For any input to a discrete memoryless channel, there is at least one output symbol with strictly positive probability.
Set.disjoint_left.mp
If two sets are disjoint, any element in the first set cannot belong to the second set.
congrArg
Applying a function to equal inputs yields equal outputs.

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

open Setprivate lemma random_switching_distinguishability_graph_support_nonempty    {A Y : Type*} [Fintype Y] (W : DiscreteMemorylessChannel A Y) (a : A) :    ∃ y, 0 < W.prob a y := by  by_contra h  push Not at h  have h0 : ∑ y, W.prob a y = 0 := by    apply Finset.sum_eq_zero    intro y _    exact le_antisymm (h y) (W.prob_nonneg a y)  linarith [W.prob_sum a]private lemma random_switching_distinguishability_graph_support_eq    {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) (ab : A × B) :    {x : Y ⊕ Z | 0 < (random_switching_channel W_G W_H p hp0 hp1).prob ab x}      = Sum.inl '' {y : Y | 0 < W_G.prob ab.1 y} ∪ Sum.inr '' {z : Z | 0 < W_H.prob ab.2 z} := by  ext x  cases x with  | inl y =>    rw [mem_ofPred_eq, mem_union]    constructor    · intro h      left      simp only [random_switching_channel, mul_pos_iff_of_pos_left hp0] at h      exact mem_image_of_mem Sum.inl h    · rintro (h | h)      · rcases (Set.mem_image Sum.inl _ _).mp h with ⟨y', hy', hEq⟩        injection hEq with hEq'        rw [hEq'] at hy'        simp only [random_switching_channel, mul_pos_iff_of_pos_left hp0]        exact hy'      · rcases (Set.mem_image Sum.inr _ _).mp h with ⟨z, hz, hz'⟩        exact absurd hz' (by simp)  | inr z =>    rw [mem_ofPred_eq, mem_union]    constructor    · intro h      right      simp only [random_switching_channel] at h      exact mem_image_of_mem Sum.inr (by        rw [mul_pos_iff_of_pos_left] at h        · exact h        · linarith)    · rintro (h | h)      · rcases (Set.mem_image Sum.inl _ _).mp h with ⟨y', hy', hy'⟩        exact absurd hy' (by simp)      · rcases (Set.mem_image Sum.inr _ _).mp h with ⟨z', hz', hEq⟩        injection hEq with hEq'        rw [hEq'] at hz'        simp only [random_switching_channel]        rw [mul_pos_iff_of_pos_left]        · exact hz'        · linarithprivate lemma random_switching_distinguishability_graph_disj    {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) (ab ab' : A × B) :    Disjoint {x : Y ⊕ Z | 0 < (random_switching_channel W_G W_H p hp0 hp1).prob ab x}        {x : Y ⊕ Z | 0 < (random_switching_channel W_G W_H p hp0 hp1).prob ab' x} ↔      Disjoint {y : Y | 0 < W_G.prob ab.1 y} {y : Y | 0 < W_G.prob ab'.1 y} ∧        Disjoint {z : Z | 0 < W_H.prob ab.2 z} {z : Z | 0 < W_H.prob ab'.2 z} := by  rw [random_switching_distinguishability_graph_support_eq W_G W_H p hp0 hp1 ab,    random_switching_distinguishability_graph_support_eq W_G W_H p hp0 hp1 ab']  rw [Set.disjoint_union_left, Set.disjoint_union_right, Set.disjoint_union_right]  rw [Set.disjoint_image_iff Sum.inl_injective, Set.disjoint_image_iff Sum.inr_injective]  simp only [Set.disjoint_image_inl_image_inr, Set.disjoint_image_inl_image_inr.symm, and_true, true_and]/-- The distinguishability graph of a random switching channel is the categorical product of the component distinguishability graphs. -/theorem random_switching_distinguishability_graph {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) := by  apply SimpleGraph.ext  funext u v  apply propext  simp only [channel_distinguishability_graph, simple_graph_categorical_prod]  constructor  · rintro ⟨hne, hdisj⟩    obtain ⟨hdG, hdH⟩ := (random_switching_distinguishability_graph_disj W_G W_H p hp0 hp1 u v).mp hdisj    refine ⟨⟨?_, hdG⟩, ⟨?_, hdH⟩⟩    · intro h      rw [← h] at hdG      obtain ⟨y, hy⟩ := random_switching_distinguishability_graph_support_nonempty W_G u.1      exact (Set.disjoint_left.mp hdG hy) hy    · intro h      rw [← h] at hdH      obtain ⟨z, hz⟩ := random_switching_distinguishability_graph_support_nonempty W_H u.2      exact (Set.disjoint_left.mp hdH hz) hz  · rintro ⟨⟨hne1, hdG⟩, ⟨hne2, hdH⟩⟩    refine ⟨?_, (random_switching_distinguishability_graph_disj W_G W_H p hp0 hp1 u v).mpr ⟨hdG, hdH⟩⟩    intro h    exact hne1 (congrArg Prod.fst h)
See it in the graphDiscuss this resultChallenge it