A floor under a run count

There are 4,096 strings of twelve characters over two symbols. Transform every one of them and count the runs in the result.

This is the site’s seventh lower-bound argument and its second of the counting kind. It is short enough to state in one sentence.

The argument #

An index that can hand its text back must give a different bit string to every text it might hold. If its size is a function of $r$ alone, then all the texts with at most $r$ runs are stored in bit strings of the same length, so there must be at least as many bit strings of that length as there are such texts:

$$f(r) \;\ge\; \log_2 N(n, \sigma, r)$$

where $N$ is the number of texts of length $n$ over $\sigma$ symbols whose transform has at most $r$ runs.

The whole content is in $N$, and $N$ is not estimated here. Every one of the $\sigma^n$ texts is transformed, its runs counted, and the histogram accumulated — so the right-hand column above is exact, and so is the claim that only 154 of 4,096 texts have four runs or fewer.

What the shape says #

The floor reaches 11.15 bits at $r = 7$ and 12.00 — the whole text — at $r = 10$. So:

Texts with few runs are rare, and the rarity is steep. Two texts have two runs; twenty-five have three; a hundred and twenty-seven have four. By the seventh run count the cumulative floor is 93% of the way to storing the text uncompressed.

That is the standard fact about compressibility — most strings are incompressible, by any measure — made exact for this one. It is worth having exactly rather than in general because $r$ is the measure a whole family of structures is built on, and “an index of size $O(r\log(n/r))$” invites the reading that $r$ can be small for interesting inputs. It can, and the inputs for which it is are a vanishing fraction of all inputs. A repetitive collection is a special input and the structure is built for it; the floor is the statement of how special.

And the distribution has a mode in the middle. The most common run count is seven of a possible thirteen, held by 990 of the 4,096 texts. Nothing is uniform here and nothing is concentrated at either end.

The floor is small and the structure is not #

At $r = 4$ the floor is 7.27 bits. The smallest run-length index measured over a four-run text of this length is 142.

That ratio is nineteen and it is not a finding about the structure. At twelve characters an index is almost entirely constants: a C table with an entry per symbol, sample widths, the fixed parts of three bit vectors. The floor is measuring information and the structure is measuring an implementation, and at a length where the implementation’s constants dominate, the comparison says only that the constants dominate.

So the honest use of this floor is not as a constant-factor claim. What it establishes is the existence and shape of a bound in $r$, which no earlier essay in this strand had: everything up to here measured what a structure costs, and this measures what any structure must.

The gap does narrow where it can be seen at all. Over three symbols and nine characters the same construction gives floors of 8.75 at $r=4$ and 13.99 at $r=8$, against measured minima of 132 and 200 — a ratio of 15.1 falling to 14.3 as the floor rises and the constants stay put.

Why this is a floor and not a size #

One clarification, because the argument is short enough to be misread as saying something stronger than it does.

The floor bounds a structure whose size is a function of $r$ alone. That is the shape every published bound in this family has — $O(r\log(n/r))$, $O(r)$ words, $O(r\log(n/r) + n/s\log n)$ — and it is the shape because $r$ is the parameter the family is named for.

A structure whose size depends on something else is not bound by it. An index that stored the text and reported its run count would be $n\log\sigma$ bits and would satisfy nothing above; an index proportional to $z$ or to a grammar size is measuring a different quantity and needs its own argument. The floor is about a class of structures, and the class is defined by the parameter rather than by the mechanism.

Which is why the argument is worth making at all. “This structure is $O(r\log(n/r))$” is a claim about one implementation; “no structure of size $f(r)$ can be smaller than $\log_2 N(\le r)$” is a claim about every implementation anybody could write with that shape of bound, and it is the second that says whether the shape is the right one to be chasing.

The representation is not tight, and the slack is exactly countable #

The second half is sharper, because it compares two counts rather than a count with an implementation.

A run-length representation of a transform is two things: a sequence of $r$ heads in which no two neighbours are equal, and a composition of the transform’s $n+1$ positions into $r$ positive parts. So the number of representable configurations is

$$(\sigma+1)\,\sigma^{\,r-1} \binom{n}{r-1}$$

— the first head free over the alphabet with its sentinel, every later head anything but its predecessor, and the lengths any positive composition.

