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 ?


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...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.