# The Eulerian polynomials of type D have only real roots

Carla D. Savage<fnref n="1" /> and Mirkó Visontai<fnref n="2" />

**Abstract.** We give an intrinsic proof of a conjecture of Brenti that all the roots of the Eulerian polynomial of type D are real and a proof of a conjecture of Dilks, Petersen, and Stembridge that all the roots of the affine Eulerian polynomial of type B are real, as well.

**Résumé.** Nous prouvons, de façon intrinsèque, une conjecture de Brenti affirmant que toutes les racines du polynôme eulérien de type D sont réelles. Nous prouvons également une conjecture de Dilks, Petersen, et Stembridge que toutes les racines du polynôme eulérien affine de type B sont réelles.

**Keywords:** Eulerian polynomials, Coxeter group of type D, inversion sequences, polynomials with only real roots.

## 1 Overview

Let $\mathfrak{S}_n$ denote the group of all permutations of the set $[n] = \{1, 2, \dots, n\}$. The descent set of a permutation $\pi$ in $\mathfrak{S}_n$ (given in its one-line notation $\pi = \pi_1 \cdots \pi_n$) is defined as

$$ \text{Des } \pi = \{i \in [n-1] : \pi_i > \pi_{i+1}\}. $$

The Eulerian polynomial, $S_n(x)$, is the generating function for the statistic $\text{Des } \pi = |\text{Des } \pi|$ on $\mathfrak{S}_n$:

$$ S_n(x) = \sum_{\pi \in \mathfrak{S}_n} x^{\text{des } \pi}. \qquad (1) $$

In addition to its many notable properties, $S_n(x)$ has only real roots, which implies that its coefficient sequence, the Eulerian numbers, is unimodal and log-concave.

The notion of descents, and therefore Eulerian polynomials, extends to all finite Coxeter groups. Brenti conjectured (Conjecture 5.1 in Brenti (1994)) that the Eulerian polynomials for all finite Coxeter groups have only real roots. He proved this to be the case for the exceptional groups and for type B. The main goal of this paper is to prove the last missing part of Brenti's conjecture, for type D groups:

**Conjecture 1.1 (Conjecture 5.2 in Brenti (1994))** The type D Eulerian polynomials have only real roots.

<footnote n="1">¹Department of Computer Science, North Carolina State University, Raleigh, NC</footnote>

<footnote n="2">²Department of Mathematics, Royal Institute of Technology, Stockholm 100 44, Sweden</footnote>
To be precise, we view the Coxeter group of type B (resp. D) of rank n, denoted by $\mathfrak{B}_n$ (resp. $\mathfrak{D}_n$), as the set of signed (resp. even-signed) permutations of the set $[n]$. The type B and D descents have the following simple combinatorial interpretation (see Brenti (1994); Björner and Brenti (2005)). For a signed (resp. even-signed) permutation $\sigma$ given in its “window notation” $(\sigma_1, \dots, \sigma_n)$, let

$$ \mathrm{Des}_B \sigma = \{i \in [n-1] : \sigma_i > \sigma_{i+1}\} \cup \{0 : \text{if } \sigma_1 < 0\}, \quad (2) $$

$$ \mathrm{Des}_D \sigma = \{i \in [n-1] : \sigma_i > \sigma_{i+1}\} \cup \{0 : \text{if } \sigma_1 + \sigma_2 < 0\}. \quad (3) $$

The type B and type D Eulerian polynomials are, respectively,

$$ B_n(x) = \sum_{\sigma \in \mathfrak{B}_n} x^{\mathrm{des}_B \sigma} \quad \text{and} \quad D_n(x) = \sum_{\sigma \in \mathfrak{D}_n} x^{\mathrm{des}_D \sigma}, $$

where $\mathrm{des}_B \sigma = |\mathrm{Des}_B \sigma|$ and $\mathrm{des}_D \sigma = |\mathrm{Des}_D \sigma|$.

Our approach is novel and general. It applies not only to type D, but also—as we will see—to the type A and type B Eulerian polynomials. Moreover, we will apply our method to the *affine* Eulerian polynomials proposed by Dilks, Petersen, and Stembridge (2009). In doing so, in Section 8, we will resolve another conjecture:

**Conjecture 1.2 (Dilks et al. (2009))** *The affine Eulerian polynomials of type B have only real roots.*

The type A and C affine Eulerian polynomials are multiples of the classical Eulerian polynomial and hence, have only real roots. However, the affine type D case remains open. See discussion in Section 8.

Our method makes use of the *s*-inversion sequences and their *ascent* statistic, defined in the Section 3. These were inspired by lecture hall partitions Bousquet-Mélou and Eriksson (1997) and introduced in Savage and Schuster (2012). The method works as follows.

* First, encode each element, $w$, of the Coxeter group as an *s*-inversion sequence, $e$, in such a way that the descent set of $w$ is the same as the ascent set of $e$ (Sections 2,3 and 4).

* Secondly, observe that (a refinement of) the generating polynomial for the number of ascents over inversion sequences satisfies a recurrence of a certain form (Section 5).

* Finally, show that the polynomials defined by such recurrences are “compatible” (a notion closely related to interlacing) to deduce that the Eulerian polynomials have all roots real (Sections 6, 7).

