Interesting conjectures "discovered" by computers and proved by humans? - MathOverflow

Interesting conjectures "discovered" by computers and proved by humans?

2012-03-25T09:26:33Z

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.

Answer by Marco Caminati for Interesting conjectures "discovered" by computers and proved by humans?

2012-03-25T09:55:47Z

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

Answer by Cristi Stoica for Interesting conjectures "discovered" by computers and proved by humans?

2012-03-25T10:15:05Z

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".

Answer by Ralph for Interesting conjectures "discovered" by computers and proved by humans?

2012-03-25T11:44:16Z

I agree with the preceding answers that a computer seldom says "I conjecture ... but I can't prove it". But there a results found by computers that were later on proved by humans to have some particular property or that were generalized by humans:

McCune found with help of a computer the single-axiom in products and inverses for groups:

$$ x \cdot (y \cdot (((z \cdot z^{-1})\cdot (u \cdot y)^{-1}) \cdot x))^{-1} = u$$

Later it was proved by Kunen (by hand and with computer) that there is no shorter axiom in terms of products and inverses. More on this can be found in the paper.

Similarly, Kunen and Hart showed that $$f_m(x,f_m(x,(x \cdot y)\cdot z)\cdot g_m(z)) = y$$ is a single-axiom for groups of exponent $2m+1$ where $f_m(x,y) = x(x(...(xy)...))$ and $g_m(z) = z \cdot (\cdots (z\cdot z)...)$. For small $m$ the formulas where found and proved by a computer and by analyzing the computer's proof, the general result was obtained and proved by humans.

Answer by Gerald Edgar for Interesting conjectures "discovered" by computers and proved by humans?

2012-03-25T13:09:12Z

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.

Answer by Denis Serre for Interesting conjectures "discovered" by computers and proved by humans?

2012-03-25T14:09:01Z

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.

Answer by Péter Komjáth for Interesting conjectures "discovered" by computers and proved by humans?

2012-03-25T14:32:55Z

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.

Answer by alvarezpaiva for Interesting conjectures "discovered" by computers and proved by humans?

2012-03-25T18:09:13Z

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.

Answer by Piero D'Ancona for Interesting conjectures "discovered" by computers and proved by humans?

2012-03-25T18:28:52Z

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.

Answer by Kristal Cantwell for Interesting conjectures "discovered" by computers and proved by humans?

2012-03-25T18:37:07Z

There is a related question on experimental mathematics here.

Answer by Gerald Edgar for Interesting conjectures "discovered" by computers and proved by humans?

2012-03-25T19:07:39Z

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.

Answer by Nathan Clisby for Interesting conjectures "discovered" by computers and proved by humans?

2012-03-25T22:03:55Z

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.

Answer by Camilo Sarmiento for Interesting conjectures "discovered" by computers and proved by humans?

2012-03-26T12:56:20Z

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. "