elementary results about multiplicative functions and convolution

One of the most important elementary results about multiplicative functions and convolution (http://planetmath.org/DirichletConvolution) is:

Theorem.

If $f$ , $g$ , and $h$ are arithmetic functions with $f*g=h$ and at least two of them are multiplicative, then all of them are multiplicative.

The above theorem will be proven in two separate parts.

Lemma 1.

If $f$ and $g$ are multiplicative, then so is $f*g$ .

Proof.

Note that $\\displaystyle(f*g)(1)=f(1)g(1)=1\\cdot 1=1$ since $f$ and $g$ are multiplicative.

Let $a,b\\in\\mathbb{N}$ with $\\gcd(a,b)=1$ . Then any divisor $d$ of $a b$ can be uniquely factored as $d=d_{1}d_{2}$ , where $d_{1}$ divides $a$ and $d_{2}$ divides $b$ . When a divisor $d$ of $a b$ is factored in this manner, the fact that $\\gcd(a,b)=1$ implies that $\\gcd(d_{1},d_{2})=1$ and $\\displaystyle\\gcd\\left(\\frac{a}{d_{1}},\\frac{b}{d_{2}}\\right)=1$ . Thus,

∎

Lemma 2.

If $f$ is an arithmetic function and $g$ and $h$ are multiplicative functions with $f*g=h$ , then $f$ is multiplicative.

Proof.

Let $a,b\\in\\mathbb{N}$ with $\\gcd(a,b)=1$ . Induction will be used on $a b$ to establish that $f(ab)=f(a)f(b)$ .

If $ab=1$ , then $a=b=1$ . Note that $f(1)=f(1)\\cdot 1=f(1)g(1)=(f*g)(1)=h(1)=1$ . Thus, $f(ab)=f(1)=1=1\\cdot 1=f(a)f(b)$ .

Now let $a b$ be an arbitrary natural number. The induction hypothesis yields that, if $d_{1}$ divides $a$ , $d_{2}$ divides $b$ , and $d_{1}d_{2}<ab$ , then $f(d_{1}d_{2})=f(d_{1})f(d_{2})$ . Thus,

$\\begin{array}[]{ll}h(a)h(b)&=h(ab)\\\\\\\\&=(f*g)(ab)\\\\\\\\&\\displaystyle=\\sum_{d|ab}f(d)g\\left(\\frac{ab}{d}\\right)\\\\\\\\&\\displaystyle=f(ab)g(1)+\\sum_{\\begin{subarray}{c}d|ab\\\\d<ab\\end{subarray}}f(d)g\\left(\\frac{ab}{d}\\right)\\\\\\\\&\\displaystyle=f(ab)\\cdot 1+\\sum_{\\begin{subarray}{c}d_{1}|a\\\\d_{2}|b\\\\d_{1}d_{2}<ab\\end{subarray}}f(d_{1}d_{2})g\\left(\\frac{ab}{d_{1}d_{2}}\\right)\\\\\\\\&\\displaystyle=f(ab)+\\sum_{\\begin{subarray}{c}d_{1}|a\\\\d_{2}|b\\\\d_{1}d_{2}<ab\\end{subarray}}f(d_{1})f(d_{2})g\\left(\\frac{a}{d_{1}}\\right)g%\\left(\\frac{b}{d_{2}}\\right)\\\\\\\\&\\displaystyle=f(ab)-f(a)f(b)g(1)g(1)+\\sum_{\\begin{subarray}{c}d_{1}|a\\\\d_{2}|b\\end{subarray}}f(d_{1})f(d_{2})g\\left(\\frac{a}{d_{1}}\\right)g\\left(%\\frac{b}{d_{2}}\\right)\\\\\\\\&\\displaystyle=f(ab)-f(a)f(b)\\cdot 1\\cdot 1+\\left(\\sum_{d_{1}|a}f(d_{1})g\\left%(\\frac{a}{d_{1}}\\right)\\right)\\left(\\sum_{d_{2}|b}f(d_{2})g\\left(\\frac{b}{d_{2%}}\\right)\\right)\\\\\\\\&=f(ab)-f(a)f(b)+(f*g)(a)(f*g)(b)\\\\\\\\&=f(ab)-f(a)f(b)+h(a)h(b).\\end{array}$

It follows that $f(ab)=f(a)f(b)$ .∎

The theorem follows from these two lemmas and the fact that convolution is commutative.

The theorem has an obvious corollary.

Corollary.

If $f$ is multiplicative, then so is its convolution inverse.

Proof.

Let $f$ be multiplicative. Since $f(1)\eq 0$ , $f$ has a convolution inverse $f^{-1}$ . (See convolution inverses for arithmetic functions for more details.) Since $f*f^{-1}=\\varepsilon$ , where $\\varepsilon$ denotes the convolution identity function, and both $f$ and $\\varepsilon$ are multiplicative, the theorem yields that $f^{-1}$ is multiplicative.∎

单词	ElementaryResultsAboutMultiplicativeFunctionsAndConvolution
释义	elementary results about multiplicative functions and convolution One of the most important elementary results about multiplicative functions and convolution (http://planetmath.org/DirichletConvolution) is: Theorem. If $f$ , $g$ , and $h$ are arithmetic functions with $fg=h$ and at least two of them are multiplicative, then all of them are multiplicative. The above theorem will be proven in two separate parts. Lemma 1. If $f$ and $g$ are multiplicative, then so is $fg$ . Proof. Note that $\\displaystyle(fg)(1)=f(1)g(1)=1\\cdot 1=1$ since $f$ and $g$ are multiplicative. Let $a,b\\in\\mathbb{N}$ with $\\gcd(a,b)=1$ . Then any divisor $d$ of $a b$ can be uniquely factored as $d=d_{1}d_{2}$ , where $d_{1}$ divides $a$ and $d_{2}$ divides $b$ . When a divisor $d$ of $a b$ is factored in this manner, the fact that $\\gcd(a,b)=1$ implies that $\\gcd(d_{1},d_{2})=1$ and $\\displaystyle\\gcd\\left(\\frac{a}{d_{1}},\\frac{b}{d_{2}}\\right)=1$ . Thus, ∎ Lemma 2. If $f$ is an arithmetic function and $g$ and $h$ are multiplicative functions with $fg=h$ , then $f$ is multiplicative. Proof. Let $a,b\\in\\mathbb{N}$ with $\\gcd(a,b)=1$ . Induction will be used on $a b$ to establish that $f(ab)=f(a)f(b)$ . If $ab=1$ , then $a=b=1$ . Note that $f(1)=f(1)\\cdot 1=f(1)g(1)=(fg)(1)=h(1)=1$ . Thus, $f(ab)=f(1)=1=1\\cdot 1=f(a)f(b)$ . Now let $a b$ be an arbitrary natural number. The induction hypothesis yields that, if $d_{1}$ divides $a$ , $d_{2}$ divides $b$ , and $d_{1}d_{2}<ab$ , then $f(d_{1}d_{2})=f(d_{1})f(d_{2})$ . Thus, $\\begin{array}[]{ll}h(a)h(b)&=h(ab)\\\\\\\\&=(fg)(ab)\\\\\\\\&\\displaystyle=\\sum_{d\|ab}f(d)g\\left(\\frac{ab}{d}\\right)\\\\\\\\&\\displaystyle=f(ab)g(1)+\\sum_{\\begin{subarray}{c}d\|ab\\\\d<ab\\end{subarray}}f(d)g\\left(\\frac{ab}{d}\\right)\\\\\\\\&\\displaystyle=f(ab)\\cdot 1+\\sum_{\\begin{subarray}{c}d_{1}\|a\\\\d_{2}\|b\\\\d_{1}d_{2}<ab\\end{subarray}}f(d_{1}d_{2})g\\left(\\frac{ab}{d_{1}d_{2}}\\right)\\\\\\\\&\\displaystyle=f(ab)+\\sum_{\\begin{subarray}{c}d_{1}\|a\\\\d_{2}\|b\\\\d_{1}d_{2}<ab\\end{subarray}}f(d_{1})f(d_{2})g\\left(\\frac{a}{d_{1}}\\right)g%\\left(\\frac{b}{d_{2}}\\right)\\\\\\\\&\\displaystyle=f(ab)-f(a)f(b)g(1)g(1)+\\sum_{\\begin{subarray}{c}d_{1}\|a\\\\d_{2}\|b\\end{subarray}}f(d_{1})f(d_{2})g\\left(\\frac{a}{d_{1}}\\right)g\\left(%\\frac{b}{d_{2}}\\right)\\\\\\\\&\\displaystyle=f(ab)-f(a)f(b)\\cdot 1\\cdot 1+\\left(\\sum_{d_{1}\|a}f(d_{1})g\\left%(\\frac{a}{d_{1}}\\right)\\right)\\left(\\sum_{d_{2}\|b}f(d_{2})g\\left(\\frac{b}{d_{2%}}\\right)\\right)\\\\\\\\&=f(ab)-f(a)f(b)+(fg)(a)(fg)(b)\\\\\\\\&=f(ab)-f(a)f(b)+h(a)h(b).\\end{array}$ It follows that $f(ab)=f(a)f(b)$ .∎ The theorem follows from these two lemmas and the fact that convolution is commutative. The theorem has an obvious corollary. Corollary. If $f$ is multiplicative, then so is its convolution inverse. Proof. Let $f$ be multiplicative. Since $f(1)\eq 0$ , $f$ has a convolution inverse $f^{-1}$ . (See convolution inverses for arithmetic functions for more details.) Since $f*f^{-1}=\\varepsilon$ , where $\\varepsilon$ denotes the convolution identity function, and both $f$ and $\\varepsilon$ are multiplicative, the theorem yields that $f^{-1}$ is multiplicative.∎
随便看	Heap1 HeapInsertionAlgorithm heap insertion algorithm HeapRemovalAlgorithm heap removal algorithm HeapsLaw Heapsort heapsort Heaps’ law HeatEquation heat equation HeavisideFormula Heaviside formula HeavisideStepFunction Heaviside step function HeawoodNumber Heawood number HeckeAlgebra Hecke algebra HedgehogSpace hedgehog space Height height HeightbalancedTree height-balanced tree