Definition: A tuple $\lambda = (\lambda_1, \ldots, \lambda_k)$ of natural numbers is called a numeric partition of $n$ if $1 \leq \lambda_1 \leq \cdots \leq \lambda_k$ and $\lambda_1 + \cdots + \lambda_k = n$ and is written as $\lambda \vdash n$.

Exercise: Let $p(n)$ be the amount of numeric partitions of $n$. Prove that

i) Let $f_n := \prod_{i=1}^n (1-x^i)^{-1}$. Prove that $(f_n)_{n\geq 0}$ creates a Cauchy sequence in $\mathbb{C}[[x]]$.

ii) Prove that $$ \sum\limits_{n \geq 0} p(n) x^n = \lim\limits_{n \rightarrow \infty} f_n = \prod\limits_{i=1}^\infty (1-x^i)^{-1} .$$

I tried to play around with the definition of $f_n$ and tried (quite successfully as I hope) to understand what a Cauchy sequence is. But how do I prove that?

What should I do to prove the second one? Any hints?

Thanks in advance!

  • 1
    $\begingroup$ expand each $(1-x_i)^{-1}$ as a geometric series. this (should) let you see that you get $p(n)$ and that the series converges in the formal power series ring. $\endgroup$ – yoyo May 29 '11 at 14:01
  • $\begingroup$ Do you know what a Cauchy sequence is in general? Do you know what the metric on $\mathbb{C}[[x]]$ is? $\endgroup$ – Qiaochu Yuan May 29 '11 at 17:47
  • $\begingroup$ @qiaochu-yuan I do know what a Cauchy sequence in general is - but I don't know the metric on $\mathbb{C}[[C]]$, could you please explain that to me? $\endgroup$ – muffel May 29 '11 at 20:54
  • $\begingroup$ @yoyo by expanding I get $$\left(\frac{1}{(1-x)},\frac{1}{(1-x)}+\frac{1}{(1-x^2)},\frac{1}{(1-x)}+\frac{1}{(1-x^2)}+\frac{1}{(1-x^3)},\cdots\right)$$ but I don't see the relation to neither $p(n)$ nor to $p(n)x^n$. Could you please give me another hint? $\endgroup$ – muffel May 29 '11 at 21:09
  • $\begingroup$ Okay, that would explain why you're confused. The metric isn't unique, but for example it can be given by $d(a, b) = 2^{-\nu(a-b)}$ where $\nu(a-b)$ is the largest power of $x$ dividing $a-b$. This metric satisfies a very strong form of the triangle inequality (see en.wikipedia.org/wiki/Ultrametric_space) and it turns out to be very easy to characterize convergence: a series converges if and only if its terms tend to $0$, and a product converges if and only if its terms are nonzero and tend to $1$. $\endgroup$ – Qiaochu Yuan May 29 '11 at 23:28

First note that $$ \frac{1}{1-x^i}=\sum_{j=0}^{\infty}x^{ij}. $$ We have $f_{n+1}-f_n$ is divisible by $x^{n+1}$, so we get convergence in $\mathbb{C}[[x]]$ (see http://en.wikipedia.org/wiki/Formal_power_series or something similar, neighborhoods of zero are powers of the ideal $(x)$).

For the connection to the partition function, think about a partition of $n$. choose how many $1$'s will appear, how many $2$'s etc., and pick them out in the product $$ (1+x+x^2+ \cdots)(1+x^2+(x^2)^2+\cdots)(1+x^3+(x^3)^2+\cdots) \cdots. $$ Pick the number of ones from the $(1+x)^{-1}$ (i.e., if you want three $1$'s in the partition pick $x^3$), pick the number of $2$'s from the $(1+x^2)^{-1}$ (i.e., if you want three $2$'s in the partition pick $(x^2)^3$).

Adding up every way you can do this is exactly the coefficient of $x^n$ in $\lim f_n$ (or $f_N$ for large enough $N$). (If this isnt clear just multiply out the first few coefficients or look up the partition function online and you'll see a better exposition.)

  • $\begingroup$ thank you for that great explanation! $\endgroup$ – muffel May 30 '11 at 7:31
  • $\begingroup$ Just one question left: What exactly do you mean by "neighborhoods of zero are powers of the ideal (x)"? $\endgroup$ – muffel May 30 '11 at 7:42
  • $\begingroup$ @muffel power series are "smaller" if they are more highly divisible by $x$. the wikipedia page on formal power series gives a few different equivalent ways of talking about the topology $\endgroup$ – yoyo May 30 '11 at 18:02

The function $f_n$ already has all the correct coefficients up to $p(n)$. Open the expression up (following yoyo's advice) and see if you can figure out why.

Continuing, when you move from $f_n$ to $f_{n+1}$, all the low-order coefficients remain the same, and this is the reason that the infinite product converges - since every particular coefficient is equal to some finite sum (that counts the number of integer partitions of that size).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.