Spectral Bounds and SDP Hierarchies for Geometric Packing Problems

on YouTube ↗53m

" summary

Uses a unified sum-of-squares SDP hierarchy to get provable upper bounds for geometric packings by recasting independent sets on Cayley graphs as optimization over positive-type functions on the Euclidean motion group, then expressing those via irreducible unitary representations and Fourier transforms. Applied numerically to pentagon packings: best known construction fills ~0.92 of the plane and the SDP method proves an upper bound of ≈0.98. Implementation truncates infinite operators, uses Laguerre polynomial bases, solves large SDP with SDP-GMP, then rationally rounds and verifies feasibility rigorously.

AI-written summary · about

" chapters (16)

1. 0:00Introduction to packing
2. 1:07Cayley graphs definition
3. 2:20Independent sets and codes
4. 3:55Compact and motion groups
5. 6:18Hilbert's 18th problem
6. 7:23SOS proof systems
7. 10:25Current state of research
8. 13:06Pentagons and tetrahedra
9. 17:15SOS hierarchy mechanics
10. 20:36Generalizing to infinite
11. 25:39Duality and convergence
12. 28:39Summary of bound types
13. 31:37Positive type functions
14. 34:23Fourier analysis on groups
15. 37:30Euclidean group case study
16. 41:22Computations and conclusion