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\},$$ (1)

where the product is over Primes. The case $D(1)$ is just the probability that two random Integers are coprime,

$$D(1)={6\over\pi^2}=0.6079271019\ldots.$$ (2)

Vardi (1991) computed the limit

$$\sigma\equiv \lim_{n\to\infty} D(n)=0.3532363719\ldots.$$ (3)

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

References

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/hafner/hafner.html

Flajolet, P. and Vardi, I. ``Zeta Function Expansions of Classical Constants.'' Unpublished manuscript. 1996. http://pauillac.inria.fr/algo/flajolet/Publications/landau.ps.

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.