Transcription
DIMACS REU 2018Project: Sphere Packings and Number TheoryAlisa Cui, Devora Chait, Zachary StierMentor: Prof. Alex KontorovichJuly 13, 2018
Apollonian Circle PackingThis is an Apollonian circle packing:
Apollonian Circle PackingHere’s how we construct it:IStart with three mutuallytangent circles
Apollonian Circle PackingHere’s how we construct it:IStart with three mutuallytangent circles
Apollonian Circle PackingHere’s how we construct it:IStart with three mutuallytangent circlesIDraw two more circles, eachof which is tangent to theoriginal three
Apollonian Circle PackingIStart with three mutuallytangent circlesIDraw two more circles, eachof which is tangent to theoriginal three
Apollonian Circle PackingIStart with three mutuallytangent circlesIDraw two more circles, eachof which is tangent to theoriginal threeIContinue drawing tangentcircles, densely filling space
Apollonian Circle Packing
Apollonian Circle PackingThese two images actually represent the same circle packing!We can go from one realization to the other using circleinversions.
Circle InversionsCircle inversion sends points at a distance of rd from the center ofthe mirror circle to a distance of r /d from the center of the mirrorcircle.
Circle InversionsCircle inversion sends points at a distance of rd from the center ofthe mirror circle to a distance of r /d from the center of the mirrorcircle.
Circle InversionsCircle inversion sends points at a distance of rd from the center ofthe mirror circle to a distance of r /d from the center of the mirrorcircle.IWe apply circle inversions toboth spheres and planes,where planes are consideredspheres of infinite radius.ICircle inversions preservetangencies and angles.Source: Malin Christersson
Apollonian Circle Packing
Apollonian Circle PackingTo generate a packing, invert the blue line about the reds
Apollonian Circle PackingTo generate a packing, invert the blue line about the reds
Apollonian Circle PackingTo generate a packing, invert the blue line about the reds
Apollonian Circle PackingTo generate a packing, invert the blue line about the reds
Apollonian Circle PackingTo generate a packing, invert the blue line about the reds
Apollonian Circle PackingTo generate a packing, invert the blue line about the reds
Apollonian Circle PackingTo generate a packing, invert the blue line about the reds
Apollonian Circle PackingTo generate a packing, invert the blue line about the reds
Sphere Packings: DefinitionThe sphere packings we’ve examined this summer areconfigurations where the spheres:Ihave varying radiiIare oriented to have mutually disjoint interiorsIdensely fill up space
Hyperbolic GeometriesIThere is a surprising connection between sphere packings andnon-Euclidean geometries.
Hyperbolic GeometriesIThere is a surprising connection between sphere packings andnon-Euclidean geometries.IEuclidean geometry is characterized by Euclid’s parallelpostulate, which states that the angles formed by two linesintersecting on one side of a third line sum to be less than πradians.Source: Wikipedia
Hyperbolic GeometriesIThese geometries have several models which are each used asis necessary.IFor now, we are going to focus on the upper half-spacemodel of Hn 1 : consider Rn 1 , subject to x0 0. This spacehas its own metric, and has as its boundary Rn .
Hyperbolic GeometriesIThese geometries have several models which are each used asis necessary.IFor now, we are going to focus on the upper half-spacemodel of Hn 1 : consider Rn 1 , subject to x0 0. This spacehas its own metric, and has as its boundary Rn .IBecause of the different metric, planes in Hn 1 are actuallyhemispheres, with their circumferences lying in Rn (i.e., thesubset x0 0).IConveniently, we’ve already been looking at spheres lying inRn ! We can “continue our configurations upwards” in what isknown as the Poincaré extension.
Poincaré Extension
Hyperbolic GeometriesAnother useful model of hyperbolic space is the two-sheetedhyperboloid model.
Hyperbolic GeometriesAnother useful model of hyperbolic space is the two-sheetedhyperboloid model.Resting in R3Source: supermath.infoIA quadratic form Q is apolynomial where each termis of degree exactly 2. It canbe used to define an innerproduct space.IWe’re working on the topsheet of this 2-sheetedhyperboloid model ofhyperbolic space, where allvectors v satisfyhv , v iQ 1
Hyperbolic GeometriesAnother useful model of hyperbolic space is the two-sheetedhyperboloid model.IA quadratic form Q is apolynomial where each termis of degree exactly 2. It canbe used to define an innerproduct space.We’re working on the topsheet of this 2-sheetedhyperboloid model ofhyperbolic space, where allResting in R3vectors v satisfySource: supermath.infohv , v iQ 1Where did this quadratic form Q 1 come from?I
Hyperbolic GeometriesAnother useful model of hyperbolic space is the two-sheetedhyperboloid model.IA quadratic form Q is apolynomial where each termis of degree exactly 2. It canbe used to define an innerproduct space.We’re working on the topsheet of this 2-sheetedhyperboloid model ofhyperbolic space, where allResting in R3vectors v satisfySource: supermath.infohv , v iQ 1Where did this quadratic form Q 1 come from? Circleinversions!I
From Circle Inversions to Quadratic Forms
From Circle Inversions to Quadratic Forms
From Circle Inversions to Quadratic Forms
From Circle Inversions to Quadratic Forms
From Circle Inversions to Quadratic Forms
From Circle Inversions to Quadratic Forms
From Circle Inversions to Quadratic Formsdˆ dˆ rˆ 11 z r z r2r z 2 r 2r z 2 r 2r z 2 r 2 rˆ z 21 1 b̂b2rrˆrb̂b bz 2 1
Crystallographic Sphere PackingsIFirst introduced by Kontorovich & Nakamura in 2017
Crystallographic Sphere PackingsIIFirst introduced by Kontorovich & Nakamura in 2017A crystallographic sphere packing is generated by theaction of a geometrically finite reflection group
Crystallographic Sphere PackingsIIFirst introduced by Kontorovich & Nakamura in 2017A crystallographic sphere packing is generated by theaction of a geometrically finite reflection groupIGeometrically finite: generated by a finite number offundamental reflections
Crystallographic Sphere PackingsIIFirst introduced by Kontorovich & Nakamura in 2017A crystallographic sphere packing is generated by theaction of a geometrically finite reflection groupIIGeometrically finite: generated by a finite number offundamental reflectionsGroups that are geometrically finite have a finite fundamentalpolytope, or the region bounded by the planes associated withtheir fundamental reflections
Crystallographic Sphere PackingsIIFirst introduced by Kontorovich & Nakamura in 2017A crystallographic sphere packing is generated by theaction of a geometrically finite reflection groupIIIGeometrically finite: generated by a finite number offundamental reflectionsGroups that are geometrically finite have a finite fundamentalpolytope, or the region bounded by the planes associated withtheir fundamental reflectionsThe fundamental polytope encodes the same information as aCoxeter diagram
Coxeter DiagramA Coxeter diagram is a collection of nodes and edges thatrepresents a geometric relationship between n-dimensional spheresand hyperplanes. For two nodes i, j, the edge ei,j is defined by thefollowing:ei,j a dotted line,if i and j are disjoint a thick line,if i and j are tangent m 2 thin lines, if the angle between i and j is π/m no line,if i j
Computation of the Coxeter Diagram12534
Computation of the Coxeter Diagram12534
Computation of the Coxeter Diagram12534
Computation of the Coxeter Diagram12534
Computation of the Coxeter Diagram12534
Computation of the Coxeter Diagram12534
Computation of the Coxeter Diagram12534
Computation of the Coxeter Diagram12534
Computation of the Coxeter Diagram12534
Computation of the Coxeter Diagram12534
Computation of the Coxeter Diagram12534
Computation of the Coxeter Diagram12534
Cluster and CoclusterIn a Coxeter diagram, we select nodes that are connected to eachother only by thick or dashed lines, and to the rest by thick ordashed lines, or no lines at all. For 9875In each case, the selected nodes form the isolated cluster, and theremainder is the cocluster.
Cluster and CoclusterThe cocluster acts on the cluster through sphere inversions.
Cluster and CoclusterThe cocluster acts on the cluster through sphere inversions. Eerilyenough, we get packings!
Cluster and CoclusterThe cocluster acts on the cluster through sphere inversions. Eerilyenough, we get packings!
Structure TheoremThis is no coincidence.
Structure TheoremThis is no coincidence. In 2017, Kontorovich and Nakamuraproved the Structure Theorem for crystallographic packings: aCoxeter diagram’s isolated cluster generates a crystallographicpacking in this manner, and all crystallographic packings arise asthe orbit of an isolated cluster.
Finiteness TheoremWhy are crystallographic sphere packings a pressing topic?Recently, Kontorovich and Nakamura proved that there existfinitely many crystallographic packings. In fact, no such packingsexist in higher than 21 dimensions.
Finiteness TheoremWhy are crystallographic sphere packings a pressing topic?Recently, Kontorovich and Nakamura proved that there existfinitely many crystallographic packings. In fact, no such packingsexist in higher than 21 dimensions.This means that crystallographic packings can be systematicallyexplored and classified – which was a large part of our research thissummer.
Finiteness TheoremWhy are crystallographic sphere packings a pressing topic?Recently, Kontorovich and Nakamura proved that there existfinitely many crystallographic packings. In fact, no such packingsexist in higher than 21 dimensions.This means that crystallographic packings can be systematicallyexplored and classified – which was a large part of our research thissummer.There are 3 sources that can be used to generate crystallographicpackings, and each of us focused on one source:IAlisa – PolyhedraIDevora – Bianchi groupsIZack – Higher dimensional quadratic forms
Sources of Circle PackingsPolyhedraDimension n 3Apply K-A-T TheoremSelect quadratic formApply Vinberg’s algorithmObtain fundamental polyhedronDescribe with Coxeter diagramApply Structure TheoremGenerate circle packingWhich are integral?Bianchi groups
PolyhedraIHow can circle packings arise from polyhedra?
Polyhedra: Koebe-Andreev-Thurston TheoremITheorem: Every polyhedron (up to combinatorialequivalence) has a midsphere.
Polyhedra: Koebe-Andreev-Thurston TheoremITheorem: Every polyhedron (up to combinatorialequivalence) has a midsphere.ICombinatorial equivalence: containing the same informationabout faces, edges, and vertices, regardless of physicalrepresentation
Polyhedra: Koebe-Andreev-Thurston TheoremITheorem: Every polyhedron (up to combinatorialequivalence) has a midsphere.ICombinatorial equivalence: containing the same informationabout faces, edges, and vertices, regardless of physicalrepresentationIMidsphere: a sphere tangent to every edge in a polyhedron
Polyhedra: Koebe-Andreev-Thurston TheoremIThe midsphere gives rise to two sets of circles: facet circles(purple) and vertex horizon circles (pink)Planar representation of a polyhedron (left), its vertex horizon circles(center), and its realization with midsphere, vertex horizon circles, andfacet circles (right).Source: David Eppstein 2004
Polyhedra: Koebe-Andreev-Thurston TheoremIStereographically projecting the facet and vertex horizoncircles onto R2 yields a collection of circles in the plane.IStereographic projections map a sphere onto the plane,preserving tangencies and anglesSource: Strebe
Polyhedra: Koebe-Andreev-Thurston TheoremIStereographically projecting the facet and vertex horizoncircles onto R2 yields a collection of circles in the plane.IStereographic projections map a sphere onto the plane,preserving tangencies and anglesSource: David E. Joyce 2002
Polyhedra: Koebe-Andreev-Thurston Theorem
Polyhedra: Koebe-Andreev-Thurston TheoremIBy K-A-T, this collection of circles is unique up to circleinversions
Polyhedra: Koebe-Andreev-Thurston TheoremIBy K-A-T, this collection of circles is unique up to circleinversionsIThese circles actually generate a packing: let pink cluster,purple cocluster
Polyhedra: Generating a PackingBy constructing the Coxeter diagram of this cluster/coclustergroup, we can see that the Structure Theorem applies
Polyhedra: Generating a PackingBy constructing the Coxeter diagram of this cluster/coclustergroup, we can see that the Structure Theorem applies
Polyhedra: Generating a PackingBy constructing the Coxeter diagram of this cluster/coclustergroup, we can see that the Structure Theorem applies
Polyhedra: Generating a Packing
Polyhedra: MethodsIPolyhedron data was generated with plantri, a programcreated by Brinkmann and McKayIWe wrote code in Mathematica using some techniques fromZiegler 2004IData is being collected and presented on our website
Polyhedra: Website
Polyhedra: FindingsInterested in which polyhedra give rise to integral packings
Polyhedra: FindingsIPreviously known integral polyhedra: tetrahedron, squarepyramid, hexagonal pyramid, and gluings thereof
Polyhedra: FindingsIPreviously known integral polyhedra: tetrahedron, squarepyramid, hexagonal pyramid, and gluings thereofIDefine a gluing operation to be a joining along vertices orfaces
Polyhedra: FindingsIPreviously known integral polyhedra: tetrahedron, squarepyramid, hexagonal pyramid, and gluings thereofIIDefine a gluing operation to be a joining along vertices orfacesSince the tetrahedron, square pyramid, and hexagonalpyramid cannot be decomposed (unglued) into smallerintegral polyhedra, they can be considered seed polyhedra
Polyhedra: FindingsIPreviously known integral polyhedra: tetrahedron, squarepyramid, hexagonal pyramid, and gluings thereofIDefine a gluing operation to be a joining along vertices orfacesISince the tetrahedron, square pyramid, and hexagonalpyramid cannot be decomposed (unglued) into smallerintegral polyhedra, they can be considered seed polyhedraIWe found a new integral seed polyhedron!
Polyhedra: Findings - 6v7f 2
Polyhedra: Findings - 6v7f 2This is the packing of a hexagonal pyramid; it is in fact the samepacking as 6v7f 2.
Polyhedra: Findings - 6v7f 2
Bianchi GroupsBianchi groups, Bi(m), are the set of 2x2 matrices whose entriesare of the complex form a b m, and which have determinant 1.
Bianchi GroupsBianchi groups, Bi(m), are the set of 2x2 matrices whose entriesare of the complex form a b m, and which have determinant 1.Luigi Bianchi began studying these groups over 100 years ago, in1892.
Bianchi GroupsBianchi groups, Bi(m), are the set of 2x2 matrices whose entriesare of the complex form a b m, and which have determinant 1.Luigi Bianchi began studying these groups over 100 years ago, in1892. Before they were ever connected to circle packings!
Bianchi Groups
Bianchi GroupsFigure: Bi(2): From 1892 to 2018
Bianchi GroupsBianchi was interested in exploring which Bianchi groups arereflective, meaning finitely generated. 120 years later, Belolipetskyand McLeod conclusively showed that there are a finite number ofthese reflective Bianchi groups, and enumerated them.
Bianchi GroupsBianchi was interested in exploring which Bianchi groups arereflective, meaning finitely generated. 120 years later, Belolipetskyand McLeod conclusively showed that there are a finite number ofthese reflective Bianchi groups, and enumerated them.The reflective Bianchi groups can be used to generate circlepackings. But how do we go from matrices to circles?
Bianchi GroupsPolyhedraDimension n 3Apply K-A-T TheoremSelect quadratic formApply Vinberg’s algorithmObtain fundamental polyhedronDescribe with Coxeter diagramApply Structure TheoremGenerate circle packingWhich are integral?Bianchi groups
Bianchi GroupsPolyhedraDimension n 3Apply K-A-T TheoremSelect quadratic formBianchi groupsApply Vinberg’s algorithmMcLeod, VinbergObtain fundamental polyhedronDescribe with Coxeter diagramApply Structure TheoremGenerate circle packingWhich are integral?
Bianchi GroupsThis summer, using McLeod’s application of Vinberg’s algorithm,we catalogued all known circle packings that arise from Bianchigroups.
Bianchi GroupsThis summer, using McLeod’s application of Vinberg’s algorithm,we catalogued all known circle packings that arise from Bianchigroups.
Bianchi GroupsThis summer, using McLeod’s application of Vinberg’s algorithm,we catalogued all known circle packings that arise from Bianchigroups.
Bianchi Groups and IntegralityAn interesting property of Bianchi group circle packings is thatmost of them are integral.
Bianchi Groups and IntegralityAn interesting property of Bianchi group circle packings is thatmost of them are integral.It’s very easy to see that a packing is integral empirically just bycomputing the bends of the packing, but there’s actually a way toprove integrality more rigorously.
Bianchi Groups and IntegralityAn interesting property of Bianchi group circle packings is thatmost of them are integral.It’s very easy to see that a packing is integral empirically just bycomputing the bends of the packing, but there’s actually a way toprove integrality more rigorously.Likewise, there’s a way to prove nonintegrality of a packing.
Bianchi Groups and IntegralityAn interesting property of Bianchi group circle packings is thatmost of them are integral.It’s very easy to see that a packing is integral empirically just bycomputing the bends of the packing, but there’s actually a way toprove integrality more rigorously.Likewise, there’s a way to prove nonintegrality of a packing.An exciting part of our work this summer is proving integrality andnonintegrality for all known Bianchi packings.
Doubling in B̂i(3)One note, which will also be relevant shortly, is that an insight inKontorovich & Nakamura’s 2017 paper was the observation thatwhat was thought to be the B̂i(3) Coxeter diagram did notactually represent the full group of mirrors:
Doubling in B̂i(3)2134
Doubling in B̂i(3)1234
Doubling in B̂i(3)Through a further series of operations, we can transform thediagram121233445.into the diagram
Doubling in B̂i(3)Through a further series of operations, we can transform thediagram121233445into the diagram. However, this was done lesssystematically; it primarily derived from looking at the orbit of theoriginal generators acting on themselves until a valid configurationwas found that has an isolated cluster.
Questions About Existence of PackingsNow that we’ve covered polyhedra and Bianchi groups, which giveall the crystallographic packings in two dimensions, the naturalquestion is: Do higher dimensional packings exist? What can wesay about them?
Questions About Existence of PackingsNow that we’ve covered polyhedra and Bianchi groups, which giveall the crystallographic packings in two dimensions, the naturalquestion is: Do higher dimensional packings exist? What can wesay about them? We can answer this by looking at Coxeterdiagrams of higher-dimensional configurations, and applying theStructure Theorem, which still holds.
High-Dimensional PackingsThis summer, I worked on putting together the known candidatesfor these packings, namely 41 potential packings for quadraticnPxi2 for d 1, 2, 3.forms dx02 i 1
High-Dimensional PackingsThis summer, I worked on putting together the known candidatesfor these packings, namely 41 potential packings for quadraticnPxi2 for d 1, 2, 3. Here is a snapshot of howforms dx02 i 1some appear on our website:
High-Dimensional PackingsThe techniques discussed here have also allowed us to attack thefollowing diagrams that lack isolated clusters:Source: John McLeod
High-Dimensional PackingsThe techniques discussed here have also allowed us to attack thefollowing diagrams that lack isolated clusters:Source: John McLeodWhat’s something that all of these have in common?
High-Dimensional PackingsThe techniques discussed here have also allowed us to attack thefollowing diagrams that lack isolated clusters:Source: John McLeodWhat’s something that all of these have in common? They allfeature1234as a subdiagram!
High-Dimensional PackingsSo, if we apply the known transformation for123451234intofollowed by a suitable action onthe remainder of the nodes in the Coxeter diagram, then hopefullywe will obtain a valid diagram representing one such desiredsubgroup of mirrors.
ResultsThe following Coxeter diagrams were obtained for the n 6, 7, 8nPxi2 :cases of the quadratic form 3x02 i 1936751284231059863214779851061141
ResultsThe following is believed to work for n 10, and works for n 11:51165671213831547149215 114 101312101124981613
ResultsLastly, this behemoth is a diagram for n 13:8202116231227919111712321314181510456
ReferencesWe are much indebted to the following papers:IM. Belolipetsky, “Arithmetic Hyperblic Reflection Groups,”2016.IM. Belolipetsky & J. McLeod, “Reflective andQuasi-Reflective Bianchi Groups,” 2013.IL. Bianchi, “Sui gruppi di sostituzioni lineari con coefficientiappartenenti a corpi quadratici immaginari,” 1892.IA. Kontorovich & K. Nakamura, “Geometry and Arithmetic ofCrystallographic Sphere Packings,” 2017.IJ. McLeod, “Arithmetic Hyperbolic Reflection Groups,” 2013.IE. Vinberg, “On Groups of Unit Elements of CertainQuadratic Forms,” 1972.IG. Ziegler, “Convex Polytopes: Extremal Constructions andf -Vector Shapes,” 2004.
AcknowledgementsWe would like to acknowledge support and funding from: NSFDMS-1802119; DIMACS; and the Rutgers MathematicsDepartment. We would also like to thank Kei Nakamura and AliceMark for taking the time to discuss this material with us; and wewould most of all like to thank Professor Kontorovich for hisguidance and mentorship on these projects.
Circle Inversions Circle inversion sends points at a distance of rd from the center of the mirror circle to a distance of r d from the center of the mirror circle. I We apply circle inversions to both spheres and planes, where planes are considered spheres of in nite radius. I Circle inv
