Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The construction angle α\alphaα is well defined (Section 5)

Proved
ExactKMeans.ProductReduction.alpha_spec

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

complexity-theorycomputational-geometry

This lemma shows that the angle α\alphaα fixed in the Section 5 construction is well defined.

Let a,b≥1a,b\ge 1a,b≥1 be integers with ab≥2ab\ge 2ab≥2, let t≥3t\ge 3t≥3 be odd, and put N=abtN=abtN=abt and λ=N12−t+1\lambda=N^{12}-t+1λ=N12−t+1. The construction chooses a positive angle α\alphaα with

12<αλ<1andλsin⁡α=cos⁡((t−1)α),\frac12<\alpha\lambda<1 \qquad\text{and}\qquad \lambda\sin\alpha=\cos\big((t-1)\alpha\big),21​<αλ<1andλsinα=cos((t−1)α),

and then sets r=1/(b N12sin⁡α)r=1/(\sqrt b\,N^{12}\sin\alpha)r=1/(b​N12sinα). The lemma asserts that such an angle exists. Consequently the chosen α\alphaα satisfies all of the displayed conditions, and moreover

sin⁡α>0andr>0.\sin\alpha>0 \qquad\text{and}\qquad r>0 .sinα>0andr>0.

The later quantitative statements of Section 5 involve α\alphaα, rrr and γ=αrδ/b\gamma=\alpha r\delta/\sqrt bγ=αrδ/b​ and rely on these defining relations and on positivity. This lemma isolates that fact so that it can be imported once instead of being re-derived in each proof.

Formalization Note In the published definition, α\alphaα is a choice (Classical.epsilon) of a real number satisfying the displayed conditions; without an existence proof it would be an unconstrained real number. The conclusion lists, in order, 0<α0<\alpha0<α, 12<αλ\tfrac12<\alpha\lambda21​<αλ, αλ<1\alpha\lambda<1αλ<1, the defining equation, sin⁡α>0\sin\alpha>0sinα>0 and r>0r>0r>0.

Preamble
import Definitions.Def_ExactKMeans_ProductReduction_Selector

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

theorem alpha_spec (p : Parameters) :
    0 < p.alpha ∧ (1 / 2 : ℝ) < p.alpha * p.lam ∧ p.alpha * p.lam < 1 ∧
      (p.lam : ℝ) * Real.sin p.alpha = Real.cos (((p.t : ℝ) - 1) * p.alpha) ∧
      0 < Real.sin p.alpha ∧ 0 < p.r := 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: choice of the positive angle α with 1/2<αλ<1 and λ sin α=cos((t−1)α), and r=1/(√b N^12 sin α)

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