For \(k=1\), the statement holds trivially, since there are no positive transpositions in \(\Pi_1\).

Induction hypothesis. Assume that for some \(k\ge 1\), relation \eqref{eq:1} hold for every \(\pi\in \Pi_k\) and every positive transposition with respect to \(\pi\).

We now prove the claim for \(k+1\). Let \(\pi\in \Pi_{k+1}\). Our goal is to show that relations \eqref{eq:1} also hold for every positive transposition \(\tau_{a,b}\) with respect to \(\pi\) in this case.

Step 1 - Adjacent transpositions Link to heading

First, we prove relation \eqref{eq:1} for adjacent transpositions.

Let \(a\in \{1,\ldots ,2k+1\}\) and let \(\tau_a\) denote a positive adjacent transposition with respect to \(\pi\). We show that

\begin{equation}\label{eq:step1} \Delta_a(\pi):=\mathcal{P}_{k+1}\bigl(\tau_a(\pi)\bigr)-\mathcal{P}_{k+1}(\pi)\ge 0. \end{equation}

Since \(\tau_a\) is positive with respect to \(\pi\), it follows that \(\pi(a)< \pi(a+1)\). In particular, \(\{a,a+1\}\not\in \pi\). By the definition of \(\mathcal{P}_{k+1}\), we therefore obtain

\begin{equation} \mathcal{P}_{k+1}\bigl(\tau_a(\pi)\bigr) - \mathcal{P}_{k+1}(\pi) = \sum_{\substack{p< a <\pi(p), \\ p \neq \pi(a), \pi(a+1)} } \Delta_{p',\pi(p)'}(\rho_a^p(\pi)) + \epsilon_a(\pi) d \mathcal{P}_{k}\bigl(R_a(\pi)\bigr). \label{eq:taua_formula} \end{equation}

Note that, in accordance with the remark in (0x68624c9f) , all terms with \(\pi(p)< a\) have been removed from the sum. In the following, we show that each difference in the sum, as well as \(\epsilon_a(\pi)d\mathcal{P}_k\bigl(R_a(\pi)\bigr)\), has non-negative coefficients. ¹

Step 1.1 - Each difference has non-negative coefficients Link to heading

Let \(p< a\) be such that \(a<\pi(p)\) and \(p\neq \pi(a), \pi(a+1)\). Denote by \(\rel_{a}\) the relabeling map in the definition of \(\rho_{a}^p\). For brevity, we write \(\tilde{n}:=\rel_{a}(n)\). By (0x6881dd71) , we obtain

\[ \rho_{a}^{\pi(p)}(\pi) = \tau_{\tilde{p},\tilde{\pi(p)}}(\rho_{a}^p(\pi)). \]