## 2 Type D Eulerian polynomials

Let us start with a simple observation. Note that the type D descent statistic, $\mathrm{Des}_D$, defined in (3) can be extended to all signed permutations. Furthermore, $\mathrm{Des}_D$ is equidistributed over even-signed and odd-signed permutations. In other words, we have the following equality.

**Proposition 2.1** For $n \ge 2$,

$$ \sum_{\sigma \in \mathfrak{B}_n} x^{\mathrm{des}_D \sigma} = 2 \sum_{\sigma \in \mathfrak{D}_n} x^{\mathrm{des}_D \sigma}. $$
**Proof:** The involution on $\mathfrak{B}_n$ that swaps the values 1 and $-1$ in (the window notation of) $\sigma \in \mathfrak{B}_n$ is a bijection between $\mathfrak{D}_n$ and $\mathfrak{B}_n \setminus \mathfrak{D}_n$ that preserves the type $D$ descent statistic. $\square$

Therefore, in order to avoid dealing with the parity of the signs and to allow for simpler recurrences, we will be working instead with the polynomial

$$T_n(x) = \sum_{\sigma \in \mathfrak{B}_n} x^{\mathrm{des}_D \sigma}. \qquad (4)$$

Clearly, $T_n(x)$ has only real roots if and only if $D_n(x)$ does. In what follows, we will restrict our attention to permutations and signed permutations, with the goal of showing $T_n(x)$ has all real roots.

## 3 s-Inversion sequences and s-Eulerian polynomials

For a sequence $s = s_1, s_2, \dots$ of positive integers, the set $I_n^{(s)}$ of s-inversion sequences of length $n$ is defined by

$$I_n^{(s)} = \{e \in \mathbb{Z}^n : 0 \le e_i < s_i\}.$$

The ascents of an inversion sequence $e \in I_n^{(s)}$ are the elements of the set

$$\mathrm{Asc} e = \left\{ i \in [n-1] : \frac{e_i}{s_i} < \frac{e_{i+1}}{s_{i+1}} \right\} \cup \{0 : \text{ if } e_1 > 0\}.$$

The s-Eulerian polynomial, $E_n^{(s)}(x)$, is the generating polynomial for the ascent statistic $\mathrm{asc} e = |\mathrm{Asc} e|$ on $I_n^{(s)}$:

$$E_n^{(s)}(x) = \sum_{e \in I_n^{(s)}} x^{\mathrm{asc} e}.$$

Our main result is the following theorem which we will prove in Section 6.

**Theorem 3.1** For any $n \ge 1$ and any sequence $s$ of positive integers, $E_n^{(s)}(x)$ has only real roots.

Consequently, to show the real-rootedness of a family of polynomials, it suffices to show that it is equal to $E_n^{(s)}(x)$ for some sequence $s$ of positive integers. For example, the type A and type B Eulerian polynomials have the following form (we defer the proof to Section 4).

**Proposition 3.2 (Savage and Schuster (2012))** For $n \ge 1$,

$$S_n(x) = E_n^{(1,2,\dots,n)}(x), \qquad (5)$$

$$B_n(x) = E_n^{(2,4,\dots,2n)}(x), \qquad (6)$$

from which it follows by Theorem 3.1 that $S_n(x)$ and $B_n(x)$ have only real roots.

In this paper, we will show how to adapt this idea to type D and affine type B Eulerian polynomials.
# 4 Inversion sequence representation of (signed) permutations

To simplify notation for inversion sequences, let

$$I_n = I_n^{(1,2,...,n)} \text{ and } I_n^B = I_n^{(2,4,...,2n)}.$$

In this section, we will prove bijections that imply not only the inversion sequence representations for $\mathfrak{S}_n$ (5) and $\mathfrak{B}_n$ (6), but also the following, novel, inversion sequence representation for $\mathfrak{D}_n$.

**Proposition 4.1** For $n \ge 1$,

$$T_n(x) = \sum_{e \in I_n^B} x^{\text{asc}_D e},$$

where $\text{asc}_D e = |\text{Asc}_D e|$ is the number of type D ascents of $e = (e_1, \dots, e_n) \in I_n^B$ given by

$$\text{Asc}_D e = \left\{ i \in [n-1] : \frac{e_i}{i} < \frac{e_{i+1}}{i+1} \right\} \cup \left\{ 0 : \text{ if } e_1 + \frac{e_2}{2} \ge \frac{3}{2} \right\}. \quad (7)$$

## 4.1 An inversion sequence for permutations

We will make use of the following bijection between permutations and inversion sequences (see, for example, Lemma 1 in (Savage and Schuster, 2012)). We note that several variants of this map are known under different names: inversion table, Lehmer code, etc.

**Lemma 4.2** The mapping $\phi: \mathfrak{S}_n \to I_n$ defined by $\phi(\pi_1\pi_2\cdots\pi_n) = (t_1, t_2, \dots, t_n)$, where

$$t_i = |\{j \in [i-1] : \pi_j > \pi_i\}|$$

is a bijection satisfying

$$\pi_i > \pi_{i+1} \text{ if and only if } t_i < t_{i+1}, \text{ for } i \in [n-1].$$

