Asymptotic conjecture for prefix normal words and extension-critical words

About 12 years old · traced to

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) Θ(ln⁡nn),\textit{crit}(n)=\textit{pnw}(n)\,\Theta\left(\frac{\ln n}{n}\right),

and

pnw(n)=2n−Θ((ln⁡n)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.

References

Primary source

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

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.