1
$\begingroup$

Let $\|\cdot\|_2$ denote the Euclidean norm, let $\langle \cdot, \cdot\rangle$ denote the standard dot product, and let $\mathcal{S}^{d-1} = \{\mathbf{x} \in \mathbb{R}^d: \|\mathbf{x}\|_2 = 1\}$ denote the Euclidean unit sphere in $\mathbb{R}^d$. For constants $\alpha, \beta$ such that $[\alpha, \beta]$ is a subinterval of $[-1, 1]$, define

$$\mathcal{P}_{[\alpha, \beta]}(d) = \{S \subseteq \mathcal{S}^{d-1}: \text{for all distinct } \mathbf{x}, \mathbf{y} \in S \text{ it holds that } \alpha \leq \langle \mathbf{x}, \mathbf{y}\rangle \leq \beta\}.$$

In other words, dot products between any two vectors in $S$ must always lie in the interval $[\alpha, \beta] \subseteq [-1, 1]$ for $S$ to be contained in $\mathcal{P}_{[\alpha, \beta]}$. For certain values of $\alpha$ and $\beta$ I am interested in (upper bounds on) high-dimensional asymptotics of the maximal size of such sets $S \in \mathcal{P}_{[\alpha, \beta]}(d)$:

$$M_{[\alpha, \beta]} = \lim_{d \to \infty} \frac{1}{d} \log_2\left(\max_{S \in \mathcal{P}_{[\alpha, \beta]}(d)} |S|\right)$$

Without the condition on the minimum dot product (i.e. with $\alpha = -1$), we are looking for standard sphere packing bounds, and e.g. the famous Kabatiansky-Levenshtein result states $M_{[-1, 1/2]} \leq 0.4014135\dots$. For $\alpha > -1$, the additional condition can be interpreted as not only putting spheres around points $\mathbf{x} \in S$, but also putting spheres of potentially different radius around $-\mathbf{x}$.

For $\alpha = -\beta$, the additional condition with $\alpha$ can be interpreted as only considering sphere packings where either none or both of $\pm\mathbf{x}$ are included in packings $S$, for arbitrary $\mathbf{x} \in \mathcal{S}^{d-1}$. Since any packing in $\mathcal{P}_{[-\beta, \beta]}$ induces a packing in $\mathcal{P}_{[-1, \beta]}$, one trivially has $M_{[-\beta, \beta]} \leq M_{[-1, \beta]}$, which together with Kabatiansky-Levenshtein's results leads to upper bounds on $M_{[-\beta, \beta]}$.

Note that the conditions on spheres around $\mathbf{x}$ and $-\mathbf{x}$ are not quite symmetric: it is possible to construct arbitrarily large sets $S \in \mathcal{P}_{[\alpha, 1]}$ by clustering a large number of points around an arbitrary point $\mathbf{x} \in \mathcal{S}^{d-1}$. In a sense, the upper bound $\beta$ on the inner products is more restrictive than the lower bound $\alpha$.

Some concrete research questions that came up:

  1. What can be said about $M_{[-\beta, \beta]}$? Is it the same as $M_{[-1, \beta]}$? In other words: is the maximum packing density of antipodal packings the same as of arbitrary sphere packings?

  2. For $|\alpha| < \beta$, what can be said about $M_{[\alpha, \beta]}$ other than $M_{[\alpha, -\alpha]} \leq M_{[\alpha, \beta]} \leq M_{[-\beta, \beta]}$? Can we perhaps show that $M_{[\alpha, \beta]}$ is the same as $M_{[\alpha, -\alpha]}$ if $\beta$ is not too close to $1$?

If general remarks about $M_{[\alpha, \beta]}$ are too much to ask for, I'm mostly interested in finding non-trivial upper bounds for $M_{[-1/k, 1/2]}$ for integer $k \geq 2$.

Any help or pointers to relevant literature would be greatly appreciated!


Edit: To add, Kabatiansky and Levenshtein studied the first problem above as well, and concluded that their method does not give sharper upper bounds on $M_{[-\beta,\beta]}$ than those obtained by first using the trivial relation $M_{[-\beta,\beta]} \leq M_{[-1,\beta]}$ and then applying their upper bound on $M_{[-1,\beta]}$. They conjecture that $M_{[-1,\beta]} = M_{[-\beta, \beta]}$ just after Equation (69) in the English version of the paper, but they do not give a proof. Alas, it seems that to obtain sharper bounds on $M_{[-1,\beta]}$ (or proving that there do not exist sharper bounds) it does not suffice to only use K-L's techniques.

$\endgroup$
  • $\begingroup$ Anyone? (Is this likely an open problem that cannot be solved easily?) $\endgroup$ – TMM Feb 2 '18 at 18:43

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.