AFTD Auto-Formalizing Theoretical Domains

op_599_complete_graph_equality

theoremverified

For the complete graph on at least 1 vertex and any real lambda >= 1, the lambda-weighted mean order of a nonempty connected induced vertex set equals n * lambda * (1 + lambda)^(n - 1) / ((1 + lambda)^n - 1).

Statement

open scoped BigOperators Polynomial in
theorem op_599_complete_graph_equality
    {V : Type*} [Fintype V] [DecidableEq V] (lam : ℝ) (hlam : 1 ≤ lam) (hn : 1 ≤ Fintype.card V) :
    let Z := open scoped Classical in
      ∑ S ∈ (Finset.univ.filter (fun (S : Finset V) => is_connected_vertex_set (⊤ : SimpleGraph V) (↑S : Set V))),
        (Polynomial.X : Polynomial ℝ) ^ Finset.card S
    let mu := (Fintype.card V : ℝ) * lam * (1 + lam) ^ (Fintype.card V - 1) / ((1 + lam) ^ (Fintype.card V) - 1)
    let mean_order := lam * (Polynomial.derivative Z).eval lam / Z.eval lam
    mean_order = mu
Source
knowledge base, OP-599
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_connected_vertex_setA vertex set S of a graph G is connected if the subgraph of G induced by S is connected (in particular S is nonempty).

Read back from the Lean

