# Compression theory reference?

Tue Aug 31 18:04:59 EDT 2004

```On Aug 31, 2004, at 14:50, Victor Duchovni wrote:

> This is a question in elementary finite set theory, not computer
> science
> (whatever that is :-). All proofs will involve some mathematics. The
> above is I think simpler than your original argument and is the
> simplest
> I can come up with...

I think Hadmut was looking for an authority that would be respected by
the CS department he is dealing with.  It's a sad state of affairs when
they will accept authority over proof.  However, I can give what I
think is a simpler proof, using only high school math.

Assume that some invertible function f() turns no input message into a
longer output message.

We can prove that it also does not make any message *shorter*, and
hence is not a "compression" function after all.

In particular, f() turns every one-bit message into a one-bit message.

Suppose f() preserves the length of all n-bit messages, for 1 <= n <=
N.  (This is already the case for N=1.) What does f() do to a message M
of N+1 bits length?  By assumption, f(M) is not N+2 bits or longer.
But all output messages of N bits or less are the result of some input
of N bits or less and hence cannot be f(M).  So by elimination, f(M) is
N+1 bits long.

By mathematical induction, f() preserves the length of every message.

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

```