Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Source: published paper, printed p. 220, Lemma 2.2; proof on p. 221.

Statement

If S⊂RnS\subset\mathbb R^n is tt-separated, then every closed ball of radius s≥0s\ge0 contains at most (2s/t+1)n(2s/t+1)^n points of SS.

Full proof

Place open radius-t/2t/2 balls at the points of SS in the given closed ball. Their interiors are disjoint and all lie in the concentric open ball of radius s+t/2s+t/2. Comparing volumes and canceling the unit-ball volume gives

#(S∩B‾(p,s))≤(s+t/2)n(t/2)n=(2s/t+1)n.\#(S\cap\overline B(p,s))\le \frac{(s+t/2)^n}{(t/2)^n}=(2s/t+1)^n.

This works first for every finite subcollection, hence also proves that the collection is finite. Open small balls avoid any boundary-overlap issue.

For a separated torus set, the same local bound holds whenever each point in the torus ball is represented by a lift in the Euclidean radius-ss ball. Distinct chosen lifts remain tt-separated, since Euclidean distance is at least quotient distance. The ball need not be contained in one fundamental cube. This is the form used to bound the Bernoulli neighborhoods.

Bears on. Problem 188.