The asymptotic consecutive-pattern distribution conjecture

About 6 years old · traced to

For k≥3k\geq 3, let π∈Sk\pi\in S_k be a consecutive pattern, let I⊆Z+I\subseteq\mathbb{Z}^+ be finite, let Pπ(I,n)\mathcal{P}_{\pi}(I,n) be the set of permutations in SnS_n whose consecutive-pattern occurrence starting indices are exactly II, and write

pπ(I,n)=∣Pπ(I,n)∣,pπ(n)=pπ(∅,n).p_{\pi}(I,n)=|\mathcal{P}_{\pi}(I,n)|,\qquad p_{\pi}(n)=p_{\pi}(\emptyset,n).

The asymptotic consecutive-pattern distribution conjecture. For any k≥3k\geq 3, any π∈Sk\pi\in S_k, and any finite I⊆Z+I\subseteq\mathbb{Z}^+, there are constants cπ,I,α∈Rc_{\pi,I},\alpha\in\mathbb{R} with α>0\alpha>0 such that

pπ(I,n)=cπ,Ipπ(n)(1+O(n−α)).p_{\pi}(I,n)=c_{\pi,I}p_{\pi}(n)\left(1+O\left(n^{-\alpha}\right)\right).

This conjectures that prescribing any finite set of consecutive-pattern occurrences changes the unrestricted count only by an asymptotically constant factor, with a power-saving error term. The source presents it as an analogue of an earlier theorem for decreasing patterns and states that the question remains open.

References

Primary source

Kaarel Hänni, “Asymptotics of descent functions”, arXiv:2011.14360 (2020).

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.