Open MathsAll courses

Counting lattice matrices

Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).

The probability that three sampled columns have a small determinant will be expressed (sixth lesson) as a count of integer \(3\times3\) matrices whose rows lie in a given lattice \(\Lambda\subseteq\mathbb Z^3\), whose rows are not too long, and whose determinant is a prescribed number. This lesson proves the count for a nonzero determinant: at most a constant times \((\log X)^2X^6/I^2\), where \(X\) bounds the row lengths and \(I\) is the index of \(\Lambda\). The lattice may be very elongated, so the proof keeps three different scales apart. The tools are elementary facts about lattices, proved here: covolume equals index, a product bound for successive lengths, and point counts in plane lattices.

We use from Measure and Integration (Fremlin, Measure Theory, volumes 1 and 2) that Lebesgue measure \(\mu\) on \(\mathbb R^s\) is a measure (countably additive on measurable sets), gives a half-open box the product of its side lengths (115D(b)), is invariant under translations (134A), and satisfies \(\mu T[E]=|\det T|\,\mu E\) for a linear map \(T\) (263A). From Thom classes and Euler classes we use Lemma 5.1: every subgroup of a free abelian group of finite rank is free, of no larger rank. All lengths are Euclidean.

1. Lattices, covolume and index

A lattice of rank \(s\) is a subgroup \(L=\mathbb Zb_1\oplus\cdots\oplus\mathbb Zb_s\) of some \(\mathbb R^n\) generated by linearly independent vectors \(b_1,\ldots,b_s\), a basis. Its determinant (covolume) \(\det L\) is \(|\det(b_1,\ldots,b_s)|\) computed in orthonormal coordinates of the real span of \(L\). Two bases differ by an integer matrix with integer inverse, of determinant \(\pm1\), so \(\det L\) does not depend on the basis; nor on the orthonormal coordinates, which differ by an orthogonal matrix. A ball meets \(L\) in finitely many points: the coordinates of a lattice vector in the basis are a linear function of the vector, hence bounded on a ball.

Lemma 1.1 (index and covolume). (a) If \(M\) is an \(n\times n\) integer matrix with \(\det M\neq0\), then \(\mathbb Z^n/M\mathbb Z^n\) has exactly \(|\det M|\) elements. In particular a lattice \(\Lambda\subseteq\mathbb Z^n\) of rank \(n\) has \([\mathbb Z^n:\Lambda]=\det\Lambda\).

(b) If \(L_0\subseteq L\) are lattices of the same rank, then \(\det L_0=m\det L\) for a positive integer \(m\), and \(m\) times every vector of \(L\) is an integer combination of any basis of \(L_0\).

