Lemma 5.2 (used in the proof of Theorem 1.2) — Arc-derivative support
OpenOddPermSum.Evaluation.Supplement.lemma_5_2algebracomplexity-theorylinear-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let have shortest even-cycle length . For each arc , set , with formal differentiation. Then
Here is the full union of arcs of shortest even directed cycles. The equivalence identifies every support arc, rather than selecting one cycle.
Differences from the source:
- encoding: vertices indexed by [n] and cycles up to rotation → vertices indexed by Fin n and cycles represented by their directed arc sets; reason: zero-based relabeling and rotation quotient preserve every directed cycle, including length two
- generalization: the field F_{2^d} chosen for the graph application → every field of characteristic two; reason: the coefficient identities and deterministic extraction are field-independent and include the chosen finite fields
Preamble
import Definitions.Def_OddPermSum_Evaluation_Supplement_generatingPolynomial set_option autoImplicit false
Formal statement
namespace OddPermSum.Evaluation.Supplement
theorem lemma_5_2 {F : Type*} [Field F] [CharP F 2] {n : ℕ}
(D : Digraph n) (ℓ : ℕ) (hℓ : IsShortest D ℓ) (e : D.Arc) :
(arcQ (F := F) D e).coeff ℓ =
∑ C ∈ (cyclesAt D ℓ).filter (fun C => e.val ∈ C), cycleMonomial (F := F) D C ∧
((arcQ (F := F) D e).coeff ℓ ≠ 0 ↔ e.val ∈ shortestArcs D ℓ) := by sorry
end OddPermSum.Evaluation.Supplement
Source
Boxuan Chen, Bin Cui, Hanqing Li, Xupeng Miao, Haoze Wang, STOC 2027 submission #716 (October 2026), p. 13, Lemma 5.2