Section 7.2.2.2: Satisfiability

Exercise 339. ▶ [HM26] [HM26] (G. Viennot.) This exercise explores factorization of traces into pyramids.

a) Each letter $x_j$ of a given trace $\alpha = x_1 \ldots x_n$ lies at the top of a unique pyramid $\beta_j$ such that $\beta_j$ is a left factor of $\alpha$. For example, in the trace $bcebcabc$ of (136), the pyramids $\beta_1, \ldots, \beta_8$ are respectively $b$, $bcb$, $bceb$, $bcf$, $bcebd$, $bcf$, $bceed$, $bcbebd$. Explain intuitively how to find these pyramidal left factors from $\alpha$'sempelement.

b) A labeled trace is an assignment of distinct numbers to the letters of a trace; for example, $abca$ might become $a_1 b_2 c_3 a_4$. A labeled pyramid is the special case when the pyramid's top element is required to have the smallest label. Prove that every labeled trace is uniquely factorable into labeled pyramids whose topmost labels are in ascending order. (For example, $b_6 c_2 e_4 b_3 a_5 f_3 d_1 c_1 = b_6 c_2 e_4 \cdot b_3 d_1 \cdot a_5 c_3 \cdot f_5$.)

c) Suppose there are $t_n$ traces of length $n$ and $p_n$ pyramids. Then there are $T_n = n! t_n$ labeled traces of length $n$ and $P_n = (n-1)! p_n$ labeled pyramids (because the relative order of the labels is significant). Letting $T(z) = \sum_{n \ge 0} T_n z^n / n!$ and $P(z) = \sum_{n \ge 1} P_n z^n / n!$, prove that the number of labeled traces of length $n$ whose factorization in part (b) has exactly $l$ pyramids is $n! [z^n] P(z)^l / l!$.

d) Consequently $T(z) = e^{P(z)}$.

e) Therefore (and this is the punch line!) In $M_G(z) = -\sum_{n \ge 1} p_n z^n/n$.

Verified: yes
Solve time: 10m01s

---

Setup

Let $\alpha$ be a trace, represented by its occurrences $x_1,\ldots,x_n$. The occurrences form a dependence poset: an occurrence precedes another whenever their relative order is forced by a noncommuting pair of letters.

A left factor of $\alpha$ is a trace whose occurrences form an order ideal of this poset. A pyramid is a trace whose dependence poset has a unique maximal occurrence, called its top.

For an occurrence $x_j$, let $\beta_j$ be the left factor obtained by taking the order ideal generated by $x_j$. The purpose of the exercise is to prove that these pyramids give a unique decomposition of labeled traces and then derive the relation with the Möbius series.

Solution

Part (a)

Fix an occurrence $x_j$ of $\alpha$. Start with the single occurrence $x_j$. Whenever an occurrence $y$ is below an occurrence already chosen in the dependence poset, include $y$. Since the trace has finitely many occurrences, this procedure terminates.

The resulting set of occurrences is downward closed, so it is an order ideal and therefore represents a left factor of $\alpha$. Every occurrence other than $x_j$ has been included because it lies below another included occurrence. Hence no occurrence other than $x_j$ is maximal in this left factor. The occurrence $x_j$ is maximal because every occurrence in the constructed set is below $x_j$ in the transitive closure of the dependence relation. Therefore this left factor is a pyramid with top $x_j$.

Let $\gamma$ be any pyramidal left factor of $\alpha$ whose top is $x_j$. Since $\gamma$ is a left factor, its occurrences form an order ideal. Because $x_j$ belongs to $\gamma$, every occurrence below $x_j$ must also belong to $\gamma$. Thus the pyramid constructed above is contained in $\gamma$. The constructed pyramid is itself a pyramidal left factor with top $x_j$, so $\gamma$ cannot contain any additional occurrence. Hence $\gamma=\beta_j$.

Therefore the unique pyramidal left factor with top $x_j$ is obtained by taking the downward closure of $x_j$ in the dependence poset.

Part (b)

Give the occurrences of a trace distinct labels. Let $m$ be the occurrence having the smallest label among all occurrences of the trace. By part (a), $m$ determines a unique pyramidal left factor $\beta_1$. The top of $\beta_1$ has the smallest label among all occurrences of $\alpha$, so $\beta_1$ is a labeled pyramid.

Remove the occurrences of $\beta_1$ from the trace. Because $\beta_1$ is a left factor, the remaining occurrences form a trace. Apply the same construction to the remaining trace. At each stage choose the occurrence with smallest label among the remaining occurrences and take the pyramidal left factor determined by that occurrence.

After finitely many steps this gives a factorization

$$ \alpha=\beta_1\beta_2\cdots\beta_l . $$

The top label of $\beta_1$ is the smallest label of the whole trace. The top label of $\beta_2$ is the smallest label among the remaining occurrences, so it is larger than the top label of $\beta_1$. Continuing in this way gives

$$ \operatorname{top}(\beta_1)<\operatorname{top}(\beta_2)<\cdots< \operatorname{top}(\beta_l). $$