Let $V$ be a finite type with decidable equality. Let $\lambda \ge 1$ be a real number, and assume that the cardinality of $V$ is at least $1$ ($1 \le |V|$). Define the polynomial $Z \in \mathbb{R}[X]$ as the sum over all subsets $S \subseteq V$ whose induced subgraph in the complete graph $\top$ on $V$ is connected (via is_connected_vertex_set), of $X^{|S|}$. Define $\mu \in \mathbb{R}$ by $$\mu = \frac{|V| \cdot \lambda \cdot (1 + \lambda)^{|V| - 1}}{(1 + \lambda)^{|V|} - 1}$$ Define $\text{mean\_order} \in \mathbb{R}$ by $$\text{mean\_order} = \frac{\lambda \cdot Z'(\lambda)}{Z(\lambda)}$$ where $Z'$ is the formal derivative of $Z$. The theorem asserts that $\text{mean\_order} = \mu$.

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 lambda-weighted partition function Z(X) sums X^|S| over all nonempty connected induced vertex sets S of the complete graph. Because every nonempty subset of vertices in a complete graph induces a connected subgraph, Z(X) is simply the sum over all nonempty subsets of V, which by the binomial theorem evaluates to (X + 1)^n - 1, where n = |V|. Differentiating this polynomial gives Z'(X) = n * (X + 1)^(n - 1). Evaluating Z and Z' at X = lambda and substituting into the formula for the mean order lam * Z'(lam) / Z(lam) immediately matches the expression mu.

  1. A subset of vertices in the complete graph induces a connected subgraph if and only if it is nonempty.

    Unfolding the definition `is_connected_vertex_set`, the induced subgraph on S in the complete graph ⊤ is the complete graph on S (`SimpleGraph.induce_top`). For the forward direction, a connected graph must have a nonempty vertex type, but the empty finset coerces to the empty set (`Finset.coe_empty`, `Set.not_nonempty_empty`, `Set.nonempty_coe_sort.mp`), giving a contradiction. For the reverse direction, if S ≠ ∅, it contains an element x (`Finset.nonempty_iff_ne_empty.mpr`), making the vertex type nonempty; any nonempty complete graph is connected (`SimpleGraph.connected_top`).

    lines 5–15

    uses SimpleGraph.induce_top, Finset.coe_empty, Set.not_nonempty_empty, Set.nonempty_coe_sort.mp, Finset.nonempty_iff_ne_empty.mpr, SimpleGraph.connected_top

      dsimp [is_connected_vertex_set]
      rw [SimpleGraph.induce_top]
      constructor
      · intro h rfl
        have hne : Nonempty (↑(∅ : Finset V) : Set V) := h.nonempty
        rw [Finset.coe_empty] at hne
        exact Set.not_nonempty_empty (Set.nonempty_coe_sort.mp hne)
      · intro hne
        obtain ⟨x, hx⟩ := Finset.nonempty_iff_ne_empty.mpr hne
        have : Nonempty (↑S : Set V) := ⟨⟨x, hx⟩⟩
        exact SimpleGraph.connected_top
  2. The collection of connected vertex subsets in the complete graph consists of all nonempty subsets of V.

    By finset extensionality (`ext S`), a subset S belongs to the filtered finset of connected vertex sets if and only if it induces a connected subgraph. Rewriting with `op_599_complete_graph_equality_connected_iff`, this is equivalent to S ≠ ∅, which is precisely membership in `Finset.univ.erase ∅`. Propositional logic (`tauto`) finishes the equivalence.

    lines 20–23

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase, ne_eq, op_599_complete_graph_equality_connected_iff

      ext S
      simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase, ne_eq]
      rw [op_599_complete_graph_equality_connected_iff]
      tauto
  3. The partition polynomial Z(X) = ∑_{S connected} X^|S| equals (X + 1)^n - 1, where n = |V|.

    Using `op_599_complete_graph_equality_filter_eq`, the sum is over all nonempty subsets S. Applying `Finset.add_sum_erase`, the empty set term X^|∅| = X^0 = 1 plus the sum over nonempty subsets equals the total sum over all subsets ∑_{S ⊆ V} X^|S|. By the binomial theorem for finite types (`Fintype.sum_pow_mul_eq_add_pow`), this total sum equals (X + 1)^n. Subtracting 1 (`add_sub_cancel_left`) yields (X + 1)^n - 1.

    lines 29–35

    uses op_599_complete_graph_equality_filter_eq, Finset.add_sum_erase, Finset.mem_univ, Fintype.sum_pow_mul_eq_add_pow, one_pow, mul_one, Finset.card_empty, pow_zero, add_sub_cancel_left

      rw [op_599_complete_graph_equality_filter_eq]
      have h_add := Finset.add_sum_erase (Finset.univ : Finset (Finset V))
        (fun S => (Polynomial.X : Polynomial ℝ) ^ S.card) (Finset.mem_univ ∅)
      have h_pow := @Fintype.sum_pow_mul_eq_add_pow (Polynomial ℝ) _ V _ (Polynomial.X : Polynomial ℝ) 1
      simp only [one_pow, mul_one] at h_pow
      simp only [Finset.card_empty, pow_zero] at h_add
      rw [← h_pow, ← h_add, add_sub_cancel_left]
  4. In the main theorem, express the partition polynomial Z(X) in closed form as (X + 1)^n - 1.

    Introduce the local definitions Z, mu, and mean_order. By lemma `op_599_complete_graph_equality_Z_eq`, the partition polynomial Z equals (X + 1)^n - 1.

    lines 47–48

    uses op_599_complete_graph_equality_Z_eq

      intro Z mu mean_order
      have hZ : Z = (Polynomial.X + 1) ^ Fintype.card V - 1 := op_599_complete_graph_equality_Z_eq
  5. The derivative of Z(X) is n * (X + 1)^(n - 1).

    Substituting Z(X) = (X + 1)^n - 1, the derivative is computed using standard polynomial rules: difference rule (`Polynomial.derivative_sub`), power rule (`Polynomial.derivative_pow`), sum rule (`Polynomial.derivative_add`), and the base derivatives of X (`Polynomial.derivative_X`) and 1 (`Polynomial.derivative_one`).

    lines 49–53

    uses Polynomial.derivative_sub, Polynomial.derivative_pow, Polynomial.derivative_add, Polynomial.derivative_X, Polynomial.derivative_one

      have hder : Polynomial.derivative Z =
          Polynomial.C (Fintype.card V : ℝ) * (Polynomial.X + 1) ^ (Fintype.card V - 1) := by
        rw [hZ]
        simp [Polynomial.derivative_sub, Polynomial.derivative_pow, Polynomial.derivative_add,
              Polynomial.derivative_X, Polynomial.derivative_one]
  6. Evaluating at X = lam yields Z'(lam) = n * (lam + 1)^(n - 1) and Z(lam) = (lam + 1)^n - 1.

    Substituting the closed forms of Z' and Z, polynomial evaluation at lam simplifies directly to n * (lam + 1)^(n - 1) and (lam + 1)^n - 1 respectively.

    lines 54–60

      have h_eval_der : (Polynomial.derivative Z).eval lam =
          (Fintype.card V : ℝ) * (lam + 1) ^ (Fintype.card V - 1) := by
        rw [hder]
        simp
      have h_eval_Z : Z.eval lam = (lam + 1) ^ (Fintype.card V) - 1 := by
        rw [hZ]
        simp
  7. The lambda-weighted mean order equals mu.

    Unfolding the definitions of mean_order and mu, we substitute the evaluations of Z'(lam) and Z(lam). Commuting lam + 1 to 1 + lam (`add_comm`), the numerator lam * (n * (1 + lam)^(n - 1)) simplifies to n * lam * (1 + lam)^(n - 1), and `ring` verifies the equality of the two rational expressions.

    lines 61–65

    uses add_comm

      dsimp [mean_order, mu]
      rw [h_eval_der, h_eval_Z]
      have h1 : lam + 1 = 1 + lam := add_comm lam 1
      rw [h1]
      ring
