Charles V. Schaefer, Jr. School of Engineering and Science
 
 
SES Home » Science Departments » Algebraic Cryptography Center » Statistical Algebra

Statistical Algebra

Introduction

In the book, " Experimentation in Mathematics," authors J.Borwein and D.Bailey write: "One of the greatest ironies of the information technology revolution is that while the computer was conceived and born in the field of pure mathematics, through the genius of giants such as John von Neumann and Alan Turing, until recently this marvelous technology had only a minor impact within the field that gave it birth."

Computers have been an essential tool of any researcher working in fields raging from applied mathematics and physics to medicine or biology. To the contrary, most mathematicians are still looking at the computers as mere calculators or printing devices, not acknowledging the fact that computer simulations and experiments could be a very useful instrument in tackling mathematical problems. In fact, experiments have always been an important tool in mathematical discovery. Carl Friedrich Gauss once declared that his way of arriving at mathematical truth was "through systematic experimentation." In recent years there was a definite shift toward this direction. Computers as well as various mathematical software packages have gained enough power to be able to perform sophisticated computations right on the office desk. If properly utilized, they might enable a completely new approach to discovery by running experiments and analyzing the outcomes.

At this point we would like to mention a few examples where computer computations were essential in obtaining mathematical results. One of the most controversial proofs accepted to a major mathematical journal in recent years was Hales' computer-assisted proof of the Kepler's conjecture. The problem of finding the densest packing of spheres was introduced by Kepler in 1611. T.Hale was able to reduce the problem to one of global optimization. He solved it by systematically applying linear programming methods to 5,000 different configurations of spheres which involved solving around 100,000 linear programming problems. The proof contains 250 pages and 3 gigabytes of computer programs and results. After a year of work, a team of 12 referees concluded that they are 99% sure that the proof is correct, but they cannot verify the correctness of all computer computations. Another prominent example is the solution of the Four Colour Conjecture, where researches used more then 1,200 hours of computer time to work through the details of the final proof. Computers were used in solving a number of key equations over free groups during the process of discovering a solution to the famous Tarski problem. A computer program was responsible for discovering of a direct formula for Pi, which allows the computation of individual hexadecimal or binary digits of Pi. An interesting fact is that proving that the formula is correct was almost a trivial matter after it had been obtained. Finally, we would like to mention that intensive computations preceded the proof of the famous Fermat's last theorem. With the help of computers Fermat's last theorem was proved to be true for integers up to 4.000.000.

The process of using advanced computing technology in mathematical research is often termed as Experimental Mathematics. The power of the computer experiment approach lies in the belief that it can lead a mathematician to discoveries and insights that might never have been reached using traditional methods. We have to say here, that in spite of growing interest and acceptance of the new technology among working mathematicians, there is still no common methodology. Applications are usually limited to exhaustive enumerations, visualizations or verifying the correctness of suggested proofs.

One of our main objectives is to show that the techniques of exploratory data analysis and statistical pattern recognition can be successfully used in abstract algebra and the theory of infinite groups in particular. The approach produces methods that are helpful in revealing hidden mathematical structures and formulating rigorous mathematical hypotheses. Our philosophy here that if an irregular or non-random behavior has been observed during an experiment then there must be a pure mathematical reason behind this phenomenon, which can be uncovered by a proper statistical analysis. The discovered knowledge can be of great interest to mathematicians. In addition, one can use the obtained knowledge to develop new (perhaps probabilistic) methods to solve hard combinatorial problems in algebra.

References:

  1. K. Appel and W. Haken, Every planar map is four colorable. Part I. Discharging, Illinois Journal of Mathematics, 21, pp. 429-490, 1977.
  2. K. Appel, and W. Haken and J. Koch, Every planar map is four colorable. Part II. Reducibility, Illinois Journal of Mathematics, 21, pp. 491-567, 1977.
  3. K. Appel and W. Haken, Every planar map is four colorable, Contemporary Mathematics, 98, 1989.
  4. D. Bailey, P. Borwein and S. Plouffe, On The Rapid Computation of Various Polylogarithmic Constants, Mathematics of Computation, 66, pp. 903-913, 1997.
  5. J. Borwein and D. Bailey, Mathematics by Experiment: Plausible Reasoning in the 21st century. A K Peters. Hardcover, 288pp, ISBN 1568812116, 2003.
  6. J. Borwein, D. Bailey, and R. Girgensohn, Experimentation in Mathematics: Computational Paths to Discovery. A K Peters. Hardcover, 300pp. ISBN 1568811365, 2004.
  7. B. Cipra, Mathematics-Fermat's Last Theorem Finally Yields, Science, 261, 32-33, 1993.
  8. D. Epstein and S. Levy, Experimentation and Proof in Mathematics. Notices of the American Mathematical Society , pp. 670-674, 1995.
  9. T. Hales, Sphere Packings I, Discrete and Computational Geometry, 17, pp. 1-51, 1997.
    T. Hales, Sphere Packings II, Discrete and Computational Geometry, 18, pp. 135-149, 1997.
  10. R.M. Haralick, A.D. Miasnikov and A.G. Myasnikov. Heuristics for Whitehead Minimization Problem, J. Experimental Mathematics, Vol. 14, No. 1, (2004), 7-14.
  11. R. M. Haralick, A.D. Miasnikov and A.G. Myasnikov. Pattern Recognition Approaches to Solving Combinatorial Problems in Free Groups, Contemporary Mathematics, 349:197-213, 2004.
  12. O. Kharlampovich and A. Myasnikov, Tarski's problem about the elementary theory of free groups has a positive solution, Electron. Res. Announc. Amer. Math. Soc., 4, pp. 101-108, 1998.