Theorem 1.2 — Euclidean coreset lower bound at every error scale
ProvedTightCoreset2027.Euclidean.euclidean_coreset_lower_boundFix any real exponent . There are a positive constant and nonnegative integer degrees , depending only on , such that for every integer and every , some positive finite dimension and finite set force every strong -coreset for -clustering to satisfy
The coreset must preserve every set of exactly distinct ambient centers, with absolute relative error, and may use any nonnegative weights on any subset of . No sampling or mass constraint is imposed. The dimension and dataset may depend on but precede the candidate subset and its weights. This is the full lower bound in Theorem 1.2 under footnote 1's asymptotic convention, including all real exponents, both error regimes, , and arbitrarily small positive errors.
Formalization Note The constants and log degrees are quantified before . All logarithm arguments exceed in this domain. The calibrated general-power construction and boundary arguments of §2.5 remain proof obligations; they are not hypotheses of this theorem.
Differences from the source:
- encoding: tilde-Omega with z-only constants and finite polylogarithmic factors by footnote 1 → positive c_z and natural degrees a_z,b_z chosen before k and epsilon, with the displayed denominator; reason: this is precisely the source asymptotic convention, not instance-dependent constants
- encoding: a finite subset of Euclidean space and every exact-k ambient center set → Finset (EuclideanSpace R (Fin d)) for data and all ambient queries; reason: finite sets preserve distinct support and exact cardinality; Euclidean coordinates use an isometric representation
- encoding: arbitrary nonnegative weights defined on S → an arbitrary ambient NNReal function whose values outside S are ignored; reason: every source weight function extends by zero, including zero weights and the empty candidate
import Definitions.Def_TightCoreset2027_Euclidean_coresetModel set_option autoImplicit false
namespace TightCoreset2027.Euclidean
theorem euclidean_coreset_lower_bound (z : ℝ) (hz : 1 ≤ z) :
∃ c : ℝ, 0 < c ∧ ∃ a b : ℕ,
∀ k : ℕ, 1 ≤ k → ∀ ε : ℝ, 0 < ε → ε < 1 →
∃ d : ℕ, 1 ≤ d ∧ ∃ X : Finset (Point d),
∀ (S : Finset (Point d)) (w : Point d → NNReal),
IsStrongCoreset z ε k X S w →
c * lowerBoundScale z k ε /
((Real.log (2 + (k : ℝ))) ^ a * (Real.log (2 + 1 / ε)) ^ b)
≤ (S.card : ℝ) := by sorry
end TightCoreset2027.Euclidean
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.