convolution method


Let f, g, and h be multiplicative functionsMathworldPlanetmath such that f=g*h, where * denotes the convolution (http://planetmath.org/MultiplicativeFunction) of g and h. The convolution method is a way to nxf(n) by using the fact that f=g*h:

nxf(n)=nxd|ng(d)h(nd)=dxmxdg(d)h(m)=dxg(d)mxdh(m)

This method for calculating nxf(n) is advantageous when the sums in of g and h are easier to handle.

As an example, the sum nxμ2(n) will be calculated using the convolution method.

Since μ2=μ2*ε=μ2*(μ*1)=(μ2*μ)*1, the functionsMathworldPlanetmath μ2*μ and 1 can be used.

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

Let k. Then

(μ2*μ)(pk)=j=0kμ2(pj)μ(pk-j)=μ(pk)+μ(pk-1)={0if k2-1if k=2.

Since μ2*μ is multiplicative (http://planetmath.org/MultiplicativeFunction), then (μ2*μ)(n)={0if n is not a squareμ(n)if n is a square.

The convolution method yields:

nxμ2(n)=dx(μ2*μ)(d)mxd1=dx(μ2*μ)(d)(xd+O(1))=axμ(a)(xa2+O(1))=xaxμ(a)a2+O(ax|μ(a)|)=x(aμ(a)a2-a>xμ(a)a2)+O(ax1)=xaμ(a)a2+O(xa>x|μ(a)a2|)+O(x)=6π2x+O(xa>x1a2)+O(x)=6π2x+O(x(1x))+O(x)=6π2x+O(x)

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