**Proof:** First, $\pi_i > \pi_{i+1}$ if and only if the set $\{j \in [i-1] \mid \pi_j > \pi_i\}$ is a proper subset of the set $\{j \in [i] \mid \pi_j > \pi_{i+1}\}$, which happens if and only if $t_i < t_{i+1}$.

Clearly, $\phi(\mathfrak{S}_n) \subseteq I_n$. In particular, $t_1 = 0$ and $t_n = n - \pi_n$. It is clear that $\phi$ is a bijection for $n = 1$. Let $(t_1, \dots, t_n) \in I_n$ for some $n > 1$ and assume that $\phi$ is a bijection for smaller dimensions. Let $\pi_1 \cdots \pi_{n-1} = \phi^{-1}(t_1, \dots, t_{n-1})$. Then $\phi^{-1}(t_1, \dots, t_n) = \pi'_1 \cdots \pi'_n$, where $\pi'_n = n - t_n$ and $\pi'_i = \pi_i + \chi(\pi_i \ge \pi_n)$ for $i \in [n-1]$, where $\chi(P) = 1$ if $P$ is true and 0, otherwise. $\square$

We will also use the following basic but useful observation.

**Proposition 4.3** Let $a, b, p$ be nonnegative integers such that $0 \le a/p < 1$ and $0 \le b/(p+1) < 1$. Then

$$\frac{a}{p} < \frac{b}{p+1} \iff a < b.$$

**Proof:** If $a < b$, then $a+1 \le b$. Thus, since $a < p$, $(p+1)a = pa + a < pa + p = p(a+1) \le pb$. So, $(p+1)a < pb$. Conversely, if $a \ge b$, then $(p+1)a \ge (p+1)b > pb$, so $(p+1)a > pb$. $\square$

**Remark 4.4** The proposition does not hold without the hypothesis. For example, $4 < 5$, but $4/3 > 5/4$.

**Proof of (5) in Proposition 3.2:** Follows from Lemma 4.2 and Proposition 4.3. $\square$
## 4.2 The bijection for signed permutations and its properties

Clearly, the set of signed permutations, $\mathfrak{B}_n$, has the same cardinality as the set of “type B” inversion sequences, $I_n^B$. Next, we define a bijection between these sets that maps type B descents in signed permutations to ascents in the inversion sequences. We will prove several other properties of $\Theta$ as well. Some will be used to establish the real-rootedness of $T_n(x)$—and hence $D_n(x)$—and others will be needed in Section 8 for the affine Eulerian polynomials. Throughout this paper we will assume the natural ordering of integers,

$$-n < \cdots < -1 < 0 < 1 < \cdots < n.$$

**Theorem 4.5** For $\sigma = (\sigma_1, \dots, \sigma_n) \in \mathfrak{B}_n$, let $(t_1, \dots, t_n) = \phi(|\sigma_1| \cdots |\sigma_n|)$ where $\phi$ is the map defined in Lemma 4.2 and $|\sigma_1| \cdots |\sigma_n|$ denotes the underlying permutation in $\mathfrak{S}_n$. Define the map $\Theta : \mathfrak{B}_n \to I_n^B$ as follows. Let

$$\Theta(\sigma) = (e_1, \dots, e_n),$$

$$\text{where, for each } i \in [n], e_i = \begin{cases} t_i & \text{if } \sigma_i > 0, \\ 2i - 1 - t_i & \text{if } \sigma_i < 0. \end{cases}$$

Then $\Theta$ is a bijection satisfying the following properties.

1. $\sigma_1 < 0$ if and only if $e_1 > 0$.

2. $\sigma_n > 0$ if and only if $e_n < n$.

3. $\sigma_1 + \sigma_2 < 0$ if and only if $e_1 + \frac{e_2}{2} \ge \frac{3}{2}$.

4. $\sigma_i > \sigma_{i+1}$ if and only if $\frac{e_i}{i} < \frac{e_{i+1}}{i+1}$, for $i \in [n-1]$.

5. $\sigma_{n-1} + \sigma_n > 0$ if and only if $\frac{e_{n-1}}{n-1} + \frac{e_n}{n} < \frac{2n-1}{n}$.

**Proof:** $\Theta$ is a bijection since $\phi$ is. Note that $\sigma_i < 0$ if and only if $e_i \ge i$ which proves 1. and 2.

3. It is not too hard to see that it is sufficient to verify this claim for all $\sigma \in \mathfrak{B}_2$. See Table 1.

<table><caption>**Tab. 1:** An example of the bijection for $n = 2$.</caption><thead><tr><th>σ ∈ B<sub>2</sub></th><th>e ∈ I<sub>2</sub><sup>B</sup></th><th>Asc<sub>D</sub> e</th><th>asc<sub>D</sub> e</th></tr></thead><tbody><tr><td>(1,2)</td><td>(0,0)</td><td>{}</td><td>0</td></tr><tr><td>(-1,2)</td><td>(1,0)</td><td>{}</td><td>0</td></tr><tr><td>(2,1)</td><td>(0,1)</td><td>{1}</td><td>1</td></tr><tr><td>(-2,1)</td><td>(1,1)</td><td>{0}</td><td>1</td></tr><tr><td>(2,-1)</td><td>(0,2)</td><td>{1}</td><td>1</td></tr><tr><td>(-2,-1)</td><td>(1,2)</td><td>{0}</td><td>1</td></tr><tr><td>(1,-2)</td><td>(0,3)</td><td>{0,1}</td><td>2</td></tr><tr><td>(-1,-2)</td><td>(1,3)</td><td>{0,1}</td><td>2</td></tr></tbody></table>

