Prepare terminal endpoint values and independent admissibility flags
ProvedThreeSum.LightReportingTerminalPreparation.program_meets3sumalgorithmsfine-grained-complexitythree-sum-1962word-ram
Fix , a list of selected local occurrences , and two length- arrays of coordinate sets . Assume their masks, occurrence indices, selected coefficients, candidate indices, and trimming histograms are stored correctly before output base . Put and . Reserve two preparation blocks of size , followed by bit, row, and arithmetic scratch satisfying the source-preparation space and word budgets; space fits in a word and depth is available. The program returns and stores
The flags encode the prescribed per-block size and trimming tests independently of endpoint values. Memory below is preserved, with time .
These arrays supply the terminal physical bucket scan.
Preamble
/- Copyright (c) 2026 Anthropic, PBC. All rights reserved. Released under Apache 2.0 license as described in the file LICENSE. SPDX-License-Identifier: Apache-2.0 -/ import Aesop import Definitions.Def_APSPSource_RemainingDefinitions import Definitions.Def_APSPSource_ThreeSumApsp_Lang_Logic import Definitions.Def_APSPSource_ThreeSumApsp_Lang_Regions import Definitions.Def_APSPSource_ThreeSumApsp_Lang_Syntax import Definitions.Def_ThreeSum1962Source_Bundle01 import Definitions.Def_ThreeSum1962Source_Bundle06 import Definitions.Def_ThreeSum1962Source_Bundle07 import Definitions.Def_ThreeSum1962Source_Bundle09 import Definitions.Def_ThreeSum1962Source_Bundle10 import Definitions.Def_ThreeSum1962Source_Bundle11 import Definitions.Def_ThreeSum1962Source_Bundle12 import Lean.Elab.Tactic.Omega import Mathlib.Algebra.BigOperators.Fin import Mathlib.Algebra.BigOperators.Group.Finset.Basic import Mathlib.Algebra.BigOperators.Group.Finset.Piecewise import Mathlib.Algebra.BigOperators.Group.Finset.Powerset import Mathlib.Algebra.BigOperators.Group.Finset.Sigma import Mathlib.Algebra.BigOperators.Ring.Finset import Mathlib.Algebra.Field.ZMod import Mathlib.Algebra.Group.Equiv.Basic import Mathlib.Algebra.Group.Int.Defs import Mathlib.Algebra.GroupWithZero.Nat import Mathlib.Algebra.Order.BigOperators.Group.Finset import Mathlib.Algebra.Order.BigOperators.Group.List import Mathlib.Algebra.Order.BigOperators.Group.Multiset import Mathlib.Algebra.Order.Chebyshev import Mathlib.Algebra.Order.Field.Basic import Mathlib.Algebra.Order.Floor.Div import Mathlib.Algebra.Order.Group.Abs import Mathlib.Algebra.Order.Group.Int import Mathlib.Algebra.Order.Group.Nat import Mathlib.Algebra.Order.Group.Unbundled.Abs import Mathlib.Algebra.Order.Ring.Abs import Mathlib.Algebra.Order.Ring.Int import Mathlib.Algebra.Order.Ring.Nat import Mathlib.Algebra.Order.Ring.Pow import Mathlib.Algebra.Polynomial.Basic import Mathlib.Algebra.Polynomial.Coeff import Mathlib.Algebra.Ring.Nat import Mathlib.Combinatorics.Colex import Mathlib.Data.Bool.Basic import Mathlib.Data.Fin.Embedding import Mathlib.Data.Fin.VecNotation import Mathlib.Data.Finset.Card import Mathlib.Data.Finset.Powerset import Mathlib.Data.Finset.Prod import Mathlib.Data.Finset.Range import Mathlib.Data.Finset.Sigma import Mathlib.Data.Finset.Sort import Mathlib.Data.Fintype.BigOperators import Mathlib.Data.Fintype.Card import Mathlib.Data.Fintype.EquivFin import Mathlib.Data.Fintype.Pi import Mathlib.Data.Fintype.Prod import Mathlib.Data.Int.Cast.Lemmas import Mathlib.Data.Int.ModEq import Mathlib.Data.Int.Notation import Mathlib.Data.Int.SuccPred import Mathlib.Data.List.Basic import Mathlib.Data.List.GetD import Mathlib.Data.List.MinMax import Mathlib.Data.List.Nodup import Mathlib.Data.List.OfFn import Mathlib.Data.List.Pi import Mathlib.Data.List.Range import Mathlib.Data.Nat.Cast.Order.Ring import Mathlib.Data.Nat.Choose.Basic import Mathlib.Data.Nat.Choose.Bounds import Mathlib.Data.Nat.Choose.Central import Mathlib.Data.Nat.Choose.Sum import Mathlib.Data.Nat.Count import Mathlib.Data.Nat.Log import Mathlib.Data.Nat.Notation import Mathlib.Data.Nat.Size import Mathlib.Data.Nat.Sqrt import Mathlib.Data.Nat.SuccPred import Mathlib.Data.Real.Basic import Mathlib.Data.ZMod.Basic import Mathlib.GroupTheory.Index import Mathlib.LinearAlgebra.Dual.Lemmas import Mathlib.LinearAlgebra.Matrix.Defs import Mathlib.LinearAlgebra.Matrix.Dual import Mathlib.LinearAlgebra.Matrix.ToLin import Mathlib.Logic.Equiv.Fin.Basic import Mathlib.Logic.Function.Basic import Mathlib.NumberTheory.Bertrand import Mathlib.Order.ConditionallyCompleteLattice.Basic import Mathlib.RingTheory.Coprime.Lemmas import Mathlib.Tactic import Mathlib.Tactic.Abel import Mathlib.Tactic.ByContra import Mathlib.Tactic.FieldSimp import Mathlib.Tactic.FinCases import Mathlib.Tactic.GCongr import Mathlib.Tactic.Linarith import Mathlib.Tactic.NormNum import Mathlib.Tactic.Positivity import Mathlib.Tactic.Push import Mathlib.Tactic.Ring import Mathlib.Tactic.SplitIfs import Mathlib.Tactic.Tauto import Theorems.Thm_ThreeSum_BlockSourceCoverInput_Input_of_kept import Theorems.Thm_ThreeSum_LightBlockSourcePreparation_meets set_option autoImplicit false set_option relaxedAutoImplicit false set_option Elab.async false namespace Light end Light namespace ThreeSum.BlockCoefficientRows end ThreeSum.BlockCoefficientRows namespace ThreeSum.BlockEncoding end ThreeSum.BlockEncoding namespace ThreeSum.BlockIndex end ThreeSum.BlockIndex namespace ThreeSum.BlockRows end ThreeSum.BlockRows namespace ThreeSum.BlockSourceFlags end ThreeSum.BlockSourceFlags namespace ThreeSum.GlobalEncoding end ThreeSum.GlobalEncoding namespace ThreeSum.LocalCoverBounds end ThreeSum.LocalCoverBounds
Formal statement
theorem ThreeSum.LightReportingTerminalPreparation.program_meets : ∀ {lim : Light.Limits} {μ : Nat → Int}
{h J occ maps candidates histL histR masksL masksR n base bitBase rowOut work d : Nat}
(o : ThreeSum.BlockEncoding.Occurrences h J)
(setsL setsR :
Nat →
Finset.{0}
(ThreeSum.BlockRows.Coord J
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 512) (instOfNatNat (nat_lit 512))) h)))
(hw : @LE.le.{0} Int Int.instLEInt (@Nat.cast.{0} Int instNatCastInt lim.space) lim.word)
(hd :
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) d
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) J
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 512) (instOfNatNat (nat_lit 512))) h)))
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6))))
lim.depth)
(hocc : @LE.le.{0} Nat instLENat (@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) occ J) base)
(hmaps :
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) maps
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 512) (instOfNatNat (nat_lit 512))) h))
(ThreeSum.GlobalEncoding.scheduleSize h)))
base)
(hcandidates :
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) candidates
(ThreeSum.GlobalEncoding.scheduleSize h))
base)
(hleft :
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) histL
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) (ThreeSum.LightLocalCoverSchedule.rows h)
(ThreeSum.LocalCoverBounds.localPrime h)))
base)
(hright :
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) histR
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) (ThreeSum.LightLocalCoverSchedule.rows h)
(ThreeSum.LocalCoverBounds.localPrime h)))
base)
(hmasksL : @LE.le.{0} Nat instLENat (@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) masksL n) base)
(hmasksR : @LE.le.{0} Nat instLENat (@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) masksR n) base)
(hstop :
@LE.le.{0} Nat instLENat
(ThreeSum.LightReportingTerminalPreparation.stop base
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) J
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 512) (instOfNatNat (nat_lit 512))) h))
n)
bitBase)
(hbits :
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) bitBase
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) J
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 512) (instOfNatNat (nat_lit 512))) h)))
rowOut)
(hrowOut :
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) rowOut
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
work)
(hspace :
@LE.le.{0} Nat instLENat
(ThreeSum.LightSourcePreparation.space work J
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 512) (instOfNatNat (nat_lit 512))) h)
(ThreeSum.LocalCoverBounds.localPrime h))
lim.space)
(hword :
@LE.le.{0} Int Int.instLEInt
(@Nat.cast.{0} Int instNatCastInt
(ThreeSum.LightSourcePreparation.word J
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 512) (instOfNatNat (nat_lit 512))) h)
(ThreeSum.LocalCoverBounds.localPrime h) (ThreeSum.LocalCoverBounds.localPrime h)
((@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 512) (instOfNatNat (nat_lit 512))) h).choose
h)
(ThreeSum.LocalCoverBounds.localBucketCap h)))
lim.word)
(hoccRead :
∀ (j : Nat),
@LT.lt.{0} Nat instLTNat j J →
@Eq.{1} Int (μ (@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) occ j))
(@Nat.cast.{0} Int instNatCastInt (@ThreeSum.BlockCoefficientRows.occurrenceIndices h J o j)))
(hcover : ThreeSum.BlockSourceCoverInput.Input μ h maps candidates histL histR)
(hmaskL :
∀ (i : Nat),
@LT.lt.{0} Nat instLTNat i n →
@Eq.{1} Int (μ (@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) masksL i))
(@Nat.cast.{0} Int instNatCastInt
(@ThreeSum.SubsetAddress.subsetMask
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) J
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 512) (instOfNatNat (nat_lit 512))) h))
(@ThreeSum.BlockIndex.indexSet J
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 512) (instOfNatNat (nat_lit 512))) h)
(setsL i)))))
(hmaskR :
∀ (i : Nat),
@LT.lt.{0} Nat instLTNat i n →
@Eq.{1} Int (μ (@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) masksR i))
(@Nat.cast.{0} Int instNatCastInt
(@ThreeSum.SubsetAddress.subsetMask
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) J
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 512) (instOfNatNat (nat_lit 512))) h))
(@ThreeSum.BlockIndex.indexSet J
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 512) (instOfNatNat (nat_lit 512))) h)
(setsR i))))),
Light.Meets lim ThreeSum.LightReportingTerminalPreparation.program
(@OfNat.ofNat.{0} Nat (nat_lit 17) (instOfNatNat (nat_lit 17))) d
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt J)
(@List.cons.{0} Int
(@HMul.hMul.{0, 0, 0} Int Int Int (@instHMul.{0} Int Int.instMul)
(@OfNat.ofNat.{0} Int (nat_lit 512) (@instOfNat (nat_lit 512))) (@Nat.cast.{0} Int instNatCastInt h))
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt h)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt (ThreeSum.LocalCoverBounds.localPrime h))
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt (ThreeSum.LocalCoverBounds.localBucketCap h))
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt occ)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt maps)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt candidates)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt histL)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt histR)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt masksL)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt masksR)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt n)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt base)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt bitBase)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt rowOut)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt work)
(@List.nil.{0} Int))))))))))))))))))
μ (ThreeSum.LightReportingTerminalPreparation.time h J n) fun (r : Int) (ν : Nat → Int) =>
And
(@Eq.{1} Int r
(@Nat.cast.{0} Int instNatCastInt
(ThreeSum.LightReportingTerminalPreparation.stop base
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) J
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 512) (instOfNatNat (nat_lit 512))) h))
n)))
(And
(∀ (i : Nat),
@LT.lt.{0} Nat instLTNat i n →
@Eq.{1} Int
(ν
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(ThreeSum.LightReportingTerminalPreparation.leftRaw base
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) J
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 512) (instOfNatNat (nat_lit 512))) h)))
i))
(@ThreeSum.BlockEncoding.endpointLeft h J o (setsL i)))
(And
(∀ (i : Nat),
@LT.lt.{0} Nat instLTNat i n →
@Eq.{1} Int
(ν
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(ThreeSum.LightReportingTerminalPreparation.rightRaw base
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) J
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 512) (instOfNatNat (nat_lit 512))) h))
n)
i))
(@ThreeSum.BlockEncoding.endpointRight h J o (setsR i)))
(And
(∀ (i : Nat),
@LT.lt.{0} Nat instLTNat i n →
@Eq.{1} Int
(ν
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(ThreeSum.LightReportingTerminalPreparation.leftFlags base
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) J
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 512) (instOfNatNat (nat_lit 512))) h))
n)
i))
(@Nat.cast.{0} Int instNatCastInt
(@ite.{1} Nat (@ThreeSum.BlockEncoding.LeftAllowed h J o (setsL i))
(@ThreeSum.BlockEncoding.instDecidableLeftAllowed h J o (setsL i))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))))
(And
(∀ (i : Nat),
@LT.lt.{0} Nat instLTNat i n →
@Eq.{1} Int
(ν
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(ThreeSum.LightReportingTerminalPreparation.rightFlags base
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) J
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 512) (instOfNatNat (nat_lit 512))) h))
n)
i))
(@Nat.cast.{0} Int instNatCastInt
(@ite.{1} Nat (@ThreeSum.BlockEncoding.RightAllowed h J o (setsR i))
(@ThreeSum.BlockEncoding.instDecidableRightAllowed h J o (setsR i))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))))
(Light.Kept μ ν base))))) := by
sorry
Source