Lemma 5.3 (used in the proof of Theorem 1.2) — Truncated-ring value, inverse, determinant and gradient
OpenOddPermSum.Evaluation.Supplement.lemma_5_3algebracomplexity-theorylinear-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Fix an admissible bilinear exponent . For every characteristic-two coefficient field , one deterministic algebraic program, chosen before the dimensions and input matrix, takes the coefficients of each entry of , where and is invertible. It returns all four quantities
There are and , independent of , for which the actual charged field-operation count is at most
The program receives as integer parameters. This supplies complete truncated-ring computation from a prime-field bilinear multiplier, without an oracle for ring operations.
Differences from the source:
- 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: 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
- 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_bilinearMultiplier import Definitions.Def_OddPermSum_Evaluation_Supplement_ringAlgorithmInterfaces set_option autoImplicit false
Formal statement
namespace OddPermSum.Evaluation.Supplement
theorem lemma_5_3 (ω : ℝ) (hω : UniformBilinearExponent ω) :
∃ (C : ℝ) (k : ℕ), 0 < C ∧
∀ (F : Type) [Field F] [CharP F 2], ∃ p : AlgebraicProgram F,
∀ (s L : ℕ), 1 ≤ s → ∀ A : Matrix (Fin s) (Fin s) (Trunc F L),
IsUnit (constantMatrix A).det → ∃ (fuel : ℕ) (st : MachineState F),
runParameters p s L 0 (truncMatrixEncoding A) fuel = some st ∧
st.outputs = allRingOutputs A ∧
(st.cost : ℝ) ≤ C * (s : ℝ)^ω * (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. 14, Lemma 5.3