Abstract
In 1978, Makai Jr. established a remarkable connection between the volume-product of a convex body, its maximal lattice packing density and the minimal density of a lattice arrangement of its polar body intersecting every affine hyperplane. Consequently, he formulated a conjecture that can be seen as a dual analog of Minkowski’s fundamental theorem, and which is strongly linked to the well-known Mahler-conjecture. Based on the covering minima of Kannan and Lovász and a problem posed by Fejes Tóth, we arrange Makai Jr.’s conjecture into a wider context and investigate densities of lattice arrangements of convex bodies intersecting every i-dimensional affine subspace. Then it becomes natural also to formulate and study a dual analog to Minkowski’s second fundamental theorem. As our main results, we derive meaningful asymptotic lower bounds for the densities of such arrangements, and furthermore, we solve the problems exactly for the special, yet important, class of unconditional convex bodies.
Similar content being viewed by others
Notes
The natural idea to establish that the set of lattices \(\Lambda \in {\mathcal {L}}^n\) with the property that \(K+\Lambda \) intersects every affine \((n-i)\)-dimensional subspace is closed exhibits some difficulties. In fact, it is not clear whether this holds in general. We refer to [26, Prop. 3.6] and its discussion for more information on this issue.
Aicke Hinrichs (personal communication) pointed out to us that the volume of \(P_{n,i}\) can also be computed via a probabilistic argument based on the Irwin–Hall distribution.
References
Aliev, I.: On the lattice programming gap of the group problems. Oper. Res. Lett. 43(2), 199–202 (2015)
Álvarez Paiva, J.C., Balacheff, F., Tzanev, K.: Isosystolic inequalities for optical hypersurfaces. Adv. Math. 301, 934–972 (2016)
Averkov, G., Wagner, C.: Inequalities for the lattice width of lattice-free convex sets in the plane. Beitr. Algebra Geom. 53(1), 1–23 (2012)
Bambah, R.P., Woods, A.C.: On a problem of G. Fejes Tóth. Proc. Indian Acad. Sci. Math. Sci. 104(1), 137–156 (1994)
Banaszczyk, W.: Inequalities for convex bodies and polar reciprocal lattices in \(\mathbf{R}^n\). II. Application of \(K\)-convexity. Discrete Comput. Geom. 16(3), 305–311 (1996)
Beck, M., Robins, S.: Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra. Undergraduate Texts in Mathematics, 2nd edn. Springer, New York (2015)
Betke, U., Henk, M.: Densest lattice packings of 3-polytopes. Comput. Geom. 16(3), 157–186 (2000)
Betke, U., Henk, M., Wills, J.M.: Successive-minima-type inequalities. Discrete Comput. Geom. 9(2), 165–175 (1993)
Böröczky, K., Bárány, I., Makai Jr., E., Pach, J.: Maximal volume enclosed by plates and proof of the chessboard conjecture. Discrete Math. 60, 101–120 (1986)
Böröczky, K., Makai Jr., E., Meyer, M., Reisner, S.: On the volume product of planar polar convex bodies—lower estimates with stability. Stud. Sci. Math. Hung. 50(2), 159–198 (2013)
Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2010)
Fejes Tóth, G.: Research problem 18. Period. Math. Hung. 7(1), 89–90 (1976)
Fejes Tóth, G.: New results in the theory of packing and covering. In: Gruber, P.M., Wills, J.M. (eds.) Convexity and Its Applications, pp. 318–359. Birkhäuser, Basel (1983)
Fejes Tóth, G., Fodor, F., Vígh, V.: The packing density of the \(n\)-dimensional cross-polytope. Discrete Comput. Geom. 54(1), 182–194 (2015)
Fejes Tóth, L.: On the density of a connected lattice of convex bodies. Acta Math. Acad. Sci. Hung. 24, 373–376 (1973)
Fejes Tóth, L., Makai Jr., E.: On the thinnest non-separable lattice of convex plates. Stud. Sci. Math. Hung. 9, 191–193 (1974)
Groemer, H.: Zusammenhängende Lagerungen konvexer Körper. Math. Z. 94, 66–78 (1966)
Gruber, P.M.: Convex and Discrete Geometry. Grundlehren der Mathematischen Wissenschaften, vol. 336. Springer, Berlin (2007)
Gruber, P.M., Lekkerkerker, C.G.: Geometry of Numbers. North-Holland Mathematical Library. North-Holland, Amsterdam (1987)
Jarník, V.: Zwei Bemerkungen zur Geometrie der Zahlen. Věstník Královské České Společnosti Nauk Třída Matemat.-Přírodověd. (1941) (in Czech)
Kannan, R.: Lattice translates of a polytope and the Frobenius problem. Combinatorica 12(2), 161–177 (1992)
Kannan, R., Lovász, L.: Covering minima and lattice-point-free convex bodies. Ann. Math. 128(3), 577–602 (1988)
Kuperberg, G.: From the Mahler conjecture to Gauss linking integrals. Geom. Funct. Anal. 18(3), 870–892 (2008)
Mahler, K.: Polar analogues of two theorems by Minkowski. Bull. Aust. Math. Soc. 11, 121–129 (1974)
Makai Jr., E.: On the thinnest nonseparable lattice of convex bodies. Stud. Sci. Math. Hung. 13(1–2), 19–27 (1978)
Makai Jr., E., Martini, H.: Density estimates for \(k\)-impassable lattices of balls and general convex bodies in \({\mathbb{R}}^n\). https://arxiv.org/abs/1612.01307 (2016)
Malikiosis, R.-D.: A discrete analogue for Minkowski’s second theorem on successive minima. Adv. Geom. 12(2), 365–380 (2012)
Marklof, J., Strömbergsson, A.: Diameter of random circulant graphs. Combinatorica 33(4), 429–466 (2013)
Martinet, J.: Perfect Lattices in Euclidean Spaces. Grundlehren der Mathematischen Wissenschaften, vol. 327. Springer, Berlin (2003)
Meyer, M.: A volume inequality concerning sections of convex sets. Bull. Lond. Math. Soc. 20(2), 151–155 (1988)
Minkowski, H.: Geometrie der Zahlen. Bibliotheca Mathematica Teubneriana, vol. 40. Teubner, Leipzig–Berlin (1896). Reprinted by Johnson Reprint Corp., New York (1968)
Rogers, C.A., Shephard, G.C.: Convex bodies associated with a given convex body. J. Lond. Math. Soc. 33, 270–281 (1958)
Schnell, U.: A Minkowski-type theorem for covering minima in the plane. Geom. Dedicata 55(3), 247–255 (1995)
Stanley, R.P.: Eulerian partitions of a unit hypercube. In: Aigner, M. (ed.) Higher Combinatorics. Riedel, Dordrecht, Boston (1977)
Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, New York (1995)
Acknowledgements
We thank Iskander Aliev for pointing us to the connection of covering radii of simplices and diameters of quotient lattice graphs. We are grateful to Peter Gritzmann, Martin Henk, and María A. Hernández Cifre for providing opportunities for mutual research visits of the authors and for useful discussions on the topics of this paper. Finally, we thank the anonymous referees for very useful comments, corrections, and suggestions that greatly improved the presentation. Parts of this research were carried out during the authors’ stay at the Mathematisches Forschungsinstitut Oberwolfach within the program “Research in Pairs” in 2014. The first author was partially supported by Fundación Séneca, Science and Technology Agency of the Región de Murcia, through the Programa de Formación Postdoctoral de Personal Investigador, project reference 19769/PD/15, and the Programme in Support of Excellence Groups of the Región de Murcia, Spain, project reference 19901/GERM/15, and MINECO project reference MTM2015-63699-P, Spain. The second author was supported by the Freie Universität Berlin within the Excellence Initiative of the German Research Foundation.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editor in Charge: János Pach
Rights and permissions
About this article
Cite this article
Merino, B.G., Schymura, M. On Densities of Lattice Arrangements Intersecting Every i-Dimensional Affine Subspace. Discrete Comput Geom 58, 663–685 (2017). https://doi.org/10.1007/s00454-017-9911-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-017-9911-x
Keywords
- Convex body
- Lattice point
- Covering minimum
- Lattice arrangement
- Density
- Polar body
- Linear form
- Unconditional body
- Quotient lattice graph