[CraigD]

In 1968, in the SF story “Gold at the Starbow's End" (which was expanded in 1983 to become the novel “Starburst”), the late Fred Pohl makes an interesting mathematical conjecture.

With its fictional context parenthesized, here is what I term “the Starburst Conjecture”:
1) A lengthy, meaningful text is written in everyday, understandable English. (the text, presumable several tens of pages long, explains how to solve many pressing engineering problems, including controlled, small-scale fusion power)

2) This text is encoded into a large integer using an easily decodable scheme (“godelization” – see below)

3) This integer is written as an expression using ordinary arithmetic operators. The expression is much shorter than the original text. ( The “Starburst number”, (3.875*12^26)! + 1973^854 +331^852 + 17^2008 + 3^9606 + 2^88 – 78, where “!” is the factoral unary operator, e.g: 5! = 1*2*3*4*5 = 120)

According to accepted information theory, this may be impossible. Roughly stated, information theory says that an arbitrary random integer cannot be “compressed” into an shorter integer enough that the length of the compressed integer + the length of the program required to decompress it back into the original integer are less than the original integer. This is commonly called “the Compression Challenge”, and has withstood decades of attempts to refute it. It’s important to note that the Compression Challenge doesn’t say that no integer can be compressed, just that one with a lot of randomness – and thus, a lot of information, can’t. For example, the integer 10^(10^100), a huge integer, can obviously be described by this very short expression, and, like the Starburst Number, decompressed using a program consisting of just the rules of arithmetic. The integer in the Starburst Conjecture is not an arbitrary random number – the author can carefully compose and tweak the text and encoding scheme that generates it - but neither is it as “easy” number like 10^(10^100).

Here’s my challenge to number-crunching-inclined Hypographers: prove the Starburst Conjecture by providing an example of any meaningful English text, encoding scheme, and expression satisfying the rules. Strange spacing, punctuation, capitalization, and spelling is OK. All that’s required to win is that the final expression be many times shorter than the original text. Of course, a formal proof or disproof wins, too.

PS:
1) Nobody claims that Pohl’s “Starburst number” can really be expanded into a document containing the secret of controlled fusion, or any readable text – it’s fictional, intended for illustration purposes only. This is not a challenge to discover any hidden information in the number (3.875*12^26)! + 1973^854 +331^852 + 17^2008 + 3^9606 + 2^88 - 78.

2) “Godelization” is a symbol-to-integer encoding scheme. A strength is that it can be used with any number of symbols, which you don’t have to know in advance. A weakness is that it quickly generates very large integers. I neither recommend not don’t recommend using it for this challenge, but include it in this PS to provide background on Pohl’s original example.

It works as follows:
1. Beginning with 1, assign a number to each symbol used. For example, 1=SPACE, 2=A … 27=Z, 28=PERIOD is a valid assignment. Any order can be used, and new symbols may be added as needed.
2. Initialize G = 1
3. For the first symbol, multiply G by the first prime raised to the power of the symbol (G=G*2^symbol).
4. Repeat for the 2nd symbol and prime, and so on, until all symbols in the message have been encoded.
Example: “HELLO WORLD” encodes to 2^9*3^6*5^13*7^13*11^16*13*17^24*19^16*23^19*29^13 *31^5 = 16201674618135353117026999186798460736594220862673 25990498526101998386676287418792874442737803105156 98642043413401302718344893318901988199466356250000 00000

[Turtle]

