Discrepancy of weighted matrix nets

W.W.L. Chen and V.F. Lev

1. Introduction

Suppose that s ∈ ℕ is fixed. For any invertible real s × s matrix A, consider the lattice

Λ = {Am : m ∈ ℤ^{s}},

and write

X = Λ ∩ U^{s},

where

ℤ^{s} = {(m_{1}, …, m_{s}) : m_{1}, …, m_{s} ∈ ℤ}

is the s–dimensional integer lattice, and

U^{s} = {(x_{1}, …, x_{s}) : 0 ≤ x_{1}, …, x_{s} < 1}

is the s–dimensional unit cube. In other words, X is the set of all the points of the lattice Λ that fall into the unit cube U^{s}.

By a matrix net generated by A, we mean a pair of the form (X, ρ), where the set X is defined as above and ρ : X → ℝ is a weight function on the points of the set X.

Remark. We emphasize here that the set X arises from a lattice Λ. If X is an arbitrary set of N points in U^{s}, not generated by a matrix as indicated above, then the “natural” choice of weight function ρ(x) = 1/N may result in a very poorly distributed net. To see this, consider the one–dimensional case with

X = \{0, \frac{1}{4K} , \frac{2}{4K} , …, \frac{2K − 2}{4K}, \frac{2K − 1}{4K}, \frac{2K + 1}{4K}, \frac{2K + 3}{4K}, …, \frac{4K − 3}{4K}, \frac{4K − 1}{4K}\} ,

where K is a positive integer and N = 3K. If ρ(x) = 1/N for every x ∈ X, then the discrepancy

sup_{I⊆[0,1)} |∑_{x∈I} ρ(x) − μ(I)| ≥ | ∑_{x∈[0,1/2)} ρ(x) − \frac{1}{2}| = |\frac{2}{3} − \frac{1}{2}| = \frac{1}{6}.

Here the supremum is taken over all intervals I ⊆ [0, 1) and μ(I) denotes the length of the interval I. On the other hand, if

