The pointwise otimality of the LZ algorithm - the fact that it beats every other information-lossless finite-state compressor like Huffman encoding asymptotical

The pointwise otimality of the LZ algorithm - the fact that it beats every other information-lossless finite-state compressor like Huffman encoding asymptotically on /every/ string, is an ingenious theorem. For versions of the algorithm (LZ77 in particular), it was open till the late 1990s when Paul Shields settled it. The algorithm is easy, but the analysis of its effectiveness is not at all easy.