# convolution method

Let $f$, $g$, and $h$ be multiplicative functions such that $f=g*h$, where $*$ denotes the convolution (http://planetmath.org/MultiplicativeFunction) of $g$ and $h$. The convolution method is a way to $\displaystyle\sum_{n\leq x}f(n)$ by using the fact that $f=g*h$:

$\begin{array}[]{ll}\displaystyle\sum_{n\leq x}f(n)&\displaystyle=\sum_{n\leq x% }\sum_{d|n}g(d)h\left(\frac{n}{d}\right)\\ &\displaystyle=\sum_{d\leq x}\sum_{m\leq\frac{x}{d}}g(d)h(m)\\ &\displaystyle=\sum_{d\leq x}g(d)\sum_{m\leq\frac{x}{d}}h(m)\end{array}$

This method for calculating $\displaystyle\sum_{n\leq x}f(n)$ is advantageous when the sums in of $g$ and $h$ are easier to handle.

As an example, the sum $\displaystyle\sum_{n\leq x}\mu^{2}(n)$ will be calculated using the convolution method.

Since $\mu^{2}=\mu^{2}*\varepsilon=\mu^{2}*(\mu*1)=(\mu^{2}*\mu)*1$, the functions $\mu^{2}*\mu$ and $1$ can be used.

To use the convolution method, a nice way to $(\mu^{2}*\mu)(n)$ needs to be found. Note that $\mu^{2}*\mu$ is multiplicative (http://planetmath.org/MultiplicativeFunction), so it only needs to be evaluated at prime powers.

Let $k\in\mathbb{N}$. Then

 $(\mu^{2}*\mu)(p^{k})=\sum_{j=0}^{k}\mu^{2}(p^{j})\mu(p^{k-j})=\mu(p^{k})+\mu(p% ^{k-1})=\begin{cases}0&\text{if }k\neq 2\\ -1&\text{if }k=2.\end{cases}$

Since $\mu^{2}*\mu$ is multiplicative (http://planetmath.org/MultiplicativeFunction), then $(\mu^{2}*\mu)(n)=\begin{cases}0&\text{if }n\text{ is not a square}\\ \mu(\sqrt{n})&\text{if }n\text{ is a square.}\end{cases}$

The convolution method yields:

$\begin{array}[]{ll}\displaystyle\sum_{n\leq x}\mu^{2}(n)&\displaystyle=\sum_{d% \leq x}(\mu^{2}*\mu)(d)\sum_{m\leq\frac{x}{d}}1\\ &\\ &\displaystyle=\sum_{d\leq x}(\mu^{2}*\mu)(d)\left(\frac{x}{d}+O(1)\right)\\ &\\ &\displaystyle=\sum_{a\leq\sqrt{x}}\mu(a)\left(\frac{x}{a^{2}}+O(1)\right)\\ &\\ &\displaystyle=x\sum_{a\leq\sqrt{x}}\frac{\mu(a)}{a^{2}}+O\left(\sum_{a\leq% \sqrt{x}}|\mu(a)|\right)\\ &\\ &\displaystyle=x\left(\sum_{a\in\mathbb{N}}\frac{\mu(a)}{a^{2}}-\sum_{a>\sqrt{% x}}\frac{\mu(a)}{a^{2}}\right)+O\left(\sum_{a\leq\sqrt{x}}1\right)\\ &\\ &\displaystyle=x\sum_{a\in\mathbb{N}}\frac{\mu(a)}{a^{2}}+O\left(x\sum_{a>% \sqrt{x}}\left|\frac{\mu(a)}{a^{2}}\right|\right)+O(\sqrt{x})\\ &\\ &\displaystyle=\frac{6}{\pi^{2}}x+O\left(x\sum_{a>\sqrt{x}}\frac{1}{a^{2}}% \right)+O(\sqrt{x})\\ &\\ &\displaystyle=\frac{6}{\pi^{2}}x+O\left(x\left(\frac{1}{\sqrt{x}}\right)% \right)+O(\sqrt{x})\\ &\\ &\displaystyle=\frac{6}{\pi^{2}}x+O(\sqrt{x})\end{array}$

Title convolution method ConvolutionMethod 2013-03-22 15:58:24 2013-03-22 15:58:24 Wkbj79 (1863) Wkbj79 (1863) 13 Wkbj79 (1863) Definition msc 11N37 DirichletHyperbolaMethod MoebiusFunction DisplaystyleYOmeganOleftFracxlogXy12YRightFor1LeY2 DisplaystyleXlog2xOleftsum_nLeX2OmeganRight