Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Expansion of ∏if^idi\prod_i \hat f_i^{d_i}∏i​f^​idi​​ into rooted operators ∂DR\partial^{D_R}∂DR​

Proved
HararySachs.Hyper.operator_expansion

by milia · Nov 12, 2026 · Mathlib 0df444a (Lean v4.33.1)

differential-operatorhypergraphrootingtrace

This is the expansion of a product of the paper's differential operators f^i\hat f_if^​i​ into rooted operators. It states precisely the observation of Definitions 6–7 (pp. 7–8) that every addend of ∏if^idi\prod_i\hat f_i^{d_i}∏i​f^​idi​​ is the operator f^DR\hat f_{D_R}f^​DR​​ of a rooting RRR.

Let k≥2k\ge2k≥2 and let H=([n],E)\mathcal H=([n],E)H=([n],E) be a simple kkk-graph. Let A=(Aij)A=(A_{ij})A=(Aij​) be an n×nn\times nn×n matrix of independent variables, and for a vertex iii let

f^i=∑t1,…,tk−1∈[n]ai t1⋯tk−1 ∂∂Ait1⋯∂∂Aitk−1,\hat f_i=\sum_{t_1,\ldots,t_{k-1}\in[n]} a_{i\,t_1\cdots t_{k-1}}\ \frac{\partial}{\partial A_{i t_1}}\cdots\frac{\partial}{\partial A_{i t_{k-1}}},f^​i​=t1​,…,tk−1​∈[n]∑​ait1​⋯tk−1​​ ∂Ait1​​∂​⋯∂Aitk−1​​∂​,

where aaa is the normalized adjacency hypermatrix, equal to 1/(k−1)!1/(k-1)!1/(k−1)! on orderings of edges. Fix an arrangement (d1,…,dn)(d_1,\ldots,d_n)(d1​,…,dn​) of ddd into nonnegative parts. Then, for every polynomial PPP in the variables AijA_{ij}Aij​,

f^n dn⋯f^1 d1 P  =  ∑S ∑R ∂DRP.\hat f_{n}^{\,d_n}\cdots\hat f_{1}^{\,d_1}\,P\;=\;\sum_{S}\ \sum_{R}\ \partial^{D_R}P.f^​ndn​​⋯f^​1d1​​P=S∑​ R∑​ ∂DR​P.

Here SSS runs over the multisets of ddd edges of H\mathcal HH, and RRR runs over the rootings of SSS in which exactly dvd_vdv​ edges are rooted at vvv for each vertex vvv. A rooting is a sequence ((v1,e1),…,(vd,ed))\bigl((v_1,e_1),\ldots,(v_d,e_d)\bigr)((v1​,e1​),…,(vd​,ed​)) with vj∈ejv_j\in e_jvj​∈ej​, nondecreasing roots, and edge multiset SSS. The operator ∂DR=∏u≠v∂mR(u,v)/∂AuvmR(u,v)\partial^{D_R}=\prod_{u\ne v}\partial^{m_R(u,v)}/\partial A_{uv}^{m_R(u,v)}∂DR​=∏u=v​∂mR​(u,v)/∂AuvmR​(u,v)​ differentiates once for every arc of the rooted digraph DRD_RDR​, where mR(u,v)m_R(u,v)mR​(u,v) is the number of jjj with vj=uv_j=uvj​=u and v∈ejv\in e_jv∈ej​.

This identity converts the differential trace Tr⁡d(H)\operatorname{Tr}_d(\mathcal H)Trd​(H) of Equation (1) into a sum over rootings, which is the first step of the proof of Lemma 13.

Formalization Note The left-hand side is the mission's applyAll, which applies f^1d1\hat f_1^{d_1}f^​1d1​​ first. The operators commute, so the order is immaterial. Arrangements are functions Fin n → Fin (d+1) with sum ddd. The rootings are the sequences R : Fin S.card → Fin n × Finset (Fin n) satisfying IsRooting S R together with the root-count condition, and ∂DR\partial^{D_R}∂DR​ is diffMonomial (rootedArcs R). The identity is stated as an identity of polynomials, valid for every PPP.

Preamble
import Mathlib
import Definitions.Def_HararySachs_Hyper_Operators
import Definitions.Def_HararySachs_Hyper_Veblen
Formal statement
namespace HararySachs.Hyper
open Classical

theorem operator_expansion {n k d : ℕ} (hk : 2 ≤ k)
    (E : Finset (Finset (Fin n))) (hE : ∀ e ∈ E, e.card = k)
    (a : Fin n → Fin (d + 1)) (ha : (∑ i, (a i).val) = d) (P : AuxPoly n) :
    applyAll (k := k) E a P =
      ∑ S ∈ allMultisets E d,
        ∑ R : Fin S.card → Fin n × Finset (Fin n),
          if IsRooting S R ∧
              ∀ v, (Finset.univ.filter (fun i => (R i).1 = v)).card = (a v).val
          then diffMonomial (rootedArcs R) P else 0 := by sorry

end HararySachs.Hyper
Source
Clark and Cooper, A Harary-Sachs theorem for hypergraphs, arXiv:1812.00468v2, pp. 7-8, Definitions 6-7 and the remark that a rooted operator divides prod_i f_i^{d_i}; p. 12, proof of Lemma 13, display after 'Applying Lemma 10'

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me