A proof of the peak polynomial positivity conjecture

Abstract

We say that a permutation $\pi ={\pi }_1{\pi }_2\cdots {\pi }_n\in {\mathfrak{S}}_n$ has a peak at index $i$ if ${\pi }_{i-1}<{\pi }_i>{\pi }_{i+1}$. Let $\mathcal{P}(\pi )$ denote the set of indices where $\pi$ has a peak. Given a set $S$ of positive integers, we define ${\mathcal{P}}_S(n)=\{\pi \in {\mathfrak{S}}_n:\mathcal{P}(\pi )=S\}$. In 2013 Billey, Burdzy, and Sagan showed that for subsets of positive integers $S$ and sufficiently large $n$, $|{\mathcal{P}}_S(n)|=p_S(n)2^{n-|S|-1}$ where $p_S(x)$ is a polynomial depending on $S$. They gave a recursive formula for $p_S(x)$ involving an alternating sum, and they conjectured that the coefficients of $p_S(x)$ expanded in a binomial coefficient basis centered at $\max (S)$ are all nonnegative. In this paper we introduce a new recursive formula for $|{\mathcal{P}}_S(n)|$ without alternating sums, and we use this recursion to prove that their conjecture is true.

7 pages