1 Introduction and motivation↩︎

Run-length compression of the Burrows–Wheeler transform (BWT) [1] exploits a basic clustering effect: after sorting contexts, equal letters often become grouped into long runs. This paper studies the opposite extremal regime, in which the BWT output is completely unclustered.

A factor-two theorem of Mantaci et al. [2] shows that this opposite behaviour is universally bounded: for every Lyndon word \(w\), \[\label{eq:MRRSV-bound} \rho(\operatorname{BWT}(w))\le 2\rho(w).\tag{1}\] Moreover, the factor \(2\) is sharp, and the binary case of maximal unclustering is governed by primitive-root arithmetic.

A recent theorem of Fici et al. [3] gives a complementary existence result. For every integer \(n>0\) and every alphabet size \(k\ge3\), there exists a primitive necklace \([u]\) of length \(n\) over \(\Sigma_k\) whose BWT is completely unclustered: \[\rho(\operatorname{BWT}([u]))=n.\] Their proof proceeds through generalized de Bruijn words and then uses insertion/deletion operations preserving the cyclicity of the standard permutation. For the generalized de Bruijn viewpoint on BWT and standard permutations, see also Fici–Gabory [4].

These two results leave a natural joint extremal problem. Inequality 1 implies that if \(\operatorname{BWT}([u])\) has \(n\) runs, then the input necklace must have at least \(\lceil n/2\rceil\) cyclic runs. The existence theorem of [3] shows that BWT outputs with \(n\) runs exist in every length over non-binary alphabets. The missing question is whether the two extremal behaviours can occur simultaneously: \[\rho(\operatorname{BWT}([u]))=n, \qquad \rho_{\circ}([u])\approx n/2.\] We investigate this extremal question in the present paper.

Our main contributions are:

1. we introduce \(U_k(n)\) and prove the universal lower bound \(U_k(n)\ge\lceil n/2\rceil\);

2. we reduce the one-cycle sharpness problem to an explicit Hamming-distance criterion;

3. we compute the first small values, including the exceptional value \(U_k(6)=4\);

4. we construct Artin-type sharp families in the adjacent lengths \(p-1\) and \(p\);

5. we prove a parity obstruction for the Parikh vectors of sharp examples;

6. we determine the associated multiset-of-necklaces relaxation exactly.

2 Preliminaries↩︎

2.1 Words, necklaces, and runs↩︎

