ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 16 (2019) 349-358 https://doi.org/10.26493/1855-3974.1485.0b1 (Also available at http://amc-journal.eu) Decomposition method related to saturated hyperball packings Jeno Szirmai Budapest University of Technology and Economics, Institute of Mathematics, Department of Geometry, H-1521 Budapest, Hungary Received 14 September 2017, accepted 28 November 2018, published online 22 January 2019 In this paper we study the problem of hyperball (hypersphere) packings in 3-dimen-sional hyperbolic space. We introduce a new definition of the non-compact saturated ball packings with generalized balls (horoballs, hyperballs) and describe to each saturated hyperball packing, a new procedure to get a decomposition of 3-dimensional hyperbolic space H3 into truncated tetrahedra. Therefore, in order to get a density upper bound for hyperball packings, it is sufficient to determine the density upper bound of hyperball packings in truncated simplices. Keywords: Hyperbolic geometry, hyperball packings, Dirichlet-Voronoi cell, packing density, Coxeter tilings. Math. Subj. Class.: 52C17, 52C22, 52B15 1 Introduction In n-dimensional hyperbolic space Hn (n > 2) there are 3 kinds of generalized "balls" (spheres): the usual balls (spheres), horoballs (horospheres) and hyperballs (hyperspheres). The classical problems of ball packings and coverings with congruent generalized balls of hyperbolic spaces Hn are extensively discussed in the literature, however there are several essential open questions e.g.: 1. What are the optimal ball packing and covering configurations of usual spheres and what are their densities (n > 3) (see [1, 5, 7, 12])? 2. The monotonicity of the density related to the Boroczky type ball configurations depending on the radius of the congruent balls (n > 4) (see [4, 10]). E-mail address: szirmai@math.bme.hu (Jeno Szirmai) Abstract ©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/ 350 Ars Math. Contemp. 16 (2019) 331-348 3. What are the optimal horoball packing and covering configurations and what are their densities allowing horoballs in different types (n > 4) (see [3, 8, 9])? 4. What are the optimal packing and covering arrangements using non-compact balls (horoballs and hyperballs) and what are their densities? These are the so-called hyp-hor packings and coverings (see [21]). 5. What are the optimal hyperball packing and covering configurations and what are their densities (n > 3)? In this paper we study the 5th question related to saturated, congruent hyperball packings in 3-dimensional hyperbolic space H3. In the hyperbolic plane H2 the universal upper bound of the hypercycle packing density is n, proved by I. Vermes in [24] and the universal lower bound of the hypercycle covering density is ^n2 determined by I. Vermes in [25]. In [15] and [16] we studied the regular prism tilings (simply truncated Coxeter or-thoscheme tilings) and the corresponding optimal hyperball packings in Hn (n = 3,4) and we extended the method developed in the former paper [20] to 5-dimensional hyperbolic space. Moreover, their metric data and their densities have been determined. In paper [19] we studied the n-dimensional hyperbolic regular prism honeycombs and the corresponding coverings by congruent hyperballs and we determined their least dense covering densities. Furthermore, we formulated conjectures for the candidates of the least dense hyperball covering by congruent hyperballs in the 3- and 5-dimensional hyperbolic space (n G N, 3 < n < 5). In [22] we discussed congruent and non-congruent hyperball (hypersphere) packings of the truncated regular tetrahedron tilings. These are derived from the Coxeter simplex tilings {p, 3, 3} (7 < p G N) and {5,3, 3, 3,3} in 3- and 5-dimensional hyperbolic space. We determined the densest hyperball packing arrangement and its density with congruent hyperballs in H5 and determined the smallest density upper bounds of non-congruent hyperball packings generated by the above tilings in Hn (n = 3,5). In [21] we deal with packings derived by horo- and hyperballs (briefly hyp-hor packings) in n-dimensional hyperbolic spaces Hn (n = 2, 3) which form a new class of the classical packing problems. We constructed in the 2- and 3-dimensional hyperbolic spaces hyp-hor packings that are generated by complete Coxeter tilings of degree 1 i.e. the fundamental domains of these tilings are simple frustum orthoschemes and we determined their densest packing configurations and their densities. We proved using also numerical approximation methods that in the hyperbolic plane (n = 2) the density of the above hyp-hor packings arbitrarily approximate the universal upper bound of the hypercycle or horocycle packing density 3 and in H3 the optimal configuration belongs to the {7,3,6} Coxeter tiling with density « 0.83267. Furthermore, we analyzed the hyp-hor packings in truncated orthoschemes {p, 3,6} (6 < p < 7, p G R) whose density function is attained its maximum for a parameter which lies in the interval [6.05, 6.06] and the densities for parameters lying in this interval are larger that « 0.85397. That means that these locally optimal hyp-hor configurations provide larger densities that the Boroczky-Florian density upper bound (« 0.85328) for ball and horoball packings but these hyp-hor packing configurations can not be extended to the entirety of hyperbolic space H3. In [23] we studied a large class of hyperball packings in H3 that can be derived from truncated tetrahedron tilings. In order to get a density upper bound for the above hyperball packings, it is sufficient to determine this density upper bound locally, e.g. in truncated J. Szirmai: Decomposition method related to saturated hyperball packings 351 tetrahedra. Thus, we proved that if the truncated tetrahedron is regular, then the density of the densest packing is « 0.86338. This is larger than the Boroczky-Florian density upper bound for balls and horoballs but our locally optimal hyperball packing configuration cannot be extended to the entirety of H3. However, we described a hyperball packing construction, by the regular truncated tetrahedron tiling under the extended Coxeter group {3, 3,7} with maximal density « 0.82251. Recently, (to the best of author's knowledge) the candidates for the densest hyperball (hypersphere) packings in the 3,4 and 5-dimensional hyperbolic space Hn are derived by the regular prism tilings that have been published in papers [15, 16] and [20]. In this paper we study hyperball (hypersphere) packings in 3-dimensional hyperbolic space. We develope a decomposition algorithm that for each saturated hyperball packing provides a decomposition of H3 into truncated tetrahedra. Therefore, in order to get a density upper bound for hyperball packings, it is sufficient to determine the density upper bound of hyperball packings in truncated simplices. 2 Projective model and saturated hyperball packings in H3 We use for H3 (and analogously for Hn, n > 3) the projective model in the Lorentz space E1,3 that denotes the real vector space V4 equipped with the bilinear form of signature (1, 3), (x, y) = -x0y0 + x V + x2y2 + x3y3, where the non-zero vectors x = (x0,x1,x2,x3) € V4 and y = (y0,y1,y2,y3) G V4, are determined up to real factors, for representing points of Pn(R). Then H3 can be interpreted as the interior of the quadric Q = {(x) G P3 | (x, x) =0} =: dH3 in the real projective space P3(V4, V4) (here V4 is the dual space of V4). Namely, for an interior point y holds (y, y) < 0. Points of the boundary dH3 in P3 are called points at infinity, or at the absolute of H3. Points lying outside dH3 are said to be outer points of H3 relative to Q. Let (x) g P3, a point (y) G P3 is said to be conjugate to (x) relative to Q if (x, y) = 0 holds. The set of all points which are conjugate to (x) form a projective (polar) hyperplane pol(x) := {(y) G P3 | (x, y) =0}. Thus, the quadric Q induces a bijection (linear polarity V4 ^ V4) from the points of P3 onto their polar hyperplanes. Point X (x) and hyperplane a (a) are incident if xa = 0 (x G V4 \ {0}, a G V4 \ {0}). The hypersphere (or equidistance surface) is a quadratic surface at a constant distance from a plane (base plane) in both halfspaces. The infinite body of the hypersphere, containing the base plane, is called hyperball. The half hyperball with distance h to a base plane ft is denoted by H+. The volume of a bounded hyperball piece H+ (A), delimited by a 2-polygon Ac and its prism orthogonal to can be determined by the classical formula (2.1) of J. Bolyai [2]. Vol(H+(A)) = - Area(A) , , 2h k sinh ——+ 2h k (2.1) The constant k = y — is the natural length unit in H3, where K denotes the constant negative sectional curvature. In the following we may assume that k =1. 352 Ars Math. Contemp. 16 (2019) 331-348 Let Bh be a hyperball packing in H3 with congruent hyperballs of height h. The notion of saturated packing follows from that fact that the density of any packing can be improved by adding further packing elements as long as there is sufficient room to do so. However, we usually apply this notion for packings with congruent elements. Now, A„ An (a) (b) Figure 1: (a) Saturated hyp-hor packing, at present a = 0.7. (b) Saturated horocycle packing with parameter a = —. we modify the classical definition of saturated packing for non-compact ball packings with generalized balls (horoballs, hyperballs) in n-dimensional hyperbolic space Hn (n > 2 integer parameter): Definition 2.1. A ball packing with non-compact balls (horoballs or/and hyperballs) in Hn is saturated if no new non-compact ball can be added to it. We illustrate the meaning of the above definition by 2-dimensional Coxeter tilings given by the Coxeter symbol [to] (see Figure 1), which are denoted by Ta. The fundamental domain of Ta is a Lambert quadrilateral A0AiP0Pi (see [21]) that is denoted by Fa. It is derived by the truncation of the orthoscheme A0AiA2 by the polar line n of the outer vertex A2. The other initial principal vertex A0 of the orthoscheme is lying on the absolute quadric of the Beltrami-Cayley-Klein model. The images of Fa under reflections on its sides fill the hyperbolic plane H2 without overlap. The tilings Ta contain a free parameter 0 < a < 1, a G R. The polar straight line of A2 is n and n n A0A2 = P0, n n AiA2 = Pi. If we fix the parameter a then a optimal hypercycle tiling can be derived from the mentioned Coxeter tiling (see Figure 1(a)) but here there are sufficient rooms to add horocycles with centre A0 and with centres at the images of A0. This saturated hyp-hor packing (packing with horo- and hyperballs) is illustrated in Figure 1(a). The Figure 1(b) shows a saturated horocycle packing belonging to the same Coxeter tiling. To obtain hyperball (hypersphere) packing bounds it obviously suffices to study saturated hyperball packings (using the above definition) and in what follows we assume that all packings are saturated unless otherwise stated. J. Szirmai: Decomposition method related to saturated hyperball packings 353 3 Decomposition into truncated tetrahedra We take the set of hyperballs {Hh } of a saturated hyperball packing Bh (see Definition 2.1). Their base planes are denoted by Pi. Thus, in a saturated hyperball packing the distance between two ultraparallel base planes d(pi, p) is at least 2h (where for the natural indices holds i < j and d is the hyperbolic distance function). In this section we describe a procedure to get a decomposition of 3-dimensional hyperbolic space H3 into truncated tetrahedra corresponding to a given saturated hyperball packing. Step 1. The notion of the radical plane (or power plane) of two Euclidean spheres can be extended to the hyperspheres. The radical plane (or power plane) of two non-intersecting hyperspheres is the locus of points at which tangents drawn to both hyperspheres have the same length (so these points have equal power with respect to the two non-intersecting hyperspheres). If the two non-intersecting hyperspheres are congruent also in Euclidean sense in the model then their radical plane coincides with their "Euclidean symmetry plane" and any two congruent hypersphere can be transformed into such an hypersphere arrangement. Using the radical planes of the hyperballs Hh, similarly to the Euclidean space, can be constructed the unique Dirichlet-Voronoi (in short D-V) decomposition of H3 to the given hyperball packing Bh. Now, the D-V cells are infinite hyperbolic polyhedra containing the corresponding hyperball, and its vertices are proper points of H3. We note here (it is easy to see), that a vertex of any D-V cell cannot be outer or boundary point of H3 relative to Q, because the hyperball packing Bh is saturated by the Definition 2.1. Step 2. We consider an arbitrary proper vertex P e H3 of the above D-V decomposition and the hyperballs Hh (P) whose D-V cells meet at P. The base planes of the hyperballs Hh(P) are denoted by pi(P), and these planes determine a non-compact polyhedron Di (P) with the intersection of their halfspaces containing the vertex P. Moreover, denote A1, A2, A3,... the outer vertices of Di (P) and cut off Di (P) with the polar planes aj (P) of its outer vertices Aj. Thus, we obtain a convex compact polyhedron D(P). This is bounded by the base planes Pi(P) and "polar planes" aj (P). Applying this procedure for all vertices of the above Dirichlet-Voronoi decomposition, we obtain an other decomposition of H3 into convex polyhedra. Step 3. We consider D(P) as a tile of the above decomposition. The planes from the finite set of base planes {pi(P)} are called adjacent if there is a vertex As of Di(P) that lies on each of the above plane. We consider non-adjacent planes pkl (P), pk2 (P), pk3 (P),..., pkm (P) e {Pi(P)} (k e N+, l = 1, 2, 3,..., m) that have an outer point of intersection denoted by Akl... km. Let ND(P) e N denote the finite number of the outer points Akl... km related to D(P). It is clear, that its minimum is 0 if Di(P) is tetrahedron. The polar plane ak 1 • • km of Afci... km is orthogonal to planes Pki (P ),Pk2 (P),.. .,Pkm (P) (thus, it contains their poles Bkl, Bk2,..., Bkm) and divides D(P) into two convex polyhedra D1(P) and D2(P). m Step 4. If Ndi(p) = 0 and Nv2 (p) = 0 then N®i(p) < Nv{p) and N^p) < Nv{p) then we apply the Step 3 for polyhedra Di (P), i e {1,2}. Step 5. If NDi(P) =0 or NDj(P) =0 (i = j, i,j e {1, 2}) then we consider the polyhedron Di(P) where NDi(P) = ND(P) - 1 because the vertex Akl...km is left out and apply the Step 3. 354 Ars Math. Contemp. 16 (2019) 331-348 Step 6. If NDl(P) = 0 and ND2(P) = 0 then the procedure is over for D(P). We continue the procedure with the next cell. Step 7. It is clear, that the above plane akl •..km intersects every hyperball Hj(P) (j = ki,... ,km). Lemma 3.1. The plane akl... km of Akl ... km does not intersect the hyperballs Hlh(P) where Aki. • • km 1. In order to determine an upper bound for the density of congruent hyperball packings in H we used an extended notion of such local density. Therefore, we had to construct a decomposition of Hn into compact cells to define local density to a given hyperball packing and these corresponding cells are (not absolutely congruent) truncated tetrahedra (see the above algorithm and [23]). 2. From the above section it follows that, to each saturated hyperball packing Bh of hyperballs Hh there is a decomposition of H3 into truncated tetrahedra. Therefore, in order to get a density upper bound for hyperball packings, it is sufficient to determine the density upper bound of hyperball packings in truncated simplices. We observed in [23] that some extremal properties of hyperball packings naturally belong to the regular truncated tetrahedron (or simplex, in general, see Lemma 3.2 and Lemma 3.3 in [23]). Therefore, we studied hyperball packings in regular truncated tetrahedra, and prove that if the truncated tetrahedron is regular, then the density of the densest packing is « 0.86338 (see Theorem 5.1 in [23]). However, these hyperball packing configurations are only locally optimal, and cannot be extended to the whole space H3. Moreover, we showed that the densest known hyperball packing, dually related to the regular prism tilings, introduced in [15], can be realized by a regular truncated tetrahedron tiling with density « 0.82251. 3. In [22] we discussed the problem of congruent and non-congruent hyperball (hyper-sphere) packings to each truncated regular tetrahedron tiling. These are derived from the Coxeter simplex tilings {p, 3,3} and {5, 3,3,3,3} in the 3- and 5-dimensional hyperbolic space. We determined the densest hyperball packing arrangement and its density with congruent hyperballs in H5 (« 0.50514) and determined the smallest density upper bounds of non-congruent hyperball packings generated by the above tilings: in H3 (« 0.82251); in H5 (« 0.50514). The question of finding the densest hyperball packings and horoball packings with horoballs of different types in the n-dimensional hyperbolic spaces n > 3 has not been settled yet either (see e.g. [8, 9, 13, 23]). Optimal sphere packings in other homogeneous Thurston geometries represent another huge class of open mathematical problems. For these non-Euclidean geometries only very few results are known (e.g. [17,18]). Detailed studies are the objective of ongoing research. The applications of the above projective method seem to be interesting in (non-Euclidean) crystallography as well, a topic of much current interest. J. Szirmai: Decomposition method related to saturated hyperball packings 357 References [1] K. Bezdek, Sphere packings revisited, European J. Combin. 27 (2006), 864-883, doi:10.1016/ j.ejc.2005.05.001. [2] J. Bolyai, Appendix: Scientiam spatii absolute veram exhibens, in: F. Bolyai (ed.), Tentamen juventutem studiosam in elementa matheseos purae, elementaris ac sublimioris, methodo intuitiva, evidentiaque huic propria, introducendi, Tomus primus, Maros Vasarhelyini: J. & S. Kali, 1832. [3] K. Boroczky, Packing of spheres in spaces of constant curvature, Acta Math. Acad. Sci. Hungar. 32 (1978), 243-261, doi:10.1007/bf01902361. [4] K. Boroczky and A. Florian, Über die dichteste Kugelpackung im hyperbolischen Raum, Acta Math. Acad. Sci. Hungar. 15 (1964), 237-245, doi:10.1007/bf01897041. [5] G. Fejes Toth, G. Kuperberg and W. Kuperberg, Highly saturated packings and reduced coverings, Monatsh. Math. 125 (1998), 127-145, doi:10.1007/bf01332823. [6] G. Fejes Toth and W. Kuperberg, Packing and covering with convex sets, in: P. M. Gruber and J. M. Wills (eds.), Handbook of Convex Geometry, Volume B, North-Holland, Amsterdam, pp. 799-860, 1993, doi:10.1016/c2009-0-15706-9. [7] R. Kellerhals, Ball packings in spaces of constant curvature and the simplicial density function, J. Reine Angew. Math. 494 (1998), 189-203, doi:10.1515/crll.1998.006. [8] R. T. Kozma and J. Szirmai, Optimally dense packings for fully asymptotic Coxeter tilings by horoballs of different types, Monatsh. Math. 168 (2012), 27-47, doi:10.1007/ s00605-012-0393-x. [9] R. T. Kozma and J. Szirmai, New lower bound for the optimal ball packing density in hyperbolic 4-space, Discrete Comput. Geom. 53 (2015), 182-198, doi:10.1007/s00454-014-9634-1. [10] T. H. Marshall, Asymptotic volume formulae and hyperbolic ball packing, Ann. Acad. Sci. Fenn. Math. 24 (1999), 31-43, http://www.acadsci.fi/mathematica/Vol24/ marshall.html. [11] E. Molnar, The projective interpretation of the eight 3-dimensional homogeneous geometries, Beitrage Algebra Geom. 38 (1997), 261-288, https://www.emis.de/journals/ BAG/vol.38/no.2/8.html. [12] E. Molnár and J. Szirmai, Top dense hyperbolic ball packings and coverings for complete Coxeter orthoscheme groups, Publ. Inst. Math. (Beograd) 103 (2018), 129-146, doi:10.2298/ pim1817129m. [13] L. Nemeth, On the hyperbolic Pascal pyramid, Beitrage Algebra Geom. 57 (2016), 913-927, doi:10.1007/s13366-016-0293-7. [14] C. Radin, The symmetry of optimally dense packings, in: A. Prekopa and E. Molnar (eds.), Non-Euclidean Geometries, Springer, New York, volume 581 of Mathematics and Its Applications (New York), 2006 pp. 197-207, doi:10.1007/0-387-29555-0_10, papers from the International Conference on Hyperbolic Geometry held in Budapest, July 6- 12, 2002. [15] J. Szirmai, The regular p-gonal prism tilings and their optimal hyperball packings in the hyperbolic 3-space, Acta Math. Hungar. 111 (2006), 65-76, doi:10.1007/s10474-006-0034-8. [16] J. Szirmai, The regular prism tilings and their optimal hyperball packings in the hyperbolic n-space, Publ. Math. Debrecen 69 (2006), 195-207. [17] J. Szirmai, A candidate for the densest packing with equal balls in Thurston geometries, Beitrcige Algebra Geom. 55 (2014), 441-452, doi:10.1007/s13366-013-0158-2. 358 Ars Math. Contemp. 16 (2019) 331-348 [18] J. Szirmai, Simply transitive geodesic ball packings to S2 x R space groups generated by glide reflections, Ann. Mat. PuraAppl. 193 (2014), 1201-1211, doi:10.1007/s10231-013-0324-z. [19] J. Szirmai, The least dense hyperball covering of regular prism tilings in hyperbolic n-space, Ann. Mat. PuraAppl. 195 (2016), 235-248, doi:10.1007/s10231-014-0460-0. [20] J. Szirmai, The optimal hyperball packings related to the smallest compact arithmetic 5-orbifolds, Kragujevac J. Math. 40 (2016), 260-270, doi:10.5937/kgjmath1602260s. [21] J. Szirmai, Packings with horo- and hyperballs generated by simple frustum orthoschemes, Acta Math. Hungar. 152 (2017), 365-382, doi:10.1007/s10474-017-0728-0. [22] J. Szirmai, Density upper bound for congruent and non-congruent hyperball packings generated by truncated regular simplex tilings, Rend. Circ. Mat. Palermo 67 (2018), 307-322, doi:10. 1007/s12215-017-0316-8. [23] J. Szirmai, Hyperball packings in hyperbolic 3-space, Mat. Vesnik 70 (2018), 211-221, http: //www.vesnik.math.rs/vol/mv18 30 3.pdf. [24] I. Vermes, Ausfullungen der hyperbolischen Ebene durch kongruente Hyperzykelbereiche, Period. Math. Hungar. 10 (1979), 217-229, doi:10.1007/bf02020020. [25] I. Vermes, Über regulare Überdeckungen der Bolyai-Lobatschewskischen Ebene durch kongruente Hyperzykelbereiche, Period. Polytech. Mech. Engrg. 25 (1981), 249-261, https: //pp.bme.hu/me/article/view/58 4 2.