Question

\[\sum\limits_{d\mid n}\mu^2(d)/\tau(d)=?\]

Answer 1

\(\color{blue}{\text{Originally Posted by}}\) @ganeshie8
\[\sum\limits_{d\mid n}\mu^2(d)/\tau(d)=?\]
\(\color{blue}{\text{End of Quote}}\)
It is blank for me

Answer 2

The functions \(\mu\) and \(\tau\) are multiplicative, it follows that \(\mu^2/\tau\) is also multiplicative.

Answer 3

If \(n = p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}\), then we have :
\[\sum\limits_{d\mid n}\mu^2(d)/\tau(d)=\left(\sum\limits_{d\mid p_1^{e_1}}\mu^2(d)/\tau(d)\right)\left(\sum\limits_{d\mid p_2^{e_2}}\mu^2(d)/\tau(d)\right)\cdots\left(\sum\limits_{d\mid p_r^{e_r}}\mu^2(d)/\tau(d)\right) \]

Answer 4

thanks @OregonDuck

Answer 5

we need to prove LHS=RHS?

Answer 6

we need to find an expression for the sum in main question

Answer 7

the sum itself is multiplicative, meaning :
\[f(ab) = f(a)f(b)\]
whenever \(\gcd(a,b)=1\)

Answer 8

Here is no LHS and RHS

Answer 9

since all the prime powers are relatively prime, we can split the sum as shown above..

Answer 10

Don't understand what it is? The previous one is at least understandable
but this one is so far..............

Answer 11

:)
we can write it in this form-\(\sum\limits_{d\mid n}\mu^2(d)/\tau(d)=\left(\sum\limits_{d\mid p_1^{e_1}}\mu^2(d)/\tau(d)\right)\left(\sum\limits_{d\mid p_2^{e_2}}\mu^2(d)/\tau(d)\right)\cdots\left(\sum\limits_{d\mid p_r^{e_r}}\mu^2(d)/\tau(d)\right)\)

the divisors of any \(p_i^{e_i}\) will be like this-> \(1,~p_i,~p_i^2,~p_i^3,..\)

\(\left(\sum\limits_{d\mid p_1^{e_1}}\mu^2(d)/\tau(d)\right)\) = \(\Large{\frac{ \mu^2(1) }{ \tau(1) }+\frac{ \mu^2(p_1) }{ \tau(p_1) }+\frac{ \mu^2(p_1^2) }{ \tau(p_1^2) }}+\frac{ \mu^2(p_1^3) }{ \tau(p_1^3) }....\)

after \(p_1^2,~p_1^3,~p_1^4.....\) are divisible by \(p^2\)
so \(0=\mu(p_1^2)=\mu(p_1^3)=\mu(p_1^4)=...\)


so basically all that part will become 0 and we will be left with

\(\left(\sum\limits_{d\mid p_1^{e_1}}\mu^2(d)/\tau(d)\right)=\Large{\frac{ \mu^2(1) }{ \tau(1) }+\frac{ \mu^2(p_1) }{ \tau(p_1) }}\)
\(\left(\sum\limits_{d\mid p_1^{e_1}}\mu^2(d)/\tau(d)\right)=\large{1+\frac{1}{2}}\)

if the prime factorization of \(n\) has \(r\) primes
then

\(\sum\limits_{d\mid n}\mu^2(d)/\tau(d)=\large{\left( 1+\frac{ 1 }{ 2 } \right)^r}\)

we had to do this right?

Answer 12

wow! that looks perfect !

Answer 13

but \(r\) is a variable that is not there in the actual question right ?

Answer 14

that can be easily fixed by using number of distinct prime factors function : \(\omega(n)\)
http://mathworld.wolfram.com/DistinctPrimeFactors.html

Answer 15

\[\sum\limits_{d\mid n}\mu^2(d)/\tau(d)=\large{\left( 1+\frac{ 1 }{ 2 } \right)^{\omega(n)}}\]

Answer 16

\(\omega(n)\) spits out the number of distinct prime factors of \(n\)

Answer 17

