Construct raw source endpoints and both independent trim flags
ProvedThreeSum.LightSourcePreparation.Procs.meetsFix blocks of width , required row size , modulus , and masks below . Memory stores valid block selections into pairs of weight rows, a valid map-to-candidate table into histogram pairs, weights bounded by , and histogram entries bounded by . All inputs precede two coefficient arrays of length , then two raw arrays of length , a flag area of length , bit cells, two row-result cells, and scratch , in that order.
Assume the specified procedures, , , and the defined source-preparation space and word budgets fit . For mask , let be the one-hot sum with coefficients , and let interchange the two weight rows. The output satisfies
Each flag requires row cardinality and the corresponding bucket cap in every block. Execution meets the defined preparation time budget and preserves memory below the first coefficient array.
This constructs endpoint arithmetic and trimming decisions together.
/- 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_Bundle02 import Definitions.Def_ThreeSum1962Source_Bundle03 import Definitions.Def_ThreeSum1962Source_Bundle05 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 Lean.Elab.Tactic.Omega import Mathlib.Algebra.BigOperators.Fin import Mathlib.Algebra.BigOperators.Group.Finset.Basic 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.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.Sigma import Mathlib.Data.Finset.Sort import Mathlib.Data.Fintype.BigOperators import Mathlib.Data.Fintype.Card 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.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_LightBlockSourceHashes_Procs_meets import Theorems.Thm_ThreeSum_LightSourceFlagArray_Procs_meets set_option autoImplicit false set_option relaxedAutoImplicit false set_option Elab.async false namespace Light end Light namespace ThreeSum.BlockCoefficientRows end ThreeSum.BlockCoefficientRows
theorem ThreeSum.LightSourcePreparation.Procs.meets : ∀ {lim : Light.Limits} {P : Light.Program} {d pMain : Nat} (C : ThreeSum.LightSourcePreparation.Procs P pMain)
{μ : Nat → Int}
{J L h p cap occ maps candidates histL histR masks n coeff0 coeff1 rawLeft rawRight flags bitBase rowOut work U V M
K : Nat}
(sel candidate mask : Nat → Nat) (w0 w1 leftCount rightCount : Nat → Nat → Nat)
(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 L))
(@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5))))
lim.depth)
(hp : @LT.lt.{0} Nat instLTNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) p)
(hh : @LE.le.{0} Nat instLENat h L)
(hocc : @LE.le.{0} Nat instLENat (@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) occ J) coeff0)
(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))) L)
M))
coeff0)
(hcandidates :
@LE.le.{0} Nat instLENat (@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) candidates M) coeff0)
(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) K p))
coeff0)
(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) K p))
coeff0)
(hmasks : @LE.le.{0} Nat instLENat (@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) masks n) coeff0)
(hc0 :
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) coeff0
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) J L))
coeff1)
(hc1 :
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) coeff1
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) J L))
rawLeft)
(hrawLeft :
@LE.le.{0} Nat instLENat (@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) rawLeft n) rawRight)
(hrawRight :
@LE.le.{0} Nat instLENat (@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) rawRight n) flags)
(hflags :
@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) flags
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) n))
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
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 L))
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 L U) lim.space)
(hword :
@LE.le.{0} Int Int.instLEInt (@Nat.cast.{0} Int instNatCastInt (ThreeSum.LightSourcePreparation.word J L p U V cap))
lim.word)
(hsel : ∀ (j : Nat), @LT.lt.{0} Nat instLTNat j J → @LT.lt.{0} Nat instLTNat (sel j) M)
(hcandidate : ∀ (s : Nat), @LT.lt.{0} Nat instLTNat s M → @LT.lt.{0} Nat instLTNat (candidate s) K)
(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 (sel j)))
(hcandidateRead :
∀ (s : Nat),
@LT.lt.{0} Nat instLTNat s M →
@Eq.{1} Int (μ (@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) candidates s))
(@Nat.cast.{0} Int instNatCastInt (candidate s)))
(hread0 :
∀ (s : Nat),
@LT.lt.{0} Nat instLTNat s M →
∀ (a : Nat),
@LT.lt.{0} Nat instLTNat a L →
@Eq.{1} Int
(μ
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@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))) L)
s))
a))
(@Nat.cast.{0} Int instNatCastInt (w0 s a)))
(hread1 :
∀ (s : Nat),
@LT.lt.{0} Nat instLTNat s M →
∀ (a : Nat),
@LT.lt.{0} Nat instLTNat a L →
@Eq.{1} Int
(μ
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@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))) L)
s))
L)
a))
(@Nat.cast.{0} Int instNatCastInt (w1 s a)))
(hbound0 :
∀ (s : Nat),
@LT.lt.{0} Nat instLTNat s M → ∀ (a : Nat), @LT.lt.{0} Nat instLTNat a L → @LE.le.{0} Nat instLENat (w0 s a) U)
(hbound1 :
∀ (s : Nat),
@LT.lt.{0} Nat instLTNat s M → ∀ (a : Nat), @LT.lt.{0} Nat instLTNat a L → @LE.le.{0} Nat instLENat (w1 s a) U)
(hcountL :
∀ (k : Nat),
@LT.lt.{0} Nat instLTNat k K →
∀ (r : Nat),
@LT.lt.{0} Nat instLTNat r p →
@Eq.{1} Int
(μ
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@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) k p))
r))
(@Nat.cast.{0} Int instNatCastInt (leftCount k r)))
(hcountR :
∀ (k : Nat),
@LT.lt.{0} Nat instLTNat k K →
∀ (r : Nat),
@LT.lt.{0} Nat instLTNat r p →
@Eq.{1} Int
(μ
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@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) k p))
r))
(@Nat.cast.{0} Int instNatCastInt (rightCount k r)))
(hcountBoundL :
∀ (k : Nat),
@LT.lt.{0} Nat instLTNat k K →
∀ (r : Nat), @LT.lt.{0} Nat instLTNat r p → @LE.le.{0} Nat instLENat (leftCount k r) V)
(hcountBoundR :
∀ (k : Nat),
@LT.lt.{0} Nat instLTNat k K →
∀ (r : Nat), @LT.lt.{0} Nat instLTNat r p → @LE.le.{0} Nat instLENat (rightCount k r) V)
(hmaskRead :
∀ (i : Nat),
@LT.lt.{0} Nat instLTNat i n →
@Eq.{1} Int (μ (@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) masks i))
(@Nat.cast.{0} Int instNatCastInt (mask i)))
(hmaskBound :
∀ (i : Nat),
@LT.lt.{0} Nat instLTNat i n →
@LT.lt.{0} Nat instLTNat (mask i)
(@HPow.hPow.{0, 0, 0} Nat Nat Nat
(@instHPow.{0, 0} Nat Nat (@NPow.toPow.{0} Nat (@Monoid.toNPow.{0} Nat Nat.instMonoid)))
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) J L))),
Light.Meets lim P pMain d
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt J)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt L)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt h)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt p)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt cap)
(@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 masks)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt n)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt coeff0)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt coeff1)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt rawLeft)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt rawRight)
(@List.cons.{0} Int (@Nat.cast.{0} Int instNatCastInt flags)
(@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.LightSourcePreparation.time n J L U) fun (x : Int) (ν : Nat → Int) =>
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) rawLeft i))
(@Nat.cast.{0} Int instNatCastInt
(ThreeSum.OneHotMask.eval (ThreeSum.BlockCoefficientRows.flat J L p sel w0)
(ThreeSum.BlockCoefficientRows.flat J L p sel w1)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) J L) (mask 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) rawRight i))
(@Nat.cast.{0} Int instNatCastInt
(ThreeSum.OneHotMask.eval (ThreeSum.BlockCoefficientRows.flat J L p sel w1)
(ThreeSum.BlockCoefficientRows.flat J L p sel w0)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) J L) (mask 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) flags i))
(@Nat.cast.{0} Int instNatCastInt
(ThreeSum.LightSourceFlagArray.flag J L h p cap sel candidate w0 w1 leftCount (mask 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)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) flags n) i))
(@Nat.cast.{0} Int instNatCastInt
(ThreeSum.LightSourceFlagArray.flag J L h p cap sel candidate w1 w0 rightCount (mask i))))
(Light.Kept μ ν coeff0)))) := by
sorry