A Riemannian Variational and Spectral Framework for High-Dimensional Sphere Packing: Barrier–Dynamics Reconciliation, Periodic Rigidity, and Discrete-Time Guarantees
Faruk Alpay, Hamdi Alakkad · 2025
Read A Riemannian Variational and Spectral Framework for High-Dimensional Sphere Packing: Barrier–Dynamics Reconciliation, Periodic Rigidity, and Discrete-Time Guarantees by Faruk Alpay, Hamdi Alakkad (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-21066.txt.
Introduction
Packing equal spheres as densely as possible is an old problem with modern uses in materials and coding. Faruk Alpay and Hamdi Alakkad build a unified variational framework for periodic sphere packings in a 2025 mathematics paper. Their approach works on a Riemannian landscape with barrier functions keeping spheres apart.
The authors construct a smooth interior barrier compatible with a strict feasibility safeguard and a Lipschitz gradient. They correct and formalize a discrete-time update, with explicit step-size and damping rules. Proofs connect the barrier problem to the optimality conditions of the original packing problem. They further show that strict prestress stability implies the packing's contact framework is rigid. A Lyapunov argument gives energy descent, turning the geometry into a dynamics with guarantees.
Catalog record
| CREATOR | Faruk Alpay, Hamdi Alakkad |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 22 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-21066
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Riemannian Variational and Spectral Framework for High-Dimensional Sphere Packing: Barrier–Dynamics Reconciliation, Periodic Rigidity, and Discrete-Time Guarantees Faruk Alpay, Hamdi Alakkad Abstract We reconcile a barrier-based geometric model of sphere packings with a provably convergent discrete-time dynamics and provide full technical development of key theorems. Specifically, we (i) introduce a C 2 C^{2} interior barrier potential U ν U_{\nu} that is compatible with a strict-feasibility safeguard and has Lipschitz gradient on the iterates’ domain; (ii) correct and formalize the discrete update previously denoted as Eq. (12); (iii) prove barrier-to-KKT consistency and state (and prove) a corollary explaining the role of the quadratic term in U ν U_{\nu} (Section 4 ); (iv) prove that strict prestress stability implies periodic infinitesimal rigidity (Section 5 ); (v) establish discrete-time Lyapunov descent and projected descent (with feasibility projection integrated into the proof) and local linear convergence for the Spectral-Projected Interior Trajectory method ( Spit ) under explicit, non-circular step-size/damping rules (Section 6 ); (vi) clarify B B -updates and give an ℰ \mathcal{E} -nonexpansive joint solver (Sec. 6.1 – 6.1 ); and (vii) include minimal schematic illustrations and a reproducibility stub (Sec. 7 ). We emphasize theoretical rigor and mathematical proofs; empirical evaluation is deferred. Acronyms. KKT = Karush–Kuhn–Tucker optimality; LICQ = Linear Independence Constraint Qualification; SOSC = Second-Order Sufficiency Condition; HVP = Hessian–Vector Product; QP = Quadratic Program; Spit = Spectral-Projected Interior Trajectory method. 1 Introduction The sphere packing problem seeks the maximal volume fraction covered by congruent unit balls in \mathbb{R}^{n} . It is resolved in n=2,3 (hexagonal, Kepler [ 1 , 2 ] ) and in n=8,24 via modular forms [ 3 , 4 ] . Foundational bounds arise from linear and semidefinite programming [ 5 , 6 , 7 , 8 ] and classical lattice methods [ 9 , 10 , 11 , 12 ] . Spectral and rigidity themes are central in jamming and contact networks [ 15 , 14 ] . We give a self-contained treatment of interior barriers, KKT optimality, periodic rigidity, spectral stability, and discrete-time algorithmics with explicit assumptions and proofs. 2 Configuration, Constraints, and C^{2} Interior Barrier Let \Lambda be a full-rank lattice with basis B\in\mathbb{R}^{n\times n} and volume V(\Lambda)=|\det B| . Let x=(x_{1},\dots,x_{N})\in(\mathbb{R}^{n})^{N} be sphere centers modulo \Lambda . For i<j and t\in\Lambda , define the slack s_{ij,t}(x,B):=\|x_{i}-x_{j}-t\|^{2}-4\qquad(\text{feasible iff }s_{ij,t}\geq 0). (1) We minimize V(B) subject to s_{ij,t}\geq 0 . Standing assumptions and gauge (global, non-circular) (A1) Gauge fixing. We work modulo translations/rotations by fixing \sum_{i=1}^{N}x_{i}=0 and treating rigidity modulo the space \mathsf{T}=\{(u,A):u_{i}=c+\Omega x_{i},\ A=\Omega,\ \Omega^{\top}=-\Omega,\ c\in\mathbb{R}^{n}\} . (A2) Finite shift set. There exists R<\infty and a finite symmetric set \mathcal{S}\subset\Lambda such that if a pair contributes to U_{\nu} , then \|x_{i}-x_{j}-t\|\leq R with t\in\mathcal{S} on the safeguarded domain. (A3) Cell nondegeneracy. There are constants 0<\underline{\sigma}\leq\overline{\sigma}<\infty with \underline{\sigma}\,\mathrm{Id}\preceq B^{\top}B\preceq\overline{\sigma}\,\mathrm{Id} on the feasible set. (A4) Strict interior initialization. The initial (x^{0},B^{0}) satisfies s_{ij,t}(x^{0},B^{0})\geq\delta for some \delta\in(0,1) , and we maintain this by projection (Assumption 6.1 ). (A5) Existence for barrier subproblems. Under (A2)–(A4) the feasible set modulo gauge is compact; hence for each \nu>0 , the log-barrier \Phi_{\nu} in ( 4 ) has a minimizer. (A6) Regularity at the limit. At any limit point (x^{\star},B^{\star}) of \Phi_{\nu_{k}} -minimizers with \nu_{k}\downarrow 0 , LICQ holds for the active set \mathcal{A} ; if invoked, SOSC holds on the feasible manifold. (A7) Connectivity (spectral). When spectral quantities are used, the contact graph is connected. 2.1 Interior barrier compatible with dynamics Fix parameters \nu>0 (barrier strength) and \delta\in(0,1) (safety margin). Define a C^{2} interior barrier on the strict-feasibility slab \{s_{ij,t}\geq\delta\} : U_{\nu}(x,B):=\sum_{i<j}\sum_{t\in\mathcal{S}}\phi_{\nu}\bigl(s_{ij,t}(x,B)\bigr),\qquad\phi_{\nu}(s):=-\nu\log s+\frac{\nu}{2\delta}\,(s-\delta)^{2}\quad(s>0). (2) The term -\nu\log s enforces strict feasibility; the quadratic term makes U_{\nu}\in C^{2} and strongly convex near s=\delta . Lemma 2.1 (Lipschitz gradient on a safeguarded domain) . Fix \nu,\delta and assume s_{ij,t}\in[\delta,S] for all (i,j,t) included in U_{\nu} , and \|x_{i}-x_{j}-t\|\leq R uniformly on the iterates’ domain. Then there is L_{\text{lip}}=L_{\text{lip}}(\nu,\delta,S,R) such that \|\nabla U_{\nu}(\xi)-\nabla U_{\nu}(\zeta)\|\leq L_{\text{lip}}\|\xi-\zeta\| on this domain. Proof. Deferred to Appendix A.1 . ∎ 3 Spectral Stability on Contact Graphs Let G=(V,E) be the periodic contact graph (one vertex per sphere; one edge per active contact). Let \mathsf{A} be its adjacency matrix, D the degree matrix, and denote the (combinatorial) Laplacian by \mathcal{L}\ :=\ D-\mathsf{A}. (We reserve \mathcal{L} for the graph Laplacian; the symbol L_{\text{lip}} denotes a Lipschitz constant elsewhere.) Lemma 3.1 (Graph Poincaré inequality) . For any u\in\mathbb{R}^{N} with \sum_{i}u_{i}=0 , \sum_{i}u_{i}^{2}\ \leq\ \frac{1}{\lambda_{2}(G)}\sum_{(i,j)\in E}(u_{i}-u_{j})^{2}. (3) Proof. Expand u in the orthonormal eigenbasis of \mathcal{L} and use the Rayleigh quotient [ 16 ] . ∎ Theorem 3.2 (Cheeger-type bounds) . Let h(G)=\min_{S\subset V,0<|S|\leq|V|/2}\frac{|\partial S|}{|S|} and \Delta_{\max} be the max degree. Then \frac{h(G)^{2}}{2\Delta_{\max}}\leq\lambda_{2}(G)\leq 2h(G) [ 17 , 18 , 19 ] . 4 Barrier Consistency and Interior Variant Consider the log-barrier family on the strict interior: \Phi_{\nu}(x,B)=V(B)-\nu\sum_{i<j}\sum_{t\in\mathcal{S}}\log s_{ij,t}(x,B). (4) Theorem 4.1 (Log-barrier \Rightarrow KKT) . Suppose \nu_{k}\downarrow 0 and minimizers (x_{\nu_{k}},B_{\nu_{k}})\to(x^{\star},B^{\star}) exist, and LICQ holds for the active set \mathcal{A} at (x^{\star},B^{\star}) . Then (x^{\star},B^{\star}) satisfies the KKT conditions for \min V(B) s.t. s_{ij,t}\geq 0 . Proof. Deferred to Appendix A.2 . ∎ Corollary 4.2 (Interior U_{\nu} has the same KKT limit) . Let \widetilde{\Phi}_{\nu}(x,B):=V(B)+U_{\nu}(x,B) , and let (x_{\nu},B_{\nu}) be a minimizer of \widetilde{\Phi}_{\nu} . Under (A2)–(A6), any accumulation point (x^{\star},B^{\star}) of \{(x_{\nu},B_{\nu})\} as \nu\downarrow 0 satisfies the KKT conditions of the original problem. In particular, with \mu^{(\nu)}_{ij,t}\ :=\ -\phi_{\nu}^{\prime}\!\bigl(s_{ij,t}(x_{\nu},B_{\nu})\bigr)\ =\ \frac{\nu}{s_{ij,t}(x_{\nu},B_{\nu})}\ -\ \nu\,\frac{s_{ij,t}(x_{\nu},B_{\nu})-\delta}{\delta}, the sequence \mu^{(\nu)}\rightharpoonup\mu\geq 0 (after extraction), and the limiting multipliers satisfy KKT. Proof. Set s_{i}=s_{ij,t}(x_{\nu},B_{\nu}) to simplify notation and write \phi^{\prime}=\phi_{\nu}^{\prime} . First-order optimality for \widetilde{\Phi}_{\nu} reads \nabla_{B}V(B_{\nu})\ +\ \sum_{i}\phi^{\prime}(s_{i})\,\nabla_{B}s_{i}\ =\ 0,\qquad\sum_{i}\phi^{\prime}(s_{i})\,\nabla_{x}s_{i}\ =\ 0. Define \mu_{i}^{(\nu)}:=-\phi^{\prime}(s_{i})=\nu/s_{i}-\nu(s_{i}-\delta)/\delta . Then the above is equivalent to \nabla_{B}V(B_{\nu})\ -\ \sum_{i}\mu_{i}^{(\nu)}\,\nabla_{B}s_{i}\ =\ 0,\qquad\sum_{i}\mu_{i}^{(\nu)}\,\nabla_{x}s_{i}\ =\ 0. Partition indices into active-at-the-limit \mathcal{A} and inactive-at-the-limit \mathcal{I} : by continuity, there exists \sigma>0 such that s_{i}\geq\sigma for i\in\mathcal{I} and \nu small enough, hence \mu_{i}^{(\nu)}\to 0 for i\in\mathcal{I} . For i\in\mathcal{A} , boundedness of \{\mu^{(\nu)}\} follows from LICQ: introduce \mathsf{J}(x,B):=\bigl[\,\{\nabla_{x}s_{i}(x,B)\}_{i\in\mathcal{A}}\ \ \ \ \{\nabla_{B}s_{i}(x,B)\}_{i\in\mathcal{A}}\,\bigr]. LICQ implies \sigma_{\min}(\mathsf{J}(x^{\star},B^{\star}))>0 , hence in a neighborhood \|\sum_{i\in\mathcal{A}}\mu_{i}^{(\nu)}[\nabla_{x}s_{i};\nabla_{B}s_{i}]\|\geq\underline{\sigma}\,\|\mu_{\mathcal{A}}^{(\nu)}\| . Taking norms and using boundedness of \nabla V,\nabla s_{i} yields \|\mu_{\mathcal{A}}^{(\nu)}\|\leq C for some C independent of \nu . Extract a convergent subsequence \mu^{(\nu)}\to\mu\geq 0 ; pass to the limit to obtain KKT stationarity and complementarity (inactive \Rightarrow \mu_{i}=0 , active \Rightarrow s_{i}\to 0 ). ∎ 5 Periodic Rigidity Notation and trivial motions (disambiguation). On the active set \mathcal{A} , write r_{ij,t}=x_{i}-x_{j}-t and n_{ij,t}=r_{ij,t}/\|r_{ij,t}\| . We define A\ :=\ \dot{B}\,B^{-1}\quad\text{(cell velocity/strain rate; dimensionless)}. A periodic infinitesimal motion is a pair (u,A) with u=(u_{1},\dots,u_{N})\in(\mathbb{R}^{n})^{N} and A\in\mathbb{R}^{n\times n} satisfying r_{ij,t}^{\top}\bigl(u_{i}-u_{j}-A\,r_{ij,t}\bigr)=0\qquad\forall(i,j,t)\in\mathcal{A}. (5) Trivial (Euclidean) motions form the subspace \mathsf{T}\ :=\ \bigl\{\,(u,A):\ u_{i}=c+\Omega x_{i},\ A=\Omega,\ \Omega^{\top}=-\Omega,\ c\in\mathbb{R}^{n}\,\bigr\}. Definition 5.1 (Prestress and stress energy) . An equilibrium stress is a set \omega=\{\omega_{ij,t}\}_{\mathcal{A}} with \omega_{ij,t}=\omega_{ji,-t} . Its quadratic form on motions is Q_{\omega}(u,A)\ :=\ \sum_{(i,j,t)\in\mathcal{A}}\omega_{ij,t}\,\bigl(n_{ij,t}^{\top}(u_{i}-u_{j}-A\,r_{ij,t})\bigr)^{2}. (6) We say the framework is strictly prestress stable if there exists an equilibrium stress \omega with Q_{\omega} positive definite on the subspace \{(u,A):\eqref{eq:inf}\text{ holds}\}/\mathsf{T} . Theorem 5.2 (Prestress stability \Rightarrow periodic rigidity) . If the framework is strictly prestress stable, then it is periodically infinitesimally rigid; i.e., any (u,A) satisfying ( 5 ) is trivial modulo \mathsf{T} . Proof. By strict prestress stability, Q_{\omega} is positive definite on the nontrivial motion subspace; hence