Suppose, we are given a set of $k$ unit vectors $v_1,\ldots,v_k$ in $\mathbb{R}^n$. Consider all possible dot products among distinct vectors $v_i \cdot v_j$, where $i \ne j$. Let,

$$\alpha = \max_{1 \le i <j \le k} \{v_i \cdot v_j\}.$$

What is the minimum possible value of $\alpha$?

  • 1
    $\begingroup$ Is that an answer or a half-baked attempt? $\endgroup$ Dec 15, 2012 at 14:49
  • 1
    $\begingroup$ Also math.berkeley.edu/~noahgian/files/spheres.pdf seems relevant $\endgroup$
    – Vanessa
    Dec 15, 2012 at 15:14
  • 2
    $\begingroup$ I haven't read the article in detail, but the problem of packing spheres on a sphere is exactly the same as selecting unit vectors s.t. all dot products are above some fixed value. Since this is an introductory article I suspect that the article and references therein should tell you about state-of-the-art in understanding this problem $\endgroup$
    – Vanessa
    Dec 15, 2012 at 17:07
  • 1
    $\begingroup$ This may be better suited for math.SE or even MathOverflow. $\endgroup$
    – Jeffε
    Dec 16, 2012 at 4:54
  • 4
    $\begingroup$ $\alpha = - 1 / (k-1)$. This value is attained when vectors $v_i$ are vertices of a regular simplex (centered at $0$). This fact is used a lot in the design and analysis of Semidefinite Programming algorithms. (This question is not a research-level question in TCS.) $\endgroup$
    – Yury
    Dec 16, 2012 at 6:12

2 Answers 2


Answer: $\alpha = - 1/(k-1)$. This value is attained when vectors $v_i$ are the vertices of a regular simplex, centered at the origin.

This follows from symmetry: given a set of vectors $u_i$ consider new vectors $u_i'= \frac{1}{\sqrt{k}}\left( u_i \oplus u_{i+1} \oplus \dots \oplus u_{i-1} \right)$ (where we add up all vectors $u_i$ in the cyclic order starting from $u_i$). It is easy to show that vectors $u'_i$ form a better (or equal) solution than vectors $u_i$, and that vectors $u_i$ are vertices of a regular simplex (not necessarily centered at $0$). Symmetry arguments (like this one) are very useful in general for finding extreme configurations of vectors. In this case, it is very easy to find the value of $\alpha$ directly.

I. Let us first prove that $\alpha \geq -\frac{1}{k-1}$. We have, $$0 \leq \|v_1 + \dots + v_k\|^2 = \sum_i \|v_i\|^2 + 2\sum_{i < j} v_i \cdot v_j \leq \sum_i 1 + 2\sum_{i<j} \alpha = k + k(k-1) \alpha.$$ We get that $\alpha \geq - 1/(k-1)$.

II. Now we prove that $\alpha \leq -\frac{1}{k-1}$. Consider a $k\times k$ matrix $A = (a_{ij})$ with $a_{ii} = 1$ and $a_{ij} = {-1/(k-1)}$ for $i\neq j$. This matrix is (non-strictly) diagonally dominant and thus is positive semidefinite. (Note also that $A$ is the normalized Laplacian matrix of $K_k$.) Therefore, there exist a set of vectors $v_i$ with $v_i \cdot v_j = a_{ij}$. We get that $$\alpha \leq \max_{i\neq j} a_{ij} = -1/(k-1).$$

We proved that $\alpha = -1/(k-1)$. Note that vectors $v_i$ are vertices of a regular simplex since the distance $\|v_i - v_j\| = \sqrt{2- 2v_i \cdot v_j} = \sqrt{2k/(k-1)}$ is the same for all pairs $i,j$ (where $i\neq j$), and $\sum v_i =0$ since $\|\sum v_i\|^2 = 0$.

What we computed equals $$-\frac1{\vartheta(\text{empty graph on } k \text{ vertices})-1},$$ where $\vartheta$ is the Lovász Theta Function; see the Wikipedia article on the Lovász Theta Function for details.

  • $\begingroup$ That was a great answer and one I was looking for. Thanks a lot, Yury! $\endgroup$ Dec 17, 2012 at 2:27
  • 2
    $\begingroup$ What happens when $k>n+1$? $\endgroup$ Dec 18, 2012 at 12:08
  • 3
    $\begingroup$ @KlausDraeger: That's a much more difficult problem! There is no closed form expression for $\alpha$ in this case. Extreme configurations of vectors are known only for certain values of $n$ and $k$. A configuration of vectors on the unit sphere in $n$ dimensions s.t. $\langle v_i, v_j \rangle \leq t$ is known as $(n,k,t)$ spherical code. The question asks to find the best possible $t$ s.t. an $(n,k,t)$ spherical code exists. See table 1 on p. 102 in [Cohn, Kumar. Universally optimal distribution of points on spheres. J. of AMS, vol. 20, n. 1; available on arXiv] for the list of known results. $\endgroup$
    – Yury
    Dec 18, 2012 at 16:42
  • $\begingroup$ See also neilsloane.com/packings/index.html . $\endgroup$
    – Yury
    Dec 18, 2012 at 16:54
  • $\begingroup$ what is a regular simplex? Is it not the convex hull of 0 and e_i's? $\endgroup$ Apr 5, 2020 at 4:03

This problem is closely related to the graph coloring problem. The problem is to color the vertices of a $k$-colorable graph with as few colors as possible. The following vector program is a relaxation of the graph coloring problem.

$$minimize \qquad \alpha \qquad \qquad \\ subject \ to \quad v_i \cdot v_j \le \alpha \quad \; \; \, \forall (i,j) \in E \\ \qquad \quad \ v_i \cdot v_i = 1 \quad \quad \forall i \in V \\ \qquad \qquad \quad \ v_i \in \mathbb{R}^n \quad \forall i \in V$$

The claim is that $-\frac{1}{k-1}$ is the minimum possible value of $\alpha$.

  • 6
    $\begingroup$ Is this an answer or a clarification to the question ? Also, are you asking how to understand a claim ? if so, pointing to the original source is helpful. $\endgroup$ Dec 16, 2012 at 5:04
  • $\begingroup$ One of my friends asked me this question. I don't know from where he got this. $\endgroup$ Dec 16, 2012 at 9:44
  • $\begingroup$ I believe the source may be Lemma 4.1 of this paper. They don't show prove the upper bound, but give an explicit construction that reaches this bound. $\endgroup$ Apr 11, 2023 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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