Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!ncar!csn!boulder!spot.Colorado.EDU!weverka
From: weverka@spot.Colorado.EDU (Robert T. Weverka)
Newsgroups: comp.compression
Subject: Re: You can't get something for nothing.
Message-ID: <1991Apr11.044640.20930@colorado.edu>
Date: 11 Apr 91 04:46:40 GMT
References: <5351@ns-mx.uiowa.edu> <4931@pink1.UUCP> <1991Apr10.193417.28193@agate.berkeley.edu>
Sender: news@colorado.edu (The Daily Planet)
Organization: University of Colorado, Boulder
Lines: 26
Nntp-Posting-Host: spot.colorado.edu

In article <1991Apr10.193417.28193@agate.berkeley.edu> greg@math.berkeley.edu writes:
>In article <4931@pink1.UUCP> beville@motcid.UUCP (Anthony T. Beville) writes:
>>It seems to me that a scheme using the the digits of
>>and irrational number ( or a repeating rational number, for that
>>matter) might be able to yeild some really good compression
>>ratios.  
>>
>>For any given sequence of bits longer than some number,  
>>merely (!) find a matching sequence deep within the bowels 
>>of pi or sqrt(2) or some fraction or whatever, and represent
>>that sequence with a greatly reduced number of bits.  
>The catch in this particular case is that most sequences of bits
>occur so far down in the expansion of pi or sqrt(2) that you will need
>at least as many bits as you started with to describe their locations.
>----
>Greg Kuperberg
>greg@math.berkeley.edu

A sloppy proof to that effect (but simple)
suppose we want to compress a ten digit number   (decimal)
the chance of matching the first digit to a digit in the pi sequence is 0.1
the chance of matching the first two digits to two digits in the pi seq. is 0.01
the chance of matching all ten is 10^-10.
  so the description of where the ten digit sequence occurs in the sequence
of pi digits is a number of size 10^10 and to store this we need 10 digits.
  --->  no compression   QED  BFD .