# Factoring peak polynomials

Sara Billey, Matthew Fahrbach, Alan Talmage

► To cite this version:

Sara Billey, Matthew Fahrbach, Alan Talmage. Factoring peak polynomials. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.441-452, 10.46298/dmtcs.2478 . hal-01337803

HAL Id: hal-01337803

https://hal.science/hal-01337803

Submitted on 27 Jun 2016

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Factoring peak polynomials

Sara Billey<fnref n="1" /> and Matthew Fahrbach<fnref n="2" /> and Alan Talmage<fnref n="3" />

**Abstract.** Given a permutation $\pi = \pi_1\pi_2\cdots\pi_n$ in the symmetric group, we say an index $i$ is a peak if $\pi_{i-1} < \pi_i > \pi_{i+1}$. Let $P(\pi)$ denote the set of peaks of $\pi$. Billey-Burdzy-Sagan showed that for all fixed subsets of positive integers $S$ and sufficiently large $n$, the number of permutations on $n$ elements with peak set $S$ is $p_S(n)2^{n-|S|-1}$ for some polynomial $p_S(x)$ depending on $S$. They conjectured that the coefficients of $p_S(x)$ expanded in a binomial coefficient basis centered at $\max(S)$ are all positive. We show that this is a consequence of a stronger conjecture that bounds the modulus of the roots of $p_S(x)$. Furthermore, we give an efficient explicit formula for peak polynomials in the binomial basis centered at 0, which we use to identify many integer roots of peak polynomials along with certain inequalities and identities.

**Résumé.** Étant donné une permutation $\pi = \pi_1\pi_2\cdots\pi_n$ du groupe symétrique, nous disons qu’un indice $i$ est un sommet si $\pi_{i-1} < \pi_i > \pi_{i+1}$. Soit $P(\pi)$ l’ensemble des sommets de $\pi$. Billey-Burdzy-Sagan ont montré que, pour tout sous-ensemble d’entiers positifs $S$ et $n$ suffisamment grand, le nombre de permutations de $n$ éléments avec ensemble de sommets $S$ est $p_S(n)2^{n-|S|-1}$ pour un certain polynôme $p_S(x)$ dépendant de $S$. Ils ont fait la conjecture que les coefficients du polynôme $p_S(x)$ exprimé dans une base de coefficients binomiaux centrée en $\max(S)$ sont tous positifs. Nous montrons que cela découle d’une conjecture plus forte qui borne le module des racines du polynôme $p_S(x)$. De plus, nous donnons une formule explicite efficace pour les polynômes sommets dans la base binomiale centrée en 0, que nous utilisons pour identifier plusieurs racines entières de polynômes sommets, ainsi que certaines inégalités et identités.

**Keywords:** binomial coefficient, combinatorics, peak, permutation

# 1 Introduction

Let $\mathfrak{S}_n$ be the symmetric group of all permutations $\pi = \pi_1\pi_2\cdots\pi_n$ of $[n] := \{1, 2, \dots, n\}$. An index $1 < i < n$ of $\pi$ is a *peak* if $\pi_{i-1} < \pi_i > \pi_{i+1}$, and the *peak set* of $\pi$ is defined as $P(\pi) = \{i : i$ is a peak of $\pi\}$. We are interested in counting the permutations of $\mathfrak{S}_n$ with a given peak set, so let us define $\mathcal{P}_S(n) = \{\pi \in \mathfrak{S}_n : P(\pi) = S\}$. We say that a set $S = \{i_1 < i_2 < \cdots < i_s\}$ is $n$-admissible if $|\mathcal{P}_S(n)| \neq 0$. Note that we insist the elements of $S$ be listed in increasing order and that $S$ is $n$-admissible if and only if $1 < i_1,$ no two $i_r$ are consecutive integers, and $i_s < n$. If we make a statement about an *admissible set* $S$, we

Support for this work was provided by the National Science Foundation under grants DMS-1062253, DMS-1101017, and the University of Washington Mathematics REU 2013 and 2014.

<footnote n="1">¹Department of Mathematics, University of Washington, USA</footnote>

<footnote n="2">²Department of Mathematics, University of Kentucky, USA</footnote>

<footnote n="3">³Department of Mathematics, Washington University in St. Louis, USA</footnote>

<footnote>(i)Emails: billey@math.washington.edu, matthew.fahrbach@uky.edu, amtalmage@wustl.edu</footnote>
mean that $S$ is $n$-admissible for some $n$, and the statement holds for every $n$ such that $S$ is $n$-admissible. Burdzy, Sagan, and the first author recently proved the following result in [3].

**Theorem 1.1** ([3, Theorem 3]). If $S$ is a nonempty admissible set and $m = \max(S)$, then

$$|\mathcal{P}_S(n)| = p_S(n)2^{n-|S|-1}$$

for $n \ge m$, where $p_S(x)$ is a polynomial of degree $m-1$ depending on $S$ such that $p_S(n)$ is an integer for all integral inputs $n$. If $S = \emptyset$, then $|\mathcal{P}_S(n)| = 2^{n-1}$, so we can set $p_\emptyset(n) = 1$.

