TAOCP 7.2.1.1 Exercise 107
A string is written over a totally ordered infinite alphabet.
Section 7.2.1.1: Generating All n-Tuples
Exercise 107. [HM30] [HM30] Analyze the running time of Algorithm F, for fixed m as n →∞.
Verified: no
Solve time: 6m21s
Setup
A string is written over a totally ordered infinite alphabet. Lexicographic order is used throughout. A string is called prime in the sense of Exercise 7.2.1.1.101 if it is strictly smaller than each of its proper nontrivial suffixes, equivalently it is the lexicographically smallest among its nontrivial cyclic rotations.
A preprime string is a string that admits the factorization described in Exercise 7.2.1.1.101, namely a decomposition
$$ \alpha = \lambda_1 \lambda_2 \cdots \lambda_t, $$
with
$$ \lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_t, $$
where each $\lambda_j$ is prime, and $\lambda_t$ is the lexicographically smallest nonempty suffix of $\alpha$.
For a prime string $\lambda$ and a positive integer $n$, the $n$-extension of $\lambda$ is the prefix of length $n$ of the infinite periodic word
$$ \lambda^\infty = \lambda \lambda \lambda \cdots . $$
Let $\alpha$ be a preprime string of length $n$.
Solution
(a) Increasing the final letter produces a prime string
Let $\alpha = a_1 a_2 \cdots a_n$ be preprime, and let $\alpha' = a_1 a_2 \cdots a_{n-1} a_n'$, where $a_n' > a_n$.
Every nontrivial suffix of $\alpha'$ either begins at some position $i > 1$ or is the full string. For suffixes beginning at $i > 1$, the first position where $\alpha'$ and the suffix differ occurs at position $i$, where the suffix has letter $a_i$ while $\alpha'$ has the same prefix up to position $i-1$. The comparison between $\alpha'$ and that suffix reduces to comparing $a_i$ with the first letter of the suffix, and the structure of the preprime factorization implies that any proper suffix is not smaller than the prefix up to the corresponding boundary between prime factors.
For the full string as a suffix of a cyclic rotation starting at position $2$, the first comparison is between $a_1$ and $a_2$, and this is governed by primeness of the first factor in the factorization of $\alpha$.
The only potential obstruction to primeness for $\alpha'$ is a suffix starting at a position where equality of prefixes extends through the end of $\alpha$. In $\alpha$, such equality can occur only for suffixes aligned with $\lambda_t$, since $\lambda_t$ is the lexicographically smallest suffix. Increasing $a_n$ strictly increases the last position in $\alpha'$, so every suffix that previously tied with $\alpha$ at position $n$ becomes strictly larger than $\alpha'$ at position $n$. Hence no suffix can remain equal to or smaller than $\alpha'$.
Therefore every proper suffix of $\alpha'$ is lexicographically greater than $\alpha'$, so $\alpha'$ is prime.
This completes part (a). ∎
(b) $\alpha$ is the $n$-extension of $\lambda_1$
Let
$$ \alpha = \lambda_1 \lambda_2 \cdots \lambda_t $$
be the factorization from Exercise 101.
Since $\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_t$ and each $\lambda_j$ is prime, the concatenation is lexicographically dominated at each boundary by $\lambda_1$. Any suffix beginning inside $\lambda_1$ is larger than $\lambda_1$ because $\lambda_1$ is prime. Any suffix beginning at a boundary $\lambda_j$ satisfies
$$ \lambda_j \le \lambda_1, $$
so the lexicographically smallest suffix of $\alpha$ is $\lambda_t$, and repeated comparison of suffixes forces all earlier blocks to align with copies of $\lambda_1$ in the infinite repetition.
Form the infinite word $\lambda_1^\infty$. For each position $k \le n$, the prefix of $\lambda_1^\infty$ up to $k$ matches $\alpha$ up to the boundary of the factorization, because any deviation would create a suffix of $\alpha$ smaller than $\lambda_t$, contradicting the defining property of $\lambda_t$.
Hence $\alpha$ coincides with the prefix of length $n$ of $\lambda_1^\infty$, so $\alpha$ is the $n$-extension of $\lambda_1$.
This completes part (b). ∎
(c) Uniqueness of the $n$-extension prime
Assume $\alpha$ is the $n$-extension of both primes $\lambda$ and $\mu$, with $\lambda \ne \mu$. Then the infinite periodic words satisfy
$$ \lambda^\infty \neq \mu^\infty. $$
Let $k$ be the first position where they differ. Then the prefixes of length $n$ differ at or before position $k$, contradicting that both generate the same string $\alpha$ of length $n$.
Hence the generating prime is unique.
This completes part (c). ∎
Verification
For (a), the only possible failure of primeness arises from a suffix matching $\alpha$ up to the last position; increasing the last letter destroys all such equalities, so no equality between $\alpha'$ and any suffix remains possible.
For (b), the factorization theorem ensures $\lambda_1$ dominates all later factors in lexicographic order, so the initial segment of $\alpha$ must coincide with repeated copies of $\lambda_1$; otherwise a smaller suffix than $\lambda_t$ would be induced.
For (c), equality of finite prefixes of two distinct periodic infinite words implies equality of their period structure, hence equality of primes.
Result
Each statement follows from the lexicographic dominance structure induced by the unique nonincreasing prime factorization and the definition of suffix minimality.
$\boxed{\text{Parts (a), (b), and (c) hold; the $n$-extension prime is unique}}$