Skip to main content
1 of 2
Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741

The sum identity

$$\frac{1}{k} \sum_{i=0}^{k-1} \left( 2 \cos \frac{2 \pi i}{k} \right)^{2n} = {2n \choose n}$$

(where $k > 2n$) can be explained combinatorially as follows: the adjacency matrix $A_k$ of the cycle graph of size $k$ has eigenvalues $2 \cos \frac{2 \pi i}{k}, 0 \le i \le k-1$, and the sum of the $2n^{th}$ powers of the eigenvalues of the adjacency matrix is the total number of closed walks of length $2n$ on the graph. For $k > 2n$ this is easily seen to be $k {2n \choose n}$ (where the coefficient of $k$ comes from the choice of starting vertex), and dividing by $k$ we get the identity above.

Letting $k \to \infty$ the above becomes a Riemann sum and we obtain the integral identity

$$\int_0^1 (2 \cos 2 \pi x)^{2n} \, dx = {2n \choose n}$$

which is fairly straightforward to prove but not quite as straightforward to interpret directly, since it's not obvious that the argument above about adjacency matrices generalizes.

This identity can be explained combinatorially using the representation theory of the circle group $\text{SO}(2)$. Associated to (say) any compact Lie group $G$ and representation $V$ of $G$ there is a graph $\Gamma_G(V)$, the principal graph, whose vertices are the irreducible representations of $G$, and where the number of edges from a representation $A$ to a representation $B$ is $\dim \text{Hom}_G(A \otimes V, B)$.

The principal graph of the standard representation of $\text{SO}(2)$ is precisely the Cayley graph of $\mathbb{Z}$ with generators $\pm 1$, which one can think of as the "limit" of the cycle graphs above (the Cayley graphs of the finite, rather than infinite, cyclic groups) in some appropriate sense. It follows that the number of closed walks from the origin to itself on $\mathbb{Z}$ of length $2n$ is, on the one hand, clearly ${2n \choose n}$ and, on the other hand, is $\dim \text{Hom}_G(V^{\otimes n}, 1)$, or the dimension of the invariant subspace of $V^{\otimes n}$, and this quantity can be computed by character theory in a way that exactly generalizes the eigenvalue computation above.

The principal graph of the standard representation of $\text{SU}(2)$ is similar, but is infinite in one direction rather than two. This gives a corresponding integral identity for the Catalan numbers, and in order to get the Riemann sum version of this integral identity one must pass to the representation theory of quantum groups at roots of unity, as I learned in the linked MO question.

Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741