# Alternative proof (more geometric?) of packing statement, Exercise 3, Section 13.1 in Matousek

The following (rephrased) exercise is given on page 315 of Matousek's book [1].

Fix $$n \geq 1$$ and let $$\mathscr{X} \subset \mathbb{S}^{n-1}$$ be $$\sqrt{2}$$-separated, so that $$\|x - y\|_2 \geq \sqrt{2} \quad \mbox{for all distinct}~x, y \in \mathscr{X}.$$ Show that the cardinality satisfies $$|\mathscr{X}| \leq 2n$$.

Above, $$\|\cdot\|_2$$ denotes the standard Euclidean norm and $$\mathbb{S}^{n-1} \subset \mathbb{R}^n$$ the unit sphere.

Here's my approach to a solution.

Solution: We note the separation condition, is equivalent to $$\langle x, y \rangle \leq 0, \quad \mbox{for all distinct}~ x, y \in \mathscr{X}.$$ Now, induct on the dimension. The claim is obvious when $$n = 1$$. For $$n > 1$$, fix $$x \in \mathscr{X}$$ and partition $$\mathscr{X}$$ as $$\mathscr{X} = \mathscr{Y} \cup \{x\}, \quad \mbox{and} \quad \mathscr{Y} = \mathscr{Y}_0 \cup\mathscr{Y}_<.$$ Here we split $$\mathscr{X}$$ into $$x$$ and its complement, $$\mathscr{Y}$$, which is further split into the part with strictly negative (resp., 0) inner product with $$x$$, given by $$\mathscr{Y}_{<}$$ (resp., $$\mathscr{Y}_0$$). Consider the projection, $$\pi(u) = u - \langle u, x \rangle x$$. We claim that $$\pi(y) \neq \pi(y') \quad \mbox{for any distinct}~y, y' \in \mathscr{Y}.$$ This obviously holds for $$y, y' \in \mathscr{Y}_0$$. If $$y, y' \in \mathscr{Y}_<$$, then $$0 \geq \langle y, y' \rangle = \langle y, x \rangle \langle y', x\rangle + \langle \pi(y), \pi(y') \rangle > \langle \pi(y), \pi(y') \rangle,$$ implying $$\pi(y) \neq \pi(y')$$. If $$y \in \mathscr{Y}_0, y' \in \mathscr{Y}_<$$, then similarly, $$\langle \pi(y), \pi(y')\rangle \leq 0$$, which implies $$\pi(y) \neq \pi(y')$$ (otherwise $$y = \pm x$$). Finally, set $$\mathscr{Y}_{<, \neq} = \mathscr{Y}_< \setminus \mathrm{ker}(\pi)$$. Then the collection $$\mathscr{X'} = \pi(\mathscr{Y}_{0}) \cup \Big\{\, \frac{\pi(y)}{\| \pi(y) \|_2} : y \in \mathscr{Y}_{<, \neq} \,\Big \}$$ is (the image of) a set of vectors in $$\mathbb{S}^{n-2}$$ with pairwise nonpositive inner product. Induction yields $$|\mathscr{Y}_{<, \neq}| + |\mathscr{Y}_0| = |\mathscr{X'}| \leq 2(n-1) = 2n-2.$$ Concluding, we find $$|\mathscr{X'}| = |\mathscr{Y}_<| + |\mathscr{Y_0}| + 1 \leq (|\mathscr{Y}_{<, \neq}| + 1) + |\mathscr{Y}_0| + 1 \leq 2n.$$

Although I think it is correct, I feel like it is maybe too complicated. I feel like there should be a more "geometric" proof that simply uses some observation that each time we add a point it requires the remaining points to lie in some (intersection of) halfspace(s) and there can't be too many of those.

[1] Matoušek, Jiří. Lectures on discrete geometry. Graduate Texts in Mathematics, 212. Springer-Verlag, New York, 2002.