# Inverse map for partition transform

Let $(a_n)$, $n\in\mathbb{N}$, be a sequence of complex numbers, then formally one has

(1) $$\prod_{1}^{\infty}\left(1-a_nx^n\right)^{-1}=1+\sum_{1}^{\infty}\left(\sum_{j_1+2j_2+\cdots +nj_n=n}a_1^{j_1}a_2^{j_2}\cdots a_n^{j_n}\right)x^n=1+\sum_{1}^{\infty}b_n x^n,$$ say. I'm almost certain the answer to my question has been known for centuries, but I don't know where to find it:

What is the inverse of the map defined by

(2) $$b_n=\sum_{j_1+2j_2+\cdots +nj_n=n}a_1^{j_1}a_2^{j_2}\cdots a_n^{j_n},$$ and where can I find it in the literature?

-
Just to be sure I understand the question: you are asking for a formula for the sequence of $a_i$, given the $b_i$? –  Gerry Myerson Mar 29 '12 at 23:32
Indeed, Gerry. I do not even know what products of the type on the r.h.s. of (1) are called. Obviously they generalize Euler's infinite product for the partition numbers. Equivalently, by logarithmic differentiation, the inverse map is analogous to the inverse of $$\sum_{d|n}a_d^{n/d},$$ whatever that is? –  Kevin Smith Mar 30 '12 at 8:11
First line of previous comment should be l.h.s. –  Kevin Smith Mar 30 '12 at 8:19
Maybe it's worthwhile working out the $a_i$ for some simple sequences $b_i$ (e.g., $b_i=1$ for all $i$) to see what kinds of sequence come up. You could look up any interesting sequence in the Online Encyclopedia of Integer Sequences, and the references there might put you onto something more general. –  Gerry Myerson Apr 1 '12 at 23:34
I'm pretty sure I've found the pattern now, although the "proof" is still incomplete. Despite bringing up some interesting $\theta$-function identities, the analytic approach is difficult, so I've resorted to doing it recursively. Just missing a little piece, shouldn't be long. –  Kevin Smith Apr 2 '12 at 8:12

Kevin Smith wrote:

I'm almost certain the answer to my question has been known for centuries, but I don't know where to find it...

You're right! It goes back to Euler. You're looking for a variation on Euler's infinite product representation algorithm (EIPRA). EIPRA takes as input a sequence $b_n$ and outputs a sequence $a_n$ such that

$$1+\sum_{n=1}^{\infty}b_n x^n = \prod_{n=1}^{\infty}\left(1-x^n\right)^{-a_n},$$ whereas you are looking for an algorithm that takes as input a sequence $b_n$ and outputs a sequence $a_n$ such that

$$1+\sum_{n=1}^{\infty}b_n x^n = \prod_{n=1}^{\infty}\left(1-a_nx^n\right)^{-1}.$$

Fortunately, the key to both algorithms is to take the logarithmic derivative of both sides of the equation, which transforms the infinite product into a Lambert series.

[I see from the comments that you already considered logarithmic differentiation, so you must be looking for something more explicit than the recurrence that follows.]

Taking the logarithmic derivative of both sides of your equation (1) (and multiplying by $x$),

$$\sum_{n=1}^{\infty}\frac{a_n n x^n}{1-a_n x^n}= \frac{\sum_{n=1}^{\infty}b_n n x^n}{ 1+\sum_{ n=1}^\infty b_n x^n } := \sum_{n=1}^\infty c_n x^n .$$

The sequence $c_n$ is easily determined by the sequence $b_n$, and the sequence $a_n$ is then determined from the sequence $c_n$ as in EIPRA.

Expanding $\frac{1}{1-a_n x^n}$ as a geometric series, $$\sum_{m=1}^\infty \sum_{j=1}^\infty m a_m^j x^{m j} = \sum_{n=1}^\infty c_n x^n ,$$
hence, $a_n$ is defined recursively by

$$n a_n = c_n - \sum_{m|n,m\ne n} m a_m^{\frac n m} .$$

-
Thank you Gareth - yes I do know this, and indeed this kind of reasoning is the starting point of my (still ongoing) analysis of this problem. However, the formula to which you arrive here is recursive, and when you expand it out you get an expression, the terms of which don't seem to follow a nice rule. It is this somewhat badly behaved function that I want to understand. –  Kevin Smith Nov 22 '12 at 19:17
If you don't expand it too much, there is a discernible pattern, but I don't think it's what you're looking for; it's really just a restatement of the recurrence. You can see $a_{30}$ organized in "towers" here along with the Mathematica one-liner I wrote to express the $a_n$ in terms of $c_n$. –  Garth Payne Nov 24 '12 at 17:42
Garth, I apologize for spelling your name incorrectly - I was reading your answer on a mobile device. Thank you for taking the time to investigate this. It seems a good time then to point out that, along these lines, you'll find that you get $$a_n=\sum k_n(j_1,j_2,...)c_1^{j_1}c_2^{j_2}...,$$ where the sum is taken over all tuples satisfying $sum dj_d=n$ where $d|n$. The problem is then to determine the constants $k_n(j_1,j_2,...)$. I suspect this can be done by induction on an optimization argument of sorts, although one gets stuck in finding a formula for the dimension for each $n$. –  Kevin Smith Nov 27 '12 at 20:30
The above comment has some errors in it. It should state that you get $$na_n=\sum k_n(j_1,j_2,...)c_1^{j_1}c_2^{j_2}...,$$ where the sum is taken over all non-negative integer-tuples $\{j_1,j_2,...\}$ satisfying $$\sum_{d|n}d j_d=n$$. The numbers $k_n(j_1,j_2,...)$ are non-zero integers, and the dimension is the number of non-negative integer-tuples that satisfy the equation above. –  Kevin Smith Nov 29 '12 at 13:19
However, it is important to note that the $j_d$s also depend on $n$, so the condition should really be written as $$\sum_{d|n}dj_d(n)=n$$. –  Kevin Smith Nov 29 '12 at 13:29

To simplify things, one might consider the reciprocal generating function and expands the reciprocal of the product on the l.h.s. of (1) into

(3) $$\prod_{1}^{\infty}(1-a_nx^n)=1+\sum_{1}^{\infty}c_nx^n,$$ where

(4) $$c_n=\sum_{j_1+\cdots +nj_n=n:j_i\leq 1}(-a_1)^{j_1}\cdots (-a_n)^{j_n}$$ counts only partitions into distinct parts (i.e. $j_i\leq 1$). Noting that, by the multinomial expansion, one also has

(5) $$c_n=\sum_{j_1+\cdots +nj_n=n}{{j_1+\cdots +j_n}\choose{j_1,...,j_n}}(-b_1)^{j_1}\cdots (-b_n)^{j_n}$$ this reduces the problem to that of inverting the map defined by (4), and composition with the involution (5). To this end, recursive examination of (4) for the first 6 terms gives: $$a_1=-c_1$$ $$a_2=-c_2$$ $$a_3=-c_3+c_1c_2$$ $$a_4=-c_4+c_1c_3-c_1^2c_2$$ $$a_5=-c_5+c_1c_4-c_1^2c_3+c_1^3c_2-c_1c_2^2+c_2c_3$$ $$a_6=-c_6+c_1c_5-c_1^2c_4+c_1^3c_3-c_1^4c_2+c_1^2c_2^2-c_1c_2c_3+c_2c_4.$$

i.e. those partitions that are not of the form $n=dj_d$ for any $d < n$. So, one then supposes that

(6) $$a_n=\sum_{j_1+\cdots +nj_n=n:dj_d\neq n:d < n}(-c_1)^{j_1}\cdots (-c_n)^{j_n}$$ is the inverse map. In an attempt to verify this conjecture, one may add in the missing terms to get $$a_n+c_n+\sum _{d|n}(-c_d)^{n/d}=\sum_{j_1+\cdots +nj_n=n}(-c_1)^{j_1}\cdots (-c_n)^{j_n}.$$

UPDATE (02/04/12): The conjecture is incorrect - Martin Rubey has verified that the partitions are correct for $n\leq 15$, but the coefficients are not all unity.

-
It seems to me that I get coefficients different from 1 in the expression for $a_7$. –  Martin Rubey Apr 2 '12 at 19:42
Thank you Martin, I'm not sure about this myself now. What do you have? –  Kevin Smith Apr 2 '12 at 19:52
Unfortunately, I cannot copy and paste here. In any case, your conjecture about the terms which appear seems correct. Maybe this is also a hint about the coefficients. If you send me an email, I can answer with some data... –  Martin Rubey Apr 2 '12 at 20:15
I've sent an email to the address at your link. Many thanks. –  Kevin Smith Apr 2 '12 at 20:56