Mertens function

[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 (2.62 KiB) Viewed 8804 times

Thank you.

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

[Alhazen]

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

1000000000000000000000 Thanx!!!

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

[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]

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]

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 2² and therefore not squarefree, so the Mobius function is 0.

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.

[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]

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.

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

[Alhazen]

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]

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.