0
$\begingroup$

Let $S^{n-1}$ be the unit sphere in $\mathbb{R}^{n}$.

Let $\{e_1,\ldots,e_n\}$ be an orthonormal basis for $\mathbb{R}^{n}$.

Let $\Sigma=\{e_1,-e_1,\ldots,e_n,-e_n\}$ be the set of $2n$ points thought of as a subset of $S^{n-1}$.

For any $p\in S^{n-1}$, let $$c_n(p) = \mathrm{dist}(p,\Sigma)$$ where dist is the intrinsic distance of $S^{n-1}$.

Let $$c_n = \sup_{p\in S^{n-1}} c_n(p).$$

Questions

(a) Is the formula for $c_n$ written down somewhere? If so, what is it? If not, can you figure one out?

(b) What is $\lim_{n\rightarrow\infty}c_n$?

$\endgroup$
  • $\begingroup$ Your $\Sigma$ is also known as the orthoplex code (=generalized octahedron). Neil Sloane has a database of spherical codes, and I would search that first. I also expect SPLAG to discuss the $c_n$ sequence in the early chapters, but my copy is in my office, and I don't remember this detail. $\endgroup$ – Jyrki Lahtonen Jul 10 '13 at 18:54
  • 2
    $\begingroup$ $c_n = \cos^{-1}\frac{1}{\sqrt{n}}$, it is attained by vectors of the form $\frac{1}{\sqrt{n}}(\pm e_1 \pm e_2 \pm \ldots\pm e_n)$ $\endgroup$ – achille hui Jul 10 '13 at 19:00
  • $\begingroup$ Correct, @achille (I calculated it as I didn't remember). Wanna type it out as an answer or should I? $\endgroup$ – Jyrki Lahtonen Jul 10 '13 at 19:01
  • $\begingroup$ @Jyrki I'll do it. $\endgroup$ – achille hui Jul 10 '13 at 19:05
  • $\begingroup$ Thanks, I guess it's not surprising (b) is $\pi/2$...or is it? $\endgroup$ – Mud Jul 10 '13 at 19:29
2
$\begingroup$

Let $\theta(\vec{p},\vec{q})$ be the intrinsic distance/angle between any two unit vectors $\vec{p}, \vec{q} \in S^{n-1}$. Notice $1 - \cos \theta(\vec{p},\vec{q}) = 1 - \vec{p}\cdot\vec{q}$ is a stricting increasing function of $\theta$, this means for any finite set of unit vectors $\Sigma \subset S^{n-1}$, we have:

$$1 - \cos\theta(\vec{p},\Sigma) = 1 - \cos(\min_{\vec{q}\in\Sigma}\theta(\vec{p},\vec{q})) = \min_{\vec{q}\in\Sigma}(1 - \cos \theta(\vec{p},\vec{q})) = 1 - \max_{\vec{q}\in\Sigma}\vec{p}\cdot\vec{q}$$

When $\Sigma = \{ \pm \vec{e}_1, \ldots, \pm \vec{e}_n \}$, this reduces to:

$$\cos\theta(\vec{p},\Sigma) = \max_{i=1..n} |p_i|$$

where $p_i = \vec{p}\cdot\vec{e}_i$ is the coordinates of $\vec{p}$ with respect to the orthonormal base $\{ \vec{e}_1, \ldots \vec{e}_n \}$.

Finding $c_n$ is equivalent to maximizing $1 - \cos\theta(\vec{p},\Sigma)$. This is equivalent to minimizing $\cos\theta(\vec{p},\Sigma)$ which in turn equivalent to minimizing $$(\cos \theta(\vec{p},\Sigma))^2 = \max_{i=1..n}p_i^2$$

Since $\sum_{i=1}^n p_i^2 = 1$, the minimum of $\{ \max_{i=1..n}p_i^2 : \vec{p} \in S^{n-1} \}$ is clearly equal to $1/n$ and attained when $\vec{p}$ has the form $\frac{1}{\sqrt{n}}(\pm \vec{e}_1 \pm \cdots \pm \vec{e}_n )$. From this, we can conclude:

$$c_n = \sup_{\vec{p} \in S^{n-1}} \theta(\vec{p},\Sigma) = \cos^{-1}\frac{1}{\sqrt{n}} \quad\text{ and }\quad \lim_{n\to\infty} c_n = \cos^{-1} 0 = \frac{\pi}{2}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.