A compression tool claims it makes every possible input file smaller — why is that claim impossible?
answer
- reversible means one-to-one
- count the outputs, not the files
- 2^n inputs, one fewer short strings
- pigeonhole: some input cannot shrink
- shrink one, expand another
basics
~20 sLossless compression must be reversible, so distinct inputs need distinct outputs. There are more n-bit inputs than shorter strings, so no map can shrink them all; a scheme that shrinks one input must expand another.
solid answer
~40 sLossless means `decompress(compress(x))` returns `x` for every input, which forces `compress` to be injective: two different inputs can never share an output, or the decompressor would not know which original to return. Now count. There are `2^n` inputs of exactly `n` bits, but only `2^n - 1` strings shorter than `n` bits in total, adding up all lengths from `0` to `n-1`. Pigeonhole: those inputs cannot all land on distinct shorter outputs, so at least one of them does not shrink. Stronger still, if the scheme does shrink some input, then some other input must come out strictly longer, because the short outputs it consumed are no longer available to the shorter inputs that would otherwise use them. The honest claim is always 'shrinks the files you actually have', never 'shrinks everything'.
go deeper
Recall that lossless means exactly reversible and that reversibility forces different inputs to different outputs. From there the one-line count of inputs against shorter strings is the whole answer.
Do the count out loud: 2^n inputs of length n against 2^n - 1 strings shorter than n, then explain why a scheme that shrinks one input must expand some other one.
Use it to close a claim in review without benchmarking: ask what the scheme does with the inputs that do not shrink, and what the format emits for them.
Treat 'compresses anything' in a design or procurement claim as a category error, and judge proposals on the input distribution they actually target and the growth bound they offer.
## 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.
- Someone proposes compressing the compressed output again and again until the archive is one byte. Refute it in a line.Each pass is injective, so repeating it would eventually funnel all `2^n` distinct inputs into a handful of short strings, and no decoder could tell them apart. In practice the second pass sees near-uniform bytes, finds no skew and no repeats, and returns the same payload plus another layer of framing.
- Does the counting argument also limit how badly a scheme can expand an input?No. It forbids universal shrinkage but says nothing about the size of the loss; a naive scheme could double its input. Formats impose that limit themselves by emitting a block's original bytes whenever coding them would be larger, so the worst case becomes the small header on that block.
- Why does the argument not rule out a lossy coder that shrinks every input?Lossy coders are not injective: many inputs map on purpose to the same output, so the pigeonhole obstruction disappears. The cost moves to the reconstruction, which is an approximation rather than the original, and the relevant bound becomes rate against fidelity instead of a count.
A cloakroom with 256 coats and 255 numbered hooks. You can hang the coats however you like, but one of them has no hook of its own, and you find out only when everybody tries to collect the right coat back.
saying these in an interview costs you the question
- Says a smarter algorithm will eventually shrink every possible file
- Thinks the limit comes from CPU or memory rather than counting
- Believes feeding the output back in keeps shrinking it
- Says the same counting bound also stops lossy coders shrinking everything
- Offers a folder where every file shrank as a counterexample