Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Selecting feasible integer parameters or the boundary regime

Proved
TightCoreset2027.Euclidean.numeric_scale_selection

by Shuze Chen · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

clusteringcomputational-geometrycoresets

Fix z≥1z\ge1z≥1 and a positive error-scale constant AAA. There are a constant c>0c>0c>0 and a nonnegative integer bbb, independent of kkk and ε\varepsilonε, such that the following alternative holds for every k≥1k\ge1k≥1 and 0<ε<10<\varepsilon<10<ε<1. Put

F=cmin⁡{k(2z+2)/(z+2)ε−2,  kε−z−2}[log⁡(2+1/ε)]b.F=\frac{c\min\{k^{(2z+2)/(z+2)}\varepsilon^{-2},\;k\varepsilon^{-z-2}\}}{[\log(2+1/\varepsilon)]^b}.F=[log(2+1/ε)]bcmin{k(2z+2)/(z+2)ε−2,kε−z−2}​.

Either F≤kε−2F\le k\varepsilon^{-2}F≤kε−2, or positive integers n,m,L,qn,m,L,qn,m,L,q satisfy the coding condition, the exact center budget and the error constraint, with

q+(q3)<2L,n(⌈nz/2⌉−1)+m(L+1)≤k,εnqL2<A,F≤12⌈nz/2⌉nmq.q+\binom q3<2^L,\quad n(\lceil n^{z/2}\rceil-1)+m(L+1)\le k,\quad\varepsilon\sqrt{nq}L^2<A,\quad F\le\tfrac12\lceil n^{z/2}\rceil nmq.q+(3q​)<2L,n(⌈nz/2⌉−1)+m(L+1)≤k,εnq​L2<A,F≤21​⌈nz/2⌉nmq.

This isolates the arithmetic and rounding component of the source parameter choice. A larger logarithmic loss is permitted here; using a power of log⁡(2+1/ε)\log(2+1/\varepsilon)log(2+1/ε) alone fits the goal with zero degree on the kkk logarithm. The alternative states exactly when the boundary lower bound suffices and when feasible construction parameters supply the desired cardinality.

Preamble
import Definitions.Def_TightCoreset2027_Euclidean_generalPowers
open scoped BigOperators
set_option autoImplicit false
Formal statement
namespace TightCoreset2027.Euclidean
 theorem numeric_scale_selection (z : ℝ) (hz : 1 ≤ z) (A : ℝ) (hA : 0 < A) :
    ∃ c : ℝ, 0 < c ∧ ∃ b : ℕ,
      ∀ k : ℕ, 1 ≤ k → ∀ ε : ℝ, 0 < ε → ε < 1 →
        c * lowerBoundScale z k ε / (Real.log (2 + 1 / ε)) ^ b ≤
          (k : ℝ) * Real.rpow ε (-2) ∨
        ∃ n m L q : ℕ, 1 ≤ n ∧ 1 ≤ m ∧ 1 ≤ L ∧ 1 ≤ q ∧
          q + Nat.choose q 3 < 2 ^ L ∧
          n * (copyCountZ z n - 1) + m * (L + 1) ≤ k ∧
          ε * Real.sqrt ((n : ℝ) * (q : ℝ)) * (L : ℝ) ^ 2 < A ∧
          c * lowerBoundScale z k ε / (Real.log (2 + 1 / ε)) ^ b ≤
            ((copyCountZ z n : ℝ) * (n : ℝ) * (m : ℝ) * (q : ℝ)) / 2 := by sorry
end TightCoreset2027.Euclidean
Source
Hu–Huang–Li–Xu, STOC2027 submission879, §2.3 parameter choice and rounding, printed pp.15–16 / PDF pp.17–18, and §2.5 small/larger-error parameter choices and boundary cases, printed pp.20–21 / PDF pp.22–23; Theorem1.2 and footnote1 logarithmic convention; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/879.pdf

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