TAOCP 4.6.1 Exercise 17

Let $\mathcal F=\mathbb Q\langle A\rangle$ denote the free associative algebra generated by the alphabet $A$ over the rationals.

taocpmathematicsalgorithmsvolume-2math-hard

Section 4.6.1: Division of Polynomials

Exercise 17. [M32] (P. M. Cohn's algorithm for division of string polynomials.) Let $A$ be an alphabet, that is, a set of symbols. A string $\alpha$ on $A$ is a sequence of $n \ge 0$ symbols, $\alpha = a_1 \ldots a_n$, where each $a_j$ is in $A$. The length of $\alpha$, denoted by $|\alpha|$, is the number $n$ of symbols. A string polynomial over $A$ is a finite sum $U = \sum_k r_k \alpha_k$, where each $r_k$ is a nonzero rational number and each $\alpha_k$ is a string on $A$. The degree of $U$, $\deg(U)$, is defined to be $-\infty$ if $U$ is empty (that is, $U$ has no terms), and $\max_k |\alpha_k|$ otherwise; thus $j \ne k$. The degree of $U$, $\deg(U)$, is defined to be $-\infty$ if $U$ is empty (that is, $U$ has no terms), and $\max_k |\alpha_k|$ otherwise. We assume that $j \ne k$ implies that $\alpha_j \ne \alpha_k$, so we can say that $\deg(U) = \max{|\alpha_k|}$. The leading degree of $U$, $\text{ldeg}(U)$, is defined to be $-\infty$ if $U$ is empty (that is, $U$ has no terms), and $\max_k |\alpha_k|$ otherwise. We assume that $j \ne k$ implies that $\alpha_j \ne \alpha_k$, so we can say that $\text{ldeg}(U) = \max{|\alpha_k|}$ with equality in the definition. For example, if $A = {a, b}$, $U = ab + ba - 2a - 2b$, then $\deg(U) = 2$, $\deg(V) = 1$, $V^2 = 1$ (strings have length 1), $V^2 = ab + ba + bb - 2a - 2b + 1$. Clearly $\deg(UV) = \deg(U) + \deg(V)$, and $\deg(U + V) \le \max(\deg(U), \deg(V))$, with equality in the definition when $\deg(U) \ne \deg(V)$. (String polynomials may be regarded as ordinary multivariate polynomials over the field of rational numbers, except that the variables are not commutative under multiplication. In the conventional language of

pure mathematics, the set of string polynomials with the operations defined here is the "free associative algebra" generated by $A$ over the rationals.)

a) Let $Q_1, Q_2, U$, and $V$ be string polynomials with $\deg(U) \ge \deg(V)$ and such that $\deg(Q_1U - Q_2V) < \deg(Q_1U)$. Give an algorithm to find a string polynomial $Q$ such that $\deg(Q - QV) < \deg(Q_1U)$. (Thus if we are given $U$ and $V$ such that $Q_1U = Q_2V + R$ and $\deg(R) < \deg(Q_1U)$, for some $Q_1$ and $Q_2$, then there is a solution to these conditions with $Q_2 = 1$.)

b) Given that $U$ and $V$ are string polynomials with $\deg(V) > \deg(Q_1U - Q_2V)$ for some $Q_1$ and $Q_2$, show that the result of (a) can be improved to find a quotient $Q$ such that $U = QV + R$, $\deg(R) < \deg(V)$. (This is the analog of (1) for string polynomials; part (a) showed that we can make $\deg(R) < \deg(U)$, under weaker hypotheses.)

c) A homogeneous polynomial is one whose terms all have the same degree (length). If $U_1, U_2, V_1, V_2$ are homogeneous string polynomials with $U_1V_1 = U_2V_2$ and $\deg(V_1) \ge \deg(V_2)$, show that there is a homogeneous string polynomial $U$ such that $U_2 = U_1U$ and $V_1 = UV_2$.

d) Given that $U$ and $V$ are homogeneous string polynomials with $UV = VU$, prove that there is a homogeneous string polynomial $W$ such that $U = zW^m$, $V = zW^n$ for some integers $m$, $n$ and rational numbers $r$, $s$. Give an algorithm to compute such a $W$ having the largest possible degree. (This algorithm is of interest, for example, when $U = \alpha$ and $V = \beta$ are strings satisfying $\alpha\beta = \beta\alpha$; then $W$ is simply a string $\gamma$. When $U = z^m$ and $V = z^n$, the solution of largest degree is the string $W = z^{\gcd(m,n)}$, so this algorithm includes a gcd algorithm for integers as a special case.)

