“Lempel-Ziv: a ‘1-Bit Catastrophe’ but Not a Tragedy”, Guillaume Lagarde, Sylvain Perifel2017-07-13 (adversarial examples (AI), compression)⁠:

The so-called “one-bit catastrophe” for the compression algorithm LZ’78 asks whether the compression ratio of an infinite word can change when a single bit is added in front of it.

We answer positively this open question raised by Lutz and others: we show that there exists an infinite word w such that ρ_sup(w) = 0 but ρ_inf(0w) > 0, where ρ_sup and ρ_inf are respectively the lim sup and the lim inf of the compression ratios ρ of the prefixes.

To that purpose we explore the behavior of LZ’78 on finite words and show the following results:

\n

- There is a constant C > 0 such that, for any finite word w and any letter a, ρ(aw) ≤ C√(ρ(w) log |w|). Thus, sufficiently compressible words (ρ(w) = o(1⁄log|w|)) remain compressible with a letter in front;

\n

The previous result is tight up to a multiplicative constant for any compression ratio ρ(w) = \U0001D4AA(1⁄log|w|). In particular, there are infinitely many words w satisfying ρ(w) = \U0001D4AA(1⁄log|w|) but ρ(0w) = Ω(1).