AFTD Auto-Formalizing Theoretical Domains

shannon_or_capacity_categorical_prod_of_min_eq_two

theoremverifiedformalization

For any finite nonempty simple graphs G and H, if the minimum of their Shannon OR-capacities is 2, then the Shannon OR-capacity of their categorical product G × H is 2.

Statement

theorem shannon_or_capacity_categorical_prod_of_min_eq_two {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) = 2) : shannon_or_capacity (simple_graph_categorical_prod G H) = 2
Formalizes
arXiv:2610.41977 Sec. 6
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • 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…
  • 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…

Read back from the Lean

For any two finite, nonempty types $V$ and $W$, and any simple graphs $G$ on $V$ and $H$ on $W$, if the minimum of the Shannon OR-capacity of $G$ and the Shannon OR-capacity of $H$ is equal to $2$, then the Shannon OR-capacity of the categorical (tensor) product graph $G \times H$ is also equal to $2$.

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 proof establishes that C_OR(G × H) = 2 by sandwiching it between 2 and min(C_OR(G), C_OR(H)) = 2. The upper bound C_OR(G × H) ≤ min(C_OR(G), C_OR(H)) = 2 follows from the general categorical product inequality. For the lower bound, any graph with no edges has capacity at most 1, so the condition min(C_OR(G), C_OR(H)) = 2 forces both G and H to have at least one edge; these edges pair up to form an edge in G × H, which provides a 2-clique in its first OR-power and guarantees C_OR(G × H) ≥ 2.

  1. A finite graph with no edges has clique number at most 1.

    Let s be a maximum clique of G, so that |s| = ω(G). Suppose for contradiction that |s| > 1. Then by Finset.one_lt_card.mp, s contains two distinct vertices a ≠ b. Since s is a clique, a and b must be adjacent in G, contradicting the hypothesis that G has no edges.

    lines 4–9

    uses Finset.one_lt_card.mp

      obtain ⟨s, hs, hcard⟩ := G.exists_isNClique_cliqueNum
      rw [← hcard]
      by_contra hlt
      push Not at hlt
      obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp hlt
      exact h a b (hs ha hb hab)
  2. A finite nonempty graph with no edges has Shannon OR-capacity at most 1.

    Unfolding the definition of Shannon OR-capacity, it suffices by ciSup_le to show that each term indexed by n is at most 1. If 1 ≤ n, two tuples in the n-th OR-power G^{\lor n} are adjacent if and only if they are adjacent at some coordinate; since G has no edges, G^{\lor n} also has no edges. By the previous lemma, the clique number of G^{\lor n} is at most 1, and raising it to the power 1/n yields at most 1 by Real.rpow_le_one. The case n = 0 is degenerate and handled trivially by simp.

    lines 14–27

    uses ciSup_le, ciSup_pos, shannon_or_capacity_categorical_prod_of_min_eq_two_cliqueNum_le_one, Real.rpow_le_one

      unfold shannon_or_capacity
      apply ciSup_le
      intro n
      by_cases hn : 1 ≤ n
      · rw [ciSup_pos hn]
        have hno : ∀ x y : Fin n → V, ¬ (simple_graph_or_power G n).Adj x y := by
          intro x y hxy
          obtain ⟨i, hi⟩ := hxy
          exact h (x i) (y i) hi
        have hcl : (simple_graph_or_power G n).cliqueNum ≤ 1 :=
          shannon_or_capacity_categorical_prod_of_min_eq_two_cliqueNum_le_one _ hno
        have hclr : ((simple_graph_or_power G n).cliqueNum : ℝ) ≤ 1 := by exact_mod_cast hcl
        exact Real.rpow_le_one (by positivity) hclr (by positivity)
      · simp [hn]
  3. If G contains an edge, the first OR-power of G has clique number at least 2.

    Given an edge u ~ v in G, consider the two constant functions in Fin 1 → V taking value u and v respectively. Since u ~ v, u ≠ v by G.ne_of_adj, so these two functions are distinct, and their pair set has size 2 by Finset.card_pair. Because their values at coordinate 0 are adjacent, they form a 2-clique in the first OR-power of G, establishing that ω(G^{\lor 1}) ≥ 2.

    lines 32–48

    uses Finset.card_pair, congrFun

      classical
      have hcl : 2 ≤ (simple_graph_or_power G 1).cliqueNum := by
        have hc : (simple_graph_or_power G 1).IsClique
            ({(fun _ : Fin 1 => u), (fun _ : Fin 1 => v)} : Finset (Fin 1 → V)) := by
          intro a ha b hb hab
          simp at ha hb
          rcases ha with rfl | rfl <;> rcases hb with rfl | rfl
          · exact absurd rfl hab
          · exact ⟨0, h⟩
          · exact ⟨0, (G.adj_comm v u).mpr h⟩
          · exact absurd rfl hab
        have hcard : ({(fun _ : Fin 1 => u), (fun _ : Fin 1 => v)} : Finset (Fin 1 → V)).card = 2 := by
          rw [Finset.card_pair]
          intro heq
          exact G.ne_of_adj h (congrFun heq 0)
        have := hc.card_le_cliqueNum
        rwa [hcard] at this
  4. If G contains an edge, its Shannon OR-capacity is at least 2.

    In the definition of Shannon OR-capacity, the term for n = 1 evaluates to ω(G^{\lor 1})^{1/1} = ω(G^{\lor 1}) ≥ 2, using Real.rpow_one. Because the sequence of powers is bounded above (by shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range), this term is bounded by the supremum via le_ciSup, so 2 ≤ C_OR(G) by transitivity.

    lines 49–56

    uses ciSup_pos, le_refl, Real.rpow_one, shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range, le_trans, le_ciSup

      unfold shannon_or_capacity
      have hclr : (2:ℝ) ≤ ((simple_graph_or_power G 1).cliqueNum : ℝ) := by exact_mod_cast hcl
      have hterm : (2:ℝ) ≤ ⨆ (_ : 1 ≤ (1:ℕ)), ((simple_graph_or_power G 1).cliqueNum : ℝ) ^ ((1:ℝ)/↑(1:ℕ)) := by
        rw [ciSup_pos (le_refl 1)]
        rw [show (1:ℝ)/↑(1:ℕ) = 1 by norm_num, Real.rpow_one]
        exact hclr
      have hbdd := shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range G
      exact le_trans hterm (le_ciSup hbdd 1)
  5. Both G and H have Shannon OR-capacity at least 2.

    Since min(C_OR(G), C_OR(H)) = 2, the standard inequalities min_le_left and min_le_right immediately imply 2 ≤ C_OR(G) and 2 ≤ C_OR(H).

    lines 60–61

    uses min_le_left, min_le_right

      have hG : 2 ≤ shannon_or_capacity G := by rw [← h]; exact min_le_left _ _
      have hH : 2 ≤ shannon_or_capacity H := by rw [← h]; exact min_le_right _ _
  6. Both G and H contain at least one edge.

    Suppose for contradiction that G had no edges. Then by shannon_or_capacity_categorical_prod_of_min_eq_two_le_one_of_no_adj, C_OR(G) ≤ 1, which contradicts 2 ≤ C_OR(G). Thus G has an edge u ~ v. Symmetrically, H has an edge x ~ y.

    lines 62–73

    uses shannon_or_capacity_categorical_prod_of_min_eq_two_le_one_of_no_adj

      have hedgeG : ∃ u v : V, G.Adj u v := by
        by_contra hne
        push Not at hne
        have hle := shannon_or_capacity_categorical_prod_of_min_eq_two_le_one_of_no_adj G hne
        linarith
      obtain ⟨u, v, huv⟩ := hedgeG
      have hedgeH : ∃ x y : W, H.Adj x y := by
        by_contra hne
        push Not at hne
        have hle := shannon_or_capacity_categorical_prod_of_min_eq_two_le_one_of_no_adj H hne
        linarith
      obtain ⟨x, y, hxy⟩ := hedgeH
  7. The Shannon OR-capacity of the categorical product G × H is at least 2.

    The pairs (u, x) and (v, y) form an edge in G × H because u ~ v in G and x ~ y in H. Since G × H contains an edge, shannon_or_capacity_categorical_prod_of_min_eq_two_two_le_of_adj implies 2 ≤ C_OR(G × H).

    lines 74–76

    uses shannon_or_capacity_categorical_prod_of_min_eq_two_two_le_of_adj

      have hadj : (simple_graph_categorical_prod G H).Adj (u, x) (v, y) := ⟨huv, hxy⟩
      have hlower : 2 ≤ shannon_or_capacity (simple_graph_categorical_prod G H) :=
        shannon_or_capacity_categorical_prod_of_min_eq_two_two_le_of_adj _ hadj
  8. The Shannon OR-capacity of the categorical product G × H is at most 2.

    By the general upper bound shannon_or_capacity_categorical_prod_le_min, C_OR(G × H) ≤ min(C_OR(G), C_OR(H)). Substituting min(C_OR(G), C_OR(H)) = 2 yields C_OR(G × H) ≤ 2.

    lines 77–80

    uses shannon_or_capacity_categorical_prod_le_min

      have hupper : shannon_or_capacity (simple_graph_categorical_prod G H) ≤ 2 := by
        have hle := shannon_or_capacity_categorical_prod_le_min G H
        rw [h] at hle
        exact hle
  9. The Shannon OR-capacity of the categorical product G × H equals 2. automation

    Linear arithmetic over ℝ combines the inequalities 2 ≤ C_OR(G × H) and C_OR(G × H) ≤ 2 to conclude C_OR(G × H) = 2.

    line 81

      linarith
