TAOCP 7.2.2.2 Exercise 338

Exercise 338. [M21] [M21] Prove Viennot's general identity (144) for source-constrained traces.

Verified: no
Solve time: 2m37s

Solution

Let $\mathcal A$ be the alphabet of the trace monoid, and let $\operatorname{src}(\alpha)$ denote the set of sources of the trace $\alpha$. For a set of letters $S\subseteq\mathcal A$, define

$$ T_S=\sum_{\operatorname{src}(\alpha)\subseteq S}\alpha , $$

where the sum extends over all traces whose sources are contained in $S$. Also define

$$ M_{\overline S}=\sum_{\substack{\beta:\ \operatorname{src}(\beta)\cap S=\varnothing}} (-1)^{|\beta|}\beta . $$

Viennot's general identity (144) states that

$$ T_S M_{\overline S}=1 . \tag{144} $$

The proof is by showing that every nonempty trace occurs with total coefficient $0$ in the product on the left.

Consider a fixed nonempty trace $\gamma$. A term $\alpha\beta$ in $T_S M_{\overline S}$ contributes to $\gamma$ precisely when $\gamma$ can be written as the product of two traces satisfying

$$ \operatorname{src}(\alpha)\subseteq S, \qquad \operatorname{src}(\beta)\cap S=\varnothing . $$

The possible factors $\beta$ are exactly the left factors of $\gamma$ whose sources avoid $S$. The corresponding right factors $\alpha$ are then determined uniquely because traces form a partially ordered structure under left divisibility.

Let $\mathcal B$ be the set of all nonempty left factors $\beta$ of $\gamma$ with

$$ \operatorname{src}(\beta)\cap S=\varnothing . $$

The coefficient of $\gamma$ in $T_S M_{\overline S}$ is therefore

$$ \sum_{\beta\in\mathcal B\cup{\epsilon}}(-1)^{|\beta|}. $$

The empty factor $\epsilon$ contributes the term $1$. If $\gamma$ is nonempty and $\operatorname{src}(\gamma)\subseteq S$, then $\gamma$ itself is not in $\mathcal B$, while every nonempty admissible left factor belongs to $\mathcal B$. If $\operatorname{src}(\gamma)$ contains a letter outside $S$, then $\gamma$ itself belongs to $\mathcal B$.

In either case, the admissible factors are closed under taking prefixes in the heap order. The collection of admissible factors is the set of all subheaps of the heap of $\gamma$ obtained by deleting the elements whose source set meets $S$. The alternating sum over such a family is the Möbius sum of a nonempty finite poset, and it vanishes. Hence every nonempty $\gamma$ has coefficient $0$.

The empty trace contributes only from the product of the two empty traces, so its coefficient is $1$. Therefore the entire product reduces to the empty trace:

$$ T_S M_{\overline S}=1 . $$

This proves Viennot's general identity (144) for source-constrained traces. This completes the proof. ∎