Optimal simplices and codes in projective spaces

Cohn, Henry¹ ; Kumar, Abhinav² ; Minton, Gregory¹

¹ Microsoft Research, One Memorial Drive, Cambridge, MA 02142, United States
² Department of Mathematics, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA 02139, United States, Department of Mathematics, Stony Brook University, Stony Brook, NY 11794, United States

Geometry & topology, Tome 20 (2016) no. 3, pp. 1289-1357.

Résumé

We find many tight codes in compact spaces, in other words, optimal codes whose optimality follows from linear programming bounds. In particular, we show the existence (and abundance) of several hitherto unknown families of simplices in quaternionic projective spaces and the octonionic projective plane. The most noteworthy cases are $15$–point simplices in $ℍ‘{\mathbb{P}}^2$ and $27$–point simplices in $\mathbb{O}‘{\mathbb{P}}^2$, both of which are the largest simplices and the smallest $2$–designs possible in their respective spaces. These codes are all universally optimal, by a theorem of Cohn and Kumar. We also show the existence of several positive-dimensional families of simplices in the Grassmannians of subspaces of ${ℝ}^n$ with $n\le 8$; close numerical approximations to these families had been found by Conway, Hardin and Sloane, but no proof of existence was known. Our existence proofs are computer-assisted, and the main tool is a variant of the Newton–Kantorovich theorem. This effective implicit function theorem shows, in favorable conditions, that every approximate solution to a set of polynomial equations has a nearby exact solution. Finally, we also exhibit a few explicit codes, including a configuration of $39$ points in $\mathbb{O}‘{\mathbb{P}}^2$ that form a maximal system of mutually unbiased bases. This is the last tight code in $\mathbb{O}‘{\mathbb{P}}^2$ whose existence had been previously conjectured but not resolved.

Détail

DOI : 10.2140/gt.2016.20.1289

Classification : 51M16, 52C17, 65G20, 49M15
Keywords: code, design, regular simplex, linear programming bounds, projective space, Grassmannian

Bibliographie

[1] C An, X Chen, I H Sloan, R S Womersley, Well conditioned spherical designs for integration and interpolation on the two-sphere, SIAM J. Numer. Anal. 48 (2010) 2135

[2] E Anderson, Z Bai, C Bischof, L S Blackford, J Demmel, J Dongarra, J Du Croz, A Greenbaum, S Hammarling, A Mckenney, D Sorenson, LAPACK Users’ Guide, SIAM (1999)

[3] D M Appleby, I Bengtsson, S Brierley, Å Ericsson, M Grassl, J Å Larsson, Systems of imprimitivity for the Clifford group, Quantum Inf. Comput. 14 (2014) 339

[4] D M Appleby, C A Fuchs, H Zhu, Group theoretic, Lie algebraic and Jordan algebraic formulations of the SIC existence problem, Quantum Inf. Comput. 15 (2015) 61

[5] C Bachoc, Linear programming bounds for codes in Grassmannian spaces, IEEE Trans. Inform. Theory 52 (2006) 2111

[6] C Bachoc, Y Ben-Haim, S Litsyn, Bounds for codes in products of spaces, Grassmann, and Stiefel manifolds, IEEE Trans. Inform. Theory 54 (2008) 1024

[7] C Bachoc, R Coulangeon, G Nebe, Designs in Grassmannian spaces and lattices, J. Algebraic Combin. 16 (2002) 5

[8] C Bachoc, G Nebe, F M De Oliveira Filho, F Vallentin, Lower bounds for measurable chromatic numbers, Geom. Funct. Anal. 19 (2009) 645

[9] C Bachoc, F Vallentin, New upper bounds for kissing numbers from semidefinite programming, J. Amer. Math. Soc. 21 (2008) 909

[10] J C Baez, The octonions, Bull. Amer. Math. Soc. 39 (2002) 145

[11] E Bannai, S G Hoggar, On tight t–designs in compact symmetric spaces of rank one, Proc. Japan Acad. Ser. A Math. Sci. 61 (1985) 78

[12] E Bannai, S G Hoggar, Tight t–designs and squarefree integers, European J. Combin. 10 (1989) 113

[13] V Bargmann, Note on Wigner’s theorem on symmetry operations, J. Mathematical Phys. 5 (1964) 862

[14] M Berger, A panoramic view of Riemannian geometry, Springer (2003)

