## Proof & Beauty

What do you get when you add a couple of math professors, a Roman Catholic nun, and a computer?

Not the start of a bad joke, but a major breakthrough in mathematics -- and a pretty one, too.

By Mark F. Bernstein

MATHEMATICIANS HAVE BEEN writing proofs since Euclid first took up geometry 2,300 years ago, but a corner of the field that has long been regarded as one of its highest intellectual endeavors is now obsolete. Thanks in large measure to the work of Dr. Herbert S. Wilf, the Thomas A. Scott Professor of Mathematics, and Dr. Doran Zeilberger of Temple University, at least one type of proof is now the province of the computer. Adapting a technique discovered 50 years ago by a Roman Catholic nun, they have helped demonstrate that even some of the most intractable mathematical problems can not only be simplified, but made elegant and even beautiful, as well.
Wilf and Zeilberger have shown that computers can prove a certain class of equations, known as combinatorial identities, instantly and infallibly. They first published that discovery eight years ago in a paper for The Journal of the American Mathematical Society. This past January, the American Mathematical Society acknowledged the importance of their work by awarding Wilf and Zeilberger its Leroy P. Steele Prize for Seminal Contributions to Research, one of the highest honors a mathematician can receive.
What exactly are combinatorial identities? Dissecting mathematical terminology is like walking through a dark cave: It is much less frightening if one stays close to the wall and proceeds in small steps.
Combinatorics is simply a mathematician's fancy term for the art of counting or arranging things. If you have 30 couples at a dinner party and want to seat them at tables of four so that no husband sits next to his own wife, determining the number of different ways this can be done -- and finding a simple formula for doing so -- is an exercise in combinatorics.
An identity, the other part of that imposing-looking term, is just another way of saying that what is to the left of an equals sign is the same as what is to the right; in other words, that A equals B. All of us are familiar with identities, though we may not know it. Einstein's famous theory of relativity -- e=mc2 -- and the Pythagorean Theorem -- a2+b2=c2 -- are two famous identities. So is 2+2=4.
To prove a combinatorial identity, one must find, or attempt to find, that the often numbingly complex set of equations to the left of an equals sign (the "A" in our A=B equation) is in fact identical to a much simpler equation to the right (the "B" part). It is the art of proving that something ungainly can be reduced to something simple, the distillation of something monstrous into something elegant. The standard analogy is that combinatorial identities fold together like an origami swan, although given the size of some of the equations Wilf and Zeilberger now can simplify, a more fitting comparison might be to an inflatable life raft.
Proving combinatorial identities has long been an intellectual challenge -- as well as a source of intense pleasure -- for mathematicians, but the exercise could be full of uncertainty. Frequently an equation could not be simplified, though it was impossible for the frustrated mathematician to tell whether this was because no simplification existed or because he or she just was not clever enough to find it. Thanks in part to Wilf, the computer can now find those elusive combinatorial identities or, which is just as helpful, state with certainty that no simplified identity exists. Small wonder that some have called Wilf's and Zeilberger's creation an "automatic proofing machine."
Very well, a philistine might say. A fine little mathematical trick. But of what use is this breakthrough in the real world? The short answer is that it has many practical applications, chief of which is perhaps enabling computer programmers to determine the number of steps -- and hence the amount of memory -- required to perform a given task. But the question of practicality makes Wilf bristle, though in a cheerful, Wilfian way. "Nobody ever subjected Picasso to that test," he points out. "They'd just hang his pictures on the wall, and they'd smile."
To Wilf, the distillation is its own reward. "Mathematics," he says, "is a deeply satisfying aesthetic experience. The human race is deeply in need of aesthetically satisfying experiences, and we're happy to provide them. That's a very practical, real-world application -- to make you smile and think."
Mathematics -- good for the soul? Smiling and thinking as balanced parts of the same equation? To the great innumerate mass of us, that would indeed be an identity worth proving.
Continued...
May Contents | Gazette Home