ρ(x) = \{ \begin{matrix}1/4K, & if x < 1/2, \\ 1/2K, & if x > 1/2, \end{matrix}

then it is easily seen that there exists a positive constant c such that

sup_{I⊆[0,1)} |∑_{x∈I} ρ(x) − μ(I)| ≤ \frac{c}{N} .

The purpose of this paper is to show that the phenomenon discussed in the remark above cannot possibly happen for matrix nets. We shall show that in the approximation of certain integrals and in certain discrepancy problems, matrix nets with equal weights are essentially best possible. Here, we say that the matrix net (X, ρ) has equal weights if there exists some fixed number ρ_{0} ∈ ℝ such that ρ(x) = ρ_{0} for every x ∈ X.

We shall consider classes Φ of functions f : ℝ^{s} → ℝ which satisfy the following conditions:

(Φ1) Integrability: Every f ∈ Φ is Riemann integrable on U^{s}.

(Φ2) Periodicity: Every f ∈ Φ is periodic with period 1 in each variable.

(Φ3) Translation invariance: For every f ∈ Φ and every z ∈ ℝ^{s}, we have f_{z} ∈ Φ,

where f_{z}(x) = f(x + z) for all x ∈ ℝ^{s}. Examples of such classes Φ are given by the class of characteristic functions of aligned rectangular boxes modulo U^{s} and the class of functions with restrictions on the absolute values of Fourier coefficients which provide sufficient smoothness.

For every function f ∈ Φ and for every matrix net (X, ρ), write

R(f; X, ρ) = ∑_{x∈X} ρ(x)f(x) − ∫_{U^{s}} f(t)dt,

and let

R(Φ; X, ρ) = sup_{f∈Φ} |R(f; X, ρ)|,

where the supremum is taken over all functions f ∈ Φ. Furthermore, for every ρ_{0} ∈ ℝ, write

R(f; X, ρ_{0}) = ∑_{x∈X} ρ_{0}f(x) − ∫_{U^{s}} f(t)dt,

and let

R(Φ; X, ρ_{0}) = sup_{f∈Φ} |R(f; X, ρ_{0})|,

where the supremum is again taken over all functions f ∈ Φ. Here we have used the same letter R to denote four related, but distinct, quantities. However, this should not lead to confusion in the subsequent argument.

The following theorem shows that if the inverse of A has integer entries, then one can always choose equal weights to minimize the error term in approximate integration.

Theorem 1. Suppose that A is an inverse of an integer-valued matrix. Then for every class Φ satisfying conditions (Φ1)–(Φ3), we have

inf_{ρ} R(Φ; X, ρ) = inf_{ρ_{0}} R(Φ; X, ρ_{0}),

where the infima are taken over all functions ρ : X → ℝ and over all numbers ρ_{0} ∈ ℝ respectively.

Theorem 1 shows that for any matrix A, the inverse A^{−1} of which has integer entries, the weights may be chosen to be equal. This raises the question of whether the natural choice ρ_{0} = 1/N, where N = |X| denotes the cardinality of the set X, is always the best. Our next theorem shows that this is necessarily the case for any “reasonable” point set X arising from a lattice.

Theorem 2. Suppose that A is an inverse of an integer-valued matrix, and that the class Φ satisfies conditions (Φ1)–(Φ3). Let

M(Φ) = sup_{f∈Φ} |∫_{U^{s}} f(t)dt| .  (1)

Suppose further that for some fixed real number ε ∈ (0, 1), at least one of the following two conditions holds:

(a) R(Φ; X, 1/N) ≤ ε^{−1}M(Φ).

(b) inf_{ρ_{0}} R(Φ; X, ρ_{0}) ≤ (1 − ε)M(Φ) and M(Φ) > 0. Then

R(Φ; X, 1/N) ≤ \frac{3}{ε} inf_{ρ} R(Φ; X, ρ),

where the infimum is taken over all functions ρ : X → ℝ.

Observe that if condition (b) does not hold, then in view of Theorem 1, matrix nets with the point set X are not suitable for approximate integration of functions in Φ for any choice of weights. Condition (a) may be easier to verify.

Let us now concentrate on the special case of Theorem 2 when Φ is the class of characteristic functions of all aligned rectangular boxes

B = [a_{1}, b_{1}) × … × [a_{s}, b_{s}),

where we assume that 0 ≤ b_{i} − a_{i} ≤ 1 for every i = 1, …, s. We denote by 𝔅 the collection of all boxes of this type. For every x ∈ ℝ^{s} and every B ∈ 𝔅, we shall write x ∈ B (mod U^{s}) to denote that there exists n ∈ ℤ^{s} such that x − n ∈ B. We define

χ_{B}(x) = \{ \begin{matrix}1, & if x ∈ B (mod U^{s}), \\ 0, & otherwise. \end{matrix}

For every matrix net (X, ρ), consider the discrepancy function

D_{B}(X, ρ) = ∑_{{x∈X \atop χ_{B}(x)=1}} ρ(x) − μ(B),  (2)

where μ(B) denotes the s–dimensional volume of B, and let

D(X, ρ) = sup_{B∈𝔅} |D_{B}(X, ρ)|,  (3)

where the supremum is taken over all aligned rectangular boxes in 𝔅. In the case of constant weight function ρ(x) = ρ_{0}, we shall use the notation D_{B}(X, ρ_{0}) and D(X, ρ_{0}) respectively, so that in particular

D_{B}(X, 1/N) = \frac{1}{N} ∑_{{x∈X \atop χ_{B}(x)=1}} 1 − μ(B).  (4)

It is easily seen that the class Φ of all the functions χ_{B} satisfies the conditions (Φ1) − (Φ3), and that for this class, M(Φ) = 1 and R(Φ; X, ρ) = D(X, ρ), the latter identity in view of

R(χ_{B}; X, ρ) = ∑_{x∈X} ρ(x)χ_{B}(x) − ∫_{U^{s}} χ_{B}(t)dt = ∑_{{x∈X \atop χ_{B}(x)=1}} ρ(x) − μ(B) = D_{B}(X, ρ)

for every B ∈ 𝔅. Also, it is clear from (3) and (4) that D(X, 1/N) ≤ 1, and so condition (a) of Theorem 2 is satisfied for any constant ε < 1. Therefore, as very special cases of Theorems 1 and 2, we immediately have the following two corollaries.

Corollary 1. Suppose that A is an inverse of an integer-valued matrix. Then

inf_{ρ} D(X, ρ) = inf_{ρ_{0}} D(X, ρ_{0}),

where the infima are taken over all functions ρ : X → ℝ and over all numbers ρ_{0} ∈ ℝ respectively.

Corollary 2. Suppose that A is an inverse of an integer-valued matrix. Then

D(X, 1/N) ≤ 3 inf_{ρ} D(X, ρ),

where the infimum is taken over all functions ρ : X → ℝ.

The situation becomes more complicated if the inverse matrix A^{−1} has some non– integer entries. Indeed, the method for proving Theorem 1 does not extend directly to this more general case. Consequently, we are only able to prove a result analogous to Corollary 2 above.

More precisely, our aim is to show that there is some positive constant c = c(s), depending only on the dimension s, such that D(X, 1/N) ≤ c(s)D(X, ρ) for every matrix net (X, ρ).

Theorem 3. Suppose that A is an arbitrary invertible real matrix. Then

D(X, 1/N) ≤ (2s)^{2s} inf_{ρ} D(X, ρ),

where the infimum is taken over all functions ρ : X → ℝ.

In fact, the multiplicative constant on the right hand side can be slightly improved. However, we make no serious attempt here to optimize this constant.

We shall prove Theorem 1 in §2, Theorem 2 in §3 and Theorem 3 in §§4–5.

The use of lattices in discrepancy problems is motivated by the study of the sequence {nα} of the fractional parts of nα, and dates back to the work of Hardy and Littlewood, Kronecker, Ostrowski, Weyl and others in the first half of this century. Later, Davenport [4] used lattices to show that Roth’s celebrated result on irregularities of distribution is best possible in dimension 2, and Korobov [5] initiated systematic studies of parallelepipedal nets, which are a special case of nets generated by inverses of integer-valued matrices. For more recent work involving the use of lattices in discrepancy theory, see the papers of Beck and Chen [1–3] and Skriganov [6].

2. Proof of Theorem 1

The proof of Theorem 1 is based on the following observation concerning matrix nets arising from matrices whose inverses have integer entries. For every y = (y_{1}, …, y_{s}) ∈ ℝ^{s}, write

{y} = ({y_{1}}, …, {y_{s}}) ∈ U^{s};

in other words, {y} is obtained from y by replacing each coordinate by its fractional part.

Lemma 1. Suppose that A is an inverse of an integer-valued matrix. Then for every fixed w ∈ Λ, we have

{{x + w} : x ∈ X} = X;

in other words, the set X is invariant under translation modulo U^{s} by any vector of Λ.

Proof. For every i = 1, …, s, let

e_{i} = (\underbrace{0, …, 0}_{i−1}, 1, \underbrace{0, …, 0}_{s−i}).

To prove the lemma, we shall first prove that ℤ^{s} ⊆ Λ by showing that e_{i} ∈ Λ for every i = 1, …, s. Let m_{i} denote the i–th column of the matrix A^{−1}. Then clearly

m_{i} = A^{−1}e_{i} ∈ ℤ^{s},

where m_{i} and e_{i} are written as column matrices. It follows that

e_{i} = Am_{i} ∈ Λ

as required. Next, for any fixed w ∈ Λ, consider the mapping φ : X → U^{s}, defined by φ(x) = {x + w} for every x ∈ X. Since x + w ∈ Λ and x + w − {x + w} ∈ ℤ^{s} ⊆ Λ, it follows that {x + w} ∈ Λ, so that φ maps X into itself. On the other hand, φ is clearly injective, as φ(x′) = φ(x′′) implies x′′ − x′ ∈ ℤ^{s}, and hence x′′ = x′ since x′, x′′ ∈ U^{s}. The assertion now follows since any injective mapping of a finite set into itself is necessarily a bijection. ♣

We can now complete the proof of Theorem 1. First of all, it is obvious that

inf_{ρ} R(Φ; X, ρ) ≤ inf_{ρ_{0}} R(Φ; X, ρ_{0}),

so it remains to show that

inf_{ρ} R(Φ; X, ρ) ≥ inf_{ρ_{0}} R(Φ; X, ρ_{0}).

To do this, it clearly suffices to show that for every ρ : X → ℝ, there exists ρ_{0} ∈ ℝ such that

R(Φ; X, ρ) ≥ |R(f; X, ρ_{0})|  (5)

for every f ∈ Φ. We choose

ρ_{0} = \frac{1}{N} ∑_{x∈X} ρ(x).  (6)

In view of (Φ3), we have, for any y ∈ ℝ^{s},

| ∑_{x∈X} ρ(x)f_{y}(x) − ∫_{U^{s}} f_{y}(t)dt| ≤ R(Φ; X, ρ).

This, in view of (Φ2), can be rewritten as

| ∑_{x∈X} ρ(x)f(x + y) − ∫_{U^{s}} f(t)dt| ≤ R(Φ; X, ρ).  (7)

The key idea here is to take an average over all y ∈ X. More precisely, in view of (Φ2), Lemma 1 and (6), we have

\frac{1}{N} ∑_{y∈X} ∑_{x∈X} ρ(x)f(x + y) = \frac{1}{N} ∑_{x∈X} ρ(x) ∑_{y∈X} f(x + y) = \frac{1}{N} ∑_{x∈X} ρ(x) ∑_{y∈X} f(\{x + y\})

= \frac{1}{N} ∑_{x∈X} ρ(x) ∑_{y∈X} f(y) = ρ_{0} ∑_{y∈X} f(y) = ∑_{x∈X} ρ_{0}f(x).

It follows that

| ∑_{x∈X} ρ_{0}f(x) − ∫_{U^{s}} f(t)dt| ≤ \frac{1}{N} ∑_{y∈X} | ∑_{x∈X} ρ(x)f(x + y) − ∫_{U^{s}} f(t)dt| ≤ R(Φ; X, ρ).

This establishes the inequality (5), and completes the proof of Theorem 1.

3. Integral Nets with Normalized Weights

Suppose that for some f ∈ Φ and every constant C ∈ ℝ, we also have f + C ∈ Φ. Then

R(f + C; X, ρ_{0}) = ∑_{x∈X} ρ_{0}f(x) − ∫_{U^{s}} f(t)dt + (ρ_{0}N − 1)C.

It follows that

R(Φ; X, ρ_{0}) = sup_{f∈Φ} |R(f; X, ρ_{0})|

can be finite only if ρ_{0} = 1/N. In this case, we clearly have

R(Φ; X, 1/N) = inf_{ρ_{0}} R(Φ; X, ρ_{0}).

Theorem 2 establishes a conclusion of this type, but under far less restrictive and more acceptable conditions.

Note that the first condition in hypothesis (b) of Theorem 2 cannot be replaced by the weaker condition

inf_{ρ_{0}} R(Φ; X, ρ_{0}) ≤ M(Φ).

Consider, for example, the class Φ of all Riemann integrable functions f : ℝ^{s} → ℝ, periodic with period 1 in each variable and satisfying the condition that

|∫_{U^{s}} f(t)dt| ≤ 1.

Obviously, for this class, M(Φ) = 1 and

inf_{ρ} R(Φ; X, ρ) ≤ inf_{ρ_{0}} R(Φ; X, ρ_{0}) ≤ R(Φ; X, 0) = 1,

but R(Φ; X, 1/N) = ∞. On the other hand, the condition M(Φ) > 0 is also necessary. Consider, for example, the class Φ of all Riemann integrable functions f : ℝ^{s} → ℝ, periodic with period 1 in each variable and satisfying the condition that

∫_{U^{s}} f(t)dt = 0.

Obviously, for this class, M(Φ) = 0 and

0 ≤ inf_{ρ} R(Φ; X, ρ) ≤ inf_{ρ_{0}} R(Φ; X, ρ_{0}) ≤ R(Φ; X, 0) = 0,

but again R(Φ; X, 1/N) = ∞.

To prove Theorem 2, we need the following lemma.

Lemma 2. For any net (X, ρ), we have

R(Φ; X, ρ) ≥ |Nρ_{0} − 1|M(Φ),

where ρ_{0} is defined by (6).

Proof. We return to the inequality (7), and apply a different averaging argument. Instead of averaging over all y ∈ X, we integrate over y ∈ U^{s}, and obtain

|∫_{U^{s}} ( ∑_{x∈X} ρ(x)f(x + y) − ∫_{U^{s}} f(t)dt) dy| ≤ R(Φ; X, ρ).

In view of (Φ2), this gives

| ∑_{x∈X} ρ(x) − 1| |∫_{U^{s}} f(t)dt| ≤ R(Φ; X, ρ).

The assertion follows on taking the supremum over all f ∈ Φ and noting (6). ♣

To prove Theorem 2, we shall in fact only use Lemma 2 in the case of constant weight functions ρ(x) = ρ_{0}. In this case, we have

R(Φ; X, ρ_{0}) ≥ |Nρ_{0} − 1|M(Φ).  (8)

We assume, for the sake of simplicity, that the infimum inf_{ρ_{0}} R(Φ; X, ρ_{0}) is attained for some number ρ_{0} ∈ ℝ, so that by Theorem 1, we have

R(Φ; X, ρ_{0}) = inf_{ρ} R(Φ; X, ρ).

Consider first the case |Nρ_{0}| < 2ε/3. By (8), we have

R(Φ; X, ρ_{0}) ≥ |Nρ_{0} − 1|M(Φ) ≥ (1 − \frac{2ε}{3}) M(Φ),

contradicting hypothesis (b) of Theorem 2. It follows that hypothesis (a) is valid, and so

R(Φ; X, ρ_{0}) ≥ (1 − \frac{2ε}{3}) M(Φ) ≥ (1 − \frac{2ε}{3}) εR(Φ; X, 1/N) ≥ \frac{ε}{3}R(Φ; X, 1/N).

On the other hand, if |Nρ_{0}| ≥ 2ε/3, then for every f ∈ Φ, we have

R(f; X, 1/N) = \frac{1}{N} ∑_{x∈X} f(x) − ∫_{U^{s}} f(t)dt

= \frac{1}{Nρ_{0}} ( ∑_{x∈X} ρ_{0}f(x) − ∫_{U^{s}} f(t)dt) − (1 − \frac{1}{Nρ_{0}} ) ∫_{U^{s}} f(t)dt,

so that

|R(f; X, 1/N)| ≤ \frac{1}{|Nρ_{0}|}R(Φ; X, ρ_{0}) + \frac{|Nρ_{0} − 1|}{|Nρ_{0}|} |∫_{U^{s}} f(t)dt|

≤ \frac{2}{|Nρ_{0}|}R(Φ; X, ρ_{0}) ≤ \frac{3}{ε}R(Φ; X, ρ_{0}),

in view of (1) and (8). This completes the proof of Theorem 2.

4. Preparation for the Proof of Theorem 3

We note first that if B ⊆ U^{s}, then (2) becomes simply

D_{B}(X, ρ) = ∑_{x∈Λ∩B} ρ(x) − μ(B).  (9)

Furthermore, if B contains no points of Λ, then D(X, ρ) ≥ μ(B). Indeed, this last inequality remains valid for any aligned rectangular box B ⊆ U^{s} which is free of points of Λ, even without the additional restriction that B ∈ 𝔅, as B can be “approximated” by another box in 𝔅. We shall use this remark later in the course of the proof of Theorem 3.

It will be convenient to consider, along with D(X, ρ), the corresponding discrepancy function arising only from those rectangular boxes B ∈ 𝔅 contained in U^{s}. Accordingly, we denote by \overline{𝔅} the collection of all boxes B ∈ 𝔅 such that B ⊆ U^{s}, and write

\overline{D}(X, ρ) = sup_{B∈\overline{𝔅}} |D_{B}(X, ρ)|,  (10)

where the supremum is taken over all rectangular boxes B ∈ \overline{𝔅}. As before, in the case of constant weight functions ρ(x) = ρ_{0}, we shall use the notation \overline{D}(X, ρ_{0}).

Clearly, we have \overline{D}(X, ρ) ≤ D(X, ρ) for any matrix net (X, ρ). In the other direction, we have the following result.

Lemma 3. We have D(X, ρ) ≤ 2^{s}\overline{D}(X, ρ).

Proof. For any box B ∈ 𝔅, there obviously exist at most 2^{s} integer vectors c_{i} ∈ ℤ^{s} and aligned rectangular boxes B_{i} ∈ \overline{𝔅} such that

B = ⋃_{i}(c_{i} + B_{i}),

and where the union is disjoint. Then it follows easily from (2) and (10) that

|D_{B}(X, ρ)| = |∑_{i} D_{c_{i}+B_{i}}(X, ρ)| = |∑_{i} D_{B_{i}}(X, ρ)| ≤ 2^{s}\overline{D}(X, ρ),

and the conclusion follows on taking the supremum over all B ∈ 𝔅. ♣

It now follows from Lemma 3 that, to prove Theorem 3, it suffices to establish the estimate

\overline{D}(X, 1/N) ≤ 2^{s}s^{2s}\overline{D}(X, ρ)  (11)

for every matrix net (X, ρ).

The idea underpinning the proof of Theorem 3 is to approximate the discrepancy function D_{B}(X, ρ) by another discrepancy function D_{B}(Λ), arising from the lattice Λ and not from the matrix net (X, ρ). We shall define this new discrepancy function by assigning to each point of Λ the “correct” weight det Λ, instead of the “approximation” 1/N. For technical reasons, we shall also consider the supremum of D_{B}(Λ) on all boxes B ∈ 𝔅, not necessarily in U^{s} and not reduced modulo U^{s}. This enables us to apply the averaging argument used in the proof of Theorem 1 to this new discrepancy function.

More precisely, for every B ∈ 𝔅, write

D_{B}(Λ) = ∑_{x∈Λ∩B} det Λ − μ(B),  (12)

and let

D(Λ) = sup_{B∈𝔅} |D_{B}(Λ)|,

where the supremum is taken over all aligned rectangular boxes in the collection 𝔅.

For any set B ⊆ ℝ^{s}, let N_{B}(Λ) = |Λ ∩ B|, the number of points of Λ in B (hence, for instance, N_{U^{s}}(Λ) = N). Then (12) becomes

D_{B}(Λ) = N_{B}(Λ) det Λ − μ(B),

and so

|N_{B}(Λ) − \frac{μ(B)}{det Λ}| ≤ \frac{D(Λ)}{det Λ}  (13)

for any B ∈ 𝔅.

Lemma 4. We have \overline{D}(X, 1/N) ≤ 2D(Λ).

Proof. Suppose that B ∈ \overline{𝔅}. Then it follows from (9) and (12) that

|D_{B}(Λ) − D_{B}(X, 1/N)| = |det Λ − \frac{1}{N} | ∑_{x∈Λ∩B} 1 ≤ |N det Λ − 1|,

so that

|D_{B}(X, 1/N)| ≤ |D_{B}(Λ)| + |N det Λ − 1| ≤ D(Λ) + |N det Λ − 1|.

Note next that U^{s} ∈ 𝔅, so that

|N det Λ − 1| = |D_{U^{s}}(Λ)| ≤ D(Λ).

Hence

|D_{B}(X, 1/N)| ≤ 2D(Λ).

The result now follows on taking the supremum over all B ∈ \overline{𝔅}. ♣

For any B ∈ 𝔅 and any x ∈ Λ, consider the aligned rectangular box

B_{x} = (x − B) ∩ U^{s},

where x − B = {x − y : y ∈ B}. Note here that B_{x} ∉ 𝔅 in general. Clearly, B_{x} is non–empty if and only if x ∈ U^{s} + B = {y + z : y ∈ B, z ∈ U^{s}}. Lemma 5. The number N_{U^{s}+B}(Λ) = |Λ ∩ (U^{s} + B)| of all lattice points x ∈ Λ for which B_{x} = (x − B) ∩ U^{s} is non–empty satisfies

N_{U^{s}+B}(Λ) ≤ \frac{2^{s}(1 + D(Λ))}{det Λ}.

Proof. Clearly, the rectangular box U^{s} + B can be written as the disjoint union of at most 2^{s} rectangular boxes in 𝔅. Hence it follows from (13) that

N_{U^{s}+B}(Λ) ≤ \frac{μ(U^{s} + B) + 2^{s}D(Λ)}{det Λ},

and the result follows on noting that μ(U^{s} + B) ≤ 2^{s}. ♣

Our next lemma implements the averaging idea from the proof of Theorem 1 and is the heart of our argument. Lemma 6. For every B ∈ 𝔅, we have

|Nρ_{0} ∑_{x∈Λ∩B} 1 − 𝔖| ≤ N_{U^{s}+B}(Λ)\overline{D}(X, ρ),

where ρ_{0} is defined by (6) and

𝔖 = ∑_{x∈Λ} μ((x − B) ∩ U^{s}) = ∑_{x∈Λ} μ(B_{x}).  (14)

Proof. It is not difficult to see that given any box B_{x} = (x−B)∩U^{s} and any positive number ε, there exists B′_{x} ∈ \overline{𝔅} such that

|μ(B′_{x}) − μ(B_{x})| < ε and B′_{x} ∩ Λ = B_{x} ∩ Λ.

Since

| ∑_{y∈B′_{x}∩Λ} ρ(y) − μ(B′_{x})| ≤ \overline{D}(X, ρ),

and since ε can be chosen arbitrarily small, we have also

| ∑_{y∈B_{x}∩Λ} ρ(y) − μ(B_{x})| ≤ \overline{D}(X, ρ).

Summing over all x ∈ Λ for which B_{x} is non–empty, we obtain

|∑_{x∈Λ} ∑_{y∈B_{x}∩Λ} ρ(y) − ∑_{x∈Λ} μ(B_{x})| ≤ N_{U^{s}+B}(Λ)\overline{D}(X, ρ).  (15)

Note now that

∑_{x∈Λ} ∑_{y∈B_{x}∩Λ} ρ(y) = ∑_{x∈Λ} ∑_{y∈Λ∩(x−B)∩U^{s}} ρ(y)

= ∑_{y∈Λ∩U^{s}} ρ(y) ∑_{x∈Λ∩(y+B)} 1

= ∑_{y∈Λ∩U^{s}} ρ(y) ∑_{x∈Λ∩B} 1.  (16)

The result follows on combining (6) and (14)–(16). ♣

To calculate 𝔖, we need two more lemmas. Lemma 7. For every B ∈ 𝔅, we have

∫_{U^{s}} N_{B+x}(Λ)dx = 𝔖.  (17)

Furthermore, for any fundamental region R of the lattice Λ, we have

∫_{R} N_{B+x}(Λ)dx = μ(B).  (18)

Proof. We have

∫_{U^{s}} N_{B+x}(Λ)dx = ∫_{U^{s}} ( ∑_{y∈Λ∩(B+x)} 1) dx = ∑_{y∈Λ} ∫_{(y−B)∩U^{s}} dx

= ∑_{y∈Λ} μ((y − B) ∩ U^{s}) = 𝔖,

in view of (14). On the other hand,

∫_{R} N_{B+x}(Λ)dx = ∫_{R} ( ∑_{y∈Λ∩(B+x)} 1) dx = ∑_{y∈Λ} ∫_{(y−B)∩R} dx

= ∑_{y∈Λ} ∫_{B∩(y−R)} dz = ∫_{B} dz = μ(B).  ♣

Suppose now that R is a fixed fundamental region of Λ. We write U^{s} = Ω_{0} ∪ Ω_{1}, where

Ω_{0} = ⋃_{{w∈Λ \atop R+w⊆U^{s}}} (R + w)  and  Ω_{1} = U^{s} \ Ω_{0}.  (19)

Then it follows from (17) that

𝔖 = ∫_{Ω_{0}} N_{B+x}(Λ)dx + ∫_{Ω_{1}} N_{B+x}(Λ)dx.  (20)

Lemma 8. For every B ∈ 𝔅, we have

∫_{Ω_{0}} N_{B+x}(Λ)dx = \frac{μ(B)μ(Ω_{0})}{det Λ}.

Furthermore,

|∫_{Ω_{1}} N_{B+x}(Λ)dx − \frac{μ(B)μ(Ω_{1})}{det Λ}| ≤ \frac{μ(Ω_{1})D(Λ)}{det Λ}.

Proof. We have, by (18) and (19), that

∫_{Ω_{0}} N_{B+x}(Λ)dx = ∑_{{w∈Λ \atop R+w⊆U^{s}}} ∫_{R+w} N_{B+x}(Λ)dx = ∑_{{w∈Λ \atop R+w⊆U^{s}}} μ(B)

= \frac{μ(B)}{μ(R)} ∑_{{w∈Λ \atop R+w⊆U^{s}}} μ(R) = \frac{μ(B)μ(Ω_{0})}{μ(R)} = \frac{μ(B)μ(Ω_{0})}{det Λ}.

This proves the first assertion. The second assertion follows immediately on applying (13) to the box B + x and integrating with respect to x over Ω_{1}. ♣

To use Lemma 8, we need an estimate for μ(Ω_{1}).

Lemma 9. Suppose that s ≥ 2. Suppose further that for every fundamental region R of the lattice Λ, the inequality μ(Ω_{1}) > 1/2 holds. Then D(X, ρ) > (2s)^{−2s} for any choice of the weight function ρ.

Proof. Consider the aligned cube

𝔔 = \{x = (x_{1}, …, x_{s}) ∈ ℝ^{s} : |x_{i}| ≤ \frac{1}{4s^{2}} \} ,

centred at the origin. We claim that this cube cannot possibly contain s linearly independent vectors of Λ. Indeed, if it does, then for the fundamental region R generated by those s points, we have

d = sup_{x,y∈R} max_{1≤i≤s} |x_{i} − y_{i}| ≤ \frac{1}{4s},

where the supremum is taken over all pairs of vectors x = (x_{1}, …, x_{s}), y = (y_{1}, …, y_{s}) in R. But U^{s} has 2s faces, each of area 1, so that μ(Ω_{1}) ≤ 2sd ≤ 1/2, clearly a contradiction. It follows that all the points of 𝔔 ∩ Λ lie on some (s − 1)–dimensional hyperplane L. We now consider the 2^{s} open cubes

𝔔(δδδ) = {x ∈ 𝔔 : δ_{i}x_{i} > 0 for every i = 1, …, s},

where δδδ = (δ_{1}, …, δ_{s}) ∈ {−1, 1}^{s}. At most 2^{s−1} of these can have a non–empty intersection with L. Hence at least one of these small cubes, say 𝔔_{0}, does not contain any point of Λ. We observe that the edge length of 𝔔_{0} is 1/(4s^{2}). Now consider the cube

B = \{x = (x_{1}, …, x_{s}) ∈ U^{s} : \frac{1}{4s^{2}} ≤ x_{1}, …, x_{s} < 1 − \frac{1}{4s^{2}} \} .

If B ∩ Λ is empty, then it follows from (3) and (9) that

D(X, ρ) ≥ μ(B) = (1 − \frac{1}{2s^{2}} )^{s} ≥ (\frac{1}{2s^{2}} )^{s} > (2s)^{−2s}.

On the other hand, if B ∩ Λ is non–empty, then there exists a lattice vector y ∈ B ∩ Λ. Consider the translation 𝔔_{0} + y. Since 𝔔_{0} ∩ Λ = ∅, we clearly have (𝔔_{0} + y) ∩ Λ = ∅. Note also that 𝔔_{0} + y ⊆ U^{s}. Hence it follows again from (3) and (9) that

D(X, ρ) ≥ μ(𝔔_{0} + y) = μ(𝔔_{0}) = (4s^{2})^{−s} = (2s)^{−2s}.  ♣

5. Completion of the Proof of Theorem 3

Suppose first of all that s = 1. If det Λ > 1, then the distance between any two neighbouring points of Λ is greater than 1. Hence for any weight function ρ, we clearly have

D(X, ρ) ≥ 1 = D(X, 1/N).

If det Λ ≤ 1, then the distance between any two neighbouring points of Λ is det Λ ≤ 1, so that D(X, ρ) ≥ det Λ for any ρ and hence by Lemmas 3 and 4,

D(X, 1/N) ≤ 2\overline{D}(X, 1/N) ≤ 4D(Λ) = 4 det Λ ≤ 4D(X, ρ)

as required. For the remainder of this paper, we shall assume that s ≥ 2.

Suppose that B ∈ 𝔅, and that ρ_{0} and 𝔖 are defined by (6) and (14) respectively. Then

|D_{B}(Λ)| = | ∑_{x∈Λ∩B} det Λ − μ(B)| ≤ I_{1} + I_{2} + |𝔖 det Λ − μ(B)|,  (21)

where

I_{1} = |(1 − Nρ_{0}) ∑_{x∈Λ∩B} det Λ|  and  I_{2} = |Nρ_{0} ∑_{x∈Λ∩B} det Λ − 𝔖 det Λ| .

It is easy to see from (6), (9) and (10) that

|Nρ_{0} − 1| = |D_{U^{s}}(X, ρ)| ≤ \overline{D}(X, ρ).

On the other hand, it follows from (13) that

∑_{x∈Λ∩B} det Λ = N_{B}(Λ) det Λ ≤ μ(B) + D(Λ) ≤ 1 + D(Λ).

Hence

I_{1} ≤ \overline{D}(X, ρ)(1 + D(Λ)).  (22)

Next, it follows from Lemma 6 and Lemma 5 that

I_{2} ≤ 2^{s}\overline{D}(X, ρ)(1 + D(Λ)).  (23)

Finally, it follows from (20), Lemma 8 and μ(Ω_{0}) + μ(Ω_{1}) = 1 that

|𝔖 det Λ − μ(B)| ≤ μ(Ω_{1})D(Λ).  (24)

In view of Lemma 9, we may assume that there exists a fundamental region R such that μ(Ω_{1}) < 1/2. We may also assume, without loss of generality, that

\overline{D}(X, ρ) < 2^{−s}s^{−2s};  (25)

for otherwise \overline{D}(X, 1/N) ≤ 1 ≤ 2^{s}s^{2s}\overline{D}(X, ρ), so that (11) follows immediately. Substituting (22)–(24) into (21) and noting (25), we get

|D_{B}(Λ)| ≤ (2^{s} + 1)\overline{D}(X, ρ)(1 + D(Λ)) + μ(Ω_{1})D(Λ)

≤ 2^{s+1}\overline{D}(X, ρ)(1 + D(Λ)) + \frac{1}{2}D(Λ)

≤ 2^{s+1}\overline{D}(X, ρ) + (2s^{−2s} + \frac{1}{2}) D(Λ)

≤ 2^{s+1}\overline{D}(X, ρ) + \frac{3}{4}D(Λ).

Taking the supremum over all B ∈ 𝔅, we obtain

D(Λ) ≤ 2^{s+1}\overline{D}(X, ρ) + \frac{3}{4}D(Λ),

so that

D(Λ) ≤ 2^{s+3}\overline{D}(X, ρ).

It now follows from Lemma 4 that

\overline{D}(X, 1/N) ≤ 2^{s+4}\overline{D}(X, ρ).

The inequality (11) follows on noting that 2^{s+4} ≤ 2^{s}s^{2s}. This completes the proof of Theorem 3.

References

1. J. Beck and W.W.L. Chen, “Irregularities of point distribution relative to half– planes I”, Mathematika, 40 (1993), 102–126.

2. J. Beck and W.W.L. Chen, “Irregularities of point distribution relative to convex polygons II”, Mathematika, 40 (1993), 127–136.

3. J. Beck and W.W.L. Chen, “Irregularities of point distribution relative to convex polygons III”, J. London Math. Soc. (to appear).

4. H. Davenport, “Note on irregularities of distribution”, Mathematika, 3 (1956), 131–135.

5. N.M. Korobov, Number-theoretical methods in approximation analysis, Moscow, 1963.

6. M.M. Skriganov, “Constructions of uniform distributions in terms of geometry of numbers”, St. Petersburg Math. J. (Algebra i Analiz), 6 (1994), 200–230.

W.W.L. Chen  V.F. Lev
Department of Mathematics  Department of Mathematics
Macquarie University  The University of Georgia
Sydney NSW 2109  Athens GA 30602