If $S$ is not admissible, then $|\mathcal{P}_S(n)| = 0$ for all positive integers $n$, and one defines the corresponding polynomial to be $p_S(x) = 0$. Thus, for all finite sets $S$ of positive integers, $p_S(x)$ is a well-defined polynomial, which is called the peak polynomial for $S$.

In this paper, we study properties of peak polynomials such as their expansions into binomial bases, roots, and related inequalities and identities. We also enumerate permutations with a given peak set using alternating permutations and connect our results to other recent work about the peak statistic [3, 11, 14, 16]. Our primary motivation comes from combinatorics, information theory, and probability theory. Peaks sets have been studied for decades going back to [17] and used more recently in a probabilistic project concerned with mass redistribution [10]. Below are the primary results of this paper.

**Theorem 1.2.** Let $S = \{i_1 < i_2 < \cdots < i_s = m\}$ be admissible and nonempty. For $0 \le j \le m-1$, define the coefficients

$$d_j^S = (-1)^{m-j-1} (-2)^{|S \cap (j, \infty)|-1} p_{S \cap [j]}(j).$$

If there exists an index $1 \le r \le s-1$ such that $i_{r+1} - i_r$ is odd, let $b = i_r$ for the largest such $r$. Then the peak polynomial $p_S(x)$ expands in the binomial basis centered at 0 as

$$p_S(x) = \sum_{j=b}^{m-1} d_j^S \binom{x}{j}.$$

Otherwise, if there are no odd gaps, then

$$p_S(x) = \left(d_0^S - (-2)^{|S|-1}\right) + \sum_{j=1}^{m-1} d_j^S \binom{x}{j}.$$

Theorem 1.1 implies that $p_S(m) = 0$ using the fact that $\mathcal{P}_S(m)$ is empty, but we may have $p_S(\ell) \ne 0$ for $\ell < m$ even though $|\mathcal{P}_S(\ell)| = 0$. The next two theorems describe additional roots of $p_S(x)$.

**Corollary 1.3.** If $S = \{i_1 < i_2 < \cdots < i_s\}$ and $i_{r+1} - i_r$ is odd for some $1 \le r \le s-1$, then $0, 1, 2, \dots, i_r$ are roots of $p_S(x)$.

**Theorem 1.4.** We have $p_S(i) = 0$ for all $i \in S$.

In [3], they conjecture that the coefficients of any peak polynomial are nonnegative integers in the shifted binomial basis $\binom{x-m}{j}$, where $m$ is the maximum value in the corresponding peak set. We refer to this as the “positivity conjecture”, and we show in this paper that it is a consequence of the following conjecture. These two conjectures motivated our research, because they suggest that we look at the roots of peak polynomials.
**Conjecture 1.5.** The complex roots of $p_S(z)$ lie in $\{z \in \mathbb{C} : |z| \le m \text{ and } \text{Re}(z) \ge -3\}$ if $S$ is admissible.

This conjecture is similar in nature to the Riemann Hypothesis. More specifically, our work fits into a bigger context of studying roots for polynomials with integer coefficients in some basis. For example, the roots of Ehrhart polynomials [2, 6, 9, 18], chromatic polynomials [7, 8], and Hilbert polynomials [19] have all been shown to respect similar bounds on the complex plane. Additionally, we are investigating the roots of peak polynomials, because they may encode properties of their peak set, similar to how the roots of a chromatic polynomial $P(G, k)$ encode the number of connected components, blocks, and acyclic orientations of $G$.

## 2 Background

In this section, we state results from [3] that are used throughout this paper. Additionally, we discuss the calculus of finite differences, specifically forward differences, and the positivity conjecture from [3]. Let $S$ be a nonempty admissible set of constants and $m = \max(S)$ throughout the section.

**Corollary 2.1 ([3, Corollary 4]).** We have

$$p_S(x) = p_{S_1}(m-1) \binom{x}{m-1} - 2p_{S_1}(x) - p_{S_2}(x),$$

where $S_1 = S \setminus \{m\}$ and $S_2 = S_1 \cup \{m-1\}$.

**Theorem 2.2 ([3, Theorem 6]).** If $S = \{m\}$, then

$$p_S(x) = \binom{x-1}{m-1} - 1.$$

In the calculus of finite differences, we define the *forward difference operator* $\Delta$ to be $(\Delta f)(x) = f(x+1) - f(x)$. Higher order differences are given by $(\Delta^n f)(x) = (\Delta^{n-1} f)(x+1) - (\Delta^{n-1} f)(x)$. We use the definition of the Newton interpolating polynomial to expand $p_S(x)$ in the binomial basis centered at $k$ as

$$p_S(x) = \sum_{j=0}^{m} (\Delta^j p_S)(k) \binom{x-k}{j}.$$

