Lemma 5.1 (used in the proof of Theorem 1.2) — Cycle polynomial and lowest coefficient
OpenOddPermSum.Evaluation.Supplement.lemma_5_1algebracomplexity-theorylinear-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a loopless simple directed graph, and let over a characteristic-two field. If has no even directed cycle, then . Otherwise let be its shortest even-cycle length, and let be all cycles of that length. Then
Nonvanishing concerns a formal polynomial in independent arc variables. This identifies the first possible nonzero degree without a genericity assumption on an evaluated weight assignment.
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_1 {F : Type*} [Field F] [CharP F 2] {n : ℕ} (D : Digraph n) :
((evenCycles D = ∅) → generatingQ (F := F) D = 0) ∧
(∀ ℓ, IsShortest D ℓ →
(∀ r < ℓ, (generatingQ (F := F) D).coeff r = 0) ∧
(generatingQ (F := F) D).coeff ℓ = ∑ C ∈ cyclesAt D ℓ, cycleMonomial (F := F) D C ∧
(generatingQ (F := F) D).coeff ℓ ≠ 0) := 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.1