From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Moebius tranform Date: 8 Jun 1998 17:58:44 GMT In article <357BEDBB.2E87@univ-tln.fr>, Langevin Philippe wrote: >What is the Moebius transform of a function from E into >Z when E is an ordered set ? > >what about the basic Properties ? I believe you're thinking of the Mobius Inversion function mu on a partially ordered set. I may be messing up some details, but the defining property is: If f: E -> Z is any function and g: E-> Z is then defined by g(e) = Sum( f(e'), e' < e ) then f may be recovered from g by the formula f(e) = Sum( mu(e',e)*g(e'), e' < e ). (In order for these expressions to make sense we must assume each element of E has only finitely many predecessors.) Thus for example if E = {1, 2, 3, ...} with the usual ordering, mu(e', e) = 1 if e'=e, and =-1 if e'=e-1. If instead this same set E is partially ordered by divisibility (" e' < e " means e' | e ) then mu(e', e) = mu(e/e'), where the second mu is the Moebius function on integers: it's 0 for integers divisible by a proper square, and otherwise is (-1)^d where d is the number of distinct prime divisors of e/e'. I seem to recall that the formula mu(e',e)=mu(e/e') is valid in more general contexts in which " e/e' " makes sense, e.g. if E is the lattice of subgroups of a p-group, ordered by inclusion. (Here mu(e', e) = 0 is e' is not normal in e.) You must be working in the context of ordered sets and lattices; see e.g. index/06-XX.html There's a Moebius transform in complex analysis too, but that's different. (It would be a map from the Riemann sphere to itself given by a fractional linear map.) dave ============================================================================== From: hrubin@stat.purdue.edu (Herman Rubin) Newsgroups: sci.math.research Subject: Re: Moebius Inversion Date: 16 Jun 1998 14:45:34 -0500 In article <35865509.7E42@univ-tln.fr>, Langevin Philippe wrote: >Hey ! >Let m be a positive integer and let E={0,1,...,m-1}, I denote >by <= the usual order on E. >Now let n be a positive integer, E^n is a partially ordered set >with the order | defined by : > x | y iff x_i<=y_i for all i in [1,n] >What does one know about the Moebius function of ( E^n, |) ? >References ? This seems too easy to need references. The definition of the Moebius function is enough, and it is a little easier to see it in generality. In fact, the USUAL Moebius function is a slight generalization of the special form you have indicated. Suppose that we have partially ordered sets A_j, all of which are rooted trees with the root designated as 0, and we consider the weak direct product of the A_j, with only a finite number of the coordinates not 0. Then the Moebius function of the product is just the product of the Moebius functions! As an example, consider the positive integers ordered by divisibility. This is the product over all primes p of the powers (starting from the 0's power) of the primes. For A_p = {p^n: n = 0, 1, ... }, we have the linear ordering Moebius function. Combine these by multiplication to get the usual one. -- This address is for information only. I do not claim that these views are those of the Statistics Department or of Purdue University. Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399 hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558 ============================================================================== From: nikl+sm000079@pchelwig1.mathematik.tu-muenchen.de (Gerhard Niklasch) Newsgroups: sci.math Subject: Re: Moebius tranform Date: 8 Jun 1998 17:36:58 GMT In article <357BEDBB.2E87@univ-tln.fr>, Langevin Philippe writes: |> Hey ! Bonjour. :) |> What is the Moebius transform of a function from E into |> Z when E is an ordered set ? |> |> what about the basic Properties ? You don't really give enough context to be sure what is being meant, but here's one possibility. (I don't know it by the name of `Moebius _transform_', which is usually reserved for fractional linear trans- formations of the completed complex plane -- `Moebius inversion' would be more appropriate.) Assume that E is a partially ordered set such that, for every element x of E, the set down(x) =[def] {y in E : y <= x} is finite. The classical example is the set of positive integers, partially ordered by divisibility. Let A be any abelian group, and f any A-valued function on E. Then the following is well-defined: F[f]: E --> A, F[f](x) = sum_{y<=x} f(y) , the `summatory function' of f. The `Moebius inversion problem' is to retrieve the function f, given the function F. A more or less obvious idea is to write f(x) = sum_{y<=x} c(y,x) F(y) and try to deduce the (integer-valued) coefficients c(y,x), acting on the Z-module A in the natural way, by induction on x >= y for each fixed y. If all goes well, one can find a system of coefficients c(y,x) which doesthe trick for all F and depends on E alone (more precisely, on the structure of the interval of elements z of E which satisfy y <= z <= x, with the induced partial order -- the coefficients do not even depend on A). (Semi-technical note: The group A might be `too small' to nail down the coefficients. However, it is obvious that there exists a group which is `large enough', viz. the free abelian group on the set E, and if we can find a coefficient system which works in this case, then it will work in all cases.) Carrying this out for the standard example gives you the usual Moebius function c(y,x) = mu(x/y) -- this is arguably the most natural way to define this function, followed by a proof that it behaves in the well-known way with respect to prime factorization. (Exercise: if f is a multiplicative arithmetic function, then so is F, and vice versa.) In general, it is clear that c(y,y) has to be +1 for all y (consider functions f which are supported on the singleton x), and (for the same reason) that c(y,x) must be -1 whenever x is an immediate successor of y. One proves uniqueness first, and only afterwards shows that the unique solution is in fact a solution. When E is a simplicial set (each down(x) looks like the Boolean algebra of subsets of a finite set, ordered by set inclusion), you recover the classical `inclusion-exclusion' counting principle of combinatorics. I don't remember whether any further conditions need to be imposed on E, and am too lazy to check the details -- you'll discover them when you work out the inductive argument. :^) Enjoy, Gerhard -- * Gerhard Niklasch * spam totally unwelcome * http://hasse.mathematik.tu-muenchen.de/~nikl/ ******* all browsers welcome * This .signature now fits into 3 lines and 77 columns * newsreaders welcome ==============================================================================