The transposition \(\tau_{\tilde{p},\tilde{\pi(p)}}\) is positive with respect to \(\pi'=\rho_a^p(\pi)\), because \(\rel_a(p)< \rel_a\bigl(\pi(p)\bigr)\). Moreover, by the construction of \(\rel_a\), we have

\[ \pi'\bigl(\rel_a(p)\bigr)=\rel_a\bigl(\pi(a)\bigr)< \rel_a\bigl(\pi(a+1)\bigr)=\pi'\bigl(\rel_a\bigl(\pi(p)\bigr)\bigr). \]

Applying relation \eqref{eq:1} for \(\mathcal{P}_k\), we conclude that

\[ \mathcal{P}_k\bigl(\rho^{\pi(p)}_a(\pi)\bigr)-\mathcal{P}_k\bigl(\rho^p_a(\pi)\bigr)=\mathcal{P}_k\Bigl(\tau_{p',\pi(p)'}\bigl(\rho^p_a(\pi)\bigr)\Bigr)-\mathcal{P}_k\bigl(\rho^p_a(\pi)\bigr)\ge 0. \]

Step 1.2 - Ricci-deletion term has non-negative coefficients Link to heading

Because \(\pi(a)<\pi(a+1)\), it follows that \(\epsilon_a(\pi)\ge 0\) . If \(R_a(\pi)\) equals the minimal pairing \(\pi_{k,\min }\), then \(\mathcal{P}_k(R_a(\pi))=t^k\ge 0\). Otherwise, by (0x687552d6) , there exists a finite sequence of positive adjacent transpositions \((\tau_{a_n})_{n=1,\ldots, N}\) with

\[ \pi=\tau_{a_N}\circ \cdots \circ \tau_{a_1}(\pi_{k,\min }). \]

Repeated application of \eqref{eq:1} from the induction hypothesis yields

\[ 0\le t^k=\mathcal{P}_k(\pi_0)\le \mathcal{P}_k\bigl(\tau_{a_1}(\pi_0)\bigr)\le \cdots \le \mathcal{P}_k\bigl(\tau_{a_N}\circ \cdots \circ \tau_{a_1}(\pi_0)\bigr)=\mathcal{P}_k(\pi). \]

Together, Step 1.1 and Step 1.2 establish \eqref{eq:step1}.

Step 2 - Relation \eqref{eq:1} for non-adjacent transpositions Link to heading

Assume, for any \(l\in \{1,\ldots ,2k-2\}\), relation \eqref{eq:1} is true for every pair \(a,b\in \{1,\ldots ,2k+2\}\) with \(a< b\le a+l\). We want to use this assumption to prove relation \eqref{eq:1} for every admissible pair \((a,a+l+1)\), where \(a\in \{1,\ldots ,2k+2\}\).

For brevity, we write \(b=a+l+1\). Assume \(\pi\in \Pi_{k+1}\), \(a\in \{1,\ldots ,2k+2\}\) and \(\tau_{a,b}\) is a positive transposition with respect to \(\pi\), i.e.

\[ \pi(a)<\pi(b). \]

According to (0x6892cfdd) , we have

\[ \tau_{a,b}(\pi) = \tau_a\circ \tau_{a+1,b}\circ \tau_a (\pi). \]

To simplify notation, we introduce intermediate pairings

\[ \pi_0:=\pi, \qquad \pi_1 := \tau_a(\pi), \qquad \pi_2:=\tau_{a+1,b}(\pi_1). \]

Then, by telescoping sum argument, it follows that

\begin{equation}\label{eq:main-diff} \Delta_{a,b}(\pi) = \Delta_{a}(\pi_0) + \Delta_{a+1,b}(\pi_1) + \Delta_{a}(\pi_2). \end{equation}

In the next steps we prove \(\Delta_{a+1,b}(\pi_1)\ge 0\) and \(\Delta_a(\pi_0)+\Delta_a(\pi_2)\ge 0\).

Step 2.1 - Non-negativity of \(\Delta_{a+1,b}(\pi_1)\) Link to heading

By construction, \(\tau_{a+1,b}\) is positive with respect to \(\pi_1\), since \(\pi_1(a+1) = \tau_a(\pi)(a+1)=\pi(a)< \pi(b)=\pi_1(b)\). Because of our assumption, it is

\[ \Delta_{a+1,b}(\pi_1)\ge 0. \]

Step 2.2 - Non-negativity of \(\Delta_a(\pi_2)+\Delta_a(\pi)\) Link to heading

It remains to show that

\begin{equation}\label{eq:22} \Delta_a(\pi_2)+\Delta_a(\pi)\ge 0. \end{equation}

We assume that \((a,a+1)\) and \((a+1,b)\) do not belong to \(\pi\). We discuss these cases in the end of this step.

By definition of \(\Delta_a\),

\begin{equation}\label{eq:22pi} \Delta_a(\pi) = \sum_{\substack{p< a< \pi(p), \\ p \neq \pi(a), \pi(a+1)} } \Delta_{p', \pi(p)'}\bigl(\rho^p_a(\pi)\bigr) \;+\;\epsilon_a(\pi) \mathcal{P}_{k}\bigl(R_a(\pi)\bigr). \end{equation}

Similarly, for \(\pi_2\) we obtain

\begin{equation}\label{eq:22pi2} \Delta_a(\pi_2) = \sum_{\substack{p< a< \pi_2(p), \\ p \neq \pi_2(a), \pi_2(a+1)} } \Delta_{p', \pi_2(p)'}\bigl(\rho^p_a(\pi_2)\bigr) \;+\; \epsilon_a(\pi_2) \mathcal{P}_{k}\bigl(R_a(\pi_2)\bigr). \end{equation}

The map \(\pi_2\) is defined by

\[ \pi_2(p) = \begin{cases} \pi(a+1) & \text{if } p=a,\\ a & \text{if } p=\pi(a+1),\\ \pi(b) & \text{if } p=a+1,\\ a+1 & \text{if } p=\pi(b),\\ \pi(a) & \text{if } p=b,\\ b & \text{if } p=\pi(a),\\ \pi(p), & \text{otherwise.} \end{cases} \]

Substituting the explicit form of \(\pi_2\) into \eqref{eq:22pi2} yields

\begin{equation}\label{eq:22pi2-v2} \Delta_a(\pi_2) \;=\; \sum_{\substack{p< a< \pi(p) \\ p \neq \pi(a), \pi(a+1), \pi(b)}} \Delta_{p',\pi(p)'} \!\big(\rho_a^p(\pi_2)\big) \;+\; 𝟙_{\pi(a)< a}\, \Delta_{\pi(a)',b'}\!\big(\rho_a^{\pi(a)}(\pi_2)\big) \;+\; \epsilon_a(\pi_2)\,\mathcal{P}_k(R_a(\pi_2)). \end{equation}

Here

\[ 𝟙_{\pi(a)< a} = \begin{cases} 1 & \text{if } \pi(a)< a,\\ 0 & \text{otherwise.} \end{cases} \]

Using \eqref{eq:22pi} and \eqref{eq:22pi2-v2}, we obtain

\begin{equation}\label{eq:step22_relation} \begin{aligned} \Delta_a(\pi_2)+\Delta_a(\pi) &= \sum_{\substack{p< a, \\ p \neq \pi(a), \pi(a+1), \pi(b), \\ \pi(p)>a}} \Bigl[\Delta_{p',\pi(p)'}(\rho_a^{p}(\pi_2)) + \Delta_{p',\pi(p)'}(\rho_a^p(\pi))\Bigr] + \\ &\qquad + 𝟙_{\pi(a)< a}\,\Delta_{\pi(a)',b'}\bigl(\rho_a^{\pi(a)}(\pi_2)\bigr) + 𝟙_{\pi(b)< a}\,\Delta_{\pi(b)',b'}\bigl(\rho_a^{\pi(b)}(\pi)\bigr) + \\ &\qquad+\epsilon_a(\pi_2) \mathcal{P}_{k}\bigl(R_a(\pi_2)\bigr) + \epsilon_a(\pi)\mathcal{P}_k \bigl(R_a(\pi)\bigr). \end{aligned} \end{equation}

In the next step we prove that each summand in the sum is non-negative. We address the remaining term afterwards.

Step 2.2a - Non-negativity of \(\Delta_{p',\pi(p)'}(\rho_a^{p}(\pi_2)) + \Delta_{p',\pi(p)'}(\rho_a^p(\pi))\) ² Link to heading

Step 2.2b - Non-negativity of the remaining term Link to heading

We show

\begin{equation*} 𝟙_{\pi(a)< a}\,\Delta_{\pi(a)',b'}\bigl(\rho_a^{\pi(a)}(\pi_2)\bigr) + 𝟙_{\pi(b)< a}\,\Delta_{\pi(b)',b'}\bigl(\rho_a^{\pi(b)}(\pi)\bigr) +\epsilon_a(\pi_2) \mathcal{P}_{k}\bigl(R_a(\pi_2)\bigr) + \epsilon_a(\pi)\mathcal{P}_k \bigl(R_a(\pi)\bigr)\ge 0. \end{equation*}

We have

\[ \pi=(a~~\pi(a))(a+1~~\pi(a+1))(b~~\pi(b))\cdots \]

and

\[ \pi_2=(a~~\pi(a+1))(a+1~~\pi(b))(b~~\pi(a))\cdots . \]

Then we need to check various cases with different configurations for \(a\), \(\pi(a)\), \(\pi(a+1)\),\(\pi(b)\) and \(b\)…

Excluded cases at the beginning of Step 2.2 Link to heading

We now address the cases that were excluded at the beginning.

Case 1. Assume \((a,a+1)\) and \((b,\pi(b))\) are pairs in \(\pi\). We first prove relation \eqref{eq:22} in the case \(b<\pi(b)\), and treat the case \(b>\pi(b)\) afterwards.

Case 1a. Since \(\tau_a(\pi)=\pi\), it follows that

\begin{equation}\label{eq:231} \Delta_a(\pi)=0. \end{equation}

Moreover, since \(\pi_2(a)=b< \pi(b)=\pi_2(a+1)\) by assumption, the transposition \(\tau_a\) is positive with respect to \(\pi_2\). Thus, by Step 1 , we deduce

\begin{equation}\label{eq:232} \Delta_a(\pi_2)\ge 0. \end{equation}

Together, \eqref{eq:231} and \eqref{eq:232} yield relation \eqref{eq:22} for \(\pi\).

Case 1b. If \(b>\pi(b)\), we consider the transposition \(\tau_{a+1,\pi(b)}\) instead of \(\tau_{a,b}\) since \(\tau_{a+1,\pi(b)}(\pi)=\tau_{a,b}(\pi)\). Note that \(\tau_{a+1, \pi(b)}\) is positive with respect to \(\pi\), and by the induction hypothesis we obtain

\[ \Delta_{a,b}(\pi)=\Delta_{a+1,\pi(b)}(\pi)\ge 0. \]

This is because \(\pi(b)-(a+1)< b-a = l+1\).

Case 2. Assume \((a,\pi(a))\) and \((b,a+1)\) are pairs in \(\pi\). Since \(\tau_{a,b}\) is positive with respect to \(\pi\), it follows that \(\pi(a)< a+1 < b\). The adjacent transposition \(\tau_a\) is therefore positive with respect to \(\pi\) since \(\pi(a)< b=\pi(a+1)\). By Step 1 , and since \(\pi_1=\tau_a(\pi_0)\), we obtain

\begin{equation}\label{eq:233} \mathcal{P}_{k+1}(\pi_1)-\mathcal{P}_{k+1}(\pi_0)\ge 0. \end{equation}

Moreover, we have

\begin{equation}\label{eq:234} \mathcal{P}_{k+1}(\pi_3) - \mathcal{P}_{k+1}(\pi_2) =0 \end{equation}

because \((a,a+1)\in \pi_2\), which implies \(\pi_3=\tau_a(\pi_2)=\pi_2\). As a consequence of \eqref{eq:233} and \eqref{eq:234}, we find \eqref{eq:22} for \(\pi\).

Together, Step 2.1 and Step 2.2 establish \eqref{eq:main-diff}.