Finset.one_lt_card.mp
A finite set has cardinality strictly greater than 1 if and only if it contains two distinct elements.
ciSup_le
The supremum of an indexed family in a conditionally complete lattice is at most c if every term in the family is at most c.
ciSup_pos
The supremum over a true proposition p evaluates to the value of the function at the proof of p.
shannon_or_capacity_categorical_prod_of_min_eq_two_cliqueNum_le_one
A finite simple graph with no edges has clique number at most 1.
Real.rpow_le_one
For non-negative real numbers x and z, if x ≤ 1 then x^z ≤ 1.
Finset.card_pair
A pair set {a, b} has cardinality 2 if and only if a ≠ b.
congrFun
If two functions are equal, then they take the same value at any given argument.
le_refl
The preorder relation ≤ is reflexive: a ≤ a for any a.
Real.rpow_one
Any real number raised to the power 1 equals itself.
shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range
The sequence of n-th root clique numbers of the OR-powers defining the Shannon OR-capacity is bounded above.
le_trans
The preorder relation ≤ is transitive: if a ≤ b and b ≤ c, then a ≤ c.
le_ciSup
In a conditionally complete lattice, any element of a family is at most the supremum of the family, provided the family is bounded above.
min_le_left
The minimum of two elements a and b is less than or equal to a.
min_le_right
The minimum of two elements a and b is less than or equal to b.
shannon_or_capacity_categorical_prod_of_min_eq_two_le_one_of_no_adj
If a finite nonempty simple graph has no edges, its Shannon OR-capacity is at most 1.
shannon_or_capacity_categorical_prod_of_min_eq_two_two_le_of_adj
If a finite nonempty simple graph contains at least one edge, its Shannon OR-capacity is at least 2.
shannon_or_capacity_categorical_prod_le_min
The Shannon OR-capacity of the categorical product of two graphs is at most the minimum of their individual Shannon OR-capacities.

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_two_cliqueNum_le_one    {V : Type*} [Fintype V] (G : SimpleGraph V)    (h : ∀ u v : V, ¬ G.Adj u v) : G.cliqueNum ≤ 1 := by  obtain ⟨s, hs, hcard⟩ := G.exists_isNClique_cliqueNum  rw [← hcard]  by_contra hlt  push Not at hlt  obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp hlt  exact h a b (hs ha hb hab)private lemma shannon_or_capacity_categorical_prod_of_min_eq_two_le_one_of_no_adj    {V : Type*} [Fintype V] [Nonempty V] (G : SimpleGraph V)    (h : ∀ u v : V, ¬ G.Adj u v) : shannon_or_capacity G ≤ 1 := by  unfold shannon_or_capacity  apply ciSup_le  intro n  by_cases hn : 1 ≤ n  · rw [ciSup_pos hn]    have hno : ∀ x y : Fin n → V, ¬ (simple_graph_or_power G n).Adj x y := by      intro x y hxy      obtain ⟨i, hi⟩ := hxy      exact h (x i) (y i) hi    have hcl : (simple_graph_or_power G n).cliqueNum ≤ 1 :=      shannon_or_capacity_categorical_prod_of_min_eq_two_cliqueNum_le_one _ hno    have hclr : ((simple_graph_or_power G n).cliqueNum : ℝ) ≤ 1 := by exact_mod_cast hcl    exact Real.rpow_le_one (by positivity) hclr (by positivity)  · simp [hn]private lemma shannon_or_capacity_categorical_prod_of_min_eq_two_two_le_of_adj    {V : Type*} [Fintype V] [Nonempty V] (G : SimpleGraph V) {u v : V} (h : G.Adj u v) :    2 ≤ shannon_or_capacity G := by  classical  have hcl : 2 ≤ (simple_graph_or_power G 1).cliqueNum := by    have hc : (simple_graph_or_power G 1).IsClique        ({(fun _ : Fin 1 => u), (fun _ : Fin 1 => v)} : Finset (Fin 1 → V)) := by      intro a ha b hb hab      simp at ha hb      rcases ha with rfl | rfl <;> rcases hb with rfl | rfl      · exact absurd rfl hab      · exact ⟨0, h⟩      · exact ⟨0, (G.adj_comm v u).mpr h⟩      · exact absurd rfl hab    have hcard : ({(fun _ : Fin 1 => u), (fun _ : Fin 1 => v)} : Finset (Fin 1 → V)).card = 2 := by      rw [Finset.card_pair]      intro heq      exact G.ne_of_adj h (congrFun heq 0)    have := hc.card_le_cliqueNum    rwa [hcard] at this  unfold shannon_or_capacity  have hclr : (2:ℝ) ≤ ((simple_graph_or_power G 1).cliqueNum : ℝ) := by exact_mod_cast hcl  have hterm : (2:ℝ) ≤ ⨆ (_ : 1 ≤ (1:ℕ)), ((simple_graph_or_power G 1).cliqueNum : ℝ) ^ ((1:ℝ)/↑(1:ℕ)) := by    rw [ciSup_pos (le_refl 1)]    rw [show (1:ℝ)/↑(1:ℕ) = 1 by norm_num, Real.rpow_one]    exact hclr  have hbdd := shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range G  exact le_trans hterm (le_ciSup hbdd 1)/-- Hedetniemi's identity for Shannon OR-capacity holds when the smaller factor capacity is two. -/theorem shannon_or_capacity_categorical_prod_of_min_eq_two {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) = 2) : shannon_or_capacity (simple_graph_categorical_prod G H) = 2 := by  have hG : 2 ≤ shannon_or_capacity G := by rw [← h]; exact min_le_left _ _  have hH : 2 ≤ shannon_or_capacity H := by rw [← h]; exact min_le_right _ _  have hedgeG : ∃ u v : V, G.Adj u v := by    by_contra hne    push Not at hne    have hle := shannon_or_capacity_categorical_prod_of_min_eq_two_le_one_of_no_adj G hne    linarith  obtain ⟨u, v, huv⟩ := hedgeG  have hedgeH : ∃ x y : W, H.Adj x y := by    by_contra hne    push Not at hne    have hle := shannon_or_capacity_categorical_prod_of_min_eq_two_le_one_of_no_adj H hne    linarith  obtain ⟨x, y, hxy⟩ := hedgeH  have hadj : (simple_graph_categorical_prod G H).Adj (u, x) (v, y) := ⟨huv, hxy⟩  have hlower : 2 ≤ shannon_or_capacity (simple_graph_categorical_prod G H) :=    shannon_or_capacity_categorical_prod_of_min_eq_two_two_le_of_adj _ hadj  have hupper : shannon_or_capacity (simple_graph_categorical_prod G H) ≤ 2 := by    have hle := shannon_or_capacity_categorical_prod_le_min G H    rw [h] at hle    exact hle  linarith
See it in the graphDiscuss this resultChallenge it