4 ms·

There is a limit beyond which you can't compress data any further, called the Shannon limit. Any sequence of bytes is just a number. So if you think of pi as a

There is a limit beyond which you can't compress data any further, called the Shannon limit. Any sequence of bytes is just a number. So if you think of pi as an RNG, then the chances of finding a run of N digits equal to another number with N digits is (1/10) to the power of N, which quickly becomes intractible. In reality the digits of pi are biased, so finding a particular number of N digits is even less likely. It would be easier to search for that number by randomly seeding an RNG then searching the RNG output for the number. Then you could just store the seed+offset, which may be significantly less than the Shannon limit. But since the chance of encountering such a number is (1/256)^N, it quickly becomes impossible. And even if it weren't, the receiver would need to invoke the RNG [offset] times, which will be a massive number of times due to the probabilities involved. So it's not like you could precompute the index: the receiver still needs to compute the answer, which requires just as many computations as the sender. In general, the closer you try to get to the Shannon limit, the more computation that is required. And perfect compression is impossible in practice except in constrained cases, so I'd speculate it requires infinite computational resources.

wging 13y ago
>In reality the digits of pi are biased, so finding a particular number of N digits is even less likely. This is actually not known to be true. In fact, it's conjectured that pi is normal[1]--meaning that we should expect every sequence of digits of a given length to be as likely as any other, no matter what base we're using. So if you know the position at which the string you're interested in appears, you can just 'compress' by giving the location in the binary expansion of pi at which your message appears, and the length of your message in bits. Where this fails, of course, is that you're likely to have to search a long time to find your message in pi, and you're also probably unlikely to be able to express your starting offset in fewer bits than it would take to write your full message. [1] http://en.wikipedia.org/wiki/Normal_number http://en.wikipedia.org/wiki/Normal_number
- sillysaurus2 13y ago
  So pi containing 3.141592653579 is equally likely as pi containing 1415926535797, which is equally likely to contain ABCDEFGHIJKL for every random ABCDEFGHIJKL? Fascinating. Completely impossible to take advantage of, too, but fascinating.
  - dbaupp 13y ago
    If the conjecture of being normal is true, yes.
  - weavie 13y ago
    Hmm.. it would also mean that somewhere in pi there is a sequence of 1 trillion consecutive zeros.
    - judk 13y ago
      http://en.m.wikipedia.org/wiki/Feynman_point http://en.m.wikipedia.org/wiki/Feynman_point
  - p4bl0 13y ago
    > Completely impossible to take advantage of That depends on your goals, to do geeky things it's pretty cool :). I know my birth date (in the "ddmmyy" format) appears at the 262768th decimal of π. By the way this example validates part of the answer of sillysaurus2 to mvleming: I need 6 digits to encode 6 other. Not that good a compression.
  - wging 13y ago
    If pi is normal, and the two strings are of equal length, then yes... not only that, but if pi is normal it's likely that each appears infinitely often. By the way, sorry to point this out, but after 535 pi actually goes 5358979...
    - Someone 13y ago
      "if pi is normal it's likely that each appears infinitely often." Not likely, _certain_. If there is a sequence S that appears a finite number of times, there is a N such that as never appears after digit N. That, in turn, means that, in the limit of L => infinity, the probability that S appears in the first L digits is zero.
- BuildTheRobots 13y ago
  > So if you know the position at which the string you're interested in appears, you can just 'compress' by giving the location in the binary expansion of pi at which your message appears, and the length of your message in bits. It's a bit tongue in cheek, but this is exactly what piFS[1] does. [1] https://github.com/philipl/pifs https://github.com/philipl/pifs
  - trentlott 13y ago
    That's beautiful.
  - wging 13y ago
    I love his commitment to the joke.
