Vanishing leading asymptotic coefficient for fixed-occurrence word enumeration

From papers

Let k,rNk,r\in\mathbb N, let v[k]v\in[k]^* be a pattern using d>1d>1 distinct letters, and let frv(k,n)f_r^v(k,n) count words in [k]n[k]^n containing vv exactly rr times. Let MrM_r be the maximal number of states with d1d-1 loops in a simple path in the automaton Au(v,r,k)Au(v,r,k). For constants KrK_r determined by

limnfrv(k,n)nMr(d1)n=Kr,\lim_{n\to\infty}\frac{f_r^v(k,n)}{n^{M_r}(d-1)^n}=K_r,

vanishing-coefficient conjecture. There exist k,rNk,r\in\mathbb N and a pattern v[k]v\in[k]^* such that d>1d>1 and Kr=0K_r=0. In that case, there exist LrNL_r\in\mathbb N, Lr<MrL_r<M_r, and K~r(0,)\widetilde K_r\in(0,\infty) such that

limnfrv(k,n)nLr(d1)n=K~r.\lim_{n\to\infty}\frac{f_r^v(k,n)}{n^{L_r}(d-1)^n}=\widetilde K_r.

The authors report that they observed Kr>0K_r>0 in many examples, so the conjecture predicts an exceptional pattern and a lower polynomial exponent in its asymptotics; no resolution is supplied.

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

Toufik Mansour, Reza Rastegar and Alexander Roitershtein, “Finite automata, probabilistic method, and occurrence enumeration of a pattern in words and permutations”, arXiv:1905.05646 (2019).

Solutions 0

No solutions have been posted yet.