Interesting Links for 02-10-2012

[andrewducker]

• Scottish Oyster Card announced
  (tags: scotland travel transport )
• Venues with under 200 people will no longer need a license for unamplified music.
  (tags: viaFanf music libdem law uk )
• California bans teenage gay conversion therapy
  (tags: lgbt teenagers california )
• All "smart" ways of calculating pi are useless.
  (tags: mathematics pi )

Comments

[simont]

No, that sounds about right to me. Generally, you expect that a rational approximation and a decimal approximation to the same value using the same number of digits will be about as accurate as each other (plus or minus a digit or so for fiddly edge cases), simply on the grounds that you've got about the same number of possible representations covering the same amount of space. Equivalently, if it worked any other way then you'd have a magic compression algorithm of the form "express your file as a decimal, convert to a fraction, aha! it takes fewer digits" or vice versa, and we know magic compressors can't exist by the obvious counting argument.

It's slightly more subtle than there being no pattern to the digits, in that some numbers with no obvious digit pattern can be encoded cheaply. (Proof: just evaluate small fractions until one doesn't have an obvious pattern, and you've found one! E.g. if you happened to want to approximate 0.052631578947365, you'd happen to be in luck, since it's extremely close to 1/19.)

A useful representation for these purposes is to write your target number as a continued fraction. Numbers which have an unusually good rational approximation will also have an unusually large term early on in their continued fraction representation. Pi's continued fraction starts off [3;7,15,1,292,1,1,1,2,1,3,1,...], and that 292 (which is quite big as these things go) indicates that the approximation you get by truncating just before it will be particularly good. And that's [3;7,15,1] = 3+1/(7+1/(15+1/1)) = 355/113, which is the same one that the post you link to spotted as being (barely) above the threshold of usefulness.

A couple of curiosities related to this: the number which is least well approximated by rationals (in the sense of how big the numerator and denominator need to be to get a given accuracy) is the one all of whose continued fraction terms are 1, i.e. [1;1,1,1,1,...], which works out to be the golden ratio φ = (1+sqrt(5))/2. And a number which is especially well approximated by certain rationals (and wasn't deliberately constructed for that purpose) is the Champernowne constant, made by writing "0." followed by the concatenation of the decimal representations of all the positive integers. You can find its extremely silly continued fraction here.

[nancylebov]

Thank you. I think I understand that.

I also looked at continued fractions a bit, and it's exceedingly weird that some of them shake out into simple patterns. Pi remains intractable, and I begin to admire its stubbornness.

Is there anything interesting about the fact that some uncompressible numbers can be expressed as simple concepts?

[simont]

I'm inclined to say 'no, not really', on the basis that there's a very wide range of wildly different ways to express a mathematical concept that defines a real number, and a lot of those concepts have nothing much to do with rationals; so it's not greatly surprising that some of the numbers you can express that way indeed turn out to have no particular relation to rationals. I think I'd find it a lot more surprising if every real number interesting to mathematicians did turn out to be more than averagely compressible (or, indeed, if all of them turned out to share any other specific property).