Empirical asymptotics for extension-critical and prefix normal word counts

From papers

Let Σ={0,1}\Sigma=\{0,1\}, let LPN1\mathcal L_{\mathrm{PN1}} be the language of prefix normal words, and let ecrit(n)\textit{ecrit}(n) count the extension-critical words in LPN1Σn\mathcal L_{\mathrm{PN1}}\cap\Sigma^n, where an extension-critical word is a prefix normal word ww such that w1w1 is not prefix normal. Let pnw(n)\textit{pnw}(n) denote the number of prefix normal words of length nn. Extension-critical asymptotic conjecture. As nn tends to infinity,

ecrit(n)=pnw(n)Θ(lognn),\textit{ecrit}(n)=\textit{pnw}(n)\,\Theta\left(\frac{\log n}{n}\right),

and

pnw(n)=2nΘ((logn)2).\textit{pnw}(n)=2^{n-\Theta((\log n)^2)}.

These are empirical asymptotic predictions refining the conjectured convergence of the extension-critical ratio to zero; the paper presents numerical evidence but no proof.

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, “On Prefix Normal Words and Prefix Normal Forms”, arXiv:1611.09017 (2016).

Solutions 0

No solutions have been posted yet.