Proof. (a) Integer column operations (exchanging two columns, changing the sign of a column, adding an integer multiple of one column to another) change \(M\) to \(MU\) with \(U\) invertible over the integers, and do not change \(M\mathbb Z^n\) or \(|\det M|\). By Euclid's algorithm on the entries of the first row, column operations make the first row \((d_1,0,\ldots,0)\) with \(d_1>0\) (the row is nonzero since \(\det M\neq0\)). Operations among columns \(2,\ldots,n\) then do the same for the second row without changing the first, and so on. We reach a lower triangular matrix \(M'\) with diagonal \(d_1,\ldots,d_n>0\) and \(\prod d_i=|\det M|\). The vectors \(x\) with \(0\leq x_i<d_i\) represent every class of \(\mathbb Z^n/M'\mathbb Z^n\): subtracting multiples of the columns of \(M'\) one row at a time, from the top (column \(i\) of \(M'\) has zeros above row \(i\)), brings any \(y\in\mathbb Z^n\) into this set. They represent different classes: if \(x-x'=M'c\) with \(c\neq0\), and \(i\) is the first index with \(c_i\neq0\), then the \(i\)-th coordinate of \(M'c\) is \(d_ic_i\), so \(|x_i-x'_i|\geq d_i\), impossible. For the last assertion take \(M\) to be a basis matrix of \(\Lambda\).

(b) Write a basis of \(L_0\) in a basis of \(L\): an integer matrix \(M\) with \(\det M\neq0\), so \(\det L_0=|\det M|\det L\). For \(v\in L\) with coordinate vector \(c\in\mathbb Z^s\) in the basis of \(L\), its coordinates in the basis of \(L_0\) are \(M^{-1}c=\operatorname{adj}(M)c/\det M\in m^{-1}\mathbb Z^s\), with \(m=|\det M|\). \(\square\)

2. Successive lengths

Let \(L\) have rank \(s\). Choose \(v_1,\ldots,v_s\in L\) successively, \(v_i\) a shortest vector of \(L\) outside the span of \(v_1,\ldots,v_{i-1}\) (it exists, since a ball contains finitely many lattice vectors), and put \(\lambda_i=|v_i|\), the successive lengths. Thus \(0<\lambda_1\leq\cdots\leq\lambda_s\); the \(v_i\) are linearly independent.

Lemma 2.1 (successive lengths). \(\det L\leq\lambda_1\cdots\lambda_s\leq s^{s/2}\det L\). Consequently the lattice \(L_0\) spanned by \(v_1,\ldots,v_s\) has \(\det L_0=m\det L\) with \(m\leq s^{s/2}\), and every vector of \(L\) has coordinates in \(m^{-1}\mathbb Z\) with respect to \(v_1,\ldots,v_s\).

Proof. Choose orthonormal coordinates \(a_1,\ldots,a_s\) of the span of \(L\) such that the first \(j\) coordinate directions span \(v_1,\ldots,v_j\), for every \(j\). In these coordinates the matrix with columns \(v_1,\ldots,v_s\) is upper triangular, with diagonal entries of absolute value at most \(|v_i|=\lambda_i\); so \(\det L_0\leq\prod\lambda_i\), and Lemma 1.1(b) gives \(\det L\leq\det L_0\).

For the other inequality let \(Q=\{a:|a_i|<\lambda_i/\sqrt s\text{ for all }i\}\). A nonzero \(x\in L\cap Q\) has a last nonzero coordinate \(a_j\); then \(x\) lies outside the span of \(v_1,\ldots,v_{j-1}\), and \(|x|^2<\sum_{i\leq j}\lambda_i^2/s\leq\lambda_j^2\), contradicting the choice of \(v_j\). So \(L\cap Q=\{0\}\). Since \(Q\) is convex and symmetric, \(\frac12Q-\frac12Q=Q\), and the translates \(\frac12Q+x\), \(x\in L\), are pairwise disjoint. Let \(F=\{\sum t_ib_i:0\leq t_i<1\}\) for a basis \(b_i\) of \(L\); the sets \(F+x\), \(x\in L\), partition the span. Hence, by countable additivity and translation invariance, \[ \begin{aligned} \mu(\tfrac12Q)&=\sum_{x\in L}\mu\bigl(\tfrac12Q\cap(F+x)\bigr)\\ &=\sum_{x\in L}\mu\bigl((\tfrac12Q-x)\cap F\bigr)\\ &\leq\mu(F)=\det L, \end{aligned} \] the sets \((\frac12Q-x)\cap F\) being disjoint subsets of \(F\), and \(\mu(F)=\det L\) by 263A applied to the unit cube. Since \(\mu(\frac12Q)=\prod_i\lambda_i/\sqrt s=s^{-s/2}\prod_i\lambda_i\), the inequality follows. The last statement is Lemma 1.1(b) with \(m=\det L_0/\det L\leq\prod\lambda_i/\det L\leq s^{s/2}\). \(\square\)

3. Plane lattices

Lemma 3.1 (points of a plane lattice). Let \(L\) be a lattice of rank two with successive lengths \(\lambda_1\leq\lambda_2\).

(a) If \(R\geq\lambda_2\), every translate \(x_0+L\) has at most \(36R^2/\det L\) points in any closed ball of radius \(R\).

(b) If \(R<\lambda_2\), the points of \(L\) of length at most \(R\) lie on the line \(\mathbb Rv_1\) and number at most \(1+2R/\lambda_1\).

Proof. (a) Let \(L_0=\mathbb Zv_1+\mathbb Zv_2\), with \(\det L_0=m\det L\) (Lemma 2.1, \(m\leq2\)), and let \(F_0=\{t_1v_1+t_2v_2:0\leq t_i<1\}\), of diameter at most \(\lambda_1+\lambda_2\leq2R\). The points of \(x_0+L\) in the ball lie in at most \(m\) cosets of \(L_0\); for the points \(y\) of one coset, the sets \(y+F_0\) are disjoint, have area \(\det L_0\) each, and lie in the disc of radius \(3R\) about the centre, which lies in a square of area \(36R^2\). So each coset contributes at most \(36R^2/\det L_0\) points, and all together at most \(36mR^2/\det L_0=36R^2/\det L\).

(b) A vector of \(L\) outside \(\mathbb Rv_1\) has length at least \(\lambda_2>R\). The vectors of \(L\) on \(\mathbb Rv_1\) are the integer multiples of \(v_1\): this set is a subgroup of the line containing \(v_1\), generated by some \(w\), and \(\lambda_1\leq|w|\leq|v_1|=\lambda_1\). The multiples \(jv_1\) with \(|j|\lambda_1\leq R\) number at most \(1+2R/\lambda_1\). \(\square\)

Lemma 3.2 (integral planes). Let \(\Lambda\subseteq\mathbb Z^3\) be a lattice of rank three and index \(I\), let \(y\in\mathbb Z^3\setminus\{0\}\), and let \(g>0\) generate the subgroup \(y\cdot\Lambda=\{y\cdot v:v\in\Lambda\}\) of \(\mathbb Z\). Then \(\Lambda_y=\Lambda\cap y^\perp\) is a lattice of rank two with \[ \det\Lambda_y=\frac{I\,|y|}g . \] In particular, if \(y\) is primitive (its coordinates have greatest common divisor one), \(\mathbb Z^3\cap y^\perp\) has determinant \(|y|\).

Proof. The map \(v\mapsto(y\cdot v)/g\) sends \(\Lambda\) onto \(\mathbb Z\), with kernel \(\Lambda_y\). Choose \(u\in\Lambda\) with \(y\cdot u=g\). Every \(v\in\Lambda\) is \(\frac{y\cdot v}g\,u+\bigl(v-\frac{y\cdot v}gu\bigr)\), with the second term in \(\Lambda_y\); so \(\Lambda=\mathbb Zu\oplus\Lambda_y\). The group \(\Lambda_y\) is free (Lemma 5.1 of the lesson cited above) of rank \(2\), and a basis \(w_1,w_2\) of it together with \(u\) is a basis of \(\Lambda\). In orthonormal coordinates whose first two directions span \(y^\perp\), the matrix \((w_1,w_2,u)\) is block triangular, so \(I=\det\Lambda=\det\Lambda_y\cdot d_u\), using Lemma 1.1(a), where \(d_u=|y\cdot u|/|y|=g/|y|\) is the distance of \(u\) from \(y^\perp\). For \(\Lambda=\mathbb Z^3\) and primitive \(y\), \(g=1\) because the coordinates of \(y\) generate \(\mathbb Z\). \(\square\)

4. Three different column bounds

Lemma 4.1 (unequal column bounds). There is an absolute constant \(C\) such that for all reals \(R_1\geq R_2\geq R_3\geq1\) and every integer \(t\neq0\), the number of triples \(u_1,u_2,u_3\in\mathbb Z^3\) with \(|u_j|\leq R_j\) and \(\det(u_1,u_2,u_3)=t\) is at most \[ C\,(R_1R_2R_3)^2\bigl(\log(2R_1)\bigr)^2 . \]

Proof. The normal. Since \(t\neq0\), \(u_2,u_3\) are independent. Let \(y\) be the primitive integer vector orthogonal to both whose first nonzero coordinate is positive. The cross product \(u_2\times u_3\) is an integer vector on the line \(\mathbb Ry\), hence \(u_2\times u_3=ay\) with \(a\) a nonzero integer, and \(|y|\leq|u_2||u_3|\leq R_2R_3\). Let \(\mu_1\leq\mu_2\) be the successive lengths of \(L_y=\mathbb Z^3\cap y^\perp\), which has \(\det L_y=|y|\) (Lemma 3.2). The independent vectors \(u_2,u_3\in L_y\) give \(\mu_1\leq R_3\) and \(\mu_2\leq R_2\). Also \(|y|\leq\mu_1\mu_2\leq2|y|\) by Lemma 2.1.

Counting \(u_1\) and \(u_2\). For fixed \(u_2,u_3\) the condition is \(u_1\cdot y=t/a\); its integer solutions form a translate of \(L_y\) or are absent, and by Lemma 3.1(a) (with \(R_1\geq R_2\geq\mu_2\)) at most \(36R_1^2/|y|\) of them have \(|u_1|\leq R_1\). For fixed \(y\), at most \(36R_2^2/|y|\) vectors \(u_2\in L_y\) have \(|u_2|\leq R_2\).

Case \(\mu_2\leq R_3\). Then at most \(36R_3^2/|y|\) vectors \(u_3\in L_y\) have \(|u_3|\leq R_3\), and the number of triples with normal \(y\) is at most \(36^3(R_1R_2R_3)^2|y|^{-3}\). The integer vectors with \(Y\leq|y|<2Y\), for \(Y\geq1\), number at most \((4Y+1)^3\leq125Y^3\); summing over the dyadic shells \(Y=1,2,4,\ldots\leq R_2R_3\), each contributes at most \(125\), and there are at most \(1+\log_2(R_2R_3)\leq1+2\log_2(R_1)\) shells.

Case \(\mu_2>R_3\). Then every admissible \(u_3\) lies on the line of a shortest vector of \(L_y\), and there are at most \(1+2R_3/\mu_1\leq3R_3/\mu_1\) of them (Lemma 3.1(b), with \(\mu_1\leq R_3\)). Sort the normals by the powers of two \(U,Z\geq1\) with \(U\leq\mu_1<2U\) and \(Z\leq\mu_2<2Z\); then \(U\leq R_3\), \(Z\leq R_2\) and \(\frac12UZ\leq|y|<4UZ\). We claim that at most \(C_1U^4Z^2\) normals \(y\) have given \(U,Z\). Let \(z\) be a shortest nonzero vector of \(L_y\); it is primitive in \(\mathbb Z^3\) (dividing it by a common factor would give a shorter vector of \(L_y\)) and \(U\leq|z|<2U\), so there are at most \(125\cdot8U^3\) choices of \(z\). For fixed \(z\), the normal \(y\) lies in \(L_z=\mathbb Z^3\cap z^\perp\), of determinant \(|z|\), and \(|y|<4UZ\). The successive lengths \(\nu_1\leq\nu_2\) of \(L_z\) satisfy \(\nu_1\geq1\) (nonzero integer vectors) and \(\nu_1\nu_2\leq2|z|\), so \(\nu_2\leq2|z|<4U\leq4UZ\), and Lemma 3.1(a) gives at most \(36(4UZ)^2/|z|\leq576UZ^2\) choices of \(y\). This proves the claim. The triples with normals of given \(U,Z\) therefore number at most \[ \begin{aligned} &C_1U^4Z^2\cdot\frac{36R_1^2}{UZ/2}\cdot\frac{36R_2^2}{UZ/2}\cdot\frac{3R_3}U\\ &\quad=C_2R_1^2R_2^2R_3U\leq C_2(R_1R_2R_3)^2, \end{aligned} \] and there are at most \((1+\log_2R_3)(1+\log_2R_2)\) pairs \((U,Z)\).

Both cases together give the bound. \(\square\)

5. A fixed nonzero determinant

Proposition 5.1 (fixed nonzero determinant). There is an absolute constant \(C\) with the following property. Let \(\Lambda\subseteq\mathbb Z^3\) be a lattice of rank three and index \(I\), let \(X\geq2\), and suppose that the largest successive length satisfies \(\lambda_3\leq X\). Then for every integer \(t\neq0\), the number of \(3\times3\) integer matrices with all rows in \(\Lambda\), all rows of length at most \(X\), and determinant \(t\), is at most \[ C\,\bigl(\log(2X)\bigr)^2\frac{X^6}{I^2}. \]

Proof. Let \(V\) be the matrix with rows \(v_1,v_2,v_3\) (successive shortest vectors of \(\Lambda\)), and \(m=|\det V|/I\). By Lemma 2.1 and Lemma 1.1(a), \(m\) is a positive integer at most \(3^{3/2}\), and every \(u\in\Lambda\) is \(u=\sum_j\alpha_jv_j\) with \(\alpha_j\in m^{-1}\mathbb Z\). By Cramer's rule, \(\alpha_j\) is a determinant in which the row \(v_j\) of \(V\) is replaced by \(u\), divided by \(\det V\). The numerator is at most \(|u|\prod_{i\neq j}\lambda_i\) (the volume of a parallelepiped is at most the product of its edge lengths, by the triangular form used in Lemma 2.1), and \(|\det V|\geq\det\Lambda\geq3^{-3/2}\prod_i\lambda_i\). So for \(|u|\leq X\), \[ |\alpha_j|\leq3^{3/2}\frac X{\lambda_j}. \] Map a matrix \(A\) of the proposition to \(Q=mAV^{-1}\). The rows of \(Q\) are \(m\) times the coordinate vectors of the rows of \(A\), so \(Q\) is an integer matrix; the map is injective; and \(\det Q=m^3t/\det V\) is the same nonzero number for all \(A\) (if it is not an integer, there are no such \(A\)). The entries of the \(j\)-th column of \(Q\) have absolute value at most \(m3^{3/2}X/\lambda_j\leq27X/\lambda_j\), so the column has length at most \(R_j=27\sqrt3\,X/\lambda_j\). We have \(R_1\geq R_2\geq R_3\geq1\) (as \(\lambda_3\leq X\)); since nonzero vectors of \(\Lambda\subseteq\mathbb Z^3\) have length at least one, \(R_1\leq27\sqrt3\,X\); and \(R_1R_2R_3=(27\sqrt3)^3X^3/(\lambda_1\lambda_2\lambda_3)\), which is at most \((27\sqrt3)^3X^3/I\) by Lemma 2.1. Lemma 4.1 applied to the columns of \(Q\) gives the bound, since \(\log(2\cdot27\sqrt3X)\leq C'\log(2X)\) for \(X\geq2\). \(\square\)

The hypothesis \(\lambda_3\leq X\) is harmless in the application: there, \(\Lambda\) contains \(E\mathbb Z^3\) for an integer \(E\leq X\), so its three successive lengths are at most \(E\).

6. Exercises

6.1. Compute the index of the lattice spanned by \((2,1,0),(0,3,0),(1,1,5)\) in \(\mathbb Z^3\) and list a complete set of representatives as in the proof of Lemma 1.1.

6.2. For the plane lattice spanned by \((1,0)\) and \((0,100)\), compute \(\lambda_1,\lambda_2\), and check both parts of Lemma 3.1 for \(R=10\) and \(R=200\).

6.3. Show that \(\mathbb Z^3\cap y^\perp\) has determinant \(|y|\) for \(y=(1,2,2)\) by exhibiting a basis.

6.4. In Lemma 4.1, why can the bound not hold with \(t=0\)? Give a family of triples with determinant zero and \(|u_j|\leq R\) whose number is of order \(R^7\) or more.

6.5. Show that the hypothesis "rows in \(\Lambda\)" is what produces the factor \(I^{-2}\) in Proposition 5.1, by computing the count heuristically for \(\Lambda=E\mathbb Z^3\).

7. Solutions

6.1. With the vectors as columns, \(\det\begin{pmatrix}2&0&1\\1&3&1\\0&0&5\end{pmatrix}=5\det\begin{pmatrix}2&0\\1&3\end{pmatrix}=30\), so the index is \(30\). Integer column operations reach the lower triangular matrix \(\begin{pmatrix}1&0&0\\1&1&0\\5&10&30\end{pmatrix}\) with diagonal \(1,1,30\); the representatives are \((0,0,x_3)\) with \(0\leq x_3<30\), and \(\mathbb Z^3/\Lambda\) is cyclic of order \(30\).

6.2. \(\lambda_1=1\), \(\lambda_2=100\), \(\det L=100\). For \(R=10<\lambda_2\), the points of length at most \(10\) are \((j,0)\), \(|j|\leq10\): \(21=1+2R/\lambda_1\) points. For \(R=200\geq\lambda_2\), a ball of radius \(200\) contains at most \(36\cdot200^2/100=14400\) points; the actual number is about \(\pi\cdot200^2/100\approx1257\).

6.3. The vectors \((2,-1,0)\) and \((2,0,-1)\) are orthogonal to \(y\); they span \(\mathbb Z^3\cap y^\perp\) because a vector \((a,b,c)\) with \(a+2b+2c=0\) equals \(-b(2,-1,0)-c(2,0,-1)\). The area of the parallelogram is \(|(2,-1,0)\times(2,0,-1)|\), the length of \((1,2,2)\), which is \(3=|y|\).

6.4. If \(u_1=u_2\), the determinant vanishes for every \(u_3\): the triples \((u,u,w)\) with \(|u|,|w|\leq R\) number of order \(R^6\); more generally \(u_3\in\mathbb Zu_1+\mathbb Zu_2\) gives about \(R^6\cdot R^2/|u_1\times u_2|\) triples, of order \(R^7\) or more after summing. The proof of Lemma 4.1 uses \(t\neq0\) to make \(u_2,u_3\) independent and \(u_1\) lie on a single translate of \(L_y\).

6.5. For \(\Lambda=E\mathbb Z^3\), \(I=E^3\), and \(A=EA'\) with \(A'\) integral, \(\det A'=t/E^3\); the rows of \(A'\) have length at most \(X/E\), and the count of such \(A'\) is about \((X/E)^6\) up to logarithms (\(\det\) of a random matrix with entries of size \(Y\) is spread over about \(Y^3\) values, while there are \(Y^9\) matrices). This is \(X^6/I^2\).

References