Shoup: A computational introduction to number theory and algebra

A Computational Introduction to Number Theory and Algebra, online book, by Victor Shoup. (There's also a print edition, but the online PDF-book will remain freely available.) It is what it sounds like; "computational" doesn't mean "non-mathematical" but rather means that a lot of the applications are chosen with regard to their usability in computer science, specifically cryptography.

From reddit, where various commenters have pointed out things like "the author says that book is elementary but it really isn't." Of course, this is fairly common. The author actually says

The mathematical prerequisites are minimal: no particular mathematical concepts beyond what is taught in a typical undergraduate calculus sequence are assumed.
The computer science prerequisites are also quite minimal: it is assumed that the reader is proficient in programming, and has had some exposure to the analysis of algorithms, essentially at the level of an undergraduate course on algorithms and data structures.

As usual, "elementary" means something like "a smart, well-trained undergrad could read and understand it"; it's a term of art like anything else. But in some provinces of the Internet there seems to be an idea that everything should be immediately understandable to all readers at first glance. (I use Reddit for the links it gives me to interesting news, not for the comments.)

"Square roots" of probability distributions

Think about probability distributions supported on the positive integers. Not all of them have a "square root" -- that is, given a random variable X supported on the positive integer, there do not exist independent, identically distributed variables Y₁, Y₂ such that X has the same distribution as Y₁ + Y₂.

You might be wondering why it's natural to refer to this as a "square root". Well, let p_k be the probability of the event X = k. Then the probability generating function for X is

.

Similarly, let q_j be the probability of the event Y = j, and define the probability generating function

.

Let Y, Y₁, Y₂ be equidistributed. Then X is equidistributed with Y₁ + Y₂ if and only if f(z) = g(z)², since addition of independent random variables corresponds to convolution of distributions and multiplication of their generating functions.

Conversely, the random variable X has a square root in this sense if and only if its generating function f(z) has a square root which has a Taylor series at z = 0 with all coefficients positive.

The simplest case is when X has finite support. Then X has a square root if and only if its generating function f(z) is the square of a polynomial. For example, the random variable which takes values 0, 1, 2 with probabilities 1/4, 1/2, 1/4 has a square root; its generating function is

.

But the random variable taking values 0, 1, 2 with probability 1/3 each is not, since 1/3 + z/3 + z²/3 is not a square.

But what about distributions with infinite support? Some of these are easy -- the square root of the Poisson distribution with mean λ is Poisson with mean λ/2. This can easily be seen since the probability generating function of a Poisson(λ) random variable is

.

(In fact, the Poisson distribution is infinitely divisible; in the nomenclature used in this post one might say it has roots of all orders.)

Now consider a random variable X, with geometric distribution with parameter 1/2 supported on {0, 1, 2, 3, ...}; this has P(X = k) = 2^-(k+1). This is a special case of the negative binomial distribution, which is infinitely divisible. We have f(z) = 1/2 + z/2² + z²/2³ + ... = 1/(2-z). So the square root distribution has generating function

and in general the coefficient of zⁿ is, by the binomial theorem,

That binomial coefficient is ${1 \over 2} {2n \choose n}$; we have ${2n \choose n} \sim 4^n/\sqrt{\pi n}$, so the coefficient of zⁿ in our probability generating function, which we'll call q_k, is asymptotic to

In particular, the "square root" distribution decays just a bit faster than the distribution that it's the square root of, the main difference being the additional factor of n^-1/2. This is reasonable, if you think about the process of convolution. We have

p_n = q₀ q_n + q₁ q_n-1 + q₂ q_n-2 + ... + q_n-1 q₁ + q_n q₀

and each of the n terms is roughly 1/(n2ⁿ). This is just another negative binomial distribution. (I actually didn't realize that until I started writing this post; the post was originally titled "what's the name of this distribution?" and then I did some research.)

Video abstracts?

From John Baez at the n-Category Cafe: the Journal of Number Theory is now inviting authors to post their abstracts on YouTube.

Something about putting them on YouTube -- as opposed to on the journal's website -- strikes me as saying that they're not "really" part of the paper.

More interestingly, though, the few "video abstracts" there are just people reading their abstracts. I think it's a good idea, but mathematical speech is just not mathematical writing read out loud. (This is, of course, the converse of the fact that mathematical writing is not just mathematical speech transcribed.) Perhaps there's potential here, though. The first few minutes of a good talk would work as a good "video abstract", I think.

But you've got to start somewhere.

Stochastic generation of ideas

I'm reading about continuous time Markov processes, from Adventures in Stochastic Processes: The Random World of Happy Harry by Sidney Resnick. This book has some of the most amusing problems I've come across in a while; many of the problems involve a character known as "Happy Harry", who owns a greasy spoon near some university that occasionally reveals itself to be Cornell. This post does not involve one of those problems.

A discrete-time Markov chain is what people usually mean when they say "Markov chain". This is a sequence of elements X₀, X₁, X₂, ... selected from some state space S = (s₁, s₂, ...), where

P(X_n = s_j | X_n-1 = s_i) = p_ij

(the p_ij are called transition probabilities) and X_n does not depend on the history before X_n-1. Now, from any discrete-time Markov chain it's possible to construct a continuous-time Markov chain. We simply assign a parameter λ(j) to each state s_j. When the discrete-time Markov chain finds itself in state j, we wait for a time which is exponentially distributed with parameter λ(j) (and therefore mean 1/λ(j)); after this time passes we proceed into another state according to the transition probabilities.

There's a problem, though, as Resnick explains in Section 5.2 -- it can happen that the chain "blows up", i. e. it makes infinitely many transitions in finite time.

The "pure birth" process has state space {1, 2, 3, ...}; the transition probabilities are p_n,n+1 = 1 with all others zero; the parameters are λ(n) = λn. That is, the process waits in state n for a time which is exponentially distributed with mean 1/(λn) and then advances to state n+1. Not surprisingly, the population grows exponentially fast -- if the population is at n currently, it grows at rate λn.

But if you let λ(n) = λn², then the process "blows up" almost surely. This isn't surprising from the point of view of a differential equation -- if the population is n, it grows at rate λn². If we ignore the stochastic elements and model this as an ordinary differential equation, the population P satisfies dP/dt = λP², and solutions to this have vertical asymptotes. Something similar (I don't pretend to know all the details) happens in the stochastic case.

I then thought, when would you get a population that grows like this? Consider not a population of living beings, but a population of ideas. And let us assume that new ideas come into being when two old ideas combine. Then in some idealized world where all pairs of ideas are constantly interacting, one might expect that the rate at which new ideas exist is proportional to the number of pairs of ideas. Of course, this is a silly model, because ideas don't interact all by themselves, but rather in people's brains -- and the population of people grows just exponentially. Still, this feels like it could explain why certain ideas seem to "come out of nowhere" -- at first in some area of intellectual inquiry there isn't much there because new ideas require new insights, but at some point combining old insights in new ways becomes a viable way to come up with new ideas.

(Of course, checking this against reality would be quite difficult. For one thing, how do you count ideas?)

Abuse of averages

At Freakonomics, they're talking about an advertisement that says that the average termite eats 24 hours a day. (This is an ad for a pest control company.)

Of course, this isn't possible!

Nearly every termite is actually below average; I don't know much about termites but at some point they slack off.

However, the average termite colony might be eating close to 24 hours a day, in that at least one of the termites in your house may be eating at any given moment. And I think this is the point the ad was trying to make -- termites are constantly destroying your house. (Even this might not be true. Do termites sleep at night?)

I Will Derive

"I Will Derive", a parody of "I Will Survive".



(via reddit.)

Now, the original song is clearly about female empowerment, and there is somebody who could be described as a "jerk" in the song. (Here are the lyrics, in case you've been living in a cave, or you're not from the US -- I'm not sure how well-known this song is in other countries.) I think this parody would be improved if it mentioned jerk, the third derivative of position.

Phillies radio silliness

There's a commercial which airs on Phillies radio broadcasts. Since I dislike Comcast, but am addicted to the Internet, I'm willing to pay them for high-speed Internet access but not for cable TV. This means I listen to Phillies games on the radio.

Anyway, there's a commercial for Citizens Bank (who own the naming rights to Citizens Bank Park, where the Phillies play) that regularly airs during these broadcasts. It goes something like this (I'm paraphrasing, but the "math" is correct):

Did you ever notice how important the number seven is to the Phillies? They've won seven National League East division titles. There are seven letters in Ashburn, Schmidt, and Carlton. Thirty-two Hall of Famers played for the Phillies. Divide by the number of runs scored in a grand slam and, yes, you get eight. Subtract the number on Whitey's back and what do you get. Seven!

The voice then proceeds to tell us how Citizens Bank is open seven days a week. Which I suppose would be nice to know if I didn't do basically all my banking at ATMs anyway.

But I think the commercial is intended to make fun of people who jump through hoops like this to make the numbers work out. And seven is a small number and therefore easy to manufacture by the manipulation of other small numbers, or so I noted on July 7, 2007.