What Is the Theoretical Limit of Lossless Data Compression?

Every lossless compression algorithm — zip, gzip, the codec behind a PNG — is bounded by a limit that was proven mathematically in 1948, decades before any of them existed. No amount of cleverness in the algorithm can beat it, because the limit isn’t about the algorithm. It’s about the information itself.

Shannon’s source-coding theorem

Claude Shannon’s 1948 paper A Mathematical Theory of Communication defined a quantity called entropy: given a source that produces symbols with certain probabilities, entropy measures the average number of bits genuinely needed to represent each symbol, given how predictable or surprising it is. A source that’s highly predictable (say, English text, where “e” is far more common than “z”) has low entropy per symbol; a source of true coin flips has the maximum possible entropy, one bit per flip.

The source-coding theorem states that no lossless encoding scheme can, on average, use fewer bits per symbol than the source’s entropy — and, just as importantly, that schemes getting arbitrarily close to that limit actually exist. It’s tracked in the Registry as Shannon channel capacity and source-coding limits.

Why real compressors don’t hit it exactly

Practical formats trade a little efficiency for speed and simplicity. Huffman coding, used inside many common formats, is provably optimal only when every symbol’s probability happens to be a power of two; arithmetic coding and modern range coders get much closer to true entropy for arbitrary distributions, at some extra computational cost. The gap between a real-world compressor and the Shannon limit is a genuine, measurable inefficiency — and it’s also why compression research hasn’t stopped: better modeling of a source’s true statistics (what real files actually look like) still yields real gains, even though the entropy floor itself hasn’t moved since 1948.

What the limit doesn’t cover

Entropy is defined relative to a specific probabilistic model of the source. Two different files with identical byte content can have different achievable compressed sizes if you’re allowed a smarter model of what “normal” data looks like for that context — general-purpose compressors like gzip use a fairly generic model, while a specialized compressor built for, say, DNA sequences or a specific image format can do meaningfully better precisely because it encodes stronger prior assumptions about the data. The theorem isn’t violated either way; the achievable limit just depends on what you’re allowed to assume in advance.

Why it’s here

The source-coding theorem is one of the oldest and most thoroughly settled entries in the Registry — a hard mathematical limit, not an engineering target, established the same year the field of information theory itself was founded.