Notice its similarity to Taylor's theorem. Below is an example of the forward differences of $p_{\{2,6,10\}}(x)$. The $k$-th column in the table is the basis vector for the expansion of $p_{\{2,6,10\}}(x)$ in the binomial basis centered at $k$. We consider these expansions centered at both 0 and $m$ in this paper.
<table><caption>Tab. 1: Forward differences of $p_{\{2,6,10\}}(x)$.</caption><thead><tr><th>j, k</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th></tr></thead><tbody><tr><td>0</td><td>-8</td><td>-4</td><td>0</td><td>2</td><td>4</td><td>6</td><td>0</td><td>-18</td><td>-72</td><td>-196</td><td>0</td></tr><tr><td>1</td><td>4</td><td>4</td><td>2</td><td>2</td><td>2</td><td>-6</td><td>-18</td><td>-54</td><td>-124</td><td>196</td><td>3094</td></tr><tr><td>2</td><td>0</td><td>-2</td><td>0</td><td>0</td><td>-8</td><td>-12</td><td>-36</td><td>-70</td><td>320</td><td>2898</td><td>12376</td></tr><tr><td>3</td><td>-2</td><td>2</td><td>0</td><td>-8</td><td>-4</td><td>-24</td><td>-34</td><td>390</td><td>2578</td><td>9478</td><td>26564</td></tr><tr><td>4</td><td>4</td><td>-2</td><td>-8</td><td>4</td><td>-20</td><td>-10</td><td>424</td><td>2188</td><td>6900</td><td>17086</td><td>36376</td></tr><tr><td>5</td><td>-6</td><td>-6</td><td>12</td><td>-24</td><td>10</td><td>434</td><td>1764</td><td>4712</td><td>10186</td><td>19290</td><td>33324</td></tr><tr><td>6</td><td>0</td><td>18</td><td>-36</td><td>34</td><td>424</td><td>1330</td><td>2948</td><td>5474</td><td>9104</td><td>14034</td><td>20460</td></tr><tr><td>7</td><td>18</td><td>-54</td><td>70</td><td>390</td><td>906</td><td>1618</td><td>2526</td><td>3630</td><td>4930</td><td>6426</td><td>8118</td></tr><tr><td>8</td><td>-72</td><td>124</td><td>320</td><td>516</td><td>712</td><td>908</td><td>1104</td><td>1300</td><td>1496</td><td>1692</td><td>1888</td></tr><tr><td>9</td><td>196</td><td>196</td><td>196</td><td>196</td><td>196</td><td>196</td><td>196</td><td>196</td><td>196</td><td>196</td><td>196</td></tr><tr><td>10</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr></tbody></table>

We know from Theorem 1.1 that $(\Delta^0 p_S)(m) = 0$, $(\Delta^{m-1} p_S)(k)$ is a positive integer, and $(\Delta^j p_S)(k) = 0$ for all $k \in \mathbb{Z}$ and $j \ge m$. Burdzy, Sagan, and the first author proposed the following positivity conjecture in [3].

**Conjecture 2.3** ([3, Conjecture 14]). Each coefficient $(\Delta^j p_S)(m)$ is a positive integer for $1 \le j \le m-1$ and all admissible sets $S$.

It follows from Stanley's text [21, Corollary 1.9.3] that $p_S(n)$ is an integer for all integral $n$ if and only if the coefficients in the expansion of $p_S(n)$ in a binomial basis are integral, so we only need to prove that $(\Delta^j p_S)(m)$ is positive for $1 \le j \le m-1$. In [4], we show that the positivity conjecture is a consequence of Conjecture 1.5 using the following theorem.

**Theorem 2.4.** If $S$ is admissible and $p_S(n)$ has no zero whose real part is greater than $m$, then each coefficient $(\Delta^j p_S)(m)$ is positive for $1 \le j \le m-1$.

It is worth noting that we have checked the zeros of the peak polynomials for all admissible sets $S$ with $\max(S) \le 15$ in [13], and they agree with Conjecture 1.5.

# 3 Roots of peak polynomials

Our main theorems from the introduction are proved here in Subsection 3.1. In particular, we give an explicit formula for $p_S(x)$ in the binomial basis centered at 0. In Subsection 3.2 we look at peak polynomials with only integral roots, and the results in Subsection 3.3 show that if $S$ has a gap of 3, then $p_S(x)$ is independent of the peaks to the left of this gap up to a constant. All of the results in this section assume that $S$ is admissible, though not explicitly stated in the hypothesis. Also, note that $m \ne \max(S)$ in most of the recurrences.

## 3.1 Main results

The following recurrence relation is very efficient for computation and is the foundation of every result in this section.
**Lemma 3.1.** If $S = \{i_1 < i_2 < \dots < i_s = m < m + k\}$ and $k \ge 2$, then

$$p_S(x) = -2p_{S_1}(x)\chi(k \text{ even}) + \sum_{j=1}^{k-1} (-1)^{k-1-j} p_{S_1}(m+j) \binom{x}{m+j}.$$

*Proof.* We induct on $k$. Corollary 2.1 implies the base case when $k = 2$, and by induction,

