Theorem 9 — -separated points in a radius- ball number at most
ProvedParallelHAC.Supplement.theorem_9_packingclusteringcomputational-geometryhierarchical-clusteringp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let and , and let be a set of points such that for all distinct and for some . Then is finite and
This folklore packing bound is the only place where low dimension enters the paper's arguments: it underlies the packability of centroid and Ward's linkage (Theorems 1 and 2).
Formalization Note is an arbitrary set, so finiteness is part of the conclusion; is Set.ncard.
Differences from the source:
- generalization: (1 + R/r)^{O(k)} → (1 + R/r)^{3k}; reason: the exponent 3k is the one the proof on p.53 gives; an explicit exponent implies the O(k) claim
- encoding: a collection of points P with |P| ≤ … → P : Set (EuclideanSpace ℝ (Fin k)), conclusion P.Finite ∧ (P.ncard : ℝ) ≤ …; reason: finiteness of P is a consequence, so it is concluded; ncard of a finite set is its cardinality
Preamble
import Mathlib
Formal statement
namespace ParallelHAC.Supplement
/-- **Theorem 9** (Packing points in `ℝ^k`, folklore; p.14): let `r > 0`, `R ≥ 0`, and let
`P ⊆ ℝ^k` be a set of points with `‖u − v‖ ≥ r` for all distinct `u, v ∈ P`, contained in a closed
ball `B(x, R)`. Then `P` is finite, `|P| ≤ (1 + 3R/r)^k`, and `(1 + 3R/r)^k ≤ (1 + R/r)^{3k}`.
Source: arXiv:2507.20047 (sha256 a21061c8…), §3, Theorem 9, printed p.14 (PDF p.17); restated
and proved in App. A.1, printed p.53 (PDF p.56).
**Formalization Note.** `ℝ^k` is `EuclideanSpace ℝ (Fin k)` and `B(x, R)` is
`Metric.closedBall x R`. `P` is any set, so finiteness is part of the conclusion. The paper's
`(1 + R/r)^{O(k)}` is stated with the exponent `3k` that its proof gives (p.53). -/
theorem theorem_9_packing (k : ℕ) (r R : ℝ) (hr : 0 < r) (hR : 0 ≤ R)
(P : Set (EuclideanSpace ℝ (Fin k)))
(hsep : ∀ u ∈ P, ∀ v ∈ P, u ≠ v → r ≤ ‖u - v‖)
(x : EuclideanSpace ℝ (Fin k)) (hx : P ⊆ Metric.closedBall x R) :
P.Finite ∧ (P.ncard : ℝ) ≤ (1 + 3 * R / r) ^ k ∧
(1 + 3 * R / r) ^ k ≤ (1 + R / r) ^ (3 * k) := by sorry
end ParallelHAC.Supplement
Source
Bateni, Dhulipala, Fletcher, Gowda, Hershkowitz, Jayaram, Łącki, Parallel Hierarchical Agglomerative Clustering in Low Dimensions, arXiv:2507.20047 (sha256 a21061c8…), §3, Theorem 9, p.14 (PDF p.17); proof App. A.1, p.53 (PDF p.56)