A compression tool claims it makes every possible input file smaller — why is that claim impossible?

## What lossless demands of the map A compression scheme is a pair of procedures, `compress` and `decompress`, over finite bit strings. Calling it **lossless** is a promise about every possible input, not about a test corpus: for any input `x`, `decompress(compress(x))` gives back `x` bit for bit. That one promise fixes a structural property of `compress` before any code is written. - If two different inputs `x` and `y` ever produced the same output, the decompressor would be handed one string and asked to return two different originals. It cannot. - So `compress` must be **injective**, one-to-one: different in, different out, always. - Injectivity is not an implementation choice that a cleverer author could avoid. It is what the word lossless means. Everything after that is counting. ## The count Fix a length `n` and ask what can happen to the inputs of exactly that length. 1. There are exactly `2^n` bit strings of length `n`, and every one of them is a legal input. 2. The strings strictly shorter than `n` bits are those of length `0, 1, ..., n-1`. Summing the powers of two gives `1 + 2 + 4 + ... + 2^(n-1) = 2^n - 1`. 3. So the outputs that would count as a win are one short of the inputs that need them, before a single short slot is given away to a shorter input that also wants one. 4. By the **pigeonhole principle**, an injective map cannot place `2^n` items into `2^n - 1` slots. At least one input of length `n` comes out no shorter than it went in. | Input length | Inputs of that length | Strings strictly shorter | Slots short by | |---|---|---|---| | 8 bits | 256 | 255 | 1 | | 16 bits | 65,536 | 65,535 | 1 | | n bits | 2^n | 2^n - 1 | 1 | The margin is always exactly one, which makes the bound look weightless. It is not, because of what comes next. ## Shrinking one input forces another to grow Suppose the scheme shrinks at least one input `x0`, and suppose, for contradiction, that nothing ever grows, so every output is at most as long as its input. Let `n` be the length of `x0`. Every string shorter than `n` bits then maps to a string shorter than `n` bits, and an injective map from that finite set of `2^n - 1` strings into itself is a permutation of it: the short inputs already occupy every short slot. But `x0` also maps into that same set, so its output collides with the output of some shorter string, contradicting injectivity. Therefore: - A scheme that never grows anything is a scheme that never shrinks anything, a relabelling at best. - The moment it wins on one input it loses on another. This is a conservation statement, not a warning about rare edge cases. - **Which** inputs pay is the designer's choice, and every real format makes the same one: lose on inputs that look like uniform noise, win on the structured inputs people actually store. ## The honest version of the claim - *'Shrinks event logs by eight to ten times'* is a claim about a corpus. Checkable, usually true, and no counting argument touches it. - *'Shrinks any file'* is a claim about the whole input space. False by counting, and no benchmark is needed to refute it. - *'Shrinks its own output again'* is the recursive form of the same false claim. Each pass is injective, so iterating would funnel every distinct input into a handful of short strings that cannot be told apart. - *'Never grows a file'* is achievable only by never shrinking one. What a real format offers instead is a **bound** on growth: emit the original bytes when coding them would be bigger, and pay only a small block header. ## Two objections worth answering - *'Everything in my archive folder shrank.'* Real files occupy a vanishingly small, highly structured corner of the space of all bit strings, and a coder is built for that corner. The bound says no scheme is universal; it never claimed no scheme is useful. - *'Then how can a lossy coder shrink everything?'* Because a lossy coder is deliberately **not** injective: many inputs share an output and the decoder returns an approximation. The obstruction here is exact reversibility, so giving that up removes it. - *'Could a dictionary shared by both sides fix it?'* No. Fixing a shared dictionary changes which inputs are cheap; the map over all inputs stays injective, and the count is unchanged. ## Why an interviewer asks it The payoff is not the theorem, it is the speed. An engineer meets this whenever a pipeline compresses something that was already compressed, whenever a proposal promises a fixed ratio on arbitrary user data, and whenever someone suggests a second pass to squeeze out more. The counting argument settles all three in one sentence, in a review, without a benchmark: ask what the scheme does with the inputs that do not shrink.