$$\begin{align*}
p_S(x) &= p_{S_1}(m+k-1) \binom{x}{m+k-1} - 2p_{S_1}(x) - p_{S_2}(x) \\
&= p_{S_1}(m+k-1) \binom{x}{m+k-1} - 2p_{S_1}(x) \\
&\quad - \left[ -2p_{S_1}(x)\chi(k-1 \text{ even}) + \sum_{j=1}^{k-2} (-1)^{k-2-j} p_{S_1}(m+j) \binom{x}{m+j} \right] \\
&= -2p_{S_1}(x)\chi(k \text{ even}) + \sum_{j=1}^{k-1} (-1)^{k-1-j} p_{S_1}(m+j) \binom{x}{m+j}. \quad \square
\end{align*}$$

**Corollary 3.2.** If $S = \{i_1 < i_2 < \dots < i_s = m < m + k\}$ and $k \ge 2$, then

$$|\mathcal{P}_S(n)| = -\chi(k \text{ even})|\mathcal{P}_{S_1}(n)| + \sum_{j=1}^{k-1} (-1)^{k-1-j} \binom{n}{m+j} |\mathcal{P}_{S_1}(m+j)| \cdot |\mathcal{P}_0(n - (m+j))|.$$

*Proof.* Apply Theorem 1.1 to Lemma 3.1. $\square$

We can interpret Corollary 3.2 combinatorially. Choose $m + k - 1$ of the $n$ elements and arrange them such that their peak set is $S_1$. Arrange the remaining $n - (m + k - 1)$ elements so that there are no peaks, and append this sequence to the previous one. In the combined sequence there is either a peak at $m + k, m + k - 1$, or no peak after $m$. Since $m + k \in S$,

$$|\mathcal{P}_S(n)| = \binom{n}{m+k-1} |\mathcal{P}_{S_1}(m+k-1)| \cdot |\mathcal{P}_0(n-(m+k-1))| - |\mathcal{P}_{S_2}(n)| - |\mathcal{P}_{S_1}(n)|.$$

We repeat this procedure for $|\mathcal{P}_{S_2}(n)|$ to count all the permutations whose peak set is $S_1 \cup \{m + k - 1\}$, but this also counts permutations whose peak set is $S_1 \cup \{m + k - 2\}$ and $S_1$. We repeat this process until we count permutations whose peak set is $S_1 \cup \{m + 1\}$, but this peak set is inadmissible and terminates the procedure. Notice that $|\mathcal{P}_{S_1}(n)|$ telescopes because it is included in each iteration with an alternating sign.

We now present the proof of an explicit formula for peak polynomials with nonempty peak sets in the binomial basis centered at 0. The results about roots due to odd gaps and peaks follow.

*Proof of Theorem 1.2.* The proof follows by iterating Lemma 3.1. In the case that there no odd gaps, we have

$$p_S(x) = (-2)^{|S|-1} \left[ \binom{x-1}{i_1-1} - 1 \right] + \sum_{j=i_1}^{m-1} d_j^S \binom{x}{j},$$

and then use Vandermonde's identity to shift the $p_{\{i_1\}}(x)$ term to the binomial basis centered at 0. $\square$
**Corollary 3.3.** If $S = \{i_1 < i_2 < \dots < i_s\}$ and $i_{r+1} - i_r$ is odd for some $1 \le r \le s-1$, then $0, 1, \dots, i_r$ are roots of $p_S(x)$.

*Proof.* The proof follows from Theorem 1.2. $\square$

**Corollary 3.4.** If $S$ contains an odd peak, then $p_S(0) = 0$. Otherwise, $p_S(0) = (-2)^{|S|}$.

*Proof.* The proof follows from Theorem 1.2. $\square$

**Theorem 3.5.** We have $p_S(i) = 0$ for $i \in S$.

*Proof.* We induct on $|S|$ for all nonempty admissible sets $S$. In the base case $|S| = 1$, and $p_{\{m\}}(m) = 0$ by Theorem 2.2. In the inductive step, let $m = \max(S)$. If $i \in S_1$, then $p_{S_1}(i) = 0$ by the induction hypothesis, so $p_S(i) = 0$ by Lemma 3.1. We also know that $p_S(m) = 0$ by Theorem 1.1, so $p_S(i) = 0$ for all $i \in S$. $\square$

## 3.2 Peak polynomials with only integral roots

All of the peak polynomials in this subsection are completely factored and have all nonnegative integral roots. As a result, they satisfy Conjecture 2.3 by Theorem 2.4, because we have bounded the real part of their roots by $\max(S)$. In the next two lemmas, the leading coefficient is all that is recursively defined, and it depends solely on the structure of $\{i_1 < i_2 < \dots < i_s\}$. In Conjecture 6.5 we classify all the peak polynomials with only integral roots.

**Lemma 3.6.** If $S = \{i_1 < i_2 < \dots < i_s = m < m + 3\}$, then

$$p_S(x) = \frac{p_{S_1}(m+1)}{2(m+1)!} (x - (m+3)) \prod_{j=0}^{m} (x-j).$$

**Lemma 3.7.** If $S = \{i_1 < i_2 < \dots < i_s = m < m + 3 < m + 5\}$, then

$$p_S(x) = \frac{p_{S\setminus\{m+3, m+5\}}(m+1)}{12(m+1)!} (x - (m+5))(x - (m+3))(x - (m-2)) \prod_{j=0}^{m} (x-j).$$

