How to compute a dirichlet product of arithmetic function

347 Views Asked by At

The arithmetic function v(n) be the number of distinct prime factors of n. And Dirichlet product f = m * v be given I hope to prove that f is either 0 or 1 for every integers n. ( v(1) = 0 is defined and m is mobius function )

Firstly, i tried to divide cases, n is a square free or Not.

If n is a square free Let $n=p_1p_2...p_r$ $p_i$ are distinct prime numbers

$f(n) = \sum_{d|n} m(d)v(n/d)$ $=\sum_{k=0}^r\binom r k (-1)^r (r-k) $

I cant compute this sum. What is the matter of this process? And if n is Not a square free, How should i start ?

1

There are 1 best solutions below

0
On BEST ANSWER

I will use more common notations : $\mu(n)$ for the Möbius function and $\omega(n)$ for the distinct prime factors function omega.

So you want $\;f:= \mu * \omega$.

In pari/gp this becomes simply f(n)=sumdiv(n,d,moebius(d)*omega(n/d)) and from the first values it is clear that the answer is probably the sequence OEIS A010051 that is :

  • $f(n)=1\ $ for $n$ prime and $0$ else (this is the "prime characteristic function")

Let's suppose that $f$ is the prime characteristic function and define $\omega$ with : \begin{align} \omega(n)&= \sum_{\text{prime}\;p|n} 1\\ &=\sum_{d|n} f(d)\\ \end{align}

Now simply use the Möbius inversion formula to get $\;f=\mu * \omega\;$ that is $\;\displaystyle f(n) = \sum_{d|n} \mu(d)\;\omega(n/d)$.
(this trick was used by Kunnysan in this thread and should be considered for every convolution with the Möbius function $\mu$) $$-$$ One may object that the answer needed to be known (or guessed) so let's try the direct method you suggested for $\,n=p_1^{a_1}\;p_2^{a_2}\cdots p_r^{a_r}$ (we will suppose $n>1$ i.e. $\,r\ge 1\,$ since $f(1)=0$ is easy) : \begin{align} f(n) &= \sum_{d|n} \mu(d)\;\omega(n/d)\\ &= \sum_{\text{squarefree}\ d|n} (-1)^{\omega(d)}\;\omega(n/d)\\ &\quad\text{(partitioning $d$ by its prime divisors count)}\\ \tag{1}&= \omega(n)-\sum_{\text{prime}\;p_i|n} \omega\left(\frac n{p_i}\right)+\sum_{\text{primes}\;p_i<p_j|n} \omega\left(\frac n{p_i\;p_j}\right)-\\&\quad \cdots+(-1)^r \omega\left(\frac n{p_1\;p_2\cdots p_r}\right)\\ \end{align} As you noticed when $n$ is square free $\ \omega\left(\dfrac n{\underbrace{p_i\cdots p_l}_{k\ \text{terms}}}\right)\ $ becomes simply $(r-k)$ and we get : $$\tag{2}f(n)=\sum_{k=0}^r (-1)^k \binom{r}{k} (r-k)$$ Defining $\;g(x):=\sum_{k=0}^r \binom{r}{k} x^k=(1+x)^r\,$ gives $\,x\;g'(x)=\sum_{k=0}^r k\binom{r}{k} x^k=x\,r\,(1+x)^{r-1}$ and : $$\tag{3}f(n)=r\,g(-1)-(-1)\,g'(-1)=(1+(-1))^r+r\,(1+(-1))^{r-1}$$ For $n$ square free we have thus $\,f(n)=0\,$ except for $\,r=1\,$ in which case $f(n)=f(p_1)=1$ (because $g'(-1)=1$, the $f(n)$ formula remains valid using $0^0=1$).

If $n$ is not square free we will have one or more additional exponents $a_l>1$ when compared with $n_0=p_1\,p_2\cdots p_r$. Each associated $p_l$ will increment the corresponding $\;\omega\left(\dfrac n{p_l\cdots}\right)\;$ terms in $(1)$ for $\,f(n_0)\,$ giving I think $\binom{r-1}{k-1}$ terms for $k$ primes (the possible choices for the remaining primes).

The total additional contribution for any $p_l$ should thus be $\;\displaystyle\sum_{k=1}^r (-1)^k \binom{r-1}{k-1}=-(1-1)^{r-1}\,$ which is $\,0\,$ for $r>1$ and $-1$ for $\,r=1$ (i.e. a total of $0$ for the specific case $\,n=p^a, a>1\;$ and $\,0\,$ for all the non square free cases).

Thus in general $f(n)$ will be the "prime characteristic function".

Sorry if I missed a faster direct derivation. The first trick is much easier...