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: Christmas cracker pulling: How to send everyone home a winner

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

CMU professor honored for computational complexity breakthrough

May 21, 2007

Computer scientists at Carnegie Mellon University and the Russian Academy of Science will share the Association for Computing Machinery's 2007 Gödel Prize for their seminal work on what many consider the most important unresolved ...

Recommended for you

Consumer loyalty driven by aesthetics over functionality

10 hours ago

When designing a new car, manufacturers might try to attract consumers with more horsepower, increased fuel efficiency or a lower price point. But new research from San Francisco State University shows consumers' loyalty ...

Short-necked Triassic marine reptile discovered in China

12 hours ago

A new species of short-necked marine reptile from the Triassic period has been discovered in China, according to a study published December 17, 2014 in the open-access journal PLOS ONE by Xiao-hong Chen f ...

Study: Alcatraz inmates could have survived escape

12 hours ago

The three prisoners who escaped from Alcatraz in one of the most famous and elaborate prison breaks in U.S. history could have survived and made it to land, scientists concluded in a recent study.

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.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.