Discrete Faà di Bruno via Möbius Inversion

We approach discrete and differential Faà di Bruno formulas from a Möbius inversion angle.
On the Boolean cube, Newton's discrete Taylor formula and the definition of iterated forward differences form a zeta--Möbius dual pair,
and composing two Taylor expansions and inverting once yields a closed discrete
Faà di Bruno formula at a fixed basepoint: for arbitrary maps $f, g$ between abelian groups,

$$ \Delta(f \circ g;,x;,u_1,\dots,u_k) = \sum_{H \in \mathrm{Cov}(k)} \Delta(f;,g(x);,(\Delta(g;x;u_T))_{T\in H}), $$

where $\mathrm{Cov}(k)$ denotes the coverings of $[k]$ by nonempty subsets.
Grouping repeated directions gives binomial versions on multi-index grids, and iterating gives formulas for $m$-fold composites,
with integer covering coefficients governed by explicit cross and level recursions, a discrete analogue of the Constantine--Savits formulas.

The relationship between coverings and partitions appearing in classical Faà di Bruno formulas, is exhibited in an algebraic setting.
The discrete formulas are Taylor expansions over the function algebra of the Boolean cube,
$B_k = \mathbf{k}[\delta_1,\dots,\delta_k]/(\delta_i^2-\delta_i)$, whose idempotent generators absorb overlapping products;
in the differential analogue $A_k = \mathbf{k}[\varepsilon_1,\dots,\varepsilon_k]/(\varepsilon_i^2)$,
nilpotent generators annihilate overlaps and only partitions remain.
Both algebras are fibers of the flat deformation $C_k = \mathbf{k}[t][x_1,\dots,x_k]/(x_i^2 - tx_i)$,
over which a single weighted covering formula interpolates:
its coefficients are difference quotients, non-partition coverings carry positive powers of $t$, and evaluation at $t = 0$ yields
the classical partition-indexed Faà di Bruno formula.

We demonstrate how these algebraic identities can be lifted to the analytical setting of $C^n$ maps between Banach spaces,
recovering the multivariate Faà di Bruno formula of Constantine--Savits and extending it to composites of several maps.
Boolean finite differences, binomial grid formulas, infinitesimal Taylor algebras, and Fréchet derivatives thus appear
as four realizations of one Möbius-dual Faà di Bruno formula, connected by a flat family.

Read online