The next two corollaries show how $p_S(x)$ grows from $x_0$ to $x_0+1$ for any $x_0 \in \mathbb{R}$, and they demonstrate how the roots shift when translating $p_S(x)$ to $p_S(x+1)$.

**Corollary 3.8.** If $S = \{i_1 < i_2 < \dots < i_s = m < m + 3\}$, then

$$p_S(x+1) = \lim_{t \to x} \frac{(t+1)(t-(m+2))}{(t-m)(t-(m+3))} p_S(t).$$

**Corollary 3.9.** If $S = \{i_1 < i_2 < \dots < i_s = m < m + 3 < m + 5\}$, then

$$p_S(x+1) = \lim_{t \to x} \frac{(t+1)(t-(m-3))(t-(m+2))(t-(m+4))}{(t-(m-2))(t-m)(t-(m+3))(t-(m+5))} p_S(t).$$
A limit is needed in Corollary 3.8 and Corollary 3.9, because $p_S(m + 1)$ is defined and nonzero by Lemma 3.6 and Lemma 3.7, respectively. We now give closed-form formulas for $p_S(x)$ when $S = \{m, m+3, \dots, m+3k\}$ and $S = \{m, m+3, \dots, m+3k, m+3k+2\}$ for $k \ge 1$. These formulas are direct consequences of Lemma 3.6 and Lemma 3.7

**Corollary 3.10.** If $S = \{m, m+3, \dots, m+3k\}$ for $k \ge 1$, then

$$p_S(x) = \frac{(m-1)(x - (m+3k))}{2(m+1)!(12^{k-1})} \prod_{j=0}^{m+3(k-1)} (x-j).$$

**Corollary 3.11.** If $S = \{m, m+3, \dots, m+3k, m+3k+2\}$ for $k \ge 1$, then

$$p_S(x) = \frac{(m-1)(x - (m+3k+2))(x - (m+3k))(x - (m+3k-5))}{(m+1)!(12^k)} \prod_{j=0}^{m+3(k-1)} (x-j).$$

## 3.3 Gap of three independence

The following theorem shows that if $S$ has a gap of three anywhere, then $p_S(x)$ is independent of the peaks to the left of that gap up to a constant. Furthermore, the complex roots of $p_S(x)$ depend only on the peaks to the right of the gap of three and where this gap occurs. Corollaries of this result follow.

**Theorem 3.12.** Let $S_L = \{i_1 < i_2 < \dots < i_\ell = m\}$ and $S_R = \{2 < j_2 < \dots < j_r\}$. If $S = \{i_1 < i_2 < \dots < m < m+3 < (m+1)+j_2 < \dots < (m+1)+j_r\}$, then

$$p_S(x) = \frac{p_{S_L}(m+1)}{2(m+1)!} p_{S_R}(x - (m+1)) \prod_{k=0}^{m} (x-k).$$

We see that 0, 1, 2, ..., $m$ are zeros of $p_S(z)$, and the roots of $p_{S_R}(z)$ are roots of $p_S(z)$ when translated to the right by $m+1$ in the complex plane. Note that $\deg(p_S(x)) = m + j_r$ because $\max(S) = (m+1) + j_r$, but we also see this by counting the $m+1$ leftmost integer roots and then the $j_r-1$ roots of $p_{S_R}(x)$. Theorem 3.12 also implies Lemma 3.6 when $S_R = \{2\}$ for all $S_L$ because $p_{\{2\}}(x) = x-2$. The plots and corollaries below demonstrate this independence.

<figure><img src="image_2.png" /><figcaption>Fig. 1: Roots of $p_{\{2,10\}}(z)$.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2: Roots of $p_{\{4,7,15\}}(z)$.</figcaption></figure>
**Corollary 3.13.** Let $S_L = \{i_1 < i_2 < \dots < i_\ell = m\}$, $S_R = \{j_1 = 2 < j_2 < \dots < j_r\}$, and $S = \{i_1 < i_2 < \dots < m < m+3 < (m+1)+j_2 < \dots < (m+1)+j_r\}$. If $S_R$ has no zero with real part greater than $j_r$, then $p_S(x)$ has no zero with real part greater than $\max(S)$.

*Proof.* The proof follows from Theorem 3.12. □

If we want to verify that Conjecture 2.3 holds for a peak set $S$ with a gap of three, then it suffices to check that it holds for $S_R$ by Corollary 3.13.

**Corollary 3.14.** Let $S_L = \{i_1 < i_2 < \dots < i_\ell = m\}$, $S_R = \{j_1 = 2 < j_2 < \dots < j_r\}$, and $S = \{i_1 < i_2 < \dots < m < m+3 < (m+1)+j_2 < \dots < (m+1)+j_r\}$. If we define $S+1 = \{i+1 : i \in S\}$, then

$$p_{S+1}(x) = C(S)p_S(x-1)x,$$

where

$$C(S) = \frac{p_{S_L+1}(m+2)}{(m+2)p_{S_L}(m+1)}$$

is a constant depending only on $S$.

Observe that Corollary 3.14 shifts all of the zeros of $p_S(z)$ in the complex plane to the right by one and then picks up a new root at 0 since $C(S)$ is a constant. The plots below illustrate this behavior.

