Proof of `Clustering of a tuple`

groundedproofs/Lax185574Proofs/Clustering.lean · lax-185574

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.

Read the Lean proof on GitHub

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 rr, 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 4ρ−2r4ρ − 2r, and entries of different groups are farther apart than 6ρ≥4ρ+2r6ρ ≥ 4ρ + 2r.

For the detection property, if every vertex of XX is near the tuple, then the vertices of SS lie in distinct blocks, by the scattering of SS. Conversely, if some vertex x0x₀ of XX is far from the tuple and no vertex of XX is at a distance between rr and HH, then the blocks met by XX inject into SS minus the representative of x0x₀.