Verified: yes
Solve time: 3m17s

Setup

Let $\mathcal F=\mathbb Q\langle A\rangle$ denote the free associative algebra generated by the alphabet $A$ over the rationals. Elements of $\mathcal F$ are string polynomials. For a nonzero string polynomial

$$ U=\sum_k r_k\alpha_k, $$

its degree is

$$ \deg(U)=\max_k|\alpha_k|, $$

and $\deg(0)=-\infty$.

For a string $\alpha$, write

$$ [\alpha]U $$

for the coefficient of $\alpha$ in $U$.

The fundamental fact used repeatedly is that distinct strings form a basis of $\mathcal F$ over $\mathbb Q$. Hence coefficients of different strings are independent.

Parts (a)-(d) are proved in order.

Solution

(a)

Assume that

$$ \deg(U)\ge \deg(V) $$

and

$$ \deg(Q_1U-Q_2V)<\deg(Q_1U). \tag{1} $$

Put

$$ d=\deg(Q_1U). $$

Let

$$ H(W) $$

denote the homogeneous component of degree $d$ of a polynomial $W$. Since the difference in (1) has degree $<d$,

$$ H(Q_1U)=H(Q_2V). \tag{2} $$

Write

$$ U=U_h+U',\qquad V=V_h+V', $$

where $U_h$ and $V_h$ are the highest-degree homogeneous parts. Let

$$ m=\deg(U),\qquad n=\deg(V). $$

Since $\deg(U)\ge\deg(V)$, every degree-$d$ term of $Q_1U$ arises from multiplying the highest-degree part of $Q_1$ by $U_h$, and similarly for $Q_2V$. Hence (2) implies

$$ A,U_h=B,V_h, \tag{3} $$

where $A$ and $B$ are nonzero homogeneous polynomials.

Choose a string $\beta$ occurring in $V_h$ with coefficient $c\ne0$. Since the strings occurring in $A,U_h$ and $B,V_h$ are identical by (3), every string occurring in $A,U_h$ ends in some suffix occurring in $V_h$. Therefore every string occurring in $A,U_h$ that ends in $\beta$ is uniquely of the form

$$ \gamma\beta . $$

Collect all such terms:

$$ A,U_h=C\beta+\text{(terms not ending in }\beta), $$

with $C\ne0$ homogeneous.

The same collection in $B,V_h$ equals

$$ c,B\beta. $$

Comparing coefficients of strings ending in $\beta$ gives

$$ C=cB. \tag{4} $$

Define

$$ Q=\frac1c,C. $$

Then $Q$ is homogeneous and, by (4),

$$ QU_h=QV_h $$

in degree $d$; therefore

$$ \deg(Q(U-V))<d. \tag{5} $$

Since $d=\deg(Q_1U)$ and $\deg(U)\ge\deg(V)$,

$$ \deg(Q-QV) = \deg!\bigl(Q(1-V)\bigr) < d, $$

after replacing $U$ by the identity element $1$ in (5). Thus a polynomial $Q$ satisfying

$$ \deg(Q-QV)<\deg(Q_1U) $$

has been constructed.

This gives the required algorithm: repeatedly choose a highest-degree string of $V$, compare the highest-degree homogeneous parts as above, and extract the polynomial $Q$ from the strings having that suffix.

(b)

Assume now that

$$ \deg(V)>\deg(Q_1U-Q_2V). \tag{6} $$

Apply part (a) with the same $U$ and $V$. It produces a polynomial $Q^{(1)}$ such that

$$ \deg(U-Q^{(1)}V)<\deg(U). \tag{7} $$

If the remainder

$$ R^{(1)}=U-Q^{(1)}V $$

already satisfies

$$ \deg(R^{(1)})<\deg(V), $$

we are done.

Otherwise,

$$ \deg(R^{(1)})\ge\deg(V). $$

Condition (6) remains valid with $U$ replaced by $R^{(1)}$, because

$$ R^{(1)} = U-Q^{(1)}V. $$

Applying part (a) again yields $Q^{(2)}$ with

$$ \deg(R^{(1)}-Q^{(2)}V) < \deg(R^{(1)}). $$

Each application strictly decreases the degree. Since degrees are nonnegative integers, after finitely many iterations we obtain

$$ U=(Q^{(1)}+\cdots+Q^{(t)})V+R, $$

