3
$\begingroup$

The following problem came up in one of my research works. Suppose that $C$ denotes the positive face of the $d$-dimensional unit sphere surface, i.e. $$C := \{\mathbf{x} \in \mathbb{R}^d: x_1 >0,\ldots,x_d>0, \|\mathbf{x}\|_2 =1\}~.$$

I am given a fixed real number $\rho \in (0,1)$. Then, how many points can I have at maximum on $C$, such that all their pairwise inner products are bounded above by $\rho$? In other words, I am trying to fill up $C$ in a most crowded manner, such that the points are separated enough.

It seems to me that there should be some well known result in Mathematics about this, but I cannot figure it out. For my research purpose, I would be happy if the maximum number of such possible points is of the order $e^{\mathrm{poly}(d)}$, and if so, I would be grateful if someone can tell me the exact degree of this $\mathrm{poly}(d)$, assuming $\rho$ is fixed.

$\endgroup$
5
  • $\begingroup$ Do you want the inner products bounded above? If you want them bounded below you can take arbitrarily many that are all close to the same vector $\endgroup$
    – user44143
    Commented Mar 20, 2021 at 2:12
  • $\begingroup$ @MattF.You are right, I want bounded above. Changed it. $\endgroup$ Commented Mar 20, 2021 at 2:56
  • $\begingroup$ How you come you expect an exponential bound? I'm a bit confused - what is the obstruction to a polynomial bound, perhaps obtained by summing the areas of disjoint discs centered at the points? $\endgroup$
    – Leo Moos
    Commented Mar 20, 2021 at 3:07
  • $\begingroup$ It is polynomial in $\rho$ but exponential in $d$. I think your reasoning shows it is at most $(1/\varepsilon)^d$, up to a constant and for $\rho=\cos(\varepsilon)$, or something similar. $\endgroup$
    – Pierre PC
    Commented Mar 20, 2021 at 3:21
  • $\begingroup$ @PierrePC Oops, my bad. In any case I'm glad it worked out in this way. $\endgroup$
    – Leo Moos
    Commented Mar 20, 2021 at 10:37

1 Answer 1

5
$\begingroup$

Having scalar product above $\rho$ is equivalent to having spherical distance above $2\theta$, where $\theta=\cos(\rho)/2$. I consider first the case of the whole sphere, and I'll discuss the positive orthant at the end.

Upper bound

Let us begin by finding an upper bound. Suppose that you have points $x_1,\ldots,x_N$ on the surface of the $(d-1)$-sphere, at spherical distance at least $2\theta$ from each other. Then there are disjoint open cones $C_i$ in the unit $d$-sphere, where $C_i$ is the interior of the convex hull of

  • the vertex $0$,
  • the points $y$ on the $(d-1)$-sphere with $\langle x_i,y\rangle=\sin(\theta)$

The cones $C_i$ and $C_j$ are disjoint whenever $i \neq j$, because points in $C_i$ have angles with $x_i$ of less than $\theta$, and points in $C_j$ have angles with $x_j$ of less than $\theta$, but the angle between $x_i$ and $x_j$ is at least $2\theta$.

This means that $N\cdot|C_1|_d\leq |\mathbb B^d|_d$, where $|\cdot|_d$ denotes the Lebesgue volume in dimension $d$ and $\mathbb B^d$ is the unit ball in $\mathbb R^d$. Since the height of the cones is $\cos(\theta)$, their volume is $$|C_1|_d=\frac1d|\mathbb B^{d-1}|_{d-1}\cdot\sin(\theta)^{d-1}\cdot\cos(\theta).$$ and therefore $$N \leq \frac{|\mathbb B^d|_d}{|\mathbb B^{d-1}|_{d-1}}\cdot\frac{d}{\cos(\theta)}\cdot\sin(\theta)^{1-d}.$$ Since the first ratio goes to zero (as $1/\sqrt d$, up to constant), $N$ has to be asymptotically less than $\lambda^d$ for all $\lambda>1/\sin(\theta)$.

Lower bound

