\documentclass[12pt]{amsbook} \usepackage{palatino, euler, amsmath, amssymb, comment} \usepackage{nils} \usepackage[all]{xy} \begin{document}
\chapter[M\"obius inversion and PIE are discrete derivatives]{M\"obius inversion and the Principle of Inclusion-Exclusion (PIE) are discrete derivatives}
M\"obius inversion and the Principle of Inclusion-Exclusion (PIE) are discrete derivatives
on particular posets, analogs of (backward) discrete difference. It's just order theory,
and it algebraicizes as ``incidence algebras'', analogs of group algebras.
The picture is:
\begin{itemize}
\item discrete difference = line\\
Poset:\\
\xymatrix{ 0\ar[r] & 1\ar[r] & 2\ar[r] & \cdots}\\
Difference kernel\\
(what you pair a function against to differentiate):\\
\xymatrix{ 0 & -1 & 1}
\item PIE = hypercube\\
\begin{tabular}{ccc}
Poset & & Difference kernel\\
\xymatrix{ \set{a}\ar[r] & \set{a,b}\\
\set{}\ar[u]\ar[r] & \set{b}\ar[u] }
& \ \hspace{2 cm}\ &
\xymatrix{-1 & 1\\
1 & -1}
\end{tabular}
\item M\"obius inversion = hyperbox\\
(several steps in each direction), and is a combo of the above\\
\begin{tabular}{ccc}
Poset & & Difference kernel\\
\xymatrix{ 3\ar[r] & 6\ar[r] & 12\\
1\ar[u]\ar[r] & 2\ar[u]\ar[r] & 4\ar[u] }
& \ \hspace{2 cm}\ &
\xymatrix{ 0 & -1 & 1\\
0 & 1 & -1}
\end{tabular}
\end{itemize}
M\"obius inversion seems mysterious at first because it is presented as a
(Dirichlet!) convolution operator (likely the first convolution a novice reader has seen),
and ``square-free'' sounds like it has subtle number-theoretic meaning
(it doesn't: it's just the order picture above).
We review each case, emphasizing the connections.
\section{Discrete difference}
Given a sequence $a_0,a_1,\dotsc$, one can integrate it, getting the sequence of partial sums:
$$(\Sigma a)_n := \sum_{i\leq n} a_i$$
Inverse to this (corresponding to differentiation) is successive differences:
$$(\Delta b)_n := b_n - b_{n-1}$$
(and $(\Delta b)_0 = b_0$).
These two operations are inverse, which is the discrete fundamental theorem of calculus:
$\Delta\sum$ is the difference of partial sums, while $\sum\Delta$ is the telescoping sum.
\section{PIE}
fixme: The classic PIE is subtle from this POV, and I don't really understand it; see \TeX~source for details.
\begin{comment}
Classic PIE says $$\abs{\bigcup A_\alpha =
\sum (-1)^{k+1} \abs{\bigcap_{I=(\alpha_1<\dots<\alpha_k)} A_I}}$$
As the $k+1$ indicates, it's better stated all on one side:
$$\sum (-1)^k \abs{\bigcap_{\alpha_1<\dots<\alpha_k} A_{\alpha_i}}} = 0$$
...where the empty intersection is the union of all of them.
As the double indexing indicates, there's a function underlying this:
You have a map $\set{\alpha} \to \cP(X)$,
and thus get a map of algebras $A\from \cP(\set{\alpha}) \to \cP(X)$,
sending a set of indices to the appropriate intersection.
(so $I \subset \set{\alpha} \mapsto \bigcap_{\alpha \in I} A_\alpha$)
Now consider the function $\abs{A_I}$ on $\cP(\set{\alpha})$:
the PIE says that this has derivative zero!
Actually, not quite: the derivative is the function that's 1 on
the one element sets (careful of the orientation-reversing-ness;
should perhaps says co-one element sets)
...hence the integral is the ``count elements of a subset'' function,
as stated, so I somewhat understand it.
\end{comment}
Given a function on a power set $f\from \cP(X) \to R$, one can integrate it:
$$\left({\textstyle \int} f\right)(A) := \sum_{B \subset A} f(B)$$
Inverse to this is the
XXXXXXXXXXXXX
We illustrate with the classic application of the PIE as counting derangements
(fixed-point-free permutations).
The idea is that ``permutations with fixed set $A$'' is the derivative
of ``permutations that stabilize $A$ (and possibly more besides)'', and the latter
is easy to count (it's $(n-k)!$, where $k=\abs{A}$); note that the derivative
is in the \emph{opposite} of the usual order: $A \leq B$ iff $A \supset B$.
Formally, a permutation $\sigma$ stabilizes $A$ iff the fixed set of $\sigma$ \emph{contains} $A$: $A \subset \Fix_\sigma$.
The permutations that fix $A$ are the identity on $A$, and arbitrary on $X\setminus A$,
so they are exactly $S_{X\setminus A}$, and there are $\abs{X\setminus A}!=(n-k)!$ of them.
Given $A \subset X$,
$\Fix A$ are all disjoint
$\Stab A = \coprod_{B \supset A} \Fix B$
to count derangements which fix particular subsets:
let $F_A$ be the set of permutations that fix $A \subset X$,
look at $\cP(X)$, and
OH!
The point is that you have two functions:
everything fixes $\emptyset$,
but we want to count those that fix *exactly* the empty set
Incidentally, how many permutations have fixed set $A$ for $A\neq \emptyset$?
That's just a derangement of $X\setminus A$, so it's $[(n-k)!/e]$.
\section{Incidence algebras}
The notion of an incidence algebra algebraicizes this:
define a product on the module of ``functions on (intervals in) a poset''
via convolution, and then the differentiation (and integration) operators
become convolution operators.
Formally:
\footnote{Why $a\leq b$? You might consider $a < b$ (strictly less),
but this isn't as good, as it's not reversible.
(It does work for functions on the naturals though, where you can use forward differences
instead of backward differences, but this is unusual.)
For instance, you never capture the value of top elements,
and bottom elements are indistinguishable from the empty set:
if you ``integrate'' (via $a < b$) a function on the poset
with a single element, you get zero.}
Most familiar interesting application of PIE is counting derangements (fixed-point-free permutations).
BTW, why is M\"obius inversion interesting?
Combinatorially it's cute but not deep.
It's interesting b/c summation (of arithmetic functions) is interesting
(related to totient, divisors, zeta function)
%%%%%%%%%%%%%%%%%%%%%%%%%%%
Wiki:
See wiki page on incidence algebras
...and wikify this
%http://en.wikipedia.org/wiki/Incidence_algebra
% Link this from "PIE"
%http://en.wikipedia.org/wiki/Random_permutation_statistics#Number_of_permutations_that_are_derangements
convolution:
The formula
$(f*g)(x) = \int_{yz=x} f(y)g(z)$
...makes sense without any *group* structure,
and you don't even need a complete operation.
(partial magma)
wiki:
- link semigroup algebra / monoid algebra to group ring,
and discuss there
! you can't in general differentiate !
EG, in a group algebra, the group of units is $\set{\pm g}$
(notably, $\zeta$ is not invertible)
Concretely, in $\bZ[\bZ/2]$, $\zeta (1-g) = 0$.
\end{document}