[16056] in cryptography@c2.net mail archive
Re: Compression theory reference?
daemon@ATHENA.MIT.EDU (Matt Crawford)
Wed Sep 1 08:39:22 2004
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Tue, 31 Aug 2004 17:04:59 -0500
From: Matt Crawford <crawdad@fnal.gov>
In-reply-to: <20040831195055.GN30677@piias899.ms.com>
To: Victor Duchovni <Victor.Duchovni@MorganStanley.com>
Cc: cryptography@metzdowd.com
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@metzdowd.com
