Quadratic discrepancy conjecture for the Pref-opposite construction
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.