The Burrows-Wheeler transform is not onto. Most strings are not the transform of anything, because inverting one requires its LF permutation to close into a single cycle, and a representation that stores heads and lengths without that constraint can express configurations that decode to nothing.

So a structure storing the runs of a transform is wasting between five and thirteen bits of every text at this length, and no amount of coding each part better recovers them — the waste is not in how the heads and lengths are encoded, it is in the fact that they are stored as heads and lengths at all.

That is a different kind of statement from the floor above it. The floor says how much information there is; this says that the representation everybody uses does not achieve it, and by exactly how much.

Why the transform is not onto, in one paragraph #

The slack above rests on a fact worth stating plainly, because it is the only part of the argument that is not counting.

A transform is inverted by the LF mapping: from a row, one operation gives the row of the rotation one character earlier, and repeating it $n+1$ times walks every position of the text exactly once. That walk is a permutation of the rows, and inverting the transform requires it to be a single cycle. A string that produces two or more cycles inverts to two or more shorter texts glued in an order nothing recovers, and is the transform of nothing.

Nothing in a run representation enforces that. Heads that alternate legally and lengths that sum correctly can describe a string whose LF permutation has three cycles, and the structure will store it, answer ranks about it, and return nonsense if asked for its text. The slack is exactly the count of those.

And it is why this collection’s index machinery checks the round trip rather than the shape. A structure that verified its own heads and lengths would accept every one of the 5,280 configurations at $r = 4$; the check that rejects the 5,153 impossible ones is asking for the text back and comparing it.

The lengths alone are not enough, and here is the pair #

The other direction: could a structure drop the heads and store only the lengths, which are the cheap part?

No, and the refutation is produced rather than argued. Walking all 256 texts of eight characters over two symbols, the first pair whose transforms have identical run lengths in identical order:

Two texts, one length sequence. A structure storing only the lengths would have to return one text for both, and the check that catches it is the one this strand has run since it opened: hand the text back, character for character.

The heads are 1,563 bits of the 11,900-bit structure at thirty-two copies — 13% — and this is the eight-character demonstration that they cannot be the part that is dropped.

The seven floors, and which kind this is #

It is worth placing this one, because the collection now has seven and they are not the same sort of object.

Five of the seven are counting arguments and they differ in what is being counted: outcomes of comparisons, distinguishable machine states, code words, and now texts. The one common move is the same each time — some set has to be mapped injectively into some other set, so the second must be at least as large — and everything interesting is in identifying the two sets correctly.

This one’s sets are the easiest to name and the hardest to count. The texts with at most $r$ runs, and the bit strings a structure of that size can produce. The second is $2^{f(r)}$ by definition; the first has no closed form, which is why it is walked.

That is the trade this collection keeps making with its floors and it is worth being explicit about. An asymptotic argument would give a formula and no certainty about small cases; an exhaustive walk gives certainty about small cases and no formula. Six of the seven above are exhaustive at a size a figure can draw, and every one of them says so on its plate.

What this floor is and is not #

It is a bound on a representation, not on a problem. Every other floor on this site bounds the work or the space any algorithm must use to answer a question: comparison sorting, connectivity, a distinct count in one pass. This one bounds what a structure of a stated shape must cost, and a structure of a different shape is not bound by it — an index proportional to $z$, or to the size of the smallest grammar, is outside the argument entirely.

It is exhaustive rather than asymptotic, which is the trade this collection keeps making. Twelve characters is small enough to walk and small enough that a structure’s constants swamp everything, so what the walk buys is certainty about $N$ and nothing about how a real index behaves.

And it is not tight in the direction that matters. $\log_2 N(\le r)$ is a floor and the enumeration achieving it is not a structure anybody could query: it is a rank in a list, and computing it requires the list. The gap between “the information is $x$ bits” and “a searchable structure costs $y$” is where every one of this field’s essays lives.

None of those three sentences is a statement about twelve characters over two symbols, so the walk is run again over a different shape of text — nine characters over three symbols, where there are 19,683 texts rather than 4,096 and the alphabet is the thing that changed. If the floor were an artefact of the binary case it would be visible here.

Why the rarity is the parameterisation working #

The steepness of the first table can be read as bad news about the structure, and it is the opposite.

