Asymptotic conjecture for prefix normal words and extension-critical words

From papers

For each nn, let pnw(n)\textit{pnw}(n) be the number of prefix normal binary words of length nn, and let crit(n)\textit{crit}(n) be the number of extension-critical words of length nn. Prefix-normal asymptotic conjecture. Based on empirical evidence,

crit(n)=pnw(n)Θ(lnnn),\textit{crit}(n)=\textit{pnw}(n)\,\Theta\left(\frac{\ln n}{n}\right),

and

pnw(n)=2nΘ((lnn)2).\textit{pnw}(n)=2^{n-\Theta((\ln n)^2)}.

These estimates refine the preceding conjecture about the extension-critical ratio and are presented as empirical predictions; no proof or resolution is supplied in the paper.

Progress summary

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

Sources & referencesView supporting material

Primary source

Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták, Frank Ruskey and Joe Sawada, “Normal, Abby Normal, Prefix Normal”, arXiv:1404.2824 (2014).

Solutions 0

No solutions have been posted yet.