The Discrepancy of the Lex-Least De Bruijn Sequence

2009/03/22 by Joshua Cooper, Cooper, Joshua, Christine Heitsch +1
Arts and Humanities · Mathematics · #05A16 (Primary) 05D40 #68R15 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #Linguistics and language evolution #Medieval Literature and History #Renaissance Literature and Culture #math.CO #msc:05A16 #msc:05D40 #msc:68R15

paper · pdf · doi:10.48550/arxiv.0903.3753

11 pages, 0 figures

arxiv created 2009/03/22 · openalex publication_date 2009/03/22 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We answer the following question of R. L. Graham: What is the discrepancy of the lexicographically-least binary de Bruijn sequence? Here, "discrepancy" refers to the maximum (absolute) difference between the number of ones and the number of zeros in any initial segment of the sequence. We show that the answer is Θ(2ⁿ log n/n).

Related

• Investigating the discrepancy property of de Bruijn sequences
• De Bruijn Sequences with Minimum Discrepancy
• Generalized Fibonacci recurrences and the lex-least De Bruijn sequence
• On the lower bound of the discrepancy of (t; s) sequences: I
• To Infinity and Beyond: Continuing De Bruijn Sequences by Extending the Alphabet