A bound in terms of a parameter is honest exactly when the inputs on which the parameter is small are as rare as the saving is large. If a tenth of all texts had two runs, a two-run index would be a general-purpose compressor and there would be a counting argument saying it cannot exist. The table says that only two of the 4,096 do — which is precisely the licence the structure needs.

So the floor is not in tension with the family’s claims. It is the statement that the family is claiming the right thing: small on a vanishing fraction of inputs, and the fraction vanishes at the rate the saving grows. Every legitimate parameterised bound has that shape, and the reason to compute it is that an illegitimate one does not.

That reframes what the parameter is for as well. $r$ is not a measure of how compressible a text is in general — the essays in this strand established that it disagrees with every entropy and with the phrase count. It is a certificate that a particular text belongs to a small family, and the index’s size is the cost of naming a member of that family. Read that way the whole construction is one sentence: a structure of $f(r)$ bits is an encoding of a text by its address within the set of texts with at most $r$ runs, plus whatever the encoding wastes.

The recipe, which audits any parameterised bound #

The argument in this essay is four lines long and it does not mention runs, transforms or indexes. Stripped to its parts it is a recipe, and the recipe is worth having because this collection is full of bounds it applies to.

Let $p$ be any statistic of an input — a run count, a phrase count, a number of distinct symbols, an entropy order, an alphabet size. Suppose a structure claims to occupy $f(p)$ bits and to be able to reproduce its input. Then every input with statistic at most $p$ gets a distinct bit string of length $f(p)$, so

$$f(p) \;\ge\; \log_2 \bigl\lvert \{\text{inputs} : \text{statistic} \le p\} \bigr\rvert$$

and nothing else about the structure enters. Count the inputs the parameter admits, take the logarithm, and that is the floor.

Two consequences fall straight out and both are useful for reading a bound rather than proving one.

A statistic with few values cannot support a good bound. If $p$ takes only $k$ distinct values over inputs of length $n$, then by the pigeonhole one of the classes holds at least $\sigma^n/k$ inputs, so the largest $f(p)$ is at least $n\log_2\sigma - \log_2 k$. A parameterisation into a handful of buckets is therefore worthless no matter how the buckets are chosen, and this can be seen without knowing anything about what the structure does. It is the reason nobody proposes an index parameterised by “how many distinct characters the text uses”: the count of texts over $d$ symbols is about $d^{\,n}$, so the floor is $n \log_2 d$, and the parameterisation buys exactly the alphabet reduction and not one bit more.

And a bound stated in a statistic of the input is a different object from a bound stated in its size. An index described as $n H_k + o(n)$ is not of the form $f(p)$ at all — $H_k$ is computed from the text, so two texts of the same length with the same $H_k$ may still need different structures, and the counting argument has to be reformulated before it applies. That is not a loophole; it is a note that the recipe needs its set defined carefully, which is the only place any of these arguments has ever gone wrong.

What the recipe does not give is any indication of how close a searchable structure can get. The floor is achieved by an enumeration, and an enumeration answers no questions. Every gap in this collection between a floor and a structure is that gap, and this essay’s is nineteen times at a length where the constants are the whole story.

What is not measured here #

Whether a tight searchable structure exists. The slack above says the heads-and-lengths representation is loose. It does not say that a structure achieving $\log_2 N$ and supporting rank is impossible, and nothing here bears on that.

The asymptotic form of $N$. Everything above is a walk at $n = 12$ and $n = 9$. What $\log_2 N(n,\sigma,r)$ looks like as $n$ grows is a counting problem with a known answer for compositions and no obvious one once the transform’s constraint is imposed, and no fit here would be worth the name at three points.

How many texts there are for a given $r$ at a useful length. The walk stops at twelve characters because $\sigma^n$ stops being walkable, and every number in this essay is therefore about texts far shorter than anything a run-length index would be built for. The shape of the distribution at twelve characters and at ten is the same, which is evidence and is not a proof that it stays so.

And the sentinel is in every count. The transform of an $n$-character text is $n+1$ characters over $\sigma+1$ symbols, and the sentinel contributes a run of one wherever it lands. That is why the minimum run count above is two rather than one, and it is a property of this construction rather than of the measure.