Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 7.1 — one coefficient [w]C[w]C[w]C in O(size(C)d3)O(\mathrm{size}(C)d^3)O(size(C)d3) field operations, the empty-word coefficient in O(size(C))O(\mathrm{size}(C))O(size(C))

Open
NCFactorClosure607.Circuits.Supplement.computing_one_coefficient

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithmsarithmetic-circuitsnoncommutative-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Let FFF be a field, XXX a set of variables, CCC a circuit and www a word of length ddd. There is an absolute constant KKK such that the algorithm coeffAlgo\mathrm{coeffAlgo}coeffAlgo returns the coefficient [w]C[w]C[w]C of www in the polynomial computed by CCC, and

  1. if d≥1d\ge1d≥1, it performs at most K⋅size(C)⋅d3K\cdot\mathrm{size}(C)\cdot d^3K⋅size(C)⋅d3 field operations;
  2. if w=εw=\varepsilonw=ε, it performs at most K⋅size(C)K\cdot\mathrm{size}(C)K⋅size(C) field operations.
[w]C in O(size(C) d3) field operations(d≥1),[ε]C in O(size(C)).[w]C\ \text{in}\ O(\mathrm{size}(C)\,d^3)\ \text{field operations}\quad(d\ge1),\qquad [\varepsilon]C\ \text{in}\ O(\mathrm{size}(C)).[w]C in O(size(C)d3) field operations(d≥1),[ε]C in O(size(C)).

No degree bound on intermediate gates is assumed. The lemma supplies the edge labels of Theorem 7.2 and the coefficient tests of the factorization algorithms.

Differences from the source:

  • generalization: X = {x_1, …, x_m} with m ≥ 1 → an arbitrary type X with decidable equality; reason: decidable equality is needed to compare letters; every finite variable set has it
  • encoding: the coefficient can be computed in O(size(C)d³) field operations → the explicit algorithm coeffAlgo stores every computed interval coefficient once and returns [w]C with at most K·size(C)·d³ counted field operations; reason: the operation count of the proof’s dynamic program, with later lookups reusing stored values
  • encoding: O(size(C)d³) and O(size(C)) → one absolute natural constant K quantified before the field, the variable type, the input and the factors; reason: the O(·) of the source is a uniform absolute constant
  • encoding: No degree bound on intermediate gates is needed → no syntactic-degree hypothesis on C; reason: the sentence states the absence of the hypothesis
Preamble
import Mathlib
import Definitions.Def_NCFactorClosure607_Circuits_Supplement_CoeffAlgorithm

universe u v
Formal statement
namespace NCFactorClosure607.Circuits.Supplement

open NCFactorClosure607.Circuits

/-- Lemma 7.1 (Computing one coefficient), p.17. There is one absolute constant `K` such that for
every field `F`, every type `X` of variables, every well-formed circuit `C` (no degree bound on
any gate) and every word `w`, the algorithm `coeffAlgo` returns the coefficient `[w]C`, using at
most `K · size(C) · d³` field operations when `w` has length `d ≥ 1`, and at most `K · size(C)`
field operations for the empty word. -/
theorem computing_one_coefficient :
    ∃ K : ℕ, ∀ (F : Type u) [Field F] (X : Type v) [DecidableEq X] (C : Circuit F X)
      (w : List X), C.WellFormed →
      (coeffAlgo C w).1 = coeff (FreeMonoid.ofList w) C.eval ∧
      (1 ≤ w.length → (coeffAlgo C w).2 ≤ K * C.size * w.length ^ 3) ∧
      (w = [] → (coeffAlgo C w).2 ≤ K * C.size) := by sorry

end NCFactorClosure607.Circuits.Supplement
Source
V. Arvind, Pushkar S Joglekar, Factor Closure in Noncommutative Algebraic Complexity, STOC 2027 submission #607 (October 2026), p.17, Lemma 7.1 and its proof; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/607.pdf

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me