Asymptotic constant for the discrepancy of the lex-least de Bruijn sequence

Let Ln{\mathcal L}_n be the lexicographically least binary order-nn de Bruijn sequence, formed by concatenating all Lyndon words of length dividing nn in lexicographic order. For a word ww, define its discrepancy by

disc(w)=maxMk=0M(1)wk.\operatorname{disc}(w)=\max_M\left|\sum_{k=0}^M(-1)^{w_k}\right|.

Discrepancy asymptotic constant conjecture. There is some constant CC such that

limnndisc(Ln)2nlogn=C.\lim_{n\rightarrow\infty}\frac{n\operatorname{disc}({\mathcal L}_n)}{2^n\log n}=C.

The preceding theorem establishes the order of magnitude disc(Ln)=Θ(2nlogn/n){\operatorname{disc}({\mathcal L}_n)}=\Theta(2^n\log n/n); the conjecture asserts that the normalized discrepancy has a limiting constant, strengthening that asymptotic estimate.

Sources & referencesView supporting material

Primary source

Joshua Cooper and Christine Heitsch, “The Discrepancy of the Lex-Least De Bruijn Sequence”, arXiv:0903.3753 (2009).

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.