The next game is the only tournament game I’ve ever played against a grandmaster. My opponent was Georgian GM Mikheil Kekelidze. Not surprisingly, he outplayed me in every phase of the game. Obviously, I’ve still got a lot of work to do!
I played the following game with the White pieces against WFM Anna Levina. The middlegame shows the thematic idea of playing with a good knight against a bad bishop. The finale shows off a beautiful twist on the same idea.
In this post, we will explore the following question: If we choose two integers uniformly at random, what is the probability that they are relatively prime?
We start with a preliminary result. The Riemann zeta function, , is ubiquitous in number theory. Although the most interesting version of it is the complex-valued one, today we only need the real version. It is defined as follows: for any real number greater than
The Euler product for the zeta function is the following alternative expression:
where the product is taken over every prime . To see why this formula is true, we start with the right-hand side and use a geometric series expansion to obtain
By the Fundamental Theorem of Arithmetic, every positive integer can be expressed as a unique product of primes, up to order. (We consider to be the product of no primes; i.e., the empty product.) Thus, there is a one-to-one correspondence between the terms in the sum and the terms in the expansion of the product Hence,
Now back to our original problem! Suppose we choose uniformly at random. Fix an arbitrary prime . The probability that both and are divisible by is . Hence, the probability that they are not both divisible by is .
The condition that and are relatively prime is equivalent to the condition that, for every prime , and are not both divisible by . Furthermore, for distinct primes and , the events that and are not both divisible by and and are not both divisible by are mutually independent. (In fact, more precisely, the events that and are not both divisible by and and are not both divisible by , for relatively prime integers and , are mutually independent.)
Thus, the probability that and are relatively prime is equal to
where the product is taken over every prime . But
Hence the answer is
The closed-form expression for is actually well-known (it equals , but that’s another story for another day. The result also generalizes to more than two integers, a nice exercise for the reader.
Euler’s totient function, is a well-known arithmetic function from number theory. For any , is defined to be the number of integers in the range for which . There is a formula for computing :
where the product is taken over all the distinct primes dividing . This formula can be proved in a few ways. One rests on the fact that is multiplicative. Another uses an elaborate form of inclusion-exclusion. The one I am presenting now is based on probability.
Suppose we fix a positive integer and choose uniformly at random an integer in the range . What is the probability that ? We answer this question in two ways. On one hand, we know by definition that there are successful outcomes and total outcomes, so the probability is equal to . On the other hand, we proceed more constructively. In order for the integer to be relatively prime to , it is necessary and sufficient for each prime divisor of that must not be divisible by .
The probability that is divisible by is . Hence, the probability that is not divisible by is . Furthermore, for distinct primes and , the events that is not divisible by and is not divisible by are mutually independent. (More precisely, the events that and are not both divisible by and and are not both divisible by , for relatively prime integers and , are mutually independent.)
Thus, the probability that is relatively prime to is
Equating our two results, we have
In other words,
We’ll use a similar approach in the future to show that the probability of choosing uniformly at random a pair of relatively prime integers is
Here’s a historical paper I wrote on different musical temperaments from Antiquity until the late Renaissance.
Recommended reading for anyone who is confused about the differences between just, mean, and equal temperament.
Here are some supplementary audio samples:
Just major third:
Pythagorean major third (ditone):
Just major third cycle:
The resulting comma (“diesis”):
Here’s a nice positional game I played recently as White against USCF expert Robert Radford. What started out as a nice space advantage for me first changed into a structural advantage, then into a dynamic advantage, and then finally into a decisive structural and dynamic endgame advantage. (Had my opponent not resigned, I would have concluded with a material advantage!)
Here’s an interesting exercise that can be solved using complex integration and basic combinatorics. Consider the following integral:
No apparent tricks from ordinary calculus appear to be helpful, so we turn instead to complex variables. The limits of integration suggest a parametrization of the unit circle. Let denote the unit circle, oriented counterclockwise. We’d like to convert our original integral into a contour integral of the form for an appropriate function . We can parametrize the contour by letting Then , so that , or in other words, We also observe that, on our contour, . Hence,
Within the region bounded by the contour, the integrand has exactly one singularity. More precisely, it has an essential singularity at . Thus, by Cauchy’s residue theorem, the value of the integral is equal to times the integrand’s residue at .
Let . To find the residue of at , we consider the Laurent series for centered at . (A simple approach here is to write , but we shall take a more roundabout path. The reader is invited to attempt the direct route.) Using the standard series for the exponential, we obtain
The residue of at is defined as the coefficient of the term in the Laurent series for centered at . From the above expansion, we see that in order to determine this coefficient, it suffices to determine the coefficient of within the infinite sum.
Fix a nonnegative integer and consider the binomial . We wish to determine the coefficient of in the expansion of this binomial. In order to obtain a term in the first place, we see that the terms and must multiply together in pairs. Hence, if is odd, the coefficient of is . Thus, we may focus our attention on the nonnegative even integers.
Consider the binomial . What is the coefficient of in its expansion? If we imagine copies of the expression being multiplied together, the only way we obtain a nonzero term is when we choose the and terms in pairs. There will be a total of pairs. Of the copies of , we can choose any of them, and then the remaining choices will have to be terms. Hence, the coefficient of is .
Since, in our original series, each term is divided by , we must divided by . By definition, , so divided by is simply .
Thus, the desired residue is seen to be
It follows by the residue theorem that the value of the integral we seek is equal to
It turns out that the original integral is not entirely unmotivated, as it can also be written as , where denotes the modified Bessel function of the first kind. This result can be seen from the integral formulas for these functions.
Here’s my senior composition project from Brown, written in 2008–2009. Titled “Percussion Quartet,” it’s scored for two pianists and two percussionists, much in the spirit of Bartók’s well-known piece for the same instruments. Lasting approximately 16 minutes, the piece is divided into four movements, the first two being played attacca.
An analytic commentary is also available.