___The challenge is dealt & I meet the small blind. Now I need to firm up a few points before the flop. (Forgive the obscure poke references; it's late).
___First if we may, I call for a set message length in characters, rather than the general "tens of pages". A double space page is rougly 250 words & say an average word is 5 letters = 1250 characters. Since spaces count, add 250 for 1500 characters per page. Now let's use 20 pages for a message length of 30,000 characters for encryption.
___Sooooo tired...Stopping here for the flop.

[CraigD]

Originally Posted by CraigD

Here’s my challenge to number-crunching-inclined Hypographers: prove the Starburst Conjecture by providing an example of any meaningful English text, encoding scheme, and expression satisfying the rules. Strange spacing, punctuation, capitalization, and spelling is OK. All that’s required to win is that the final expression be many times shorter than the original text. Of course, a formal proof or disproof wins, too.

Originally Posted by Turtle

First if we may, I call for a set message length in characters, rather than the general "tens of pages".

Please feel free to use a starting text of any length, the only restriction being that it is something that a reasonable English-speaking reader would recognize as meaningful. Let’s take that to imply a minimum length of about 250 characters.

Let “the final expression be many times shorter than the original text” be taken to mean “the final expression be less than 1/5 the length of the original text”, but let’s be flexible with this requirement. I’d be excited to see any result where the final expression is even about the same size as the starting text.

An important freedom is that the starting text may be altered – spaces or nonsense characters inserted, words strangely capitalized, slightly misspelled, etc. – to yield an encoded integer better suited for reduction to a shorter expression.

I suspect this is a very hard challenge, so let’s impose a minimum of rules.

[Turtle]

___ Just rying to get my shell around it. Do I properly understand that besides the 1/5 which is the compressed message, you then add the characters in the encryption program too?
___Another question I have; how important is the difference here between the information in the message & the message itself?
___I seem to recall an anecdote of similar circumstance to this; a professor assigned a hard problem in compression to a bunch of young students who didn't know it was a hard problem. As it turned out, one of these "naive" young guys produced a solution by using a binary probability tree, thus solving a long standing problem.
___I'm all in!

[CraigD]

Don’t worry about the size of the encoder/decoder program – just assume it’s trivially small compared to the original text. Just don’t cheat by having a “decoder” that can produce the starting message with little or no input.

The difference between the common-sense information in the starting message and its formal information (entropy) is unimportant. The message can contain lots of extra “noise” information, as long as a reasonable reader can distinguish the noise from the “signal”. For example: “Mary had a little lamb”; “mARy haD a LiTtLe lamB”; and “mary … had …… a litle … lamb” are all legitimate.

[Turtle]

___Acknowledged. To the bat cave! Er... to the turtle cave.

[Turtle]

___In rereading the original description, "It’s important to note that the Compression Challenge doesn’t say that no integer can be compressed, just that one with a lot of randomness – and thus, a lot of information, can’t"; I have to say I agree.
___For example, I believe it's impossible to compress anomalous Strange Numbers & their ilk.
___In any case the written numerals , which we casually refer to as numbers, themselves constitute a compression algorithm for representing amount. Staying with position based systems using zero, the higher the base you use, the fewer positions required to encode the amount. Conversley, the lower the base, the more positions required.
___Just thinking out loud

[Turtle]

Originally Posted by CraigD

In 1968, in the SF story “Gold at the Starbow's End" (which was expanded in 1983 to become the novel “Starburst”), the late Fred Pohl makes an interesting mathematical conjecture.


Here’s my challenge to number-crunching-inclined Hypographers: prove the Starburst Conjecture by providing an example of any meaningful English text, encoding scheme, and expression satisfying the rules. Strange spacing, punctuation, capitalization, and spelling is OK. All that’s required to win is that the final expression be many times shorter than the original text. Of course, a formal proof or disproof wins, too.

___I saw this thread mentioned elsewhere & thought to revisit it. I have in mind something Katabatak. Cogitating.

[Turtle]

Something new in this perhaps, by way of a fractal compression scheme developed -as best I can tell - by Prof. Ian Stewert. I heard it described in a recent PBS show entitled Colours of Infinity, hosted by Arthur C. Clarke. In short, a given image (your information) is subjected to an analysis that gives a fractal equation specific to that image. Then, the equation is given back the initial conditions and it generates missing detail. For a spacecraft for example, this means less data is required without loss of detail and so image compression. Or so they said...
Here is a link to Ian's homepage, and a Google of 'Prof. Ian Stewart' turns up many resources to his work.
Ian Stewart Home Page v 2.1