MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $A \in M_n(\mathbb Z)$ and $\|A\| = \max |a_{ij}|$. Denote $$ S(r) = \sum_{\substack{\|A\| \leq r \\\ \det{A} \neq 0}} \dfrac{1}{|\det{A}|} $$ - the sum over all matrices $A \in M_n(\mathbb Z)$ with $\|A\| \leq r$ and $\det{A} \neq 0$.

I'm interested about the asymptotic behavior of the function $S(r)$:

  • How does $S(r)$ grows?
  • Is it true that $\lim\limits_{r \to \infty} \dfrac{S(r)}{r^{n^2}} = 0 $ ?

Suggestions on special cases when $n = 2,3$ are also appreciated.

share|cite|improve this question
For 4r greater than log(2^n), you can restrict the off diagonal entries to beng nonzero, but replace upper triangular in Davide Giraudo's suggestion by "comb" patterns of mostly zero rows and columns to get a factor of 2^(n-1). As r grows, the loss by replacing 2r+1 by 2r becomes negligible comapred to the 2^(n-1) gain. Because the denomnator of your limit is not (2r+1)^(n^2), I suspect your limit does not go to 0. Gerhard "Ask Me About Integer Matrices" Paseman, 2013.06.01 – Gerhard Paseman Jun 1 '13 at 13:51
A lower bound for the problem can be found from Example 1.6 in "DENSITY OF INTEGER POINTS ON AFFINE HOMOGENEOUS VARIETIES" by Duke, Rudnick, and Sarnak, Vol. 71, Duke, July 1993. This gives a lower bound of form $mr^{n^2−n}$, where m is a constant, by estimating the number of matrices in $SLn(\mathbb{Z})$, with bounded coefficients. I would guess that this could be also used for further analysis. A related question:… Related work: – user18180 Jun 2 '13 at 9:09
One natural thing to do in this setting is to introduce a zeta function like $Z_n(s)=\sum_{A \in M_n(\mathbb{Z})}|\mathrm{det} A|^{-s}$. Unfortunately this zeta function is not very well behaved and does not converge for any $s \in \mathbb{C}$ due to there being infinitely many unimodular matrices. Perhaps you can consider a zeta function in your setting which takes into account the condition $||A|| \leq r$. – Daniel Loughran Jun 3 '13 at 12:48
Out of interest, there is a related zeta function which is very well-behaved. Namely, the set of matrices in $M_n(\mathbb{Z})$ up to unimodular equivalence is naturally in bijection with the set of all sublattices of $\mathbb{Z}^n$. The associated zeta function $\sum_{ \Lambda \subset \mathbb{Z}^n} (\mathrm{det \Lambda})^{-s}$ is well behaved and has a nice expression in terms of products of the Riemann zeta function. – Daniel Loughran Jun 3 '13 at 12:52
up vote 1 down vote accepted

RV above links to a paper of Duke, Rudnick and Sarnak where they establish the following (see Example 1.6 and Theorem 1.10):

The number of $n \times n$ matrices with $||A|| \leq r$ and $\det A = k$ is $$c_n r^{n^2-n} \sum_{d_1 d_2 \cdots d_n=k} \frac{1}{d_2 d_3^2 \cdots d_n^{n-1}} + O(r^{n^2-n-1/n + \epsilon})$$ where $$c_n = \frac{\pi^{n^2-n}}{\Gamma\left(\frac{n}{2}\right) \Gamma\left(\frac{n^2-n+2}{2}\right) \zeta(2) \zeta(3) \cdots \zeta(n)}.$$

Taking $k=1$, we get the lower bound $$S(r) > (c_n-o(1)) r^{n^2-n}.$$ I didn't read the paper carefully enough to figure out how uniform the $O(\ )$ bound is. If we ignored the $O(\ )$ term altogether, we'd get $$S(r) \approx c_n r^{n^2-n} \sum_k \sum_{d_1 d_2 \cdots d_n=k} \frac{1}{k d_2 d_3^2 \cdots d_n^{n-1}} = c_n r^{n^2-n} \sum_{d_1 d_2 \cdots d_n} \frac{1}{d_1 d_2^2 d_3^3 \cdots d_n^{n}}$$ $$ = c_n r^{n^2-n} \sum_{d_1} \frac{1}{d_1} \sum_{d_2} \frac{1}{d_2^2} \sum_{d_3} \frac{1}{d_3^3} \cdots \sum_{d_n} \frac{1}{d_n^n} = c_n r^{n^2-n} \left( \sum_d \frac{1}{d} \right) \zeta(2) \zeta(3) \cdots \zeta(n)$$ Hmm, the sum diverges. That isn't good.