4. To prove this claim, we consider four cases, based the signs of $\sigma_i$ and $\sigma_{i+1}$.
(a) If $\sigma_i > 0$ and $\sigma_{i+1} > 0$. Then $e_i = t_i < i$ and $e_{i+1} = t_{i+1} < i+1$. By Lemma 4.2, $\sigma_i > \sigma_{i+1}$ if and only if $t_i < t_{i+1}$, i.e, if and only if $e_i < e_{i+1}$. By Proposition 4.3, this is equivalent to $e_i/i < e_{i+1}/(i+1)$.

(b) If $\sigma_i < 0$ and $\sigma_{i+1} < 0$. Then $e_i = 2i-1-t_i$ and $e_{i+1} = 2(i+1)-1-t_{i+1}$. Now $\sigma_i > \sigma_{i+1}$ if and only if $|\sigma_i| < |\sigma_{i+1}|$, which, applying Lemma 4.2, is equivalent to $t_i \ge t_{i+1}$. If $t_i \ge t_{i+1}$,

$$ \frac{e_i}{i} = 2 - \frac{t_i + 1}{i} \le 2 - \frac{t_{i+1} + 1}{i} < 2 - \frac{t_{i+1} + 1}{i+1} = \frac{e_{i+1}}{i+1}. $$

On the other hand, if $t_i < t_{i+1}$, then $t_i + 1 \le t_{i+1}$ and by Proposition 4.3, $t_{i+1}/i < (t_{i+1} + 1)/(i+1)$, so

$$ \frac{e_i}{i} = 2 - \frac{t_i + 1}{i} \ge 2 - \frac{t_{i+1}}{i} > 2 - \frac{t_{i+1} + 1}{i+1} = \frac{e_{i+1}}{i+1}. $$

(c) If $\sigma_i < 0 < \sigma_{i+1}$. In this case, $e_i = 2i-1-t_i$ and $e_{i+1} = t_{i+1} \le i$. Since $t_i \le i-1$, $e_i \ge 2i-1-(i-1)=i$. Thus we have

$$ \frac{e_i}{i} \ge 1 > \frac{i}{i+1} \ge \frac{e_{i+1}}{i+1}. $$

(d) If $\sigma_i > 0 > \sigma_{i+1}$. In this case, $e_i = t_i < i$ and $e_{i+1} = 2(i+1)-1-t_{i+1}$. Since $t_{i+1} \le i$, $e_{i+1} \ge 2(i+1)-1-(i)=i+1$. Thus we have

$$ \frac{e_i}{i} < 1 \le \frac{e_{i+1}}{i+1}. $$

5. The proof of this claim is a tedious case analysis which we defer to the full paper. We make use of the fifth claim only at the end of the paper where we propose an inversion sequence characterization of the type D affine Eulerian polynomials.

□

**Proof of (6) in Proposition 3.2:** Follows from Theorem 4.5 (parts 1 and 4).

□

**Remark 4.6** The bijection $\Theta$ is different from the one given in (Pensyl and Savage, 2013).

**Proof of Proposition 4.1:** Follows from Theorem 4.5 (parts 3 and 4).

□

For example, for $n=2$, from Table 1, $T_2(x) = 2+4x+2x^2 = 2D_2(x)$, as expected.
## 5 A recurrence for refined Eulerian polynomials

The inversion sequence representation of $E_n^{(s)}(x)$ and $T_n(x)$ allows us to refine these polynomials as follows. Let $\chi(P) = 1$ if $P$ is true and let $\chi(P) = 0$, otherwise. Define

$$E_{n,i}^{(s)}(x) = \sum_{e \in I_n^{(s)}} \chi(e_n = i) \cdot x^{\text{asc } e}, \qquad (8)$$

$$T_{n,i}(x) = \sum_{e \in I_n^B} \chi(e_n = i) \cdot x^{\text{asc}_D e}. \qquad (9)$$

Clearly, $E_n^{(s)}(x) = \sum_{i=0}^{s_i} E_{n,i}^{(s)}(x)$ and $T_n(x) = \sum_{i=0}^{2n-1} T_{n,i}(x)$. We have the following recurrences.

**Proposition 5.1** Let $s = \{s_i\}_{i=1}^\infty$. For $n \ge 1$ and $0 \le i < s_{n+1}$,

$$E_{n+1,i}^{(s)}(x) = \sum_{\ell=0}^{\lfloor ni/(n+1) \rfloor-1} x E_{n,\ell}^{(s)}(x) + \sum_{\ell=\lfloor ni/(n+1) \rfloor}^{s_n-1} E_{n,\ell}^{(s)}(x),$$

with initial conditions $E_{1,0}^{(s)}(x) = 1$ and $E_{1,i}^{(s)}(x) = x$ for $0 < i < s_1$.

**Proof:** Omitted. $\square$

**Proposition 5.2** For $n \ge 2$ and $0 \le i < 2(n+1)$,

