Explicit formulas for permutation pattern character polynomials

Abstract

Given permutations $\pi \in S_n$ and $\sigma \in S_k$, let $N_{\sigma }(\pi )$ denote the number of occurrences of $\sigma$ in $\pi$. While pattern avoidance and the distribution of pattern occurrences in permutations have been extensively studied, their interactions with the group structure on $S_n$ are still poorly understood. Gaetz and Ryba showed that the expected value of ${\chi }^{\lambda [n]}(\pi )N_{\sigma }(\pi )$ for $\pi \in S_n$ is given by a polynomial $a_{\sigma }^{\lambda }(n)$. More recently, Gaetz and Pierson derived explicit formulas for $a_{{\mathrm{id}}_k}^{\lambda }(n)$ when $|\lambda |\le 2$, which led them to conjecture that the polynomials $a_{{\mathrm{id}}_k}^{\lambda }(n)$ are real-rooted and nonnegative for $n\ge k$. We show that for all partitions $\lambda$, the polynomials $a_{{\mathrm{id}}_k}^{\lambda }(n)$ admit explicit closed forms in $n$ and $k$. These formulas allow us to exhibit counterexamples to Gaetz and Pierson's real-rootedness conjecture as well as to prove special cases of their nonnegativity conjecture. Our results imply that the expected value of $f\cdot N_{{\mathrm{id}}_k}$ on $S_n$ admits a closed form whenever $f$ is a permutation statistic expressible as a polynomial in the functions $m_j:{⨆}_{n\ge 0}{S}_n\to \mathbb{Z}$ which count $j$-cycles in their inputs.

75 pages and 12 figures. Accompanying SageMath code is available at https://github.com/JonasIskander/character-polynomials. Substantially revised from the previous version, incorporating a new proof strategy, stronger and more explicit main results, additional applications, and substantial improvements to exposition