Lemma 6.3 (used in the proof of Theorem 1.3) — Gradient-column and rank-one updates
OpenOddPermSum.Evaluation.Supplement.lemma_6_3algebracomplexity-theorylinear-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be invertible, and suppose , and are given as input. For a row and index , put , , , , and . Then
If is a unit, then
Moreover, guarantees that is a unit. One program over each coefficient field, chosen before , computes , both updated scalars, and the updated inverse when applicable, using at most
charged field operations, with and independent of all inputs and the coefficient field. This is a simultaneous query-and-update statement, including all algebraic clauses and the unit safeguard.
Differences from the source:
- encoding: soft-O field-operation complexity → one program and positive constants C,k preceding s,L and all matrix inputs, with an explicit logarithmic bound; reason: expands soft-O uniformly without a loss in the exponent or dependence on the truncation precision
- encoding: inverse of a unit and available stored quantities → Ring.inverse under IsUnit and explicit coefficient-list inputs for B, determinant and value; reason: ring inverse is only asserted valid for units and the input interface retains the source availability convention
- generalization: the finite coefficient field chosen in section 5 → every characteristic-two coefficient field, with C and k uniform over that field; reason: the ring algorithms on pp. 14–15 and 21 use characteristic two and uniform scalar polynomial arithmetic; the chosen finite field is a special case
Preamble
import Definitions.Def_OddPermSum_Evaluation_Supplement_ringAlgorithmInterfaces set_option autoImplicit false
Formal statement
namespace OddPermSum.Evaluation.Supplement
theorem lemma_6_3 :
∃ (C : ℝ) (k : ℕ), 0 < C ∧
∀ (F : Type) [Field F] [CharP F 2], ∃ p : AlgebraicProgram F,
∀ (s L : ℕ) (A B : Matrix (Fin s) (Fin s) (Trunc F L))
(δ φA : Trunc F L) (i : Fin s) (ρ : Fin s → Trunc F L),
IsUnit A.det → B = A⁻¹ → δ = A.det → φA = phi A →
phi (rowUpdate A i ρ) = phi A + ∑ j, ρ j * gradient A j i ∧
(rowUpdate A i ρ).det = δ * updateEta B i ρ ∧
(IsUnit (updateEta B i ρ) → (rowUpdate A i ρ)⁻¹ = inverseUpdate B i ρ) ∧
((∀ j, truncCoeff (ρ j) 0 = 0) → IsUnit (updateEta B i ρ)) ∧
∃ (fuel : ℕ) (st : MachineState F),
runParameters p s L i.val (updateInputs A B δ φA ρ) fuel = some st ∧
st.outputs = updateOutputs A i ρ ∧
(st.cost : ℝ) ≤ C * (s : ℝ)^2 * (L+1) * (Real.logb 2 (s+L+2))^k := by sorry
end OddPermSum.Evaluation.Supplement
Source
Boxuan Chen, Bin Cui, Hanqing Li, Xupeng Miao, Haoze Wang, STOC 2027 submission #716 (October 2026), p. 20, Lemma 6.3