Spectral bounds in extremal discrete geometry

离散几何中的极值/最优结构是数学、物理、（量子）信息理论和材料科学许多领域的基础。著名的例子是最密集的球体填料，最密集的四面体填料，以及欧几里得平面的色数。四面体的最佳填充问题可以追溯到古希腊，球体填充问题最早是由开普勒提出的，而确定平面的色数被称为哈德维格-纳尔逊问题。尽管这些问题有着悠久的历史，但只有很少的数学工具可以解决它们。研究离散几何中的极值结构，我们面临着两个基本问题：构造：如何构造推测最优的结构？障碍：如何证明给定的结构确实是最优的？对于建筑问题，数学和工程研究者发现了许多启发式方法，这些方法在实践中往往很有效。本提案的主要目标是开发和验证（计算）障碍工具。对于球形填料的特殊情况，PI开发了来自无限维半定优化和谐波分析的工具，以及来自实际代数几何和多项式优化的计算技术。得到的结果往往是最著名的，例如球体填充问题，亲吻数问题或欧几里德空间的可测量色数。这个提议的目的是超越球体填充到更复杂的几何形状（如四面体）的填充，超越欧几里得空间的可测量着色到更复杂的几何形状（如黎曼对称空间）的可测量着色。要实现这一点，必须改进当前的计算技术。具体来说，目标是1。扩展当前的方法，使其能够处理更复杂的几何图形；建立在更强大、计算成本更高的组合优化工具上。这将允许将数学优化应用于离散几何中更广泛的具有挑战性的优化问题。

Extremal / optimal structures in discrete geometry are fundamental to many areas in mathematics, physics, (quantum) information theory, and materials science. Famous examples are densest packings of spheres, densest packings of tetrahedra, and the chromatic number of the Euclidean plane. The problem of optimal packings of tetrahedra goes back to the ancient Greeks, the sphere packing problem was first mentioned by Kepler, and determining the chromatic number of the plane is known as the Hadwiger-Nelson problem. Despite the long history of these problems, there are only few mathematical tools available to tackle them.Studying extremal structures in discrete geometry, we are facing twobasic tasks:Constructions: How to construct structures which are conjecturally optimal?Obstructions: How to prove that a given structure is indeed optimal?For the constructions researchers in mathematics and engineering found many heuristics which often work well in practice. The main objective of this proposal is the development and the validation of (computational) tools for the obstructions. For the special case ofsphere packings the PI developed a blend of tools coming from infinite-dimensional semidefinite optimization and harmonic analysis,together with computational techniques coming from real algebraic geometry and polynomial optimization. The results obtained arefrequently the best-known, for example for the sphere packing problem, the kissing number problem or the measurable chromatic number of Euclidean space.The aim of this proposal is to go beyond sphere packings to packings of more complex geometric shapes (like tetrahedra) and to go beyond measurable colorings of Euclidean spaces to measurable colorings of more complex geometries (like Riemannian symmetric spaces).To achieve this one has to improve current computational techniques. In particular, the goal is to 1. extend the current methods so that they can deal with more complex geometries,2. build on stronger, computationally more expensive, tools from combinatorial optimization.This will allow to apply mathematical optimization to a much wider range of challenging optimization problems in discrete geometry.