# 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: CMU professor honored for computational complexity breakthrough

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

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

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

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

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

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

## Recommended for you

#### Using vouchers found to reduce waste when offering health products to the poor in Africa

August 26, 2016

(Phys.org)—A team of researchers affiliated with several institutions in the U.S. has found that offering vouchers as a means of distributing health products to poor people in Africa resulted in less waste than other methods. ...

#### Researchers plumb the secrets of tissue paper

August 24, 2016

Canada's tissue manufacturers are now much closer to producing the perfect paper, thanks to new UBC research.

#### Seeing inside an ancient Australian Indigenous artefact non-invasively

August 26, 2016

Nuclear techniques have allowed archaeologists to see into an embedded section of an ancient Australian Indigenous stone artefact non-invasively—suggesting important information about its origin and use.

#### One of the most significant Etruscan discoveries in decades names female goddess Uni

August 24, 2016

Archaeologists translating a very rare inscription on an ancient Etruscan temple stone have discovered the name Uni—an important female goddess.

#### More than a few good men: Study finds counterintuitive outcomes of gender imbalance

August 24, 2016

Contrary to traditional expectations of unbalanced sex ratios, places with more men than women do not typically experience higher rates of family and social instability, according to a University of Utah study. The study, ...

#### Urban sociologists call for expanding concepts of 'livable cities'

August 24, 2016

A commentary in the current issue of the journal Nature, co-written by Hillary Angelo, UC Santa Cruz assistant professor of sociology, argues that while big cities appear to be islands of sustainable living, issues of social ...

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