Mertens function

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

Mertens function

Post by Alhazen »

Can you please check if this formula (see attachments) is right.
M(2o) is Mertens function
Example :
o=25
M(2*25)=M(50)=mu(25+2)+mu(25+4)+mu(25+6)+....+mu(25+24)=-3
mertens.GIF
mertens.GIF (2.62 KiB) Viewed 8804 times
Thank you.
Last edited by Alhazen on Mon Apr 09, 2012 6:01 pm, edited 1 time in total.
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Mertens function

Post by thundre »

I think you used absolute value symbols where you meant to use floor. But since you have defined o as an odd number, you could just say (o-1)/2.

Your formula is interesting in that it can compute M for any 4n+2 number using only n values from the Mobius function, rather than the 4n+2 in the Mertens definition. For some reason, the remaining 3n+2 values cancel each other out.

All multiple of 4 have mu=0. That eliminates another n values, leaving 2n+2 which must cancel.
Image
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Mertens function

Post by Alhazen »

Thank you.
So for what I understood the formula is correct.
More simplification is still possible.

1000000000000000000000 Thanx!!!
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Mertens function

Post by thundre »

I think we should be able to prove this iteratively.

Let n = (o-1)/2, so 2o = 4n+2

Assume M(4n+2) = mu(2n+3) + mu(2n+5) + mu(2n+7) + ... + mu(4n+1) for some n
Does that imply M(4n+6) = mu(2n+5) + mu(2n+7) + ... + mu(4n+1) + mu(4n+3) + mu(4n+5)?

Subtracting the two gives:
mu(4n+3) + mu(4n+4) + mu(4n+5) + mu(4n+6) = -mu(2n+3) + mu(4n+3) + mu(4n+5)
which simplifies to:
mu(4n+6) = -mu(2n+3)
Which must be true, because 4n+6 is squarefree iff 2n+3 is, and 4n+6 is a multiple of 1 additional prime (2).

Since the formula is true for n=1, and being true for n implies it's true for n+1, it must be true for all positive integers.
Image
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Mertens function

Post by Alhazen »

Thank you for the proof.
Is the result a new one? I do not know.
Has the result some consequences on Mertens function? I do not know.
Will it be helpful in computing Mertens function? Yes for sure.
Will it lead to some new algorithm? It is up to the programmers to answer to this question.
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Mertens function

Post by Alhazen »

Here is how I found the formula.

Let us split n in infinite sets.

Set 1 : 1,3,5,7,......,2k+1 (set of odd numbers)
Set 2 : we multiply set 1 by 2 so 2,4,6,10,12,........2(2k+1)
Set 3 : we multiply set 1 by 4
Set 4 : we multiply set 1 by 8
and so on

All the natural numbers will be used only once.

Here are the first elements of each set

