13
$\begingroup$

If one arranges $2d$ points on the sphere $\mathbf S^{d-1}\subset\Bbb R^d$ at the vertices of the crosspolytope, then one can achieve a minimal spherical distance of $\pi/2$ between any two points, and this is best possible.

What if I want to arrange $2d+1$ points on $\mathbf S^{d-1}$ as far apart as possible from each other? What are the best known upper and lower bounds on the minimal distance between any two points in such an arrangement, and is there anything known about how these arrangements look like?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
7
$\begingroup$

I finally came to do the computations on Yoav Kallus' comment. After quite some tedious work one finds a cubic polynomial:

$$p_d(x)\,=\,d(d-2)^2 x^3 - d^2 x^2 - dx + 1$$

which has exactly one zero in the interval $[0,1]$. This zero is the cosine of the maximal distance between points in Yoav's solution. In fact, comparing with this source, these values seem to agree with the best known solutions (and for $d\in\{2,3\}$ they are proven to be optimal). These solutions are cited from

  • T. Ericson and V. Zinoviev, "Codes on Euclidean spheres"

but I wasn't able to find the exact place where they are computed.

Improve this answer
$\endgroup$
6
$\begingroup$

OK, it's late and I may be wrong but I think that you can obtain the $2d$ points by using any set of orthonormal basis vectors $\{v_1,\ldots,v_d\}$ and their negatives.

Now if $n$ is such that a Hadamard matrix exists, you could take the rows of $H$ an $n\times n$ Hadamard matrix in its $\pm 1$ formulation, and its negative. If you then remove the first column, that would leave you with pairwise inner product $\pm \frac{1}{n} \sqrt{\frac{n}{n-1}}$ or something of this ilk. You can then convert this to the angle $\theta.$ This means that your $d=n-1.$

Maybe more general constructions exist, and feel free to shoot down my answer.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thanks for your answer. If I made no mistake, then this gives $2d+2$ points on $\mathbf S^{d-1}$ with minimal spherical distance $\arccos(1/d)$ (assuming that a Hadamard matrix of size $(d+1)\times(d+1)$ exists). $\endgroup$
    – M. Winter
    Commented May 7, 2020 at 9:03
  • 3
    $\begingroup$ In the case $d=3$ one can achieve a better result for $2d+1=7$ points using the vertices of a bipyramid with pentagonal base. This yields a slightly larger minimal distance $2\pi/5>\arccos(1/3)$. In this case, the Hadamard construction gives the vertices of a cube. $\endgroup$
    – M. Winter
    Commented May 7, 2020 at 9:54
  • 1
    $\begingroup$ Also for eight points in three dimensions the maximin distance is not obtained with a cube. If you have eight points on a cube, you can twist one of the faces in-plane, thus increasing the length of the lateral edges. Then you are free to move the twisted square and its opposite slightly closer (and slightly expand them) to get a greater overall maximin distance. $\endgroup$
    – Oscar Lanzi
    Commented Aug 19, 2023 at 16:41
6
$\begingroup$

Turns out kodlu's idea works in all dimensions, regardless of the existence of any Hadamard matrices.

Consider all coordinate permutations of

$$(1,...,1,-d)\in\Bbb R^{d+1}\quad\text{and}\quad (-1,...,-1,d)\in\Bbb R^{d+1}.$$

This gives $2d+2$ points in $\Bbb R^{d+1}$, but all these lie in the $d$-dimensional subspace orthogonal to $(1,...,1)$. The smallest angle between two of these is attained e.g. between $a=(1,...,1,-d)$ and $b=(-1,...,-1,d,-1)$, whose cosine turns out to be

$$\cos\measuredangle(a,b)=\frac{\langle a,b\rangle}{\|a\|\|b\|} = \frac{\overbrace{(-1)+\cdots+(-1)}^{d-1}+d+d}{\underbrace{1+\cdots+1}_d+d^2} = \frac{d+1}{d(d+1)}=\frac1d.$$

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ One way to describe this configuration is to consider on of the points as the "north pole", then you have a (d-1)-simplex on one lattitudinal cross section (the "tropic of cancer") another one, with the opposite orientation, on the "tropic of capricorn", and another point on the souther pole. The minimum distance is not realized inside each line of lattitude, but only between adjacent ones. Since we have one more point than needed, we can remove the south pole, and pull the tropics south a little bit. This should increase the minimal distance slightly. $\endgroup$
    – Yoav Kallus
    Commented May 10, 2020 at 15:17

You must log in to answer this question.

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