\(\omega(2*5*7^5) = 3\)

\(\omega(11*31) = 2\)

etc

Answer 18

ok so instead of \(r\) we should use the function \(\omega(n)\) because its a general type of notation with our variable \(n\)

Answer 19

its not a big deal, \(\omega(n)\) is a very popular function, it shows up in many places

Answer 20

okay :) i'll study this function

Answer 21

not much to study actually, it just spits out the number of prime factors that all

Answer 22

\(\tau, \sigma, \phi,\mu\) are more interesting functions...

Answer 23

thats just in my opinion again..

Answer 24

but what if the number is very big
is there any formula to find the number of prime factors

Answer 25

without doing any prime factorization..

Answer 26

do you expect there exists such a formula ?

Answer 27

If such a formula had existed, prime numbers wouldn't be any fun

Answer 28

because then it can be used to check if a number is prime

Answer 29

ah yes :)

Answer 30

people have been trying for such a formula though

Answer 31

it seems impossible as prime numbers are just so mysterious

Answer 32

it has this trivial yet interesting property :
\[\omega(ab) = \omega(a)+\omega(b)\]

whenever \(\gcd(a,b)=1\)

Answer 33

yeah if gcd is 1 means no common prime factor

if prime factorization is like this-
\(a=p_1p_2p_3..~~and~~~b=p_ap_bp_c..\) its clear that in the prime factorization of \(ab\) will have all these diff primes so \(\omega(ab)=\omega(a)+\omega(b)\)

Answer 34

i can conclude these stuff only :-

\(\Large if~ n=p_1p_2....p_i \) such that \( {p_i}'s \) are distinct primes, then
\(\Large \sum_{d|n}\dfrac{\mu^2(d)}{\tau(d)}=\sum_{d|n}\dfrac{1}{\tau(d)}\\\Large =\sum_{d|n}\frac{1}{\log_d{\prod_{i|d}{i}}}\)

and this also goes for any n.

\(\Large \sum_{d|n}\dfrac{\mu^2(d)}{\tau(d)}=\Large \sum_{d|n^2}\dfrac{\mu^2(d)}{\tau(d)}\)

Answer 35

wait its like this function be simplified as sum of 1 over tau(d) for d|n, as
\(\mu(d)=0 ~~ when ~~p^2|d.\)

Answer 36

ok here is a full proof for what i'm saying "need time to write"

Answer 37

\( \Large \mu^2(d)=\left\{\begin{matrix}
0 & if & p_i^2|d\\
1 & else&
\end{matrix}\right. \\ \Large

\begin{matrix}
n=\prod_{i=1}^{\omega(n)}p_i^{k_i}
\end{matrix}\\
\Large
\begin{matrix}
n_{\omega(n)}=\prod_{i=1}^{\omega(n)}p_i
\end{matrix}\\


\begin{align*}
f(n) &= \sum_{d|n}\frac{\mu^2(d)}{\tau(d)} \\
&= \frac{\mu^2(p_1)}{\tau(p_1)}+\frac{\mu^2(p_1^2)}{\tau(p_1^2)}+...+ \frac{\mu^2(p_1^{k_{\omega(n)} } )}{\tau(p_1^{k_{\omega(n)} } )}\\
&+\frac{\mu^2(p_1p_2)}{\tau(p_1p_2)}+\frac{\mu^2(p_1^2p_2)}{\tau(p_1^2p_2)}+...+ \frac{\mu^2(p_1^{k_{\omega(n)} } p_2^{k_{\omega(n)} } )}{\tau(p_1^{k_{\omega(n)} } p_2^{k_{\omega(n)} } )} \\
&+... \\
&+ \frac{\mu^2(p_1p_2...p_{\omega(n)})}{\tau(p_1p_2...p_{\omega(n)})}+...+\frac{\mu^2((p_1p_2...p_{\omega(n)})^{\omega(n)})}{\tau((p_1p_2...p_{\omega(n)})^{\omega(n)})}\\
&= \frac{1}{\tau(p_1)}+ \frac{1}{\tau(p_2)}+...+\frac{1}{\tau(p_{\omega(n)})} \\
&+\frac{1}{\tau(p_1p_2)}+ \frac{1}{\tau(p_2p_3)} +... \\
&+... \\
&+ \frac{1}{\tau(p_1p_2...p_{\omega(n)})}\\
&=\sum_{d|{n_{\omega(n)}}}\frac{1}{\tau(d)}

\end{align*}
\)

Answer 38

=)

Answer 39

Small note before I really play round with this, is @ganeshie8 's thing, I noticed a while back that the similar \(\Omega(n)\) function is a lot like the logarithm:

\[\Omega(p^aq^b)=a \Omega(p) + b \Omega(q)\]

Anyways time to play around with the actual problem hehe...!

Answer 40

but i have consider about @imqwerty everything looks fine then i thought of such cases like

n=1*2*3*5
cuz i have answer of (1+1/2^5+1/2^6+1/2^3)
seems contradict with urs if its (1+1/2)3
hmmm

Answer 41

The way I remember it is like this:

\[\omega(n) \le \Omega(n)\]

the little one is smaller than the bigger one haha. the smaller one strips off the exponents and just counts the unique prime factors while the big one tells you the total prime factors. Pretty cool.

Answer 42

oh yeah i should remember that in its easyxD Omega vs omega

Answer 43

hmm my method is also not applicable for the numbers of the form \(n=p^k\)
where \(p\) is a prime. For example n=8

Answer 44

p=2 and k=3 does it not? #_#

Answer 45

oops sorry :)

