Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!crdgw1!uakari.primate.wisc.edu!caen!uwm.edu!linac!att!news.cs.indiana.edu!news.nd.edu!mentor.cc.purdue.edu!purdue!haven!adm!smoke!gwyn
From: gwyn@smoke.brl.mil (Doug Gwyn)
Newsgroups: comp.compression
Subject: Re: theoretical compression factor
Message-ID: <15626@smoke.brl.mil>
Date: 29 Mar 91 10:37:02 GMT
References: <1991Mar25.054838.15588@bingvaxu.cc.binghamton.edu> <15098:Mar2512:53:1291@kramden.acf.nyu.edu> <18263:Mar2518:10:4091@kramden.acf.nyu.edu>
Organization: U.S. Army Ballistic Research Laboratory, APG, MD.
Lines: 8

In article <18263:Mar2518:10:4091@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>... and there is no way they can all be compressed to length n,
>as the method in question claims to do.

A shorter argument is to note that any invertible method that maps the
domain onto the range, which is known to map at least one point to a
shorter representation, MUST map at least one other point to a longer
representation.  (I think this was noted somewhere in Knuth.)