# 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.

4more comments