The cycle polynomial and its arc derivatives
DefinitionOddPermSum_Evaluation_Supplement_generatingPolynomialalgebracomplexity-theorylinear-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Over a field , assign an independent variable to each arc of . With on arcs and zero elsewhere, define
The coefficient ring is , and is a separate polynomial variable. The monomial of a cycle is the product of its arc variables, each occurring once.
The published permutation polynomial defines independently of the graph, while coefficientwise formal differentiation defines .
Definition code
import Definitions.Def_OddPermSum_Evaluation_Supplement_digraph
import Definitions.Def_OddPermSum_Evaluation_gradient
set_option autoImplicit false
namespace OddPermSum.Evaluation.Supplement
noncomputable def cycleMonomial {F : Type*} [Field F] {n : ℕ} (D : Digraph n)
(C : Finset (Fin n × Fin n)) : MvPolynomial D.Arc F := by
classical
exact ∏ e : D.Arc, if e.val ∈ C then MvPolynomial.X e else 1
noncomputable def symbolicAdjacency {F : Type*} [Field F] {n : ℕ} (D : Digraph n) :
Matrix (Fin n) (Fin n) (Polynomial (MvPolynomial D.Arc F)) := by
classical
exact fun i j => if h : (i,j) ∈ D.arcs then Polynomial.C (MvPolynomial.X ⟨(i,j),h⟩) else 0
noncomputable def generatingQ {F : Type*} [Field F] {n : ℕ} (D : Digraph n) :
Polynomial (MvPolynomial D.Arc F) :=
phi (1 + (Polynomial.X : Polynomial (MvPolynomial D.Arc F)) • symbolicAdjacency (F := F) D)
/-- Coefficientwise formal differentiation in an arc variable, followed by multiplication by it. -/
noncomputable def arcQ {F : Type*} [Field F] {n : ℕ} (D : Digraph n) (e : D.Arc) :
Polynomial (MvPolynomial D.Arc F) :=
(generatingQ (F := F) D).sum fun r c =>
Polynomial.monomial r (MvPolynomial.X e * MvPolynomial.pderiv e c)
end OddPermSum.Evaluation.Supplement
Source
Boxuan Chen, Bin Cui, Hanqing Li, Xupeng Miao, Haoze Wang, STOC 2027 submission #716 (October 2026), p. 13, Eqs. (5.1), (5.3)