SimpleGraph.induce_top
The subgraph induced on a vertex set s in a complete graph is the complete graph on s.
Finset.coe_empty
The coercion of the empty finset to a set is the empty set.
Set.not_nonempty_empty
The empty set is not nonempty.
Set.nonempty_coe_sort.mp
If the subtype corresponding to a set is nonempty, then the set itself is nonempty.
Finset.nonempty_iff_ne_empty.mpr
A finset is nonempty if and only if it is not equal to the empty set.
SimpleGraph.connected_top
A complete graph on a nonempty vertex type is connected.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the finset and satisfies the filter predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
true_and
The conjunction of True with a proposition p is equivalent to p.
Finset.mem_erase
An element belongs to a finset with b removed if and only if it is not equal to b and belongs to the finset.
ne_eq
The notation a ≠ b is defined as ¬(a = b).
op_599_complete_graph_equality_connected_iff
In a complete graph, a vertex subset induces a connected subgraph if and only if it is nonempty.
op_599_complete_graph_equality_filter_eq
The finset of connected vertex subsets of the complete graph equals the universal finset with the empty set removed.
Finset.add_sum_erase
The sum of a function over a finset equals the term at an element a plus the sum over the finset with a removed.
Fintype.sum_pow_mul_eq_add_pow
The sum of a^|s| * b^(n - |s|) over all subsets s of an n-element type equals (a + b)^n.
one_pow
One raised to any power is one.
mul_one
Multiplying an element by one leaves it unchanged.
Finset.card_empty
The cardinality of the empty finset is zero.
pow_zero
Any element raised to the power zero is one.
add_sub_cancel_left
Subtracting a from a + b leaves b.
op_599_complete_graph_equality_Z_eq
The partition polynomial Z(X) = ∑_{S connected} X^|S| for the complete graph equals (X + 1)^n - 1, where n = |V|.
Polynomial.derivative_sub
The derivative of a difference of polynomials is the difference of their derivatives.
Polynomial.derivative_pow
The derivative of a power p^n is n * p^(n - 1) * p'.
Polynomial.derivative_add
The derivative of a sum of polynomials is the sum of their derivatives.
Polynomial.derivative_X
The derivative of the polynomial indeterminate X is 1.
Polynomial.derivative_one
The derivative of the constant polynomial 1 is 0.
add_comm
Addition is commutative (a + b = b + a).

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 scoped BigOperators Polynomial Classicallemma op_599_complete_graph_equality_connected_iff {V : Type*} [Fintype V] [DecidableEq V] (S : Finset V) :    is_connected_vertex_set (⊤ : SimpleGraph V) (↑S : Set V) ↔ S ≠ ∅ := by  dsimp [is_connected_vertex_set]  rw [SimpleGraph.induce_top]  constructor  · intro h rfl    have hne : Nonempty (↑(∅ : Finset V) : Set V) := h.nonempty    rw [Finset.coe_empty] at hne    exact Set.not_nonempty_empty (Set.nonempty_coe_sort.mp hne)  · intro hne    obtain ⟨x, hx⟩ := Finset.nonempty_iff_ne_empty.mpr hne    have : Nonempty (↑S : Set V) := ⟨⟨x, hx⟩⟩    exact SimpleGraph.connected_toplemma op_599_complete_graph_equality_filter_eq {V : Type*} [Fintype V] [DecidableEq V] :    (Finset.univ.filter (fun (S : Finset V) => is_connected_vertex_set (⊤ : SimpleGraph V) (↑S : Set V))) =    Finset.univ.erase ∅ := by  ext S  simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase, ne_eq]  rw [op_599_complete_graph_equality_connected_iff]  tautolemma op_599_complete_graph_equality_Z_eq {V : Type*} [Fintype V] [DecidableEq V] :    (∑ S ∈ (Finset.univ.filter (fun (S : Finset V) => is_connected_vertex_set (⊤ : SimpleGraph V) (↑S : Set V))),      (Polynomial.X : Polynomial ℝ) ^ Finset.card S) =    (Polynomial.X + 1) ^ Fintype.card V - 1 := by  rw [op_599_complete_graph_equality_filter_eq]  have h_add := Finset.add_sum_erase (Finset.univ : Finset (Finset V))    (fun S => (Polynomial.X : Polynomial ℝ) ^ S.card) (Finset.mem_univ ∅)  have h_pow := @Fintype.sum_pow_mul_eq_add_pow (Polynomial ℝ) _ V _ (Polynomial.X : Polynomial ℝ) 1  simp only [one_pow, mul_one] at h_pow  simp only [Finset.card_empty, pow_zero] at h_add  rw [← h_pow, ← h_add, add_sub_cancel_left]open scoped BigOperators Polynomial in/-- The complete graph achieves equality in the activity-weighted mean order bound. -/theorem op_599_complete_graph_equality    {V : Type*} [Fintype V] [DecidableEq V] (lam : ℝ) (hlam : 1 ≤ lam) (hn : 1 ≤ Fintype.card V) :    let Z := open scoped Classical in      ∑ S ∈ (Finset.univ.filter (fun (S : Finset V) => is_connected_vertex_set (⊤ : SimpleGraph V) (↑S : Set V))),        (Polynomial.X : Polynomial ℝ) ^ Finset.card S    let mu := (Fintype.card V : ℝ) * lam * (1 + lam) ^ (Fintype.card V - 1) / ((1 + lam) ^ (Fintype.card V) - 1)    let mean_order := lam * (Polynomial.derivative Z).eval lam / Z.eval lam    mean_order = mu := by  intro Z mu mean_order  have hZ : Z = (Polynomial.X + 1) ^ Fintype.card V - 1 := op_599_complete_graph_equality_Z_eq  have hder : Polynomial.derivative Z =      Polynomial.C (Fintype.card V : ℝ) * (Polynomial.X + 1) ^ (Fintype.card V - 1) := by    rw [hZ]    simp [Polynomial.derivative_sub, Polynomial.derivative_pow, Polynomial.derivative_add,          Polynomial.derivative_X, Polynomial.derivative_one]  have h_eval_der : (Polynomial.derivative Z).eval lam =      (Fintype.card V : ℝ) * (lam + 1) ^ (Fintype.card V - 1) := by    rw [hder]    simp  have h_eval_Z : Z.eval lam = (lam + 1) ^ (Fintype.card V) - 1 := by    rw [hZ]    simp  dsimp [mean_order, mu]  rw [h_eval_der, h_eval_Z]  have h1 : lam + 1 = 1 + lam := add_comm lam 1  rw [h1]  ring
See it in the graphDiscuss this resultChallenge it