Packings in Real Projective Spaces

Matthew Fickus, John Jasper, Dustin G. Mixon

TL;DR

This paper introduces new algebraic and differential geometry techniques to solve the problem of packing points in real projective spaces. The authors provide a computer-assisted proof of optimality for a specific packing, develop an efficient algorithm for a range of packing problems, and offer new methods for certifying the optimality of packings.

What Problem Does This Paper Address?

The paper tackles the problem of "packing" points in real projective spaces. Imagine you have a space, and you want to place as many points as possible in it such that the minimum distance between any two points is maximized. This is a fundamental problem with applications ranging from error correction in digital communication to quantum state tomography. Specifically, the authors focus on finding "optimal packings," which are configurations of points where the minimum distance is as large as possible. They aim to develop new theoretical tools and computational methods to find and prove the optimality of these packings, especially in cases where traditional methods fall short.

Methods

The paper employs a blend of algebraic and differential geometry. Key techniques include:

  • Computer-assisted proofs: For specific cases, they use computational tools (like cylindrical algebraic decomposition) to prove optimality.
  • Algebraic geometry: They leverage polynomial equalities and inequalities to characterize packings and their properties, reducing packing problems to quantifier elimination problems.
  • Differential geometry: Concepts like tangent spaces and geodesics are used to analyze local optimality on manifolds.
  • Combinatorial design theory: Connections to strongly regular graphs and other combinatorial structures are exploited to construct and analyze packings.
  • Linear programming: Delsarte's linear programming bound is used as a tool to establish lower bounds on packing coherence.
  • "C-to-R trick" and Naimark complements: These operations are used to convert complex-valued packings into real-valued ones and to construct new packings from existing ones.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and proofs rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Bridging Geometry and Algebra: The paper demonstrates how tools from algebraic and differential geometry can be powerful for solving geometric packing problems, opening up new avenues for research.
  • Beyond the Welch Bound: While the Welch bound is a standard tool, the authors show that optimal packings often don't achieve it, necessitating the development of new bounds and proof techniques.
  • The Power of Computer Assistance: For certain challenging cases, computer-assisted proofs are essential for establishing optimality, highlighting the synergy between theoretical insights and computational power.
  • Local Optimality as a Stepping Stone: The paper introduces a method to certify "locally optimal" packings, which can serve as a starting point for finding globally optimal solutions or for constructing near-optimal packings.
  • Connections to Combinatorics: The deep connections between optimal packings and combinatorial structures like strongly regular graphs are further explored and utilized.

Key Results

  • Computer-assisted proof of optimality: The paper provides a proof of optimality for a specific 6-packing in RP³.
  • Approximation algorithm: An algorithm is presented that constructs packings with coherence within a constant factor of the optimal for a specific range of parameters (the "Gerzon range").
  • Local optimality certificates: The authors develop a method to certify local optimality for infinite families of packings.
  • New infinite families of packings: Several new infinite families of near-optimal packings are introduced, inspired by combinatorial designs.
  • Perfected packings: Versions of existing "putatively optimal" packings from Sloane's database are presented with improved properties.

Limitations and Future Work

  • Computational Complexity: While cylindrical algebraic decomposition (CAD) is a powerful tool, its runtime can be prohibitive for larger problems, motivating the search for more efficient techniques.
  • Existence of ETFs: The paper notes that equiangular tight frames (ETFs), a special class of optimal packings, only exist for specific parameter pairs (d, n), leaving many cases open.
  • Generalizing Proofs: The methods developed for specific cases (like the d=4 case) are suggested to be generalizable, but may require significant computational resources or further theoretical advancements.
  • Optimizing Constants: The paper mentions that the constant factor in their approximation algorithm (around 49) could likely be improved, suggesting this as a potential area for future student projects.
  • Exploring New Combinatorial Structures: The paper hints at the potential for discovering new packings by exploring novel combinatorial designs and incidence structures.

Summary updated

Abstract

This paper applies techniques from algebraic and differential geometry to determine how to best pack points in real projective spaces. We present a computer-assisted proof of the optimality of a particular 6-packing in $\mathbb{R}\mathbf{P}^3$, we introduce a linear-time constant-factor approximation algorithm for packing in the so-called Gerzon range, and we provide local optimality certificates for two infinite families of packings. Finally, we present perfected versions of various putatively optimal packings from Sloane's online database, along with a handful of infinite families they suggest, and we prove that these packings enjoy a certain weak notion of optimality.
BibTeX
@article{fickus2018packings,
  author = {Matthew Fickus and John Jasper and Dustin G. Mixon},
  title = {{Packings in Real Projective Spaces}},
  journal = {SIAM J. Appl. Algebra Geom.},
  year = {2018},
  url = {https://openreview.net/forum?id=oqnUmmNfW_f},
}
Figure