§7, unnumbered: column reduction operation count
OpenQAlgorithms.Papers.Independent.Intakethird100.P85.columnOperation_boundCount each one-/two-level as one operation. There is an absolute constant with all the following properties. For every pair satisfying Lemma 4 at a valid exponent , the selected row word lowers the exponent and has at most letters. For every unit column , , at a valid exponent , there are a single-pass word and a complete-reduction word , recorded by the column proof's traces, such that
The same constant works for all dimensions, exponents and input columns. Word lengths are actual output counts; the statement makes no arithmetic runtime claim. It quantifies the size of the column reduction used in synthesis.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P85
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakethird100.P85
open scoped Classical BigOperators
open QAlgorithms
open QAlgorithms.Papers.Independent.Gap48.P10
(InZomega InDomega Residue bits residue residueMultiply Reducible)
open QAlgorithms.Papers.Independent.Support21.P13
(synthesisRing integralRing coordinateValue HTLetter htWordMatrix EntriesInRing cliffordTLibrary)
local notation "omega" => QAlgorithms.gateT true true
local notation "sqrtTwo" => ((Real.sqrt 2 : ℝ) : ℂ)
/-- Section 7, PDF p.6: uniform row, one-pass, and complete-column output bounds.
The positive-exponent domain excludes the nontrivial exponent-zero base-case cost. -/
theorem columnOperation_bound :
∃ C : ℕ, 0 < C ∧
(∀ (u : Bool → ℂ) (k : ℕ), (∀ b, InDomega (u b)) → 0 < k →
VectorExponent u k →
residueNorm (kResidue (u false) k) = residueNorm (kResidue (u true) k) →
VectorExponent ((htWordMatrix (rowWord u k)).mulVec u) (k - 1) ∧
(rowWord u k).length ≤ C) ∧
(∀ (d : ℕ) (u : Fin d → ℂ) (k : ℕ), 0 < d → 0 < k →
(∀ i, InDomega (u i)) → vectorNormSq u = 1 → VectorExponent u k →
∃ w : List (LevelOp d), PassTrace k u w ∧
VectorExponent ((levelWordMatrix w).mulVec u) (k - 1) ∧ w.length ≤ C * d) ∧
(∀ (d : ℕ) (hd : 0 < d) (u : Fin d → ℂ) (k : ℕ), 0 < k →
(∀ i, InDomega (u i)) → vectorNormSq u = 1 → VectorExponent u k →
∃ w : List (LevelOp d), ColumnTrace ⟨0, hd⟩ u k w ∧
(levelWordMatrix w).mulVec u = (fun i => if i = (⟨0, hd⟩ : Fin d) then 1 else 0) ∧
w.length ≤ C * d * k) := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P85
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let , , and . Let denote the supplied complex constant sqrtTwo, whose defining equation is not supplied, and say that a vector has exponent when for every coordinate . For , let be its chosen coefficient quadruple modulo , and put for . For quadruples over , define , , with , and ; call reducible when for some quadruple . Set , , and , and let of any operation word be its matrix product in reverse word order, with the empty word giving . Define for a two-component vector to be the first -word in the ordered candidate list consisting of the empty word, then as words for , then all concatenations of two such words in nested increasing order of their indices, whose matrix sends to a vector of exponent ; use the empty word if no candidate succeeds. Here the notation describes successive letters followed by one letter, so its matrix is , and subtraction of natural numbers is truncated at zero. On coordinates, permitted level operations apply to an ordered pair of distinct coordinates, identically elsewhere, or multiply a single coordinate by ; lifting an -word to uses those two coordinates in that order. A pass trace at exponent starts from a vector and is any finite derivation using these rules: it may stop with the empty word if every is reducible; otherwise it may choose distinct with not reducible and , apply the lift of , and continue with a pass trace at the same exponent from the resulting vector, concatenating the words. A column trace with target coordinate has the following recursive rules: at exponent zero its input must be for and zero otherwise, for some coordinate and , and its word swaps using if they differ and then applies single-coordinate -phases at ; at exponent , it concatenates a pass trace at exponent with a column trace at exponent from the resulting vector. There exists a positive natural number , common to all the following assertions: for every with components in , and every positive for which has exponent and , the vector has exponent and ; for every positive and every with and exponent , there exists a level-operation word with a pass trace at exponent from , such that has exponent and ; and for every positive and every such normalized vector of exponent , there exists a word with a column trace targeting coordinate zero from at exponent , such that and , where at and is zero otherwise. The first assertion imposes no normalization assumption; all three assertions exclude , and the latter two exclude .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.