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