info prev up next book cdrom email home

Hafner-Sarnak-McCurley Constant

N.B. A detailed on-line essay by S. Finch was the starting point for this entry.

Given two randomly chosen Integer $n\times n$ matrices, what is the probability $D(n)$ that the corresponding determinants are coprime? Hafner et al. (1993) showed that

D(n)=\prod_{p_k} \left\{{1-\left[{1-\prod_{j=1}^n (1-{p_k}^{-j})}\right]^2}\right\},
\end{displaymath} (1)

where the product is over Primes. The case $D(1)$ is just the probability that two random Integers are coprime,
\end{displaymath} (2)

Vardi (1991) computed the limit
\sigma\equiv \lim_{n\to\infty} D(n)=0.3532363719\ldots.
\end{displaymath} (3)

The speed of convergence is roughly $\sim 0.57^n$ (Flajolet and Vardi 1996).


Finch, S. ``Favorite Mathematical Constants.''

Flajolet, P. and Vardi, I. ``Zeta Function Expansions of Classical Constants.'' Unpublished manuscript. 1996.

Hafner, J. L.; Sarnak, P.; and McCurley, K. ``Relatively Prime Values of Polynomials.'' In Contemporary Mathematics Vol. 143 (Ed. M. Knopp and M. Seingorn). Providence, RI: Amer. Math. Soc., 1993.

Vardi, I. Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, 1991.

© 1996-9 Eric W. Weisstein