Context
=======


In a [recent paper](https://arxiv.org/abs/2209.06838) involving entanglement in linear optics, we came across some summations involving [Catalan numbers](https://en.wikipedia.org/wiki/Catalan_number) 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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Kronecker_delta) defined as $\delta\_{a,b} = 1$ if $a=b$ and $0$ otherwise. Let $C\_n$ be the $n^{\rm th}$ [Catalan number](https://en.wikipedia.org/wiki/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](https://math.stackexchange.com/questions/616889/worst-case-number-of-transpositions-needed-to-generate-a-permutation) $|\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](https://arxiv.org/abs/2209.06838) 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!
=======



Conjecture on sum over permutations of products of Catalan numbers
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.


