multiplicative functionMultiplicativeFunction2002-06-12 10:36:182008-03-03 13:55:02Definitionmultiplicativecompletely multiplicativecompletely multiplicative functionconvolution identity functionconvolution inversenumber theoryarithmetic function% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here\PMlinkescapeword{convolution}
\PMlinkescapeword{formula}
\PMlinkescapeword{properties}
\PMlinkescapeword{property}
\PMlinkescapeword{restriction}
\PMlinkescapeword{words}
In number theory, a \emph{multiplicative function} is an arithmetic function $f \colon \mathbb{N} \to \mathbb{C}$ such that $f(1)=1$ and, for all $a,b \in \mathbb{N}$ with $\gcd(a,b)=1$, we have $f(ab)=f(a)f(b)$.
An arithmetic function $f(n)$ is said to be \emph{completely multiplicative} if $f(1)=1$ and $f(ab)=f(a)f(b)$ holds for \emph{all} positive integers $a$ and $b$, \PMlinkescapetext{even} when they are not relatively prime. In this case, the function is a homomorphism of monoids and, because of the fundamental theorem of arithmetic, is completely determined by its \PMlinkname{restriction}{Restriction} to prime numbers. Every completely multiplicative function is multiplicative.
Outside of number theory, the \PMlinkescapetext{term} multiplicative is usually used for all functions with the property $f(ab)=f(a)f(b)$ for all arguments $a$ and $b$. This entry discusses number theoretic multiplicative functions.
\paragraph{Examples}
Examples of multiplicative functions include many important functions in number theory, such as:
\begin{itemize}
\item $\varphi(n)$: the Euler totient function (also denoted $\phi(n)$), counting the totatives of $n$;
\item $\mu(n)$: the M\"{o}bius function, which determines the parity of the prime factors of $n$ if $n$ is squarefree;
\item $\tau(n)$: the divisor function (also denoted $d(n)$), counting the positive divisors of $n$;
\item $\sigma(n)$: the sum of divisors function (also denoted $\sigma_1(n)$), summing the positive divisors of $n$;
\item $\sigma_{k}(n)$: the sum of the $k$-th powers of all the positive divisors of $n$ for any complex number $k$ (typically a natural number);
\item $\hbox{id}(n)$: the identity function, defined by $\hbox{id}(n) = n$;
\item $\hbox{id}^{k}(n)$: the power functions, defined by $\hbox{id}^{k}(n) = n^{k}$ for any complex number $k$ (typically a natural number);
\item $1(n)$: the constant function, defined by $1(n)=1$;
\item $\varepsilon(n)$: the \emph{convolution identity function}, defined by:
\[
\varepsilon(n) = \sum_{d|n} \mu(d) =
\begin{cases}
1 &\text{if } n=1 \\
0 &\text{if } n\neq 1
\end{cases}
\]
where $d$ runs through the positive divisors of $n$.
\end{itemize}
\paragraph{Properties}
A multiplicative function is completely determined by its values at the powers of prime numbers, a consequence of the fundamental theorem of arithmetic. Thus, if $n$ is a product of powers of distinct prime numbers, say $n=p^aq^b\cdots$, then $f(n)=f(p^a)f(q^b)\cdots$. This property of multiplicative functions significantly reduces the need for computation, as in the following examples for $n=144=2^4 \cdot 3^2$:
\begin{eqnarray*}
\sigma(144) &=& \sigma_{1}(144)=\sigma_{1}(2^4)\sigma_{1}(3^2)= (1^1+2^1+4^1+8^1+16^1)(1^1+3^1+9^1)=31 \cdot 13=403 \\
\sigma_{2}(144) &=& \sigma_{2}(2^4)\sigma_{2}(3^2) = (1^2+2^2+4^2+8^2+16^2)(1^2+3^2+9^2)=341 \cdot 91=31031 \\
\sigma_{3}(144) &=& \sigma_{3}(2^{4})\sigma_{3}(3^{2}) = (1^3+2^3+4^3+8^3+16^3)(1^3+3^3+9^3)=4681 \cdot 757=3543517
\end{eqnarray*}
Similarly, we have:
\begin{eqnarray*}
\tau(144) &=& \tau(2^4)\tau(3^2)=(4+1)(2+1)=5 \cdot 3=15 \\
\varphi(144) &=& \varphi(2^4)\varphi (3^2)=2^3(2-1)3^1(3-1)=8 \cdot 1 \cdot 3 \cdot 2=48
\end{eqnarray*}
\paragraph{Convolution}
Recall that, if $f$ and $g$ are two arithmetic functions, one defines a new arithmetic function $f*g$, the Dirichlet convolution (or simply convolution) of $f$ and $g$, by
\[
(f*g)(n) = \sum_{d\vert n} f(d)g \left( {n\over d} \right),
\]
where the sum extends over all positive divisors $d$ of $n$. Some general properties of this operation with respect to multiplicative functions include (here the argument $n$ is omitted in all functions):
\begin{itemize}
\item If both $f$ and $g$ are multiplicative, then so is $f*g$ (proven \PMlinkname{here}{ElementaryResultsAboutMultiplicativeFunctionsAndConvolution});
\item $f*g = g*f$ (proven \PMlinkname{here}{ArithmeticFunctionsFormARing});
\item $(f*g)*h = f*(g*h)$ (proven \PMlinkname{here}{ArithmeticFunctionsFormARing});
\item $f*\varepsilon = \varepsilon *f = f$ (proven \PMlinkname{here}{ArithmeticFunctionsFormARing});
\item If $f$ is multiplicative, there exists a multiplicative function $g$ such that $f*g=\varepsilon$ (proven \PMlinkname{here}{ElementaryResultsAboutMultiplicativeFunctionsAndConvolution}). In other words, every multiplicative function has a \emph{convolution inverse} that is also multiplicative.
\end{itemize}
This shows that, with respect to convolution, the multiplicative functions form an abelian group with identity element $\varepsilon$. \PMlinkescapetext{Relations} among the multiplicative functions discussed above include:
\begin{itemize}
\item $\mu*1=\varepsilon$ (the M\"{o}bius inversion formula)
\item $1*1=\tau$
\item $\hbox{id}*1 = \sigma$
\item $\hbox{id}^{k}*1 = \sigma ^{k}$
\item $\phi*1 = \hbox{id}$
\end{itemize}
Given a completely multiplicative function $f$, its convolution inverse is $f\mu$. See \PMlinkname{this entry}{FormulaForTheConvolutionInverseOfACompletelyMultiplicativeFunction} for a proof.