Ulam's packing conjecture

Last updated
Unsolved problem in mathematics:

Is there any three-dimensional convex body with lower packing density than the sphere?

Contents

Ulam's packing conjecture, named for Stanislaw Ulam, is a conjecture about the highest possible packing density of identical convex solids in three-dimensional Euclidean space. The conjecture says that the optimal density for packing congruent spheres is smaller than that for any other convex body. That is, according to the conjecture, the ball is the convex solid which forces the largest fraction of space to remain empty in its optimal packing structure. This conjecture is therefore related to the Kepler conjecture about sphere packing. Since the solution to the Kepler conjecture establishes that identical balls must leave ≈25.95% of the space empty, Ulam's conjecture is equivalent to the statement that no other convex solid forces that much space to be left empty.

Origin

This conjecture was attributed posthumously to Ulam by Martin Gardner, who remarks in a postscript added to one of his Mathematical Games columns that Ulam communicated this conjecture to him in 1972. [1] Though the original reference to the conjecture states only that Ulam "suspected" the ball to be the worst case for packing, the statement has been subsequently taken as a conjecture.

Supporting arguments

Numerical experiments with a large variety of convex solids have resulted in each case in the construction of packings that leave less empty space than is left by close-packing of equal spheres, and so many solids have been ruled out as counterexamples of Ulam's conjecture. [2] Nevertheless, there is an infinite space of possible shapes that have not been ruled out.

Yoav Kallus has shown that at least among point-symmetric bodies, the ball constitutes a local maximum of the fraction of empty space forced. [3] That is, any point-symmetric solid that does not deviate too much from a ball can be packed with greater efficiency than can balls.

Analogs in other dimensions

The analog of Ulam's packing conjecture in two dimensions would say that no convex shape forces more than ≈9.31% of the plane to remain uncovered, since that is the fraction of empty space left uncovered in the densest packing of disks. However, the regular octagon and smoothed octagon give counter-examples. It is conjectured that regular heptagons force the largest fraction of the plane to remain uncovered. [4] In dimensions above four (excluding 8 and 24), the situation is complicated by the fact that the analogs of the Kepler conjecture remain open.

Related Research Articles

<span class="mw-page-title-main">Polyhedron</span> 3D shape with flat faces, straight edges and sharp corners

In geometry, a polyhedron is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices.

<span class="mw-page-title-main">Rhombicuboctahedron</span> Archimedean solid with 26 faces

In geometry, the rhombicuboctahedron, or small rhombicuboctahedron or Rectified Rhombic Dodecahedron, is a polyhedron with eight triangular, six square, and twelve rectangular faces. There are 24 identical vertices, with one triangle, one square, and two rectangles meeting at each one. If all the rectangles are themselves square, it is an Archimedean solid. The polyhedron has octahedral symmetry, like the cube and octahedron. Its dual is called the deltoidal icositetrahedron or trapezoidal icositetrahedron, although its faces are not really true trapezoids.

<span class="mw-page-title-main">Packing problems</span> Problems which attempt to find the most efficient way to pack objects into containers

Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few containers as possible. Many of these problems can be related to real-life packaging, storage and transportation issues. Each packing problem has a dual covering problem, which asks how many of the same objects are required to completely cover every region of the container, where objects are allowed to overlap.

The Kepler conjecture, named after the 17th-century mathematician and astronomer Johannes Kepler, is a mathematical theorem about sphere packing in three-dimensional Euclidean space. It states that no arrangement of equally sized spheres filling space has a greater average density than that of the cubic close packing and hexagonal close packing arrangements. The density of these arrangements is around 74.05%.

<span class="mw-page-title-main">Sphere packing</span> An arrangement of non-overlapping spheres within a containing space

In geometry, a sphere packing is an arrangement of non-overlapping spheres within a containing space. The spheres considered are usually all of identical size, and the space is usually three-dimensional Euclidean space. However, sphere packing problems can be generalised to consider unequal spheres, spaces of other dimensions or to non-Euclidean spaces such as hyperbolic space.

<span class="mw-page-title-main">Discrete geometry</span> Branch of geometry that studies combinatorial properties and constructive methods

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

<span class="mw-page-title-main">Rhombic enneacontahedron</span> Convex polyhedron with 90 rhombic faces

In geometry, a rhombic enneacontahedron is a polyhedron composed of 90 rhombic faces; with three, five, or six rhombi meeting at each vertex. It has 60 broad rhombi and 30 slim. The rhombic enneacontahedron is a zonohedron with a superficial resemblance to the rhombic triacontahedron.

Hilbert's eighteenth problem is one of the 23 Hilbert problems set out in a celebrated list compiled in 1900 by mathematician David Hilbert. It asks three separate questions about lattices and sphere packing in Euclidean space.

