28
$\begingroup$

What is the probability that three pairs $(a,b) $ , $(c,d) $ and $(e,f) $ of integers generate $\mathbb Z^2$? As usual the probability is the limit as $n\to \infty$ of the same probability for the $n\times n$ square. It is well known that for $\mathbb Z $ the probability of two numbers to generate is $6/\pi^2$.

$\endgroup$
10
  • $\begingroup$ It's often called "natural density". It's certainly zero, since the condition implies that $ad-bc=\pm 1$. The analogy would rather suggest to consider triples of pairs. $\endgroup$
    – YCor
    Jun 19, 2018 at 8:18
  • 1
    $\begingroup$ Crude numerical experiment suggests an answer of about $0.506\pm 0.001$. $\endgroup$ Jun 19, 2018 at 9:00
  • $\begingroup$ Interesting; even a proof that the ratio is bounded away from zero would be a good start. Also, in $\mathbf{Z}$, is the density of generating triples known? $\endgroup$
    – YCor
    Jun 19, 2018 at 9:01
  • 2
    $\begingroup$ After switching to C I did $10^8$ samples in the range $[-10^6,10^6]$ and got $p=0.505695$. $\endgroup$ Jun 19, 2018 at 9:36
  • 2
    $\begingroup$ @KevinP.Costello I think your $a_p$ is just $((p+1)(p^3-1)+1)/p^6$. That gives $\prod_p(1-a_p)=0.5057390639$. $\endgroup$ Jun 19, 2018 at 9:52

2 Answers 2

37
$\begingroup$

According to Proposition 1 in the paper

G. Maze, Gérard, J. Rosenthal, U. Wagner: Natural density of rectangular unimodular integer matrices, Linear Algebra Appl. 434, No. 5 (2011), 1319-1324, ZBL1211.15044,

the probability that $n$ random vectors generate $\mathbb{Z}^{n-1}$ is $$p_n = \prod_{j=2}^n \zeta(j)^{-1}.$$

For $n=2$ this gives $p_2=\zeta(2)^{-1}=6/\pi^2$, whereas for $n=3$ we obtain $$p_3= \zeta(2)^{-1} \zeta(3)^{-1} \simeq 0.505739038$$

$\endgroup$
3
  • 1
    $\begingroup$ By the way they also consider the case of $n$ random vectors in $\mathbf{Z}^k$ for any $n>k$. In particular, the "probability" for $n$ vectors to span $\mathbf{Z}$ is $1/\zeta(n)$, and in $\mathbf{Z}^2$ it's $1/(\zeta(n-1)\zeta(n))$. $\endgroup$
    – YCor
    Jun 19, 2018 at 10:24
  • $\begingroup$ Right. I just wrote the statement in the case which is relevant for the question, but their result is more general. $\endgroup$ Jun 19, 2018 at 10:25
  • 2
    $\begingroup$ Well, you extrapolated the dimension and I extrapolated the numbers of vectors. $\endgroup$
    – YCor
    Jun 19, 2018 at 10:27
32
$\begingroup$

Let me convert my comments to an answer. Let $u_n$ be the probability that a triple in $([0,n-1]^2)^3$ generates $\mathbb{Z}^2$, and let $v_n$ be the probability that a triple in $((\mathbb{Z}/n)^2)^3$ generates $(\mathbb{Z}/n)^2$. Certainly $v_n\geq u_n$, and I think that $v_n$ should be asymptotic to $u_n$. Using the Chinese Remainder Theorem and the structure of $(\mathbb{Z}/p^k)^2$ we see that $v_n$ is the product of $v_p$ for all primes dividing $n$. A little linear algebra gives $v_p=(1-p^{-2})(1-p^{-3})$. Thus, the expected density is $$ v_\infty = \prod_p (1-p^{-2})^{-1}(1-p^{-3})^{-1} = (\zeta(2)\zeta(3))^{-1} \simeq 0.5057390381 $$ agreeing with the answer that Francesco Polizzi just entered while I was typing this.

$\endgroup$
1
  • 1
    $\begingroup$ I talked to Alex Lubotzky about my question and he said that the result can be found in his book with Dan Segal "Subgroup growth", the proof he outlined was similar to your answer. $\endgroup$
    – user6976
    Jun 27, 2018 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy