From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: What is the Mu function?
Date: 7 Feb 1996 11:31:48 GMT
In article ,
Gerry Myerson wrote:
>In article <4f6a1f$gu8@ixnews4.ix.netcom.com>, khill1@ix.netcom.com (Kelly
>Hill) wrote:
>>
>> I read in an earlier posting a brief definition of a general mu
>> function, one that takes two arguments, but it was based on a more
>> specific one that takes one argument. My question is, what is mu(x)?
>
>Since I don't know what the earlier posting was about, I'll have to
>guess that we're talking about the Moebius function from Number Theory.
>This is defined, for positive integers x, as follows;
>
>If there is a prime p such that x is a multiple of p-squared,
>then mu(x) = 0.
>Otherwise, mu(x) = 1 if the number of distinct primes dividing x is even,
>mu(x) = -1 if the number of distinct primes dividing x is odd.
I don't recall the previous post either. My only guess for the 2-variable
mu would be a generalization of the Moebius function.
If L is a partially ordered set such that every element has only finitely
many predecessors (a "lattice", e.g. the lattice of subgroups of a
finite group), one can define a function mu(x,y) of pairs of
elements in L so that
for any f: L --> Z
if g:L --> Z is defined by g(x) = Sum_{y <= x} f(y)
then for any y in L, f(y) = Sum_{x <= y} g(x) mu(x,y).
(Naturally the same mu can be used for maps into any abelian group.)
This mu is the "Moebius Inversion Function" of L. When L is the
set of positive integers with "x < y" meaning "x divides y", then
mu(x,y)=mu(y/x), where this latter mu is as Myerson just described.
When L is the lattice of subgroups of a finite p-group, I believe
mu(x,y)=0 unless x is normal in y and y/x is elementary abelian;
if its rank is r, then mu(x,y) is (-1)^r p^(r-1) (?).
dave
==============================================================================
From: Benjamin.J.Tilly@dartmouth.edu (Benjamin J. Tilly)
Newsgroups: sci.math
Subject: Re: What is the Mu function?
Date: 9 Feb 1996 15:55:30 GMT
In article
gerry@mpce.mq.edu.au (Gerry Myerson) writes:
> In article <4f6a1f$gu8@ixnews4.ix.netcom.com>, khill1@ix.netcom.com (Kelly
> Hill) wrote:
> >
> > I read in an earlier posting a brief definition of a general mu
> > function, one that takes two arguments, but it was based on a more
> > specific one that takes one argument. My question is, what is mu(x)?
>
> Since I don't know what the earlier posting was about, I'll have to
> guess that we're talking about the Moebius function from Number Theory.
> This is defined, for positive integers x, as follows;
>
> If there is a prime p such that x is a multiple of p-squared,
> then mu(x) = 0.
> Otherwise, mu(x) = 1 if the number of distinct primes dividing x is even,
> mu(x) = -1 if the number of distinct primes dividing x is odd.
>
> E.g., mu(4) = 0, mu(5) = -1, mu(6) = 1.
This is, incidentally, a special case of the Moebius function from
combinatorics.
The idea is that you know a function F(x) on a partially ordered set
which is for each x the sum over all points on that lattice >= x the
value of f(x). Suppose that you want to figure out f(x). Well, the
answer turns out to be that you get
Sum F(y) mu(y,x)
y>=x
for some function mu on pairs of points in the partially ordered set.
(Think of inclusion-exclusion, which is just this inversion formula for
subsets of a set.)
Now for some nice partially ordered sets mu(x,y) depends only upon the
relationship between where x and y are in the lattice in a way where it
can be described in terms of one function.
Two important examples are the set of subsets of a set ordered under
inclusion (where mu depends only on how many elements are in the larger
set that are not in the smaller one) and the set of positive integers
ordered by divisibility. (In other words 3 is incomparible with 2, but
6 is larger than either of them.) In the latter case the combinatorial
Mobius function becomes
mu(y,x) = mu(y/x)
where the second Moebius function is the number-theoretical one that
you gave.
You can find more about this in many references, including chapter 3 of
Enumerative Combinatorics by Richard Stanley, and I think that Ken
Bogart's introductory combinatorics books may say something about this.
Ben Tilly