In mathematics, the Kepler conjecture is a conjecture about sphere packing in three dimensional Euclidean space. It says that no arrangement of equal spheres filling space has a greater average density than that of the cubic close packing (face centered cubic) and hexagonal close packing arrangements. The density of these arrangements is a little over 74%. Euclid, detail from The School of Athens by Raphael. ... In mathematics, a conjecture is a mathematical statement which has been proposed as a true statement, but which no one has yet been able to prove or disprove. ... In mathematics, sphere packing problems are problems concerning arrangements of non-overlapping identical spheres which fill a space. ... In mathematics, Euclidean space is a generalization of the 2- and 3-dimensional spaces studied by Euclid. ... A sphere is a perfectly symmetrical geometrical object. ... Density (symbol: ρ - Greek: rho) is a measure of mass per unit of volume. ...

In 1998 Thomas Hales, presently Andrew Mellon Professor at the University of Pittsburgh, announced that he had a proof of the Kepler conjecture. Hales' proof is a proof by exhaustion 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 is now very close to becoming a theorem. 1998 (MCMXCVIII) was a common year starting on Thursday of the Gregorian calendar, and was designated the International Year of the Ocean. ... Thomas Callister Hales is an American mathematician who provided computer-aided proof of the Kepler Conjecture. ... Mellon portrait Andrew William Mellon (March 24, 1855–August 27, 1937) was an American banker, industrialist, philanthropist, and Secretary of the Treasury from March 4, 1921 until February 12, 1932. ... The University of Pittsburgh is a state-related, doctoral/research university in Pittsburgh, Pennsylvania. ... Proof by exhaustion, also known as the brute force method or case analysis, 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. ... A theorem is a proposition that has been or is to be proved on the basis of explicit assumptions. ...

Background

Imagine filling a large container with small equal-sized spheres. The density of the arrangement is the proportion of the volume of the container that is taken up by the spheres. In order to maximize the number of spheres in the container, you need to find an arrangement with the highest possible density, so that the spheres are packed together as closely as possible.

Experiment shows that dropping the spheres in randomly will achieve a density of around 65%. However, a higher density can be achieved by carefully arranging the spheres as follows. Start with a layer of spheres in a hexagonal lattice, then put the next layer of spheres in the lowest points you can find above the first layer, and so on - this is just the way you see oranges stacked in a shop. This natural method of stacking the spheres creates one of two similar patterns called cubic close packing and hexagonal close packing. Each of these two arrangements has an average density of

The Kepler conjecture says that this is the best that can be done - no other arrangement of spheres has a higher average density.

Origins

