7
$\begingroup$

In some work I've been doing on the cohomology of the moduli space of curves, the following identity has come up:

$$\prod_{i=1}^n \frac{x^{i-1}}{x^i-1} = \sum_{(a_1^{r_1},\ldots,a_{\ell}^{r_{\ell}}) \vdash n} \left(\prod_{j=1}^{\ell} \frac{1}{a_i^{r_i} (x^{a_i}-1)^{r_i} (r_i)!}\right).$$

Here $x$ is a formal variable and the sum on the RHS is over all partitions of $n$. By $(a_1^{r_1},\ldots,a_{\ell}^{r_{\ell}}) \vdash n$, I mean a partition of the form

$$r_1 a_1 + r_2 a_2 + \cdots + r_{\ell} a_{\ell} = n$$

with $r_1,\ldots,r_{\ell} \geq 1$ and $a_1>a_2>\cdots>a_{\ell} \geq 1$.

I have verified this identity with Mathematica for $1 \leq n \leq 20$. However, I cannot figure out how to prove that it is always true. Can anyone help me?

This reminds me a little bit of the identity in this question, and I've tried without success to use the tools discussed in the answers to that question to solve it.

EDIT: In case anyone is interested, a version of this identity now appears as Lemma 5.2 in my paper "The high dimensional cohomology of the moduli space of curves with level structures" (joint w/ Neil Fullarton), which can be downloaded from my webpage here. Thanks to Lucia for telling me how to prove it!

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Nice! Food for thought: $n! / \prod_{j=1}^\ell\left(a_i^{r_i} r_i!\right)$ is the number of permutations in $S_n$ having cycle type $\left(a_1^{r_1},\ldots,a_\ell^{r_\ell}\right)$. Thus, the right hand side is probably better regarded as an average over $S_n$. $\endgroup$
    – darij grinberg
    Commented Sep 27, 2016 at 18:10
  • 2
    $\begingroup$ This follows if you use the interpretation in terms of cycle decompositions (as in that question) together with a simple combinatorial identity for partitions (see en.wikipedia.org/wiki/Q-Pochhammer_symbol and the section on combinatorial interpretation, which is pretty much your identity). $\endgroup$
    – Lucia
    Commented Sep 27, 2016 at 18:22
  • 2
    $\begingroup$ The RHS is the coefficient of $t^n$ in $$\exp (\sum_{n \ge 1} \frac{t^n}{n} (x^n-1)^{-1})$$ $\endgroup$
    – Ofir Gorodetsky
    Commented Sep 27, 2016 at 18:33
  • $\begingroup$ @Lucia: I'm having trouble figuring out your argument. Can you give a few more details? I'm sorry for being slow -- I'm just a simple topologist, and this kind of combinatorics is far outside my comfort zone. $\endgroup$
    – Andy Putman
    Commented Sep 27, 2016 at 18:37
  • $\begingroup$ @AndyPutman: Hope the quick sketch below helps. Will look later if there are still any issues. $\endgroup$
    – Lucia
    Commented Sep 27, 2016 at 18:47

1 Answer 1

Reset to default
15
$\begingroup$

Here's a quick sketch (since I'm pressed for time). Multiply both sides of the identity by $t^n$ and sum over $n$ from $0$ to infinity. From the cycle decomposition identity (Polya's formula) the right side becomes $$ \exp \Big( \sum_{i=1}^{\infty} \frac{t^i}{i (x^i-1)} \Big)= \exp\Big( -\sum_{i=1}^{\infty} \frac{t^i}{i} \sum_{j=0}^{\infty} x^{ji} \Big) = \exp\Big( \sum_{j=0}^{\infty} \log (1-t x^j) \Big) = \prod_{j=0}^{\infty} (1-tx^j). $$ The RHS is also known as a Pochhammer symbol (see the Wikipedia article linked in my comment): it is $(t;x)_{\infty}$. The wikipedia article already describes the combinatorial identity (simple partition relation) $$ (t;x)_{\infty} = \sum_{n=0}^{\infty} \frac{(-1)^n x^{n(n-1)/2} }{(x;x)_n} t^n, $$ where $$ (x;x)_n = (1-x) (1-x^2) \cdots (1-x^n). $$ This matches what you get from multiplying your LHS by $t^n$ and summing.

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ Very nice. I just want to give an excellent reference for the cycle decomposition identity - Theorem 5.1.4 in page 3 (!) of "Enumerative Combinatorics, Vol. 2" by Stanley covers this identity in its most general form. Proofs and applications are given. $\endgroup$
    – Ofir Gorodetsky
    Commented Sep 27, 2016 at 18:49
  • $\begingroup$ For the direct use/relevant to your problem, look at Example 5.2.10 in the same reference, which results from an application of the aforementioned Theorem 5.1.4. $\endgroup$
    – T. Amdeberhan
    Commented Sep 27, 2016 at 22:09
  • $\begingroup$ Also, for clarification: usually Polya's formula (cycle decomposition) is written as a sum over permutation $S_n$. From this, you get to the RHS in the above problem by converting to "cycle types" so that sum run though permutation $\lambda\vdash n$. $\endgroup$
    – T. Amdeberhan
    Commented Sep 28, 2016 at 0:16
  • 4
    $\begingroup$ In case you're interested, this proof now appears in my paper "The high dimensional cohomology of the moduli space of curves with level structures" (see Lemma 5.2), available on my webpage nd.edu/~andyp/papers $\endgroup$
    – Andy Putman
    Commented Oct 3, 2016 at 1:59
  • 1
    $\begingroup$ ps: I assume that you want to maintain pseudo-anonymity, but if you don't feel free to email me and I can thank you by name in the paper. This was a big help! $\endgroup$
    – Andy Putman
    Commented Oct 3, 2016 at 2:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .