Euler totient and Mobius function

Primes, divisors, arithmetic, number properties, ...
Post Reply
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Euler totient and Mobius function

Post by Alhazen »

Hi,

Here is an identity to prove :
rightformula.GIF
rightformula.GIF (3.55 KiB) Viewed 7996 times
Is there a way to express mu(n) as function of phi(n)?

Thank you for any clue

Ps : I'm sorry I corrected the mistake.
Last edited by Alhazen on Fri Apr 06, 2012 8:35 pm, edited 1 time in total.
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Euler totient and Mobius function

Post by Alhazen »

Is it a new result or is it yet known?
Thank you for any clue.
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Euler totient and Mobius function

Post by thundre »

1: 1 0
2: 3 1
3: 6 1

I don't see them ever being equal. Why even sum the right side to n? floor(n/(n+1)) = 0 for all positive n, so any expression multiplied by that will be 0.
Image
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Euler totient and Mobius function

Post by Alhazen »

thundre wrote:1: 1 0
2: 3 1
3: 6 1

I don't see them ever being equal. Why even sum the right side to n? floor(n/(n+1)) = 0 for all positive n, so any expression multiplied by that will be 0.
You are right I did a big mistake.
It is k not k+1

Sorry sorry sorry.
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Euler totient and Mobius function

Post by thundre »

Alhazen wrote:It is k not k+1
The updated formula checks out.

a(n) seems to approach n2 * .60792 for large n.

I have no idea how to prove the right and left sides are always equal.
Image
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Euler totient and Mobius function

Post by Alhazen »

Thank you very much and once again sorry my mistake.
User avatar
kevinsogo
Administrator
Posts: 1204
Joined: Thu Sep 16, 2010 4:39 am
Location: Manila, Philippines

Re: Euler totient and Mobius function

Post by kevinsogo »

ceil(n/k) is just floor(n/k) + 1 unless k divides n, so the right hand side is equal to:

$$\sum_{k=1}^n \mu\left(k\right) \left\lfloor \frac{n}{k} \right\rfloor \left(\left\lfloor \frac{n}{k} \right\rfloor + 1\right) - \sum_{k|n} \mu\left(k\right) \left\lfloor \frac{n}{k} \right\rfloor$$
$$= \sum_{k=1}^n \mu\left(k\right) \left\lfloor \frac{n}{k} \right\rfloor^2 + \sum_{k=1}^n \mu\left(k\right) \left\lfloor \frac{n}{k} \right\rfloor - \sum_{k|n} \mu\left(k\right) \left(\frac{n}{k}\right)$$
$$= S_1 + S_2 - S_3 $$

Now, we can prove the following:
S1 = 2 [sum]1[le]k[le]n φ(k) - 1
S2 = 1
S3 = φ(n)
Thus it is equal to your left hand side.

The proofs of these are relatively simple so you may try proving them yourself.

Hints:
The proof for S1 and S2 uses concepts from Problem 351 (View Problem).
The proof for S3 uses the substitution l = n/k and Möbius inversion.
Last edited by kevinsogo on Thu Apr 12, 2012 1:09 am, edited 1 time in total.
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Euler totient and Mobius function

Post by Alhazen »

Thank you for the proof.
No one found it in another forum.
Someone had found part of it.
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Euler totient and Mobius function

Post by Alhazen »

thundre wrote:
Alhazen wrote:It is k not k+1
The updated formula checks out.

a(n) seems to approach n2 * .60792 for large n.

I have no idea how to prove the right and left sides are always equal.
And 0.60792 = 6/(π^2)
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Euler totient and Mobius function

Post by Alhazen »

6/(π^2) is the density of squarefree numbers.
What can we do with that?
User avatar
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 10:43 am
Location: Netherlands

Re: Euler totient and Mobius function

Post by Lord_Farin »

Alhazen wrote:6/(π^2) is the density of squarefree numbers.
What can we do with that?
The squarefree numbers are the ones for which the Möbius function is nonzero.
Image
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Euler totient and Mobius function

Post by Alhazen »

Lord_Farin wrote:
Alhazen wrote:6/(π^2) is the density of squarefree numbers.
What can we do with that?
The squarefree numbers are the ones for which the Möbius function is nonzero.

Yes! You are right.
Did someone said otherwise?
There are some links to exploit.
Did you take a look to my new formulation of the Mertens function ?
Ethan1024
Posts: 2
Joined: Wed Sep 11, 2013 7:09 am

Re: Euler totient and Mobius function

Post by Ethan1024 »

From the Dirichlet convolution representation of the totient function
k3.PNG
k3.PNG (1.14 KiB) Viewed 6645 times
Though it still sort of feels like I am cheating since I am still using lower order values of the mobius function,
and because it requires knowing all the divisors of n.
Post Reply