<figure><img src="image_4.png" /><figcaption>**Fig. 3:** Roots of $p_{\{3,5,8,14\}}(z)$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Fig. 4:** Roots of $p_{\{4,6,9,15\}}(z)$.</figcaption></figure>

# 4 Evaluating $p_S(x)$ at nonnegative integers

In the previous section, we identified integral roots of $p_S(x)$, so now we will try to understand the behavior of $p_S(x)$ at nonnegative integers $j$ when $p_S(j) \neq 0$. We prove that there is a curious symmetry between column and row 0 in the table of forward differences of $p_S(x)$ (see Table 2), and that the nonzero values of $|p_S(j)|$ are weakly increasing for $j \in [\max(S) - 1]$ when $\min(S) \geq 4$. Again, assume that $S$ is a nonempty admissible set in the following hypotheses.

**Theorem 4.1.** Let $S \neq \emptyset$ and $m = \max(S)$. If $j \in \{0, 1, \dots, m\}$, then

$$(\Delta^j p_S)(0) = (-1)^{m+j} p_S(j).$$
For example, if $j > 0$ is between the largest odd gap and $m$, then by this symmetry property and Theorem 1.2 one can observe that

$$p_S(j) = (-1)^{m+j} (\Delta^j p_S)(0) = -(-2)^{|S \cap (j, \infty)|-1} p_{S \cap [j]}(j).$$

If $S$ has no odd gaps, then the equation above holds for all $j \in [m]$.

**Lemma 4.2.** If $S \neq \emptyset$ and $m = \max(S)$, then $p_S(j) < p_S(j+1)$ for $j \ge m$.

**Theorem 4.3.** Let $S = \{i_1 < i_2 < \cdots < i_s = m\}$. For integers $1 \le j < k$, we have $|p_S(j)| \le |p_S(k)|$ provided $p_S(k) \ne 0$, except for the case $\{2\} \subseteq S$ where $p_S(1) = 2p_S(3) = -(-2)^{|S|-1}$.

**Corollary 4.4.** Let $S$ be a set of positive integers and $j$ be a positive integer such that $p_S(j) \ne 0$. Let $k \ge j$ integer. If $p_S(k) = 0$ then $k \in S$.

# 5 Connections to alternating permutations

In this section, we enumerate permutations with a given peak set using alternating permutations and tangent numbers instead of the recurrence given by Lemma 3.1. Alternating permutations allow us to easily count the number of permutations whose peak set is a superset of $S$, so we combine this idea with the inclusion-exclusion principle to evaluate $|\mathcal{P}_S(n)|$.

Assume that $S$ is a nonempty admissible peak set and that $m = \max(S)$. Let $\mathcal{Q}_S(n) = \{\pi \in \mathfrak{S}_n : S \subseteq P(\pi)\}$ be the set of permutations $\pi \in \mathfrak{S}_n$ whose peak set contains $S = \{i_1 < i_2 < \cdots < i_s\}$, and let us partition $S$ into runs of alternating substrings. An alternating substring is a maximal size subset $A_r$ such that $A_r = \{i_r, i_r+2, \dots, i_r+2(k-1)\} \subseteq S$, where $i_r - i_{r-1} \ge 3$ if $i_{r-1} \in S$, and we call $A_r$ an alternating substring because

$$\pi_{i_r-1} < \pi_{i_r} > \pi_{i_r+1} < \pi_{i_r+2} > \cdots < \pi_{i_r+2(k-1)} > \pi_{i_r+2(k-1)+1}$$

is an alternating permutation in $\mathfrak{S}_{2k+1}$ under an order-preserving map. Alternating permutations have peaks at every even index, and there are $E_{2k+1}$ of them in $\mathfrak{S}_{2k+1}$. The numbers $E_{2k+1}$ are the tangent numbers given by the generating function

$$\tan x = \sum_{k=0}^{\infty} \frac{E_{2k+1}}{(2k+1)!} x^{2k+1} \\ = x + \frac{1}{3}x^3 + \frac{2}{15}x^5 + \frac{17}{315}x^7 + \dots$$

In 1879, André proved this result in [1] using a generating function that satisfies a differential equation. See [20] for more background on alternating permutations.

Call an index $i$ a free index of peak set $S$ if $i \in [m+2]$ and $i$ is neither a peak nor adjacent to a peak in $S$. The following theorem gives us a closed-form expression of tangent numbers for $|\mathcal{P}(m+1)|$ and $|\mathcal{P}(m+2)|$ when $S$ has no free indices. Note that if $S$ has no free indices, then it can be thought of as separate independent alternating permutations that are concatenated to each other, similar to the independence in Theorem 3.12.

**Lemma 5.1.** If $S$ has no free indices and $k \in [2]$, then

$$|\mathcal{P}_S(m+k)| = (m+k)! \prod_{A_r \in \mathcal{A}(S)} \frac{E_{2|A_r|+1}}{(2|A_r|+1)!}.$$
## 6 Related work and conjectures

