Quadratic discrepancy conjecture for the Pref-opposite construction
Quadratic discrepancy conjecture for the Pref-opposite construction
A de Bruijn sequence of order is a cyclic binary sequence in which every binary word of length occurs exactly once; the Pref-opposite algorithm is the construction specified in the source. The discrepancy of a binary sequence is the maximum, over all prefixes, of the absolute difference between the numbers of s and s.
Quadratic discrepancy conjecture. The de Bruijn sequence constructed by the Pref-opposite algorithm has discrepancy .
The conjecture is supported by computations for and by an observed connection with OEIS sequence A033638, whose shifted formula gives the displayed experimental values; no proof or resolution is supplied here.
Sources & referencesView supporting material
Primary source
Daniel Gabric and Joe Sawada, “Investigating the discrepancy property of de Bruijn sequences”, arXiv:2005.01638 (2021).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.