Answer 46

Heh :P

Answer 47

well my method says if n=p^k and p is prime then
f(n)=1+1/2 always xD so i think its the same as urs lol

Answer 48

now lets play with multiplicative thingy =D

Answer 49

Oh here's a fun thing for @imqwerty to prove for multiplicative functions if he hasn't seen this before:

All interesting multiplicative functions have f(1)=1. Prove it! :P

Answer 50

f(mn)=f(n)*f(m)
g(m)=f(m*1)=f(m)*f(1)

Answer 51

now\( f(n)=\sum_{d|n}1/\tau(n)\) is multiplicative right ?

Answer 52

BTW Here's how I derived the formula for the thing earlier, first I realize once you figure out how a multiplicative function works for \(f(p^k)\) then you know how it works for any combination cause you can multiply them together (I really think in terms of linear algebra and how a transformation acts on the basis set tells you how it affects any arbitrary value here, cause I'm sick in the head like that)

So now we use the fact that \(\mu(p^k) = 0\) for k>1 and really all we have to look at are:

\[\frac{\mu^2(1)}{\tau(1)}+ \frac{\mu^2(p)}{\tau(p)} = \frac{3}{2}\]

Now like I said I do earlier, I multiply the result of acting on one prime altogether, and since there is one of these for each distinct prime:

\[\left( \frac{3}{2} \right)^{\omega(n)}\]

Answer 53

:O
ok all interesting functions are-> \(\tau(n)\), \(\phi(n)\), \(\sigma(n)\), \(\mu(n)\)

