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
Canonical name	ConvolutionMethod
Date of creation	2013-03-22 15:58:24
Last modified on	2013-03-22 15:58:24
Owner	Wkbj79 (1863)
Last modified by	Wkbj79 (1863)
Numerical id	13
Author	Wkbj79 (1863)
Entry type	Definition
Classification	msc 11N37
Related topic	DirichletHyperbolaMethod
Related topic	MoebiusFunction
Related topic	DisplaystyleYOmeganOleftFracxlogXy12YRightFor1LeY2
Related topic	DisplaystyleXlog2xOleftsum_nLeX2OmeganRight