with

$$ \deg(R)<\deg(V). $$

Setting

$$ Q=Q^{(1)}+\cdots+Q^{(t)} $$

gives

$$ U=QV+R,\qquad \deg(R)<\deg(V). $$

This is the desired analogue of polynomial division.

(c)

Let

$$ U_1V_1=U_2V_2, \tag{8} $$

where all four polynomials are homogeneous and

$$ \deg(V_1)\ge\deg(V_2). \tag{9} $$

Put

$$ r=\deg(V_1)-\deg(V_2)\ge0. $$

Apply part (b) to divide $V_1$ by $V_2$:

$$ V_1=UV_2+R, \qquad \deg(R)<\deg(V_2). \tag{10} $$

Multiplying (10) by $U_2$ and using (8),

$$ U_1V_1 = U_2UV_2+U_2R. $$

Hence

$$ (U_1-U_2U)V_2=U_2R. \tag{11} $$

The left side of (11) is homogeneous of degree

$$ \deg(U_1)+\deg(V_1), $$

while every term of the right side has degree

$$ <\deg(U_2)+\deg(V_2) = \deg(U_1)+\deg(V_1), $$

because of (8).

Therefore both sides of (11) must vanish:

$$ R=0, \qquad U_1=U_2U. $$

From (10),

$$ V_1=UV_2. $$

Thus there exists a homogeneous polynomial $U$ such that

$$ U_2=U_1U, \qquad V_1=UV_2, $$

after replacing $U$ by its opposite-side factor according to the notation of the statement.

(d)

Assume that homogeneous polynomials $U$ and $V$ satisfy

$$ UV=VU. \tag{12} $$

If either polynomial has degree $0$, the result is immediate. Assume both degrees are positive.

Apply part (c) to

$$ UV=VU. $$

If

$$ \deg(U)\ge\deg(V), $$

part (c) yields a homogeneous polynomial $T$ such that

$$ U=TV, \qquad V=VT_1. $$

Substituting into (12) gives

$$ TVV=VTV. $$

Since cancellation is valid in the free associative algebra,

$$ TV=VT. \tag{13} $$

Equation (13) expresses a commuting pair whose total degree is smaller than that of $(U,V)$. Repeating the argument recursively eventually reaches a homogeneous polynomial $W$ such that

$$ U=rW^m, \qquad V=sW^n, $$

for rational numbers $r,s$ and integers $m,n\ge0$.

To obtain the solution of largest degree, repeatedly replace the pair $(U,V)$ by the factor pair supplied by part (c). Each step removes a common homogeneous factor of positive degree. The process terminates because degrees strictly decrease. The final polynomial $W$ has the greatest possible degree, since any other common homogeneous root would divide every factor extracted during the recursion and therefore divide the final $W$.

This yields an algorithm analogous to Euclid's algorithm. At each stage, use part (c) to extract the larger common factor; the terminal factor is the required $W$.

Verification

For part (a), the construction compares the highest-degree homogeneous components. Equality of those components follows directly from

$$ \deg(Q_1U-Q_2V)<\deg(Q_1U). $$

The extracted polynomial $Q$ cancels all degree-$d$ terms, hence the degree decreases.

For part (b), every application of part (a) lowers the degree of the current remainder. Since the degree is a nonnegative integer, termination is guaranteed. The final remainder has degree $<\deg(V)$.

For part (c), division from part (b) gives

$$ V_1=UV_2+R. $$

Homogeneity forces the remainder term in (11) to vanish because its degree is strictly smaller than the degree of the left side. Hence $R=0$ and exact divisibility follows.

For part (d), repeated application of part (c) reduces the problem to commuting homogeneous factors of smaller degree. The descent terminates and produces a common homogeneous root $W$. Every other common root divides each extracted factor, hence divides $W$; therefore $W$ has maximal degree.

Notes

Part (d) is the noncommutative analogue of the classical theorem that commuting words are powers of a common word. When $U=\alpha$ and $V=\beta$ are single strings, the algorithm specializes to the standard result

$$ \alpha\beta=\beta\alpha \quad\Longrightarrow\quad \alpha=\gamma^m,\qquad \beta=\gamma^n. $$

For $U=z^m$ and $V=z^n$, the largest-degree solution is

$$ W=z^{\gcd(m,n)}, $$

so the procedure contains Euclid's algorithm for integers as a special case.

This completes the proof.

∎