Proof of `Clustering of a tuple`
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
In the paper
- page 46 of this submission's paper
Description
The existence of an admissible pair is the grouping iteration: start with all indices surviving at scale , and while two surviving entries are within eight times the scale, drop one of them and multiply the scale by nine. At the end, entries of one group are within twice the scale , hence within , and entries of different groups are farther apart than .
For the detection property, if every vertex of is near the tuple, then the vertices of lie in distinct blocks, by the scattering of . Conversely, if some vertex of is far from the tuple and no vertex of is at a distance between and , then the blocks met by inject into minus the representative of .