Experimental mathematics leading to major advances

Question

I would like to ask about examples where experimentation by computers has led to major mathematical advances.

A new look

Now as the question is five years old and there are certainly more examples of mathematical advances via computer experimentation of various kinds, I propose to consider contributing new answers to the question.

Motivation

I am aware about a few such cases and I think it will be useful to gather such examples together. I am partially motivated by the recent polymath5 which, at this stage, have become an interesting experimental mathematics project. So I am especially interested in examples of successful "mathematical data mining"; and cases which are close in spirit to the experimental nature of polymath5. My experience is that it can be, at times, very difficult to draw useful insights from computer data.

Summary of answers according to categories

(Added Oct. 12, 2015)

To make the question a useful resource (and to allow additional answers), here is a quick summery of the answers according to categories. (Links are to the answers, and occasionally to an external link from the answer itself.)

1) Mathematical conjectures or large body of work arrived at by examining experimental data - Classic

The Prime Number Theorem; Birch and Swinnerton-Dyer conjectures; Shimura-Taniyama-Weil conjecture; Zagier's conjectures on polylogarithms; Mandelbrot set; Gosper Glider Gun (answer), Lorenz attractor; Chebyshev's bias (answer) ; the Riemann hypothesis; the discovery of the Feigenbaum constant; (related) Feigenbaum-Coullet-Tresser universality and Milnor's Hairiness conjecture; Solving numerically the so-called Fermi--Pasta--Ulam chain and then of its continuous limit, the Korteweg--de Vries equation

2) Mathematical conjectures or large body of work arrived at by examining experimental data - Current

"Maeda conjecture"; the work of Candès and Tao on compressed sensing; Certain Hankel determinants; Weari-Phelan structure; the connection of multiple zeta values to renormalized Feynman integrals; Thistlethwaite's discovery of links with trivial Jones polynomial; The Monstrous Moonshine; McKay's account on experimentation leading to mysterious "numerology" regarding the monster. (link to the answer); Haiman conjectures on the quotient ring by diagonal invariants

3) Computer-assisted proofs of mathematical theorems

Kepler's conjecture ; a new way to tile the plane with a pentagon: advances regarding bounded gaps between primes following Zhang's proof; Cartwright and Steger's work on fake projective planes; the Seifert-Weber dodecahedral space is not Haken; the four color theorem, the proof of the nonexistence of a projective plane of order 10; Knuth's work on a class of projective planes; The search for Mersenne primes; Rich Schwartz's work; The computations done by the 'Atlas of Lie groups' software of Adams, Vogan, du Cloux and many other; Cohn-Kumar proof for the densest lattice pacing in 24-dim; Kelvin's conjecture; (NEW) $R(5,5) \le 48$ and $R(4,5)=25$;

4) Computer programs that interactively or automatically lead to mathematical conjectures.

Graffiti

5) Various computer programs which allow proving automatically theorems or generating automatically proofs in a specialized field.

Wilf-Zeilberger formalism and software; FLAGTOOLS

6) Computer programs (both general purpose and special purpose) for verification of mathematical proofs.

The verification of a proof of Kepler's conjecture.

7) Large databases and other tools

Sloane's online encyclopedia for integers sequences; the inverse symbolic calculator.

8) Resources:

Journal of experimental mathematics; Herb Wilf's article: Mathematics, an experimental science in the Princeton Companion to Mathematics, genetic programming applications a fairly comprehensive website experimentalmath.info ; discovery and experimentation in number theory; Doron Zeilberger's classes called "experimental mathematics":math.rutgers.edu/~zeilberg/teaching.html; V.I. Arnol'd's two books on the subject of experimental mathematics in Russian, Experimental mathematics, Fazis, Moscow, 2005, and Experimental observation of mathematical facts, MCCME, Moscow, 2006

Answers with general look on experimental mathematics:

Computer experiments allow new avenues for productive strengthening of a problem (A category of experimental mathematics).

---

Bounty:

There were many excellent answers so let's give the bounty to Gauss...