[15] A V Bondarenko, On a spherical code in the space of spherical harmonics, Ukrainian Math. J. 62 (2010) 993

[16] A Bondarenko, D Radchenko, M Viazovska, Optimal asymptotic bounds for spherical designs, Ann. of Math. (2) 178 (2013) 443

[17] M J Bowick, L Giomi, Two-dimensional matter: order, curvature and defects, Adv. Phys. 58 (2009) 449

[18] U Brehm, The shape invariant of triangles and trigonometry in two-point homogeneous spaces, Geom. Dedicata 33 (1990) 59

[19] U Brehm, B Et-Taoui, Congruence criteria for finite subsets of complex projective and complex hyperbolic spaces, Manuscripta Math. 96 (1998) 81

[20] U Brehm, B Et-Taoui, Congruence criteria for finite subsets of quaternionic elliptic and quaternionic hyperbolic spaces, Geom. Dedicata 84 (2001) 261

[21] U Brehm, W Kühnel, 15–vertex triangulations of an 8–manifold, Math. Ann. 294 (1992) 167

[22] A R Calderbank, R H Hardin, E M Rains, P W Shor, N J A Sloane, A group-theoretic framework for the construction of packings in Grassmannian spaces, J. Algebraic Combin. 9 (1999) 129

[23] X Chen, Numerical verification methods for spherical t–designs, Japan J. Indust. Appl. Math. 26 (2009) 317

[24] X Chen, A Frommer, B Lang, Computational existence proofs for spherical t–designs, Numer. Math. 117 (2011) 289

[25] X Chen, R S Womersley, Existence of solutions to systems of underdetermined equations and spherical designs, SIAM J. Numer. Anal. 44 (2006) 2326

[26] E A Coddington, N Levinson, Theory of ordinary differential equations, McGraw–Hill (1955)

[27] A M Cohen, Exceptional presentations of three generalized hexagons of order 2, J. Combin. Theory Ser. A 35 (1983) 79

[28] H Cohn, Order and disorder in energy minimization, from: "Proceedings of the International Congress of Mathematicians, IV" (editors R Bhatia, A Pal, G Rangarajan, V Srinivas, M Vanninathan), Hindustan Book Agency (2010) 2416

[29] H Cohn, A Kumar, Universally optimal distribution of points on spheres, J. Amer. Math. Soc. 20 (2007) 99

[30] H Cohn, Y Zhao, Energy-minimizing error-correcting codes, IEEE Trans. Inform. Theory 60 (2014) 7442

[31] J H Conway, R H Hardin, N J A Sloane, Packing lines, planes, etc : packings in Grassmannian spaces, Experiment. Math. 5 (1996) 139

[32] H S M Coxeter, Regular complex polytopes, Cambridge Univ. Press (1974)

[33] J Creignou, Constructions of Grassmannian simplices,

[34] P Delsarte, J M Goethals, J J Seidel, Spherical codes and designs, Geom. Dedicata 6 (1977) 363

[35] N D Elkies, B H Gross, The exceptional cone and the Leech lattice, Internat. Math. Res. Notices (1996) 665

[36] M Fickus, D G Mixon, J C Tremain, Steiner equiangular tight frames, Linear Algebra Appl. 436 (2012) 1014

[37] L Fousse, G Hanrot, V Lefèvre, P Pélissier, P Zimmermann, MPFR: a multiple-precision binary floating-point library with correct rounding, ACM Trans. Math. Software 33 (2007)

[38] É Fouvry, E Kowalski, P Michel, Counting sheaves using spherical codes, Math. Res. Lett. 20 (2013) 305

[39] H Hadwiger, Über ausgezeichnete Vektorsterne und reguläre Polytope, Comment. Math. Helv. 13 (1940) 90

[40] T Hangan, G Masala, A geometrical interpretation of the shape invariant for geodesic triangles in complex projective spaces, Geom. Dedicata 49 (1994) 129

[41] R H Hardin, N J A Sloane, McLaren’s improved snub cube and other new spherical designs in three dimensions, Discrete Comput. Geom. 15 (1996) 429

[42] J M Hendrickx, A Olshevsky, Matrix p–norms are NP-hard to approximate if p≠1,2,∞, SIAM J. Matrix Anal. Appl. 31 (2010) 2802

[43] S G Hoggar, t–designs in projective spaces, European J. Combin. 3 (1982) 233

[44] S G Hoggar, Parameters of t–designs in FPd−1, European J. Combin. 5 (1984) 29

