Lemma 3: divisibility detected by residues
OpenQAlgorithms.Papers.Independent.Intakethird100.P85.residue_divisibilityLet , and let be its coefficient residue modulo . Reducibility and twice reducibility mean divisibility in the residue algebra by the images of and , respectively. Then
The quotients are computed in and tested for membership in the cyclotomic integer ring. This transfers divisibility questions to residues.
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 : ℝ) : ℂ)
/-- Lemma 3, PDF p.3: quotients must belong to Z[omega]. -/
theorem residue_divisibility (t : ℂ) (integral : InZomega t) :
(InZomega (t / 2) ↔ TwiceReducible (residue t)) ∧
(InZomega (t / sqrtTwo) ↔ Reducible (residue t)) := 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 , let
and let denote the complex constant called sqrtTwo, whose defining equation is not supplied. For , let be its chosen integer coefficient quadruple in the displayed expansion, reduced coordinatewise modulo . Define , and define
For every complex number satisfying , both equivalences hold:
There is no nonzero hypothesis on , so is included.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.