PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (205)
Orphanage
Unclass'd
Unproven (490)
Corrections (8)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] elementary results about multiplicative functions and convolution (Theorem)

One of the most important elementary results about multiplicative functions and convolution 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 % latex2html id marker 422 $ a,b \in \mathbb{N}$ with $ \gcd(a,b)=1$. Then any divisor $ d$ of $ ab$ can be uniquely factored as $ d=d_1d_2$, where $ d_1$ divides $ a$ and $ d_2$ divides $ b$. When a divisor $ d$ of $ ab$ 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,

$ (f*g)(ab)$ $ \displaystyle =\sum_{d\vert ab} f(d) g\left( \frac{ab}{d} \right)$
  $ \displaystyle =\sum_{\substack{d_1\vert a \\ d_2\vert b}} f(d_1d_2) g\left( \frac{ab}{d_1d_2} \right)$
  $ \displaystyle =\sum_{\substack{d_1\vert a \\ d_2\vert b}} f(d_1)f(d_2) g\left( \frac{a}{d_1} \right) g\left( \frac{b}{d_2} \right)$
  $ \displaystyle =\left( \sum_{d_1\vert a} f(d_1) g\left( \frac{a}{d_1} \right) \right) \left( \sum_{d_2\vert b} f(d_2) g\left( \frac{b}{d_2} \right) \right)$
  $ \displaystyle =(f*g)(a)(f*g)(b)$.
$ \qedsymbol$
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 % latex2html id marker 490 $ a,b \in \mathbb{N}$ with $ \gcd(a,b)=1$. Induction will be used on $ ab$ 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 $ ab$ be an arbitrary natural number. The induction hypothesis yields that, if $ d_1$ divides $ a$, $ d_2$ divides $ b$, and $ d_1d_2<ab$, then $ f(d_1d_2)=f(d_1)f(d_2)$. Thus,

\begin{displaymath}\begin{array}{ll} h(a)h(b) & =h(ab) \ \ & =(f*g)(ab) \ ... ...f*g)(a)(f*g)(b) \ \ & =f(ab)-f(a)f(b)+h(a)h(b). \end{array}\end{displaymath}

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

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) \neq 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. $ \qedsymbol$



"elementary results about multiplicative functions and convolution" is owned by Wkbj79.
(view preamble)

View style:

See Also: convolution inverses for arithmetic functions


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: convolution identity function, convolution inverses for arithmetic functions, convolution inverse, obvious, commutative, induction hypothesis, natural number, induction, implies, divides, divisor, multiplicative, arithmetic functions, multiplicative functions
There is 1 reference to this entry.

This is version 13 of elementary results about multiplicative functions and convolution, born on 2006-07-30, modified 2007-06-27.
Object id is 8197, canonical name is ElementaryResultsAboutMultiplicativeFunctionsAndConvolution.
Accessed 1155 times total.

Classification:
AMS MSC: 11A25 (Number theory :: Elementary number theory :: Arithmetic functions; related numbers; inversion formulas)
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)