The Burrows-Wheeler transform (hereafter called BWT) has had
a profound impact on a myriad of algorithmic fields in Computer Science.
Simply put, the BWT preprocesses an input text~$T$ by a reversible
transformation---the result is then easily compressible by other simpler
encoding methods. The BWT highlights (among other things) that a
series of encoders may be more effective than a one-pass compression
algorithm. The BWT has shown remarkable evidence to that effect,
especially in practice: it is at the heart of the \texttt{bzip2}
algorithm, which has become a mainstream data compression tool.

In this talk, we will present the best known lower bounds on the
encoding length of the BWT. For a text~$T$ of $n$ symbols drawn from an
alphabet~$\Sigma$ ($|\Sigma| = \sigma$), we state bounds in terms
of the modified $h$th-order empirical entropy of the text~$H_h^*$. In
particular, we establish a lower bound of $nH_h^* + M(T,\Sigma,h)$ bits,
where $M(T,\Sigma,h)$ denotes the number of bits required to store the
empirical statistical model for contexts of order up to~$h$ appearing
in~$T$.

We define a (non-trivial) class of infinite familes of texts called
\emph{$\delta$-resilient texts} for which our lower bound holds. Let
$\delta \leq 1$ and $k$ be positive constants such that
$k = O(\polylog(n)) > \lceil 1/\delta \rceil$. Let
$d = \lceil 1/\delta\rceil$. Our lower bound states that there
exists an infinite family for a chosen $k$ and $\delta$ such that for
any $n$-long text in that family, $M(T,\Sigma,h)$ is
$k \log n - O(k\log (dk))$. For our family of texts,
$k = (\sigma-1)/2$. This bound confirms Manzini's
conjecture from 2001 that the BWT cannot be compressed to just
$nH_h^* + \log n + O(\sigma^{h+1}\log \sigma)$ bits.