NaClhv

This is a picture I took on the side of a road:

The trees are planted in a regular pattern, in basically square grids. This creates the fascinating picture you see when you then look at the trees from the sides. You can see far off into the distance along some angles, but are blocked from seeing too far in other directions. The effect can be mesmerizing, especially when you drive past these fields on the highway.

While I was on one such drive, I began to wonder: what exactly is the pattern I'm looking at here? In particular: what is the probability that you can see one tree from another tree?

Let's nail down the specifics of the question: If you and a friend are in an infinite square grid of trees, and each of you choose to stand at a random tree, what is the probability that you two will be able to see each other? For the purposes of this question, we'll say that you can see each other if there are no trees between the two trees you've chosen. That is, one must be able to draw a straight, line-of-sight segment from one point on the square grid, to the other point on the grid, without any intervening points getting in the way.

I'm going to give away the answer, then explain how I got it. The probability is 6/π2, or about 61%.

That's right - you can get pi out of a problem that only has squares in it. There is no need to involve circles.

Let's begin the solution by saying that the tree you're standing at is the origin, represented by the coordinate (0,0). The x and y axis can then be arbitrarily assigned along the edges of the squares that make up the grid. All this can be done with no loss in generality.

The tree that your friend is standing on can then be assigned the coordinates (x,y). Now, can you see the point (x,y) from the origin? Well, is there a straight line connecting the two with no intervening points?

This is possible if x and y are coprime - that is, if they share no common factors other than 1. For example, 8 and 15 are coprime. So if your friend was standing at (8,15) or (15, 8), you would be able to see each other. But 2 and 2 are not coprime, because they're both divisible by 2. And if your friend were standing at (2,2), the point at (1,1) would get between you two, and you would not be able to see each other.

So now, the question has become "what is the probability that two randomly chosen integers are coprime"? Well, let's start by remembering the definition of "coprime" - that there can't be any natural number other than 1 that are factors of both integers.

Se we start by looking at 2 as a factor. We eliminate all the number pairs that are both divisible by 2, like (4,8) or (2,10). How many such pairs are there? Well, since the probability of a number being divisible by 2 is 1/2, the probability of both numbers being divisible by 2 is 1/22, or 1/4. After eliminating these, we have a remaining probability of 1 - 1/4 = 3/4. This is the probability of a number pair passing through the first filter, of them not both having 2 as a factor.

We next look at 3 as a factor, and eliminate all the number pairs that are both divisible by 3, like (30,81). As before, the probability of one number being divisible by 3 is 1/3, so the probability of both being divisible is 1/32 = 1/9, and after eliminating these, we have a probability of 1 - 1/9 = 8/9 left. This is the probability of a number pair passing through the second filter, of them not both having 3 as a factor.

Now, to combine both of the above to get a single probability value, we just multiply them: a number pair has a probability of 3/4 for passing through the first filter (having 2 as a factor), and 8/9 for passing through the second filter (having 3 as a factor). So the probability of passing through both would be 3/4 * 8/9.

But wait - can we do that? Sure, the probability of both numbers being multiples of 3 is 1/9, but doesn't that change when we condition it upon them also not being multiples of 2? We can't confuse conditional and unconditional probabilities, otherwise we'll make a mistake!

Actually, in this case we don't have to worry. In general, if p and q are prime numbers, the only way for a number to be a multiple of p and q is for it to be a multiple of p*q. In other words, if we look at the multiples of p in all the numbers going up to p*q, there are q such numbers, but only 1 number that's also a multiple of q: p*q itself. So there's q -1 other multiples of p that are NOT multiples of q.

Now, again looking at numbers up to p*q, there are p multiples of q. That means there are p*q - p numbers that are NOT multiples of q.

For the numbers larger than p*q, the pattern just repeats itself.

So, the probability of a number being a multiple of p, conditioned upon it not being a multiple of q, is given by (q - 1) / (pq - p) = 1/p. This is the same as the unconditioned probability.

Confused? Try it with 2 and 3. In numbers going up to 6, there are 2 numbers that are multiples of 3 (3 and 6). Among these, only one of them (6 itself) is also a multiple of 2. That leaves 2 - 1 = 1 number that's a multiple of 3 but not of 2.

But we also know that there are 3 numbers that are a multiple of 2 (2, 4, and 6). That means there are 6 - 3 = 3 numbers that are NOT a multiple of 2.

So, the probability of a number being a multiple of 3, conditioned upon it not being a multiple of 2, is 1/3. Exactly the same as the unconditioned probability.

Therefore the probability of having a particular prime number as a factor can be treated as independent probabilities, and since this is true for any two pair of prime numbers, the values derived from unconditioned probabilities can all be multiplied together.

So now, the only thing left to do to find the probability of two numbers being coprime is to simply go through all the possible numbers that can factor them both and eliminate those possibilities. We've already said that the probability of both numbers having 2 as a factor is 1/22, and the probability of both numbers having 3 as a factor is 1/32. The probability then of NOT having either 2 or 3 as a common factor is:

(1 - 1/22)(1 - 1/32)

We then extend this pattern for all numbers beyond 3 - except we can skip composite numbers, because if a number is not divisible by a prime number, it's guaranteed to not be divisible by any composite number with that prime number as a factor. So we don't have to check non-divisibility by 4, because we've already checked non-divisibility by 2.

Then the extended expression becomes:

probability = (1 - 1/22)(1 - 1/32)(1 - 1/52)(1 - 1/72)(1 - 1/112)(1 - 1/132)(1 - 1/172) ....
= product(1 - 1/p2), where p is an element in the set of all prime numbers.

This infinite product is a well-known expression, and it evaluates to 6/π2. That evaluation was first solved by Leonhard Euler, who was one of the greatest mathematician to have ever lived.

So, pi is far more profound than simply being the ratio of a circle's circumference to its radius. It comes up in all kinds of unexpected places, like in problems relating square grids or prime numbers.

I wish you a happy pi day! And feel free to eat square-shaped things today, like some square brownies, or a rectangular pizza you bring to a pi day potluck. You're mathematically justified!