Investigating the discrepancy property of de Bruijn sequences

2020/05/04 by Daniel Gabrić, Gabric, Daniel, Joe Sawada +1
Computer Science · Mathematics · #Analytic Number Theory Research #Coding theory and cryptography #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2005.01638

openalex publication_date 2020/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The discrepancy of a binary string refers to the maximum (absolute) difference between the number of ones and the number of zeroes over all possible substrings of the given binary string. We provide an investigation of the discrepancy of known simple constructions of de Bruijn sequences. Furthermore, we demonstrate constructions that attain the lower bound of Θ(n) and a new construction that attains the previously known upper bound of Θ((2ⁿ)/(√(n))). This extends the work of Cooper and Heitsch~[Discrete Mathematics, 310 (2010)].

Related

• De Bruijn Sequences with Minimum Discrepancy
• The Discrepancy of the Lex-Least De Bruijn Sequence
• Generalized Fibonacci recurrences and the lex-least De Bruijn sequence
• Cut-Down de Bruijn Sequences
• Efficient generation of odd order de Bruijn sequence with the same complement and reverse sequences