op_599_complete_graph_equality
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.
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`).
uses
SimpleGraph.induce_top,Finset.coe_empty,Set.not_nonempty_empty,Set.nonempty_coe_sort.mp,Finset.nonempty_iff_ne_empty.mpr,SimpleGraph.connected_topdsimp [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
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.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_erase,ne_eq,op_599_complete_graph_equality_connected_iffext 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
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.
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_leftrw [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]
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.
uses
op_599_complete_graph_equality_Z_eqintro Z mu mean_order have hZ : Z = (Polynomial.X + 1) ^ Fintype.card V - 1 := op_599_complete_graph_equality_Z_eq
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`).
uses
Polynomial.derivative_sub,Polynomial.derivative_pow,Polynomial.derivative_add,Polynomial.derivative_X,Polynomial.derivative_onehave 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]
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.
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
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.
uses
add_commdsimp [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).
- The assumptions 1 ≤ lam and 1 ≤ Fintype.card V ensure that (1 + lam)^n - 1 > 0 so that the denominator is non-zero, making the mean order well-defined. The formal identity itself is verified by algebraic simplification in the ring of real numbers without directly invoking these inequalities.
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.
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