ok so the function is mutiplicative hmmm
so (; ikram gave a hint
well its pretty clear
\(f(n)=f(n*1)=f(n)*f(1)\)
can we just say that for f(n) to be f(n) , f(1) must be 1 :/
or else if its not 1 then things get bad
for example
\(2=\tau(3)=\tau(3*1)=\tau(3)* \tau(1)=2* \tau(1)\)
if \(\tau(1)\) is not 1 then \(\tau(3) \ne \tau(3)\) so \(f(1)=1\)

Answer 54

@imqwerty Yeah that's multiplicative. In fact, all multiplicative functions with the Dirichlet convolution are multiplicative functions. What's the Dirichlet convolution? Well one way to write it (in a fairly unintuitive way is):

\[h(n) = \sum_{d|n} f(d) g(\tfrac{n}{d}) \]

So in your example you can pick \[f(n)=\frac{1}{\tau(n)}\] and \[g(n)=1\] and because of this rule (I have given with no justification :P ) that means h(n) is also multiplicative!

Answer 55

Ahhh @imqwerty Actually although those are some interesting functions, they're not all haha. I made it as a joke based on how I proved it:

\[f(1)=f(1*1)=f(1)*f(1)\]
So now either f(1)=1 or f(1)=0.

But f(1)=0 means f(n)=0 for all values! BORING! xD

Answer 56

\( f(n)=f(p_1p_2p_3...p_{\omega({n})}) =f(p_1)f(p_2)...f(p_{\omega(n)})=(1+1/2)^{\omega(n)}
\)

Answer 57

same as @imqwerty hmm im kinda not convinced about it lol

Answer 58

@kainui but how can we if f(1) will either be 1 or 0
it wuld depend on the function

Answer 59

hahaha there is no multiplicative function with f(1)=0 unless ur working on a base such that f(i)=i identity and i is not 1 .

Answer 60

\[f(1)=f(1*1)\]
There I haven't done anything special, 1=1*1
\[f(1*1)=f(1)*f(1)\]
since \(\gcd(1,1)=1\) we can split it because f(n) is multiplicative!

Now we know \[f(1)=f(1)*f(1)\] and we can divide \(f(1)\) from both sides to see it must be 1 as long as f(1) is no 0. If f(1)=0 then we have for all values:

\[f(n)=f(1*n)=f(1)*f(n)=0*f(n)=0\]

Answer 61

:O okay :D

Answer 62

what culd be the possible reason behind the failure of (1+1/2)^r method?

Answer 63

well, two reasons
major error
misunderstood

Answer 64

I don't think there is a failure of the method, maybe this could help convince you that we can do this thing where we separate it and then combine it back together:

Multiply the left side to show that you get the right hand side for this arbitrary multiplicative function:
\[[f(1)+f(p)]*[f(1)+f(q)+f(q^2)]=\]\[ f(1)+f(p)+f(q)+f(pq)+f(q^2)+f(pq^2) \]

Answer 65

i think its not multiplicative
\(\sum\limits_{d\mid n}\mu^2(d)/\tau(d)=\left(\sum\limits_{d\mid p_1^{e_1}}\mu^2(d)/\tau(d)\right)\left(\sum\limits_{d\mid p_2^{e_2}}\mu^2(d)/\tau(d)\right)\cdots\left(\sum\limits_{d\mid p_r^{e_r}}\mu^2(d)/\tau(d)\right)\)

i plugged n=30 in here and got the same answer as \(\large\ (1+\frac{1}{2})^3\)

Answer 66

You think it's not multiplicative but you got the same answer...?

Answer 67

f(1*2*3)= 1+1/2+1/2+1/4= 9/4
multiplicative method says
f(1*2*3)=(3/2)^2=9/8

hahahahaha ok we have calculation error only :P

Answer 68

i mean like i put n=30 in that 1st express and got answer 27/64 but it should be 13/4
so something is wrong there

Answer 69

which expression ?

Answer 70

this one-
\(\sum\limits_{d\mid n}\mu^2(d)/\tau(d)=\left(\sum\limits_{d\mid p_1^{e_1}}\mu^2(d)/\tau(d)\right)\left(\sum\limits_{d\mid p_2^{e_2}}\mu^2(d)/\tau(d)\right)\cdots\left(\sum\limits_{d\mid p_r^{e_r}}\mu^2(d)/\tau(d)\right)\)

Answer 71

n=30
f(30)=f( 1*2*3*5)=1+1/2+1/2+1/2+1/4+1/4+1/4+1/8=27/8 lol xD

Answer 72

i am getting confused :/ 27/64 27/8 13/4 D:

Answer 73

nvm i'm going to sleep

goodnight :D

Answer 74

me too :) goodnight :D

Answer 75

n=30 here we go!

\(\sum\limits_{d\mid 30}\mu^2(d)/\tau(d)=\left(\sum\limits_{d\mid 2}\mu^2(d)/\tau(d)\right)\left(\sum\limits_{d\mid 3}\mu^2(d)/\tau(d)\right)\left(\sum\limits_{d\mid 5}\mu^2(d)/\tau(d)\right)\)

