Fertility Monotonicity and Average Complexity of the Stack-Sorting Map

Let ${\mathcal{D}}_n$ denote the average number of iterations of West’s stack-sorting map $s$ that are needed to sort a permutation in $S_n$ into the identity permutation $123\cdots n$. We prove that $$0.62433\approx \lambda \le \underset{n\to \mathrm{\infty }}{\mathrm{lim\hspace{0.17em}inf}}\frac{{\mathcal{D}}_n}{n}\le \underset{n\to \mathrm{\infty }}{\mathrm{lim\hspace{0.17em}sup}}\frac{{\mathcal{D}}_n}{n}\le \frac{3}{5}(7-8\log 2)\approx 0.87289,$$ where $\lambda$ is the Golomb-Dickman constant. Our lower bound improves upon West’s lower bound of $0.23$, and our upper bound is the first improvement upon the trivial upper bound of $1$. We then show that fertilities of permutations increase monotonically upon iterations of $s$. More precisely, we prove that $\mathrm{\mid }{s}^{-1}(\sigma )\mathrm{\mid }\le \mathrm{\mid }{s}^{-1}(s(\sigma ))\mathrm{\mid }$ for all $\sigma \in S_n$, where equality holds if and only if $\sigma =123\cdots n$. This is the first theorem that manifests a law-of-diminishing-returns philosophy for the stack-sorting map that B'ona has proposed. Along the way, we note some connections between the stack-sorting map and the right and left weak orders on $S_n$.