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

##### January 25, 2011

(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: Computer scientists make progress on math puzzle

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

## Related Stories

#### Computer scientists make progress on math puzzle

October 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

January 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 short of a full ...

#### Doubts continue on claim to have solved P vs NP mathematical question

August 17, 2010

One of the most complex mathematical problems in the world is proving either that P ≠ NP or P=NP, a riddle that was first formulated in 1971 by mathematicians Leonid Levin and Stephen Cook. The question was one of seven ...

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

#### Simple beauties of math: Harvard professor views nature itself through geometry's clear lens

October 4, 2010

Shing-Tung Yau sees a beautiful universe around him, crafted by nature into the shapes and forms we see every day. Mathematics describes those shapes and forms, the discipline of geometry in particular. So, to Yau, it shares ...

#### A trillion triangles: New computer methods reveal secrets of ancient math problem

September 22, 2009

Mathematicians from North America, Europe, Australia, and South America have resolved the first one trillion cases of an ancient mathematics problem. The advance was made possible by a clever technique for multiplying large ...

## Recommended for you

#### Money can buy happiness but it's costly to bank on that without measuring debt

October 26, 2016

Yes, money can lead to happiness, but how much debt one has should also be considered in the money-happiness equation, according to a new a study from Purdue University.

#### Upper Paleolithic humans may have hunted cave lions for their pelts

October 26, 2016

Upper Paleolithic humans may have hunted cave lions for their pelts, perhaps contributing to their extinction, according to a study published October 26, 2016 in the open-access journal PLOS ONE by Marián Cueto from the ...

#### Ancient parrot fossil found in Siberia

October 26, 2016

(Phys.org)—A Russian paleontologist has discovered a parrot fossil uncovered in Siberia several years ago—the first evidence of parrots living in Asia. In his paper published in Biology Letters, Nikita Zelenkov describes ...

#### Ancient burials suggestive of blood feuds

October 24, 2016

There is significant variation in how different cultures over time have dealt with the dead. Yet, at a very basic level, funerals in the Sonoran Desert thousands of years ago were similar to what they are today. Bodies of ...

#### Dinosaurs of a feather flock and die together?

October 24, 2016

In the paleontology popularity contest, studying the social life of dinosaurs is on the rise.

#### Model helps explore how changing certainty in belief of one statement can lead to changings belief in truth of others

October 21, 2016

A small team of researchers with members from the U.S., the Netherlands, Russia and Italy has developed a new model that illuminates how changing the degree of certainty a person holds for a given belief can lead to changes ...

## 6 comments

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.