Now let's write out all the terms of both sides of that equation.

This is the statement that this left hand side here:

\[\frac{\mu^2(1)}{\tau(1)}+ \frac{\mu^2(2)}{\tau(2)}+\frac{\mu^2(3)}{\tau(3)}+\frac{\mu^2(5)}{\tau(5)}+\frac{\mu^2(6)}{\tau(6)}+ \frac{\mu^2(10)}{\tau(10)}+\frac{\mu^2(15)}{\tau(15)}+\frac{\mu^2(30)}{\tau(30)}\]

Is exactly equal to this right hand side here:

\[\left(\frac{\mu^2(1)}{\tau(1)}+ \frac{\mu^2(2)}{\tau(2)} \right)\left(\frac{\mu^2(1)}{\tau(1)}+ \frac{\mu^2(3)}{\tau(3)} \right)\left(\frac{\mu^2(1)}{\tau(1)}+ \frac{\mu^2(5)}{\tau(5)} \right)\]

Multiply those three binomial terms together and see for yourself that they are indeed exactly equal. :D

Answer 76

@imqwerty trust me on this, and write out the multiplication of that bottom expression, and I think you will understand a lot better.

Answer 77

huh lol.

Answer 78

just DO IT! lol

Answer 79

that is \(\large\ (1+\frac{1}{2})^3=\frac{27}{8}\)

Answer 80

which means i win :P
i just note the formula was correct both of them but we had error in calculation last night so :P

Answer 81

but the answer should be \(\large\frac{13}{4}\) right and its 27/8 m getting confused
where did we had calculation error ?

Answer 82

and how is the formula correct when its giving the wrong answer

Answer 83

why it should be 13/4 ?

its (3/2)^3=27/8 :O

Answer 84

Nice !

Answer 85

yes so \(\Large\left( 1+\frac{1}{2} \right)^{\omega(n)}\) is correct :D

in your next quetions m having difficulty with the \(\sigma(n)\) part

Answer 86

While we're at this problem of multiplicative functions, can we prove a more general result

Answer 87

is it easy to prove that \(\mu(n)\) is multiplicative ?

Answer 88

prove each of below functions are multiplicative

1) \(\tau(n)\)
2) \(\sigma(n)\)
3) \(\mu(n)\)

Answer 89

\(f(n)\) is multiplicative if
\(f(ab) = f(a)f(b)\)
whenever \(\gcd(a,b)=1\)

Answer 90

we need to show \(\mu(1)=1\) and show that
\(\mu(nm)=\mu(m)\mu(n)\)
\(\mu(n)=\begin{cases}
1 & \text{ if } n= 1\\
0 & \text{ if } p^2|n \\
(-1)^{\omega(n)} & \text{ if } n=p_1p_1...p_{\omega(n)}

\end{cases}

\)

Answer 91

do we take cases to prove for \(\mu(n)\)?

Answer 92

\(\mu(1) = 1\) is by definition

we need to prove \(\mu(ab) = \mu(a)\mu(b)\) whenever \(\gcd(a,b)=1\)

Answer 93

we can use cases if that is easy, but it seems we can do it straight without any cases...

Answer 94

so from definition \(\mu(1)=1\)

we need to show \(\mu(nm)=\mu(n)\mu(m)\)
so we have 3*3 cases
if n or m =1 its trivial done.
let p^2|n w.l.o
\(\mu(mn)=\mu(m).\mu(n)\\ 0=0\) also trivial

Answer 95

Oh rihgt, cases are required yeah...

Answer 96

now we need to consider the last case
\(gcd(n,m)=1\rightarrow n=p_1...p_\omega(n) , m=q_1...q_\omega(n) , q_i\neq p_i \forall i\)
\(\begin{align*}
\mu(mn) &= (-1)^{{\omega(m)}+\omega(n)}\\
&=(-1)^{\omega(m)} . (-1)^{\omega(n)} \\
&=\mu(m).\mu(n)
\end{align*} \)

Answer 97

next function is tau ?