Symptom

Someone sends you a pitch deck. The claim is a compression algorithm that reduces any file by a guaranteed ratio, and — this is always the tell — that it can be applied repeatedly. Four gigabytes down to one, then one down to two fifty, and so on until the whole film is a few hundred bytes and a clever decoder.

Or the same thing at a much smaller scale, in your own terminal:

$ ls -l archive.tar.gz
-rw-r--r--  1 you  staff  4823901 archive.tar.gz
$ gzip -c archive.tar.gz | wc -c
4823946

Forty-five bytes bigger. Not a bug, not a bad flag, not a pathological input. You have run into a theorem, and it is the same one that kills the pitch deck.

Statement

Call an encoder $C$ lossless if it is injective: distinct inputs get distinct outputs, which is exactly what you need for a decoder to exist.

If a lossless compressor makes any input shorter, it must make some other input longer.

There is no way to buy the first without paying the second. Not with better modelling, not with more compute, not with a smarter transform.

The quantitative version is the one that ends arguments:

Fix a length $n$. Of the $2^n$ inputs of length $n$, fewer than $2^{1-k}$ of them — that is, fewer than one in $2^{k-1}$ — can be mapped by a lossless compressor to an output of length $n - k$ or less.

For $k = 11$: fewer than one input in a thousand can be shortened by even eleven bits. For $k = 21$: fewer than one in a million can lose twenty-one bits. Those numbers are not about a particular algorithm. They bound every algorithm that will ever be written.

Argument

This is T001 with the boxes chosen well. Pigeonhole says $n+1$ items in $n$ boxes forces two into one box; here the items are inputs, the boxes are outputs, and two items sharing a box means two inputs sharing an encoding, which means no decoder.

Step one: something of length $n$ fails to shrink. There are $2^n$ strings of length exactly $n$. There are

$$2^0 + 2^1 + \cdots + 2^{n-1} = 2^n - 1$$

strings of length less than $n$. If every length-$n$ input compressed to something shorter, we would be mapping $2^n$ items into $2^n - 1$ boxes. Pigeonhole: two collide, injectivity fails, the decoder cannot exist. So at least one string of each length survives uncompressed.

Step two: something actually grows. Step one leaves an escape hatch — maybe a compressor shrinks some inputs and leaves the rest exactly as they are, never growing anything. Close it.

Suppose $C$ is injective and $|C(x)| \le |x|$ for every $x$. Let $A_n$ be the set of all strings of length at most $n$, so $|A_n| = 2^{n+1} - 1$. Since $C$ never lengthens, $C$ maps $A_n$ into $A_n$; since $C$ is injective and $A_n$ is finite, $C$ is a bijection on $A_n$. This holds for every $n$.

Now suppose $C$ shrinks something: $|C(x_0)| < |x_0| = k$ for some $x_0$. Then $C(x_0) \in A_{k-1}$. But $C$ is already a bijection on $A_{k-1}$, so every string in $A_{k-1}$ is the image of some string in $A_{k-1}$ — and $x_0 \notin A_{k-1}$. Two inputs, one output. Injectivity fails.

So a lossless compressor that never grows anything cannot shrink anything either: it is a permutation of each length class, which is to say it is not a compressor. Shrinking and growing come as a pair.

Step three: the counting bound. Outputs of length $n-k$ or less number $2^{n-k+1} - 1$. Inputs of length $n$ number $2^n$. Injectivity means at most $2^{n-k+1} - 1$ of them can land there, so the fraction is under $2^{n-k+1}/2^n = 2^{1-k}$. That is the boxed claim, and it took one division.

Nothing in any of this inspects the algorithm. That is the point, and it is why the argument is worth ten minutes: you can refute a compression claim without reading a line of its source.

Forbids

Recursive compression. If a compressor shrank every input, you could feed its output back in and iterate down to a single bit, and $2^{4,000,000,000}$ distinct files would all decode from one of two starting points. In 1992, WEB Technologies announced DataFiles/16, claiming 16:1 on any input and repeatability down to about 1024 bytes. The product never shipped. It could not have.

