SINGULAR SYMMETRIC MATRICES

ALEX ESKIN AND YONATAN R. KATZNELSON

Abstract. The varieties, S_{n,r}, of n×n symmetric matrices of rank r are studied, with the purpose of estimating the function N(T, n, r), which counts the number of integer points whose norm is bounded by T. When r = n − 1, we obtain the asymptotic formula

N(T, n, n − 1) = a(n)T^{n(n−1)/2} log T + O(T^{n(n−1)/2}(log T)^{1−ϵ(n)}).

For n − 1 > r ≥ 3 we obtain upper and lower bounds of the form

c_{1}(n, r)T^{nr/2} < N(T, n, r) < c_{2}(n, r)T^{nr/2},

for T sufficiently large, where c_{1}, c_{2} > 0. The case r = 2 has been resolved by W. Schmidt.

1. Introduction

Let S_{n,r} be the affine variety of n × n symmetric matrices of rank r;

S_{n,r} = {A ∈ ℂ^{n×n} : A = ^{t}A, rank(A) = r}.

We denote by S_{n,r}(ℤ) the integral points of S_{n,r}. Our purpose here is to analyze the counting function

N(T, n, r) = #{A ∈ S_{n,r}(ℤ) : ∥A∥ < T }.

∥A∥ denotes the standard Euclidean norm of a matrix in the space ℝ^{n×n}; ∥A∥^{2} = ∑_{ij} a_{ij}^{2}.

There is a natural correspondence between symmetric integral matrices of rank 2 and integral quadratic forms that are decomposable over the field ℚ of rational numbers. In this context Schmidt [11] proves that

