Grant: Discovery Grants Program - Individual

My research follows up recent success in the solution of a 37-year-old mathematical riddle: Dejean's Conjecture. This conjecture, published in 1972 by the French mathematician Francoise Dejean, addressed the extent to which sequences of symbols are able to avoid repetitions. In addition to being of theoretical interest, repetitions in sequences are connected to the performance of algorithms for creating compressed computer files, such as the .zip files commonly used on the internet. Using several mathematical constructions reduced finding the final proof of Dejean's conjecture to a long but feasible computer search, evaluating some 6 billion billion (around 6.673 times 10^18) pairs of words. Each ""word"" was a string of one hundred 0's and 1's. The storage involved in this search quickly grew beyond the capacity of laptops, and computational power was borrowed from my University's theoretical physics group, and then from WestGrid, Western Canada's high-performance network for scientific computation. The use of WestGrid's computers over the course of a week and a half made it possible to discern more clearly the ""shape"" of the search space, and to refine search algorithms. Ironically, in the end, algorithms had improved so much that the search could once again fit on a laptop computer. In fact, in the 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. The study of whether certain repetitions and regularities can be avoided in long sequences of symbols is part of ""Combinatorics on Words"". Potential future applications exist wherever long sequences of symbols arise, for example, in data compression, or in the study of the structures in genetic sequences.