$$T_{n+1,i}(x) = \sum_{\ell=0}^{\lfloor ni/(n+1) \rfloor-1} x T_{n,\ell}(x) + \sum_{\ell=\lfloor ni/(n+1) \rfloor}^{2n-1} T_{n,\ell}(x),$$

with initial conditions $T_{2,0}(x) = 2$, $T_{2,1}(x) = T_{2,2}(x) = 2x$, and $T_{2,3}(x) = 2x^2$.

**Proof:** The initial conditions can be checked from the Table 1. For $n \ge 2$ and $e = (e_1, \dots, e_{n+1}) \in I_{n+1}^B$ with $e_{n+1} = i$, let $\ell = e_n$. Then by the definition of the type D ascent set, $n+1 \in \text{Asc}_D e$ if and only if $\ell/n < i/(n+1)$ or, equivalently, whenever $0 \le \ell \le \lfloor ni/(n+1) \rfloor - 1$. So,

$$x^{\text{asc}_D e} = \begin{cases} x^{1+\text{asc}_D(e_1, \dots, e_n)} & \text{if } 0 \le \ell \le \lfloor ni/(n+1) \rfloor - 1 \\ x^{\text{asc}_D(e_1, \dots, e_n)} & \text{if } \lfloor ni/(n+1) \rfloor \le \ell < 2n. \end{cases}$$

$\square$

In Section 7, we will show that $T_{n,i}(x)$ has real roots for all $0 \le i < 2n$ and so also does $T_n(x)$.

## 6 Preserving real-rootedness via compatible polynomials

A classical way to show that a recurrence given by a linear combination of two polynomials preserves real-rootedness is to show that the roots of the two polynomials interlace. We say that two real-rooted polynomials $f(x) = \prod_{i=1}^{\text{deg} f} (x - x_i)$ and $g(x) = \prod_{j=1}^{\text{deg} g} (x - \xi_j)$ interlace if their roots alternate, formally,

$$\dots \le x_2 \le \xi_2 \le x_1 \le \xi_1.$$
Note that this requires the degrees to satisfy the following inequalities: $\deg f \le \deg g \le \deg f + 1$. In particular, the order of polynomials is important.

Interlacing implies real-rootedness by the following theorem.

**Theorem 6.1 (Satz 5.2 in Obreschkoff (1963))** Let $f, g \in \mathbb{R}[x]$. Then $f$ and $g$ interlace if and only if their arbitrary linear combination, $c_1f(x) + c_2g(x)$ for all $c_1, c_2 \in \mathbb{R}$ has only real roots.

Unfortunately, the interlacing property cannot be extended to linear combinations of more than two polynomials (as pointed out in Chudnovsky and Seymour (2007)). So, instead, we will be working with a weaker property, called compatibility, that can be defined for an arbitrary number of polynomials. In fact, these properties are closely related as we will see in Lemmas 6.2 and 6.4.

Following Chudnovsky and Seymour (2007), we call a set of polynomials $f_1, \dots, f_m \in \mathbb{R}[x]$ compatible if their arbitrary conic combination, i.e., $\sum_i c_i f_i(x)$ for $c_i \ge 0$, has real roots only. We say that $f_1, \dots, f_m$ are pairwise compatible if $f_i$ and $f_j$ are compatible for all $1 \le i < j \le m$. Several useful properties of compatible polynomials were summarized in the following lemma.

**Lemma 6.2 (3.6 in Chudnovsky and Seymour (2007))** Let $f_1(x), \dots, f_k(x)$ be polynomials with positive leading coefficients and all roots real. The following four statements are equivalent:

* $f_1, \dots, f_k$ are pairwise compatible,

* for all $s, t$ such that $1 \le s < t \le k$, the polynomials $f_s, f_t$ have a common interlacer,

* $f_1, \dots, f_k$ have a common interlacer,

* $f_1, \dots, f_k$ are compatible,

where $f$ and $g$ have a common interlacer if there is a polynomial $h$ such that $h$ and $f$ interlace and also $h$ and $g$ interlace.

Next we give a transformation that maps a set of compatible polynomials to another set of compatible polynomials under the following conditions.

**Theorem 6.3** Given a set of polynomials $f_1, \dots, f_m \in \mathbb{R}[x]$ with positive leading coefficients that satisfy for all $1 \le i < j \le m$ that

(a) $f_i(x)$ and $f_j(x)$ are compatible, and

(b) $xf_i(x)$ and $f_j(x)$ are compatible

