A proof of the peak polynomial positivity conjecture

摘要

We say that a permutation pi = pi(1) pi(2) center dot center dot center dot pi(n). epsilon G(n) has a peak at index i if pi(i-1) < pi(i) > pi(i+1). Let P(pi) denote the set of indices where z- has a peak. Given a set S of positive integers, we define P(S; n) = {pi epsilon G(n) : P(pi) = S}. In 2013 Billey, Burdzy, and Sagan showed that for subsets of positive integers S and sufficiently large n, vertical bar P(S; n)vertical bar = ps(n)2(n-vertical bar S vertical bar-1) where ps(x) is a polynomial depending on S. They proved this by establishing a recursive formula for ps(x) involving an alternating sum, and they conjectured that the coefficients of ps(x) expanded in a binomial coefficient basis centered at max(S) are all nonnegative. In this paper we introduce a new recursive formula for vertical bar P(S; n)vertical bar without alternating sums and we use this recursion to prove that their conjecture is true. (C) 2017 Elsevier Inc. All rights reserved.