Posted by: courtneyobrien | September 30, 2008

Hafner-Sarnak-McCurley

This past weekend, I learned that my friend’s dad was the Sarnak in the Hafner-Sarnak-McCurley constant (http://mathworld.wolfram.com/Hafner-Sarnak-McCurleyConstant.html).  I had never heard of this constant before this weekend, but I thought you would all enjoy learning about it.

The Hafner-Sarnak-McCurley constant represents the probability that the determinants of two randomly chosen square integer matrices will be relatively prime. The probability depends on the matrix size, n, in accordance with the formula

D(n)=\prod_{k=1}^\infty\left(1-\left(1-\prod_{j=1}^n(1-p_k^{-j})\right)^2\right),

where p_k is the kth prime number. The limit of this expression as n approaches infinity is roughly 0.3532363719.

Professor Peter Sarnak has been called “one of the most influential mathematicians in the world.” (http://www.math.ufl.edu/dept_news_events/ramanujan/2007-8/). He received his undergraduate education at the University of Witwatersrand in South Africa and was awarded a Ph.D. from Stanford University in 1980.  He is a Professor at the Institute for Advanced Study in Princeton, NJ, and his current research focuses on the theory of zeta functions and automorphic forms with applications to number theory, combinatorics, and mathematical physics. Professor Sarnak was the recipient of The American Mathematical Society’s Levi L. Conant Prize in 2003 and the Frank Nelson Cole Prize in 2005.  In 2002, he was named a Member of the National Academy of Sciences and a Fellow of The Royal Society of London.

Advertisements

Responses

  1. Thanks for telling us about this! I hadn’t seen the formula before. These sorts of formulas are very interesting. As we’ll see when we get to probability, it’s actually a very tricky thing to “choose a random integer.” It’s easy to describe, mathematically, what it means to choose a random element from a finite set. But how do you do it from an infinite set? It would seem that a random integer would have zero probability of being positive and less than 10, since there are infinitely many larger alternatives. But the same argument would apply to being positive and less than 10^{10} or 10^{10^{10}}! So maybe it is larger than zero? Ok, suppose the probability is larger than zero for it to be positive and less than 10. Call the probability p. Then it’s got to have the same probability of being between 10 and 20, or of being between 20 and 30. But there are infinitely many such segments, each with probability p — this adds up to way more than 1. And you can’t have something of probability more than 1! So doesn’t this mean every integer has probability zero of being chosen? How can you pick anything?!

    So what does it mean here?! Deriving the formula itself isn’t too tricky, since you can do it one prime at a time, and use congruence arithmetic, which we’ll talk about on Tuesday. Since congruence (or modular) arithmetic is finite (that is, there are only finitely many possible remainders when you divide by a prime), you can make sense of the idea of “choosing randomly” from among the possible remainders. But then you have to put this all together and give meaning to the original statement about “random integers.”

    Another way of thinking of a “random integer” is to take a random integer between 1 and N, and then derive some results, and then take the limit as N goes to infinity.

    You can see a derivation of the formula for D(1) here.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: