IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

The Discrepancy of the Lexicographically Least de Bruijn Cycle

  • Nov. 11, 2013
  • 3:15 p.m.
  • LeConte 312

Abstract

A (binary) de Bruijn cycle of order (n) is a cyclic binary word of length (2^n) so that every binary word of length (n) appears as a subword exactly once. There are many constructions for de Bruijn cycles, but one stands out for its extraordinary properties. The lexicographically-least de Bruijn cycle, sometimes called the Ford sequence, is also the de Bruijn cycle generated by the "greedy" algorithm, the cycle generated by a linear-shift feedback register of minimum weight, and the string of all Lyndon words of length dividing n arranged in lexicographic order. It is not hard to see that the Ford sequence is very "unbalanced" in the sense that there is an excess of 0's near the beginning and an excess of 1's near the end. It is possible to quantify this intuition by defining the discrepancy of a sequence to be the maximum, over all initial segments, of the difference between the number of 0's and 1's. We show that the discrepancy has order (2^n \log n/n), answering a question of Ron Graham.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC