Lattices, sphere packings and spherical codes: geometric optimization problems Abhinav Kumar MIT November 25, 2012 AbhinavKumar (MIT) Geometricoptimizationproblems November25,2012 1/46 Sphere packings Definition A sphere packing in Rn is a collection of spheres/balls of equal size which do not overlap (except for touching). The density of a sphere packing is the volume fraction of space occupied by the balls. The main question is to find a/the densest packing in Rn. AbhinavKumar (MIT) Geometricoptimizationproblems November25,2012 2/46 Good sphere packings In dimension 1, we can achieve density 1 by laying intervals end to end. In dimension 2, the best possible is by using the hexagonal lattice. [Fejes To´th, 1940] ∼ ✎☞✎☞✎✎☞☞✎☞ ✍✎✌✍☞✎✌✍✎☞✍✌☞✎✌✍☞✌ ✎✍☞✎✌✍☞✎✌✍✎☞✌✍☞✎✌☞ ✍✎✌✍☞✎✌✍✎☞✍✌☞✎✌✍☞✌ ✎✍☞✎✌✍☞✎✌✍✎☞✌✍☞✎✌☞ ✍✌✍✌✍✍✌✌✍✌ AbhinavKumar (MIT) Geometricoptimizationproblems November25,2012 3/46 Good sphere packings In dimension 1, we can achieve density 1 by laying intervals end to end. In dimension 2, the best possible is by using the hexagonal lattice. [Fejes To´th, 1940] ∼ ✎☞✎☞✎✎☞☞✎☞ ✍✎✌✍☞✎✌✍✎☞✍✌☞✎✌✍☞✌ ✎✍☞✎✌✍☞✎✌✍✎☞✌✍☞✎✌☞ ✍✎✌✍☞✎✌✍✎☞✍✌☞✎✌✍☞✌ ✎✍☞✎✌✍☞✎✌✍✎☞✌✍☞✎✌☞ ✍✌✍✌✍✍✌✌✍✌ AbhinavKumar (MIT) Geometricoptimizationproblems November25,2012 3/46 Good sphere packings II In dimension 3, the best possible way is to stack layers of the solution in 2 dimensions. [Hales, 1998] ∼ ✎☞✎☞✎✎☞☞✎☞ ✍✎✌✍☞✎✌✍✎☞✍✌☞✎✌✍☞✌ ✎☞✎✎☞☞✎☞ ✎✍☞✎♠✌✍☞✎♠✌✍✎☞♠✌✍☞✎♠✌☞ ✍✍✎✌✎✍✌☞✍✎♠☞✌✎✍✌✍✎☞♠✎☞✍✌✌✍☞✎♠☞✎✌✍✌☞♠☞✌ ✎✍☞✍✎✌✍✌☞✍✎✌✍✍✌✎☞✌✍✌✍☞✎✌✌☞ ✍✌✍✌✍✍✌✌✍✌ There are infinitely (in fact, uncountably) many ways of doing this, the Barlow packings. In dimensions 4, we have some guesses for the densest sphere packing. ≥ But we can’t prove them. In low dimensions, the best known sphere packings come from lattices. AbhinavKumar (MIT) Geometricoptimizationproblems November25,2012 4/46 Good sphere packings II In dimension 3, the best possible way is to stack layers of the solution in 2 dimensions. [Hales, 1998] ∼ ✎☞✎☞✎✎☞☞✎☞ ✍✎✌✍☞✎✌✍✎☞✍✌☞✎✌✍☞✌ ✎☞✎✎☞☞✎☞ ✎✍☞✎♠✌✍☞✎♠✌✍✎☞♠✌✍☞✎♠✌☞ ✍✍✎✌✎✍✌☞✍✎♠☞✌✎✍✌✍✎☞♠✎☞✍✌✌✍☞✎♠☞✎✌✍✌☞♠☞✌ ✎✍☞✍✎✌✍✌☞✍✎✌✍✍✌✎☞✌✍✌✍☞✎✌✌☞ ✍✌✍✌✍✍✌✌✍✌ There are infinitely (in fact, uncountably) many ways of doing this, the Barlow packings. In dimensions 4, we have some guesses for the densest sphere packing. ≥ But we can’t prove them. In low dimensions, the best known sphere packings come from lattices. AbhinavKumar (MIT) Geometricoptimizationproblems November25,2012 4/46 Lattices Definition A lattice Λ in Rn is a discrete subgroup of rank n, i.e. generated by n linearly independent vectors of Rn. Example Zn Rn ⊂ Root lattices A ,D ,E . n n n Lattices are related to quadratic forms: if b ,...,b is a basis of the 1 n lattice Λ Rn, then Q(x ,...,x ) = x b + +x b 2 is a positive 1 n 1 1 n n ⊂ || ··· || definite quadratic form. Lattices up to isometry Quadratic forms mod change of coords { } ↔ { } On(R) GLn(R)/GLn(Z) ∼= Sym2(Rn)+/SLn(Z). \ AbhinavKumar (MIT) Geometricoptimizationproblems November25,2012 5/46 Lattices Definition A lattice Λ in Rn is a discrete subgroup of rank n, i.e. generated by n linearly independent vectors of Rn. Example Zn Rn ⊂ Root lattices A ,D ,E . n n n Lattices are related to quadratic forms: if b ,...,b is a basis of the 1 n lattice Λ Rn, then Q(x ,...,x ) = x b + +x b 2 is a positive 1 n 1 1 n n ⊂ || ··· || definite quadratic form. Lattices up to isometry Quadratic forms mod change of coords { } ↔ { } On(R) GLn(R)/GLn(Z) ∼= Sym2(Rn)+/SLn(Z). \ AbhinavKumar (MIT) Geometricoptimizationproblems November25,2012 5/46 Lattices Definition A lattice Λ in Rn is a discrete subgroup of rank n, i.e. generated by n linearly independent vectors of Rn. Example Zn Rn ⊂ Root lattices A ,D ,E . n n n Lattices are related to quadratic forms: if b ,...,b is a basis of the 1 n lattice Λ Rn, then Q(x ,...,x ) = x b + +x b 2 is a positive 1 n 1 1 n n ⊂ || ··· || definite quadratic form. Lattices up to isometry Quadratic forms mod change of coords { } ↔ { } On(R) GLn(R)/GLn(Z) ∼= Sym2(Rn)+/SLn(Z). \ AbhinavKumar (MIT) Geometricoptimizationproblems November25,2012 5/46 Lattices Definition A lattice Λ in Rn is a discrete subgroup of rank n, i.e. generated by n linearly independent vectors of Rn. Example Zn Rn ⊂ Root lattices A ,D ,E . n n n Lattices are related to quadratic forms: if b ,...,b is a basis of the 1 n lattice Λ Rn, then Q(x ,...,x ) = x b + +x b 2 is a positive 1 n 1 1 n n ⊂ || ··· || definite quadratic form. Lattices up to isometry Quadratic forms mod change of coords { } ↔ { } On(R) GLn(R)/GLn(Z) ∼= Sym2(Rn)+/SLn(Z). \ AbhinavKumar (MIT) Geometricoptimizationproblems November25,2012 5/46