Game of Sloanes
A game to find putatively optimal packings in complex projective space with the goal of proving optimality of as many packings as possible.
This website concerns the problem of packing \(n\) lines, represented by unit vectors, through the origin of \(\mathbb{C}^d\) such that the angles between the lines are as large as possible. The problem has applications in fields such as compressed sensing, digital fingerprinting, quantum state tomography, and multiple description coding.
Let \(\Phi=\left(\varphi_j\right)_{j=1}^n\) be a set of unit norm vectors. The coherence \(\mu\) of \(\Phi\) is defined to be \[ \mu\left(\Phi\right) = \max_{1\leq j < k\leq n} \vert\langle \varphi_j, \varphi_k \rangle\vert. \] We call \(\Phi\) a Grassmannian frame or (optimal) projective packing if \[ \Phi \in \operatorname{argmin}\left\{ \mu(\Psi) \, : \, \Psi \textrm{ \(n\) unit norm vectors in \(\mathbb{C}^d\)} \right\}. \] For a review of results about complex Grassmannian frames, see the paper [JKM19].
Let \(\Phi=\left(\varphi_j\right)_{j=1}^n\) be a set of unit norm vectors. The coherence \(\mu\) of \(\Phi\) is defined to be \[ \mu\left(\Phi\right) = \max_{1\leq j < k\leq n} \vert\langle \varphi_j, \varphi_k \rangle\vert. \] We call \(\Phi\) a Grassmannian frame or (optimal) projective packing if \[ \Phi \in \operatorname{argmin}\left\{ \mu(\Psi) \, : \, \Psi \textrm{ \(n\) unit norm vectors in \(\mathbb{C}^d\)} \right\}. \] For a review of results about complex Grassmannian frames, see the paper [JKM19].
Leader Board
Packings for all \(2 \leq d \leq 7\) and \(d+2 \leq n \leq 49\), plus sporadic packings.
Legend and Further Notes
- The Grassmannian frames for \(d = n\) are orthonormal bases and for \(d+1 = n\) are regular simplices, hence we do not list them.
- Best Coherence gives the best coherence of the packings which have been submitted for that \(d\) and \(n\). A new packing is considered better if it beats the previous packing in at least the eighth decimal place.
- Lower Bound gives the maximum of whichever of the Bukh-Cox, Welch-Rankin, orthoplex, and/or Levenstein bounds are valid for that \(d\) and \(n\).
- Creator gives a 3–4 character string indicating the creator of the packing.
- etf: A known equiangular tight frame. See, e.g., [FM16] and the references therein.
- orth: The maximal known set of vectors in \(\mathbb{C}^d\) which saturate the orthoplex bound. When \(d\) is a prime power, this collection is a maximal set of mutually unbiased bases consisting of \(d^2 + d\) vectors. See, e.g., [KlRo04] and the reference therein.
- Lev: A set of vectors which saturate the (second) Levenstein bound.
- B-C: A set of vectors which saturate the Bukh-Cox bound.
- AUTO: Removing a vector from the best known packing for \(d\) and \(n+1\) results in a better coherence than any of the submitted packings for \(d\) and \(n\).
- njas: Grassmannian frames in \(\mathbb{C}^2\) are equivalent to optimal spherical codes in \(S^2\). The configurations labeled with njas are best known spherical codes in \(S^2\) downloaded from [Sloane1].
- dgm, ejk, and JJ: Dustin G. Mixon, Emily J. King, and John Jasper.
- BGM+19: From the paper [BGM+19].
- CID+21: From the paper [CID+21].
- Matlab File contains a link to a .mat file with the best submitted packing formated as a \(d \times n\) matrix with unit-norm columns in Matlab.
- Text File contains a link to a .txt file with the best submitted packing formated as a newline-separated list of the \(2 d n\) entries of the vectors, starting with the real parts of the first vector, then the real parts of the second vector, and so on until the imaginary parts of the last vector.
- Notes contain the following information:
- ○ indicates that the configuration is provably optimal.
- △ indicates that the configuration is conjectured to be optimal.
- When pertinent, a reference to a paper or website is listed.
- For a listing of numerically approximated and explicitly defined optimal packings when \(n=d^2\), see [FSDH], [Grassl], and [Flamm].
Submission
If you have a collection of \(n\) vectors in \(\mathbb{C}^d\) which has a better coherence (to at least the eighth decimal point) than what is listed above, we welcome you to submit it to the site. We will accept sporadic packings for \(d\) and \(n\) not listed above if there is evidence that the packing is truly optimal. We accept submissions in one of two different forms:
- A .mat file with the vectors represented as unit-norm columns in a \(d \times n\) matrix. OR
- A .txt file consisting of a newline-separated list of the \(2 d n\) entries of the (unit-norm) vectors, starting with the real parts of the components of the first vector, then the real parts of the components of the second vector, and so on until the imaginary parts of the components of the last vector.
Open Problems
- Conjecture: The frames of \(8\) vectors in \(\mathbb{C}^3\) that result from removing a single vector from any of the known equiangular tight frames of \(9\) vectors in \(\mathbb{C}^3\) are Grassmannian frames.
Sources: [JKM19]; independently conjectured by Henry Cohn. - Conjecture: Assume that an equiangular tight frame of \(d^2\) vectors in \(\mathbb{C}^d\) exists. Then removing one vector from that equiangular tight frame results in a Grassmannian frame of \(d^2-1\) vectors in \(\mathbb{C}^d\).
Source: Conjectured by Henry Cohn. - Conjecture: The following is a Grassmannian frame of \(5\) vectors in \(\mathbb{C}^3\): \[ \Phi = \left[ \begin{array}{ccccc} a & b & b & c & c \\ b & a & b & cw & cw^2 \\ b & b & a & cw^2 & cw \end{array} \right], \] \[ a = \frac{\sqrt{13}+\sqrt{2+\sqrt{13}}-1}{3\sqrt{3}}, \quad b = \sqrt{\frac{1-a^2}{2}}, \quad c = \frac{1}{\sqrt{3}}, \quad w=e^{2\pi i/3}. \] Source: [JKM19]
- Conjecture: The configuration of \(85\) vectors in \(\mathbb{C}^5\) listed numerically in the leader board and explicitly constructed as the union of the root vectors corresponding to the \(45\) \(2\)-reflections which generate the unitary reflection group \(W(K_5)\) and \(40\) vectors representing each antipodal pair of minimal vectors of the Coxeter-Todd lattice \(O_{10}\) is a Grassmannian frame.
Source: [BGM+19] - Open Problem: Generalize the Levenstein and Bukh-Cox bounds to general subspace packings.
Source: [JKM19]
Code
Matlab code used to generate the packings above. We also encourage submission of code in different languages.
- GrassPack.m: Code to numerically approximate optimal line packings. Modification of the code from [MeDa14b], which is the implementation of [MeDa14a].
- troppAltProj.m: Code to numerically approximate optimal line packings. Implementation of the algorithm in [TDHS05].
- saveF.m Code to save a packing as both a Matlab and text file with the desired filename format. The data is written to a text file in a single column, first of the real components of each vector then the imaginary.
- textToMatlab.m: Convert a text file, formatted as a long column of first the real components of each vector and then the imaginary parts, to a Matlab file.
Papers
Review Paper
[JKM19] John Jasper, Emily J. King, and Dustin G. Mixon: “Game of Sloanes: Best known packings in complex projective space.” To appear: Wavelets and Sparsity XVIII, SPIE Proceedings (2019) [arXiv]
Further Literature and Websites
[BGM+19] Dmitriy Bilyk, Alexey Glazyrin, Ryan Matzke, Josiah Park, and Oleksandr Vlasiuk: “Optimal measures for \(p\)-frame energies on spheres.” (2019) [arXiv]
[CID+21] Diego Cuevas, Carlos Beltrán, Ignacio Santamaria, Vít Tuček, and Gunnar Peters: “A Fast Algorithm for Designing Grassmannian Constellations.” (2021) https://gtas.unican.es/files/pub/non_coherent_wsa21_full_paper.pdf, Conference: WSA 2021 - 25th International ITG Workshop on Smart Antennas
[FM16] Matt Fickus and Dustin G. Mixon: “Tables of the existence of equiangular tight frames.” (2016) [arXiv]
[Flamm] Steve Flammia: “Exact SIC fiducial vectors.” http://www.physics.usyd.edu.au/~sflammia/SIC/
[FSDH] Christopher Fuchs, Blake Stacey, John DeBrota, and Michael Hoang: “QBism: Quantum Theory as a Hero's Handbook: SIC-POVM Solutions.” http://www.physics.umb.edu/Research/QBism/solutions.html
[Grassl] Markus Grassl and Andrew J. Scott: “SIC-POVMs” http://sicpovm.markus-grassl.de/
[KlRo04] Andreas Klappenecker and Martin Rötteler: “Constructions of mutually unbiased bases.” (2004) in Finite fields and applications, Lecture Notes in Comput. Sci. 2948, 137–144, Springer, Berlin. [arXiv]
[MeDa14a] Ahmed Medra and Timothy N. Davidson: “Flexible codebook design for limited feedback systems via sequential smooth optimization on the Grassmannian manifold.” IEEE Trans. Signal Process. 62(5), 1305–1318 (2014)
[MeDa14b] Ahmed Medra and Timothy N. Davidson: “Flexible codebook design for limited feedback systems.” http://www.ece.mcmaster.ca/~davidson/pubs/Flexible_codebook_design.html
[Sloane1] Neil J. A. Sloane: “Spherical codes.” http://neilsloane.com/packings/
[Sloane2] Neil J. A. Sloane: “How to pack lines, planes, \(3\)-spaces, etc.” http://neilsloane.com/grass/
[TDHS05] Joel A. Tropp, Inderjit S. Dhillon, Robert W. Heath, Jr., and Thomas Strohmer: “Designing structured tight frames via alternating projection.” IEEE Trans. Info. Theory 51(1), 188–209 (2005)
[CID+21] Diego Cuevas, Carlos Beltrán, Ignacio Santamaria, Vít Tuček, and Gunnar Peters: “A Fast Algorithm for Designing Grassmannian Constellations.” (2021) https://gtas.unican.es/files/pub/non_coherent_wsa21_full_paper.pdf, Conference: WSA 2021 - 25th International ITG Workshop on Smart Antennas
[FM16] Matt Fickus and Dustin G. Mixon: “Tables of the existence of equiangular tight frames.” (2016) [arXiv]
[Flamm] Steve Flammia: “Exact SIC fiducial vectors.” http://www.physics.usyd.edu.au/~sflammia/SIC/
[FSDH] Christopher Fuchs, Blake Stacey, John DeBrota, and Michael Hoang: “QBism: Quantum Theory as a Hero's Handbook: SIC-POVM Solutions.” http://www.physics.umb.edu/Research/QBism/solutions.html
[Grassl] Markus Grassl and Andrew J. Scott: “SIC-POVMs” http://sicpovm.markus-grassl.de/
[KlRo04] Andreas Klappenecker and Martin Rötteler: “Constructions of mutually unbiased bases.” (2004) in Finite fields and applications, Lecture Notes in Comput. Sci. 2948, 137–144, Springer, Berlin. [arXiv]
[MeDa14a] Ahmed Medra and Timothy N. Davidson: “Flexible codebook design for limited feedback systems via sequential smooth optimization on the Grassmannian manifold.” IEEE Trans. Signal Process. 62(5), 1305–1318 (2014)
[MeDa14b] Ahmed Medra and Timothy N. Davidson: “Flexible codebook design for limited feedback systems.” http://www.ece.mcmaster.ca/~davidson/pubs/Flexible_codebook_design.html
[Sloane1] Neil J. A. Sloane: “Spherical codes.” http://neilsloane.com/packings/
[Sloane2] Neil J. A. Sloane: “How to pack lines, planes, \(3\)-spaces, etc.” http://neilsloane.com/grass/
[TDHS05] Joel A. Tropp, Inderjit S. Dhillon, Robert W. Heath, Jr., and Thomas Strohmer: “Designing structured tight frames via alternating projection.” IEEE Trans. Info. Theory 51(1), 188–209 (2005)