AFTD Auto-Formalizing Theoretical Domains

shannon_or_capacity_categorical_prod_of_min_eq_one

theoremverifiedformalization

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.

  1. 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).

    lines 1–7

    uses SimpleGraph.isClique_singleton, SimpleGraph.IsClique.card_le_cliqueNum

    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
  2. 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.

    lines 11–13

    uses shannon_or_capacity_categorical_prod_le_min, le_antisymm

      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 ?_
  3. 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 ℝ.

    lines 14–15

    uses shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range

      have hbdd := shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range
        (simple_graph_categorical_prod G H)
  4. 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}.

    lines 16–24

    uses ciSup_pos, le_refl, shannon_or_capacity_categorical_prod_of_min_eq_one_cliqueNum_pos, Real.rpow_one

      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
  5. 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.

    line 25

    uses le_trans, le_ciSup

      exact 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

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

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