In the previous post in this series, I described a problem dealing with a lattice with an origin, and asked what is the probability that one can see the origin from a random place in the lattice. In this post I’ll give you my *new* proof of this result, with the understanding that someone else might have done this same proof before me (I’m not aware of such person so I will claim discovery).
As Carl Brannen pointed out in the comments, this is the same as the probability that when one picks two random integers they are relatively prime. I’ll leave that to you as a proof. This is a famous result in mathematics: it is given by
It is also sometimes stated as “Most fractions are reduced”, seeing as fractions involve the ratio of two integers.
The first time I heard about this result I was about 15 years old. It was told to me without proof and I thought it must be really hard to proof, because how does one pull all those factors of by counting?
Here below is an illustration of the situation.
I’ve graphed a region of the plane near the origin. If you don’t pay too much attention to the details, you will notice that the figure is rather uniform in color. We have to show that this uniformity of color persists to a large enough (infinite) size.
A few remarks are in order. Obviously, since the lattice is infinite, there is no uniform probability that assigns each point in the lattice the same probability: they would all have zero probability. The way around this is that we define the probability by taking a large enough distance N, and declare that all points closer than N have the same probability of being picked, and all the points away from this distance have zero probability. Afterwards we take the limit when N goes to infinity. We can not take N to infinity first and ask questions about probability. We can show that reasonable choices of how we choose a region of uniform probability, with the probability of being outside this region being finite lead to the same answer in the limit where the region of uniform probability grows to include the whole plane and so long as the probability of being outside this region approaches zero in the limit.
When we take the usual definition of probability, we need to count the number of points that have a given property, and divide it by the total number of points. If in the limit the answer is finite, then we would like to say that the set we have chosen has finite density. The figure suggests that the problem posed will have a finite density of points with the requested property, and the density of white points will be the required probability: the fraction of points with the desired property.
Now for my proof.
The idea is that instead of considering the problem as stated above, we will try to sum a function over the set of points of the plane, and compare it with the sum over the points with the desired property.
Consider the sum parametrized by the variable s
The primed sum indicates that the origin is removed. We are just summing the inverse distances of the points to the origin with some power law. Let us try the same, but now let us separate the pairs that are relatively prime, from those that are not. If two integers p,q are not relatively prime, then they have a greatest common divisor m (which we will take to be positive), and p/m=u and q/m=v are relatively prime. This m is uniquely characterized by the pair p,q. It is easy to show that
Indeed, if we sum over all p,q that are originating from the same pair u,v of relatively primer integers, we just end up summing over m.
With little effort we find that the sum over the plane is of the form
So if we do the sum over the points of interest and we compare them to the
sum over all pairs, we get a ratio that is given by , the Riemman zeta function evaluated at s. These manipulations are fine so long as the sum converges absolutely. This requires . This can be shown by comparing the sum to the integral
When the integral diverges. As a function of (thought of as a complex variable) the integral develops a pole at .
This divergence is from the far away region of the plane, due to it’s infinite size, not because the values of the function have become large locally. In quantum field theory we would call such a divergence an infrared divergence.
At the value where the divergence shows up the integral is dominated by the large volume region (large r). The same divergence shows in the infinite sum over the plane. The coefficient of the pole in s will be the same (I will not prove this here: it is intuitively reasonable, and a proper proof requires more analysis that I’m willing to use in this post.)
However, at there is nothing special happening in the function, so the same pole must appear in the sum over u,v and the residue must be off by the same factor of .
But it is exactly here that we are measuring the density of points at infinity. So long as we had picked anything with a finite density, the sum would have the same pole, and the residue at the pole would have a coefficient that indicates the density of points. This is ‘physically obvious’, by writing an integral
Where we have defined a density of points $\rho$. We assume that the density becomes constant near infinity (sufficiently fast) as in our problem. The ratio of ‘infinities’ is always our desired answer, because the integral above can easily be approximated near infinity by the one we have calculated.
In the limit we desire, we get obviously . This generalizes to a dimensional lattice giving us .
Again, let me caution you: one has to justify carefully a lot of the steps in the proof above. Without that justification, it is just a heuristic proof ( a so called ‘physics proof’ by mathematicians).
Now, the reason why I like the above proof is that it reminds me of a lot of techniques that are used in quantum field theory in the theory of renormalization (in particular how one thinks of dimensional regularization). For the readers who are practitioners of phsyics, they should recognize that the location of poles in the dimension for a regularized function in dimensional regularization
correspond exactly to the physical divergences that are most important: those that depend on the logarithm of the scale.
There have been a lot of jokes in mathematics and physics circles about physicists manipulating infinities to get finite convenient answers. I’m no better than the lot as the result above shows. The typical joke is from the following result
which is correct, if interpreted carefully and properly. I do not like writing it as the expression above, because it does not explain what the sum really is and why the right hand side might be the correct number. If I write instead that
then there is no infinity anymore: the sum over integers to various powers is a good representation of the Riemann zeta function only in a region where the sum converges. For other regions, it makes no sense. Written as the line above, even mathematicians agree that it is the right answer and nobody laughs at the joke.
The readers should also notice that I didn’t use fancy properties of the integers to get at this result. Rather, everything was replaced by analysis: fancy calculus and limit manipulations. This is an example of using analysis to solve problems in number theory. It is a whole branch of mathematics called analytic number theory. Here you get a taste.
Now I have to go sit down and prepare for teaching classes.