N(T, n, 2) = α(n)T^{n} log T + \{ \begin{matrix}O (T^{3} log^{1/2} T ) & : & n = 3 \\ O (T^{n}) & : & n ≥ 4, \end{matrix} (1)

with α(n) > 0. In his work, Schmidt considers the slightly different norm ∥A∥_{1} = max_{ij} |a_{ij}|. We will give an indication of his argument a little further on.

The principal results here are the following two theorems

Theorem 1.1. For n ≥ 4

N(T, n, n − 1) = \frac{n(n − 1)V(n)V(n(n − 1)/2)}{2^{2+(n−1)(n−2)/4}ζ(n)}T^{n(n−1)/2} log T + O (T^{n(n−1)/2}(log T)^{1−ϵ(n)}) , (2)

as T tends to infinity. Here ϵ(n) = \frac{(n−2)}{n−2+(n−3)(n^{2}+2)/3}, which is strictly positive for n ≥ 3.

Eskin supported in part by a fellowship from the Sloan foundation, and Department of Education grant no.

P200A10022.A01.

Here and throughout the paper, V(k) is the volume of the unit ball in k dimensions, and ζ(k) is the Riemann zeta function. The notations ‘f(x) ≪ g(x)’ and ‘f(x) = O(g(x))’ mean that there exists a positive constant c such that |f(x)| < c|g(x)|, and ‘f(x) ≈ g(x)’ means f(x) ≪ g(x) ≪ f(x). Throughout the paper, the constants implied by these notations will depend only on n and/or r, unless explicitly stated otherwise.

Theorem 1.2. For n ≥ 4 and n − 2 ≥ r ≥ 3, and T sufficiently large

N(T, n, r) ≈ T^{nr/2}, (3)

It is interesting that while there is a factor of log T in the main terms of both N(T, n, 2) and N(T, n, n − 1), there is no such factor in the main term of N(T, n, r) for n − 2 ≥ r ≥ 3.

Rather than specify a rank, we could simply count the number of integral symmetric matrices of determinant 0. The corresponding question for determinant k ≠ 0 has been dealt with in a general setting by Duke, Rudnick and Sarnak [2], Eskin and McMullen [3], and Eskin, Mozes and Shah [4]. If we set

N^{k}(T, n) = {A ∈ S_{n,n}(ℤ) : ∥A∥ < T, det(A) = k},

then one has

N^{k}(T, n) ∼ c(n, k)T^{n(n−1)/2},

as T tends to infinity. Once again we note that there is no log factor. To obtain these results, one applies harmonic analysis to homogeneous quotients of affine symmetric spaces. These methods do not apply to the case of determinant 0 however, in part because the variety of singular symmetric matrices is highly singular as a variety. Indeed the singular set of the variety of symmetric matrices of determinant 0 is precisely S_{n,n−2}. This naturally leads one to consider the different singular ranks separately.

To obtain our results we apply and refine the methods of [7, 8]. In those papers the problem of counting integral matrices of fixed (singular) rank was considered, without the further restriction of symmetry. The basic observation exploited there, and here, is that the rows of a rank r integral matrix span an r dimensional lattice in ℤ^{n}. This suggests the following notation. For an r dimensional lattice Λ ⊂ ℝ^{n} we set

S(Λ) = {A ∈ ℝ^{n×n} : A = ^{t}A, rows of A are in Λ}.

Several facts are clear: S(Λ) is a lattice; if dim(Λ) = r and A ∈ S(Λ) then rank(A) ≤ r; if A ∈ S_{n,r}(ℤ) then there exists an r dimensional Λ ⊂ ℤ^{n} such that A ∈ S(Λ), e.g. the lattice spanned by the rows of A; Λ_{1} ⊂ Λ_{2} implies that S(Λ_{1}) ⊂ S(Λ_{2}). This last comment indicates that we should restrict our attention to primitive sublattices of ℤ^{n}.

Definition 1.1. An r dimensional lattice Λ ⊂ ℤ^{n} is primitive if it is not properly contained in any other r dimensional sublattice of ℤ^{n}.

For any lattice Ξ in ℝ^{n} or ℝ^{n×n} we set

N(T, Ξ) = #(Ξ ∩ B(T)),

where B(T) is the ball of radius T centered at the origin in the subspace spanned by Ξ over ℝ. For an r dimensional lattice Λ ∈ ℤ^{n} we write

N(T, S(Λ)) = N_{1}(T, S(Λ)) + N_{2}(T, S(Λ))

where N_{1} counts the matrices of rank exactly r and N_{2} counts those of rank < r.

Proposition 1.1.

N(T, n, r) = ∑_{dim(Λ)=r}′N_{1}(T, S(Λ)),

where the prime indicates that the sum extends over primitive lattices in ℤ^{n}.

Proof: This amounts to the observation that if A ∈ S(Λ_{1}) ∩ S(Λ_{2}), for two distinct primitive r dimensional lattices Λ_{1} and Λ_{2}, then A has rank strictly less than r. We remark that the sum on the right is in fact finite since N_{1}(T, S(Λ)) = 0 for all but finitely many lattices, as we shall see in §4.

Notation: Throughout this paper i, j, k, m, n, r, s will denote integers. Positive constants may be denoted c, c_{1}, c_{2}, etc., when they are absolute, or depend at most on the dimensions involved. When constants depend on a function or a parameter, we will denote them by c_{f}, c_{f}(ρ), etc., or state the dependence explicitly. We use lower case greek letters to denote arbitrary real numbers as the need arises, where ε will generally denote a small positive number. l and u will frequently be used to denote vectors in ℝ^{n}.

The authors wish to thank Z. Rudnick, P. Sarnak and W. Schmidt for their comments and suggestions.

2. Lattices

We collect here some basic facts about lattices, and set some notation. The proofs of facts stated here without reference may be found in [1, 5, 12].

We denote lattices in ℝ^{n} by Λ. The dimension of Λ is the dimension of the subspace, E_{Λ}, spanned by Λ over ℝ. Every r dimensional lattice Λ has an integral basis, {u_{1}, …, u_{r}}, which spans Λ over ℤ. The determinant of Λ, d(Λ), is the r dimensional volume of the parallelepiped spanned by an integral basis of Λ in E_{Λ}; it is independent of the choice of basis. Denote by L the symmetric matrix whose coefficients are the pairwise inner products (u_{i}, u_{j}) of the elements of a basis for Λ, then

d(Λ)^{2} = | det(L)|. (4)

For vectors other than matrices, we will denote the standard Euclidean norm by | · |.

Definition 2.1. A basis {l_{1}, …, l_{r}} of Λ is reduced if it minimizes the product ∏_{i=1}^{r} |l_{i}|, among all integral bases of Λ.

This is not the classical definition, but is equivalent to that definition, and somewhat easier to state. By the fundamental theorem of Minkowski there exist constants γ_{r} > 0 (depending only on r) such that

|l_{1}| ⋯ |l_{r}| ≥ d(Λ) ≥ γ_{r}|l_{1}| ⋯ |l_{r}|, (5)

for any r-dimensional lattice Λ with reduced basis {l_{1}, …, l_{r}}. The left hand inequality is trivial, being satisfied by any basis. Thus, in some sense, a reduced basis is ‘almost orthogonal’.

Definition 2.2. The successive minima, μ_{1}, …, μ_{r}, of an r dimensional lattice Λ are defined as follows. For 1 ≤ k ≤ r, μ_{k} is the infimum over all positive numbers x such that the set B(x) ∩ Λ contains k linearly independent elements. When more than one lattice is being considered, we will sometimes specify by writing μ_{j}(Λ) for the j^{th} successive minimum of Λ.

The successive minima of Λ are closely related to the lengths of a reduced basis, {l_{1}, …, l_{r}}, for Λ. Indeed we have |l_{1}| = μ_{1} and for j = 2 … r

|l_{j}| ≥ μ_{j} ≫ |l_{j}|, (6)

where the implied constants depend only on j, and thus are uniformly bounded [12]. We adopt the convention that all bases are ordered from shortest vector to longest vector. The following lemma is essentially a reformulation of Minkowski’s theorem.

Lemma 2.1. Let {l_{1}, …, l_{r}} be a reduced basis for Λ, then

|∑_{j=1}^{r} a_{j}l_{j}|^{2} ≥ δ_{r}δ_{r−1} ⋯ δ_{1} ∑_{j=1}^{r} a_{j}^{2}|l_{j}|^{2},

where δ_{j} = 1 − (1 − γ_{j}^{2})^{1/2} > 0, and depends only on j.

Proof: The proof is by induction. We first remark that if {l_{1}, …, l_{r}} is a reduced basis, then for 1 ≤ k ≤ r, {l_{1}, …, l_{k}} is a reduced basis for the lattice, Λ_{k}, which they span [12]. Clearly |a_{1}l_{1}|^{2} = a_{1}^{2}|l_{1}|^{2} (and δ_{1} = 1), so assume that for 2 ≤ k ≤ r

|∑_{j=1}^{k−1} a_{j}l_{j}|^{2} ≥ δ_{k−1} ⋯ δ_{1} ∑_{j=1}^{k−1} a_{j}^{2}|l_{j}|^{2}.

It is sufficient to prove that |u + al_{k}|^{2} ≥ δ_{k}(|u|^{2} + a^{2}|l_{k}|^{2}), for any u ∈ Λ_{k−1}. By Minkowski’s theorem, (5), it follows that

d(Λ_{k}) ≥ γ_{k}|l_{k}||l_{k−1}| ⋯ |l_{1}| ≥ γ_{k}|l_{k}|d(Λ_{k−1}).

¿From elementary geometry we have d(Λ_{k}) = |l_{k}|d(Λ_{k−1}) sin θ_{k}, where θ_{k} is the angle between l_{k} and the subspace E_{Λ_{k−1}}. Hence sin θ_{k} ≥ γ_{k} and therefore cos θ_{k} ≤ (1 − γ_{k}^{2})^{1/2} = 1 − δ_{k}. Thus for any u ∈ Λ_{k−1}

|(u, l_{k})| ≤ (cos θ_{k})|u||l_{k}| ≤ (1 − δ_{k})|u||l_{k}|.

But now we are done by the triangle inequality.

Lemma 2.2. Let Λ be an r dimensional lattice with reduced basis {l_{1}, …, l_{r}}. Let {u_{1}, …, u_{r}} be another basis of Λ satisfying

d(Λ) ≥ C|u_{1}| ⋯ |u_{r}|,

for some C > 0. Then for 1 ≤ j ≤ r

|u_{j}| ≈ |l_{j}|,

with the implied constants depending only on r and C.

Proof: Set β_{j} = |l_{j}|/|u_{j}|, then from the definition of the successive minima and (6) it follows that α ≥ β_{j} > 0 where α depends only on r. Let j_{0} be an arbitrary index between 1 and r, then

β_{j_{0}}α^{r−1} ≥ β_{j_{0}} ( ∏_{j≠j_{0}} β_{j}) ≥ C,

where the right hand inequality follows from our assumption and the fact that ∏ |l_{j}| ≥ d(Λ) always. Hence β_{j_{0}} ≥ α^{1−r}C.

In what follows we will be dealing with lattices (of symmetric matrices) for which we will have bases that are not necessarily reduced, but which satisfy the condition of the lemma above. Thus the purpose of the lemma is to give us estimates on the successive minima of such lattices. We also note that the inequality of Lemma 2.1 remains valid for a basis satisfying the condition of Lemma 2.2, the only difference being that the product of δ’s is replaced by a possibly smaller positive constant that may depend on the constant C appearing there, but remains independent of Λ.

Analyzing the counting functions N(T, n, r) depends on obtaining good estimates for the simpler counting functions N(T, Λ), for various lattices Λ. When the successive minima (equivalently, the lengths of the elements of a reduced basis) of the lattice Λ are uniformly bounded then an elementary argument yields the following

Proposition 2.3. Let Λ be an r dimensional lattice with reduced basis {l_{1}, …, l_{r}}, and assume that |l_{r}| ≤ c. Then for T ≥ 1

N(T, Λ) = \frac{V(r)T^{r}}{d(Λ)} + O (\frac{T^{r−1}}{d(Λ)} ) ,

where the implied constant depends on c and r.

Proof: Denote by P the fundamental parallelepiped spanned by {l_{1}, …, l_{r}}. Let {u_{1}, …, u_{N}}, N = N(T, Λ), be the points of Λ ∩ B(T), and set

P (T) = ⋃_{j=1}^{N}(u_{j} + P).

The symmetric difference B(T)△P (T) is contained in the set of points whose distance from the boundary ∂(B(T)) is less than the diameter of P. The diameter of P is less than r · |l_{r}| ≤ r · c, so

|vol(B(T)) − vol(P (T))| ≪ T^{r−1}.

Now, vol(P (T)) = d(Λ) · N(T, Λ), so

d(Λ) · N(T, Λ) = vol(B(T)) + O(T^{r−1}),

and dividing by d(Λ) completes the proof, since vol(B(T)) = V(r)T^{r}.

In the more general case, when the successive minima of the lattices may be quite large, Schmidt [10] provides the following

Lemma 2.4. Let Λ be an r dimensional lattice with reduced basis {l_{1}, …, l_{r}}. Then

N(T, Λ) = \frac{V(r)T^{r}}{d(Λ)} + O (∑_{j=1}^{r} \frac{T^{r−j}}{|l_{1}| ⋯ |l_{r−j}|}) ,

where the empty product corresponding to j = r on the right hand side is set equal to 1. The implied constant depends only on r.

We will be concerned mostly with sublattices of ℤ^{n}, and in this context we require a bit more terminology. Let Λ be a primitive r-dimensional sublattice of ℤ^{n}. The dual lattice Λ^{⊥} ⊂ ℤ^{n} is the primitive n − r-dimensional lattice of integer vectors that are orthogonal to E_{Λ}. The polar lattice Λ^{p} is the lattice of all (rational) vectors in E_{Λ} having integral inner product with the elements of Λ. Denote by π_{Λ} the orthogonal projection onto E_{Λ}^{⊥}. The factor lattice Λ^{⋆} = ℤ^{n}/Λ is the image of ℤ^{n} by π_{Λ}. We have the following basic facts

Lemma 2.5. For a primitive r dimensional Λ ⊂ ℤ^{n}, the following identities hold:

• d(Λ^{⊥}) = d(Λ).

• d(Λ^{p}) = d(Λ)^{−1}.

• Λ^{⋆} = (Λ^{⊥})^{p}. Thus d(Λ^{⋆}) = d(Λ)^{−1}.

Proof: See [10].

We will be summing various functions over sets of primitive r-dimensional lattices, often defined in terms of a bound on the size of their determinant. We will use the method of summation by parts for this, and so require an estimate for the number of such lattices. Let P (X, n, r) denote the number of primitive r dimensional sublattices of ℤ^{n}, with determinant bounded by X. The following result of Schmidt is fundamental.

Theorem [10]

P (X, n, r) = a(n, r)X^{n} + O (X^{n−b(n,r)}) , (7)

where

a(n, r) = \frac{1}{n} \binom{n}{r} \frac{V(n)V(n − 1) ⋯ V(n − r + 1)}{V(1)V(2) ⋯ V(r)} · \frac{ζ(2)ζ(3) ⋯ ζ(r)}{ζ(n)ζ(n − 1) ⋯ ζ(n − r + 1)},

(with the empty product of ζ’s, corresponding to r = 1, set equal to 1), and where

b(n, r) = max(1/r, 1/(n − r)).

Definition 2.3. For a number c > 0, we say that an r-dimensional lattice Λ is c-regular if

μ_{1}(Λ) ≥ c · d(Λ)^{1/r}.

Denote by P (X, n, r, c) the number of primitive c-regular r-dimensional sublattices of ℤ^{n} with determinant bounded by X. A modification of Schmidt’s proof yields the following

Proposition 2.6. Let n ≥ 2 and n − 1 ≥ r ≥ 1. There exist constants c(n, r) > 0 and d(n, r) > 0 such that for X sufficiently large and c(n, r) ≥ c > 0, P (X, n, r, c) ≥ d(n, r)X^{n}.

In other words, a positive proportion of r-dimensional sublattices of ℤ^{n} are c(n, r)-regular. This proposition is used in establishing the lower bound in Theorem 1.2. We begin with two lemmas.

Lemma 2.7. Let 1 ≤ r − 1 ≤ n − 2 and Λ_{1} ⊂ ℤ^{n} be a primitive c_{1}-regular r − 1-dimensional lattice. Assume that Λ_{2} ⊂ ℤ^{n} is primitive r-dimensional, Λ_{1} ⊂ Λ_{2} and c_{2}d(Λ_{1})^{r/(r−1)} ≤ d(Λ_{2}) ≤ c_{3}d(Λ_{1})^{r/(r−1)}, with c_{3} > c_{2} > 0. Then Λ_{2} is c_{4}-regular with c_{4} > 0 depending only on the dimensions, c_{1}, c_{2} and c_{3}.

Proof: If μ_{1}(Λ_{1}) = μ_{1}(Λ_{2}) then the lemma follows from the regularity of Λ_{1} and the bounds on d(Λ_{2}). If not then there is a vector l_{0} ∈ Λ_{2} \ Λ_{1} with |l_{0}| = μ_{1}(Λ_{2}) < μ_{1}(Λ_{1}). Now l_{0} and a reduced basis for Λ_{1} span a sublattice of finite index in Λ_{2}, whence by Minkowski’s theorem |l_{0}|μ_{1}(Λ_{1}) ⋯ μ_{k−1}(Λ_{1}) ≫ d(Λ_{2}). Dividing both sides by the product of the successive minima of Λ_{1}, together with the bounds on d(Λ_{2}) yields the desired lower bound for |l_{0}|.

Lemma 2.8. Let Λ ⊂ ℤ^{n} be a primitive c_{1}-regular r-dimensional lattice, n − 1 ≥ r > 1. The number of primitive r − 1-dimensional sublattices Λ′ ⊂ Λ satisfying

d(Λ′) ≤ c_{2}d(Λ)^{(r−1)/r} (8)

is bounded. The bound depends only on n, r, c_{1} and c_{2}.

Proof: For a constant c > 0, the number of vectors in Λ of length less than c · d(Λ)^{1/r} is uniformly bounded in terms of c, c_{1} and r. This follows immediately from Lemma 2.4 and the fact that |l_{j}| ≥ c_{1}d(Λ)^{1/r} for every element l_{j} of a reduced basis of Λ.

If Λ′ ⊂ Λ satisfies (8), it follows that Λ′ is itself c_{3}-regular, with c_{3} ≥ c_{1}/c_{2}^{1/(r−1)}. Hence the elements of a reduced basis for Λ′ are all bounded in length by c · d(Λ)^{1/r}, where c = γ_{r−1}c_{2}/c_{1}^{r−2}. Thus by the first paragraph, the number of such sublattices is bounded independently of Λ. Proof (of 2.6): The proof is by induction on r. Fix n ≥ 2. When r = 1 the claim is trivial since every 1-dimensional lattice is 1-regular. Assume now that the proposition holds for r − 1 ≤ n − 2. We choose X sufficiently large so that P (X^{(r−1)/r}/2, n, r − 1, c) ≥ d(n, r − 1)(X^{(r−1)/r}/2)^{n} when c(n, r − 1) ≥ c > 0.

Given a primitive c_{1}-regular (c_{1} = c(n, r − 1)) Λ ⊂ ℤ^{n} of dimension r − 1, (for which we assume d(Λ) < X^{(r−1)/r}), we wish to construct primitive c_{2}-regular r-dimensional lattices Λ′ ⊂ ℤ^{n} containing Λ. For v ∈ ℤ^{n} \ Λ we denote by Λ ⊕ v the lattice spanned by Λ and v. It is immediate that Λ ⊕ v = Λ ⊕ w if and only if π_{Λ}(v) = ±π_{Λ}(w). Furthermore Λ ⊕ v is a primitive lattice if and only if π_{Λ}(v) is a primitive vector in Λ^{⋆} (see [10]). Finally, we note that d(Λ ⊕ v) = |π_{Λ}(v)| · d(Λ).

Thus to each pair {u, −u} of primitive vectors in Λ^{⋆}, there corresponds a primitive r-dimensional lattice Λ_{u} = Λ ⊕ v_{u}, where v_{u} ∈ π_{Λ}^{−1}(u) ⊂ ℤ^{n}. If we specify that

d(Λ)^{1/(r−1)} < |u| < 2d(Λ)^{1/(r−1)}, (9)

then d(Λ)^{r/(r−1)} < d(Λ_{u}) < 2d(Λ)^{r/(r−1)}, and by Lemma 2.7 Λ_{u} is c_{2}-regular. Let E(T, n, r − 1, c_{1}) denote the set of primitive c_{1}-regular r − 1-dimensional lattices Λ ⊂ ℤ^{n}, with d(Λ) < T, and let N_{p}(T, Λ^{⋆}) be the number of primitive points in Λ^{⋆} ∩B(T). If d(Λ) < X^{(r−1)/r}/2 and u ∈ Λ^{⋆} satisfies (9), then d(Λ_{u}) < X. Thus setting E_{X} = E(X^{(r−1)/r}/2, n, r − 1, c_{1}) we have

P (X, n, r, c_{2}) ≫ ∑_{Λ∈E_{X}}[N_{p}(2d(Λ)^{1/(r−1)}, Λ^{⋆}) − N_{p}(d(Λ)^{1/(r−1)}, Λ^{⋆})] (10)

since by Lemma 2.8 we are overcounting by at most a fixed constant factor independent of X.

We require an estimate for the number of primitive vectors in Λ^{⋆} satisfying the condition in (9). A theorem of Mahler [9] implies that for 1 ≤ j ≤ k

μ_{j}(Λ) ≪ μ_{k−j+1}(Λ^{p})^{−1} (11)

for any k-dimensional lattice Λ. (The constant implied by Mahler’s result is k!. This has been improved to k^{2} by Lenstra and Schnorr [5].) In particular, this implies

μ_{1}(Λ^{⋆}) ≫ μ_{n−r+1}^{−1}(Λ^{⊥}) ≫ d(Λ^{⊥})^{−1} = d(Λ)^{−1}. (12)

Furthermore, it follows from (11) that the successive minima of Λ^{⋆} = (Λ^{⊥})^{p} are bounded independently of Λ ⊂ ℤ^{n}, since μ_{1}(Λ^{⊥}) ≥ 1. So by Proposition 2.3 for a variable τ > 1

N(τ, Λ^{⋆}) = V(n − r + 1)τ^{n−r+1}/d(Λ^{⋆}) + O(τ^{n−r}/d(Λ^{⋆})). (13)

On the other hand

N(τ, Λ^{⋆}) = ∑_{j=1}^{ξτd(Λ)} N_{p}(τ/j, Λ^{⋆}),

since N_{p}(τ/j, Λ^{⋆}) = 0 when j > ξτd(Λ) ≥ μ_{1}(Λ^{⋆}), where ξ is the constant (which is independent of Λ) implied by (12). Now, by the Möbius inversion principle [6]

N_{p}(τ, Λ^{⋆}) = ∑_{j=1}^{ξτd(Λ)} μ(j)N(τ/j, Λ^{⋆}). (14)

Here, μ(j) is the Möbius function and shouldn’t be confused with the successive minima of the lattice. Inserting (13) in (14) we have

N_{p}(τ, Λ^{⋆}) = \frac{V(n − r + 1)τ^{n−r+1}}{d(Λ^{⋆})} ( ∑_{j=1}^{ξτd(Λ)} μ(j)j^{r−n−1} + O (τ^{−1} ∑_{j=1}^{ξτd(Λ)} j^{r−n}))

(15)  = \frac{V(n − r + 1)τ^{n−r+1}}{ζ(n − r + 1)d(Λ^{⋆})} (1 + O(τ^{−1} log(τd(Λ)))),

since n − r ≥ 1.

Now, for d(Λ) sufficiently large and τ ≥ d(Λ)^{1/(r−1)}, the ‘O’ term on the right of (15) is less than 1/3 in absolute value, whence

\frac{4}{3} \frac{V(n − r + 1)τ^{n−r+1}}{ζ(n − r + 1)d(Λ^{⋆})} > N_{p}(τ, Λ^{⋆}) > \frac{2}{3} \frac{V(n − r + 1)τ^{n−r+1}}{ζ(n − r + 1)d(Λ^{⋆})} .

Thus, for d(Λ) sufficiently large

N_{p}(2d(Λ)^{1/(r−1)}, Λ^{⋆}) − N_{p}(d(Λ)^{1/(r−1)}, Λ^{⋆}) > \frac{4V(n − r + 1)}{3ζ(n − r + 1)} \frac{d(Λ)^{\frac{n−r+1}{r−1}}}{d(Λ^{⋆})}
= \frac{4V(n − r + 1)}{3ζ(n − r + 1)}d(Λ)^{\frac{n}{r−1}} ,

since d(Λ^{⋆}) = d(Λ)^{−1}, by Lemma 2.5, and n − r + 1 ≥ 2. Inserting this estimate in (10) we have for X sufficiently large

P (X, n, r, c_{2}) ≫ ∑_{Λ∈E_{X}} d(Λ)^{\frac{n}{r−1}} ≫ X^{n},

using summation by parts and the induction hypothesis for r − 1.

3. Symmetric Matrices

For (row) vectors u, v ∈ ℝ^{n}, we define their tensor product

u⊗v =^{def} ^{t}u · v.

The operation on the right is just matrix multiplication, resulting in an n × n matrix. A direct computation shows that

(u⊗v, u′⊗v′) = (u, u′)(v, v′), (16)

where (·, ·) is the standard inner product in the appropriate Euclidean space. Note that u⊗u and u⊗v + v⊗u are both symmetric matrices.

Proposition 3.1. For n ≥ 3

N(T, n, 1) = \frac{V(n)ζ(n/2)}{2ζ(n)}T^{n/2} + \{ \begin{matrix}O (T log T) & : & n = 3 \\ O (T^{(n−1)/2}) & : & n ≥ 4. \end{matrix}

Proof: If A ∈ S_{n,1}(ℤ) then A has at least one nonzero row, and all other rows are multiples of this row. This and the condition of symmetry together imply that A = m · (u⊗u) for a primitive u ∈ ℤ^{n} and m ∈ ℤ. Furthermore, for two primitive vectors u, v ∈ ℤ^{n}, m_{1}(u⊗u) = m_{2}(v⊗v) if and only if m_{1} = m_{2} and u = ±v. By (16) ∥A∥ = m|u|^{2}, and so

N(T, n, 1) = ∑_{m<T} P ((T/m)^{1/2}, n, 1)

= a(n, 1)T^{n/2} ∑_{m<T} m^{−n/2} + O (T^{(n−1)/2} ∑_{m<T} m^{(1−n)/2}) .

The first sum in the second row yields ζ(n/2) + O(T^{1−(n/2)}), while the second sum is O(log T) when n = 3 and is uniformly bounded when n ≥ 4. The constant in the main term comes from the formula (7) in Schmidt’s theorem.

The proof of Schmidt’s result for N(T, n, 2) follows from the similar observation that if A ∈ S_{n,2}(ℤ) then A = u⊗v + v⊗u, for two noncolinear vectors u, v ∈ ℤ^{n}. This leads to evaluating a sum of the form

∑_{|u||v|<T} 1,

over vectors in ℤ^{n}. This gives a main term on the order of T^{n} log T. The factor of log T can be seen to come from the behavior of the divisor function d(n).

Recall the notation from §1. For Λ ⊂ ℤ^{n} we denote by S(Λ) the lattice of symmetric matrices in ℤ^{n×n} whose rows are in Λ. The first order of business is determining an integral basis for S(Λ) and to do so we fix a reduced basis of Λ, {l_{1}, …, l_{r}}. For 1 ≤ i ≤ r set

L_{ii} = l_{i}⊗l_{i}

and for 1 ≤ i < j ≤ r set

L_{ij} = l_{i}⊗l_{j} + l_{j} ⊗l_{i}.

Lemma 3.2.

\begin{aligned}(L_{ii}, L_{jj}) & = & (l_{i}, l_{j})^{2} \\ (L_{ii}, L_{st}) & = & 2(l_{i}, l_{s})(l_{i}, l_{t}) \\ (L_{ij}, L_{st}) & = & 2[(l_{i}, l_{s})(l_{j}, l_{t}) + (l_{i}, l_{t})(l_{j}, l_{s})]. \end{aligned}

In particular, for 1 ≤ i ≤ j ≤ r

|l_{i}||l_{j}| ≤ |L_{ij}| ≤ 2|l_{i}||l_{j}|.

Proof: This follows immediately from (16).

Proposition 3.3. The set {L_{ij} : 1 ≤ i ≤ j ≤ r} is an integral basis for S(Λ).

Proof: Assume that A = ∑ a_{ij}L_{ij} = 0, denote the rows of A by A_{k}. It follows that for 1 ≤ k ≤ n, A_{k} = ∑_{1}^{r} α_{k}^{j}l_{j} = 0, where

α_{k}^{j} = ∑_{s=1}^{r} a_{js}l_{s}^{k},

and l_{s}^{k} is the k^{th} component of l_{s}. By the linear independence of {l_{s}}_{1}^{r}, we see that α_{k}^{j} = 0 for 1 ≤ k ≤ n and 1 ≤ j ≤ r. Thus for any 1 ≤ j ≤ r, it follows from the definition of α_{k}^{j} above and the linear independence of the {l_{s}} that a_{js} = 0, 1 ≤ s ≤ r. Thus {L_{ij}} is an independent set.

Next assume that A ∈ S(Λ) so

A = ∑_{j=1}^{r} u_{j} ⊗ l_{j},

with u_{j} ∈ ℤ^{n}. Thus A = U · L, where U is the n × r matrix with the ^{t}u_{j}’s as columns and L is the r × n matrix with the l_{j}’s as rows. Now, since rank(L) = r it follows that rank(A) = rank(U). Hence the subspace E_{1} (over ℝ) spanned by the u′_{j}s is the same as the subspace spanned by the rows of A, since the columns of A are linear combinations of the ^{t}u′_{j}s, and A is symmetric. But the rows of A are contained in Λ so E_{1} ⊂ E_{Λ}, (the subspace spanned over ℝ by Λ). Finally, since Λ is primitive Λ = E_{Λ} ∩ ℤ^{n} and in particular each u_{j} is in Λ. Writing u_{i} as a linear combination of the l_{j}’s we obtain

A = ∑_{i,j=1}^{r} a_{ij}l_{i}⊗l_{j} = ∑_{i,j=1}^{r} a_{ij}l_{j} ⊗l_{i},

where the right hand equality follows once again from symmetry. Linear independence implies that a_{ij} = a_{ji} so that we may collect terms and conclude that

A = ∑_{1≤i≤j≤r} a_{ij}L_{ij}.

It follows that S(Λ) has dimension r(r + 1)/2.

We now calculate the determinant d(S(Λ)). Denote by dμ the standard Lebesgue measure on S_{n,n}(ℝ). For g ∈ GL(n, ℝ) let F_{g} : S_{n,n} → S_{n,n} be the linear map A → gA^{t}g. By linearity F_{g}^{∗}(dμ) = δ(g)dμ for some scalar function δ(g). We have δ(gh) = δ(g)δ(h) so that δ is a homomorphism from GL(n, ℝ) to ℝ. Such a homomorphism must be trivial on SL(n, ℝ), since this group is simple, and hence δ(g) = det(g)^{α} for some α.

Proposition 3.4.

δ(g) = det(g)^{n+1}.

Proof: Let g be a diagonal matrix and compute.

Lemma 3.5.

d(S(Λ)) = 2^{r(r−1)/4}d(Λ)^{r+1}.

Proof: Let {l_{1}, …, l_{r}} be an integral basis for Λ and let {f_{r+1}, …, f_{n}} be an orthonormal basis for the orthogonal complement in ℝ^{n} of the subspace spanned by Λ. Denote by Λ̃ the lattice spanned by {l_{1}, …, l_{r}, f_{r+1}, …, f_{n}}. Let g ∈ GL(n, ℝ) be a linear map that takes Λ̃ to ℤ^{n} then it follows that

| det(g)|^{−1} = d(Λ̃) = d(Λ).

Furthermore, F_{g} takes S(Λ̃) to S_{n,n}(ℤ), and so by the previous lemma,

d(S(Λ̃)) = d(Λ)^{n+1}d(S_{n,n}(ℤ)) = 2^{n(n−1)/4}d(Λ)^{n+1}. (17)

The second equality follows from (4) and Lemma 3.2 applied to S_{n,n}(ℤ). Applying (4) to S(Λ̃) yields

d(S(Λ̃)) = 2^{n(n−1)/4−r(r−1)/4}d(S(Λ))d(Λ)^{n−r},

and combining this with (17) completes the proof. Comment:

d(Λ)^{r+1} ≫ |l_{1}|^{r+1} ⋯ |l_{r}|^{r+1} ≫ ∏_{1≤i≤j≤r} |L_{ij}|,

so that the basis we have constructed satisfies the condition of Lemma 2.2 applied to the lattice S(Λ). Thus the successive minima of S(Λ) are, to within a uniform multiplicative factor, the pairwise products of the successive minima of the lattice Λ.

4. Upper and Lower Bounds

In order to evaluate the sum in Proposition 1.1, it is first necessary to determine the set of primitive r dimensional lattices in ℤ^{n} for which N_{1}(T, S(Λ)) > 0.

Lemma 4.1. Let Λ ⊂ ℤ^{n} be a primitive r dimensional lattice with reduced basis {l_{1}, …, l_{r}}. Then N_{1}(T, S(Λ)) > 0 implies that

|l_{i}||l_{j}| ≪ T (18)

for all pairs (i, j) such that i + j ≤ r + 1.

Proof: Let A ∈ S(Λ), with |A| ≤ T. We write

A = ∑_{1≤i≤j≤r} a_{ij}L_{ij},

with a_{ij} ∈ ℤ. From Lemma 2.1 it follows that a_{ij} ≠ 0 implies |L_{ij}| ≤ c_{1}T, for an appropriate c_{1}, which depends only on r. Let c_{2} = 2c_{1}, and assume that |l_{i}||l_{j}| > c_{2}T for some pair of indices (i, j), with i + j = r + 1. Now for s ≥ i and t ≥ j we have

|L_{st}| ≥ |l_{s}||l_{t}| ≥ |l_{i}||l_{j}| ≥ 1/2|L_{ij}| > c_{1}T,

so that a_{st} = 0 for all such pairs. We now show that it follows from this that rank(A) ≤ r − 1, and hence that N_{1}(T, S(Λ)) = 0.

Since this is now a question of linear dependence, we may assume that Λ is in fact spanned by the first r standard unit vectors, and thus the last n − r rows and columns of A are all 0’s. Hence the rank of A is the rank of the first r × r minor. From our assumption it follows that the last r − i + 1 = j rows of this minor have 0’s in their last r − j + 1 = i columns, so that they span at most an r − i = j − 1 dimensional space. Thus these last j rows are linearly dependent and rank(A) ≤ r − 1.

Corollary 4.2. If N_{1}(T, S(Λ)) > 0 then d(Λ) ≪ T^{r/2}.

Proof: Assume that N_{1}(T, S(Λ)) > 0. By the previous lemma this implies that

(c_{2}T)^{r} ≥ ∏_{i+j=r+1} |l_{i}||l_{j}| = (|l_{1}| ⋯ |l_{r}|)^{2} ≥ d(Λ)^{2},

with c_{2} as above.

We now establish an upper bound for N(T, n, r). But first, some more notation. Let E(T, n, r) be the set of primitive r dimensional lattices Λ ⊂ ℤ^{n}, for which N_{1}(T, S(Λ)) > 0. In particular, the reduced bases of such lattices satisfy (18). Let E^{⋆}(T, n, r) be the set of primitive r dimensional sublattices of ℤ^{n} that satisfy d(Λ) ≤ (c_{2}T)^{r/2}. For fixed c > 0 let E(T, n, r, c) be the subset of E^{⋆} that are c-regular. By Corollary 4.2 E(T, n, r) ⊂ E^{⋆}(T, n, r), and by choosing c sufficiently small, we may assume that E(T, n, r, c) ⊂ E(T, n, r).

Theorem 4.1. For n ≥ 4 and T sufficiently large,

N(T, n, n − 1) = O (T^{n(n−1)/2} log T ) ,

and for n − 2 ≥ r ≥ 3

N(T, n, r) = O (T^{nr/2}) .

Proof: By Proposition 1.1, and the definitions above

N(T, n, r) = ∑_{E(T,n,r)} N_{1}(T, S(Λ)) < ∑_{E(T,n,r)} N(T, S(Λ)).

By Lemma 2.4 and Lemma 3.5

N(T, S(Λ)) = \frac{V(r(r + 1)/2)T^{r(r+1)/2}}{2^{r(r−1)/4}d(Λ)^{r+1}} + O (∑_{k=1}^{ϱ} \frac{T^{ϱ−k}}{ν_{1}ν_{2} ⋯ ν_{ϱ−k}} ) , (19)

where ϱ = r(r+1)/2. In this equation on the right hand side and in the following equation on the left hand side, the term in the sum corresponding to k = ϱ is set equal to 1. The ν_{j}’s are the successive minima of S(Λ). By the comments at the end of §3, these successive minima are essentially the pairwise products |l_{i}||l_{j}|, for a reduced basis {l_{1}, …, l_{r}} of Λ. For a fixed Λ

∑_{k=1}^{ϱ} \frac{T^{ϱ−k}}{ν_{1}ν_{2} ⋯ ν_{ϱ−k}} ≪ ∏_{1≤i≤j≤r}′ max (1, \frac{T}{|l_{i}||l_{j}|}) , (20)

where the prime on the product indicates that the factor ‘max(1, T/|l_{r}|^{2})’ is omitted (this corresponds to omitting the largest successive minimum). The product is a combinatorial manipulation which captures the largest term in the sum. It follows that

N(T, n, r) ≪ T^{r(r+1)/2} ∑_{E(T,n,r)} d(Λ)^{−(r+1)} + E_{1}(T, n, r), (21)

where E_{1} is the sum over E(T, n, r) of the product in (20). For the sake of continuity, we defer the evaluation of all the remainder terms to §7. It is established there that for r ≥ 3, E_{1}(T, n, r) = O(T^{nr/2}). Since E(T, n, r) ⊂ E^{⋆}(T, n, r)

∑_{E(T,n,r)} d(Λ)^{−(r+1)} < ∑_{E^{⋆}(T,n,r)} d(Λ)^{−(r+1)},

and we evaluate the sum on the right by applying summation by parts together with Schmidt’s formula (7). For r = n − 1 this yields

∑_{E^{⋆}(T,n,n−1)} d(Λ)^{−n} = \frac{n(n − 1)V(n)}{4ζ(n)} log T + O(1), (22)

and for n − 2 ≥ r ≥ 3

∑_{E^{⋆}(T,n,r)} d(Λ)^{−(r+1)} ≪ T^{r(n−r−1)/2}.

Substituting these estimates in (21), together with the bound on E_{1}, completes the proof.

Lemma 4.3. Let Λ ⊂ ℤ^{n} be an r-dimensional lattice with reduced basis {l_{1}, …, l_{r}}. Then

N_{2}(T, S(Λ)) = O (\frac{T^{r(r−1)/2}}{|l_{1}|^{r(r−1)}} log_{+} (T/|l_{1}|^{2})) ,

where the implied constant depends on n and r, and log_{+} x denotes max(1, | log x|).

Proof: Let A ∈ S(Λ) with T > ∥A∥. We write A = ∑_{ij} a_{ij}L_{ij} and conclude from Lemma 2.1 that

T^{2} > ∥A∥^{2} ≫ ∑_{ij} a_{ij}^{2}∥L_{ij}∥^{2}.

Since ∥L_{ij}∥^{2} ≥ |l_{1}|^{4}, it follows that

T/|l_{1}|^{2} ≫ (∑_{ij} a_{ij}^{2})^{1/2} . (23)

Now assume that rank(A) < r, and consider the r × r symmetric matrix Ã = (a_{ij}) (setting a_{ji} = a_{ij} for the missing entries). Then rank(A) = rank(Ã). To see this we may once again assume that Λ is spanned by the first r standard unit vectors, as in the proof of Lemma 4.1, since this is simply a question of linear dependence. But in that case the first r ×r minor of A is Ã, and all other entries are 0. Hence Ã is singular, so Theorem 4.1 may be applied if r > 3 and Schmidt’s result (1) may be applied if r = 3, yielding the desired upper bound in both cases.

Theorem 4.2. For n ≥ 4

N(T, n, n − 1) ≫ T^{n(n−1)/2} log T,

and for n − 2 ≥ r ≥ 3

N(T, n, r) ≫ T^{nr/2}.

The implied constants depend on n and r.

Proof: We will produce the lower bound by considering only c-regular lattices (with c = c(n, r), see Proposition 2.6), and furthermore we will restrict to E(ε_{0}T, n, r, c) for a suitably chosen ε_{0} > 0.

If Λ ∈ E(T, n, r, c) then the successive minima, {ν_{j}}, of the lattice S(Λ) are all on the order of d(Λ)^{2/r}, to within a multiplicative factor that is independent of Λ. Thus if T/d(Λ)^{2/r} is sufficiently large, the main term in (19) dominates the error term. Choosing ε_{1} > 0 sufficiently small we have

N(T, S(Λ)) > \frac{2}{3} \frac{V(r(r + 1)/2)T^{r(r+1)/2}}{2^{r(r−1)/4}d(Λ)^{r+1}} , (24)

for all Λ ∈ E(ε_{1}T, n, r, c). If Λ is c-regular then |l_{1}|^{2} ≥ c^{2}d(Λ)^{2/r}, and so by Lemma 4.3

N_{2}(T, S(Λ)) ≪ \frac{T^{r(r−1)/2}}{d(Λ)^{r−1}} log_{+} (T/d(Λ)^{2/r}) .

Hence, we may choose ε_{2} > 0 sufficiently small so that

\frac{1}{3} \frac{V(r(r + 1)/2)T^{r(r+1)/2}}{2^{r(r−1)/4}d(Λ)^{r+1}} > N_{2}(T, S(Λ))

when Λ ∈ E(ε_{2}T, n, r, c). Setting ε_{0} = min(ε_{1}, ε_{2}) guarantees that

N_{1}(T, S(Λ)) = N(T, S(Λ)) − N_{2}(T, S(Λ)) > \frac{1}{3} \frac{V(r(r + 1)/2)T^{r(r+1)/2}}{2^{r(r−1)/4}d(Λ)^{r+1}} ,

for all Λ ∈ E(ε_{0}T, n, r, c). We insert this last estimate in the sum in Proposition 1.1 to obtain

N(T, n, r) ≫ T^{r(r+1)/2} ∑_{E(ε_{0}T,n,r,c)} d(Λ)^{−(r+1)} ≫ \{ \begin{matrix}T^{nr/2} & : & n − 2 ≥ r ≥ 3 \\ T^{n(n−1)/2} log T & : & r = n − 1, \end{matrix}

summing by parts and applying Proposition 2.6.

Corollary 4.4. For n − 2 ≥ r ≥ 3 and T sufficiently large

N(T, n, r) ≈ T^{nr/2},

where the implied constants depend on n and r.

Proof: This is Theorem 1.2, and it follows from Theorems 4.1 and 4.2 .

5. Proof of Theorem 1.1

In this section we restrict our attention to the case r = n − 1, and we use the shorthand E = E(T, n, n − 1), E^{⋆} = E^{⋆}(T, n, n − 1).

Definition 5.1. A lattice Λ ∈ E is said to have δ bounded quotients if |l_{j}|/|l_{j+1}| ≥ δ for 1 ≤ j ≤ n − 2. Here δ > 0 and {l_{1}, …, l_{n−1}} is a reduced basis for Λ.

We will denote the subset of these lattices by E_{δ} = E_{δ}(T, n − 1). We introduce two more sums:

(25)  E_{2} = E_{2}(T, n − 1, δ) = T^{n(n−1)/2} ∑_{E^{⋆}\E_{δ}} d(Λ)^{−n},
(26)  E_{3} = E_{3}(T, n − 1, δ) = ∑_{E_{δ}} N_{2}(T, S(Λ))

When we come to bounding the remainder terms, δ will be chosen to balance the sizes of E_{2} and E_{3}.

By Proposition 1.1, we have N(T, n, n − 1) = ∑_{E} N_{1}(T, S(Λ)), but this is not a convenient expression to evaluate. Since N_{1} = N − N_{2}, and we have a reasonably convenient expression for N, it essential to control N_{2}. To do this we restrict to E_{δ}:

N(T, n, n − 1) = ∑_{E} N_{1}(T, S(Λ))
= ∑_{E_{δ}} N_{1}(T, S(Λ)) + ∑_{E\E_{δ}} N_{1}(T, S(Λ))

= ∑_{E_{δ}} N(T, S(Λ)) + O (E_{3} + ∑_{E\E_{δ}} N(T, S(Λ)))

= \frac{V(n(n − 1)/2)T^{n(n−1)/2}}{2^{(n−1)(n−2)/4}} ∑_{E_{δ}} d(Λ)^{−n} + O (E_{1} + E_{2} + E_{3})

= \frac{V(n(n − 1)/2)T^{n(n−1)/2}}{2^{(n−1)(n−2)/4}} ∑_{E^{⋆}} d(Λ)^{−n} + O (E_{1} + E_{2} + E_{3}) .

The sum on the left of the third line is replaced by the sum on the fourth line + O(E_{1}). The sum on the right of the third line is replaced by O(E_{1} + E_{2}). Finally, the transition from the fourth to the fifth line contributes one more O(E_{2}).

To evaluate the main term in the last line above, we once more apply summation by parts together with Schmidt’s theorem for P (T^{(n−1)/2}, n, n − 1). This yields

N(T, n, n − 1) = \frac{n(n − 1)V(n)V(n(n − 1)/2)}{2^{2+(n−1)(n−2)/4}ζ(n)}T^{n(n−1)/2} log T + O (T^{n(n−1)/2} + E_{1} + E_{2} + E_{3}) . (27)

In the last section we will show that E_{1}(T, n, n − 1) = O(T^{n(n−1)/2}) and that δ can be chosen so that E_{2}(T, n, n − 1) + E_{3}(T, n, n − 1) = O(T^{n(n−1)/2}(log T)^{1− \frac{n−2}{n−2+β(n)}} ), where β(n) = (n − 3)(n^{2} + 2)/3 is strictly positive for n ≥ 4. This, together with (27), completes the proof of Theorem 1.1 .

6. Sums and Integrals

To bound the remainder terms, we will be considering multiple sums ranging over certain bounded sets of integer vectors in ℝ^{n}. To estimate such sums, it is convenient to be able to compare them to integrals which can then be computed directly. To do this the functions that are being summed, as well as the ranges of summation, need to be reasonably well behaved.

In this section we will first describe a class of functions and domains for which this type of estimate works. We will then give a more specific version of the estimate, (Lemma 6.7), for the specific domains we use in the next section.

Let P be the set of strictly positive continuous functions, f, on (0, ∞) satisfying the following condition. For each ρ ≥ 1 there exists a c_{f}(ρ), ∞ > c_{f}(ρ) > 0, such that

f(y) ≤ c_{f}(ρ)f(x), (28)

when ρx ≥ y ≥ x ≥ 1/2. (The lower bound 1/2, is artificial. Any ε > 0 would do as well.) Note that if (28) holds for any one fixed ρ_{0} > 1, then it holds for all ρ ≥ 1, with c_{f}(ρ) ≤ c_{f}(ρ_{0})^{κ(ρ)}, and κ(ρ) = log_{ρ_{0}}(ρ) + 1.

Let X be the set of strictly positive functions on (0, ∞) satisfying

f(y) ≤ c_{f}f(x), (29)

when x + 1 ≥ y ≥ x ≥ 1/2. Here also, ∞ > c_{f} > 0. Then P ⊂ X, since we may take c_{f} = c_{f}(3). The set P consists of functions whose behavior is ‘no worse’ than that of a power function, and X consists of functions whose behavior is ‘no worse’ than that of an exponential function. More precisely

Proposition 6.1. With P, X as above we have (a) If f is strictly positive, continuous and nonincreasing then f ∈ P.

(b) f(x) = x^{α} ∈ P, for α > 0.

(c) f(x) = log_{+}^{β}(x) ∈ P, for β > 0, where log_{+}(x) = max(1, | log x|).

(d) If f, g ∈ P (∈ X) then h = max(f, g) ∈ P (∈ X).

(e) If f, g ∈ P (∈ X) then h = f · g ∈ P (∈ X).

(f) f(x) = c^{x} ∈ X, for c > 0.

Proof: All the functions listed above are strictly positive and continuous on [1/2, ∞). It remains to show the existence of an appropriate c_{f}(ρ) (c_{f}) for each.

(a) Clear, with c_{f}(ρ) ≤ 1 for all ρ > 1.

(b) For ρx ≥ y ≥ x, we have y^{α} = (y/x)^{α}x^{α} ≤ ρ^{α}x^{α}.
(c) For ρx ≥ y ≥ x, we have log_{+}^{β} y = (log_{+} y/ log_{+} x)^{β} log_{+}^{β} x < (log ρ + 1)^{β} log_{+}^{β} x.
(d) If, e.g. f(y) ≥ g(y), then
h(y) = f(y) ≤ c_{f}(ρ)f(x) ≤ c_{f}(ρ)h(x),

since h(x) ≥ f(x) by defintion. It follows that c_{h}(ρ) = max(c_{f}(ρ), c_{g}(ρ)). The proof is identical for X, with c_{f} replacing c_{f}(ρ).

(e) It is immediate that c_{fg}(ρ) ≤ c_{f}(ρ)c_{g}(ρ), and c_{fg} ≤ c_{f}c_{g}.

(f) c^{y} ≤ c^{x+1} = c · c^{x}, for x + 1 ≥ y.

Remark: It is also easy to see that if cg(x) < f(x) < g(x) on (0, ∞), with c > 0 and g ∈ P (g ∈ X), then f ∈ P (f ∈ X).

For the purposes of replacing sums by integrals, the class X is sufficient. The class P however, has the following important property, which does not extend to all of X. It will allow us to replace sums by integrals iteratively.

Proposition 6.2. Assume that g(x) is an increasing positive function, and that h(x) ∈ P. We also assume that h(x) > 2g(x), unless h is nonincreasing, in which case we only require h(x) > g(x). If f(t, x) belongs to P as a function of each variable separately, with constants c_{f,1}(ρ) for the first variable, and c_{f,2}(ρ) for the second variable, then

F (x) = ∫_{g(x)}^{h(x)} f(t, x) dt ∈ P.

The constant c_{F} (ρ) depends only on c_{h}(ρ), c_{f,1}(ρ) and c_{f,2}(ρ).

Proof: Let ρx ≥ y ≥ x ≥ 1/2. If h(x) is nonincreasing then

F (y) = ∫_{g(y)}^{h(y)} f(t, y) dt ≤ c_{f,2}(ρ) ∫_{g(x)}^{h(x)} f(t, x) dt = c_{f,2}(ρ)F (x).

In the general case we have γ = c_{h}(ρ) ≥ 1, and

F (y) = ∫_{g(y)}^{h(y)} f(t, y) dt ≤ c_{f,2}(ρ) ∫_{g(x)}^{γh(x)} f(t, x) dt.

Consider the linear map of the interval [g(x), γh(x)] onto the interval [g(x), h(x)], defined by τ = λt + μ, where λ = (h(x) − g(x))/(γh(x) − g(x)), and μ = g(x) − λg(x). We have λ ≤ 1, and thus μ ≥ 0, since g(x) ≤ h(x) ≤ γh(x). Also

λ^{−1} = \frac{γh(x) − g(x)}{h(x) − g(x)} ≤ \frac{2γh(x)}{h(x)} = 2γ,

since 0 < 2g(x) ≤ h(x). Making the change of variable τ = λt + μ gives

F (y) ≤ λ^{−1}c_{f,2}(ρ) ∫_{g(x)}^{h(x)} f(λ^{−1}(τ − μ), x) dτ ≤ 2γc_{f,2}(ρ) ∫_{g(x)}^{h(x)} f(λ^{−1}(τ − μ), x) dτ.

Now, τ ≤ λ^{−1}(τ − μ) ≤ 2γτ, for g(x) ≤ τ ≤ h(x), since μ ≥ 0, and λ^{−1} ≤ 2γ. Thus

f(λ^{−1}(τ − μ), x) ≤ c_{f,1}(2γ)f(τ, x),

for τ in this range. Hence F (y) ≤ 2γc_{f,2}(ρ)c_{f,1}(2γ)F (x).

We now come to our basic lemma relating sums to integrals. For a domain D ⊂ ℝ^{n}, and constants B > A > 0 let

D(A, B) = {u ∈ D ∩ ℤ^{n} : A ≤ |u| < B},

and let

ν_{D}(x) = |D(x, x + 1)|.

Lemma 6.3. Let D ⊂ ℝ^{n}, and for B > A ≥ 1 and f ∈ X set

S(f; D, A, B) = ∑_{D(A,B)} f(|l|).

Then for any ν ∈ X for which ν_{D}(x) ≤ ν(x) on [A, B]

S(f; D, A, B) < 2c_{f}^{2}c_{ν} ∫_{A−1/2}^{B} f(t)ν(t) dt.

Proof: Let k ≥ 0 be the integer satisfying A + k < B ≤ A + k + 1, then

S(f; D, A, B) ≤ ∑_{i=0}^{k} S(f; D, A + i, A + i + 1). (30)

Since f ∈ X and ν ≥ ν_{D} on this range, it follows that

S(f; D, A + i, A + i + 1) ≤ c_{f}f(A + i)ν_{D}(A + i) ≤ c_{f}f(A + i)ν(A + i), (31)

for 0 ≤ i ≤ k. By Proposition 6.1, f · ν ∈ X, and so f(A + i)ν(A + i) ≤ c_{f}c_{ν}f(x)ν(x), for x ∈ (A + i − 1/2, A + i). Thus

f(A + i)ν(A + i) ≤ 2c_{f}c_{ν} ∫_{A+i−1/2}^{A+i} f(t)ν(t) dt.

This, together with (30) and (31) completes the proof.

We now describe the type of domain which we will be considering in the next section. These domains are defined in terms of basic geometric conditions satisfied by reduced bases.

Definition 6.1. For a vector u ∈ ℝ^{n} let

H(u) = {v ∈ ℝ^{n} : |(u, v)| ≤ |u|^{2}/2}.

Equivalently, H(u) is the set of points in ℝ^{n} whose distance from the subspace u^{⊥} is less than |u|/2. We remark that H(0) = ℝ^{n}.

Lemma 6.4. Let l_{i} and l_{j} be elements in the same reduced basis for a lattice Λ, with |l_{j}| ≥ |l_{i}| say. Then l_{j} ∈ H(l_{i}).

Proof: Since l_{j} can be replaced by l_{j} − l_{i} in a basis for Λ, it follows that

|l_{j}|^{2} + |l_{i}|^{2} − 2(l_{j}, l_{i}) = |l_{j} − l_{i}|^{2} ≥ |l_{j}|^{2}.

Hence the lemma, replacing l_{j} by −l_{j} if necessary.

Given an ordered set of integer vectors {l_{1}, …, l_{j}}, we will use the shorthand

H_{j} = H(l_{1}) ∩ … ∩ H(l_{j}),

and for the sake of consistency, we let H_{0} = ℝ^{n}. From the definition it follows that H(u) always contains the ball B(|u|/2), and in particular H_{j} contains B(1/2), for any given set of integer vectors. Finally we note that if {l_{1}, …, l_{r}} is a reduced basis for some lattice Λ, then l_{j+1} ∈ H_{j}, 1 ≤ j < r, by Lemma 6.4. We will use the following simple fact that we state as a lemma for reference.

Lemma 6.5. Let H ⊂ ℝ^{m} be a convex set containing the ball {x : |x| < 1/2}, and let H̃ = {x : d(x, H) < 1/2}. Then

H̃ ⊂ τH = {τx : x ∈ H},

where τ = 1 + \sqrt{2}.

Proof: Assume u ∈ H̃ \ H̄, and let x ∈ ∂H be the closest point to u. Thus, in particular we have

|x − u| < 1/2. (32)

If u is a multiple of x then |τx| > |2x| ≥ |u| by (32), since |x| ≥ 1/2 by our assumption. But then we are done, since τH is also convex. Thus we may assume that x and u are independent (and m ≥ 2), and we restrict our attention to the 2 dimensional plane they span.

We may now assume that x lies on the positive x-axis, and that u lies in the first quadrant. It then follows that u is contained in the half disk of radius 1/2, centered at x, that lies in the first quadrant. But this half disk is contained in the triangle with vertices (0, 0), (0, τ/2) and (τx, 0), as follows immediately from elementary geometry. Since this triangle is contained in τD by convexity, we are done.

For parameters B > A > 0 we set, as before,

H_{j}(A, B) = {u ∈ H_{j} ∩ ℤ^{n} : A ≤ |u| < B}.

Lemma 6.6. Let {l_{1}, …, l_{j}} be a reduced basis for a lattice Λ ⊂ ℤ^{n}, with j < n, and assume that B − 1 ≥ A ≥ 1, then

|H_{j}(A, B)| ≪ |l_{1}| ⋯ |l_{j}|(B^{n−j} − A^{n−j}),

where for j = 0, the empty product of |l_{i}|’s is set equal to 1. The implied constant depends only on n and j.

Proof: For the case j = 0, the lemma follows immediately from Proposition 2.3, since B ≥ A + 1. So assume n > j ≥ 1.

We enumerate the points in H_{j}(A, B): u_{1}, …, u_{N}, N = |H_{j}(A, B)|. By considering the disjoint collection of balls of radius 1/2 centered at these points, we see that

N < 2^{n}V(n)^{−1} vol_{n}(H̃), (33)

where H̃ = {x ∈ ℝ^{n} : d(x, H_{j}(A, B)) < 1/2}.

Let π be the projection onto the subspace, E, spanned by l_{1}, …, l_{j}. From the definition of H_{j}, it follows that π[H_{j}] is a parallelepiped symmetric about the origin in E which contains B(1/2). A simple induction shows that vol_{j}(π[H_{j}]) = |l_{1}| ⋯ |l_{j}|/(sin θ_{2} ⋯ sin θ_{j}), where θ_{k} is the angle between l_{k} and the subspace spanned by l_{1}, …, l_{k−1}. Since the l_{k}’s form a reduced basis, it follows that these angles and hence their sin’s are bounded uniformly away from 0, so that vol_{j}(π[H_{j}]) ≪ |l_{1}| ⋯ |l_{j}|. Now, π[H̃] ⊂ \{x ∈ E : d(x, π[H_{j}]) < 1/2\}, so by Lemma 6.5 π[H̃] ⊂ (1 + \sqrt{2})π[H_{j}], and

vol_{j}(π[H̃]) ≪ vol_{j}(π[H_{j}]) ≪ |l_{1}| ⋯ |l_{j}|. (34)

For u ∈ H̃ we write u = u_{1} + u_{2} with u_{1} ∈ E and u_{2} ⊥ E. If |u_{1}| > A − 1/2 then |u_{2}| < ((B + 1/2)^{2} − (A − 1/2)^{2})^{1/2}, otherwise ((A − 1/2)^{2} − |u_{1}|^{2})^{1/2} ≤ |u_{2}| < ((B + 1/2)^{2} − |u_{2}|^{2}))^{1/2}. In either case, for any u ∈ π[H̃]

vol_{n−j}(π^{−1}[u] ∩ H̃) ≪ (B + 1/2)^{n−j} − (A − 1/2)^{n−j} ≪ B^{n−j} − A^{n−j}.

Combining this with (33) and (34) we have

N ≪ vol_{n}(H̃) = ∫_{π[H̃]} vol_{n−j}(π^{−1}[u] ∩ H̃) du ≪ |l_{1}| ⋯ |l_{j}|(B^{n−j} − A^{n−j}).

Lemma 6.7. If {l_{1}, …, l_{j}}, with j < n, is a reduced basis for a lattice Λ ⊂ ℤ^{n}, f ∈ X and B > A ≥ 1, then

S(f; H_{j}, A, B) = ∑_{H_{j}(A,B)} f(|l|) = O (|l_{1}| ⋯ |l_{j}| ∫_{A−1/2}^{B} f(t)t^{n−j−1} dt) ,

where for j = 0 the empty product before the integral is set equal to 1. The implied constant depends only on c_{f}, n and j.

Proof: By the preceding lemma

ν_{H_{j}}(x) ≤ c(n, j)|l_{1}| ⋯ |l_{j}|((x + 1)^{n−j} − x^{n−j}) < 2^{n−j}c(n, j)|l_{1}| ⋯ |l_{j}|x^{n−j−1},

for x ≥ 1, by the binomial formula. Since ν(x) = x^{n−j−1} ∈ X (where c_{ν} depends only on n and j), the result now follows from Lemma 6.3.

7. Remainder Terms

We come finally to the remainder terms. Each of these is given as a sum over a set of primitive lattices in ℤ^{n}. For E_{1} and E_{3}, the function being summed is explicitly given as a positive function of the lengths of a reduced basis for the lattice, one basis for each lattice. In the case of E_{2}, the function is d(Λ)^{−n}, which is comparable to (|l_{1}| ⋯ |l_{n−1}|)^{−n}, where {l_{1}, …, l_{n−1}} is a reduced basis of Λ.

The procedure we follow in all three cases is the same. We have

∑_{Ẽ} f(|l_{1}|, …, |l_{r}|) < ∑_{H_{0}(A_{1},B_{1})} ∑_{H_{1}(A_{2},B_{2})} … ∑_{H_{r−1}(A_{r},B_{r})} f(|l_{1}|, …, |l_{r}|).

Ẽ is a finite set of primitive r dimensional sublattices of ℤ^{n}, defined in terms of bounds on the lengths of their reduced basis elements, and the limits B_{j} and A_{j} are determined from this definition. In the sum on the left, the function f is evaluated at precisely one reduced basis for each lattice, and the inequality is simply a reflection of the fact that we increase our estimate when we sum over all possible reduced bases for each lattice.

Using the results of the previous section, we then replace each of the sums by the corresponding integral, working from the inside out. At each stage we assume that the vectors l_{1}, …, l_{j} that define H_{j} do form a reduced basis, and thus Lemma 6.7 applies. But when summing over H_{j}, we no longer place this restriction on l_{j+1}, and simply sum over all integer vectors in the given range. Once again, we see that this can only increase the estimate.

Proposition 7.1. For n − 1 ≥ r ≥ 3

E_{1}(T, n, r) = O(T^{nr/2}).

Proof: Recall that

E_{1}(T, n, r) = ∑_{E(T,n,r)} ∏_{1≤i≤j≤r}^{′} max(1, T/|l_{i}||l_{j}|),

where for each Λ ∈ E(T, n, r), {l_{1}, …, l_{r}} is a fixed reduced basis for Λ, and the prime means that the factor max(1, T/|l_{r}|^{2}) is omitted from the product.

If {l_{1}, …, l_{r}} is the reduced basis of Λ ∈ E(T, n, r), then |l_{j}||l_{r−j+1}| ≤ c_{r}T, and, as always, |l_{1}| ≤ … ≤ |l_{r}|. Implementing the plan outlined above, we obtain

E_{1}(T, n, r) ≪ ∑_{H_{0}(1,T^{1/2})} ∑_{H_{1}(A_{2},B_{2})} … ∑_{H_{r−1}(A_{r},B_{r})} ∏_{1≤i≤j≤r}^{′} max(1, T/|l_{i}||l_{j}|), (35)

where A_{1} = 1, A_{j+1} = |l_{j}| for 1 ≤ j < r, B_{j} = T^{1/2} for j ≤ (r + 1)/2, and B_{j} = T/|l_{r−j+1}| for j > (r + 1)/2 (having ‘absorbed’ c_{r} in T).

The function of |l_{r}| appearing in the innermost sum,

∏_{1≤i≤r−1} max(1, T/|l_{i}||l_{r}|),

is in P by Proposition 6.1. We may therefore invoke Lemma 6.7 and replace the innermost sum by the integral

|l_{1}| ⋯ |l_{r−1}| ∫_{A_{r}/2}^{B_{r}} t_{r}^{n−r} ∏_{1≤i≤r−1} max(1, T/|l_{i}|t_{r}) dt_{r}.

We note that since A_{r} ≥ 1, A_{r} − 1/2 ≥ A_{r}/2, and by decreasing the lower limit of integration, we only increase the estimate. The function of |l_{r−1}| appearing in the sum over H_{r−2} is

|l_{r−1}| ∏_{1≤i≤r−1} max(1, T/|l_{i}||l_{r−1}|) ∫_{A_{r}/2}^{B_{r}} t_{r}^{n−r} ∏_{1≤i≤r−1} max(1, T/|l_{i}|t_{r}) dt_{r}.

This function is in P by Propositions 6.1 and 6.2. Thus we may apply Lemma 6.7 again and replace the sum over H_{r−2} by the integral

|l_{1}| ⋯ |l_{r−2}| ∫_{A_{r−1}/2}^{B_{r−1}}∫_{A_{r}/2}^{B_{r}} t_{r−1}^{n−r+2}t_{r}^{n−r} ∏_{r−1≤j≤r} max(1, T/t_{r−1}t_{j}) ∏_{1≤i≤r−2} max(1, T/|l_{i}|t_{j}) dt_{r}dt_{r−1}.

The resulting function of |l_{r−2}| appearing in the next sum is also in P, as before, and Lemma 6.7 may be invoked again. Continuing in this manner, all the sums are replaced by the corresponding integrals, resulting in the estimate

E_{1}(T, n, r) ≪ ∫_{1/2}^{T^{1/2}}∫_{t_{1}/2}^{T^{1/2}}… ∫_{t_{r−1}/2}^{T/t_{1}}t_{1}^{n+r−2}t_{2}^{n+r−4} ⋯ t_{r}^{n−r} ∏_{1≤i≤j≤r}^{′}max(1, \frac{T}{t_{i}t_{j}}) dt_{r} … dt_{2} dt_{1}.

We make the substitutions t_{j} = T^{1/2}u_{j} to obtain E_{1}(T, n, r) ≪ T^{nr/2}I(n, r, T^{−1/2}/2), where

I(n, r, ε) = ∫_{ε}^{1} ∫_{u_{1}/2}^{1} … ∫_{u_{r−1}/2}^{1/u_{1}} u_{1}^{n+r−2}u_{2}^{n+r−4} ⋯ u_{r}^{n−r} ∏_{1≤i≤j≤r}^{′} max (1, \frac{1}{u_{i}u_{j}} ) du_{r} … du_{1}. (36)

The lower limit of the j^{th} integral is u_{j−1}/2, for 2 ≤ j ≤ r. The upper limit of the j^{th} integral is 1 for 1 ≤ j ≤ (r + 1)/2, and is 1/u_{r−j+1} for (r + 1)/2 < j ≤ r. The proposition will follow from

Lemma 7.2. For n > r ≥ 3 and ε > 0, I(n, r, ε) = O(1).

Proof: For u_{1}, …, u_{r} in the range of integration, we have u_{j}u_{r−j+1} ≤ 1, and so u_{1}u_{2} ⋯ u_{r} ≤ 1. It follows then that I(n + 1, r, ε) ≤ I(n, r, ε), since the integrand for n + 1 is the integrand for n multiplied by u_{1} ⋯ u_{r}. It therefore suffices to prove the assertion of the lemma for r = n − 1. This will be done by induction.

To begin, we have

I(3, 2, ε) = ∫_{ε}^{1} ∫_{u_{1}/2}^{1/u_{1}} du_{2}du_{1} < | log ε|,

and

I(4, 3, ε) = ∫_{ε}^{1} ∫_{u_{1}/2}^{1} ∫_{u_{2}/2}^{1/u_{1}} u_{1} max(1, 1/u_{2}u_{3}) du_{3}du_{2}du_{1}
< ∫_{ε}^{1} ∫_{u_{1}/2}^{1} ∫_{u_{2}/2}^{1/u_{2}} u_{1}u_{2}^{−1}u_{3}^{−1} du_{3}du_{2}du_{1} + ∫_{ε}^{1} ∫_{u_{1}/2}^{1} ∫_{1/u_{2}}^{2/u_{1}} u_{1} du_{3}du_{2}du_{1}
≪ ∫_{ε}^{1} u_{1} log^{2} u_{1} + 1 du_{1} = O(1).

We now assume that I(m, m − 1, ε) = O(1) for 4 ≤ m < n, and estimate

I(n, n − 1, ε) = ∫_{ε}^{1} ∫_{u_{1}/2}^{1} ⋯ ∫_{u_{n−2}/2}^{1/u_{1}} u_{1}^{2n−3}u_{2}^{2n−5} ⋯ u_{n−1} ∏_{1≤i≤j≤n−1}^{′}max(1, \frac{1}{u_{i}u_{j}}) du_{n−1} … du_{2}du_{1}, (37)

beginning with the innermost integral. Lemma 7.3. Let u_{1}, …, u_{n−2} be in the range of integration of the integral above (as described in the paragraph following (36), then

J = J(u_{1}, …, u_{n−2}) = ∫_{u_{n−2}/2}^{1/u_{1}} u ∏_{1≤i≤n−2}max(1, \frac{1}{u_{1}u}) du ≪ u_{1}^{3−n}(log_{+} u_{1})(u_{2} ⋯ u_{n−2})^{−1},

where in this case we set log_{+} u = max(1, | log u|). proof: Let k ≥ 2 be the largest index such that u_{k}u_{n−2} ≤ 2. If u_{n−2}/2 ≤ u < 1/u_{k} then

u_{n−2}u ≥ 2^{−1}u_{n−3}u ≥ … ≥ 2^{k+2−n}u_{k+1}u > 2^{k+2−n},

and so

∏_{1≤i≤n−2} max(1, 1/u_{i}u) ≪ (u_{1} ⋯ u_{k})^{−1}u^{−k}.

By the same reasoning, when 1/u_{m+1} ≤ u ≤ 2/u_{m}, then

∏_{1≤i≤n−2} max(1, 1/u_{i}u) ≪ (u_{1} ⋯ u_{m})^{−1}u^{−m}.

Setting J_{k} = (u_{1} ⋯ u_{k})^{−1} ∫_{u_{n−2}/2}^{1/u_{k}} u^{1−k} du, and J_{m} = (u_{1} ⋯ u_{m})^{−1} ∫_{1/u_{m+1}}^{2/u_{m}} u^{1−m} du, for 1 ≤ m < k, it follows that J ≪ ∑_{m=1}^{k} J_{m}.

We have J_{1} = u_{1}^{−1} ∫_{1/u_{2}}^{2/u_{1}} du < 2u_{1}^{−2} ≪ u_{1}^{3−n}(u_{2} ⋯ u_{n−2})^{−1}, since n ≥ 5 and u_{2} ⋯ u_{n−2} ≤ 1. Next,

J_{2} = \{ \begin{matrix}(u_{1}u_{2})^{−1} ∫_{u_{2}/2}^{1/u_{2}} u^{−1} du & : & k = 2, \\ (u_{1}u_{2})^{−1} ∫_{1/u_{3}}^{2/u_{2}} u^{−1} du & : & k > 2. \end{matrix} \} ≪ u_{1}^{3−n}(log_{+} u_{1})(u_{2} ⋯ u_{n−2})^{−1},

since log_{+} u_{1} ≫ log_{+} u_{2} ≫ log_{+} u_{3}. When k > 2 then

J_{k} = (u_{1} ⋯ u_{k})^{−1} ∫_{u_{n−2}/2}^{1/u_{k}} u^{1−k} du < 2^{k−2}(u_{1} ⋯ u_{k})^{−1}u_{n−2}^{2−k}.

But u_{n−2} ≤ 2/u_{1} and u_{k+1} ⋯ u_{n−2} ≪ u_{1}^{k+2−n}, so J_{k} ≪ u_{1}^{3−n}(u_{2} ⋯ u_{n−2})^{−1}. By the same argument J_{m} ≪ u_{1}^{3−n}(u_{2} ⋯ u_{n−2})^{−1}, for 3 ≤ m ≤ k, and so J ≪ u_{1}^{3−n}(log_{+} u_{1})(u_{2} ⋯ u_{n−2})^{−1}.

Returning to (37), and inserting the estimate for J(u_{1}, …, u_{n−2}) from the preceding lemma, we have

I(n, n − 1, ε) ≪ ∫_{ε}^{1} ⋯ ∫_{u_{n−3}}^{1/u_{2}} u_{1}^{n}(log_{+} u_{1})u_{2}^{2n−6} ⋯ u_{n−2}^{2} ∏_{1≤i≤j≤n−2}max(1, \frac{1}{u_{i}u_{j}}) du_{n−2} … du_{2}du_{1}

≪ ∫_{ε}^{1} ⋯ ∫_{u_{n−3}}^{1/u_{2}} u_{1}(log_{+} u_{1})u_{2}^{2n−7} ⋯ u_{n−2} ∏_{1≤i≤j≤n−2}max(1, \frac{1}{u_{i}u_{j}}) du_{n−2} … du_{2}du_{1}.

To pass from the first line to the second line, we observe that max(1, 1/u_{1}u_{j}) ≪ 1/u_{1}u_{j}, for 1 ≤ j ≤ n − 2, and that the product of these contributes a factor of u_{1}^{1−n}(u_{2} ⋯ u_{n−2})^{−1}.

The integrand in the last integral differs from that in the definition of I(n − 2, n − 3, u_{1}/2) by the inclusion of the factor max(1, 1/u_{n−2}^{2}), which is different from 1 only when u_{n−2} < 1. This then implies that u_{j} < 2^{n−j−2}, and that ∏_{2≤i≤j≤n−2} max(1, 1/u_{i}u_{j}) ≪ (u_{2} ⋯ u_{n−2})^{2−n}. Thus

I(n, n − 1, ε) ≪ ∫_{ε}^{1} u_{1}(log_{+} u_{1})(I(n − 2, n − 3, u_{1}/2) + I_{1}(n − 2, u_{1}/2)) du_{1}, (38)

where for 0 < η < 1

I_{1}(m, η) = ∫_{η}^{1} ∫_{v_{1}/2}^{2^{m−2}} ⋯ ∫_{v_{m−2}/2}^{2} ∫_{v_{m−1}/2}^{1} v_{1}^{m−2}v_{2}^{m−4} ⋯ v_{m}^{−m} dv_{m} ⋯ dv_{2}dv_{1}.

For m = 2, I_{1}(m, η) = ∫_{η}^{1} ∫_{v_{1}/2}^{1} v_{2}^{−2} dv_{2}dv_{1} < 2| log η|. If m ≥ 3 then

∫_{u_{m−1}/2}^{1} u_{m}^{−m} du_{m} ≪ u_{m−1}^{1−m} ≪ (u_{1} ⋯ u_{m−1})^{−1}.

Thus, after performing the first integration we see that

I_{1}(m, η) ≪ ∫_{η}^{1} ∫_{v_{1}/2}^{2^{m−2}} ⋯ ∫_{v_{m−2}/2}^{2} v_{1}^{m−3}v_{2}^{m−5} ⋯ v_{m−1}^{1−m} dv_{m−1} ⋯ dv_{2}dv_{1} ≪ I_{1}(m − 1, η) ≪ | log η|,

by induction.

Inserting this estimate in (38), and invoking our induction hypothesis for I(n − 2, n − 3, u_{1}/2), we obtain finally

I(n, n − 1, ε) ≪ ∫_{ε}^{1} u_{1} log_{+}^{2} u_{1} du_{1} = O(1).

This completes the proof of Lemma 7.2 and of Proposition 7.1.

Proposition 7.4. For n ≥ 4, E_{2}(T, n − 1, δ) = O(δ^{n−2}T^{n(n−1)/2} log T).

Proof: From the definition of E_{2}, (25), it suffices to show that

S(T, δ) = ∑_{E^{⋆}\E_{δ}} d(Λ)^{−n} = O (δ^{n−2} log T ) ,

where, as in §5, E^{⋆} = E^{⋆}(T, n, n − 1) and E_{δ} = E_{δ}(T, n − 1). We first remark that for a reduced basis {l_{1}, …, l_{n−1}} of Λ we have d(Λ)^{−n} ≪ |l_{1}|^{−n} ⋯ |l_{n−1}|^{−n}, so

S(T, δ) ≪ ∑_{E^{⋆}\E_{δ}} |l_{1}|^{−n} ⋯ |l_{n−1}|^{−n},

summing over one reduced basis for each lattice.

Now if Λ ∉ E_{δ} then for some index 2 ≤ j ≤ n − 1, it follows that |l_{j}| > δ^{−1}|l_{j−1}|. Fixing such a j let A_{j}^{j} = δ^{−1}|l_{j−1}|, and for k ≠ j let A_{k}^{j} = |l_{k−1}|, with A_{1}^{j} = 1 always. We also define B_{1} = T^{1/2}, and B_{k} = T^{(n−1)/2} for 2 ≤ k ≤ n − 1. The B_{k}, k ≥ 2, are larger than need be, but this will be seen to be irrelevant. (In fact we could take B_{k} = (T^{(n−1)/2}(|l_{1}| ⋯ |l_{k−1}|)^{−1})^{1/(n−k)}, for 2 ≤ k ≤ n − 1, since Λ ∈ E^{⋆}.)

With these notations it follows that if Λ ∈ E^{⋆} \ E_{δ} then a reduced basis of Λ, {l_{1}, …, l_{n−1}}, satisfies

l_{1} ∈ H_{0}(A_{1}^{j}, B_{1}), l_{2} ∈ H_{1}(A_{2}^{j}, B_{2}), …, l_{n−1} ∈ H_{n−2}(A_{n−1}^{j}, B_{n−1}),

for some j between 2 and n − 1. Hence

S(T, δ) = O ( max_{2≤j≤n−1} S_{j}(T, δ)) , (39)

where

S_{j}(T, δ) = ∑ |l_{1}|^{−n}_{l_{1}∈H_{0}(A_{1}^{j},B_{1})} ∑ |l_{2}|^{−n}_{l_{2}∈H_{1}(A_{2}^{j},B_{2})} … ∑ |l_{n−1}|^{−n}_{l_{n−1}∈H_{n−2}(A_{n−1}^{j},B_{n−1})} .

We now replace the multiple sum above by a multiple integral, beginning with the innermost sum. We have

∑ |l_{n−1}|^{−n}_{l_{n−1}∈H_{n−2}(A_{n−1}^{j},B_{n−1})} ≪ |l_{1}| ⋯ |l_{n−2}| ∫_{A_{n−1}^{j}/2}^{B_{n−1}} t_{n−1}^{1−n} dt_{n−1},

by Lemma 6.7 and Proposition 6.1. We have used, once again, the fact that A_{n−1}^{j} ≥ 1, and hence A_{n−1}^{j} − 1/2 ≥ A_{n−1}^{j}/2. Denoting by f_{n−2} the function of |l_{n−2}| that appears in the next sum, we have

f_{n−2}(|l_{n−2}|) = ∫_{A_{n−1}^{j}/2}^{B_{n−1}} |l_{n−2}|^{1−n}t_{n−1}^{1−n} dt_{n−1}. (40)

By Proposition 6.2, f_{n−2} ∈ P since A_{n−1}^{j/2} is increasing as a function of |l_{n−2}|, B_{n−1} is constant and the integrand and the integrand is in P both as a function of |l_{n−2}| and as a function of t_{n−1}. Applying Lemma 6.7 to the next sum we have

∑_{l_{n−2}∈H_{n−3}(A_{n−2}^{j},B_{n−2})} f_{n−2}(|l_{n−2}) ≪ |l_{1}| ⋯ |l_{n−3}| ∫_{A_{n−2}^{j}/2}^{B_{n−2}} f_{n−2}(t_{n−2})t_{n−2}^{2} dt_{n−2}

= |l_{1}| ⋯ |l_{n−3}| ∫_{A_{n−2}^{j}/2}^{B_{n−2}} ∫_{A_{n−1}^{j}/2}^{B_{n−1}} t_{n−2}^{3−n}t_{n−1}^{1−n} dt_{n−1}dt_{n−2}.

Note that the inner integral above is in P as a function of t_{n−2}, by the same argument we used for f_{n−2}. Writing f_{n−3} for the function of |l_{n−3}| that now appears in the sum over H_{n−4}, we have

f_{n−3}(|l_{n−3}|) = ∫_{A_{n−2}^{j}/2}^{B_{n−2}} ∫_{A_{n−1}^{j}/2}^{B_{n−1}} |l_{n−3}|^{2−n}t_{n−2}^{3−n}t_{n−1}^{1−n} dt_{n−1}dt_{n−2}.

The integrand of the outer integral above is in P, both as a function of |l_{n−3}| and of t_{n−2}. Also, A_{n−2}^{j}/2 is an increasing function of |l_{n−3}| and B_{n−2} is constant, and so it follows, as before, that we may apply Lemma 6.7 to this sum as well. Proceeding in this manner, we replace all the sums by integrals, obtaining the estimate

S_{j}(T, δ) ≪ ∫_{1/2}^{√\overline{T}} ∫_{A_{2}^{j}/2}^{B_{2}} … ∫_{A_{n−1}^{j}/2}^{B_{n−1}} t_{1}^{n−3}t_{2}^{n−5} ⋯ t_{n−1}^{1−n}dt_{n−1} … dt_{2} dt_{1}, (41) where the exponent of t_{k} is n − 2k − 1. Note that |l_{k−1}| is replaced by t_{k−1} in the definition of A_{k}^{j}.

Let e_{n−1} = 1 − n, and for 1 ≤ k ≤ n − 2 let e_{k} = n − 2k + e_{k+1}, then e_{k} is precisely the exponent of t_{k} after performing the first n − k − 1 integrations (from the inside out). It is easy to see that e_{k} = (n − k)(1 − k) − 1, and in particular, e_{k} ≤ 1 − n ≤ −3 for k > 1, (whence the B_{k}’s for these k’s are irrelevant), and e_{1} = −1. With these observations, (41) yields S_{j}(T, δ) = O(δ^{−(e_{j}+1)} log T). Since 1 > δ, this expression is maximized when j = 2 or j = n − 1, for which e_{j} = 1 − n. Inserting this in (39) completes the proof.

Proposition 7.5. For n ≥ 4

E_{3}(T, n − 1, δ) = O (δ^{(3−n)(n^{2}+2)/3}T^{n(n−1)/2}) .

Proof: Recall that by Lemma 4.3, for r = n − 1,

N_{2}(T, S(Λ)) = O (\frac{T^{(n−1)(n−2)/2}}{|l_{1}|^{(n−1)(n−2)}} log_{+}(T/|l_{1}|^{2})) ,

where l_{1} is the shortest element in a fixed reduced basis for Λ. ¿From the definition, (26), of E_{3} it then follows that

E_{3} ≪ T^{(n−1)(n−2)/2} ∑_{E_{δ}} \frac{log_{+}(T/|l_{1}|^{2})}{|l_{1}|^{(n−1)(n−2)}}

≪ T^{(n−1)(n−2)/2} ∑_{H_{0}(1,T^{1/2})} ∑_{H_{1}(A_{2},B_{2})} … ∑_{H_{n−2}(A_{n−1},B_{n−1})} \frac{log_{+}(T/|l_{1}|^{2})}{|l_{1}|^{(n−1)(n−2)}}.

Here, A_{j} = |l_{j−1}| and B_{j} = δ^{−1}|l_{j−1}|, for j = 2, …, n − 1. Once again the sum over lattices has been replaced by a sum over reduced bases, and the definition of B_{j} expresses the fact that we are summing over lattices in E_{δ}.

For the innermost sum we have

∑_{H_{n−2}(A_{n−1},B_{n−1})} \frac{log_{+}(T/|l_{1}|^{2})}{|l_{1}|^{(n−1)(n−2)}} ≪ \frac{log_{+}(T/|l_{1}|^{2})}{|l_{1}|^{(n−1)(n−2)}}|l_{1}| ⋯ |l_{n−2}| ∫_{A_{n−1}/2}^{B_{n−1}} t_{n−1} dt_{n−1},

by Lemma 6.7 and Proposition 6.1 (a). As a function of |l_{n−2}| the integral above is in P, since the integrand satisfies the conditions of Proposition 6.2, and B_{n−1} > A_{n−1}, so B_{n−1} > 2A_{n−1}/2. Thus we may apply lemma 6.7 to the second sum as well. We continue in this manner to replace sums by integrals, (using arguments similar to those leading up to (41)), until we reach the first sum where we have

E_{3} ≪ T^{(n−1)(n−2)/2} ∑_{H_{0}(1,T^{1/2})} log_{+}(T/|l_{1}|^{2})|l_{1}|^{−n^{2}+4n−4} ∫_{A_{2}/2}^{B_{2}}…∫_{A_{n−1}/2}^{B_{n−1}}t_{2}^{2n−5} ⋯ t_{n−1} dt_{n−1} … dt_{2}.

As a function of |l_{1}|, the multiple integral above is in P by the inductive argument invoking Proposition 6.2. Also, log_{+}(T/x^{2})x^{−n^{2}+4n−4} ∈ P by Proposition 6.1. Thus Lemma 6.7 may be applied to this last sum as well, giving

E_{3} ≪ T^{(n−1)(n−2)/2} ∫_{1/2}^{√\overline{T}} ∫_{t_{1}/2}^{δ^{−1}t_{1}}…∫_{t_{n−2}/2}^{δ^{−1}t_{n−2}}t_{1}^{−n^{2}+5n−5} log_{+}(T/t_{1}^{2})t_{2}^{2n−5} ⋯ t_{n−1} dt_{n−1} … dt_{2} dt_{1}, (42)

where the exponent of t_{j} is 2(n − j) − 1 for 1 < j ≤ n − 1. As before, the definitions of A_{j} and B_{j} have been changed by replacing |l_{j−1}| with t_{j−1}.

We make the substitutions t_{j} = δ^{1−j}T^{1/2}u_{j} in (42), for 1 ≤ j ≤ n − 1. Thus

t_{j}^{2(n−j)−1} dt_{j} = δ^{2(1−j)(n−j)}T^{n−j}u_{j}^{2(n−j)−1} du_{j},

for j = 2 … n − 1, and

t_{1}^{−n^{2}+5n−5} log_{+}(T/t_{1}^{2}) dt_{1} = T^{(−n^{2}+5n−4)/2}u_{1}^{−n^{2}+5n−5} log_{+} u_{1} du_{1}.

The integral is transformed to

T^{α(n)}δ^{−β(n)} ∫_{T^{−1/2}/2}^{1} ∫_{a_{2}}^{u_{1}} … ∫_{a_{n−1}}^{u_{n−2}} 2u_{1}^{−n^{2}+5n−5} log_{+} u_{1}u_{2}^{2n−5} ⋯ u_{n−1} du_{n−1} … du_{2} du_{1},

where the a_{j}’s are all positive,

α(n) = (−n^{2} + 5n − 4)/2 + ∑_{j=2}^{n−1}(n − j) = n − 1,

and

β(n) = 2 ∑_{j=2}^{n−1}(n − j)(j − 1) = (n − 3)(n^{2} + 2)/3.

Performing the first n − 2 integrations reduces this to

T^{n−1}δ^{−β(n)} ∫_{T^{−1/2}/2}^{1} 2u_{1}^{n−3} log_{+} u_{1} du_{1} ≪ T^{n−1}δ^{−β(n)},

since the integral converges for n ≥ 4. Inserting this back in (42) completes the proof.

Corollary 7.6. Choosing δ = (log T)^{− \frac{1}{β(n)+n−2}} , we have for n ≥ 4

E_{2}(T, n − 1, δ) + E_{3}(T, n − 1, δ) = O (T^{n(n−1)/2}(log T)^{1− \frac{n−2}{β(n)+n−2}} ) .

Proof: This follows from Proposition 7.4 and Proposition 7.5, where β(n) is the cubic polynomial of n defined in the latter.

The authors thank the referee for the substantial time that he put into this paper, and for the many suggestions and corrections that he made.

References

1. J.W.S. Cassels, An Introduction to the Geometry of Numbers, Springer Verlag, (1971).

2. W. Duke, Z. Rudnick, P. Sarnak, The density of integer points on affine homogeneous varieties, Duke Math J. 71 (1993), 143–180.

3. A. Eskin, C. McMullen, Mixing, counting and equidistribution in Lie groups, Duke Math. J. 71 (1993), 181–210.

4. A. Eskin, S. Mozes, N. Shah, Unipotent flows and counting lattice points on homogeneous varieties, preprint.

5. P.M. Gruber and C.G. Lekkerkerker, Geometry of Numbers, 2^{nd} Ed., North–Holland (1987).

6. G.H. Hardy, E.M. Wright, An Introduction to the Theory of Numbers, 4^{th} ed. Oxford (1960).

7. Y.R. Katznelson, Singular matrices and a uniform bound for congruence groups of SL_{n}(ℤ), Duke Math. J. 69 (1993), 121–136.

8. Y.R. Katznelson, Matrices of fixed rank, to appear Proc. of the A.M.S.

9. K. Mahler, Ein Übertragunzprinzip für konvexe Körper, Časopis Pěst. Mat. Fyz. 68 (1939), 93–102.

10. W. Schmidt, Asymptotic formulae for point lattices of bounded determinant and subspaces of bounded height, Duke Math J. 35 (1968), 327–339.

11. W. Schmidt, Northcott’s theorem on heights, II The quadratic case, Preprint.

12. C.L. Siegel, Lectures on the Geometry of Numbers, Springer Verlag, 1988.

Alex Eskin: Institute for Advanced Studies, Princeton, NJ, USA E-mail address: eskin@math.ias.edu

Yonatan Katznelson: Institut des Hautes Études Scientifiques, Bûres sur Yvette, France E-mail address: yorick@cats.ucsc.edu