Calculus of Probabilities in the game of “co-incidence”

Here is a paper by Euler that is very readable to regular people. (Well, at least to me.) Calculus of Probabilities in the game of co-incidence The probability of no coincidence is 1/e = 0.368 in the limiting case. Updated link to paper

Pi in sexagesimal

III
        VIII    XXIX    XLIV    N       XLVII
        XXV     LIII    VII     XXIV    LVII
        XXXVI   XVII    XLIII   IV      XXIX
        VII     X       III     XLI     XVII
        LII     XXXVI   XII     XIV     XXXVI
        XLIV    LI      L       XV      XXXIII
        VII     XXIII   LIX     IX      XIII
        XLVIII  XXII    XII     XXI     XLV
        XXII    LVI     XLVII   XXXIX   XLIV
        XXVIII  XXXVII  LVIII   XXIII   XXI
        XI      LVI     XXXIII  XXII    XL
        XLII    XXXI    VI      VI      IV
 

Sixty "digits" of pi, in base sixty (sexagesimal), in Roman numerals, as a tribute to Archimedes and other ancient mathematicians. Note that "N" stands for nihil or nullus, or zero. In modern notation pi = 3 units 8 minutes 29 seconds + 44/216000 + 0/60^4 + 47/60^5 + 25/60^6 + 53/60^7 + 7/60^8 + 24/60^9 + 57/60^10 + ... I have a hundred million sexagesimal digits lying around if anyone wants it.

The Ten Greatest Mathematicians

The Ten Greatest Mathematicians There's a break between the top 4 (Gauss, Archimedes, Newton, Euler) and the rest of the field. I'd put Euler as #1, though, and Newton at 4 or even lower. Newton invented calculus, yeah, but it would have been invented without him.

Broadcasting to Aliens

