Conjecture on sum over permutations of products of Catalan numbers

Question

Context

In a recent paper involving entanglement in linear optics, we came across some summations involving Catalan numbers and permutations. In particular, these sums arise when doing integration over the unitary group $\mathrm U(n)$ in the limit that $n\to\infty$. When doing this, we encounter the asymptotic form of the Weingarten function, which is the origin of the sums over the Catalan numbers. One of these sums that is of most interest to us seems to surprisingly simplify dramatically, which makes us curious to understand why.

---

Definitions

Let $\delta$ be the Kronecker delta defined as $\delta_{a,b} = 1$ if $a=b$ and $0$ otherwise. Let $C_n$ be the $n^{\rm th}$ Catalan number $C_n := \frac{1}{n+1}\binom{2n}{n}$.

Let $S_{2\ell}$ denote the permutation group on $2\ell$ elements. For $\tau \in S_{2\ell}$, define $\#(\tau)$ to be the number of cycles in the disjoint cycle decomposition of $\tau$. Indeed let $\{c_i^{(\tau)} \mid i\in \{1,\dots, \#(\tau)\}\}$ be the cycle decomposition, and define $|c_i^{(\tau)}|$ to be the length of the $i^{\rm th}$ cycle. Let $|\tau|$ be the minimum number of transpositions needed to generate the permutation $\tau$, and note that $|\tau| = 2\ell - \#(\tau)$.

Define $\xi^{(\ell)}\colon S_{2\ell} \to \{1,2,\dots, \ell \}$ as

$$ \xi^{(\ell)}(\tau)= \log_2\sum_{j_1,\dots,j_\ell=1}^2 \delta_{j_{\lceil\tau(2\ell)/2\rceil},j_{\lceil\tau(1)/2\rceil} }\delta_{j_{\lceil\tau(2)/2\rceil},j_{\lceil\tau(3)/2\rceil}} \dots \delta_{j_{\lceil\tau(2\ell-2)/2\rceil},j_{\lceil\tau(2\ell-1)/2\rceil}}. $$

For $\ell \in \mathbb N$ and $\kappa \in \mathbb Z$, define $a^{(\ell)}_{\kappa} \in \mathbb Z$ as

$$ a^{(\ell)}_\kappa := \sum_{\substack{\tau\in S_{2\ell} \text{ s.t.}\\\xi^{(\ell)}(\tau) = |\tau|+\kappa}} (-1)^{\#(\tau)} \prod_{i=1}^{\#(\tau)} C_{|c_i^{(\tau)}| - 1}. $$

---

Example: $\ell = 1$ and $\kappa = 0$

• When $\ell = 1$, $\xi^{(1)}(\tau) = 1$ for both permutations (the identity and the swap) because $\lceil1/2\rceil = \lceil 2/2\rceil = 1$.
• When $\tau$ is the identity permutation, $|\tau| = 0$, so it does not contribute to the sum in $a^{(\ell=1)}_{\kappa=0}$.
• When $\tau$ is the swap, $|\tau| = 1 = \xi^{(1)}(\tau)$, so it does contribute. The swap permutation has one cycle of length 2. Therefore,

$$ a_{\kappa=0}^{(\ell=1)} = (-1)^{2-1}C_{2-1} = -C_1 = -1. $$

---

Theorem

In a very roundabout way, we proved in our paper that

$$ a_{\kappa=1}^{(\ell)} = \frac{(-1)^{\ell +1}}{2 \ell -1} \binom{2 \ell -1}{\ell -1}. $$

---

Conjecture

For all $\ell \in \mathbb N$, $a_{\kappa=0}^{(\ell)} = (-1)^\ell 4^{\ell-1}$.

Evidence for the conjecture: the conjecture is true for $\ell \leq 5$. We generate the following table for $\kappa = 0$ in Mathematica by iterating through all permutations.

$\ell$	$a_{\kappa=0}^{(\ell)}$
$1$	$-C_1$	$= -1$
$2$	$-4 C_0^2 C_1+4 C_0 C_2$	$=4$
$3$	$-9 C_0^4 C_1+15 C_0^2 C_1^2-C_1^3+18 C_0^3 C_2-6 C_0 C_1 C_2-9 C_0^2 C_3$	$=-16$
$4$	$-16 C_0^6 C_1+80 C_0^4 C_1^2-40 C_0^2 C_1^3+48 C_0^5 C_2-112 C_0^3 C_1 C_2 +16 C_0 C_1^2 C_2+8 C_0^2 C_2^2-48 C_0^4 C_3+24 C_0^2 C_1 C_3+16 C_0^3 C_4$	$=64$
$5$	$-25 C_0^8 C_1+250 C_0^6 C_1^2-380 C_0^4 C_1^3+80 C_0^2 C_1^4-C_1^5+100 C_0^7 C_2 -600 C_0^5 C_1 C_2+440 C_0^3 C_1^2 C_2-20 C_0 C_1^3 C_2 + 130 C_0^4 C_2^2 -50 C_0^2 C_1 C_2^2 -150 C_0^6 C_3+320 C_0^4 C_1 C_3-60 C_0^2 C_1^2 C_3-40 C_0^3 C_2 C_3 +100 C_0^5 C_4-60 C_0^3 C_1 C_4-25 C_0^4 C_5$	$=-256$

---

Question

Can one find a closed form for $a_{\kappa}^{(\ell)}$ for all $\kappa$ and $\ell$? Of particular interest for us is when $\kappa = 0$; how does one prove or disprove our conjecture that $a_{\kappa=0}^{(\ell)} = (-1)^\ell 4^{\ell-1}$? If our conjecture is indeed true, is there any insight as to why the seemingly complicated expression simplifies so dramatically?

Unfortunately, it does not seem that the roundabout way which helped us solve the $\kappa = 1$ case works for the $\kappa = 0$ case. We imagine that a first step to answering these questions is to simplify $\xi^{(\ell)}$, probably using some properties of permutations. Is there any nice interpretation of what $\xi^{(\ell)}(\tau)$ is representing about the permutation $\tau$? We spent some time and came up with a few graphical and combinatorial ways of understanding $\xi^{(\ell)}$, but nothing we’ve been able to use to make any real progress.

---

Thanks!

Answer 1

The problem naturally fits in the framework of breakpoint graphs (per Peter Taylor's observation), which makes it possible to obtain a differential equation for the generating function $$H(x,u,s_1,s_2,\dots) := \sum_{\ell\geq 0} x^{2\ell} \sum_{\tau\in S_{2\ell}} u^{\xi^{(\ell)}(\tau)} \prod_{i=1}^{\#(\tau)} s_{|c_i^{(\tau)}|}$$ by modification of the proof of Lemma 3.2 in my paper https://arxiv.org/abs/1503.05285 similarly how it was done for function $G(x,u,s_1,s_2,\dots)$ in Theorem 4.1. In fact, $H$ represents an analog of function $G$, with just a minor complication that it runs only over even $n=2\ell$.

Then it may be possible to obtain an explicit expression for $H$ and/or derive the anticipated identity directly from the differential equation. This approach can potentially be extended to other values of $\kappa$. Please let me know if you are interested to collaborate on working out details in this direction.