shannon_or_capacity_categorical_prod_of_min_eq_one
For any finite nonempty simple graphs G and H, if the minimum of their Shannon OR-capacities is 1, then the Shannon OR-capacity of their categorical product G × H is 1.
Statement
theorem shannon_or_capacity_categorical_prod_of_min_eq_one {V W : Type*} [Fintype V] [Nonempty V] [Fintype W] [Nonempty W] (G : SimpleGraph V) (H : SimpleGraph W) (h : min (shannon_or_capacity G) (shannon_or_capacity H) = 1) : shannon_or_capacity (simple_graph_categorical_prod G H) = 1
- Formalizes
- arXiv:2610.41977 Sec. 6
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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_capacity_categorical_prod_le_minFor any finite nonempty simple graphs G and H, the Shannon OR-capacity of their categorical product G × H is at most the minimum of the…
- 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…
- 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 $V$ and $W$ be finite, nonempty types, and let $G$ be a simple graph on $V$ and $H$ be a simple graph on $W$. If the minimum of the Shannon OR-capacity of $G$ and the Shannon OR-capacity of $H$ equals $1$, then the Shannon OR-capacity of the categorical product of $G$ and $H$ also equals $1$.
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 Shannon OR-capacity of the categorical product G × H is bounded above by min(c_OR(G), c_OR(H)), which is assumed to be 1. To prove equality, it suffices by antisymmetry to show that the capacity is at least 1. Because the Shannon capacity is defined as the supremum over n ≥ 1 of (ω((G × H)^{\lor n}))^{1/n}, it is bounded below by the term at n = 1, which equals the clique number ω((G × H)^{\lor 1}). Since any nonempty graph contains at least one vertex and thus a 1-clique, this clique number is at least 1, establishing the lower bound.
The clique number of any finite nonempty simple graph is at least 1
Since the vertex type α is nonempty, there is at least one vertex a. The singleton set {a} forms a clique (by SimpleGraph.isClique_singleton), and the size of any clique is bounded above by the graph's clique number (by SimpleGraph.IsClique.card_le_cliqueNum). Since |{a}| = 1, we obtain 1 ≤ ω(P).
uses
SimpleGraph.isClique_singleton,SimpleGraph.IsClique.card_le_cliqueNumprivate lemma shannon_or_capacity_categorical_prod_of_min_eq_one_cliqueNum_pos {α : Type*} [Fintype α] [Nonempty α] (P : SimpleGraph α) : 1 ≤ P.cliqueNum := by obtain ⟨a⟩ := ‹Nonempty α› have hcl : P.IsClique (↑({a} : Finset α)) := by simpa using SimpleGraph.isClique_singleton (G := P) a have hcard := SimpleGraph.IsClique.card_le_cliqueNum (G := P) (t := ({a} : Finset α)) (tc := hcl) simpa using hcard
The Shannon OR-capacity of G × H is at most 1, so it suffices to show that 1 ≤ c_OR(G × H)
By shannon_or_capacity_categorical_prod_le_min, the capacity of the categorical product is at most min(c_OR(G), c_OR(H)), which equals 1 by assumption h. By antisymmetry of ≤ (le_antisymm), proving the reverse inequality 1 ≤ c_OR(G × H) suffices to establish equality.
uses
shannon_or_capacity_categorical_prod_le_min,le_antisymmhave hle : shannon_or_capacity (simple_graph_categorical_prod G H) ≤ 1 := by simpa [h] using shannon_or_capacity_categorical_prod_le_min G H refine le_antisymm hle ?_
The sequence defining the Shannon OR-capacity of G × H is bounded above
We apply shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range to the product graph G × H to establish that the set of values (ω((G × H)^{\lor n}))^{1/n} for n ≥ 1 is bounded above in ℝ.
uses
shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_rangehave hbdd := shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range (simple_graph_categorical_prod G H)The n = 1 term in the capacity supremum is at least 1
Since 1 ≤ 1 holds reflexively (le_refl), the supremum over the condition 1 ≤ 1 collapses to the value at n = 1 by ciSup_pos. The exponent (1:ℝ)/1 simplifies to 1, and x^1 = x by Real.rpow_one. By the helper lemma shannon_or_capacity_categorical_prod_of_min_eq_one_cliqueNum_pos applied to (G × H)^{\lor 1}, its clique number is at least 1, which after casting to ℝ gives 1 ≤ (ω((G × H)^{\lor 1}))^{1/1}.
uses
ciSup_pos,le_refl,shannon_or_capacity_categorical_prod_of_min_eq_one_cliqueNum_pos,Real.rpow_onehave hterm : (1:ℝ) ≤ ⨆ (_ : 1 ≤ (1:ℕ)), ((simple_graph_or_power (simple_graph_categorical_prod G H) 1).cliqueNum : ℝ) ^ ((1:ℝ)/↑(1:ℕ)) := by rw [ciSup_pos (le_refl 1)] have hcl' : 1 ≤ (simple_graph_or_power (simple_graph_categorical_prod G H) 1).cliqueNum := shannon_or_capacity_categorical_prod_of_min_eq_one_cliqueNum_pos _ have hcl : (1:ℝ) ≤ ((simple_graph_or_power (simple_graph_categorical_prod G H) 1).cliqueNum : ℝ) := by exact_mod_cast hcl' rw [show (1:ℝ)/↑(1:ℕ) = 1 by norm_num, Real.rpow_one] exact hcl
The Shannon OR-capacity of G × H is equal to 1
Since the sequence is bounded above, each term is at most the supremum over all n by le_ciSup; in particular, this holds for n = 1. By transitivity (le_trans), combining 1 ≤ (term at n = 1) and (term at n = 1) ≤ c_OR(G × H) gives 1 ≤ c_OR(G × H), completing the proof.
uses
le_trans,le_ciSupexact le_trans hterm (le_ciSup hbdd 1)
SimpleGraph.isClique_singleton- in any simple graph, any singleton set of vertices forms a clique
SimpleGraph.IsClique.card_le_cliqueNum- the cardinality of any clique in a finite simple graph is at most the graph's clique number
shannon_or_capacity_categorical_prod_le_min- the Shannon OR-capacity of the categorical product of two finite nonempty graphs is at most the minimum of their individual Shannon OR-capacities
le_antisymm- in a partial order, if a ≤ b and b ≤ a, then a = b
shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range- the sequence of n-th root clique numbers of OR-powers defining the Shannon OR-capacity of a finite nonempty graph is bounded above
ciSup_pos- in a conditionally complete lattice, the supremum over a true proposition reduces to the value at that true proposition
le_refl- every element in a preorder is less than or equal to itself
shannon_or_capacity_categorical_prod_of_min_eq_one_cliqueNum_pos- every finite nonempty simple graph has clique number at least 1
Real.rpow_one- any real number raised to the power 1 equals itself
le_trans- if a ≤ b and b ≤ c in a preorder, then a ≤ c
le_ciSup- any element of an indexed family that is bounded above is at most the conditional supremum of that family
- The definition of Shannon capacity as a supremum over 1 ≤ n uses Lean's conditionally complete lattice supremum (`ciSup`), which requires an explicit proof that the sequence is bounded above (`hbdd`) and that the condition 1 ≤ 1 holds (`le_refl 1`).
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.
private lemma shannon_or_capacity_categorical_prod_of_min_eq_one_cliqueNum_pos {α : Type*} [Fintype α] [Nonempty α] (P : SimpleGraph α) : 1 ≤ P.cliqueNum := by obtain ⟨a⟩ := ‹Nonempty α› have hcl : P.IsClique (↑({a} : Finset α)) := by simpa using SimpleGraph.isClique_singleton (G := P) a have hcard := SimpleGraph.IsClique.card_le_cliqueNum (G := P) (t := ({a} : Finset α)) (tc := hcl) simpa using hcard/-- Hedetniemi's identity for Shannon OR-capacity holds when the smaller factor capacity is one. -/theorem shannon_or_capacity_categorical_prod_of_min_eq_one {V W : Type*} [Fintype V] [Nonempty V] [Fintype W] [Nonempty W] (G : SimpleGraph V) (H : SimpleGraph W) (h : min (shannon_or_capacity G) (shannon_or_capacity H) = 1) : shannon_or_capacity (simple_graph_categorical_prod G H) = 1 := by have hle : shannon_or_capacity (simple_graph_categorical_prod G H) ≤ 1 := by simpa [h] using shannon_or_capacity_categorical_prod_le_min G H refine le_antisymm hle ?_ have hbdd := shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range (simple_graph_categorical_prod G H) have hterm : (1:ℝ) ≤ ⨆ (_ : 1 ≤ (1:ℕ)), ((simple_graph_or_power (simple_graph_categorical_prod G H) 1).cliqueNum : ℝ) ^ ((1:ℝ)/↑(1:ℕ)) := by rw [ciSup_pos (le_refl 1)] have hcl' : 1 ≤ (simple_graph_or_power (simple_graph_categorical_prod G H) 1).cliqueNum := shannon_or_capacity_categorical_prod_of_min_eq_one_cliqueNum_pos _ have hcl : (1:ℝ) ≤ ((simple_graph_or_power (simple_graph_categorical_prod G H) 1).cliqueNum : ℝ) := by exact_mod_cast hcl' rw [show (1:ℝ)/↑(1:ℕ) = 1 by norm_num, Real.rpow_one] exact hcl exact le_trans hterm (le_ciSup hbdd 1)