Any claim containing the words “including random data”. Random data is precisely the input class the counting bound is about. A compressor that shrinks a uniformly random $n$-bit string with probability better than $2^{1-k}$ for a $k$-bit saving does not exist, and the claim can be rejected before the demo.

Meaningful gains on already-compressed bytes. The forty-five extra bytes at the top of this post are not gzip failing. A well-built compressor detects that it is losing and falls back to storing the data verbatim, and the overhead is the frame around that decision.

Universally beating the current format. “Our codec is smaller than PNG on every image” is a claim about all inputs, and all inputs includes noise. What is achievable, and worth a great deal of money, is being smaller on the images people actually have.

Does not forbid

It does not forbid compression from working. This is the misreading that makes people dismiss the theorem as a curiosity, and it is worth being precise about why they are wrong to. zstd on a directory of JSON logs routinely returns 10:1. That is not a violation and not luck. The theorem says the wins are paid for by losses on other inputs — and those other inputs are overwhelmingly high-entropy strings that no one has ever wanted to store. Real data lives in a vanishingly small corner of the input space, and every practical compressor is a bet that your file is in that corner. The bet is close to free because the losing side of it is a set you will never draw from.

It does not forbid a bounded worst case. A common overcorrection: “so any compressor might blow my file up.” No. DEFLATE has a stored-block type, so gzip on incompressible input costs about five bytes per 64 KB block plus a small header; zstd and xz do the same thing. The theorem guarantees some input grows. It says nothing about how much, and every serious format caps the damage at a fraction of a percent by refusing to compress when compression is losing. The growth is real, mandatory, and negligible.

It does not forbid lossy codecs from doing much better. JPEG, Opus and AV1 are not counterexamples and not cheating. They are not injective — many distinct inputs decode to the same output, which is the entire deal — so they are simply outside the theorem’s scope. Anyone citing MP3 as a refutation has misread which word in “lossless compressor” is load-bearing.

It does not say general-purpose compressors are near optimal. This one costs teams real money. “Information theory says you can’t do much better than gzip” is false, and the theorem being invoked says the opposite: since all the gains come from matching the input distribution, a compressor that knows your distribution can beat a general one by a lot. FLAC beats xz on audio. Parquet with dictionary and run-length encoding beats gzipped CSV by an order of magnitude on the same table. Brotli ships a built-in dictionary of common web strings because it knows what it will be asked to compress. Choosing the input distribution is the whole game, and the theorem is what tells you that.

It does not cover a corpus. Deduplicating storage — Git packfiles, restic, ZFS — often reports ratios that sound impossible. They are not compressing one string; they are noticing that the same block arrived a thousand times. The theorem is about a single injective map on single inputs, and says nothing about exploiting repetition across inputs.

Boundary

The bound is tight and there is no clever encoding that evades it. What lives just outside:

  • Drop injectivity. Lossy compression leaves the theorem’s hypotheses entirely, which is why it can offer guaranteed ratios and why it is what you use for anything perceptual.
  • Fix a distribution. Once inputs are drawn from a known source rather than adversarially, the question changes from “which inputs shrink” to “what is the expected length”, and the answer is exact: Shannon entropy, in T018. This theorem says a universal win is impossible; entropy says exactly how large the non-universal win is.
  • Move bits out of band. Shared dictionaries — Brotli’s, zstd --patch-from, HTTP/2’s HPACK table — genuinely shrink the transmitted bytes. The cost has not vanished; it has been paid once, in advance, by both sides. The accounting still balances.
  • Ask about a specific string instead of all of them. The shortest program that outputs a given string is its Kolmogorov complexity (T023). It gives the exact incompressibility of this file rather than a bound over all files, and the price is that it is uncomputable.
  • Amortize across a corpus. Delta encoding and content-addressed deduplication change the unit of work from one string to a collection, which is a different problem with different limits.