Theorem 5.4 — integral optima need not be ranges
OpenSampleRemoval.Supplement.theorem_5_4least-squaresoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1robustness-auditsample-removal
For the six points displayed in Theorem 5.4, the intercept-plus-regressor design is in GP and the saddle lifts are in LGP. Among all four-element retained sets, is the unique minimizer of cross-scatter, with
The next smallest value is attained and equals . Nevertheless, no strict plane cut of the saddle lifts selects exactly ; the unique integral optimum is not a lifted-plane range.
Differences from the source:
- encoding: printed terminating decimals and one-based point labels → exact rational real coordinates and zero-based
Fin 6indices; reason: this changes no mathematical instance and makes every equality and strict inequality exact
Preamble
import Mathlib import Definitions.Def_SampleRemoval_GeneralPosition import Definitions.Def_SampleRemoval_Supplement_simpleDesign import Definitions.Def_SampleRemoval_Supplement_crossScatter import Definitions.Def_SampleRemoval_Supplement_IsLGP import Definitions.Def_SampleRemoval_Supplement_IsLiftedPlaneRangeOn import Definitions.Def_SampleRemoval_Supplement_points54 set_option autoImplicit false
Formal statement
namespace SampleRemoval.Supplement
/-- **Theorem 5.4 (Integral optima need not be ranges).** The displayed exact six-point instance
is in GP and LGP; `{p₂,p₃,p₅,p₆}` uniquely minimizes `F` over four-sets, has the stated
value and next-best value, and is not a lifted-plane range (Xu, Gao, Hu, STOC 2027 submission,
manuscript sha256 `dcd33ace…`, Theorem 5.4, p.10 (PDF p.12)).
**Formalization Note** The paper's indices are one-based; `S` therefore uses Lean indices
`1,2,4,5`. Printed decimals in `points54` are exact terminating rationals in `ℝ`. The next
smallest value is stated by both attainment and a lower bound over every competing four-set,
avoiding any empty-infimum convention. -/
theorem theorem_5_4 :
let S : Finset (Fin 6) := Finset.univ.filter (fun i => i.1 = 1 ∨ i.1 = 2 ∨ i.1 = 4 ∨ i.1 = 5)
SampleRemoval.GeneralPosition (simpleDesign points54) ∧
IsLGP points54 ∧
S.card = 4 ∧
crossScatter points54 S = -(37469 : ℝ) / 8000 ∧
(∀ T : Finset (Fin 6), T.card = 4 → T ≠ S →
crossScatter points54 S < crossScatter points54 T) ∧
(∃ T : Finset (Fin 6), T.card = 4 ∧ T ≠ S ∧
crossScatter points54 T = -(185881 : ℝ) / 40000) ∧
(∀ T : Finset (Fin 6), T.card = 4 → T ≠ S →
-(185881 : ℝ) / 40000 ≤ crossScatter points54 T) ∧
¬ IsLiftedPlaneRangeOn points54 Finset.univ S := by sorry
end SampleRemoval.Supplement
Source
Xu, Gao, Hu, Rounding, Ranges, and Exact Sample-Removal Audits for Least Squares, STOC 2027 submission (manuscript sha256 dcd33acebc1ccdc626c7ee41bfabc29795abe2e1cd9267d8cbd66d98f81c4b26), Theorem 5.4, p.10 (PDF p.12)