The conjecture is named after Johannes Kepler, who stated the conjecture in 1611 in Strena sue de nive sexangula (On the Six-Cornered Snowflake). Kepler had started to study arrangements of spheres as a result of his correspondence with the English mathematician and astronomer Thomas Harriot in 1606. Harriot was a friend and assistant of Sir Walter Raleigh, who had set Harriot the problem of determining how best to stack cannon balls on the decks of his ships. Harriot published a study of various stacking patterns in 1591, and went on to develop an early version of atomic theory. Johannes Kepler Johannes Kepler (December 27, 1571 – November 15, 1630), a key figure in the scientific revolution, was a German mathematician, astrologer, astronomer, and an early writer of science fiction stories. ... Events June 23 - Henry Hudsons crew maroons him, his son and 7 others in a boat November 1 - At Whitehall Palace in London, William Shakespeares romantic comedy The Tempest is presented for the first time. ... Royal motto (French): Dieu et mon droit (Translated: God and my [birth]right) Englands location (dark green) within the British Isles Languages English (de facto) Capital London de facto Largest city London Area – Total Ranked 1st UK 130,395 km² Population – Total (mid-2004) – Total (2001 Census) – Density Ranked... A mathematician is a person whose primary area of study and research is mathematics. ... An astronomer or astrophysicist is a scientist whose area of research is astronomy or astrophysics. ... Thomas Harriot (ca. ... Events January 27 - The trial of Guy Fawkes and other conspirators begins ending in their execution on January 31 May 17 - Supporters of Vasili Shusky invade the Kremlin and kill Premier Dmitri December 26 - Shakespeares King Lear performed in court Storm buries a village of St Ismails near... Alternatively, Professor Walter Raleigh was a scholar and author circa 1900. ... A small Civil War-era cannon on a carriage A cannon is any large tubular firearm designed to fire a heavy projectile over a considerable distance. ... Events June - Capture of Zutphen by the Dutch under Maurice of Nassau. ... In physics, atomic theory is a theory of the nature of matter. ...

Nineteenth century

Kepler did not have a proof of the conjecture, and the next step was taken by German mathematician Carl Friedrich Gauss, who published a partial solution in 1831. Gauss proved that the Kepler conjecture is true if the spheres have to be arranged in a regular lattice. (help· info) (30 April 1777 – 23 February 1855) was a German mathematician and scientist of profound genius who contributed significantly to many fields, including number theory, analysis, differential geometry, geodesy, magnetism, astronomy and optics. ... 1831 was a common year starting on Saturday (see link for calendar). ... See lattice for other meanings of this term, both within and without mathematics. ...

This meant that any packing arrangement that disproved the Kepler conjecture would have to be an irregular one. But eliminating all possible irregular arrangements is very difficult, and this is what made the Kepler conjecture so hard to prove. In fact, there are irregular arrangements that are denser than the cubic close packing arrangement over a small enough volume, but any attempt to extend these arrangements to fill a larger volume always reduces their density.

After Gauss, no further progress was made towards proving the Kepler conjecture in the nineteenth century. In 1900 David Hilbert included it in his list of twenty three unsolved problems of mathematics - it forms part of Hilbert's eighteenth problem. 1900 (MCM) was an exceptional common year starting on Monday. ... David Hilbert David Hilbert (January 23, 1862, Wehlau, Prussia–February 14, 1943, Göttingen, Germany) was a German mathematician, recognized as one of the most influential mathematicians of the 19th and early 20th centuries. ... Hilberts problems are a list of twenty-three problems in mathematics put forth by German mathematician David Hilbert at the Paris conference of the International Congress of Mathematicians in 1900. ... Hilberts eighteenth problem is one of the 23 Hilbert problems set out in a celebrated list compiled in 1900 by David Hilbert. ...

Twentieth century

The next step towards a solution was taken by Hungarian mathematician László Fejes Tóth. In 1953 Fejes Tóth showed that the problem of determining the maximum density of all arrangements (regular and irregular) could be reduced to a finite (but very large) number of calculations. This meant that a proof by exhaustion was, in principle, possible. As Fejes Tóth realised, a fast enough computer could turn this theoretical result into a practical approach to the problem. László Fejes Tóth (Szeged, 12 March 1915 – Budapest, 17 March 2005) is a Hungarian mathematician specializing in geometry, who proved that a honeycomb pattern is the most efficient way to pack equal circles in two dimensions. ... 1953 (MCMLIII) was a common year starting on Thursday (link is to a full 1953 calendar). ... In mathematics, a set is called finite if and only if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ...

Meanwhile, attempts were made to find an upper bound for the maximum density of any possible arrangement of spheres. English mathematician Claude Ambrose Rogers established an upper bound value of about 78% in 1958, and subsequent efforts by other mathematicians reduced this value slightly, but this was still a long way above the cubic close packing density of 74%. 1958 (MCMLVIII) was a common year starting on Wednesday of the Gregorian calendar. ...

There were also some failed proofs. American architect and geometer Buckminster Fuller claimed to have a proof in 1975, but this was soon found to be incorrect. In 1993 Wu-Yi-Hsiang at the University of California, Berkeley published a paper in which he claimed to prove the Kepler conjecture using geometric methods. Some experts countered, claiming he gave insufficient support for some of his claims. Although nothing incorrect per se was found in Hsiang's work, general consensus has been reached, concluding that Hsiang's proof is incomplete. One of the most vocal critics was Thomas Hales, who at the time was working on his own proof. Architect at his drawing board, 1893 An architect is a person involved in the planning, designing and oversight of a buildings construction. ... A geometer is a mathematician whose area of study is geometry. ... In the U.S. postage stamp commemorating Buckminster Fuller and his contributions to architecture and science, some of his inventions are visible. ... 1975 (MCMLXXV) was a common year starting on Wednesday (the link is to a full 1975 calendar). ... 1993 (MCMXCIII) was a common year starting on Friday of the Gregorian calendar and marked the Beginning of the International Decade to Combat Racism and Racial Discrimination (1993-2003). ... University of California, Berkeley The University of California, Berkeley (also known as California, Cal, UCB, UC Berkeley, The University of California, or simply Berkeley) is a public, coeducational university situated east of the San Francisco Bay in Berkeley, California, overlooking the Golden Gate. ...

Hales' proof

Following the approach suggested by Fejes Tóth, Thomas Hales, then at the University of Michigan, determined that the maximum density of all arrangements could be found by minimising a function with 150 variables. In 1992, assisted by his graduate student Samuel Ferguson, he embarked on a research programme to systematically apply linear programming methods to find a lower bound on the value of this function for each one of a set of over 5,000 different configurations of spheres. If a lower bound could be found for every one of these configurations that was greater than the value for the cubic close packing arrangement, then the Kepler conjecture would be proved. To find lower bounds for all cases involved solving around 100,000 linear programming problems. This article is about the University of Michigan in Ann Arbor. ... 1992 (MCMXCII) was a leap year starting on Wednesday. ... In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ...

When presenting the progress of his project in 1996, Hales said that the end was in sight, but it might take "a year or two" to complete. In August 1998 Hales announced that the proof was complete. At that stage it consisted of 250 pages of notes and 3 gigabytes of computer programs, data and results. 1996 (MCMXCVI) was a leap year starting on Monday of the Gregorian calendar, and was designated the International Year for the Eradication of Poverty. ... August is the eighth month of the year in the Gregorian Calendar and one of seven Gregorian months with the length of 31 days. ... 1998 (MCMXCVIII) was a common year starting on Thursday of the Gregorian calendar, and was designated the International Year of the Ocean. ... A gigabyte (derived from the SI prefix giga-) is a unit of information or computer storage equal to one billion bytes. ...

Despite the unusual nature of the proof, the editors of the Annals of Mathematics agreed to publish it, provided it was accepted by a panel of twelve referees. In 2003, after four years of work, the head of the referee's panel Gábor Fejes Tóth (son of László Fejes Tóth) reported that the panel were "99% certain" of the correctness of the proof, but they could not certify the correctness of all of the computer calculations. 2003 (MMIII) was a common year starting on Wednesday of the Gregorian calendar. ...

In February 2003 Hales published a 100-page paper describing the non-computer part of his proof in detail. Look up February in Wiktionary, the free dictionary February is the second month of the year in the Gregorian Calendar. ... 2003 (MMIII) was a common year starting on Wednesday of the Gregorian calendar. ...

The Annals of Mathematics is going ahead with publishing the theoretical portions of Hales' proof. The computational portions will be published in a separate journal, Discrete and Computational Geometry.

A formal proof

In January 2003 Hales announced the start of a collaborative project to produce a complete formal proof of the Kepler conjecture. The aim is to remove any remaining uncertainty about the validity of the proof by creating a formal proof that can be verified by automated theorem proving software such as HOL. This project is called Project FlysPecK - the F, P and K standing for Formal Proof of Kepler. Hales estimates that producing a complete formal proof will take around 20 years of work. 2003 (MMIII) was a common year starting on Wednesday of the Gregorian calendar. ... Automated theorem proving (currently the most important subfield of automated reasoning) is the proving of mathematical theorems by a computer program. ... The various HOL (which stands for Higher Order Logic) systems are a family of interactive theorem proving systems sharing similar logics and implementation strategies. ...

References

• G.G. Szpiro (2003) Kepler's Conjecture Wiley, John & Sons Inc. ISBN 0471086010
• Thomas C. Hales (2003) [1] A Proof of the Kepler Conjecture
• T. Aste and D. Weaire "The Pursuit of Perfect Packing" (Institute Of Physics Publishing London 2000) ISBN 0750306483

External links

• Thomas Hales' home page
• Overview of Hales' proof
• Article in American Scientist by Dana Mackenzie