1
$\begingroup$

Does anyone know anyway or any algorithm that can exactly and/or numerically find lines $\left\{ l_{i}\right\} _{i=1}^{n_{k}+2}$ that maximizes $$\min_{1\le i<j\le n_{k}+2}\text{angle}\left(l_{i},l_{j}\right)$$ in $\mathbb{R}^{n_{k}}$ for some sequence of integers $1<n_{1}<n_{2}\cdots<n_{k}<\cdots?$ Thanks a lot.

$\endgroup$
3
  • $\begingroup$ I'm pretty sure this can be turned into some version of a sphere packing problem. $\endgroup$ – user44191 Apr 16 '20 at 2:11
  • $\begingroup$ Equivalently, one can talk about points (in place of lines) of real projective n-spaces. (Of course, projective n-space corresponds to $\ \Bbb R^{n+1}$). The metric of the projective n-space comes from the euclidean unit $\ S^n.$ $\endgroup$ – Wlod AA Apr 16 '20 at 3:15
  • $\begingroup$ @user44191 Just wondering, suppose that the question were regarding sphere packing instead, would you be able to find the coordinates of the optimal points for infinitely many dimensions? Thanks. $\endgroup$ – Tanger Apr 16 '20 at 9:24
1
$\begingroup$

Bukh and Cox provide exact constructions for the infinite sequence $n_k\equiv 1\bmod 3$. Sloane maintains numerical solutions for $n_k\leq 16$. Computer-assisted proofs of optimality have been obtained for $n_k\leq 6$; see this paper and references therein.

Edit: The Bukh–Cox construction is contained in the proofs of their Lemma 16 and Theorem 3. In what follows, I isolate the construction for convenience. (Throughout, I use their notation whenever possible, so your $n_k$ is replaced by $d$, for example.) Put $k=2$ and $N=\binom{k+1}{2}=3$, and let $A$ denote any $k\times N$ equiangular tight frame. See this survey for general information on these objects, but in this case, we may take

$$ A = \left[\begin{array}{rrr}1&-\frac{1}{2}&-\frac{1}{2}\\0&\frac{\sqrt{3}}{2}&-\frac{\sqrt{3}}{2}\end{array}\right].$$

If we denote the columns of $A$ by $x_1,x_2,x_3$, then notice that each $x_i$ has unit norm and $|\langle x_i,x_j\rangle|=\frac{1}{2}=:\beta$ for every $1\leq i<j\leq 3$. Take

$$ C:=\frac{1}{\beta}(A^\top A-I)+I. $$

Then the diagonal entries of $C$ are $1$ and the off-diagonal entries of $C$ are $\pm1$. One may further show that $\lambda:=\lambda_\mathrm{max}(C)=\frac{1}{\beta}(\frac{N}{k}-1)+1$. Since $d\equiv -k\bmod N$ by assumption, we have $b:=\frac{d+k}{N}\in\mathbb{N}$. Put $\epsilon=\frac{1}{b\lambda-1}$ and consider the matrix $G:=(1+\epsilon)I-\epsilon(C\otimes J)$, where $I$ is the identity matrix of size $Nb=d+k$ and $J$ is the all-ones matrix of size $b$. One may show that $G$ is positive semidefinite with rank at most $d$, and so $G=XX^\top$ for some $X\in\mathbb{R}^{d\times (d+k)}$. The columns of $X$ are unit vectors that achieve equality in the Bukh–Cox bound (i.e., Theorem 2(a)). It follows that the lines they span maximize the minimum interior angle.

$\endgroup$
5
  • $\begingroup$ Thank you for your answer. I'll look into the papers that you refer to. Thanks. $\endgroup$ – Tanger Apr 16 '20 at 1:39
  • $\begingroup$ Just wondering, if Bukh and Cox have provided exact, probably implementable, constructions for the infinite sequence, then why does Sloane maintain numerical solutions only for finitely many dimensions, with respect to the question? Thanks a lot. $\endgroup$ – Tanger Apr 16 '20 at 1:47
  • $\begingroup$ Sloane posted the numerical solutions in the 90s, and I'm not sure how regularly he updates his table (if at all). Meanwhile, the Bukh--Cox result is quite recent. $\endgroup$ – Dustin G. Mixon Apr 16 '20 at 1:59
  • $\begingroup$ Okay, thank you for the information. But it seems in Bukh and Cox's paper that d and k need to satisfy a special modulo equation and that the bound(s) they established rely on another maximin function. So where can one find the optimal lines for the question? Thanks a lot. $\endgroup$ – Tanger Apr 16 '20 at 3:42
  • $\begingroup$ @Tanger - Their construction is spread across a couple of proofs in their paper, so I updated my answer with a description. $\endgroup$ – Dustin G. Mixon Apr 16 '20 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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