Selecting feasible integer parameters or the boundary regime
ProvedTightCoreset2027.Euclidean.numeric_scale_selectionclusteringcomputational-geometrycoresets
Fix and a positive error-scale constant . There are a constant and a nonnegative integer , independent of and , such that the following alternative holds for every and . Put
Either , or positive integers satisfy the coding condition, the exact center budget and the error constraint, with
This isolates the arithmetic and rounding component of the source parameter choice. A larger logarithmic loss is permitted here; using a power of alone fits the goal with zero degree on the 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.EuclideanSource
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