A proof of the peak polynomial positivity conjecture

الأصل · EN

We say that a permutation π=π₁π₂ πₙ ∈ Sₙ has a peak at index i if πᵢ₋₁ < πᵢ > πᵢ₊₁. Let P(π) denote the set of indices where π has a peak. Given a set S of positive integers, we define Pₛ(n)={πₙ:P(π)=S}. In 2013 Billey, Burdzy, and Sagan showed that for subsets of positive integers S and sufficiently large n, | Pₛ(n)|=pₛ(n)2ⁿ⁻|ˢ|⁻¹ where pₛ(x) is a polynomial depending on S. They gave a recursive formula for pₛ(x) involving an alternating sum, and they conjectured that the coefficients of pₛ(x) expanded in a binomial coefficient basis centered at (S) are all nonnegative. In this paper we introduce a new recursive formula for |Pₛ(n)| without alternating sums, and we use this recursion to prove that their conjecture is true.