Generating function of a counting function.

Question

Let $m$ be odd. Let $\eta(m)$ count the number of ways we can express $m$ as a product of exactly two odd numbers, counting order. What is $$\sum_{m\text{ odd }}\eta(m)x^m\text{ ? }$$

So, as an example, $\eta(9)=3$ since $9=3\times 3=1\times 9=9\times 1$, while $\eta(p)=2$ for an odd prime. Suppose we extended $\eta$ for even numbers in the same manner. Then $\eta(0)=0$, $\eta(2)=0$ but $\eta(4)=1$ since $4=2\times 2$. Can we find $$\sum_{n\geqslant 0}\eta(n)x^n\text{ ? }$$

Answer 1

The right generating function to use here is not the ordinary generating function but the Dirichlet generating function, since your function is just the odd terms of the Dirichlet series of the divisor function

$$\sigma_0(n) = \sum_{d | n} 1.$$

The divisor function has Dirichlet series

$$\sum_{n \ge 1} \frac{\sigma_0(n)}{n^s} = \zeta(s)^2$$

and to isolate the odd terms we just need to remove the factor corresponding to $2$ in the Euler product of $\zeta(s)$ twice, giving

$$\sum_{n \text{ odd}} \frac{\sigma_0(n)}{n^s} = \zeta(s)^2 \left( 1 - \frac{1}{2^s} \right)^2.$$

The ordinary generating function you want is definitely not rational. The Taylor series of a rational function is a solution to a linear recurrence relation, and there are strong constraints on what such a sequence can look like: in particular, its growth rate is eventually a polynomial times an exponential (but possibly with a finite period), while $\sigma_0$ has a much more erratic growth rate.

Answer 2

As Quiaochu pointed out your function is very similar to $d(n)$ the number of divisors of $n$. I'll just note that, $$ \sum_{n} d(n) z^n = \sum_{d} \sum_{d | n} z^n = \sum_{d} \sum_{n} z^{nd} = \sum_{d} \frac{z^d}{1 - z^{d}} $$ This has a natural boundary at $|z| = 1$ since it has a singularity at every root of unity. Since the set of singularities is dense on $|z| = 1$ you cannot continue analytically the function beyond the unit circle. Despite the complicated nature of these functions they have been studied by the likes of Hardy and Littlewood... (There is some recent literature aswell).

As a matter of fact if your series has integer coefficients and radius of convergence equal to $1$ then there are only two possibilities, either it's a rational function or it has a natural boundary at $|z| = 1$. This is a conjecture of Polya and a theorem of Carleson. From this we see that your original series will also have a natural boundary at $|z| = 1$.