Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

New Upper Bounds for the Density of Translative Packings of Three-Dimensional Convex Bodies with Tetrahedral Symmetry

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

Abstract

In this paper we determine new upper bounds for the maximal density of translative packings of superballs in three dimensions (unit balls for the \(l^p_3\)-norm) and of Platonic and Archimedean solids having tetrahedral symmetry. Thereby, we improve Zong’s recent upper bound for the maximal density of translative packings of regular tetrahedra from \(0.3840\ldots \) to \(0.3745\ldots \), getting closer to the best known lower bound of \(0.3673\ldots \) We apply the linear programming bound of Cohn and Elkies which originally was designed for the classical problem of densest packings of round spheres. The proofs of our new upper bounds are computational and rigorous. Our main technical contribution is the use of invariant theory of pseudo-reflection groups in polynomial optimization.

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
$34.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
Fig. 2

Similar content being viewed by others

Notes

  1. The reason why we pick odd d is so that the resulting problem admits a strictly feasible solution. This will be better explained in Sect. 6.1.

References

  1. Andrews, G.E., Askey, R., Roy, R.: Special Functions. Encyclopedia of Mathematics and Its Applications, vol. 71. Cambridge University Press, Cambridge (1999)

  2. Bachoc, C., Gijswijt, D.C., Schrijver, A., Vallentin, F.: Invariant semidefinite programs. In: Anjos, M.F., Lasserre, J.B. (eds.) Handbook on Semidefinite, Conic and Polynomial Optimization. International Series in Operations Research and Management Science, vol. 166, pp. 219–269. Springer, New York (2012). arXiv:1007.2905

  3. Betke, U., Henk, M.: Densest lattice packings of 3-polytopes. Comput. Geom. 16(3), 157–186 (2000). arXiv:math/9909172v1

    Article  MathSciNet  MATH  Google Scholar 

  4. Blekherman, G., Parrilo, P.A., Thomas, R.R. (eds.): Semidefinite Optimization and Convex Algebraic Geometry. MOS-SIAM Series on Optimization, vol. 13. SIAM, Philadelphia (2013)

  5. Chen, E.R., Engel, M., Glotzer, S.C.: Dense crystalline dimer packings of regular tetrahedra. Discrete Comput. Geom. 44(2), 253–280 (2010). arXiv:1001.0586

    Article  MathSciNet  MATH  Google Scholar 

  6. Cohn, H., Elkies, N.: New upper bounds on sphere packings I. Ann. Math. 157(2), 689–714 (2003). arXiv:math/0110009

    Article  MathSciNet  MATH  Google Scholar 

  7. Cohn, H., Kumar, A.: Universally optimal distribution of points on spheres. J. Am. Math. Soc. 20(1), 99–148 (2007). arXiv:math/0607446

    Article  MathSciNet  MATH  Google Scholar 

  8. Cohn, H., Kumar, A., Miller, S.D., Radchenko, D., Viazovska, M.: The sphere packing problem in dimension 24 (2016). arXiv:1603.06518

  9. Cohn, H., Miller, S.D.: Some properties of optimal functions for sphere packing in dimensions 8 and 24 (2016). arXiv:1603.04759

  10. Cohn, H., Zhao, Y.: Sphere packing bounds via spherical codes. Duke Math. J. 163(10), 1965–2002 (2014). arXiv:1212.5966

    Article  MathSciNet  MATH  Google Scholar 

  11. Damasceno, P.F., Engel, M., Glotzer, S.C.: Crystalline assemblies and densest packings of a family of truncated tetrahedra and the role of directional entropic forces. ACS Nano 6(1), 609–614 (2012). arXiv:1109.1323

    Article  Google Scholar 

  12. D’Angelo, J.P.: Inequalities from Complex Analysis. Carus Mathematical Monographs, vol. 28. Mathematical Association of America, Washington (2002)

  13. D’Angelo, J.P.: Hermitian analogues of Hilbert’s 17th problem. Adv. Math. 226(5), 4607–4637 (2011). arXiv:1012.2479

    Article  MathSciNet  MATH  Google Scholar 

  14. Dunkl, C.F.: Cube group invariant spherical harmonics and Krawtchouk polynomials. Math. Z. 177(4), 561–577 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  15. Elkies, N.D., Odlyzko, A.M., Rush, J.A.: On the packing densities of superballs and other bodies. Invent. Math. 105(3), 613–639 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  16. 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). arXiv:1503.04571v1

  17. Fujisawa, K., Fukuda, M., Kobayashi, K., Kojima, M., Nakata, K., Nakata, M., Yamashita, M.: SDPA (SemiDefinite Programming Algorithm) User’s Manual—Version 7.0.5. Research Report B-448. Tokyo Institute of Technology, Tokyo (2008) http://www.is.titech.ac.jp/research/research-report/B/B-448, http://sdpa.sourceforge.net

  18. Gardner, M.: Mathematical Carnival, 2nd edn. Mathematical Association of America, Washington, DC (1989)

    MATH  Google Scholar 

  19. Gatermann, K., Parrilo, P.A.: Symmetry groups, semidefinite programs, and sums of squares. J. Pure Appl. Algebra 192(1–3), 95–128 (2004). arXiv:math/0211450

  20. Gauß, C.F.: Recension der “Untersuchung über die Eigenschaften der positiven ternären quadratischen Formen von Ludwig August Seeber”. J. Reine Angew. Math. 20, 312–320 (1840)

    MathSciNet  Google Scholar 

  21. Goethals, J.M., Seidel, J.J.: Cubature formulae, polytopes, and spherical designs. In: Davis, C., Grünbaum, B., Sherk, F.A. (eds.) The Geometric Vein, pp. 203–218. Springer, New York (1981)

    Chapter  Google Scholar 

  22. de Graaf, J., van Roij, R., Dijkstra, M.: Dense regular packings of irregular nonconvex particles. Phys. Rev. Lett. 107(15), # 155501 (2011)

  23. Gravel, S., Elser, V., Kallus, Y.: Upper bound on the packing density of regular tetrahedra and octahedra. Discrete Comput. Geom. 46, 799–818 (2011). arXiv:1008.2830

    Article  MathSciNet  MATH  Google Scholar 

  24. Groemer, H.: Über die dichteste gitterförmige Lagerung kongruenter Tetraeder. Monatsh. Math. 66(1), 12–15 (1962)

    Article  MathSciNet  MATH  Google Scholar 

  25. Hales, T.C., Ferguson, S.P.: In: Lagarias, J.C. (ed.) The Kepler Conjecture: The Hales–Ferguson Proof. Springer, New York (2011)

  26. Hicks, J.: A Poet with a Slide Rule: Piet Hein Bestrides Art and Science. Life Magazine, October 14, 55–66 (1966)

  27. Hoylman, F.J.: The densest lattice packing of tetrahedra. Bull. Am. Math. Soc. 76(1), 135–137 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  28. Humphreys, J.E.: Reflection Groups and Coxeter Groups. Cambridge Studies in Advanced Mathematics, vol. 29. Cambridge University Press, Cambridge (1990)

  29. Jiao, Y., Stillinger, F.H., Torquato, S.: Optimal packings of superballs. Phys. Rev. E 79(4), 041309 (2009). arXiv:0902.1504

    Article  MathSciNet  Google Scholar 

  30. Jiao, Y., Stillinger, F.H., Torquato, S.: Erratum: optimal packings of superballs [Phys. Rev. E 79, 041309 (2009)]. Phys. Rev. E 84(6), 069902 (2011)

    Article  Google Scholar 

  31. Jiao, Y., Torquato, S.: A packing of truncated tetrahedra that nearly fills all of space and its melting properties. J. Chem. Phys. 135(15), 151101 (2011). arXiv:1107.2300

    Article  Google Scholar 

  32. Kabatiansky, G.A., Levenshtein, V.I.: Bounds for packings on a sphere and in space. Probl. Inf. Transm. 14(1), 1–17 (1978)

    MathSciNet  Google Scholar 

  33. de Laat, D., de Oliveira Filho, F.M., Vallentin, F.: Upper bounds for packings of spheres of several radii. Forum Math. Sigma 2, e23 (2014). arXiv:1206.2608

  34. Lagarias, J.C., Zong, C.: Mysteries in packing regular tetrahedra. Notices Am. Math. Soc. 59(11), 1540–1549 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  35. Minkowski, H.: Dichteste gitterförmige Lagerung kongruenter Körper. Nachr. Ges. Wiss. Göttingen, 311–355 (1904)

  36. Ni, R., Gantapara, A.P., de Graaf, J., van Roij, R., Dijkstra, M.: Phase diagram of colloidal hard superballs: from cubes via spheres to octahedra. Soft Matter 8, 8826–8834 (2012). arXiv:1111.4357

    Article  Google Scholar 

  37. de Oliveira Filho, F.M., Vallentin, F.: Computing upper bounds for packing densities of congruent copies of a convex body I (2013). arXiv:1308.4893

  38. Pütz, A.: Translative Packings of Convex Bodies and Finite Reflection Groups. Master’s Thesis, University of Cologne (2016)

  39. Revol, N., Rouillier, F.: Motivations for an arbitrary precision interval arithmetic and the MPFI library. Reliab. Comput. 11(4), 275–290 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  40. Reznick, B.: Some concrete aspects of Hilbert’s 17th problem. In: Delzell, C.N., Madden, J.J. (eds.) Real Algebraic Geometry and Ordered Structures. Contemporary Mathematics, vol. 253, pp. 251–272. American Mathematical Society, Providence, RI (2000)

    Chapter  Google Scholar 

  41. Rossi, L., Sacanna, S., Irvine, W.T.M., Chaikin, P.M., Pine, D.J., Philipse, A.P.: Cubic crystals from cubic colloids. Soft Matter 7, 4139–4142 (2011)

    Article  Google Scholar 

  42. Rush, J.A., Sloane, N.J.A.: An improvement to the Minkowski–Hlawka bound for packing superballs. Mathematika 34(1), 8–18 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  43. Serre, J.-P.: Linear Representations of Finite Groups. Graduate Texts in Mathematics, vol. 42. Springer, New York (1977)

  44. Stanley, R.P.: Invariants of finite groups and their application to combinatorics. Bull. Am. Math. Soc. (N.S.) 1(3), 475–511 (1979)

  45. Stein, E.M., Weiss, G.L.: Introduction to Fourier Analysis on Euclidean Spaces. Princeton Mathematical Series, vol. 3. Princeton University Press, Princeton (1971)

  46. Stein, W.A., et al.: Sage Mathematics Software (Version 6.2). The Sage Development Team (http://www.sagemath.org) (2012)

  47. Sturmfels, B.: Algorithms in Invariant Theory. Texts and Monographs in Symbolic Computation. Springer, Vienna (1993)

    Book  MATH  Google Scholar 

  48. Terras, A.: Fourier Analysis on Finite Groups and Applications. London Mathematical Society Student Texts, vol. 43. Cambridge University Press, Cambridge (1999)

  49. Torquato, S., Jiao, Y.: Dense packings of the Platonic and Archimedean solids. Nature 460, 876–879 (2009). arXiv:0908.4107

    Article  Google Scholar 

  50. Torquato, S., Jiao, Y.: Dense packings of polyhedra: Platonic and Archimedean solids. Phys. Rev. E 80(4), 041104 (2009)

    Article  MathSciNet  Google Scholar 

  51. Viazovska, M.S.: The sphere packing problem in dimension 8 (2016). arXiv:1603.04246

  52. Ziegler, G.M.: Three mathematics competitions. In: Schleicher, D., Lackmann, M. (eds.) An Invitation to Mathematics: From Competitions to Research, pp. 195–205. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  53. Zong, C.: On the translative packing densities of tetrahedra and cuboctahedra. Adv. Math. 260, 130–190 (2014). arXiv:1208.0420

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

Frank Vallentin thanks Peter Littelmann for a helpful discussion. We also thank the referees for their thorough comments which helped to improve the paper. Frank Vallentin was partially supported by VIDI Grant 639.032.917 from the Netherlands Organization for Scientific Research (NWO).

Author information

Authors and Affiliations

  1. Mathematisches Institut, Universität zu Köln, Weyertal 86–90, 50931, Cologne, Germany

    Maria Dostert & Frank Vallentin

  2. Facultad de Matemáticas & Escuela de Ingeniería, Pontificia Universidad Católica de Chile, Av. Vicuña Mackenna 4860, Macul, Santiago, Chile

    Cristóbal Guzmán

  3. Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão, 1010, São Paulo, 05508-090, Brazil

    Fernando Mário de Oliveira Filho

Authors
  1. Maria Dostert
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Cristóbal Guzmán
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Fernando Mário de Oliveira Filho
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Frank Vallentin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Frank Vallentin.

Additional information

Editor in Charge: Günter M. Ziegler

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dostert, M., Guzmán, C., Filho, F.M.d.O. et al. New Upper Bounds for the Density of Translative Packings of Three-Dimensional Convex Bodies with Tetrahedral Symmetry. Discrete Comput Geom 58, 449–481 (2017). https://doi.org/10.1007/s00454-017-9882-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-017-9882-y

Keywords

Mathematics Subject Classification

Search

Navigation