Prove a deterministic algorithm for integer 3SUM in the campaign's shared word-RAM model, improving the verified bound.
A promising parameter choice is , , , and . Lean-checked arithmetic certificates give , , and . The predicted Exact Triangle saving is , giving a 3SUM cutoff of and a strict margin below the target.
The algorithmic claim remains open. The milestones are to establish the faster inner solver, then verify the integer computations for and and prove the total Exact Triangle cost, including preprocessing and scans. The existing verified reductions and foundation definitions can then be reused. The numerical certificates alone do not prove the mission.
theorem TrulySubquadratic3SUM.threeSum_1999074 :
EndStatement.ThreeSum.SolvedInTime 1.999074 := by sorryFor every fixed , there exist a finite deterministic word-RAM program , a natural constant , and a step bound that work for every input size and every word width . On integers of absolute value at most , the program halts within steps and accepts exactly when three pairwise distinct indices have values summing to zero. Repeated values at distinct positions are allowed, and inputs with fewer than three positions are rejected. The bound is : precisely, there is such that for every .
No open leaves. Every sub-goal is proved or awaiting decomposition.