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.
http://www.math.niu.edu/~rusin/known-math/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
==============================================================================