Let $x_1,\ldots,x_N$ be a maximal family of points on the sphere given the constraint that two points are at spherical distance at least $2\theta$. The sphere is covered by the closed caps centred at the $x_i$ with spherical radius $2\theta$, since any point not covered could be added to the maximal family. Then the unit ball is covered by closed cones $C'_i$, where $C'_i$ is the set of $ty$ with

  • $0\leq t\leq 1/\cos(2\theta)$,
  • $y$ is a point on the unit sphere with $\langle x_i,y\rangle\leq\sin(2\theta)$.

In other words, the base of the cone $C'_i$ is tangent to the unit sphere, and is just large enough so that it contains the spherical cap associated to $x_i$. This way, the $C'_i$ cover the sphere, so they have to cover the unit ball also.

This means that, considering the Lebesgue measure, $$ |\mathbb B^d|_d\leq N\cdot\frac1d|\mathbb B^{d-1}|_{d-1}\tan(2\theta)^{d-1}\cdot1 $$ and $N$ satisfies the bound $$ d\frac{|\mathbb B^d|_d}{|\mathbb B^{d-1}|_{d-1}}\tan(2\theta)^{1-d}\leq N. $$

The positive orthant

Writing $K_d$ for the ratio $|\mathbb B^d|_d/|\mathbb B^{d-1}|_{d-1}$, the above shows that the maximal number of points $N_\text{max}$ at spherical distance at least $2\theta$ on the surface of $\mathbb S^{d-1}$ satisfies $$ K_d d\tan(2\theta)^{1-d}\leq N_\text{max}\leq K_d d\frac1{\cos(\theta)}\sin(\theta)^{1-d}. $$ In other words, it grows exponentially in $d$ ($\ln(N)/d$ is bounded above and below by constants depending on $\theta$ but not $d$). For this we need the fact that $K_d$ decreases as $d^{-d/2}$, which one can show using explicit expression for the volume of a $d$-dimensional ball together with Stirling's formula.

Of course the upper bound still holds on the positive orthant. Using an averaging argument (see below), we can show that for the portion of sphere you consider, $$ 2K_d d(\tan(2\theta)/2)^{1-d}\leq\widetilde N_\text{max}\leq K_d d\frac1{\cos(\theta)}\sin(\theta)^{1-d}, $$ so the constant in the exponent is asymptotically $1/\theta$: $$ \limsup_{\theta\to0}\limsup_d\left|\frac1d\ln(\widetilde N_\text{max})+\ln(\theta)\right| = 0. $$

Averaging argument

(Note: the averaging argument is not really required here, the proof would work directly with a fraction of the sphere, but it's a nice argument.)

Let $X=\{x_1,\ldots,x_N\}$ be a set of points on $\mathbb S^{d-1}$ at spherical distance at least $2\theta$. We can divide $\mathbb R^d$ in $2^d$ open orthants $S_1,\ldots,S_{2^d}$ (and a set of measure zero that will not contribute in the following). For each of them, there exists a rotation $R_i$ sending it to $S_1$, i.e. $S_1 = R_iS_i$. Let $R$ be a random rotation in $SO_d(\mathbb R)$, distributed according to the Haar measure (say left-invariant, although the left- and right-invariant measures are actually the same in this case), and $\mathbb E$ the corresponding expectation. Then $$ \begin{align*} N &= \mathbb E[\#RX] \\ &= \mathbb E[\#(S_1\cap RX)] + \cdots + \mathbb E[\#(R_{2^d}^{-1}S_1\cap RX)] \\ &= \mathbb E[\#(S_1\cap RX)] + \cdots + \mathbb E[\#(S_1\cap R_{2^d}RX)] \\ &= 2^d\mathbb E[\#(S_1\cap RX)]. \end{align*} $$ It means that there must exist an $R_0$ with $\#(S_1\cap R_0X)\geq N/2^d$, otherwise the expectation could not be this high. Now the set $S_1\cap R_0X$ consists of at least $N/2^d$ points in a fixed orthant at spherical distance at least $2\theta$. Using this reasoning with the $N_\text{max}$ described in the previous section gives the expected estimate on $\widetilde N_\text{max}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .