Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Assume I have four (generating) functions $f$, $f'$, $g$ and $g'$. If that is interesting, we can assume that they all share the same radius of convergence $\rho > 0$. In addition, we know that

$\qquad [z^n]f(z) \sim [z^n]f'(z)$ and

$\qquad [z^n]g(z) \sim [z^n]g'(z)$.

Now we are interested in whether

$\qquad [z^n](f \ast g)(z) \sim [z^n](f' \ast g')(z)$

where $\ast$ denotes (discrete) convolution. That is, we would like to obtain asymptotics for the coefficients of a generating function by replacing factors with "equivalent" functions.

I think this is not always true. Intuitively, coefficients of small $n$ -- which can be arbitrarily bad in $f'$ and $g'$ -- factor into all coefficients of the product; hence the error is blown up and need not vanish in the limit.

What I don't have is

  • a counter-example and/or
  • a rigorous argument for above intuition (if it's accurate).

What are such?

share|improve this question

1 Answer 1

up vote 6 down vote accepted

If we take a stupid counterexample, say

$$\begin{gather} f(z) = \frac{1+z}{1-z} = 1 + 2\sum_{n=1}^\infty z^n,\\ g(z) = \frac{1-z}{1+z} = 1 + 2\sum_{n=1}^\infty (-1)^nz^n, \end{gather}$$

we see that the pole of each of the two functions on the unit circle is cancelled by the zero of the other when multiplying, $f(z)\cdot g(z) = (f\ast g)(z) \equiv 1$.

But if we add a function $h$ that is holomorphic in $D_r(0)$ for some $r > 1$, then the coefficients of $h$ tend to $0$, so we have asymptotic equality, $[z^n](f+h) \sim [z^n]g$, and also $[z^n](g+h)\sim [z^n]g$, but for the product,

$$(f+h)(z)\cdot (g+h)(z) = f(z)g(z) + \left(f(z)+g(z)\right)h(z) + h(z)^2 = 1 + 2\frac{1+z^2}{1-z^2}h(z) + h(z)^2,$$

the poles are in general not cancelled (only when $h$ has a zero in the appropriate place).

The point is that the radius of convergence of the convolution (Cauchy product) of two power series can be larger than the radius of convergence of the factors, if the singularities of each factor on the boundary of the domain of convergence are cancelled by the behaviour of the other factor, but that cancelling is not preserved under small perturbations, so if cancellation of singularities happens for $f\ast g$, it generally does not happen for $f'\ast g'$, hence the radii of convergence of $f\ast g$ and $f'\ast g'$ are different, but a necessary condition for asymptotic equivalence of the coefficients is that the two power series have the same radius of convergence.

With the condition that the coefficients of the series be positive, an example where the radius of convergence of the convolution of the power series is larger than the radius of the factors may not exist (if one exists, it's at least much harder to see), but we still need not have asymptotic equality of the coefficients preserved by small perturbations. If we consider e.g. for some $C > 1$

$$f(z) = \sum_{n=0}^\infty (n+1)C^n z^n,\quad g(z) = \sum_{n=0}^\infty \frac{C^nz^n}{(n+1)^2},$$

the coefficients of the convolution are

$$\begin{align} \sum_{k=0}^n (n+1-k)C^{n-k}\frac{C^k}{(k+1)^2} &= C^n\left((n+2)\sum_{k=0}^n \frac{1}{(k+1)^2} - \sum_{k=0}^n \frac{1}{k+1}\right)\\ &= C^n\left(n\frac{\pi^2}{6} + O(1) - O(\log n)\right), \end{align}$$

and changing the constant coefficient of $g$ already changes the constant factor on the dominant term $\frac{\pi^2}{6} n C^n$.

share|improve this answer
    
Since this goes well beyond the question as posed, I decided to write up the follow-up question as per your gut feeling. Thanks for thinking about this! –  Raphael Jul 30 at 14:33
1  
I still haven't found the answer for whether the $\Theta$ class must be preserved, but for the asymptotic equality, the answer is negative, consider e.g. $(n+1)\cdot C^n$ and $(n+1)^{-2}\cdot C^n$ for $C > 1$. The convolution's coefficients are then $\sim \frac{\pi^2}{6}n C^n$, and again adding something to the constant term of the smaller series changes the constant factor. –  Daniel Fischer Jul 30 at 15:16
    
I've added that example to the answer. I was almost at the point of declaring that the $\Theta$ class must be preserved, but then found yet another hole in the argument :( –  Daniel Fischer Jul 30 at 16:00
    
Hm, I note that $g$ does not seem to be algebraic; $[z^n]\frac{\mathrm{Li}_2(cz)}{cz} = \frac{c^n}{(n+1)^2}$. It may be worthwhile to investigate convolutions of only algebraic generating functions. –  Raphael Aug 1 at 15:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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