[45] S G Hoggar, Tight t–designs and octonions, Mitt. Math. Sem. Giessen 165 (1984) 1

[46] W Hurewicz, H Wallman, Dimension theory, 4, Princeton Univ. Press (1941)

[47] G A Kabatjanskiĭ, V I Levenšteĭn, Bounds for packings on the sphere and in space, Problemy Peredači Informacii 14 (1978) 3

[48] W M Kantor, Quaternionic line-sets and quaternionic Kerdock codes, Linear Algebra Appl. 226/228 (1995) 749

[49] L V Kantorovich, On Newton’s method for functional equations, Doklady Akad. Nauk SSSR 59 (1948) 1237

[50] M Khatirinejad Fard, Regular structures of lines in complex spaces, PhD thesis, Simon Fraser University (2008)

[51] H König, Cubature formulas on spheres, from: "Advances in multivariate approximation" (editors W Haußmann, K Jetter, M Reimer), Math. Res. 107, Wiley-VCH (1999) 201

[52] S G Krantz, H R Parks, The implicit function theorem: history, theory, and applications, Birkhäuser (2003)

[53] R Krawczyk, Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing (Arch. Elektron. Rechnen) 4 (1969) 187

[54] P W H Lemmens, J J Seidel, Equiangular lines, J. Algebra 24 (1973) 494

[55] V I Levenshteĭn, Bounds on the maximal cardinality of a code with bounded modulus of the inner product, Dokl. Akad. Nauk SSSR 263 (1982) 1303

[56] V I Levenshteĭn, Designs as maximum codes in polynomial metric spaces, Acta Appl. Math. 29 (1992) 1

[57] J H Van Lint, J J Seidel, Equilateral point sets in elliptic geometry, Nederl. Akad. Wetensch. Proc. Ser. A 69 (1966) 335

[58] Y I Lyubich, On tight projective designs, Des. Codes Cryptogr. 51 (2009) 21

[59] D G Mixon, C J Quinn, N Kiyavash, M Fickus, Fingerprinting with equiangular tight frames, IEEE Trans. Inf. Theory 59 (2013) 1855

[60] N Mukunda, R Simon, Quantum kinematic approach to the geometric phase. I. General formalism, Ann. Physics 228 (1993) 205

[61] J W Neuberger, The continuous Newton’s method, inverse functions, and Nash–Moser, Amer. Math. Monthly 114 (2007) 432

[62] A Neumaier, Combinatorial configurations in terms of distances, Memorandum 81-09 (Wiskunde en Informatica) (1980)

[63] J M Ortega, The Newton–Kantorovich theorem, Amer. Math. Monthly 75 (1968) 658

[64] , PARI/GP version 2.6.0 (2013)

[65] J M Renes, Equiangular spherical codes in quantum cryptography, Quantum Inf. Comput. 5 (2005) 81

[66] J M Renes, Equiangular tight frames from Paley tournaments, Linear Algebra Appl. 426 (2007) 497

[67] J M Renes, R Blume-Kohout, A J Scott, C M Caves, Symmetric informationally complete quantum measurements, J. Math. Phys. 45 (2004) 2171

[68] N Revol, F Rouillier, Motivations for an arbitrary precision interval arithmetic and the MPFI library, Reliab. Comput. 11 (2005) 275

[69] A J Scott, M Grassl, Symmetric informationally complete positive-operator-valued measures: a new computer study, J. Math. Phys. 51 (2010)

[70] M A Sustik, J A Tropp, I S Dhillon, R W Heath Jr., On the existence of equiangular tight frames, Linear Algebra Appl. 426 (2007) 619

[71] R R Thomas, Lectures in geometric combinatorics, 33, Amer. Math. Soc. (2006)

[72] S Waldron, On the construction of equiangular frames from graphs, Linear Algebra Appl. 431 (2009) 2228

[73] L R Welch, Lower bounds on the maximum cross correlation of signals, IEEE Trans. Inf. Theory 20 (1974) 397

[74] W K Wootters, B D Fields, Optimal state-determination by mutually unbiased measurements, Ann. Physics 191 (1989) 363

[75] P Xia, S Zhou, G B Giannakis, Achieving the Welch bound with difference sets, IEEE Trans. Inf. Theory 51 (2005) 1900

[76] G Zauner, Quantum designs: foundations of a noncommutative design theory, Int. J. Quantum Inf. 9 (2011) 445