[seqfan] The ordinary generating function for the Moebius function
Mats Granvik
mgranvik at abo.fi
Sat Mar 5 19:00:03 CET 2011
I here intend to show what a non-finite expression for the ordinary generating
function (o.g.f) for the Möbius function possibly could look like.
The reason for or the pattern in the expression is easy to understand
but the expression is not short.
With an o.g.f I mean a non-finite expression that equals:
mu(1)*x^1 + mu(2)*x^2 + mu(3)*x^3 + ...
We begin by considering the binomial series:
(1+x)^-1 = 1 - x^1 + x^2 - x^3 + x^4 - ...
Applied to triangular matrices (with ones in the main diagonal)
it can be written:
(I+X)^-1 = I - X^1 + X^2 - X^3 + X^4 - ...
where I is the identity matrix and X is the triangular matrix minus
the identity matrix.
(This matrix powers formula for matrix inversion
was discovered together with Gary W. Adamson.)
Applied to table A051731 (http://oeis.org/A051731) we then have
the triangular matrix with the definition:
If n=k then T(n,k)=0, elseif k divides n then T(n,k)=1, else T(n,k)=0.
The first few terms of our matrix X is then:
0,
1,0,
1,0,0,
1,1,0,0,
1,0,0,0,0,
1,1,1,0,0,0,
1,0,0,0,0,0,0,
1,1,0,1,0,0,0,0,
1,0,1,0,0,0,0,0,0,
1,1,0,0,1,0,0,0,0,0
raised to the power 2 we then get X^2:
0,
0,0,
0,0,0,
1,0,0,0,
0,0,0,0,0,
2,0,0,0,0,0,
0,0,0,0,0,0,0,
2,1,0,0,0,0,0,0,
1,0,0,0,0,0,0,0,0,
2,0,0,0,0,0,0,0,0,0
The first column, k=1: X^2(n,1), equals row sums of k>1: X^1(n,k).
And the rest of the columns, k>1: X^2(n,k), equal the first column,
k=1: X^2(n,1),
interleaved with k-1 zeros.
The first column, k=1: X^3(n,1), equals row sums of k>1: X^2(n,k).
And the rest of the columns, k>1: X^3(n,k), equal the first column,
k=1: X^3(n,1),
interleaved with k-1 zeros.
The first column, k=1: X^4(n,1), equals row sums of k>1: X^3(n,k).
And the rest of the columns, k>1: X^4(n,k), equal the first column,
k=1: X^4(n,1),
interleaved with k-1 zeros.
And so on... We notice the pattern.
This allows us to represent the o.g.f for the Moebius function:
mu(1)*x^1 + mu(2)*x^2 + mu(3)*x^3 + ...
=
+ [x^1]
- [Sum from n=1 to n=1 of: x^(2*n)/(1-x^(1*n))]
+ [Sum from n=2 to infinity of: x^(2*n)/(1-x^(1*n))]
- [(Sum from n=2 of to infinity of: x^(4*n)/(1-x^(2*n)))
+(Sum from n=2 of to infinity of: x^(6*n)/(1-x^(3*n)))
+(Sum from n=2 of to infinity of: x^(8*n)/(1-x^(4*n))
+ ... + (Sum from n=2 of to infinity of: x^(2*k*n)/(1-x^(k*n)))]
+ [more sums]
and so on...
I am not entirely sure if "k" is correctly used in the formula.
Hopefully this can be understood despite my lack of articulateness.
Help with continuing the formula and any feedback is appreciated.
Best regards,
DI Mats Granvik
Tel: +358 50 570 8324
CV: http://matsgranvik.wordpress.com/
More information about the SeqFan
mailing list