1
$\begingroup$

I assume that this sort of question has already been considered at great length. Nevertheless, I could not find an answer to this question in the related literature.

Given a constant $a\in (0,2]$, what are the known upper bounds of the maximum number of points we can place on the $d$-dimensional unit sphere such that the Euclidean distance between any two of them is larger or equal to $a$, for $d\gg 1$?

$\endgroup$

1 Answer 1

4
$\begingroup$

If I interpreted your question correctly this is really about spherical codes. This is a difficult problem that is unsolved in general, there are some bounds, however.

I will use $n$ for the dimension, since $d$ is used for minimum distance of related binary codes.

A spherical code is a collection of points on the surface of the $n-$ sphere. There are some known constructions and a series of bounds. I recommend pages 24-29 of Conway and Sloane's Sphere Packings, Lattices and Groups, as a good place to get started with plenty of references.

Link with coding theory: If we have a binary code (a subset of $\{0,1\}^n$) of length $n$ and minimum hamming distance $d,$ we can map (say) the symbol $0$ to $+1$ and the symbol $1$ to $-1$ and normalize by $\sqrt{n}$ to obtain points on the Euclidean unit sphere, i.e., a spherical code, where the maximal angle between any two codewords is $\phi=\cos^{-1}\left(1-\frac{2d}{n}\right)$. And this gives a Euclidean minimum distance of $$2 \sin(\phi/2)$$ for the spherical code. This, however, does not usually give the best constructions since there aren't that many good pairwise constant distance codes.

Bounds: Let $A(n,\phi)$ be the largest possible number of points on the $n-$dimensional unit sphere with maximal angle $\leq \phi,$ then some lower bounds on $A(n,\phi)$ are known. In general, for large $n$ is the nonconstructive bound via random coding arguments dating back to Shannon:

$$A(n,\phi)\geq 2^{-n \log_2 sin \phi (1+o(1))}.$$

Other "nice" bounds include $$A(n,\phi)=n+1,\quad for \quad \frac{\pi}{2} \leq \phi \leq \sec^{-1}(-n),$$ for a regular simplex, $$A(n,\pi/2)=2n,$$ for a regular cross-polytope.

Also look up the Kabatianskii-Levenshtein bound.

I know there is much more recent work on Spherical codes by H. Cohn and others but I have not kept up with developments.

Edit: The recent paper by Manin and Marcolli available here might help.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much @kodlu for your answer. I think that the Shannon's lower bound is interesting. However, I was looking for an upper bound, and it seems I cannot use Kabatianskii-Levenshtein bounds for deriving it (nor the results by H. Cohn that I found online). Could you please suggest me any reference to obtain an upper bound for $A(n,\phi)$? $\endgroup$ Commented Dec 11, 2020 at 16:18

You must log in to answer this question.

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