Compression theory reference?

[bear]

On Tue, 31 Aug 2004, John Denker wrote:

> I emphasize that I am only discussing messages of length N,
> where N is some pre-chosen number.  For concreteness, let's
> choose N=10.

> I repeat my assertion that _if_ XX can compress any string,
> shortening it by one bit, and _if_ you know that the original
> messages each have exactly 10 bits, _then_ any 10-bit message
> can be compressed down to a single bit.

Actually you don't need to take it all the way to the
reductio ad absurdum here.  There are 1024 10-bit
messages.  There are 512 9-bit messages.  You need
to point out that since a one-to-one mapping between
sets of different ordinality cannot exist, it is not
possible to create something that will compress every
ten-bit message by one bit.

Or, slightly more formally, assume that a function C
can reversibly compress any ten-bit message by one bit.
Since there are 1024 distinct ten-bit messages, there
must be at least 1024 distinct nine-bit messages which,
when the reversal is applied, result in these 1024
messages.  There are exactly 512 distinct nine-bit
messages.  Therefore 512 >= 1024.

			Bear

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com