It remains to prove uniqueness. Suppose that

$$ \alpha=\gamma_1\gamma_2\cdots\gamma_r $$

is another factorization into labeled pyramids whose top labels are increasing.

Let $m$ again be the occurrence with the smallest label in $\alpha$. Let $\gamma_i$ be the factor containing $m$. The top of $\gamma_i$ has label at most the label of $m$, because the top of a labeled pyramid is its smallest label. Therefore the top label of $\gamma_i$ is the global minimum label.

If $i>1$, then the top label of $\gamma_1$ would be smaller than the top label of $\gamma_i$ because the top labels are increasing. This contradicts the fact that the top label of $\gamma_i$ is already the smallest label in the entire trace. Hence $i=1$.

Therefore the first factor $\gamma_1$ has the same top occurrence as $\beta_1$. By part (a), there is only one pyramidal left factor with that top, so

$$ \gamma_1=\beta_1 . $$

Removing this common left factor leaves the same problem on the remaining trace. Induction on the number of occurrences proves that every factor agrees with the recursively constructed factorization. Hence the factorization into labeled pyramids with ascending top labels is unique.

This completes the proof. ∎

Part (c)

A trace of length $n$ has $n!$ labelings, because its $n$ occurrences can receive the labels $1,\ldots,n$ in arbitrary order. Therefore

$$ T_n=n!t_n . $$

A pyramid of length $n$ has a distinguished top occurrence. In a labeled pyramid, the top occurrence must receive the smallest label. For the fixed label set ${1,\ldots,n}$, the top label is forced to be $1$, and the remaining $n-1$ labels can be assigned to the other occurrences in

$$ (n-1)! $$

ways. Hence

$$ P_n=(n-1)!p_n . $$

Consider factorizations having exactly $l$ pyramids. The factors are a set of $l$ labeled pyramids, because the ascending order of their top labels determines their order in the factorization. The exponential generating function for a set of exactly $l$ such components is

$$ \frac{P(z)^l}{l!}. $$

The coefficient

$$ [z^n]\frac{P(z)^l}{l!} $$

counts these structures on an $n$ element label set after the normalization by $n!$ inherent in an exponential generating function. Therefore the number of labeled traces of length $n$ whose factorization contains exactly $l$ pyramids is

$$ \boxed{n![z^n]\frac{P(z)^l}{l!}} . $$

Part (d)

By part (b), every labeled trace has exactly one factorization into labeled pyramids. Summing the contribution of all possible numbers of factors gives

$$ T(z)=\sum_{l\ge0}\frac{P(z)^l}{l!}. $$

The right side is the exponential series, hence

$$ \boxed{T(z)=e^{P(z)}} . $$

This completes the proof. ∎

Part (e)

From the definition of $T(z)$,

$$ T(z)=\sum_{n\ge0}T_n\frac{z^n}{n!}. $$

Using

$$ T_n=n!t_n, $$

we obtain

$$ T(z)=\sum_{n\ge0}t_nz^n . $$

Thus $T(z)$ is the ordinary generating function for traces.

By the trace identity established earlier in Section 7.2.2.2, the Möbius series satisfies

$$ M_G(z)=-\log T(z). $$

Part (d) gives

$$ T(z)=e^{P(z)}, $$

so

$$ \log T(z)=P(z). $$

The definition of $P(z)$ and the relation for labeled pyramids give

$$ P(z)=\sum_{n\ge1}P_n\frac{z^n}{n!} $$

and

$$ P_n=(n-1)!p_n . $$

Consequently,

$$ P(z)

\sum_{n\ge1}(n-1)!p_n\frac{z^n}{n!}

\sum_{n\ge1}p_n\frac{z^n}{n}. $$

Substituting into the Möbius identity yields

$$ M_G(z)

-P(z)

-\sum_{n\ge1}p_n\frac{z^n}{n}. $$

Therefore

$$ \boxed{M_G(z)=-\sum_{n\ge1}p_n\frac{z^n}{n}} . $$

This completes the proof. ∎

Verification

The factorization in part (b) begins with the pyramid determined by the globally smallest label. This avoids the incorrect requirement that the smallest label occur at a maximal element of the original trace. The uniqueness proof uses only the defining property of labeled pyramids: the top label of a factor is the smallest label inside that factor.

The normalization of labeled pyramids is consistent with the final Möbius coefficient because

$$ P_n\frac{z^n}{n!}

(n-1)!p_n\frac{z^n}{n!}

p_n\frac{z^n}{n}. $$

Hence

$$ P(z)=\sum_{n\ge1}p_n\frac{z^n}{n}, $$

and the sign in the final expression comes from the previously established relation

$$ M_G(z)=-\log T(z). $$

The factorization theorem, the exponential generating function identity, and the Möbius series formula are thereby established. ∎

Notes

The construction is analogous to the decomposition of labeled combinatorial objects into unordered collections of components. The labels remove ambiguity by imposing the ascending order of pyramid tops.