Investigating the discrepancy property of de Bruijn sequences (Q2075526)

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. The authors provide an investigation of the discrepancy of over a dozen simple constructions of de Bruijn sequences as well as de Bruijn sequences based on linear feedback shift registers whose feedback polynomials are primitive. Furthermore, they demonstrate constructions that attain the lower bound of \(O(n)\) and a new construction that attains the previously known upper bound of \(O(\frac{2^n}{\sqrt{n}})\). This extends the work of \textit{J. Cooper} and \textit{C. Heitsch} [Discrete Math. 310, No. 6--7, 1152--1159 (2010; Zbl 1230.05021)].