If earth wanted to broadcast to the rest of the universe, what message should we send? I'll get to that later. A more basic question is, at what bit rate should we send it? Ethernet (10 megabits per second)? No way! Because we are transmitting at such low power, compared to, say, pulsars, our sun, supernovae, quasars, other far more advanced alien civilizations, etc., we would need to broadcast at extremely low bit rate in order for the aliens to have a remote chance of picking out signal over noise. I don't think this has been done before: at least not at the bit rates I'm thinking about. I'm thinking about 1 bit per year, which works out to (see previous post) 31.7 nanobits per second. Yeah, that's really slow. One bit per year also has the helpful property that the we will broadcast the bit through the whole sky over the course of a year, although hopefully we won't be using such a narrow beam that it won't already broadcast to the whole sky over the course of a day. The 1974 Arecibo broadcast was 10 bits per second. SETI@home does not search for alien signals at such a low bit rate -- it would take them on the order of a century worth of observations to detect it through FFT. Of course, the aliens receiving our broadcast will also have to listen for a century. On the SETI@home website, they say that the lowest frequency they can search for is 0.075 Hz, corresponding to (I think) the field of view of the Arecibo telescope as it slides underneath the rotating sky. Assuming one bit per cycle, then that is 2,366,769.4 times a higher bit rate than 1 bit per year. Having decided what rate to broadcast, the next question is what should we broadcast? We need something that is not a natural-looking signal. But at one bit per year, it can't be too long a message or we will forget what we are saying, and governments and civilizations will tumble and fall in the course. So I'll ballpark it to 20-40 bits; that is, repeat the message every twenty to forty years. The alien SETI researcher (or perhaps their military strategist plotting the annihilation of us) will conclude the signal has a one-in-a-million to one-in-a-trillion chance of being natural (2^-20 to 2^-40). So, thirty bits to prove our intelligence. What should they be? Here are some ideas. A mathematical constant, for example, pi. But pi itself got me thinking: will an alien civilization actually use 3.1416 as their version of pi? Perhaps not: 2pi=6.2832 is also a very reasonable constant. It is the period of sine and cosine, the ratio of the radius to the circumference. sqrt(pi)=1.7725 appears in various formulae for the volumes of higher-dimensional spheres and in probabilities, for example in the normalizing term of the error function. Real numbers greater than one pose a problem because it's not clear how to encode the decimal point. Maybe we can broadcast just the portion after the decimal point, or the inverse (1/x) of the constant. Two more constants "of the ancients" are the sqrt(2)=1.414 (and 1/sqrt(2)=0.7071) and the golden ratio phi=0.618. They nicely fall between zero and one. There are plenty of other mathematical constants that aren't pi to choose from. e=2.71828 is the next most famous, and it doesn't have the problems of 2e or sqrt(e) being plausible constants as well. 1/e=0.3679 is an important constant in probability -- the limiting probability of success of repeating a gazillion times an experiment that has a one-in-a-gazillion chance of succeeding: a very apt constant to be sending through space. By choosing the constant, we as a civilization can show off our level of mathematics. pi says we've advanced as far as Archimedes: basic geometry. The sqrt constants say we know algebra. e says we know calculus. Yay us. (I'm generalizing of course, after all, what is the difference between "basic geometry" and "algebra". Uh...) There is another constant that also says we know calculus, and calculating it to high accuracy is quite difficult. This is the Euler-Mascheroni constant γ = 0.577, or the "left-over" from subtracting log from the harmonic series. This constant is pretty obscure and difficult to calculate that we're tooting our own horn in broadcasting it. It's difficult to calculate: using the naive formula would require billions of terms for 30 bits of accuracy. But Euler himself calculated it to 16 decimal places (53 bits), obviously using some other formula. Euler was a calculating machine, though! Going further into obscure mathematical constants, how about Khinchin's Constant == 2.685 or the Feigenbaum Constant == 4.669 ? Brun's constant = 1.902 in fact is only known to today 9 digits (29 bits) (see link). Human mathematics has taken a detour through the Riemann Zeta function to get those nine digits, so it's pretty high math. The sum of the reciprocals of the midpoints of the twin primes, i.e., 1/4 + 1/6 + 1/12 + 1/18 + 1/30 + 1/42 + 1/60 + ... does converge to a nicely transmittable value between zero and one (by the Harmonic-Mean Arithmetic-Mean inequality), but I don't know if the same detour for Brun's constant can get us 30 bits. Instead of broadcasting a fractional constant, we can broadcast an integer. Sadly there won't much agreement. The best integer is 78557, which is conjectured to be the answer to the Sierpinski problem, but it's thought to be at least a decade until the number is proved. Or we could go with the Mersenne exponent of month (currently 24063583) which is the pinnacle of human computing. Unfortunately these numbers are 17 and than 24 bits respectively -- quite small. The largest Mersenne prime is likely to grow, a lot, in the course of the centuries of our broadcast. In the realm of constants we haven't calculated yet, how about the probability of a random Turing machine halting? Unfortunately, current theory states that expected to never know even one bit of that number. Instead of mathematical constants, how about a physical constant? The glaring example of course is the fine structure constant α (alpha) = 0.007297. It has a nice bit of zero padding at the front so that the aliens will be able to figure out where in the loop our message begins. Kind of like pi, sqrt(alpha) is also a plausible value. Through much cleverness by the experimental physicists, we now (barely) know the constant to a sufficient number of bits. A tiny possible fly in the ointment is that we are not sure that the constant is even constant! If the constant changes over the billions of years the message flies through space, they'll be some pretty confused aliens on the receiving end. Finally, here's an idea that's not so complicated. The problem with all these constants mentioned above is that each year one needs to "look up" whether to turn on the bit. How about something calculated from the year itself? Counting to 8 in binary takes up 24 bits: let's try to transmit the sequence 000001010011100101110111. This requires only some simple instructions mumble mumble divide the year by 24 and keep the remainder mumble mumble. Even better yet, Chinese zodiac mumble mumble! The reason an easy-to-calculate sequence is good is because we don't want to tie up a radio transmitter for centuries broadcasting. Instead the population of entire planet can participate, but we can't expect the entire population to have the binary value of (say) the fine structure constant handy. But a simple rule, like count to 8 in binary, people can memorize. On on-bit years, do something; on off-bit years, don't do it. For example, leave the backyard light on for the aliens. It doesn't even have to be something done continuously through the year. A crazy idea might be to only hold the World Cup on years with on-bits. The world emanations of TV being watched would make a recognizable pattern. Maybe people can vote: (a) 000001010011100101110111 (counting to 8) (b) 00000001110111100011110101 (fine structure) (c) 100001101001010101110011111100 (1/Brun) (d) 0101111000101101010110001101100010110100 (1/e) Not that I'll care about your votes when I become dictator of the world and institute alien broadcasting on the populace...

Slow cycle times

One hertz (Hz) is one cycle per second.

1 / second  = 1.000 hertz
1 / minute = 16.7 millihertz
1 / hour = 278 microhertz
1 / day = 11.6 microhertz
1 / week = 1.65 microhertz
1 / month = 380 nanohertz
1 / year = 31.7 nanohertz

Fitt's Squared Law

Which is easier to click: a 30-by-30 square or a 900-by-1 line? Clearly the square. However by Fitt's Law, they both have the same area. Thus I introduce "Fitt's Squared Law", which states that the time to acquire a target is monotonically decreasing in the size of the incircle (largest inscribed circle) of the target. So, a 33.8 pixel diameter circle is even easier to click than a 30-by-30 square. It is also pi(33.8)^2 = 900 pixels in area. Fitt's Squared Law has great implications for web browsers because all links of text are always short and wide, instead of square-like. At the very least, it asks for the Web browsers to think of pages a composed of boxes (inside boxes, and so forth), like the way TeX does. They may already do that--Mozilla DOM Viewer shows that off. However in the bigger picutere, we may want text swooping smoothly over and under circular-shaped links in text kind of like air around an airfoil. I hope to describe more in detail what web browsers should look like in the future.

