Normalized low-complexity columns are synthesizable
OpenQAlgorithms.Papers.Independent.Intakenext100.P03.low_complexity_columnLet be a positive even integer. Put , , , and , where , and .
Here . Let be the unique prime of above . Its additive ideal-normalized valuation is , with . Define and . A normalized pair has finite complexity even when a coordinate is zero. Suppose , , and . Then
This is the base regime for column synthesis. The zero-coordinate cases remain included.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P03
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P03
open scoped BigOperators Classical
-- Reuse the Mathlib matrix type without declaring a second Mat.
local notation "Mat" => Matrix Bool Bool ℂ
/-- Canonical data: the axis/exponent list and the actual residual matrix D,
not a nonunique phase/Clifford witness pair, PDF pp.6-7. -/
local notation "CanonicalData" => List (Fin 3 × ℕ) × Matrix Bool Bool ℂ
/-- Lemma 7.4, PDF pp.19-21. Zero coordinates remain allowed with valuation
+infinity; normalized pairs have finite complexity. The p.21 Case 3 proof
example needs cyclotomicRoot^j X instead of cyclotomicRoot^j I; the lemma itself is unchanged. -/
theorem low_complexity_column (n : ℕ) (hn : SmallParameter n)
(x y : ℂ) (hx : x ∈ cyclotomicSynthesisRing n) (hy : y ∈ cyclotomicSynthesisRing n)
(hnorm : Complex.normSq x + Complex.normSq y = 1)
(hsmall : columnComplexity n x y ≤ smallComplexity n) :
∃ V ∈ cyclotomicGroup n, V false false = x ∧ V true false = y := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P03
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every , put , let be the smallest subring of containing , and let be the smallest subring containing and . Define to be the intersection of all prime ideals of containing , with an empty intersection interpreted as the whole ring. For , let be the multiplicity of in the principal ideal , namely the supremum of natural numbers for which for some ideal . Write when , and otherwise regard the natural number as an extended real. Define ; for nonzero for which there exists with , choose the least such and define
for every remaining nonzero , define . All this arithmetic and the following comparisons use extended-real operations. For all satisfying and
there exists a matrix in the multiplicative submonoid generated by , , and , where and is generated by , , and their conjugate transposes, such that
Empty products are included in these submonoids, and no separate finiteness assumption is imposed on the extended-real quantities in the hypothesis.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.