Quadratic discrepancy conjecture for the Pref-opposite construction

A de Bruijn sequence of order nn is a cyclic binary sequence in which every binary word of length nn 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 11s and 00s.

Quadratic discrepancy conjecture. The de Bruijn sequence constructed by the Pref-opposite algorithm has discrepancy Θ(n2)\Theta(n^2).

The conjecture is supported by computations for 10n3010\leq n\leq 30 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.