Compression theory reference?

[Matt Crawford]

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