A solution that counts: Long-standing mathematical conjecture finally proved

Jan 25, 2011
Totally symmetric plane partitions posed for many years riddles for mathematicians. The last one has now been solved by a computer.

(PhysOrg.com) -- A conjecture presented in 1985 – the Andrews and Robbins conjecture – has recently been proved for the first time. It is thus clear that the structure which goes by the name of "totally symmetric plane partitions" can be described using a single formula. Producing the proof required vast computer resources and was only possible after the formula had been prepared for computer-assisted calculation. This finding by a Austrian Science Fund FWF supported research group based in Linz, Austria will be published in the Proceedings of the National Academy of Sciences today. The proof means that the last of a long list of famous mathematical conjectures relating to plane partitions has finally been proved.

Even mathematicians play with building blocks. At least if they are interested in so-called plane partitions, which are visualized with columns of "building blocks" (cubes) on a surface resembling a chessboard. When "building" such plane partitions, the mathematicians must adhere to certain rules: No column may be higher than the width of the surface, or than another column behind it or left of it. The question of how many column permutations may be built on a given surface area is easily answered, thanks to a specific formula. However, it becomes trickier if the permutations must follow stipulated symmetries, or if, instead of counting the permutations, you wish to count its constituents. Although formulas have been designed to do this too, the crux of the matter is that not all of these formulas have really been proved to be accurate. It is only conjectured.

The Proof Is In The Computer

The proof that one of these formulas is correct has now been found by Dr. Christoph Koutschan and Dr. Manuel Kauers from the Research Institute for Symbolic Computation of the Johannes Kepler University Linz, Austria, in cooperation with Prof. Doron Zeilberger from the United States. It is a formula that is employed for calculating the individual components in totally symmetric plane partitions. Dr. Koutschan comments on the special method they used to find the proof: "We let the computer do the work! In some areas of mathematics this has long been a matter of routine." The underlying principle of such computer-assisted proof is simple. In order to prove A=B, the computer calculates an adjoint equation U=V with the following two properties: "If U=V is true, then A=B is also true" and "it is easy to verify that U=V".

Although it may sound easy, it represents a great challenge, according to Dr. Koutschan: "This method does not work for every equation. The most important step was for us to convert the Andrews-Robbins conjecture into a suitable form for the computer to be able to prove it." The fact that the adjoint equation was really somewhat more complex than "U=V", is illustrated by its size: if it were printed, it would cover approximately 1 million A4 pages, which makes it probably the longest equation ever used in a mathematical proof.

Stanley’s List

In the end, the work that was spent on the "formulation" was well worth it. With the proof of the Andrews and Robbins conjecture, the scientists have managed to prove the last of a number of famous conjectures, which were presented by US mathematician Richard Stanley at a historic conference in Montreal in 1985. In the years following the conference, all of these conjectures were proved – except for the Andrews and Robbins conjecture. Dr. Kauers comments: "As the last remaining item on Stanley’s list, this conjecture attracted the attention of many experts. Still, it remained unproved for almost thirty years. The proof was finally obtained with an automatic method, which goes to show that modern computer programs can crack mathematical problems where traditional mathematicians fall short."

Granted, such successful results are still an exception. However, this FWF project underscores the potential of computer-based proof. Given the great pace at which computer performance is advancing, such methods will perhaps one day even offer answers to the great unsolved questions in mathematics.

Explore further: Researchers help Boston Marathon organizers plan for 2014 race

More information: A proof of George Andrews’ and David Robbins’ q-TSPP conjecture. C. Koutschan, M. Kauers D. Zeilberger. DOI:10.1073/pnas.1019186108

Provided by Austrian Science Fund

4.5 /5 (13 votes)

Related Stories

Computer scientists make progress on math puzzle

Oct 28, 2010

(PhysOrg.com) -- Two UT Dallas computer scientists have made progress on a nearly 4-decade-old mathematical puzzle, producing a proof that renowned Stanford computer scientist Don Knuth called "amazing" in his communication ...

New math theories reveal the nature of numbers

Jan 20, 2011

For centuries, some of the greatest names in math have tried to make sense of partition numbers, the basis for adding and counting. Many mathematicians added major pieces to the puzzle, but all of them fell ...

Recommended for you

Performance measures for CEOs vary greatly, study finds

2 hours ago

As companies file their annual proxy statements with the U.S. Securities and Exchange Commission (SEC) this spring, a new study by Rice University and Cornell University shows just how S&P 500 companies have ...

User comments : 6

Adjust slider to filter visible comments by rank

Display comments: newest first

Kedas
2.4 / 5 (5) Jan 25, 2011
Is this just math for the math or does it represent something?
that_guy
1 / 5 (1) Jan 25, 2011
I knew they would do it eventually. This opens up so many fields in spacial design and circuit partitioning...and...

Yeah, I have a feeling that the people who are interested and fully comprehend any ramifications of this article are not the type to comment. I admit I couldn't get myself to read past the second paragraph.
dinkster
1 / 5 (1) Jan 26, 2011
Some smart people will find some application in quantum topology or some such stuff. This is good, as hard as it is to grasp.
that_guy
3 / 5 (2) Jan 26, 2011
Some smart people will find some application in quantum topology or some such stuff. This is good, as hard as it is to grasp.


Quantum topology you say? This has absolutely nothing to do with quantum topology. Stop stroking yourself. It's a simple surface area type problem that is difficult to prove, and likely has applications in far more "mundane" fields of study...like packing objects...

Utterly dry doesn't make it obfuscate.
dinkster
not rated yet Jan 26, 2011
Some smart people will find some application in quantum topology or some such stuff. This is good, as hard as it is to grasp.


Quantum topology you say? This has absolutely nothing to do with quantum topology. Stop stroking yourself. It's a simple surface area type problem that is difficult to prove, and likely has applications in far more "mundane" fields of study...like packing objects...

Utterly dry doesn't make it obfuscate.


For a post that, by your definition, is equally elitist, you fail to address the obvious leaps and sum it all up as "stacking boxes." Thanks for the pretentious use of a thesaurus.
that_guy
1 / 5 (1) Jan 28, 2011
For a post that, by your definition, is equally elitist, you fail to address the obvious leaps and sum it all up as "stacking boxes." Thanks for the pretentious use of a thesaurus.

I'm merely yelling at you for making a connection that was not there, trying to use 'quantum topology'. The only connection this concept has to what you're saying is "Topology". And judging that it works under the rules of classical geometry, it doesn't necessarily apply to the quantum world.

I wasn't calling you elitist, I was saying that you are stretching to sound smart.

More news stories

How kids' brain structures grow as memory develops

Our ability to store memories improves during childhood, associated with structural changes in the hippocampus and its connections with prefrontal and parietal cortices. New research from UC Davis is exploring ...

Gate for bacterial toxins found

Prof. Dr. Dr. Klaus Aktories and Dr. Panagiotis Papatheodorou from the Institute of Experimental and Clinical Pharmacology and Toxicology of the University of Freiburg have discovered the receptor responsible ...