Totally Unclustered BWT Images of Any Length over Non-Binary Alphabets

Abstract

We prove that for every integer n > 0 and for every alphabet Σk of size k ≥ 3, there exist words of length n whose Burrows–Wheeler Transform (BWT) is totally unclustered, i.e., it consists of exactly n runs with no two consecutive equal symbols. These words represent the worst-case behavior of the clustering effect of the BWT. We also establish a lower bound on their number. This contrasts with the binary case, where the existence of infinitely many totally unclustered BWT images is still an open problem, related to Artin’s conjecture on primitive roots.