AES and the One Time Pad

The traditional way to use a one-time pad (OTP) is to XOR the pad data with the plain text. However, if an attacker gets a hold of the plaintext and the ciphertext, and if you are stupid enough to accidentally encrypt using the same "one-time" pad data twice, then the second encryption can be trivially broken. So instead of using XOR as your "cipher", use AES, and use the one-time pad as key material. That is, take 128 bits of plaintext and 128 bits of OTP as key to produce one block of ciphertext. For the next block, take the next 128 bits of OTP as key and so forth. Even after an attacker gains the plaintext and ciphertext, he still has to calculate f(PT,CT)->Key(s) which is conjectured to be hard. So, my AES decoder ring will also have a CD-ROM which can input a one-time-pad.

Parentheses Lifting

The basic problem in Lisp-like languages is stuff gets buried inside many levels of parentheses, which screws up code-indenting. Suppose we have a function that takes 4 args, of which the last arg is often complex containing another instance of foo.

(foo bar bar bar (foo bar2 bar2 bar2 (foo bar3 bar3 bar3 (foo ... ))))

We want to transform ("lift") so that it looks like this

(lift (foo bar bar bar) 
      (foo bar2 bar2 bar2) 
      (foo bar3 bar3 bar3)
      (foo ...))

This would be all well and good if it weren't for the fact that the embedding has to span multiple levels of parens: (foo xa1 xa2 (bar ya1 (foo xb1 xb2 (bar yb1 ...)))) You begin to need templates (or code!) describing exactly how to perform the lifting you want this time. *** The only case I really care about are :case statements in parenthesized haskell anyway, so I'll apply a one-time band-aid instead. It's all interesting in general in theory...

AES has not been broken. This time.

Google Groups: View Thread "AES partial collision (and AES Challenge)"

Sports Predictions

the end-of-the-year prediction column The prediction about the Pats and the Connecticut NCAA sweep is pretty neat. I'm also amused by Gallo's predictions: May 14 -- Mike Piazza starts his first game ever as a pitcher and gives up 29 runs in a blowout loss to the Astros. However, he hits opposing starter Roger Clemens four times in the head with pitches, and beans him repeatedly with pickoff attempts to first base.

Primes with Primitive Roots near powers of two

For every power of two, what is the largest prime number less than it for which a primitive root is known? This probably means what's the largest prime number p less than 2^n for which p-1 has been completely factored. I guess it also begs the question, for each Mersenne prime 2^p-1, is 2^p-2 factored? Another related question is what's the largest Sophie Germain prime less than 2^n, for each prime (because sophie germain primes minus easily factor). Of course, there's also: what's the smallest prime number greater than the power of two that yadda yadda...

westminster chimes

for 31 days 1 2 3 4 5 12 34 51 23 45 123 451 234 512 345 1234 5123 4512 3451 2345 there's 20. next 10 days cycle (13524) 13 52 41 35 24 135 241 352 413 524 on the 31st day 12345 == perhaps some other cycle (14253), (54321)...

web browser columns

A web browser should do this to content 123..z12 :

123 def pqr
456 ghi stu
789 jkl vwx
abc mno z12
--------------

so that scrolling happens along the bottom scrollbar only. It allows for narrow column that humans like to read.

Fitt's Law, and things competing for the edge of the screen

menu bars start button quick launch subwindow tabs (or emacs buffer tabs) toolbars task lists scroll bars don't launch screensaver corner scroll desktop window manipulation (minimize, maximize, resize)

Emacs popups and mouseovers

Need a way to make "modern" IDE's with emacs. Need a way of hiding text, for example I don't care about the type information of the paramters to this function. And need a way of expanding and re-shrinking the hidden text quickly. And having the hidden text pop up on a mouseover.

more pell's equation

http://www.kaynet.or.jp/~kay/misc/pell2.html but the results don't agree with http://mathworld.wolfram.com/PellEquation.html for example at D=46 24335 3588 3482 531 226153980 there doesn't seem to be a truly authoritative source.

pell's equation

I now learn that I studied pell's diophantine equation in 7th-grade or so, though i didn't know it was called that. I was messing with newton's method of calculating square roots, and doing everything with exact fractions, and noticed that some intermediate fraction (the correction term) in each newton iteration tended be be something like 1/n. can be seen by seeding sqrt(2) with an initial guess of 3/2, or sqrt(3) with an inital guess of 2.