1

There has been a discussion about PI-Indexing and irrational number theory here.

Now suppose you want to use indexes of PI to store information (file storage). To get around the fact that the indexes will be bigger than the files you're storing, you use tree of indexes - PI at a certain value is a pointer to PI at a another value.

Here the author writes:

By the pigeonhole principle, no matter how fast you can calculate pi, you cannot actually use this to compress data. The index to relevant sequence is on average >= the size of the data to be stored.

Now I'm looking at the pigeonhole principles - and I'm not connecting to why it says this is not possible. (It sounds plausible).

My question is: Why does the pigegonhole principle tell us that PI-indexing is not possible?

EDIT: A related example - here is an example of a filesystem that stores files as locations in PI.

hawkeye
  • 1,121
  • 8
  • 14
  • 1
    Related: http://math.stackexchange.com/questions/1163457/prove-that-every-lossless-compression-algorithm-must-result-in-increasing-the-fi. – Martin R Feb 28 '17 at 08:06

1 Answers1

0

It's explained in the first sentence of the Wikipedia entry:

The pigeonhole principle states that if $n$ items are put into $m$ containers, with $n>m$, then at least one container must contain more than one item.

So while you might be able to compress data using a clever PI-indexing algorithm, you will not be able to de-compress it to the original data, as one piece of compressed data might correspond to more than one de-compressed piece of data.

Klangen
  • 5,075
  • Thank you @Klangen. The Wikipedia entry doesn’t tell me anything about the compression method. You explanation seems to suggest that an optimisation might be used for duplicate pieces of data. I don’t see why duplicate data would hold up decompression. Your answer then suggests I might use a one-way decompression method, I’m not sure why I’d do that. – hawkeye Jun 10 '19 at 22:18
  • @hawkeye Perhaps this post (on CS.Stackexchange) will interest you: https://cs.stackexchange.com/questions/44594/data-compression-using-prime-numbers It explains the same principle, but in another context – Klangen Jun 11 '19 at 05:41