tehwalrus 13y ago
however, we can write a non-infinite computer program that generates arbitrary digits of pi, meaning we can compress it infinitely better than the Shannon Entropy of the actual baseN representation - because it is a special case (most data can't be defined by a few words of mathematical definition).
ot 13y ago
> There is a limit beyond which you can't compress data any further, called the Shannon limit. I think you are confusing things a bit here. The Shannon limit has nothing to do with lossless compression, it refer to communication in noisy channels. What you are referring to is the Shannon entropy, but even that is not actually a lower bound to compression of actual data, because it is defined for stochastic sources. When you have an actual string and you want to compress it, the only meaningful lower bound is the Kolmogorov complexity of the string, that is the size of the smallest program that generates that string. It is of course incomputable, but it is what you would get if you had infinite computing power.
- sillysaurus2 13y ago
  I appreciate you correcting my terminology, but beyond that you haven't actually disagreed with anything I've said. Humans call it either the Shannon limit, or Shannon entropy, or Kolmogorov complexity of a string, or whatever other name humans have come up with for human names. The central point is there is some limit which you can't circumvent through trickery like "find it embedded within pi," regardless of what species you are, or what your species chooses to name fundamental limitations of nature. A program to generate digits of pi is small, and pi embeds every possible string. But generating up to that offset of pi is impossible in practice. And it probably won't net you any savings anyway, since you'll still need to communicate the offset. The offset's length in digits is probably close to the length of the original string (after perfect compression), so it's unlikely you'd be able to circumvent Shannon entropy. But, if you do manage to create a practical way to bypass Shannon entropy, I'd imagine it'll be headline news, along with netting you quite a lot of money.
  - iliis 13y ago
    If you're talking about Kolmogorov Complexity here, you can't really "circumvent" it. Kolmogorov Complexitiy of a string is basically defined as the size of the shortest possible representation of said string. If you manage to"bypass" the Kolmogorov Limit you actually just "lowered" it (well, it alwayws was by definition this low). Your main point is totally valid however. You cannot compress infinitely. A simple proof: For any given N bits you can encode [at most] 2^N different strings. As there exist more than N strings there must be one which cannot be represented by N bits. As N can be arbitrarily large you'll always find strings which cannot be compressed lower than some chosen size. QED.

wging 13y ago

>In reality the digits of pi are biased, so finding a particular number of N digits is even less likely. This is actually not known to be true. In fact, it's conjectured that pi is normal[1]--meaning that we should expect every sequence of digits of a given length to be as likely as any other, no matter what base we're using. So if you know the position at which the string you're interested in appears, you can just 'compress' by giving the location in the binary expansion of pi at which your message appears, and the length of your message in bits. Where this fails, of course, is that you're likely to have to search a long time to find your message in pi, and you're also probably unlikely to be able to express your starting offset in fewer bits than it would take to write your full message. [1] http://en.wikipedia.org/wiki/Normal_number http://en.wikipedia.org/wiki/Normal_number

sillysaurus2 13y ago
So pi containing 3.141592653579 is equally likely as pi containing 1415926535797, which is equally likely to contain ABCDEFGHIJKL for every random ABCDEFGHIJKL? Fascinating. Completely impossible to take advantage of, too, but fascinating.
- dbaupp 13y ago
  If the conjecture of being normal is true, yes.
- weavie 13y ago
  Hmm.. it would also mean that somewhere in pi there is a sequence of 1 trillion consecutive zeros.
  - judk 13y ago
    http://en.m.wikipedia.org/wiki/Feynman_point http://en.m.wikipedia.org/wiki/Feynman_point
- p4bl0 13y ago
  > Completely impossible to take advantage of That depends on your goals, to do geeky things it's pretty cool :). I know my birth date (in the "ddmmyy" format) appears at the 262768th decimal of π. By the way this example validates part of the answer of sillysaurus2 to mvleming: I need 6 digits to encode 6 other. Not that good a compression.
- wging 13y ago
  If pi is normal, and the two strings are of equal length, then yes... not only that, but if pi is normal it's likely that each appears infinitely often. By the way, sorry to point this out, but after 535 pi actually goes 5358979...
  - Someone 13y ago
    "if pi is normal it's likely that each appears infinitely often." Not likely, _certain_. If there is a sequence S that appears a finite number of times, there is a N such that as never appears after digit N. That, in turn, means that, in the limit of L => infinity, the probability that S appears in the first L digits is zero.
BuildTheRobots 13y ago
> So if you know the position at which the string you're interested in appears, you can just 'compress' by giving the location in the binary expansion of pi at which your message appears, and the length of your message in bits. It's a bit tongue in cheek, but this is exactly what piFS[1] does. [1] https://github.com/philipl/pifs https://github.com/philipl/pifs
- trentlott 13y ago
  That's beautiful.
- wging 13y ago
  I love his commitment to the joke.

tehwalrus 13y ago

however, we can write a non-infinite computer program that generates arbitrary digits of pi, meaning we can compress it infinitely better than the Shannon Entropy of the actual baseN representation - because it is a special case (most data can't be defined by a few words of mathematical definition).

ot 13y ago

> There is a limit beyond which you can't compress data any further, called the Shannon limit. I think you are confusing things a bit here. The Shannon limit has nothing to do with lossless compression, it refer to communication in noisy channels. What you are referring to is the Shannon entropy, but even that is not actually a lower bound to compression of actual data, because it is defined for stochastic sources. When you have an actual string and you want to compress it, the only meaningful lower bound is the Kolmogorov complexity of the string, that is the size of the smallest program that generates that string. It is of course incomputable, but it is what you would get if you had infinite computing power.

sillysaurus2 13y ago
I appreciate you correcting my terminology, but beyond that you haven't actually disagreed with anything I've said. Humans call it either the Shannon limit, or Shannon entropy, or Kolmogorov complexity of a string, or whatever other name humans have come up with for human names. The central point is there is some limit which you can't circumvent through trickery like "find it embedded within pi," regardless of what species you are, or what your species chooses to name fundamental limitations of nature. A program to generate digits of pi is small, and pi embeds every possible string. But generating up to that offset of pi is impossible in practice. And it probably won't net you any savings anyway, since you'll still need to communicate the offset. The offset's length in digits is probably close to the length of the original string (after perfect compression), so it's unlikely you'd be able to circumvent Shannon entropy. But, if you do manage to create a practical way to bypass Shannon entropy, I'd imagine it'll be headline news, along with netting you quite a lot of money.
- iliis 13y ago
  If you're talking about Kolmogorov Complexity here, you can't really "circumvent" it. Kolmogorov Complexitiy of a string is basically defined as the size of the shortest possible representation of said string. If you manage to"bypass" the Kolmogorov Limit you actually just "lowered" it (well, it alwayws was by definition this low). Your main point is totally valid however. You cannot compress infinitely. A simple proof: For any given N bits you can encode [at most] 2^N different strings. As there exist more than N strings there must be one which cannot be represented by N bits. As N can be arbitrarily large you'll always find strings which cannot be compressed lower than some chosen size. QED.