Compression theory reference?

Matt Crawford crawdad at
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

More information about the cryptography mailing list