Unclustered BWTs of any Length over Non-Binary Alphabets

Gabriele Fici, Estéban Gabory · 2025

Read Unclustered BWTs of any Length over Non-Binary Alphabets by Gabriele Fici, Estéban Gabory (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-20879.txt.

Introduction

Gabriele Fici, Esteban Gabory, and co-authors construct strings with fully scattered transforms in a 2025 paper. The Burrows-Wheeler transform rearranges a string to cluster equal letters, which aids compression. The worst case for clustering is a transform where no two neighbors match at all.

The authors prove such strings exist at every length for alphabets of three or more letters. Their construction uses necklaces, a cyclic form of strings. They also lower-bound how many of these extreme strings exist. The binary alphabet case stays open and links to a famous conjecture about primitive roots. The result closes a basic question in combinatorics on words. It also marks the true worst case for transform-based compressors.

Catalog record

CREATORGabriele Fici, Estéban Gabory
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-20879

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Unclustered BWTs of any Length over Non-Binary Alphabets Gabriele Fici, Estéban Gabory Abstract We prove that for every integer n > 0 n>0 and for every alphabet Σ k \Sigma_{k} of size k ≥ 3 k\geq 3 , there exists a necklace of length n n whose Burrows–Wheeler Transform (BWT) is completely unclustered, i.e., it consists of exactly n n runs with no two consecutive equal symbols. These words represent the worst-case behavior of the BWT for clustering, since the number of BWT runs is maximized. We also establish a lower bound on their number. This contrasts with the binary case, where the existence of infinitely many completely unclustered BWTs is still an open problem, related to Artin’s conjecture on primitive roots. 1 Introduction The Burrows–Wheeler Transform (BWT) is a transformation on words introduced in 1994 [ 9 ] . When applied to a text, it produces a permutation obtained by concatenating the last character of each cyclic rotation (also called shift) of the text, after sorting all such rotations in lexicographic order. Since two shifts of the same word yield the same BWT, this transform can be naturally viewed as a mapping from the set of necklaces over a finite alphabet \Sigma_{k}=\{0,1,\ldots,k-1\} (i.e., equivalence classes of words under shift operation) to the set of words of \Sigma_{k}^{*} . The BWT is a widely used tool in data compression and indexing, because it is very likely to produce long runs of identical consecutive symbols (BWT-runs) when the input text is highly repetitive (clustering effect). This property is effectively exploited when combined with run-length encoding techniques. However, it is interesting to note that, while the BWT of a word typically exhibits some degree of clustering, there exist texts for which no such clustering occurs. In this work, we focus on the worst-case scenario: words whose BWT is completely unclustered, meaning that no two consecutive characters are the same. That is, the BWT consists of exactly as many runs as the length of the word. These unclustered BWTs also represent the worst cases for compression and indexing algorithms that use the Run-Length BWT. This problem was previously studied by Mantaci et al. [ 10 ] in the case of binary alphabets, revealing a connection with the generators of the multiplicative group \mathbb{Z}^{*}_{n} of integers modulo n , as stated in the following result: Theorem 1 ( [ 10 ] ) . There exists a 2n -length necklace with completely unclustered BWT if and only if 2n+1 is an odd prime and 2 generates the cyclic group \mathbb{Z}^{*}_{2n+1} . However, the question of whether infinitely many binary words with completely unclustered BWT exist is left open in [ 10 ] . This problem is tightly connected to the still-open Artin’s conjecture on the existence of primitive roots modulo infinitely many prime numbers. Here, we move beyond the binary setting and prove that the existence of completely unclustered BWTs is guaranteed for every length as soon as the alphabet contains at least three letters. In particular, we prove the following: {restatable*} theoremmainresult For every integer n>0 , and k\geq 3 , there exists a necklace u of length n over the alphabet \Sigma_{k} having completely unclustered BWT . Our approach builds upon the structure of generalized de Bruijn words and their correspondence with Hamiltonian paths in generalized de Bruijn graphs introduced in [ 5 ] . In particular, we prove the following result: {restatable*} theoremunclusteredDBW For every integer n>0 , and k\geq 3 , there exists a generalized de Bruijn word of length kn over \Sigma_{k} with completely unclustered BWT . In particular, there exists a (standard) de Bruijn word of length k^{n} over \Sigma_{k} with completely unclustered BWT . The key point is that generalized de Bruijn words, defined in the sense of [ 5 ] , are necklaces having a BWT consisting of consecutive blocks each of which is a permutation of the alphabet. As proved in [ 5 ] , generalized de Bruijn words are precisely the Hamiltonian cycles of the generalized de Bruijn graphs, introduced in the early 80 ’s independently by Imase and Itoh [ 6 ] , and by Reddy, Pradhan, and Kuhl [ 12 ] (see also [ 4 ] ) in the context of network design. Here, we provide a new algorithmic strategy that exploits combinatorial properties of generalized de Bruijn graphs, making it possible to remove equal letters between successive blocks of the BWT, thereby obtaining necklaces of length kn whose BWTs are completely unclustered. We then show how to extend this procedure to every length, not just multiples of the size of the alphabet. Beyond existence, we also investigate counting aspects: we provide a lower bound of \Omega(2^{n}/n) on the number of ternary necklaces of length 3n with completely unclustered BWT . Finally, in Section 5 we examine a special case connected to Artin’s conjecture, showing that certain highly structured words are BWT images precisely when kn+1 is prime and k is a primitive root modulo kn+1 . 2 Preliminaries We begin by introducing some preliminary definitions. For a thorough introduction, we refer the reader to [ 3 ] and [ 8 ] . Let \Sigma_{k}=\{0,1,\ldots,k-1\} , k>1 , be a sorted set of letters , called the alphabet . A word over the alphabet \Sigma_{k} is a concatenation of elements of \Sigma_{k} . The length of a word w is denoted by |w| . For a letter i\in\Sigma_{k} , |w|_{i} denotes the number of occurrences of i in w . The vector (|w|_{0},\ldots,|w|_{k-1}) is the Parikh vector of w . Let w=w_{0}\cdots w_{n-2}w_{n-1} be a word of length n>0 . When n>1 , the shift of w is the word \sigma(w)=w_{n-1}w_{0}\cdots w_{n-2} . For a word w , the n -th power of w is the word w^{n} obtained by concatenating n copies of w . We call an alphabet-permutation a word over \Sigma_{k} that contains each letter of \Sigma_{k} exactly once, and an alphabet-permutation power a concatenation of one or more alphabet-permutations over \Sigma_{k} . Example 2 . The word w=210201102102120 is an alphabet-permutation power over \Sigma_{3} . Two words w and w^{\prime} are conjugates if w=uv and w^{\prime}=vu for some words u and v . The conjugacy class of a word w can be obtained by repeatedly applying the shift operator, and contains |w| distinct elements if and only if w is primitive , i.e., for any nonempty word v and integer n , w=v^{n} implies n=1 . A necklace (resp. aperiodic necklace ) [w] is a conjugacy class of words (resp. of primitive words ). Necklaces are also called circular words . For example, [1100]=\{1100,0110,0011,1001\} is an aperiodic necklace, while [1010]=\{1010,0101\} is not aperiodic. The Burrows–Wheeler matrix (BWT matrix) of a necklace [w] is the matrix whose rows are the |w| shifts of w in ascending lexicographic order. Let us denote by F and L , respectively, the first and the last column of the BWT matrix of [w] . We have that F=0^{n_{0}}1^{n_{1}}\cdots(k-1)^{n_{k-1}} , where (n_{0},\ldots,n_{k-1}) is the Parikh vector of [w] ; L , instead, is the Burrows–Wheeler Transform (BWT) of [w] . The BWT is therefore a map from the set of necklaces to the set of

Read the complete text