Vanishing leading asymptotic coefficient for fixed-occurrence word enumeration

About 7 years old · traced to

Let k,r∈Nk,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 d−1d-1 loops in a simple path in the automaton Au(v,r,k)Au(v,r,k). For constants KrK_r determined by

lim⁡n→∞frv(k,n)nMr(d−1)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,r∈Nk,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 Lr∈NL_r\in\mathbb N, Lr<MrL_r<M_r, and K~r∈(0,∞)\widetilde K_r\in(0,\infty) such that

lim⁡n→∞frv(k,n)nLr(d−1)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.

References

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).

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.