# Interesting conjectures “discovered” by computers and proved by humans?

There are notable examples of computers "proving" results discovered by mathematicians, what about the opposite:

Are there interesting conjectures "discovered" by computers and proved by humans?

Possible example in graph theory is "Some Conjectures of Graffiti.pc (2004-07)," suggested by Joseph O'Rourke in another answer.

The question might not be well defined because "discovered" is controversial.

Added This question may be a duplicate (or refinement) of (2) in Experimental Mathematics as Kristal Cantwell pointed out.

I am mainly interested in examples where the program is designed to make conjectures which are not known identities to the program and later proved.

-
A related MO question: mathoverflow.net/questions/28651/… – Andrey Rekalo Mar 25 '12 at 11:44
Several of the 26 finite sporadic simple groups were first constructed on computer, and only later proved to exist with a help of computer. Does this qualify? – Dima Pasechnik Mar 25 '12 at 13:48
oops, I meant "proved to exist withOUT a help of computer" – Dima Pasechnik Mar 25 '12 at 14:08
@Dima sure, this is interesting. The question is community wiki anyway. – joro Mar 25 '12 at 14:15
It might be more revealing to talk about how presentation of data leads to insight. The result mentioned here mathoverflow.net/questions/11885/… occurred because the program Roger wrote displayed results in a certain lexicographic order. Since then I have often wondered on automated ways of rearranging and displaying data to allow conjectures to be formed. Gerhard "Ask Me About System Design" Paseman, 2012.03.25 – Gerhard Paseman Mar 26 '12 at 0:59

In Automated conjecture making in number theory using HR, Otter and Maple, the HR program discovered the following conjecture:

"Paraphrased,... if you take an integer and add up the divisors, then if the result is a prime, the number of divisors you have just added up will also be prime"

And formally:

all a (isprime(sigma(a)) -> isprime(tau(a)))

Where sigma(a) and tau(a) are the sum of the divisors of a, and the number of divisors of a, respectively.

They then proved that this conjecture is true. To me this seems very interesting and non-obvious. But I have no idea if this theorem is significant, or if it was totally unknown before this program discovered it.

-
Even if not obvious, this is quite a simple theorem: since $\sigma(n)$ is multiplicative, $n$ must be a prime power $p^k$ and $\sigma(p^k)=(p^{k+1}-1)/(p-1)$. If $\tau(p^k)=k+1$ had a nontrivial divisor $m$, then $\sigma(p^k)$ would have a nontrivial divisor $(p^m-1)/(p-1)$. – Wojowu 19 hours ago
I think it's not that interesting if you understand multiplicative functions. – Douglas Zare 19 hours ago

No one has mentioned the case of commutative algebra. The appearance of computer algebra systems allowed researchers in commutative algebra and/or algebraic geometry to generate lots of examples which then lead to conjectures, later proved by hand. Look at this quote from Eisenbud's home page, for instance:

"Ever since the early 70s I've used computers to produce examples in algebraic geometry and commutative algebra, and I've developed algorithms to extend the power of computation in this area. I recently joined Mike Stillman and Dan Grayson in the project to (further) develop the Macaulay2 system for symbolic computation. "

-
Interesting. To what extent generation of conjectures is automated? – joro Mar 26 '12 at 13:21
Ok, maybe this doesn't correspond exactly to what you wrote in the last gray box. It is to a rather primitive extent, since there should be some conjecture already. Then examples may be generated (which would be too lengthy/tedious to compute by hand) that could support or refute the conjecture. – Camilo Sarmiento Mar 26 '12 at 14:41

In our paper The numerical measure of a complex matrix (Comm. Pure and Appl. Math. ,65 (2012), pp 287--336), T. Gallay and I proved that the restriction to some zones of the numerical density of an $n\times n$ matrix is polynomial of degree at most $n-3$. The only reason why we were led to this result is because of numerical experiments shown some evidence. Does it qualify ?

Later on, we found that this polynomiality is related to the so-called lacunas for hyperbolic differential operators.

-
Sure, thank you Denis Serre – joro Mar 25 '12 at 14:14

Much of the early work on the Mandelbrot set was of this type. You see something strange in the computer images, then you try to prove that it really happens.

Here is one example: Pi and the Mandelbrot set. From conjecture in 1991 to paper in 2001.

-

One problem that perhaps fits in this category is the exact solution of the hard hexagon model by Rodney Baxter. In this case computer calculations revealed surprising patterns which suggested that the model was solvable, but it required someone like Rodney Baxter to first recognise these patterns, and then go ahead and find the solution. A large grey area in the nature of the question is the extent to which the computer "discovered" the solution.

This discovery is described in Ch. 14 of Rodney Baxter's book "Exactly Solved Models in Statistical Mechanics".

There must be other examples of computer discoveries in the field of solvable models in statistical mechanics, as to some extent this is the nature of field. However, to me this example stands out, as to the best of my knowledge there was no a priori expectation that the model was solvable before the computer calculations were performed.

-

About 1960 Ed Lorenz observed the "sensitive dependence on initial conditions" in a very simple weather model he was running on a computer. He later coined the term "butterfly effect" for this phenomenon.

-

There is a related question on experimental mathematics here.

-
Thank you, haven't seen this question. This one may be a duplicate/refinement of 2). – joro Mar 26 '12 at 5:54

The starting point of the mathematical theory of solitons for the Korteweg-de Vries equation was the numerical experiment of Kruskal and Zabusky in 1965, showing that solitons of different amplitudes, hence traveling at different speeds, crossed each other and reemerged (almost) undisturbed. I think this is an appropriate example in this thread, since this is an actual new phenomenon, totally unespected, discovered by computer simulation, then rigorously proved and widely generalized to constitute a whole new mathematical theory.

-

This is not precisely a conjecture, but the Fermi-Pasta-Ulam experiment seems to be the first time mathematicians and physicists realized that lack of integrals of motion does not necessarily lead to chaos or ergodicity, thus paving the way for KAM theory.

-

Lovasz told me the following interesting story. He had read a paper containing a long list of computer generated conjectures, did not like most them, but suddenly found one, which turned out to be an interesting and deep question. Then he realized that the same question had been asked earlier by humans. See http://oldwww.cs.elte.hu/~lovasz/berlin.pdf.

-
The story is on pages 7-8 and footnote 2 of the paper? – joro Mar 25 '12 at 14:53
Yes, exactly that one. – Péter Komjáth Mar 26 '12 at 5:23

I agree that it may be difficult to program a computer to find conjectures which it can't then prove, but can then be proven by humans. Much easier seems to be to find and prove theorems, or to search for counterexamples to conjectures.

That's why I am thinking at another possibility: explore mathematical constructions using computer programs, and from the observed patterns and regularities, suggest conjectures. So, not the program will be the one which suggest the conjecture, but he human user. Exploring mathematical constructions is done in experimental mathematics. On this Wikipedia page there are some examples of patterns observed when using numerical and graphical simulations, under the titles "Finding serendipitous numerical patterns" and "Visual investigations".

-

You seem to be asking about computers formulating conjectures later proved by humans. As one not having had much exposure to the issue, I wonder how to teach a computer (maybe with some form of heuristics?) assessing it has found a plausible conjecture: in this case computer misses the comfort of knowing a result is true for it has proven it's true, while human mathematicians can use instinct or some kind of common sense. However, I found this:

A Symbolic Finite-State Approach For Automated Proving of Theorems in Combinatorial Game Theory

-
Thanks. I edited the question asking about conjectures. – joro Mar 25 '12 at 10:06