Welcome to Randal Douc's wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.


====== Question ======


<WRAP center round tip 80%>
Let $D$ be an infinite set without accumulation points in $\mathbb{R}^d$.  
Show that, for every $n \in \mathbb{N}^*$, there exists a ball containing exactly $n$ points of $D$.  

</WRAP>

===== Proof =====


First, note that $D$ must be countable. Indeed, for each point $x \in D$, one can associate a **rational ball** (that is, a ball with rational center coordinates and rational radius) containing $x$ as the only element of $D$. This defines an injection from $D$ into the countable set of rational balls, which proves that $D$ is countable.

Now consider, for $(a,b) \in D \times D$, the affine hyperplane
$$
H_{a,b} = \{ x \in \mathbb{R}^d \; ; \; \|x-a\| = \|x-b\| \}.
$$

Define
$$
G = \bigcup_{a,b \in D} H_{a,b}.
$$

Since $G$ is a countable union of closed sets with empty interior, it still has empty interior by Baire’s theorem. Therefore, $G$ cannot be the whole $\mathbb{R}^d$. We can choose a point $c \in \mathbb{R}^d \setminus G$.

The distances $\|c-x\|$ for $x \in D$ are then all distinct. Define
$$
A = \{ \|c-x\| \; ; \; x \in D \}.
$$  

To order these distances strictly, it is enough to check that, for every $r>0$, the set $A \cap [0,r]$ is finite. But $A \cap [0,r]$ corresponds to the number of points in $D \cap B(c,r)$, which is a compact set containing no accumulation points. Hence it is finite.

We can thus write $A = \{\rho_n \; ; \; n \geq 1\}$ with $\rho_n$ strictly increasing.  
For every $n \geq 1$, by choosing a radius $\rho$ such that $\rho_n < \rho < \rho_{n+1}$, the ball $B(c,\rho)$ contains exactly $n$ points of $D$.  

----


<WRAP center round important 80%>
===== Remarks: =====

  * One can avoid Baire’s theorem by using a measure-theoretic argument. Let $\lambda_d$ be the Lebesgue measure on $\mathbb{R}^d$. Since $\lambda_d(H_{a,b})=0$, we get $\lambda_d(\bigcup_{a,b \in D} H_{a,b})=0$. Hence $\bigcup_{a,b \in D} H_{a,b} \neq \mathbb{R}^d$.
  * For $D = \mathbb{Z}^d$, one can construct $c$ explicitly, for example $c=(\pi,\ldots,\pi^d)$. Then, for $a,b \in \mathbb{Z}^d$, the equality $\|c-a\|^2=\|c-b\|^2$ becomes a polynomial equation with integer coefficients having $\pi$ as a root. This is impossible unless $a=b$, since $\pi$ is not algebraic. However, this explicit construction of $c$ does not generalize (or at least not simply) when $D$ is not $\mathbb{Z}^d$.
  * Obviously, when $D = \mathbb{Z}^d$, one does not need to prove that $D$ is countable, nor that $A \cap [0,r]$ is finite, which significantly shortens the proof.

</WRAP>
Welcome to Randal Douc's wiki

User Tools

Site Tools

Page Tools