Related question: Where have you used computer programming in your career as an (applied/pure) mathematician?, What could be some potentially useful mathematical databases? Results that are easy to prove with a computer, but hard to prove by hand ; What advantage humans have over computers in mathematics? Conceptual insights and inspirations from experimental and computational mathematics

Answer 1

The Shimura-Taniyama-Weil conjecture (now a theorem) and the Birch and Swinnerton-Dyer conjectures were based on examples.

Answer 2

A direct search on CDC 6600 led to a ctrx counterexample for a conjecture of Euler. Following an answer by Will Brian to a question about tweetable mathematics.

Answer 3

In a remarkable article from 1989, "Self-similarity and hairiness in the Mandelbrot set", Milnor formulates a number of conjectures (related to Feigenbaum universality). Citing Lisa Goldberg and Tony Phillips in the preface to Topological Methods in Modern Mathematics (Milnor's 60th birthday Festschrift, 1993),

OF special note is an unconventional article entitled Self-similarity and hairiness in the Mandelbrot set, where he presents some of his numerical experiments in holomorphic dynamics and uses them as evidence for a set of conjectures. ... The resulting data are so compelling as to suggest not only what the conjectures should say, but how they can be proved.

Lyubich later proved some of these conjectures in a groundbreaking article (Feigenbaum-Coullet-Tresser universality and Milnor's Hairiness conjecture, Annals of Mathematics, 1999), which also, for the first time, gave a conceptual proof of the Feigenbaum scaling law.

Answer 4

Graffiti is a computer program which makes conjectures in various subfields of mathematics, particularly graph theory. (And also in chemistry.) It was written by written by Siemion Fajtlowicz. Here is a 1989 article about it.

Answer 5

Recently Burton, Rubinstein and Tillmann proved the conjecture that the Seifert-Weber dodecahedral space is not Haken.

https://arxiv.org/abs/0909.4625

Quite a bit of experimentation led up to their algorithms, as you would see by reading their paper.

Answer 6

I think there may be an additional category, though relatively little-known outside my own field (design automation): genetic programming applications, or more generally the application of metaheuristics. Spector et al's "Genetic Programming for Finite Algebras" (2008) is a good example of the methodology, which seems to me to be much less about the automation of proof as such, and more about enhancing mathematicians' capacity for well-defined combinatorial searches.

That said, you may want to include it, and the growing number of other GP papers in this domain, in your survey categories under (4) or (5).

Answer 7

Computer experiments are necessary in order to understand the classical Laver tables and related structures. In fact, Randall Dougherty developed the most efficient algorithm for computing the classical Laver tables as a direct result of computer calculations (here is a case of experimental mathematics leading to more experimental mathematics).

Recall that the classical Laver table $A_{n}$ is the unique structure $(\{1,\ldots,2^{n}\},*_{n})$ such that $x*_{n}(y*_{n}z)=(x*_{n}y)*_{n}(x*_{n}z)$ and $x*_{n}1=x+1\mod 2^{n}$ whenever $x,y,z\in\{1,\ldots,2^{n}\}.$

Let me quote Dougherty in this paper concerning Theorem 4.1 from which Dougherty's algorithm is based.

The history of this result is interesting. Weaker versions of it, formulated in terms of critical points and embeddings in $\mathcal{A}_{j}$, were conjectured as early as 1986, before the finite algebras $A_{n}$ had been discovered; but attempts to prove these results by induction were not successful. Much later, computer experiments displaying bit patterns occurring in period sequences in $B_{\infty}$ related to these conjectures led to the statement of the stronger theorem.

From the corollaries of Theorem 4.1, Dougherty developed an algorithm for computing the Laver table $A_{48}$. Dougherty's algorithm for computing $A_{48}$ relies on a look-up table consisting of all values $x*_{48}y$ where $x\leq 2^{16}$. This look-up table takes about 2.5 megabytes and it took my computer about 10 minutes for my computer to calculate this look-up table. Once this look-up table is created, my computer has been able to calculate about 57000 random values for $x*_{48}y$ a second. As I have mentioned in other places, using Dougherty's algorithm and good data compression, I suspect that it is currently possible to compute up to $A_{96}$ using a compressed look-up table much less than a gigabyte. When one uses a basic algorithm instead of Dougherty's algorithm, a modern computer is only able to compute about $A_{28}$ or so before running out of memory.

I personally have used the technique behind Dougherty's algorithm to make my own algorithms for quickly computing in generalizations of Laver tables.

See this question for further discussions.

Answer 8

There's also a fairly comprehensive website experimentalmath.info where, I guess, some further examples of EM in action can be found.

Answer 9

Weaire-Phelan structure provides a counterexample to Kelvin's conjecture that the minimal area partition of space is realized by an appropriately curved bitruncated cubic honeycomb tesselation. It was discovered by computer simulations of foam in 1993. The problem of finding the minimizing partition is still open, but nowadays you can easily toy with it yourself using Surface Evolver. Who knows, maybe you will discover a better solution!

Answer 10

The results on Chebyshev's bias is a great example. Chebyshev in 1853 noted that primes congruent to 3 modulo 4 seem to predominate over those congruent to 1. This is called Chebyshev's bias. Littlewood proved in 1914 that this bias exists and also that it gets violated infinitely often, if you go far enough. The distance to be covered for the violation seemed to grow rapidly with each step.

Rubinstein and Sarnak proved in 1994 that the violations have nonzero density. Here the density means the "logarithmic density", as defined in that paper.

This was a quite interesting result guided at each step from considerations of experimental mathematics and computation. For more information have a look at the Rubinstein-Sarnak paper.

Answer 11

First, a brief story, then the punchline.

Elsewhere I mention a series of 0-1 matrices used for a combinatorial matrix result. This came about because of an aspiring undergraduate (Roger House) who was using a computer to search for 0-1 matrices of certain orders and determinant values.

He showed me a printout where he listed the first representative of each class (major key order, minor key absolute determinant value). He chose a lexicographical ordering of class members to pick this representative: this choice revealed a set of matrices with few differing entries, and those in just the first two or three columns. I would not blame someone else for saying it was a pattern screaming to be found.

Many a time since then, I think about how to organize computer-generated data (specifically, pick an explanatory set of representatives) that reveal patterns and structure. I think that experimental mathematics should not just include results, or even data analysis techniques, but heuristics on "how to make choices" so that patterns of note jump to the human eye. In the case above, lexicographic order was a choice made by one person that revealed a pattern of similarity to another person.

Gerhard "At Least, Raise Their Voices" Paseman, 2015.10.12

Answer 12

In some simple cases it is even possible to both guess some results and prove them too experimentally. I have done this with some Hankel determinants. Suppose you want to compute the Hankel determinant $\det \left( {a_{i + j} } \right)_{i,j = 0}^{n - 1} $ of a sequence $(a_n )$ . If no Hankel determinant vanishes then you can compute polynomials $p_n (x)$ which are orthogonal with respect to the linear functional $F$ on the polynomials defined by $F(x^n ) = a_n .$ By Favard's theorem there exist numbers $s_n ,t_n $ such that $p_{n + 2} (x) = (x - s_{n + 1} )p_{n + 1} (x) - t_n p_n (x).$ In some cases it is easy to guess a formula for these numbers after computing some of them. Thus also the Hankel determinant can be computed. In order to show that this guess gives the correct answer we can do the following: Define $a(n,j) = a(n - 1,j - 1) + s_j a(n - 1,j) + t_j a(n - 1,j + 1)$ with $a(0,j) = \delta _{j,0} .$ By the underlying theory it suffices to show that $a(n,0) = a_n .$ In order to do this we again compute $a(n,j)$ for small values and try to guess a closed formula for them. In many cases we succeed. Then it suffices to verify that $a(n,j) = a(n - 1,j - 1) + s_j a(n - 1,j) + t_j a(n - 1,j + 1)$ holds for the conjectured formula.

Answer 13

I think that Zagier's conjectures on polylogarithms were based on considerable amount of numerical evidence (this has led to impressive work by Beilinson-Deligne, Goncharov...).

Serre's conjecture on modularity of mod $p$ $2$-dimensional Galois representations was also made precise thanks to simultaneous theoretical advances and numerical computations (this has paved the way to the proof of Fermat's last theorem...).

To come back to the prime number theorem, I think that Euler already "proved" it long before Gauss conjectured it by differentiating $\sum_{p\leq x}\frac{1}{p}\sim \log\log x$.

Answer 14

$R(5,5) \le 48$

Is a title of a remarkable recent paper by Vigleik Angeltveit and Brendan D. McKay. More than 20 years ago McKay and Radziszowski proved that $R(5,5) \le 49$ and in this paper they showed that $R(4,5)=25$.

Answer 15

In March 2019, Andrew Booker in the paper Cracking the problem with 33 showed that 33 is a sum of 3 cubes in $\mathbf Z$. This is a striking example of a case where checking the solution is very easy while finding it is hard. Indeed Booker showed that $$33=8866128975287528^3+(-8778405442862239)^3+(-2736111468807040)^3.$$

The paper describes the algorithm and its implementation and concludes with "The total computation used approximately 15 core-years over three weeks of real time."

Update 2019-09-12: A team led by mathematicians from the University of Bristol and Massachusetts Institute of Technology proved that $$(−80538738812075974)^3+80435758145817515^3+12602123297335631^3=42.$$

Answer 16

In 2003 Cohn and Elkies devised linear programming upper bounds for the density of optimal sphere packings in Euclidean space. They observed that by optimizing over functions in the bound it seemed one could get arbitrarily close to the densities achieved by the conjecturally optimal $\text{E}_8$ and Leech lattice in dimensions $d=8$ and $d=24$ (this appears true for $d=2$ also, where the hexagonal lattice is well-known to be optimal). This served as a promising method of solving the conjecture in these dimensions, but optimizing functions were hard to pin down.

In 2016 Viazovska explained this mystery (proving optimality of the $\text{E}_8$ lattice) by constructing a suitable function for the linear programming problem, and within the week, the argument was generalized to $24$ dimensions by Cohn, Kumar, Miller, Radchenko, and Viazovska.

Answer 17

The Robbins conjecture from 1933, asked whether two sets of Boolean algebras were equivalent. The solution has been found only in 1996 by William McCune, using the automated theorem prover EQP.

Answer 18

Hida and Maeda's article "Non-abelian base change for totally real fields" in the pacific journal of mathematics, volume 181(3) in 1997 explains how the experimental data lead to the "Maeda conjecture" (which you'll find mentioned in a few questions on MO).