László Fejes Tóth was a Hungarian mathematician who specialized in geometry. He proved that a lattice pattern is the most efficient way to pack centrally symmetric convex sets on the Euclidean plane. He also investigated the sphere packing problem. He was the first to show, in 1953, that proof of the Kepler conjecture can be reduced to a finite case analysis and, later, that the problem might be solved using a computer.

<span class="mw-page-title-main">Circle packing</span> Field of geometry closely arranging circles on a plane

In geometry, circle packing is the study of the arrangement of circles on a given surface such that no overlapping occurs and so that no circle can be enlarged without creating an overlap. The associated packing density, η, of an arrangement is the proportion of the surface covered by the circles. Generalisations can be made to higher dimensions – this is called sphere packing, which usually deals only with identical spheres.

<span class="mw-page-title-main">Tetrahedron packing</span>

In geometry, tetrahedron packing is the problem of arranging identical regular tetrahedra throughout three-dimensional space so as to fill the maximum possible fraction of space.

In convex geometry, the Mahler volume of a centrally symmetric convex body is a dimensionless quantity that is associated with the body and is invariant under linear transformations. It is named after German-English mathematician Kurt Mahler. It is known that the shapes with the largest possible Mahler volume are the balls and solid ellipsoids; this is now known as the Blaschke–Santaló inequality. The still-unsolved Mahler conjecture states that the minimum possible Mahler volume is attained by a hypercube.

<span class="mw-page-title-main">Smoothed octagon</span>

The smoothed octagon is a region in the plane found by Karl Reinhardt in 1934 and conjectured by him to have the lowest maximum packing density of the plane of all centrally symmetric convex shapes. It was also independently discovered by Kurt Mahler in 1947. It is constructed by replacing the corners of a regular octagon with a section of a hyperbola that is tangent to the two sides adjacent to the corner and asymptotic to the sides adjacent to these.

<span class="mw-page-title-main">Károly Bezdek</span> Hungarian-Canadian mathematician

Károly Bezdek is a Hungarian-Canadian mathematician. He is a professor as well as a Canada Research Chair of mathematics and the director of the Centre for Computational and Discrete Geometry at the University of Calgary in Calgary, Alberta, Canada. Also he is a professor of mathematics at the University of Pannonia in Veszprém, Hungary. His main research interests are in geometry in particular, in combinatorial, computational, convex, and discrete geometry. He has authored 3 books and more than 130 research papers. He is a founding Editor-in-Chief of the e-journal Contributions to Discrete Mathematics (CDM).

Karl August Reinhardt was a German mathematician whose research concerned geometry, including polygons and tessellations. He solved one of the parts of Hilbert's eighteenth problem, and is the namesake of the Reinhardt polygons.

In mathematics, especially in geometry, a double lattice in n is a discrete subgroup of the group of Euclidean motions that consists only of translations and point reflections and such that the subgroup of translations is a lattice. The orbit of any point under the action of a double lattice is a union of two Bravais lattices, related to each other by a point reflection. A double lattice in two dimensions is a p2 wallpaper group. In three dimensions, a double lattice is a space group of the type 1, as denoted by international notation.

A packing density or packing fraction of a packing in some space is the fraction of the space filled by the figures making up the packing. In simplest terms, this is the ratio of the volume of bodies in a space to the volume of the space itself. In packing problems, the objective is usually to obtain a packing of the greatest possible density.

In mathematics, the theory of finite sphere packing concerns the question of how a finite number of equally-sized spheres can be most efficiently packed. The question of packing finitely many spheres has only been investigated in detail in recent decades, with much of the groundwork being laid by László Fejes Tóth.

References

  1. Gardner, Martin (1995), New Mathematical Diversions (Revised Edition) , Washington: Mathematical Association of America, p.  251
  2. de Graaf, Joost; van Roij, René; Dijkstra, Marjolein (2011), "Dense Regular Packings of Irregular Nonconvex Particles", Physical Review Letters , 107 (15): 155501, arXiv: 1107.0603 , Bibcode:2011PhRvL.107o5501D, doi:10.1103/PhysRevLett.107.155501, PMID   22107298.
  3. Kallus, Yoav (2014), "The 3-ball is a local pessimum for packing", Advances in Mathematics , 264: 355–370, arXiv: 1212.2551 , doi: 10.1016/j.aim.2014.07.015 , MR   3250288.
  4. Kallus, Yoav (2015), "Pessimal packing shapes", Geometry & Topology , 19: 343–363, arXiv: 1305.0289 , doi: 10.2140/gt.2015.19.343 , MR   3318753.