In
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
,
sphere packing problems concern arrangements of non-overlapping identical
sphereA sphere is a perfectly round geometrical object in three-dimensional space, such as the shape of a round ball. Like a circle in two dimensions, a perfect sphere is completely symmetrical around its center, with all points on the surface lying the same distance r from the center point...
s which fill a space. Usually the space involved is three-
dimensionIn mathematics and physics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify each point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
al
Euclidean spaceIn mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions higher dimensions...
. However, sphere packing problems can be generalised to two dimensional space (where the "spheres" are
circleA circle is a simple shape of Euclidean geometry consisting of those points in a plane which are equidistant from a given point called the centre. The common distance of the points of a circle from its center is called its radius....
s), to
n-dimensional space (where the "spheres" are
hypersphereIn mathematics, an n-sphere is a generalization of the surface of an ordinary sphere to arbitrary dimension. For any natural number n, an n-sphere of radius r is defined as the set of points in -dimensional Euclidean space which are at distance r from a central point, where the radius r may be any...
s) and to non-Euclidean spaces such as
hyperbolic spaceIn mathematics, hyperbolic n-space, denoted Hn, is the maximally symmetric, simply connected, n-dimensional Riemannian manifold with constant sectional curvature −1. Hyperbolic space is the principal example of a space exhibiting hyperbolic geometry...
.
A typical sphere packing problem is to find an arrangement in which the spheres fill as large a proportion of the space as possible.
In
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
,
sphere packing problems concern arrangements of non-overlapping identical
sphereA sphere is a perfectly round geometrical object in three-dimensional space, such as the shape of a round ball. Like a circle in two dimensions, a perfect sphere is completely symmetrical around its center, with all points on the surface lying the same distance r from the center point...
s which fill a space. Usually the space involved is three-
dimensionIn mathematics and physics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify each point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
al
Euclidean spaceIn mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions higher dimensions...
. However, sphere packing problems can be generalised to two dimensional space (where the "spheres" are
circleA circle is a simple shape of Euclidean geometry consisting of those points in a plane which are equidistant from a given point called the centre. The common distance of the points of a circle from its center is called its radius....
s), to
n-dimensional space (where the "spheres" are
hypersphereIn mathematics, an n-sphere is a generalization of the surface of an ordinary sphere to arbitrary dimension. For any natural number n, an n-sphere of radius r is defined as the set of points in -dimensional Euclidean space which are at distance r from a central point, where the radius r may be any...
s) and to non-Euclidean spaces such as
hyperbolic spaceIn mathematics, hyperbolic n-space, denoted Hn, is the maximally symmetric, simply connected, n-dimensional Riemannian manifold with constant sectional curvature −1. Hyperbolic space is the principal example of a space exhibiting hyperbolic geometry...
.
A typical sphere packing problem is to find an arrangement in which the spheres fill as large a proportion of the space as possible. The proportion of space filled by the spheres is called the density of the arrangement. As the density of an arrangement can vary depending on the volume over which it is measured, the problem is usually to maximise the
averageIn mathematics, an average, central tendency of a data set is a measure of the "middle" or "expected" value of the data set. There are many different descriptive statistics that can be chosen as a measurement of the central tendency of the data items. These include arithmetic mean, the median and...
or asymptotic density, measured over a large enough volume.
A
regular arrangement (also called a
periodic or
lattice arrangement) is one in which the centres of the spheres form a very symmetric pattern called a
latticeIn mathematics, especially in geometry and group theory, a lattice in R
n is a discrete subgroup of R
n which spans the real vector space R
n. Every lattice in R
n can be generated from a basis for the vector space by forming all linear combinations with...
. Arrangements in which the spheres are not arranged in a lattice are called
irregular or
aperiodic arrangements. Regular arrangements are easier to handle than irregular ones—their high degree of
symmetrySymmetry generally conveys two primary meanings. The first is an imprecise sense of harmonious or aesthetically pleasing proportionality and balance; such that it reflects beauty or perfection...
makes it easier to classify them and to measure their densities.
Circle packing
In two dimensional Euclidean space,
Carl Friedrich GaussJohann Carl Friedrich Gauss was a German mathematician and scientist who contributed significantly to many fields, including number theory, statistics, analysis, differential geometry, geodesy, geophysics, electrostatics, astronomy and optics...
proved that the regular arrangement of circles with the highest density is the
hexagonIn geometry, a hexagon is a polygon with six edges and six vertices. A regular hexagon has Schläfli symbol {6}.- Regular hexagon :The internal angles of a regular hexagon are all 120° and the hexagon has 720 degrees T. It has 6 rotational symmetries and 6 reflection symmetries, making up the...
al packing arrangement, in which the centres of the circles are arranged in a hexagonal lattice (staggered rows, like a
honeycombA honeycomb is a mass of hexagonal waxcells built by commercial and wild honey bees in their nests to contain their larvae and stores of honey and pollen.Beekeepers may remove the entire honeycomb to harvest honey...
), and each circle is surrounded by 6 other circles. The density of this arrangement is
In 1940, Hungarian mathematician
László Fejes TóthLászló Fejes Tóth was a Hungarian mathematician who specialised in geometry. He proved that a honeycomb pattern is the most efficient way to pack equal circles in the Euclidean plane, and investigated packings on the sphere...
proved that the hexagonal lattice is the densest of all possible circle packings, both regular and irregular.
The branch of mathematics generally known as
"circle packing"The circle packing theorem describes the possible tangency relations between circles in the plane whose interiors are disjoint. A packing of circles is a collection of circles whose interiors are disjoint...
, however, is not concerned with dense packing of equal-sized circles but with the geometry and combinatorics of packings of arbitrarily-sized circles; these give rise to discrete analogs of conformal mapping,
Riemann surfaceIn mathematics, particularly in complex analysis, a Riemann surface, first studied by and named after Bernhard Riemann, is a one-dimensional complex manifold. Riemann surfaces can be thought of as "deformed versions" of the complex plane: locally near every point they look like patches of the...
s and the like.
Regular packing
In three-dimensional Euclidean space, let us consider a plane with a compact arrangement of spheres on it. If we consider three neighbouring spheres, we can put a fourth sphere in the hollow between the three bottom spheres. If we do this "everywhere" in a second plane above the first, we create a new compact arrangement. The third layer can superimpose to the first one, or the spheres can be upon a hollow of the first layer. There are thus three types of planes, called A, B and C.
Gauss proved these arrangements have the highest density amongst the regular arrangements.
The two most common arrangements are called cubic close packing (or face centred cubic) — ABCABC… alternance — and hexagonal close packing — ABAB… alternance. But all combinations are possible (ABAC, ABCBA, ABCBAC, etc.). In all of these arrangements each sphere is surrounded by 12 other spheres, and both arrangements have an average density of
In 1611
Johannes KeplerJohannes Kepler was a German mathematician, astronomer and astrologer, and key figure in the 17th century scientific revolution. He is best known for his eponymous laws of planetary motion, codified by later astronomers based on his works Astronomia nova, Harmonices Mundi, and Epitome of...
had conjectured that this is the maximum possible density for both regular and irregular arrangements — this became known as the
Kepler conjectureThe Kepler conjecture, named after Johannes Kepler, is a mathematical conjecture about sphere packing in three-dimensional Euclidean space. It says that no arrangement of equally sized spheres filling space has a greater average density than that of the cubic close packing and hexagonal close...
. In 1998
Thomas HalesThomas Callister Hales is an American mathematician who, while on faculty at the University of Michigan, provided a computer-aided proof of the Kepler Conjecture. This conjecture had been the oldest problem in discrete geometry...
, following the approach suggested by
László Fejes TóthLászló Fejes Tóth was a Hungarian mathematician who specialised in geometry. He proved that a honeycomb pattern is the most efficient way to pack equal circles in the Euclidean plane, and investigated packings on the sphere...
in 1953, announced the proof of the Kepler conjecture. Hales' proof is a
proof by exhaustionProof by exhaustion, also known as proof by cases, perfect induction, or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases, and each case is proved separately...
involving checking of many individual cases using complex computer calculations. Referees have said that they are "99% certain" of the correctness of Hales' proof, so the Kepler conjecture has almost certainly been proved.
Irregular packing
If we attempt to build a densely packed collection of spheres, we will be tempted to always place the next sphere in a hollow between three packed spheres. If five spheres are assembled in this way, they will be consistent with one of the regularly packed arrangements described above. However, the sixth sphere placed in this way will render the structure inconsistent with any regular arrangement. (Chaikin, 2007). This results in the possibility of a
random close packRandom close packing is an empirical parameter used to characterize the maximum volume fraction of solid objects obtained when they are packed randomly. For example, when a solid container is filled with grain, shaking the container will reduce the volume taken up by the objects, thus allowing...
ing of spheres which is stable against compression.
When spheres are randomly added to a container and then compressed, they will generally form what is known as an "irregular" or "jammed" packing configuration when they can be compressed no more. This irregular packing will generally have a density of about 64%. Recent research predicts analytically that it cannot exceed a density limit of 63.4% This situation is unlike the case of one or two dimensions, where compressing a collection of 1-dimensional or 2-dimensional spheres (i.e. line segments or disks) will yield a regular packing.
Hypersphere packing
In dimensions higher than three, the densest regular packings of hyperspheres are known up to 8 dimensions. Very little is known about irregular hypersphere packings — it is possible that in some dimensions the densest packing may be irregular. Some support for this conjecture comes from the fact that in certain dimensions (e.g. 10) the densest known irregular packing is denser than the densest known regular packing.
Dimension 24 is special due to the existence of the
Leech latticeIn mathematics, the Leech lattice is a particular lattice Λ in 24-dimensional Euclidean space E24 discovered by John Leech in 1965...
, which has the best kissing number and for a long time was suspected to be the densest lattice packing. In 2004, Cohn and Kumar
1 published a preprint proving this conjecture, and in addition showing that an irregular packing may improve over the Leech lattice packing, if at all, by no more than 2.
Another line of research in high dimensions is trying to find asymptotic bounds for the density of the densest packings. Currently the best known result is that there exists a lattice in dimension
n with density bigger or equal to for some number
c.
Hyperbolic space
Although the concept of circles and spheres can be extended to hyperbolic space, finding the densest packing becomes much more difficult. In a hyperbolic space there is no limit to the number of spheres that can surround another sphere (for example,
Ford circleIn mathematics, a Ford circle is a circle with centre at and radius 1/, where p/q is an irreducible fraction, i.e. p and q are coprime integers...
s can be thought of as an arrangement of identical hyperbolic circles in which each circle is surrounded by an infinite number of other circles). The concept of average density also becomes much more difficult to define accurately.
Despite these difficulties, Charles Radin and Lewis Bowen of the
University of Texas at AustinThe University of Texas at Austin is a public research university located in Austin, Texas, United States, and is the flagship institution of The University of Texas System. The main campus is located approximately from the Texas State Capitol...
showed in May 2002 that the densest packings in any hyperbolic space are almost always irregular.
Other spaces
Sphere packing on the corners of a hypercube (with the spheres defined by
Hamming distanceIn information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...
) corresponds to designing error-correcting codes: if the spheres have radius
d, then their centers are codewords of a
d-error-correcting code. Lattice packings correspond to linear codes. There are other, subtler relationships between Euclidean sphere packing and error-correcting codes; thus, the
binary Golay codeIn mathematics and electronics engineering, a binary Golay code is a type of error-correcting code used in digital communications. The binary Golay code, along with the ternary Golay code, has a particularly deep and interesting connection to the theory of finite sporadic groups in mathematics....
is closely related to the 24-dimensional
Leech latticeIn mathematics, the Leech lattice is a particular lattice Λ in 24-dimensional Euclidean space E24 discovered by John Leech in 1965...
.
See also
- Apollonian sphere packing
Apollonian sphere packing is the three dimensional equivalent of the Apollonian gasket. The principle of construction is very similar: if you have any four spheres which are cotangent to each other, it is then possible to construct two more spheres which are cotangent to four of them.The fractal...
- Hermite constant
In mathematics, the Hermite constant for integers n > 0, named after Charles Hermite, is defined as follows. Given a lattice L in Euclidean space Rn,...
- Kissing number problem
In geometry, the kissing number is the maximum number of spheres of radius 1 that can simultaneously touch the unit sphere in n-dimensional Euclidean space...
- Sphere-packing bound
- Packing problem
Packing problems are one area where mathematics meets puzzles . Many of these problems stem from real-life problems with packing items.In a packing problem, you are given:...
External links
- A non-technical overview of packing in hyperbolic space.