Answer 19

Boolean Pythagorean triples Theorem (Heule, Kullmann, Oliver 2015) — The set $\{1, \dots , 7824\}$ can be partitioned into two parts, such that no part contains a Pythagorean triple, while this is impossible for $\{1, . . . , 7825\}$.

See Wikipedia. The proof uses heavy computation. See this Nature article.

Answer 20

There is a 1982 book by Ulf Grenander: "Mathematical experiments on the computer", Academic Press. He advices to use APL as programming language. While the practical computing advice and software part of the book might be obsolete, it has many examples from various fields. This examples could maybe be used in a course.

The list of examples are:

1. From statistics
2. From linear algebra
3. An energy minimization problem
4. Neural networks (static problem)
5. Limit theorems on groups
6. Pattern restoration
7. Modeling language acquisition
8. Study of invariant curves
9. Neural networks (dynamic problem)
10. High-dimensional geometry
11. Strategy of proofs.

Answer 21

Another famous example is Harald Helfgott's 2013 proof that every odd integers greater than five is the sum of three primes. "The ternary Goldbach conjecture is true". arXiv:1312.774

Answer 22

I submit for the third criterion Lewin's work on polylogarithm ladders, which culminates into a paper by Zagier, Lewin, Cohen using numerical evidence and (a desire for) an algorithm to compute relations (p. 6).