Theorem 1.3 (companion theorem; not used in the proof of the goal) — Explicit shortest even-cycle extraction
OpenOddPermSum.Evaluation.Supplement.theorem_1_3algebracomplexity-theorylinear-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a uniformly bilinear admissible exponent . There exist one randomized finite bit-RAM program and constants , , all preceding the graph input. Whenever is a loopless simple digraph on vertices with shortest even-cycle length , the program outputs an explicit verified simple directed cycle of length within
steps, with probability at least . Every execution halts within steps.
The output encodes the complete closed vertex sequence. Correctness and the length-sensitive bound hold jointly, and the general bound applies to every random tape.
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
- reading: a fixed admissible matrix multiplication exponent, with a bilinear algorithm used on p. 14 → UniformBilinearExponent with prime-field coefficients and an effective uniform circuit generator; reason: the changing finite fields require one uniform algorithm and the bilinear polynomial identity must lift to the truncated algebra; this is the structured brief’s prescribed reading
- encoding: time and probability as on p. 2, including its sentence after Theorem 1.3 → finite bit-RAM program with empty advice, a joint correctness/time event of probability at least 1-C n^(-3), and a bound on every tape; reason: charges control and finite-field construction and makes both source time guarantees explicit
Preamble
import Definitions.Def_OddPermSum_Evaluation_Supplement_bilinearMultiplier import Definitions.Def_OddPermSum_Evaluation_Supplement_graphOutputs set_option autoImplicit false
Formal statement
namespace OddPermSum.Evaluation.Supplement
theorem theorem_1_3 (ω : ℝ) (hω : UniformBilinearExponent ω) :
∃ (p : BitProgram) (C : ℝ) (k : ℕ), 0 < C ∧
∀ (n : ℕ) (D : Digraph n) (ℓ : ℕ), IsShortest D ℓ → ∃ T : ℕ,
(T : ℝ) ≤ C * (n : ℝ)^4 * logFactor n k ∧ graphHalts p D T ∧
cycleSuccess p D ℓ T (C * ((n : ℝ)^ω * ℓ + (n : ℝ)^2 * (ℓ : ℝ)^2) * logFactor n k) ≥
1 - C * (n : ℝ)^(-(3 : ℝ)) := by sorry
end OddPermSum.Evaluation.Supplement
Source
Boxuan Chen, Bin Cui, Hanqing Li, Xupeng Miao, Haoze Wang, STOC 2027 submission #716 (October 2026), p. 2, Theorem 1.3 (proof p. 22)