Set 1 : 1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31....
Set 2 :2,6,10,14,18,22,26,30,34,38,42,46,50,54,58,62....
Set 3 : 4,12,20,28,36,44,52,60,68,76,84,92,100,108,116,124....
Set 4 : 8,24,40,56,72,88,104,120,136,152,168,184,200,216,232,248....
Set 5 : 16,48,80,112,144,176,208,240,272,304,336,368,400,432,464,496.....
Set 6 :32,96,160,224,288,352,416,480,544,608,672,736,800,864,928,992.....
and so on (each row represents a set :

64,192,320,448,576,704,832,960,1088,1216,1344,1472,1600,1728,1856,1984.....
128,384,640,896,1152,1408,1664,1920,2176,2432,2688,2944,3200,3456,3712,3968....
256,768,1280,1792,2304,2816,3328,3840,4352,4864,5376,5888,6400,6912,7424,7936.....
512,1536,2560,3584,4608,5632,6656,7680,8704,9728,10752,11776,12800,13824,14848,15872....
1024,3072,5120,7168,9216,11264,13312,15360,17408,19456,21504,23552,25600,27648,29696,31744.....

and so on

What is interesting is that starting from the set 3 the Mobius function of all the numbers is equal to zero.

Hence the 2 first sets are needed to compute Mertens function.

Since the sum of the elements of the 2 first sets is equal to zero for each row

1,2
3,6
5,10
and so on

1 2 1 -1
3 6 -1 1
5 10 -1 1
7 14 -1 1
9 18 0 0
11 22 -1 1
13 26 -1 1
15 30 1 -1
17 34 -1 1
19 38 -1 1
......

So the value of Mertens function will be zero for the set of all natural numbers!
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Mertens function

Post by thundre »

Alhazen wrote:Here is how I found the formula.

Let us split n in infinite sets.

Set 1 : 1,3,5,7,......,2k+1 (set of odd numbers)
Set 2 : we multiply set 1 by 2 so 2,4,6,10,12,........2(2k+1)
Set 3 : we multiply set 1 by 4
Set 4 : we multiply set 1 by 8
You're partitioning N into subsets based on the exponent of 2 in each number's prime factorization.

Everything beyond set 2 is a multiple of 22 and therefore not squarefree, so the Mobius function is 0.
Alhazen wrote: So the value of Mertens function will be zero for the set of all natural numbers!
I think M crosses 0 an infinite number of times, but giving M(infinity) a specific value is questionable. You can play tricks re-ordering infinite sets to change the total.
Image
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Mertens function

Post by Alhazen »

Thank you for your comment.
I tried without success to reorder the remaining 2 sets such as I could remove other couples.
I changed my mind so now I think I have found a way to calculate the absolute bounds of M(n) : inf and sup. I mean by absolute : M(n) can reach them but never never exceed them no matter how n behave.
I'm not 100% sure but I'm optimistic.
I created a kind of Mertens-clone sequence. I'm testing it.

Big thanx!
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Mertens function

Post by Alhazen »

Here is my Mertens-clone sequence.
A(n)=+1-1-1+1+1+1-1-1-1-1........+1+1+1....+1((n-1) times)-1-1-1...-1(n times)

We start by +1 then we change the sign (-1) 2 times then we rechange the sign (+1) 3 times and so on.
Example
A(5) = +1-1-1+1+1+1-1-1-1-1+1+1+1+1+1=+3 (corrected)

In fact the idea is that my sequence behave like Mertens but in the worse case where we have +1 (or -1) in a row.
I exclude the zero's to compute a maximal and minimal value of Mertens function in the worst case.
As the sequence contains (n(n+1))/2 elements we can see that A(n) will never exceed the root square of Card(A(n))=(n(n+1))/2.
If we take into account the zero's the bound will be lower.
My problem is how to find an exact approximation of the bounds.
I still need some help.
Maybe someone of you will help me to compute it.
I'm still working on even if I did not fix some problems.

Thank you for any help or any idea.
Last edited by Alhazen on Wed Apr 25, 2012 9:25 pm, edited 1 time in total.
User avatar
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 10:43 am
Location: Netherlands

Re: Mertens function

Post by Lord_Farin »

Grouping terms in pairs of two easily gives $a(2n) = -n$, and then it is immediate that $a(2n+1)=n+1$ (you omitted a minus 1 in your $a(5)$, so this is in fact correct). Not sure what $a(n)$ represents, though.
Image
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Mertens function

Post by Alhazen »

Lord_Farin wrote:Grouping terms in pairs of two easily gives $a(2n) = -n$, and then it is immediate that $a(2n+1)=n+1$ (you omitted a minus 1 in your $a(5)$, so this is in fact correct). Not sure what $a(n)$ represents, though.
Thank you for your comment.
A(n) is a sequence simulating the worst case of Mertens function. You have just to read what I wrote above.
Alhazen
Posts: 94
Joined: Sun Feb 20, 2011 9:55 pm

Re: Mertens function

Post by Alhazen »

There is one thing to keep in mind :
the number of elements of the sequence A(n) is = n(n+1)/2

Example n=5

Card (A(n))=(5*6)/2=30/2=15

I did not know how to express it.
Post Reply