define another set of polynomials $g_1, \dots, g_{m'} \in \mathbb{R}[x]$ by the equations

$$g_k(x) = \sum_{\ell=0}^{t_k-1} x f_{\ell}(x) + \sum_{\ell=t_k}^{m} f_{\ell}(x), \quad \text{for } 1 \le k \le m'$$

where $0 \le t_0 \le t_1 \le \dots \le t_{m'} \le m$. Then, for all $1 \le i < j \le m'$ we have that

(a') $g_i(x)$ and $g_j(x)$ are compatible, and

(b') $xg_i(x)$ and $g_j(x)$ are compatible.
**Proof:** We first show (a'), i.e., that the polynomial $c_ig_i(x) + c_jg_j(x)$ has only real roots for all $c_i, c_j \ge 0$. By the definition of $g_i(x)$, $g_j(x)$ and the assumption that $t_i \le t_j$ it is clear that

$$c_i g_i(x) + c_j g_j(x) = \sum_{\alpha=0}^{t_i-1} (c_i x + c_j x) f_{\alpha}(x) + \sum_{\beta=t_i}^{t_j-1} (c_i + c_j x) f_{\beta}(x) + \sum_{\gamma=t_j}^{m} (c_i + c_j) f_{\gamma}(x),$$

that is, $c_ig_i(x) + c_jg_j(x)$ can be written as a conic combination of the following polynomials, which we group into three (possibly empty) sets:

$$\{xf_{\alpha}(x) : 0 \le \alpha < t_i\} \cup \{(c_i + c_j x)f_{\beta}(x) : t_i \le \beta < t_j\} \cup \{f_{\gamma}(x) : t_j \le \gamma \le m\}.$$

Therefore, it suffices to show that these $m$ polynomials are compatible. In fact, by Lemma 6.2, it is equivalent to show that they are pairwise compatible. This is what we do next.

First, two polynomials from the same sets are compatible by (a). Secondly, a polynomial from the first set is compatible with another from the third set by (b), since $\alpha < \gamma$. To show compatibility between a polynomial from the first set and one from the second, we need that $axf_{\alpha}(x) + b(c_i + c_jx)f_{\beta}(x)$ has only real roots for all $a, b, c_i, c_j \ge 0$ and $\alpha < \beta$. Note that this expression is a conic combination of $xf_{\alpha}(x)$, $xf_{\beta}(x)$, and $f_{\beta}(x)$. Since $\alpha < \beta$, these three polynomials are again pairwise compatible by (a) and (b) (and the basic fact the $f(x)$ and $xf(x)$ are compatible), and hence compatible, by Lemma 6.2. Finally, the compatibility of a polynomial in the second set and one in the third set follows by a similar argument, exploiting the fact that, $xf_{\beta}(x)$, $f_{\beta}(x)$, and $f_{\gamma}(x)$ are pairwise compatible for $\beta < \gamma$.

Now we are left to show (b'), that $xg_i(x)$ and $g_j(x)$ are compatible for all $i < j$. Similarly as before, $c_i xg_i(x) + c_j g_j(x)$ is real-rooted for all $c_i, c_j \ge 0$ if

$$\{x(c_i x + c_j) f_{\alpha}(x) : 0 \le \alpha < t_i\} \cup \{(c_i + c_j) x f_{\beta}(x) : t_i \le \beta < t_j\} \cup \{(c_i x + c_j) f_{\gamma}(x) : t_j \le \gamma \le m\}$$

is a set of compatible polynomials. This follows from analogous reasoning to the above. Two polynomials from the same subsets are compatible by (a). Considering one from the first and one from the third: $xf_{\alpha}(x)$ and $f_{\gamma}(x)$ are compatible by (b). Similarly, $x^2 f_{\alpha}(x)$, $xf_{\alpha}(x)$, and $xf_{\beta}(x)$ are pairwise compatible which settles the case when we have a polynomial from the first and one from the second subset. Finally, $xf_{\beta}(x)$, $xf_{\gamma}(x)$, and $f_{\gamma}(x)$ are compatible, settling the case of one polynomial from the second subset and one from the third. $\square$

**Proof of Theorem 3.1:** We use induction on $n$. When $n = 1$, for $0 \le i \le j < s_1$, $(E_{1,i}^{(s)}(x), E_{1,j}^{(s)}(x)) \in \{(1, 1), (1, x), (x, x)\}$ and thus $(xE_{1,i}^{(s)}(x), E_{1,j}^{(s)}(x)) \in \{(x, 1), (x, x), (x^2, x)\}$. Clearly, each of the pairs of polynomials $(1, 1)$, $(1, x)$, $(x, x)$, $(x^2, x)$, is compatible. From Proposition 5.1 we see that the polynomials $E_{n,i}^{(s)}(x)$ satisfy a recurrence of the form required in Theorem 6.3, hence, by induction, they are real-rooted for all $0 \le i < 2n$. In particular, $E_n^{(s)}(x)$ has only real roots for $n \ge 1$ (and arbitrary sequence $s$). $\square$

## 6.1 Connection to interlacing

The condition of Theorem 6.3 can be simplified since our polynomials have positive coefficients.
**Lemma 6.4** Let $f, g \in \mathbb{R}[x]$ be polynomials with positive coefficients. Then the following are equivalent:

* $f(x)$ and $g(x)$ are compatible, and $xf(x)$ and $g(x)$ are also compatible.

* $f(x)$ and $g(x)$ interlace.

**Proof:** Let $n_f(x_0)$ denote the number of roots of the polynomial $f$ in the interval $[x_0, \infty)$. There is an equivalent formulation for both compatibility and interlacing in terms of this notion. First, $f$ and $g$ are compatible if and only if $|n_f(x_0) - n_g(x_0)| \le 1$ for all $x_0 \in \mathbb{R}$ (see 3.5 in Chudnovsky and Seymour (2007)). Secondly, by definition, $f$ and $g$ interlace, if and only if $0 \le n_g(x_0) - n_f(x_0) \le 1$ for all $x_0 \in \mathbb{R}$. We also have that $n_{xf}(x_0) = n_f(x_0) + \chi(x_0 \le 0)$. Therefore, the following equivalence settles the lemma (since all roots of $f$ and $g$ are nonpositive, we can assume that $x_0 \le 0$):

$$|n_f(x_0) - n_g(x_0)| \le 1 \text{ and } |n_f(x_0) + 1 - n_g(x_0)| \le 1 \iff 0 \le n_g(x_0) - n_f(x_0) \le 1.$$

□

**Remark 6.5** Lemma 6.4 appeared (without a proof) as Lemma 3.4 in Wagner (2000).

# 7 The Eulerian polynomials of type D have only real roots

Now we are in position to prove Conjecture 1.1.

**Theorem 7.1** For $n \ge 2$, the polynomial $T_n(x)$ has only real roots. In fact, for $0 \le i < 2n$, $T_{n,i}(x)$ has only real roots.

**Proof:** Clearly, $T_2(x) = 2(x+1)^2$ has only real roots, but $T_{2,0}(x) = 2$, $T_{2,1}(x) = T_{2,2}(x) = 2x$, $T_{2,3}(x) = 2x^2$ fail to be compatible. Using the recurrence given in Proposition 5.2 we can compute $T_{n,i}$ for $n=3$. It is easy to check that $T_{3,0} = 2(x+1)^2$, $T_{3,1}(x) = 2x(x+3)$, $T_{3,2}(x) = T_{3,3}(x) = 4x(x+1)$, $T_{3,4}(x) = 2x(3x+1)$, $T_{3,5}(x) = 2x(x+1)$ are compatible polynomials—hence $T_3(x)$ has only real roots—but $xT_{3,0}(x)$ and $T_{3,1}(x)$ do not interlace and thus they don't satisfy the assumption needed for Theorem 6.3. However, iterating one more time, we obtain the following polynomials.

$$
\begin{align*}
T_{4,0}(x) &= 2(x + 1)(x^2 + 10x + 1) & \{-9.899, -1, -0.101\} \\
T_{4,1}(x) &= 4x(x + 1)(x + 5) & \{-5, -1, 0\} \\
T_{4,2}(x) &= 2x(3x^2 + 14x + 7) & \{-4.097, -0.569, 0\} \\
T_{4,3}(x) &= 2x(5x^2 + 14x + 5) & \{-2.380, -0.420, 0\} \\
T_{4,4}(x) &= 2x(5x^2 + 14x + 5) & \{-2.380, -0.420, 0\} \\
T_{4,5}(x) &= 2x(7x^2 + 14x + 3) & \{-1.756, -0.244, 0\} \\
T_{4,6}(x) &= 4x(x + 1)(5x + 1) & \{-1, -0.2, 0\} \\
T_{4,7}(x) &= 2x(x + 1)(x^2 + 10x + 1) & \{-9.899, -1, -0.101, 0\}.
\end{align*}
$$

One can check the roots explicitly (approximate values are given above for the reader's convenience) to see that $T_{4,i}(x)$ and $T_{4,i+1}(x)$ interlace for all $0 \le i \le 6$. By Lemma 6.4, this means that the polynomials $T_{4,0}(x), \dots, T_{4,7}(x)$ are compatible and also that $xT_{4,i}(x)$ and $T_{4,j}(x)$ are compatible for $0 \le i < j \le 7$. Therefore, by induction on $n$, and successive applications of Theorem 6.3 we get that for all $n \ge 4$, $\{T_{n,i}(x)\}_{0 \le i \le 2n-1}$ is a set of pairwise interlacing polynomials. In particular, this implies that they are compatible, hence $T_n(x)$ has only real roots for all $n \ge 4$ as well. □
# 8 Further implications: real-rooted affine Eulerian polynomials

Dilks, Petersen, and Stembridge (2009) recently defined Eulerian-like polynomials associated to irreducible affine Weyl groups and proposed two companion conjectures to Brenti's conjecture. In this section, we prove one of them. The affine Eulerian polynomial of type B is defined in (Dilks et al., 2009, Section 5.3) as the generating function of the "affine descents" over the corresponding finite Weyl group, $\mathfrak{B}_n$,

$$ \tilde{B}_n(x) = \sum_{\sigma \in \mathfrak{B}_n} x^{\tilde{\mathrm{des}}_{\mathfrak{B}}\sigma}, $$

where for a signed permutation $\sigma = (\sigma_1, \dots, \sigma_n) \in \mathfrak{B}_n$ the affine descent statistic is computed as

$$ \tilde{\mathrm{des}}_{\mathfrak{B}}\sigma = \chi(\sigma_1 < 0) + |\{i \in [n-1] : \sigma_i > \sigma_{i+1}\}| + \chi(\sigma_{n-1} + \sigma_n > 0). $$

We now prove Conjecture 1.2. Notice the affine Eulerian polynomial of type B is intimately related to the type D Eulerian polynomial in the following way.

**Theorem 8.1** For $n \ge 2$,

$$ \tilde{B}_n(x) = T_{n+1,n+1}(x), $$

where $T_{n,i}(x)$ is the refined Eulerian polynomial of type D defined in (9).

**Proof:** It is easy to see, under the involution $(\sigma_1, \dots, \sigma_n) \mapsto (-\sigma_n, \dots, -\sigma_1)$, that $\tilde{\mathrm{des}}_B$ has the same distribution over $\mathfrak{B}_n$ as the statistic

$$ \tilde{\mathrm{stat}}_{\mathfrak{B}}\sigma = \chi(\sigma_n > 0) + |\{i \in [n-1] : \sigma_i > \sigma_{i+1}\}| + \chi(\sigma_2 + \sigma_1 < 0). $$

From Theorem 4.5 part 3 it follows that $\sigma_2 + \sigma_1 < 0$ is equivalent to $e_1 + e_2/2 > 3/2$ and from part 2 we have that $\sigma_n > 0$ if and only if $e_n < n$. Note that $e_n < n$ is equivalent to $e_n/n < 1 = (n+1)/(n+1)$. So, $\tilde{B}_n(x) = T_{n+1,n+1}(x)$. $\square$

**Corollary 8.2** For $n \ge 2$, $\tilde{B}_n(x)$ has only real roots.

**Proof:** Follows from the fact that $T_{n,i}(x)$ have only real roots (see Theorem 7.1). $\square$

We should mention that there is an analogous conjecture for type D which remains unsolved.

**Conjecture 8.3 (Dilks et al. (2009))** Let

$$ \tilde{\mathrm{des}}_{\mathfrak{D}}\sigma = \chi(\sigma_1 + \sigma_2 < 0) + |\{i \in [n-1] : \sigma_i > \sigma_{i+1}\}| + \chi(\sigma_{n-1} + \sigma_n > 0). $$

Then the affine Eulerian polynomial of type D

$$ \sum_{\sigma \in \mathfrak{D}_n} x^{\tilde{\mathrm{des}}_{\mathfrak{D}}} $$

has only real roots.

By Theorem 4.5 (parts 2, 4 and 5) we can at least express the type D affine Eulerian polynomial in terms of ascent statistics on inversion sequences.
**Corollary 8.4** The type D affine Eulerian polynomial satisfies

$$2 \sum_{\sigma \in \mathcal{D}_n} x^{\tilde{\text{des}}_D \sigma} = \sum_{e \in I_n^B} x^{\tilde{\text{asc}}_D e},$$

where the type D affine ascent statistic is given by

$$\tilde{\text{asc}}_D e = \chi \left( e_1 + \frac{e_2}{2} \ge \frac{3}{2} \right) + \left| \left\{ i \in [n-1] : \frac{e_i}{i} < \frac{e_{i+1}}{i+1} \right\} \right| + \chi \left( \frac{e_{n-1}}{n-1} + \frac{e_n}{n} < \frac{2n-1}{n} \right).$$

## Acknowledgements

We thank the National Science Foundation (grant #1202691 supporting the Triangle Lectures in Combinatorics) and the Simons Foundation (grant #244963) for travel funding that facilitated the research presented here. The second author was also supported by the Knut and Alice Wallenberg Foundation.

Thanks to Thomas Pensyl for his contributions to Theorem 4.5. Special thanks to Christian Krattenthaler for his comments on a partial result presented at the Séminaire Lotharingien de Combinatoire at Strobl that encouraged us to develop our methods for the type D case. We also thank Petter Brändén for helpful suggestions.

## References

A. Björner and F. Brenti. *Combinatorics of Coxeter groups*, volume 231 of *Graduate Texts in Mathematics*. Springer, New York, 2005. ISBN 978-3540-442387; 3-540-44238-3.

M. Bousquet-Mélou and K. Eriksson. Lecture hall partitions. II. *Ramanujan J.*, 1(2):165-185, 1997. URL http://dx.doi.org/10.1023/A:1009768118404.

F. Brenti. *q-Eulerian polynomials arising from Coxeter groups*. *Eur. J. Comb.*, 15:417-441, September 1994. URL http://dx.doi.org/10.1016/eujc.1994.1046.

M. Chudnovsky and P. Seymour. The roots of the independence polynomial of a clawfree graph. *J. Combin. Theory Ser. B*, 97(3):350-357, 2007. URL http://dx.doi.org/10.1016/j.jctb.2006.06.001.

K. Dilks, T. K. Petersen, and J. R. Stembridge. Affine descents and the Steinberg torus. *Adv. in Appl. Math.*, 42(4):423-444, 2009. URL http://dx.doi.org/10.1016/j.aam.2008.11.002.

N. Obreschkoff. *Verteilung und Berechnung der Nullstellen reeller Polynome*. VEB Deutscher Verlag der Wissenschaften, Berlin, 1963.

T. W. Pensyl and C. D. Savage. Lecture hall partitions and the wreath products $C_k \wr S_n$. *Integers*, 2013. To appear.

C. D. Savage and M. J. Schuster. Ehrhart series of lecture hall polytopes and Eulerian polynomials for inversion sequences. *J. Combin. Theory Ser. A*, 119(4):850-870, 2012. URL http://dx.doi.org/10.1016/j.jcta.2011.12.005.

D. G. Wagner. Zeros of reliability polynomials and f-vectors of matroids. *Combin. Probab. Comput.*, 9 (2):167-190, 2000. URL http://dx.doi.org/10.1017/S0963548399004162.