Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Orthonormality of the coordinate planes of the selector construction

Proved
ExactKMeans.ProductReduction.coordinate_frame_orthonormal

by milia · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorycomputational-geometry

Let a,b≥1a,b\ge1a,b≥1 with ab≥2ab\ge2ab≥2 and odd t≥3t\ge3t≥3 be the Section 5 parameters, and work in R2b+1\mathbb R^{2b+1}R2b+1. The selector lives in the coordinate planes span⁡(ej,ej⊥)\operatorname{span}(e_j,e_j^\perp)span(ej​,ej⊥​), j=1,…,bj=1,\dots,bj=1,…,b, which occupy the first 2b2b2b coordinates, and the last coordinate direction is the axis e^\hat ee^ along which the selectors are placed.

  1. The vectors e1,…,eb,e1⊥,…,eb⊥e_1,\dots,e_b,e_1^\perp,\dots,e_b^\perpe1​,…,eb​,e1⊥​,…,eb⊥​ form an orthonormal family: ⟨ej,ek⟩=⟨ej⊥,ek⊥⟩=[j=k]\langle e_j,e_k\rangle=\langle e_j^\perp,e_k^\perp\rangle=[j=k]⟨ej​,ek​⟩=⟨ej⊥​,ek⊥​⟩=[j=k] and ⟨ej,ek⊥⟩=0\langle e_j,e_k^\perp\rangle=0⟨ej​,ek⊥​⟩=0.
  2. Each eje_jej​ and each ej⊥e_j^\perpej⊥​ is orthogonal to the axis, and e^\hat ee^ is a unit vector.
  3. For all real coefficients x1,…,xbx_1,\dots,x_bx1​,…,xb​ and y1,…,yby_1,\dots,y_by1​,…,yb​,
∥∑j=1b(xj ej+yj ej⊥)∥2=∑j=1b(xj2+yj2).\Big\|\sum_{j=1}^{b}\big(x_j\,e_j+y_j\,e_j^\perp\big)\Big\|^2=\sum_{j=1}^{b}\big(x_j^2+y_j^2\big).​j=1∑b​(xj​ej​+yj​ej⊥​)​2=j=1∑b​(xj2​+yj2​).

These are the basic facts about the ambient coordinate system of the construction. Every selector point, the averaged vector eˉ=1b∑jej\bar e=\frac1{\sqrt b}\sum_j e_jeˉ=b​1​∑j​ej​, and the reference displacement μ^(s)=rb∑jej(sj)\hat\mu(s)=\frac{r}{\sqrt b}\sum_j e_j(s_j)μ^​(s)=b​r​∑j​ej​(sj​) are combinations of this form, so norms of means and cluster costs reduce to sums of squares of coefficients.

Formalization Note In the published definitions, eje_jej​, ej⊥e_j^\perpej⊥​ and e^\hat ee^ are the standard unit vectors of R2b+1\mathbb R^{2b+1}R2b+1 in coordinates 2j2j2j, 2j+12j+12j+1 and 2b2b2b (zero-based, j<bj<bj<b), and [j=k][j=k][j=k] denotes the Kronecker delta.

Preamble
import Definitions.Def_ExactKMeans_ProductReduction_Selector

open scoped BigOperators Classical
open Finset
open ExactKMeans.ProductReduction
Formal statement
namespace ExactKMeans.ProductReduction

theorem coordinate_frame_orthonormal (p : Parameters) :
    (∀ j k : Fin p.b, inner ℝ (e p j) (e p k) = if j = k then (1 : ℝ) else 0) ∧
    (∀ j k : Fin p.b, inner ℝ (ep p j) (ep p k) = if j = k then (1 : ℝ) else 0) ∧
    (∀ j k : Fin p.b, inner ℝ (e p j) (ep p k) = 0) ∧
    (∀ j : Fin p.b, inner ℝ (e p j) (axis p) = 0 ∧ inner ℝ (ep p j) (axis p) = 0) ∧
    inner ℝ (axis p) (axis p) = 1 ∧
    ∀ x y : Fin p.b → ℝ,
      ‖∑ j, (x j • e p j + y j • ep p j)‖ ^ 2 = ∑ j, (x j ^ 2 + y j ^ 2) := by sorry

end ExactKMeans.ProductReduction
Source
Bai, Fomin, Xu (2026), Exact Euclidean k-Means: Faster in the Plane, Hard Beyond It, held STOC 2027 submission; SHA-256 89f18334320ba73627305c6f8870ae70fef423ca012f8b71a3052e407c7e62ec, printed pp. 28–31 (PDF 29–32), Definitions 3–4: the b orthogonal coordinate planes with basis vectors e_j, e_j^⊥ and their normalized averages; used in the proof of Lemma 14, printed p. 31

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me