SpringerLink
Log in

On Densities of Lattice Arrangements Intersecting Every i-Dimensional Affine Subspace

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Notes

  1. The interested reader may also consult the paper of Averkov and Wagner [3] which includes a correction to Theorem (2.13) of [22], concerning linear relations among covering minima.

  2. In general, it is not clear whether the infimum \(\theta _i(K)\) is attained by a suitable lattice (cf. [26, Prop. 3.6]). It is known to be attained in the case of lattice coverings \(i=n\), the case \(i=1\) (cf. [21, 25]), and for the Euclidean ball in small dimensions (cf.Table 1).

  3. 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.

  4. 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

  1. Aliev, I.: On the lattice programming gap of the group problems. Oper. Res. Lett. 43(2), 199–202 (2015)

    Article  MathSciNet  Google Scholar 

  2. Álvarez Paiva, J.C., Balacheff, F., Tzanev, K.: Isosystolic inequalities for optical hypersurfaces. Adv. Math. 301, 934–972 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  3. 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)

    Article  MathSciNet  MATH  Google Scholar 

  4. 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)

    Article  MathSciNet  MATH  Google Scholar 

  5. 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)

    Article  MathSciNet  MATH  Google Scholar 

  6. Beck, M., Robins, S.: Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra. Undergraduate Texts in Mathematics, 2nd edn. Springer, New York (2015)

  7. Betke, U., Henk, M.: Densest lattice packings of 3-polytopes. Comput. Geom. 16(3), 157–186 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  8. Betke, U., Henk, M., Wills, J.M.: Successive-minima-type inequalities. Discrete Comput. Geom. 9(2), 165–175 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  9. 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)

    Article  MathSciNet  MATH  Google Scholar 

  10. 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)

    MathSciNet  MATH  Google Scholar 

  11. Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2010)

    Google Scholar 

  12. Fejes Tóth, G.: Research problem 18. Period. Math. Hung. 7(1), 89–90 (1976)

    MATH  Google Scholar 

  13. 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)

    Chapter  Google Scholar 

  14. 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)

    Article  MathSciNet  MATH  Google Scholar 

  15. Fejes Tóth, L.: On the density of a connected lattice of convex bodies. Acta Math. Acad. Sci. Hung. 24, 373–376 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  16. Fejes Tóth, L., Makai Jr., E.: On the thinnest non-separable lattice of convex plates. Stud. Sci. Math. Hung. 9, 191–193 (1974)

    MathSciNet  MATH  Google Scholar 

  17. Groemer, H.: Zusammenhängende Lagerungen konvexer Körper. Math. Z. 94, 66–78 (1966)

    Article  MathSciNet  MATH  Google Scholar 

  18. Gruber, P.M.: Convex and Discrete Geometry. Grundlehren der Mathematischen Wissenschaften, vol. 336. Springer, Berlin (2007)

    Google Scholar 

  19. Gruber, P.M., Lekkerkerker, C.G.: Geometry of Numbers. North-Holland Mathematical Library. North-Holland, Amsterdam (1987)

    MATH  Google Scholar 

  20. 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)

  21. Kannan, R.: Lattice translates of a polytope and the Frobenius problem. Combinatorica 12(2), 161–177 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  22. Kannan, R., Lovász, L.: Covering minima and lattice-point-free convex bodies. Ann. Math. 128(3), 577–602 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  23. Kuperberg, G.: From the Mahler conjecture to Gauss linking integrals. Geom. Funct. Anal. 18(3), 870–892 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  24. Mahler, K.: Polar analogues of two theorems by Minkowski. Bull. Aust. Math. Soc. 11, 121–129 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  25. Makai Jr., E.: On the thinnest nonseparable lattice of convex bodies. Stud. Sci. Math. Hung. 13(1–2), 19–27 (1978)

    MathSciNet  MATH  Google Scholar 

  26. 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)

  27. Malikiosis, R.-D.: A discrete analogue for Minkowski’s second theorem on successive minima. Adv. Geom. 12(2), 365–380 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  28. Marklof, J., Strömbergsson, A.: Diameter of random circulant graphs. Combinatorica 33(4), 429–466 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  29. Martinet, J.: Perfect Lattices in Euclidean Spaces. Grundlehren der Mathematischen Wissenschaften, vol. 327. Springer, Berlin (2003)

    Book  Google Scholar 

  30. Meyer, M.: A volume inequality concerning sections of convex sets. Bull. Lond. Math. Soc. 20(2), 151–155 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  31. Minkowski, H.: Geometrie der Zahlen. Bibliotheca Mathematica Teubneriana, vol. 40. Teubner, Leipzig–Berlin (1896). Reprinted by Johnson Reprint Corp., New York (1968)

  32. Rogers, C.A., Shephard, G.C.: Convex bodies associated with a given convex body. J. Lond. Math. Soc. 33, 270–281 (1958)

    Article  MathSciNet  MATH  Google Scholar 

  33. Schnell, U.: A Minkowski-type theorem for covering minima in the plane. Geom. Dedicata 55(3), 247–255 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  34. Stanley, R.P.: Eulerian partitions of a unit hypercube. In: Aigner, M. (ed.) Higher Combinatorics. Riedel, Dordrecht, Boston (1977)

    Google Scholar 

  35. Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, New York (1995)

    Book  Google Scholar 

Download references

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

  1. University Centre of Defence, Spanish Air Force Academy, MDE-UPCT, Santiago de la Ribera, 30720, Murcia, Spain

    Bernardo González Merino

  2. Institut für Mathematik, Freie Universität Berlin, Arnimallee 2, 14195, Berlin, Germany

    Matthias Schymura

Authors
  1. Bernardo González Merino
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Matthias Schymura
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Matthias Schymura.

Additional information

Editor in Charge: János Pach

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-017-9911-x

Keywords

Mathematics Subject Classification

Search

Navigation