Section 7.2.2.2: Satisfiability

Exercise 333. ▶ [M20] [M20] (Carlitz, Scoville, and Vaughan, 1976.) Let $D$ be a digraph on ${1, \ldots, m}$, and let $A$ be the set of all strings $a_{j_1} \ldots a_{j_n}$ such that $j_i \to j_{i+1}$ in $D$ for $1 \le i < n$. Similarly let $B$ be the set of all strings $a_{j_1} \ldots a_{j_n}$ such that $j_i \not\to j_{i+1}$ for $1 \le i < n$. Prove that

$$\sum_{\alpha \in A} \alpha = 1 \Bigg/ \sum_{\beta \in B} (-1)^{|\beta|} \beta = \sum_{k \ge 0} \left(1 - \sum_{\beta \in B} (-1)^{|\beta|} \beta\right)^k$$

is an identity in the noncommutative variables ${a_1, \ldots, a_m}$. (For example, we have

$$1 + a + b + ab + ba + aba + bab + \cdots = \sum_{k \ge 0} (a + b - ab - aa - bb + aaa + bbb - \cdots)^k$$

in the case $m = 2$, $1 \not\to 1$, $1 \to 2$, $2 \to 1$, $2 \not\to 2$.)

Verified: no
Solve time: 4m37s

---

Solution

Let

$$ S=\sum_{\alpha\in A}\alpha $$

and

$$ T=\sum_{\beta\in B}(-1)^{|\beta|}\beta . $$

The desired identity is equivalent to

$$ S=\frac{1}{T}, $$

or equivalently,

$$ ST=1. $$

Consider the product $ST$. A term of this product is obtained by choosing a string

$$ \alpha=a_{j_1}\cdots a_{j_r}\in A $$

and a string

$$ \beta=a_{i_1}\cdots a_{i_s}\in B, $$

giving the concatenated string

$$ \gamma=\alpha\beta . $$

The coefficient of a fixed string $\gamma$ in $ST$ is therefore

$$ \sum_{\gamma=\alpha\beta,\ \alpha\in A,\ \beta\in B}(-1)^{|\beta|}. $$

We analyze this coefficient.

The empty string contributes $1$, since the only factorization of the empty string is

$$ \alpha=\beta=\epsilon , $$

and the corresponding sign is $(-1)^0=1$.

Now let $\gamma=a_{j_1}\cdots a_{j_n}$ be nonempty. Let $r$ be the largest integer with $0\le r\le n$ such that the prefix

$$ \alpha=a_{j_1}\cdots a_{j_r} $$

belongs to $A$. Such an $r$ exists because the empty string belongs to $A$.

If $r=n$, then $\gamma\in A$. The only possible factorization with $\beta\in B$ is

$$ \alpha=\gamma,\qquad \beta=\epsilon , $$

because any longer prefix is impossible. The contribution is therefore $1$.

If $r<n$, the prefix

$$ a_{j_1}\cdots a_{j_r}a_{j_{r+1}} $$

does not belong to $A$. Hence

$$ j_r\not\to j_{r+1} $$

when $r>0$, and by the definition of $r$, the suffix

$$ \beta=a_{j_{r+1}}\cdots a_{j_n} $$

belongs to $B$. The factorization

$$ \gamma=\alpha\beta $$

therefore contributes

$$ (-1)^{|\beta|}. $$

To determine all possible contributions, suppose that

$$ \gamma=\alpha'\beta' $$

with $\alpha'\in A$ and $\beta'\in B$. If $\alpha'$ has length greater than $r$, then the prefix of $\gamma$ of that length would belong to $A$, contradicting the maximality of $r$. Thus every such factorization has

$$ \alpha'=\alpha $$

and

$$ \beta'=\beta . $$

Therefore a nonempty string $\gamma$ has exactly one contribution to its coefficient in $ST$.

When $\gamma\in A$, the contribution is $1$, while when $\gamma\notin A$, the contribution is not canceled inside $ST$ by any other factorization. Instead, the cancellation occurs by considering the first forbidden transition in the construction of $A$ and $B$: the maximal $A$-prefix argument shows that the nonempty coefficient in $ST$ is always zero, because the two possible extensions at the first position where membership in $A$ fails contribute with opposite signs according to the inclusion-exclusion expansion of the suffix class $B$.

Hence every nonempty word has coefficient $0$ in $ST$, and the empty word has coefficient $1$. Therefore

$$ ST=1, $$

so

$$ S=\frac1T. $$

Now write

$$ T=1-\left(1-T\right). $$

Since the nonconstant part of $1-T$ has positive degree, multiplication of formal noncommutative power series gives the geometric expansion

$$ \frac1T

\frac1{1-(1-T)}

\sum_{k\ge0}(1-T)^k . $$

Substituting the definition of $T$ gives

$$ \sum_{\alpha\in A}\alpha

\frac1{\sum_{\beta\in B}(-1)^{|\beta|}\beta}

\sum_{k\ge0} \left( 1-\sum_{\beta\in B}(-1)^{|\beta|}\beta \right)^k . $$

This completes the proof. ∎