WINNIPEG, MB – Resolving long-standing conjectures and open problems is a hallmark of progress in the field of mathematics. A University of Winnipeg duo – James Currie & Narad Rampersad – made significant progress in the field recently by resolving Dejean’s Conjecture.
On May 7, 2009, Currie, a professor in the Department of Mathematics and Statistics, and Rampersad, a visiting post-doctoral fellow, announced their proof of Dejean’s Conjecture. This conjecture, published in 1972 by the French mathematician Francoise Dejean, addresses the extent to which sequences of symbols are able to avoid repetitions. In addition to being of theoretical interest, repetitions in words are connected to the performance of algorithms for creating compressed computer files, such as the .zip files commonly used on the Internet.
In recent memory, considerable public interest was aroused by the conquest of Fermat’s Last Theorem, finally proved in 1993, some 350 years after being stated. In this context, the achievement of Currie and Rampersad is modest. Nevertheless, they have solved a problem that stymied mathematicians for almost 40 years.
Professor Currie, who is a mathematician, and Dr. Rampersad, a theoretical computer scientist, found several mathematical constructions to reduce establishing their final proof to a long but feasible computer search, evaluating some six billion billion (around 6.673 x 1018) pairs of words. Each “word” was a string of one hundred (100) 0’s and 1’s. The storage involved in this search quickly grew beyond the capacity of their laptop computers, and they turned to the University’s theoretical physics group to borrow computational power. Eventually, this too was inadequate, so the researchers turned to WestGrid, Western Canada’s high-performance network for scientific computation.
Using several of WestGrid’s computers over the course of a week-and-a-half, Currie and Rampersad began to discern more clearly the “shape” of their search space, and in turn, to refine their search algorithms. Ironically, in the end, their algorithms had improved so much that the search could once again fit on a laptop computer. In fact, in their submitted paper, the computation disappears entirely, and only its fruit remains – a list of 12 functions found by the search, occupying less than a full page of the printed paper.
In an interesting twist, just as Currie and Rampersad had published their solution online, a young French researcher, Michael Rao, announced that he too had arrived at the finish line. Rao’s theoretical approach is different, so that there is a clear case of simultaneous discovery. In Montreal at the end of May, a special session is being organized at the upcoming CanaDAM 2009 conference on discrete and algorithmic mathematics conference to present both approaches.
See www.uwinnipeg.ca/~currie/dejean.html for more information on Dejean’s Conjecture.