Fix an ordered alphabet \[\Sigma_k=\{0<1<\cdots<k-1\}.\] For a word \(w=w_0w_1\cdots w_{n-1}\in\Sigma_k^n\), its ordinary, linear number of equal-letter runs is \[\rho(w)= \begin{cases} 0,& n=0,\\ 1+\#\{0\le i<n-1: w_i\ne w_{i+1}\},& n>0. \end{cases}\]

Throughout the paper, positions in words of length \(n\) are indexed from \(0\) to \(n-1\). For a letter \(a\in\Sigma_k\), we write \[|w|_a=\#\{0\le i<n:w_i=a\}\] for the number of occurrences of \(a\) in \(w\). The Parikh vector of \(w\) is \[\operatorname{Parikh}(w)=(|w|_0,\ldots,|w|_{k-1}).\]

A necklace \([w]\) is a conjugacy class of words under cyclic rotation. It is primitive, or aperiodic, if it contains \(n\) distinct conjugates. For a nonconstant necklace we define its cyclic run number by \[\rho_{\circ}([w])= \#\{i\in\mathbb{Z}/n\mathbb{Z}: w_i\ne w_{i+1}\}.\] For a constant necklace we set \(\rho_{\circ}([w])=1\). Equivalently, \[\rho_{\circ}([w])=\min\{\rho(v):v\in[w]\}.\]

2.2 The BWT of a primitive necklace↩︎

Let \([u]\) be a primitive necklace of length \(n\). Its BWT matrix is the matrix whose rows are the \(n\) cyclic shifts of \(u\), sorted lexicographically. The \(\operatorname{BWT}([u])\) is the last column of this matrix. The first column is the sorted word \[F=\operatorname{sort}(L),\qquad L=\operatorname{BWT}([u]).\]

If \(L=L_0L_1\cdots L_{n-1}\), its standard permutation \(\pi_L\) is the stable sorting map from the last column to the first column. More explicitly, if \(L_i=a\) and this is the \(r\)-th occurrence of \(a\) in \(L\), counted from \(0\), then \[\label{eq:standard-permutation} \pi_L(i)=C_a+r, \qquad C_a=\sum_{b<a}|L|_b.\tag{2}\] Thus \(\pi_L(i)\) is the position in \(F\) corresponding to the occurrence \(L_i\). In particular, \[\label{eq:L-F-pi} L_i=F_{\pi_L(i)}.\tag{3}\] A standard criterion says that a word \(L\in\Sigma_k^n\) is the BWT of an aperiodic necklace if and only if \(\pi_L\) is a single cycle of length \(n\); see, e.g., [3], [5], [6].

3 The extremal function \(U_k(n)\)↩︎

For \(k\ge3\), the non-binary existence theorem for completely unclustered BWT images [3] implies that the set in 4 is nonempty for every \(n\). Thus \(U_k(n)\) is finite for all \(n\) and \(k\ge3\).

4 Standard-permutation formulae for input and output runs↩︎

The following elementary lemma is the main bookkeeping tool. It turns the extremal problem into a problem about the crossing pattern of a permutation with respect to the ordered intervals of the sorted word \(F\).

5 The Gessel–Restivo–Reutenauer viewpoint↩︎

The standard-permutation formulation above is a one-cycle fragment of the classical Gessel–Restivo–Reutenauer bijection [5], which we call the GRR bijection below. Adding this viewpoint is useful for two reasons. First, it embeds the function \(U_k(n)\) into a broader multiset-of-necklaces framework. Second, it provides an exact Parikh-vector baseline count for possible one-cycle BWT images before imposing the completely-unclustered condition.

5.1 The GRR multiset associated with a word↩︎

Let \(L\in\Sigma_k^n\), let \(\pi_L\) be its standard permutation in the convention of 2 , and put \[\tau_L=\pi_L^{-1}.\] Write the disjoint cycle decomposition of \(\tau_L\). If \[C=(i_0,i_1,\ldots,i_{m-1})\] is a cycle, where \(\tau_L(i_j)=i_{j+1}\) cyclically, associate to it the necklace \[N_C=[L_{i_0}L_{i_1}\cdots L_{i_{m-1}}].\] The GRR map sends \[L\longmapsto \Phi(L):=\{N_C:C\in\operatorname{Cyc}(\tau_L)\},\] a multiset of primitive necklaces. With the above convention one uses the inverse standard permutation; using the standard permutation instead gives the same cycle type and an equivalent convention. The GRR theorem states that \(\Phi\) is a bijection from words of length \(n\) over the ordered alphabet to multisets of primitive necklaces of total length \(n\), preserving the Parikh vector and the cycle type. The usual BWT of one primitive necklace is precisely the inverse map restricted to multisets consisting of a single necklace [5].

This suggests a relaxed version of the extremal function in which the inverse object is allowed to be a multiset of necklaces rather than one necklace.

Since every completely unclustered one-cycle BWT image \(L\) is also an admissible word in the GRR relaxation, and in the one-cycle case \(R_{\operatorname{GRR}}(L)=\rho_{\circ}(\operatorname{BWT}^{-1}(L))\), we immediately have \[\widetilde{U}_k(n)\le U_k(n).\] Thus the original problem is the one-cycle refinement of a natural GRR multiset minimization problem.

We shall determine \(\widetilde{U}_k(n)\) exactly in Theorem 16. The remaining issue is whether a minimizing GRR multiset can be represented by a single standard cycle.

Proposition 4 shows that this relaxation is still not merely a Hamming-distance minimization problem. Any possible gap between \(\widetilde{U}_k(n)\) and \(U_k(n)\) must take into account both crossing edges and letter-constant GRR cycles. Thus the multiset relaxation is useful as a structural comparison, but it does not by itself prove or disprove the sharp one-cycle conjecture.

5.2 A Parikh-vector baseline count↩︎

Let \[\alpha=(\alpha_0,\ldots,\alpha_{k-1}),\qquad |\alpha|=\sum_a\alpha_a=n,\] be a Parikh vector. Let \(B_k(\alpha)\) denote the number of words \(L\in\Sigma_k^n\) with Parikh vector \(\alpha\) such that \(\pi_L\) is a single cycle. Equivalently, \(B_k(\alpha)\) counts BWT images of primitive necklaces with Parikh vector \(\alpha\). This count does not impose the condition \(\rho(L)=n\); it is a baseline count before the unclustered restriction.

5.3 A block-coloured cycle model↩︎

The GRR viewpoint also gives a useful permutation-only model. Fix a Parikh vector \(\alpha\) of total size \(n\), and partition \(\{0,\ldots,n-1\}\) into consecutive blocks \[I_0,I_1,\ldots,I_{k-1}, \qquad |I_a|=\alpha_a.\] Let \[b_\alpha(r)=a\quad\text{if }r\in I_a.\] A permutation \(\tau\in S_n\) is called \(\alpha\)-ascending if it is increasing on each block \(I_a\): whenever \(r<s\) and \(r,s\in I_a\), one has \(\tau(r)<\tau(s)\).

Proposition 8 is often the cleanest formulation of the exact sharpness problem. Conjecture 10 asks whether, for every sufficiently large \(n\), one can choose \(\alpha\) and an \(\alpha\)-ascending \(n\)-cycle \(\tau\) satisfying the no-adjacent-equal output condition and having exactly \(\lceil n/2\rceil\) colour-crossing cycle edges.

6 Small values and computational evidence↩︎

The lower bound of Proposition 1 is sharp in many small cases. The following table lists completely unclustered BWT images \(L\) over the ternary alphabet and one inverse necklace representative \(u\). The examples prove the corresponding upper bounds for every alphabet size \(k\ge3\).

The length \(6\) example shows that \(U_k(6)\le4\), while the general lower bound only gives \(U_k(6)\ge3\). A finite enumeration shows that the value \(3\) is impossible.

7 Main conjecture↩︎

Equivalently, over any non-binary alphabet the BWT should be able to be simultaneously maximally unclustered and maximally run-amplifying, up to the universal factor-two lower bound.

By Corollary 1, this is equivalent to the ternary Hamming construction problem stated above.

8 Comparison with the binary case and Artin-type families↩︎

In the binary case, complete unclusteredness forces \(L\) to be alternating, and the standard/FL mapping becomes conjugate, depending on convention, to multiplication by \(2^{-1}\) or by \(2\) modulo an odd integer.

9 Parikh obstructions and the GRR relaxation↩︎

The following observation gives a universal Parikh obstruction for sharp examples. It will also be used below to evaluate the GRR multiset relaxation.

The unrestricted one-cycle baseline for a fixed Parikh vector is already given by Proposition 6. The sharp Parikh-constrained problem is therefore a refinement of the GRR enumeration by two extra conditions: the no-adjacent-equal condition on \(L\), and the Hamming condition \(d_{\mathrm H}(L,\operatorname{sort}(L))=\lceil n/2\rceil\). Proposition 8 reduces this refinement to a finite problem about \(\alpha\)-ascending coloured cycles with a prescribed number of colour-crossing edges.

Thus the GRR relaxation is completely determined; the remaining gap is exactly the one-cycle sharpness defect.

The correction formula 6 shows why this question is subtler than a pure crossing-number relaxation: splitting a permutation into several GRR cycles may reduce the number of crossing edges, but letter-constant cycles contribute one run each. Thus a putative strict inequality \(\widetilde{U}_k(n)<U_k(n)\) must overcome this constant-cycle correction.

10 Open problems↩︎

11 Verification code for the small obstruction↩︎

The following Python script exhaustively enumerates all ordered equality patterns of length \(6\). This verifies both \(U_k(6)=4\) and \(\widetilde{U}_k(6)=4\). Since every word of length \(6\) over an ordered alphabet is order-isomorphic to one of these patterns, the verification is independent of the alphabet size. Here two words are order-isomorphic if they induce the same equality pattern and the same relative order on the occurring letters.

from itertools import product

def stable_permutation(L):
    F = sorted(L)
    occ_F, pos = {}, {}
    for j, c in enumerate(F):
        r = occ_F.get(c, 0)
        pos[(c, r)] = j
        occ_F[c] = r + 1

    occ_L, pi = {}, []
    for c in L:
        r = occ_L.get(c, 0)
        pi.append(pos[(c, r)])
        occ_L[c] = r + 1
    return pi

def inverse_perm(p):
    q = [0] * len(p)
    for i, j in enumerate(p):
        q[j] = i
    return q

def cycles(p):
    seen = [False] * len(p)
    out = []
    for i in range(len(p)):
        if not seen[i]:
            C, x = [], i
            while not seen[x]:
                seen[x] = True
                C.append(x)
                x = p[x]
            out.append(C)
    return out

def is_one_cycle(p):
    return len(cycles(p)) == 1

def is_unclustered(L):
    return all(L[i] != L[i+1] for i in range(len(L)-1))

def hamming_to_sorted(L):
    F = sorted(L)
    return sum(L[i] != F[i] for i in range(len(L)))

def constant_cycle_correction(L):
    tau = inverse_perm(stable_permutation(L))
    return sum(len({L[i] for i in C}) == 1 for C in cycles(tau))

def grr_run_number(L):
    return hamming_to_sorted(L) + constant_cycle_correction(L)

def canonical_pattern(L):
    alphabet = sorted(set(L))
    relabel = {c: i for i, c in enumerate(alphabet)}
    return tuple(relabel[c] for c in L)

n = 6
patterns = sorted({
    canonical_pattern(L)
    for L in product(range(n), repeat=n)
})

best_one_cycle = None
best_grr = None
count_best_one_cycle = 0
count_best_grr = 0

for L in patterns:
    if not is_unclustered(L):
        continue

    pi = stable_permutation(L)
    h = hamming_to_sorted(L)

    if is_one_cycle(pi):
        if best_one_cycle is None or h < best_one_cycle:
            best_one_cycle = h
            count_best_one_cycle = 1
        elif h == best_one_cycle:
            count_best_one_cycle += 1

    grr = grr_run_number(L)
    if best_grr is None or grr < best_grr:
        best_grr = grr
        count_best_grr = 1
    elif grr == best_grr:
        count_best_grr += 1

print("number of ordered equality patterns:", len(patterns))
print("best one-cycle:", best_one_cycle)
print("number of best one-cycle patterns:", count_best_one_cycle)
print("best GRR:", best_grr)
print("number of best GRR patterns:", count_best_grr)

assert best_one_cycle == 4
assert best_grr == 4

The output is:

number of ordered equality patterns: 4683
best one-cycle: 4
number of best one-cycle patterns: 19
best GRR: 4
number of best GRR patterns: 67

Thus the enumeration verifies both \(U_k(6)=4\) and \(\widetilde{U}_k(6)=4\).

References↩︎