Presumably, if we looked at the proof and the error bounds a little more carefully, we'd wind up cutting off the sum at some upper bound: $c_n r^{n^2-n} \zeta(2) \zeta(3) \cdots \zeta(n) \sum_{d \leq D} 1/d \approx c_n r^{n^2-n} \zeta(2) \zeta(3) \cdots \zeta(n) \log D$. I'm not going to work hard enough to figure out what $D$ is, but surely $n! r^n$ is large enough, as there are no terms with determinant larger than that. On the other hand, I would guess that the leading term in the DRS bound dominates when $k \leq r^{1/(100 n)}$. Both of these are powers of $r$, so both of them have logarithm of the form $c \log r$.

So I would guess that the asymptotics of $S(r)$ are like $$c r^{n^2-n} \log r$$ for some constant $c$ (dependent on $n$).

share|cite|improve this answer

This is only a partial answer when $n=2$.

When $n=2$, it is easier to visualize.

First, use partial summation to $S(r)$, then we have

$$ S(r)=\int_{1-}^{\infty} \frac{1}{t} dA_t = \frac{A_t}{t}\mid_{1-}^{\infty}+\int_{1-}^{\infty}\frac{1}{t^2}A_tdt,$$ where $$ A_t=\sum_{\substack{{||A||\leq r} \\\ {|\textrm{det}(A)|\leq t}}}1. $$

Interpreting the $|\textrm{det}(A)|$ as the area of parallelopiped spanned by columns of $A$, we find that $$A_t \leq 4\sqrt{2} r^3 t+O(r^3). $$

Hence, we have $$ S(r)\leq 8\sqrt{2} r^3 \log r + O(r^3). $$

Therefore $S(r)/r^4 \rightarrow 0$.

share|cite|improve this answer
Argument seems to work in general, $S(r)=O(r^{n^2-1}\log r)$. – i707107 Jun 1 '13 at 23:19
Could you clarify how did you get that $A_t \leq 4\sqrt{2} r^3 t + O(r^3)$ ? – Anton Menshov Jun 2 '13 at 10:18
I realized that that estimate was overestimate. This is a counting argument for lattice points, like one uses for Gauss Circle Problem. The number of lattice points inside a convex region is approximated by the area of the region + error term depending on perimeter. – i707107 Jun 2 '13 at 15:49
I think the true bound is $S(r)=O(r^2\log r + r^3)$ now. – i707107 Jun 2 '13 at 15:50

For $n=2$, the growth of $S(r)$ is actually significantly slower than i707107's bounds would suggest. I will show that $A_t = O(t r^2)$, not $t r^3$, and hence $S(r) = O(r^2 \log r)$. I can also establish the lower bound $S(r) > c r^2$, so $2$ is the correct exponent.

Let $A(r,t)$ be the number of $2 \times 2$ matrices with $||A|| \leq r$ and $|\det A| \leq t$, $\det A \neq 0$. We will show $A(r,t) \leq C r^2 t$ and $A(r,1) \geq c r^2$ for some constants $c$ and $C$.

The upper bound: We will count the number of matrices $\left( \begin{smallmatrix} a & b \\ c & d \end{smallmatrix} \right)$ with $0 < |\det A| \leq t$, $||A|| \leq r$ and $|d| = \max(|a|,|b|,|c|,|d|)$. Multiplying by $4$ then gives an upper bound on $A(r,t)$. We break up our count according to $GCD(c,d)$.

First, let's count the terms with $GCD(c,d)=1$. Fix a particular $(c,d)$. For each $u$ between $-t$ and $t$, the equation $ad-bc=u$ determines $b \bmod d$. Combined with the condition $|b| \leq |d|$, there are only two values for $b$, given a fixed $(c,d)$ and a fixed value for $\det \left( \begin{smallmatrix} a & b \\ c & d \end{smallmatrix} \right)$. And, $(b,c,d,u)$ determines $a$. There are $O(r^2)$ choices for $(c,d)$, and $O(t)$ choices for $u$, so such terms contribute $O(t r^2)$ to our count.

Now, let's do the case where $GCD(c,d) = g$, say $c = g c'$ and $d = g d'$. The equation $ad-bc=u$ is only solvable at all when $g|u$, which is for $O(t/g)$ values of $u$. In that case, $b$ is determined modulo $d'$. Combined with the inequality $|b|\leq d$, this gives $O(d/d') = O(g)$ choices for $b$. So, for each $(c,d)$, there are $O(g) O(t/g) = O(t)$ ways to complete it to a $(a,b,c,d,u)$ quintuple. The number of $(c,d)$ pairs with $GCD$ equal to $g$ is $O(r^2/g^2)$.

So our bound is $O \left( \sum_g t r^2/g^2 \right) = O(t r^2)$.

The lower bound There are $(6/\pi^2 - o(1)) r^2$ pairs $(c,d)$ with $GCD(c,d)=1$ and $|c|, |d| \leq r^2$. For each of these, we can find $(a,b)$ with $|a|$, $|ab| \leq \max(|c|, |d|)$ and $ad-bc=1$. So there are $(6/\pi^2 - o(1)) r^2$ matrices contributing to $A(r,1)$. (It is easy to improve this constant, but probably not worthwhile.)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.