In this final section, we relate our work to other recent results about permutations with a given peak set, and we also restate some conjectures that stemmed from our work. Kasraoui characterized in [16] which peak sets $S$ maximize $|\mathcal{P}_S(n)|$ for $n \ge 6$ and explicitly computed $|\mathcal{P}_S(n)|$ for such sets $S$. We compute the maximum $|\mathcal{P}_S(n)|$ in a different way using alternating permutations.

**Theorem 6.1 ([16, Theorem 1.1, 1.2]).** For $n \ge 6$, the sets $S$ that maximize $|\mathcal{P}_S(n)|$ are

$$ S = \begin{cases} \{3, 6, 9, \dots\} \cap [n-1] & \text{and} \quad \{4, 7, 10, \dots\} \cap [n-1] & \text{if } n \equiv 0 \pmod 3, \\ \{3, 6, 9, \dots, 3s, 3s+2, 3s+5, \dots\} \cap [n-1] & \text{for } 1 \le s \le \lfloor \frac{n}{3} \rfloor & \text{if } n \equiv 1 \pmod 3, \\ \{3, 6, 9, \dots\} \cap [n-1] & \text{if } n \equiv 2 \pmod 3. \end{cases} $$

**Theorem 6.2 ([16, Theorem 1.2]).** Suppose $n \ge 6$ and $S$ maximizes $|\mathcal{P}_S(n)|$. Set $\ell = \lfloor \frac{n}{3} \rfloor$. Then we have

$$ |\mathcal{P}_S(n)| = \begin{cases} \frac{1}{5}3^{2-\ell}n! & \text{if } n \equiv 0 \pmod 3, \\ \frac{2}{5}3^{1-\ell}n! & \text{if } n \equiv 1 \pmod 3, \\ 3^{-\ell}n! & \text{if } n \equiv 2 \pmod 3. \end{cases} $$

*Alternative proof.* We work by cases using Theorem 6.1. When $n \equiv 0 \pmod 3$, there is only one admissible superset of $S$, which we call $T$. Using Lemma 5.1 and the inclusion-exclusion principle,

$$ \begin{aligned} |\mathcal{P}_S(n)| &= |\mathcal{Q}_S(n)| - |\mathcal{Q}_T(n)| \\ &= n! \left(\frac{1}{3}\right)^{\ell-1} - n! \left(\frac{1}{3}\right)^{\ell-2} \left(\frac{2}{15}\right) \\ &= \frac{1}{5} 3^{2-\ell} n! , \end{aligned} $$

as desired. We also use Lemma 5.1 to prove the cases $n \equiv 1, 2 \pmod 3$, which are simpler because there are no admissible supersets of $S$. $\square$

Another new result in [11] shows that the number of permutations with the same peak set for signed permutations can be enumerated using the peak polynomial $p_S(x)$ for unsigned permutations. Again, we present an alternate proof, and it can be used to reduce many signed permutation statistic problems to unsigned permutation statistic problems. We denote the group of signed permutations as $B_n$.

**Theorem 6.3 ([11, Theorem 2.7]).** Let $|\mathcal{P}_S^*(n)|$ be the number of signed permutations $\pi \in B_n$ with peak set $S$. We have $|\mathcal{P}_S^*(n)| = p_S(n)2^{2n-|S|-1}$, where $p_S(x)$ is the same peak polynomial used to count unsigned permutations $\pi \in \mathfrak{S}_n$ with peak set $S$.

*Alternative proof.* We naturally partition $B_n$ by the signage of the permutations, which gives us $2^n$ copies of $\mathfrak{S}_n$ under an order-preserving map, and then we work in each copy of $\mathfrak{S}_n$ separately. For example, $B_3 = \{\mathfrak{S}_{+++}, \mathfrak{S}_{++-}, \mathfrak{S}_{+-+}, \mathfrak{S}_{+-}\mathfrak{S}_{-+}, \mathfrak{S}_{-+}, \mathfrak{S}_{--}, \mathfrak{S}_{---}\}$, and $\mathfrak{S}_{++-}$ are the permutations of $\{1, 2, -3\}$. It follows that $|\mathcal{P}_S^*(n)| = 2^n|\mathcal{P}_S(n)|$, so $|\mathcal{P}_S^*(n)| = p_S(n)2^{2n-|S|-1}$ by Theorem 1.1. $\square$
Now we restate some conjectures. In [13] we checked Conjecture 6.4 for all admissible peak sets $S$ where $\max(S) \le 15$, and this conjecture implies the truth of Conjecture 2.3. We have also shown in Subsection 3.2 that the peak sets listed in Conjecture 6.5 have only integral roots, but we have not proven the other direction. Conjecture 6.6 is an observation that is related to Conjecture 6.4, and we have proved it for all integral $x_0$ using Lemma 4.2, but not all real $x_0$.

**Conjecture 6.4.** The complex roots of $p_S(n)$ lie in $\{z \in \mathbb{C} : |z| \le m \text{ and } \text{Re}(z) \ge -3\}$ if $S$ is admissible.

**Conjecture 6.5.** If $S = \{i_1 < i_2 < \cdots < i_s\}$ is admissible and all of the roots of $p_S(n)$ are real, then all of the roots of $p_S(n)$ are integral. Furthermore, $p_S(n)$ has all real roots if and only if $S = \{2\}$, $S = \{2, 4\}$, $S = \{3\}$, $S = \{3, 5\}$, $S = \{i_1 < i_2 < \cdots < i_s < i_s+3\}$, or $S = \{i_1 < i_2 < \cdots < i_s < i_s+3 < i_s+5\}$.

**Conjecture 6.6.** Let $S$ be admissible and $|S| \ge 2$. If $p_S(x_0) = 0$ for $x_0 \in \mathbb{R}$, then $x_0 > \max(S_1)$ if and only if $x_0 = \max(S)$.

**Question 6.7.** What does $p_S(n)$ count for $n > \max(S)$?

## Acknowledgements

We would like to thank Jim Morrow first and foremost for organizing the University of Washington Mathematics REU for over 25 years. We also would like to thank Ben Braun, Tom Edwards, Richard Ehrenborg, Noam Elkies, Daniel Hirsbrunner, Jerzy Jaromczyk, Beth Kelly, Ethan Linville, Etienne Rassart, and Austin Tran for their discussions with us about various results in this paper.

## References

[1] D. André, Développement de $\sec x$ et $\tg x$, *Comptes Rendus Mathématique* **88** (1879), 965-979.

[2] M. Beck, J. A. De Loera, M. Develin, J. Pfeifle, R. P. Stanley, Coefficients and roots of Ehrhart polynomials, *Integer Points in Polyhedra–Geometry, Number Theory, Representation Theory, Algebra, Optimization, Statistics*, Contemporary Mathematics **374** (2005), 15–36.

[3] S. Billey, K. Burdzy, B. E. Sagan, Permutations with Given Peak Set, *Journal of Integer Sequences* **16** (2013), Article 13.6.1.

[4] S. Billey, M. Fahrbach, A. Talmage, Coefficients and roots of peak polynomials. Preprint available at http://arxiv.org/abs/1410.8506.

[5] M. Bóna, *Combinatorics of Permutations*, Book 72 of *Discrete Mathematics and Its Applications*, Chapman and Hall/CRC, 2nd edition, 2012.

[6] B. Braun, M. Develin, Ehrhart polynomial roots and Stanley's non-negativity theorem, *Integer Points in Polyhedra–Geometry, Number Theory, Representation Theory, Algebra, Optimization, Statistics*, Contemporary Mathematics **452** (2008), 67–78.

[7] F. Brenti, Expansions of chromatic polynomials and log-concavity, *Transactions of the American Mathematical Society* **332** (1992), No. 2, 729–756.

[8] F. Brenti, G. F. Royle, D. G. Wagner, Location of zeros of chromatic and related polynomials in graphs, *Canadian Journal of Mathematics* **46** (1994), No. 1, 55–80.
[9] D. Bump, K. Choi, P. Kurlberg, Jeffrey Vaaler, A Local Riemann Hypothesis, I, *Mathematische Zeitschrift* **233** (2000), No. 1, 1–19.

[10] S. Billey, K. Burdzy, S. Pal, B. E. Sagan, On meteors, earthworms and WIMPs. To appear *Annals of Applied Probability* Preprint available at http://arxiv.org/abs/1308.2183.

[11] F. Castro-Velez, A. Diaz-Lopez, R. Orellana, J. Pastrana, R. Zevallos, Number of permutations with same peak set for signed permutations. Preprint available at http://arxiv.org/abs/1308.6621.

[12] C. de Boor, Divided Differences, *Surveys in Approximation Theory* **1** (2005), 46–69.

[13] M. Fahrbach, Peak polynomials and their complex zeros, http://www.math.washington.edu/~billey/papers/factoring_peak_polynomials_data.pdf.

[14] A. E. Holroyd, T. M. Liggett, Finitely Dependent Coloring. Preprint available at http://arxiv.org/abs/1403.2448.

[15] G. Jameson, Interpolating polynomials and divided differences, http://www.maths.lancs.ac.uk/~jameson/interpol.pdf.

[16] A. Kasraoui, The most frequent peak set in a random permutation. Preprint available at http://arxiv.org/abs/1210.5869.

[17] W. O. Kermack, A. G. McKendrick, Tests for randomness in a series of numerical observations, *Proceedings of the Royal Society Edinburgh* **57** (1937), 228–240.

[18] J. Pfeifle, Gale duality bounds for roots of polynomials with nonnegative coefficients, *Journal of Combinatorial Theory* **117** (2010), Series A, 248–271.

[19] F. Rodriguez-Villegas, On the zeros of certain polynomials, *Proceedings of the American Mathematical Society* **130** (2002), No. 8, 2251–2254.

[20] R. P. Stanley, *A survey of alternating permutations*, *Contemporary Mathematics* **531** (2010), 165–196.

[21] R. P. Stanley, *Enumerative Combinatorics, Volume 1*, Vol. 49 of *Cambridge Studies in Advanced Mathematics*, Cambridge University Press, 2nd edition, 2012.

[22] W. A. Stein et al., *Sage Mathematics Software (Version 5.10)*, The Sage Development Team, 2013, http://www.sagemath.org.