Lemma 4, counting part — equals the number of Euler tours of
ProvedHararySachs.Hyper.coeff_eq_numToursThis is the counting identity at the heart of Lemma 4 of Clark and Cooper: extracting the constant term of a monomial differential operator applied to a matrix trace counts Euler tours.
Let be a matrix of independent variables over , and let be a directed multigraph on with distinguishable arcs from to (loops allowed) and arcs in total. Put
Then the constant term of equals the number of Euler tours of :
An Euler tour is a closed trail that traverses every arc exactly once and has a distinguished first position. No Eulerian hypothesis is needed: when is not Eulerian, both sides vanish.
Together with Euler's criterion for the existence of a tour, this gives Lemma 4. Through the BEST theorem it also gives Corollary 6, the closed form of each summand of the differential trace .
Formalization Note The operator is the mission's diffMonomial m, and is trPow n L. Euler tours are counted by numTours m hL: bijections from positions Fin L onto the labeled arcs Arcs m in which each arc's head is the next arc's tail, cyclically. The tour count in the paper's Equation (3) is this number.
import Mathlib import Definitions.Def_HararySachs_Hyper_Operators
namespace HararySachs.Hyper
theorem coeff_eq_numTours {n L : ℕ} (hL : 0 < L) (m : ArcMult n)
(hm : (∑ u : Fin n, ∑ v : Fin n, m u v) = L) :
MvPolynomial.coeff 0 (diffMonomial m (trPow n L)) = (numTours m hL : ℚ) := by sorry
end HararySachs.Hyper