= Universal lossless shortening is impossible
Fix $n\geq1$. There is no <injective function> from all length-$n$ <binary strings> to <binary strings> of length strictly less than $n$. There are $2^n$ possible <inputs>, but even allowing the empty string gives only
$$
\sum_{k=0}^{n-1}2^k=2^n-1
$$
possible shorter <outputs>. The <finite geometric series> and <pigeonhole principle> leave at least two <inputs> sharing an <output>, which prevents exact decoding. For $n=3$, eight <inputs> compete for the empty string and the six strings `0`, `1`, `00`, `01`, `10`, `11`.
This counting argument includes any <file header> or other information sent to the decoder. An <algorithm> chosen separately for each <input> must also be identified to the receiver; its description is not free. A useful compressor saves space on some <inputs> while leaving others unchanged or making them longer. <Lossy compression> avoids the exact-recovery requirement by deliberately allowing several <inputs> to share an <output>.
Back to article page
