NetNews Usenet Archive 1992 #16/NN_1992_16.iso/spool/comp/compress/2764

Internet Message Format | 1992-07-21 | 3.5 KB

Path: sparky!uunet!zaphod.mps.ohio-state.edu!mips!mips!public!rem
From: [e-mail] (Robert E. Maas  [e-mail])
Newsgroups: comp.compression
Subject: Re: PERPETUAL MOTION
Message-ID: <[e-mail]>
Date: 21 Jul 92 18:06:20 GMT
References: <[e-mail]> <[e-mail]>
Organization: BTR Public Access UNIX, MtnView CA. Contact: Customer Service [e-mail]
Lines: 51

<<If you are refering to my outrageous claims, you are missing the
point of my posting.  When people make outrageous claims (e.g., WEB),
people who know that these are outrageous sometimes post refutations of
the claims. My point was to show that some of these refutations are
flawed.>>

I have not seen any counterexample to the primary refutation, that if
you consider all files of size less then or equal to N bits, you have a
certain number of different possible files, and if you compress them
ALL using a single method, either all will end up exactly the same
size, or at least one of them will get larger, or two different files
will compress to the same result meaning the method isn't reversible,
or the method simply will refuse to work on at least one file.

The only proposed counterexample to this I've seen posted or emailed is
one where the file is treated as a binary number and you simply
subtract one, with the claim that once in a while the number of bits
decreases by one. But if you allow any file, the ones with leading
zeroes break the method from the very start (001 and 01 compress to the
same result) unless you retain all leading bits in which case there is
NEVER any reduction because for example 1000 becomes 0111. If you allow
only files with leading ones, then there's one file namely 1 which
can't be compressed because it produces a file not among the set you
are allowing as files. You can always compress a set of files if you
allow compression of a restricted set into a larger set. For example if
you allow only files composed of pairs of matching bits, such as
111100110011110000001100, the you can compress by simply replacing each
pair by a singleton.

But the mathematical proof applies to a fixed definition of "file",
where the claim is that *all* files of that class can be reversibly
compressed, with some getting smaller and none ever getting larger, and
that the result is again in that class. That has been proven impossible
by a simple counting argument where we count the number of different
files larger than and not larger than some critical size (where the
claim is at least one file larger got compressed to not-larger) and
discover the number of smaller-size compressed files is equal to the
number of already smaller-size files plus at least one larger-size file
that became smaller-size after compression, which is a contradiction
because there aren't enough files of smaller-size to equal that larger
number of them after compression. By the pidgenhole principle, either
two of the must be the same (compression not reversible) or one of them
is NOT among that allowed set (compression doesn't work). The
subtract-one trick doesn't satisfy the contition of this mathematical
proof, thus isn't a counterexample. The math stands. For such
rock-solid mathematical proofs, if you think you have a counterexample
probably you didn't understand the mathematical statement and you are
violating the premise in some way. The garbage about subtract-one is an
example of such a non-counterexample. If you have what you think is a
different method which might be a counterexample, you're mistaken, in
my expert opinion.