On Two Versions of L^{2}-Discrepancy and Geometrical Interpretation of Diaphony

Vsevolod F. Lev ^{∗}

Abstract

The present paper concentrates on a comparison of two versions of L^{2}- discrepancy: the “usual” one and the one “on parallelepipeds modulo the unit cube.” We also show that the last variant of discrepancy is closely connected with diaphony, and in the most important case the two characteristics of distribution coincide up to a multiplicative constant.

Part of the results of this paper was earlier published in provisional form in [3] (Russian).

1 Notation and Definitions

Let ℚ^{s} be the s-dimensional unit cube:

ℚ^{s} = {x ∈ ℝ^{s} | 0 ≤ x_{j} < 1 ; j = 1, …, s}

or, equally,

ℚ^{s} = {x ∈ ℝ^{s} | 0 ≤ x < 1}

(we reserve lower indexes for coordinates of vectors and write 0 = (0, …, 0) and 1 = (1, …, 1)).

By a net S = (X, ρ) we will mean a finite weighted set of points in ℚ^{s}, that is, a set of points in the unit cube:

X = {x^{(k)} ∈ ℚ^{s} | k = 1, …, N}

and a set of real weights, corresponding to these points:

ρ = {ρ_{k} ∈ ℝ^{s} | k = 1, …, N} .

∗School of Mathematical Sciences, Tel-Aviv University, 69987 Tel-Aviv, Israel.

The pair (x^{(k)}, ρ_{k}) is said to be the k-th node of the net S, and ρ_{0} will denote the sum of the net’s weights: ρ_{0} = ρ_{1} + ⋯ + ρ_{N}.

Numeration of net’s nodes is not essential: we will not distinguish nets differing only by order of following their nodes.

Generally speaking, we do not impose any additional restrictions on the points (some of them may coincide) or on the weights (their sum may differ from 1). A net having the sum of its weights equal to 1 (that is, a net with ρ_{0} = 1) we will refer to as a normalized one; in such a case, the system of weights will also be called normalized. Therefore, for the normalized net with N nodes and with equal weights we have:

ρ_{1} = ⋯ = ρ_{N} = 1/N .

It should be pointed out, that those “traditional” nets are included, as a particular case, in all of the results of this paper. In other words, none of the results are based on using some “exotic” weights.

By a shift of a system of points X by a vector x modulo ℚ^{s} we will mean the new system of points in ℚ^{s}

X + x = {{x^{(k)} + x} | k = 1, …, N}

(the inner figure parentheses denote the vector’s fractional part, that is, the vector of fractional parts of coordinates).

By a shift of a net S by a vector x modulo ℚ^{s} we will mean the new net S + x = (X + x, ρ) with the nodes

({x^{(k)} + x}, ρ_{k}) , k = 1, …, N .

For 1 ≤ t ≤ s let ℚ^{t} be some t-dimensional face of ℚ^{s}, and let π be the operator of orthogonal projection of ℚ^{s} to ℚ^{t}. By the projection of S to ℚ^{t} we will mean the new net S′ = (X′, ρ) in ℚ^{t}, whose nodes (x^{′(k)}, ρ_{k}) are defined by

x^{′(k)} = π(x^{(k)}) .

Let I ⊂ {1, …, s} be a system of indexes, Σ be the corresponding system of sdimensional hyperplanes

x_{i} = 1/2 (i ∈ I)

and σ : ℚ^{s} → ℚ^{s} be the transformation of the unit cube to itself, involving symmetries relative to all hyperplanes from Σ, followed by obtaining of fractional parts (order of executing these operations obviously does not influence the result). By the image of S under the transformation σ (or under symmetry relative to the hyperplanes of the system Σ) we will mean the net S′ = (X′, ρ) in ℚ^{s}, whose nodes (x^{′(k)}, ρ_{k}) are defined by

x^{′(k)} = σ(x^{(k)}) ,

so that

x_{i}^{′(k)} = \{ \begin{matrix}\{1 − x_{i}^{(k)}\} ; & i ∈ I , \\ x_{i}^{(k)} ; & i ∉ I . \end{matrix}

We’ll call the net symmetric, if it coincides with its image under any transformation of the described type.

For u, v ∈ ℝ^{s} consider the parallelepiped

Π(u, v) = {x ∈ ℝ^{s} | u ≤ x < v}

(the parallelepiped is non-empty only if u < v). Let’s denote its volume by |Π(u, v)| and introduce the local discrepancy of net S in Π(u, v) by

R(u, v) = ∑_{x^{(k)}∈Π(u,v) (mod ℚ^{s})}ρ_{k} − |Π(u, v)|  (1)

(where the summing is extended over all points x^{(k)} of the net S, belonging to Π(u, v) “modulo the unit cube”, that is, over those points x^{(k)}, some integral shift of which belongs to Π(u, v)). Clearly, the local discrepancy R(u, v) is invariant relative to shifts of Π(u, v) by any integer vector.

For κ ∈ [1; ∞] let’s define L^{κ}-discrepancy of a net S by

D_{κ}(S) = ∥R(0, ·)∥_{κ} ,  (2)

that is

D_{κ}(S) = (∫_{ℚ^{s}} |R(0, γ)|^{κ}dγ)^{1/κ} , κ < ∞ ,

and

D_{∞}(S) = sup_{γ∈ℚ^{S}} |R(0, γ)| ;

we set also

D̃_{κ}(S) = (∫_{ℚ^{s}×ℚ^{s}} |R(α, α + γ)|^{κ}dαdγ)^{1/κ} , κ < ∞ ,

(3)

D̃_{∞}(S) = sup_{α,γ∈ℚ^{s}} |R(α, α + γ)| .

The value, defined by (3), we will call the Weyl L^{κ}-discrepancy of the net S.

In particular, in the case of κ = 2 we obtain the L^{2}-discrepancy D_{2}(S) and the Weyl L^{2}-discrepancy D̃_{2}(S), and in the case of κ = ∞ — the supreme discrepancy D_{∞}(S) and the Weyl supreme discrepancy D̃_{∞}(S). The supreme discrepancy D_{∞}(S) is often called just discrepancy and is denoted by D(S); similarly, Weyl supreme discrepancy D̃_{∞}(S) we will denote simply by D̃(S).

Let S + α be the shift of S by a vector α ∈ ℚ^{s}, and R_{α} be the local discrepancy of S + α. It is obvious from (1), that R_{α}(0, γ) = R(−α, −α + γ), and therefore, according to definitions (2) and (3),

D̃_{κ}(S) = (∫_{ℚ^{s}} |D_{κ}(S + α)|^{κ}dα)^{1/κ} ,

that is, the Weyl L^{κ}-discrepancy D̃_{κ}(S) may be considered as the L^{κ}-average of “usual” L^{κ}-discrepancies D_{κ}(S + α) of all shifts of S by vectors α from ℚ^{s}.

2 Diaphony F_{2}(S) and its Connection with Weyl L^{2}- Discrepancy D̃_{2}(S)

One more characteristic of multidimensional net S = (X, ρ) distribution uniformity,

— diaphony, denoted by us F_{2}(S) — was introduced first by P. Zinterhof in 1976 (see [5]) and then considered by a number of authors (see, for instance, [1], [3], [4]). There are two well-known “classic” definitions of diaphony. We’ll reproduce them with some changes, caused, mainly, by our intention to consider (unlike the “classic” approach) the general case of nets with arbitrary weights.

One of the definitions uses the representation by infinite series:

F_{2}(S) = (\begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \frac{|T (m)|^{2}}{\overline{m}^{2}} )^{1/2} ,

where

\overline{m} = \overline{m}_{1} ⋯ \overline{m}_{s} , \overline{m}_{j} = max(1, |m_{j}|) ,

T (m) is a trigonometric sum of the net S, defined by

T (m) = ∑_{k=1}^{N} ρ_{k} · e^{2πi<m·x^{(k)}>}

(< m · x^{(k)} > is vectors m and x^{(k)} scalar product), and, finally, the dash in the sum sign means, that zero vector m = 0 should be excluded from the sum.

Another definition:

F_{2}(S) = ( ∑_{k,l=1}^{N} ρ_{k}ρ_{l} ∏_{j=1}^{s} (1 + 2π^{2}B_{2}({x_{j}^{(k)} − x_{j}^{(l)}})) − ρ_{0}^{2})^{1/2} ,

where B_{2}(ξ) = ξ^{2}−ξ+1/6 is the Bernoulli polynomial of order 2 (and ρ_{0} = ρ_{1}+⋯+ρ_{N}).

The equivalence of the two definitions mentioned above can be easily verified in view of the well-known expansion B_{2}(ξ) into a Fourier series:

B_{2}(ξ) = \frac{1}{2π^{2}} \begin{matrix}∑ & ′ \\ m∈ℤ \end{matrix} \frac{1}{\overline{m}^{2}} e^{2πimξ} .

We state below three exciting properties of diaphony, following almost immediately from the above definitions.

Statement 1. Let S + α be a shift of S by a vector α ∈ ℚ. Then F_{2}(S + α) = F_{2}(S).

Proof. This follows from the “second definition” in view of {{x_{j}^{(k)} + α} − {x_{j}^{(l)} + α}} = {x_{j}^{(k)} − x_{j}^{(l)}}.

Statement 2. Let S′ = π(S) be a projection of S. Then F_{2}(S′) ≤ F_{2}(S).

Proof. We can suppose that the projection π is defined by

π((x_{1}, x_{2}, …, x_{s})) = (0, x_{2}, …, x_{s}),

and let T′ be a trigonometric sum of the net S′. Then, obviously,

T ((0, m_{2}, …, m_{s})) = T′((m_{2}, …, m_{s})) ,

and according to the “first definition”,

F_{2}^{2}(S) =\begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \frac{|T (m)|^{2}}{\overline{m}^{2}} ≥_{\begin{matrix}∑ & ′ \\ m∈ℤ^{s}, m_{1}=0 \end{matrix}} \frac{|T (m)|^{2}}{\overline{m}^{2}} = F_{2}^{2}(S′) .

Statement 3. Let S′ = σ(S) be an image of S under some symmetry σ. Then F_{2}(S′) = F_{2}(S).

Proof. Again, we can consider only the particular case of the symmetry σ defined by

σ((x_{1}, x_{2}, …, x_{s})) = ({1 − x_{1}}, x_{2}, …, x_{s}) .

and let T′ be a trigonometric sum of the net S′. Then, obviously,

T′((m_{1}, m_{2}, …, m_{s})) = T ((−m_{1}, m_{2}, …, m_{s})) ,

and we use the first definition to complete our proof.

Do these three statements hold for discrepancies D̃_{2}(S) and D_{2}(S) instead of diaphony F_{2}(S)? As we show later, the answer is affirmative for D̃_{2}(S) and negative for D_{2}(S).

Note that, unlike discrepancies, diaphony has pure analytic definitions which does not explain its “geometrical nature”. The following theorem^{1} clarifies this nature by establishing a direct connection between diaphony and Weyl L^{2}-discrepancy D̃_{2}(S).

Theorem 1. The following equality holds:

D̃_{2}^{2}(S) = 3^{−s} (\begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \frac{|T (m)|^{2}}{\overline{m}^{2}} · (\frac{3}{2π^{2}} )^{ν(m)} + |T (0) − 1|^{2}) ,

where the sum is extended over all non-zero s-dimensional integer vectors, and ν(m) is the number of non-zero coordinates of m.

Proof. Let us consider the local discrepancy R(α, α + γ) as a function of α with fixed γ, and evaluate its Fourier coefficients. If m ≠ 0, then the corresponding coefficient is

R̂(m) = ∫_{ℚ^{s}} R(α, α + γ)e^{−2πi<m·α>}dα =
= ∑_{k=1}^{N} ρ_{k} ∫_{x^{(k)}−γ<α≤x^{(k)}} e^{−2πi<m·α>}dα =

= ∑_{k=1}^{N} ρ_{k}e^{−2πi<m·x^{(k)}>} ∫_{−γ<α≤0} e^{−2πi<m·α>}dα =
= T (−m) ∫_{0≤α<γ} e^{2πi<m·α>}dα ;

1this theorem was first proved by the author in [3] (Russian). However, we reproduce it here for the sake of completeness.

and if m = 0, then

R̂(m) = R̂(0) = T (0) ∫_{0≤α<γ} dα − ∫_{ℚ^{s}} γ_{1} ⋯ γ_{s}dα =
= (T (0) − 1)γ_{1} ⋯ γ_{s} .

Hence, using Parseval’s equality, from the definition (3) we obtain:

D̃_{2}^{2}(S) = ∫_{ℚ^{s}} \begin{matrix}∑ & ′ \\ m \end{matrix} |T (m)|^{2} · |∫_{0≤α<γ} e^{2πi<m·α>}dα|^{2} dγ +
+ ∫_{ℚ^{s}} |T (0) − 1|^{2}γ_{1}^{2} ⋯ γ_{s}^{2}dγ =
= \begin{matrix}∑ & ′ \\ m \end{matrix} |T (m)|^{2} ∏_{j=1}^{s} ∫_{0}^{1} |∫_{0}^{γ_{j}} e^{2πim_{j}α_{j}}dα_{j}|^{2} dγ_{j} +
+ 3^{−s}|T (0) − 1|^{2} ,

and we have only to note, that the jth integral under the product sign is equal to \frac{1}{3\overline{m}_{j}^{2}} , if m_{j} = 0, and is equal to \frac{1}{3\overline{m}_{j}^{2}} · \frac{3}{2π^{2}} otherwise.

The theorem proved is a direct analog of the well-known Erdős-Turan inequality for the metrics of L^{2}. It shows, that up to a multiplicative constant and the summand measuring “normalization”, the diaphony of the net coincides with its Weyl L^{2}-discrepancy. In particular, for normalized nets we immediately obtain the following

Corollary 1. Let S be normalized: ρ_{0} = 1; then

(2π^{2} · 3^{s−1})^{1/2}D̃_{2}(S) ≤ F_{2}(S) ≤ (2π^{2})^{s/2}D̃_{2}(S) .

Proof. It’s sufficient to use in Theorem 1 the obvious inequality 1 ≤ ν(m) ≤ s (m ≠ 0).

Corollary 2. Statements 1–3 hold for Weyl L^{2}-discrepancy D̃_{2}(S) instead of diaphony F_{2}(S).

Proof. Follows proof of Statements 1–3 with Theorem 1 instead of the “first definition” of diaphony, and (3) instead of the “second definition”.

3 D̃_{2} versus D_{2}: One-Dimensional Nets

The rest of the paper investigates the correspondence between Weyl L^{2}-discrepancy D̃_{2}(S) and diaphony F_{2}(S), on the one hand, and “usual” L^{2}-discrepancy D_{2}(S), on the other hand. We’ll see, that the question is not a trivial one, and even for normalized nets allows a direct solution only in a few particular cases.

We start from the simplest of them, the case of one-dimensional normalized nets. In this case one of the estimates, — of the type D̃_{2}(S) ≪ D_{2}(S), — follows easily

from

Lemma 1. Let S be a one-dimensional normalized net: s = 1, ρ_{0} = 1. Then

D_{2}^{2}(S) = \frac{1}{2π^{2}} F_{2}^{2}(S) + (∑_{k=1}^{N} ρ_{k}x^{(k)} − \frac{1}{2})^{2} .

Proof. The identity of the lemma is a “weighted variant” of a well-known identity (see, for instance, [2], equality (2.27)). It can be obtained by means of expansion of R(0, γ) into a Fourier series and then applying Parseval’s equality — the method, used in Theorem 1.

Corollary. Let S be a one-dimensional normalized net: s = 1, ρ_{0} = 1. Then

D̃_{2}(S) ≤ D_{2}(S) .

Proof. According to Theorem 1, in our case

D̃_{2}^{2}(S) = 3^{−1}F_{2}^{2}(S) · (3/2π^{2}) = F_{2}^{2}(S)/2π^{2} ,

and in view of Lemma 1,

D_{2}^{2}(S) ≥ F_{2}^{2}(S)/2π^{2} .

Is it possible to obtain an inverse estimate, that is, an estimate of the type D_{2}(S) ≪ D̃_{2}(S)? The following example, suitable for the general s-dimensional case, shows that it is not the case.

Example 1. Let S = (X, ρ) vary over a sequence of s-dimensional nets with the number of nodes increasing to infinity and Weyl supreme discrepancy decreasing to zero: N → ∞, D̃(S) → 0. Set

δ = (D̃(S))^{1/(s+0.5)} → 0 ,
P = {x ∈ ℚ^{s} | x ≥ (1 − δ)1} ,

(so that δ and P depend on S) and consider new net S′ = (Y, ρ) with the same weights as S and the system of points Y, defined by

y^{(k)} = \{ \begin{matrix}x^{(k)} ; & x^{(k)} ∉ P , \\ 0 ; & x^{(k)} ∈ P . \end{matrix}

Denote the local discrepancy of S′ by R′. It is clear, that for γ < (1 − δ)1

|R′(0, γ)| ≥ ∑_{x^{(k)}∈P} ρ_{k} − |R(0, γ)| ≥
≥ |P | − |R((1 − δ)1, 1)| − |R(0, γ)| ≥ δ^{s} − 2D̃(S) ,

and so for sufficiently large N

D_{2}^{2}(S′) ≥ (1 − δ)^{s}(δ^{s} − 2D̃(S))^{2} ≫ δ^{2s} .  (4)

On the other hand, if α > 0, it is easily seen that

R′(α, α + γ) ≤ \{ \begin{matrix}D̃(S) ; & α_{i}, α_{i} + γ_{i} ∉ [1 − δ; 1] (i = 1, …, s) , \\ 2(D̃(S) + δ^{s}) ; & otherwise . \end{matrix}

It follows that

D̃_{2}^{2}(S′) ≪ D̃^{2}(S) + δ · δ^{2s} ≪ δ^{2s+1}  (5)

and from (4) and (5) we conclude, that for no constant C is D_{2}(S′) ≤ CD̃_{2}(S′) for all the nets S′.

4 D̃_{2} versus D_{2}: Symmetric Nets. Estimate D̃_{2}(S) ≪ D_{2}(S)

Another case of interest is one of symmetric nets. The subject was first investigated by P. Proinov (see [4]), who proved an estimate of the type D_{2}(S) ≪ D̃_{2}(S) for normalized symmetric nets with equal weights. Then in [3] the author obtained an inverse estimate D̃_{2}(S) ≪ D_{2}(S) for all normalized symmetric nets (with not necessarily equal weights), and also generalized Proinov’s proof for such nets. Below we generalize both results for arbitrary (not necessarily normalized) symmetric nets and also make some refinements in formulations and proofs; this section contains a proof of the author’s estimate D̃_{2}(S) ≪ D_{2}(S), and the next one — of the generalized Proinov’s estimate D_{2}(S) ≪ D̃_{2}(S). By means of combining the two estimates with appropriate constants one obtains:

Theorem 2. Let S be a symmetric net having all its points strictly inside the unit cube ℚ^{s}. Then

(4/5)^{s/2}D_{2}(S) ≤ D̃_{2}(S) ≤ 8^{s/2}D_{2}(S) .

Note, that we have to require that S has no points on the border of ℚ^{s}; this requirement is not a casual one, and arises from the fact, that in some sense a net, having a number of its points on a border of ℚ^{s}, is not actually symmetric “relative to D_{2}” (at the same time, it may be symmetric “relative to D̃_{2}”.

We see, therefore, that in the case of symmetric nets the two L^{2}-discrepancies D_{2}(S) and D̃_{2}(S) coincide up to a multiplicative constant.

Let ε ∈ {0, 1}^{s}, and denote by S_{ε} the image of the net S under the symmetry σ_{ε} relative to all the hyperplanes x_{j} = 1/2 for which the index j satisfies condition ε_{j} = 0:

σ_{ε} : x ↦ x′ , x′_{j} = \{ \begin{matrix}\{1 − x_{j}\} ; & ε_{j} = 0 , \\ x_{j} ; & ε_{j} = 1 . \end{matrix}  (6)

Note, that from Corollary 2 of Theorem 1 it follows that

D̃_{2}(S_{ε}) = D̃_{2}(S) .

The main result of this section (which easily implies the discussed estimate of the type D̃_{2}(S) ≪ D_{2}(S)) is

Theorem 3. Let S be a net, having all its points strictly inside ℚ^{s} . Then

D̃_{2}^{2}(S) ≤ 6^{s} ∑_{ε∈{0,1}^{s}} 3^{−ν(ε)}D_{2}^{2}(S_{ε})

(here S_{ε} varies over all nets, obtained by symmetric transformations of S).

Proof. Our idea is to divide the parallelepiped Π(α, α + γ) into “elementary parallelepipeds”, each of which entirely lies in a shift of ℚ^{s} on some vector ε ∈ {0, 1}^{s}; then the local discrepancy of S in such elementary parallelepiped will be replaced by the local discrepancy of S_{ε} in some parallelepiped with “minimal” vertex in the point 0.

Now perform the reasoning in detail.

Let \overline{Π}(u, v) = Π(u, v)∩ℚ^{s}, and ε vary over all vectors from \{0, 1\}^{s}. Denote the local discrepancies of the net S_{ε} in Π(u, v) and \overline{Π}(u, v) by R_{ε}(u, v) and \overline{R}_{ε}(u, v), respectively. It is clear that

Π(α, α + γ) = ∪_{ε}(Π(α, α + γ) ∩ (ℚ^{s} + ε)) =
= ∪_{ε}(ε + \overline{Π}(α − ε, α + γ − ε)) .

Since ε is an integer and the parallelepipeds ε+\overline{Π}(α−ε, α+γ −ε) are pairwise disjoint, we have:

R(α, α + γ) = ∑_{ε∈\{0,1\}^{s}} \overline{R}(α − ε, α + γ − ε) .

For δ ∈ {0, 1}^{s} let Ω(δ) ⊂ ℚ^{s} × ℚ^{s} be the set of all pairs (α, γ) with the given integral part [α + γ] = δ, that is

α_{j} + γ_{j} \{ \begin{matrix}< 1 ; & δ_{j} = 0 , \\ ≥ 1 ; & δ_{j} = 1 . \end{matrix}

Obviously, if (α, γ) ∈ Ω(δ) but ε ≤ δ does not hold, then \overline{Π}(α − ε, α + γ − ε) is empty; hence

D̃_{2}^{2}(S) = ∫_{α,γ∈ℚ^{s}} ( ∑_{ε∈\{0,1\}^{s}} \overline{R}(α − ε, α + γ − ε))^{2} dαdγ =

= ∑_{δ∈\{0,1\}^{s}} ∫_{Ω(δ)} (∑_{ε≤δ} \overline{R}(α − ε, α + γ − ε))^{2} dαdγ ≤  (7)
≤ ∑_{δ∈{0,1}^{s}} 2^{ν(δ)} ∑_{ε≤δ} I(δ, ε) ,

where

I(δ, ε) = ∫_{Ω(δ)} \overline{R}^{2}(α − ε, α + γ − ε) dαdγ .

But one can easily see that the symmetry (6), transferring S to S_{ε}, also transfers parallelepiped \overline{Π}(α − ε, α + γ − ε) into another parallelepiped Π(u, v) (possibly, up to inclusion of some points of the border of Π(u, v) and some part of the border of ℚ^{s}), such that for (α, γ) ∈ Ω(δ) , δ ≥ ε we have:

u_{j} = \{ \begin{matrix}1 − α_{j} − γ_{j} ; & δ_{j} = 0 , \\ 0 ; & δ_{j} = 1 , \end{matrix}

(8)

v_{j} = \{ \begin{matrix}1 − α_{j} ; & ε_{j} = 0 , \\ α_{j} + γ_{j} − 1 ; & ε_{j} = 1 . \end{matrix}

So for all α and γ such that the border of Π(u, v) does not contain points of S_{ε} (that is, for all α and γ, except possibly a set of zero measure), we obtain:

\overline{R}(α − ε, α + γ − ε) = R_{ε}(u, v) ,

and

I(δ, ε) = ∫_{Ω(δ)} R_{ε}^{2}(u, v)dαdγ ,  (9)

where u, v depend on α, γ as shown in (8). Now set

z_{j} = \{ \begin{matrix}1 − α_{j} − γ_{j} ; & δ_{j} = 0 , \\ 1 − γ_{j} ; & δ_{j} = 1 , \end{matrix}  (10)

and change in (9) the integration variables α, γ to the new variables z, v. The region of change of these new variables is contained (as follows from (8) and (10)) in closed unit cube \overline{ℚ}^{s}, and the old variables α, γ may be expressed in terms of the new ones by the formulae

α_{j} = \{ \begin{matrix}1 − v_{j} ; & ε_{j} = 0 , \\ v_{j} + z_{j} ; & ε_{j} = 1 , \end{matrix}
γ_{j} = \{ \begin{matrix}v_{j} − z_{j} ; & δ_{j} = 0 , \\ 1 − z_{j} ; & δ_{j} = 1 . \end{matrix}

The Jacobian of our change of variables is

\frac{D(α, γ)}{D(z, v)} = | \begin{matrix}\frac{Dα}{Dz} & \frac{Dα}{Dv} \\ \frac{Dγ}{Dz} & \frac{Dγ}{Dv} \end{matrix} | = −\frac{Dα}{Dv} · \frac{Dγ}{Dz} = ±1

(since from the two determinants \frac{Dα}{Dz} and \frac{Dγ}{Dv} at least one is always equal to 0, while the absolute values of the determinants \frac{Dα}{Dv} and \frac{Dγ}{Dz} are always equal to 1). Therefore

I(δ, ε) ≤ ∫_{z,v∈ℚ^{s}} R_{ε}^{2}(u, v)dzdv ,

where

u_{j} = \{ \begin{matrix}z_{j} ; & δ_{j} = 0 , \\ 0 ; & δ_{j} = 1 . \end{matrix}

The function R_{ε}^{2}(u, v) under the sign of the last integral does not depend on the variables z_{j} with indexes j under δ_{j} = 1; thus after integrating over these variables we obtain:

I(δ, ε) ≤ ∫ R_{ε}^{2}(u, v) dudv ,

where we set

du = ∏_{δ_{j}=0} du_{j} ,

and the region of integration is defined by u ∈ ℚ^{s−ν(δ)}, v ∈ ℚ^{s} (while coordinates u_{j} for indexes j under δ_{j} = 1 are constant and equal to 0).

For μ ∈ {0, 1}^{s} , μ ≥ δ let’s set

t_{j} = \{ \begin{matrix}u_{j} ; & μ_{j} = 0 \\ v_{j} ; & μ_{j} = 1 \end{matrix} (j = 1, …, s) .

Then it is easily seen that

R_{ε}(u, v) = ∑_{μ≥δ}(−1)^{s−ν(μ)}R_{ε}(0, t) ,

(one can consider the equality as a variant of the inclusion-exclusion formula), and so

I(δ, ε) ≤ 2^{s−ν(δ)} ∑_{μ≥δ} ∫_{ℚ^{s−ν(δ)}×ℚ^{s}} R_{ε}^{2}(0, t)dudv .

Now performing integration by variables u_{j} for indexes j under μ_{j} = 1, δ_{j} = 0, and for variables v_{j} for indexes j under μ_{j} = 0, we obtain:

I(δ, ε) ≤ 2^{s−ν(δ)} ∑_{μ≥δ} ∫_{ℚ^{s}} R_{ε}^{2}(0, t)dt = 2^{2(s−ν(δ))}D_{2}^{2}(S_{ε}) ,

so that from (7)

D̃_{2}^{2}(S) ≤ ∑_{δ∈{0,1}^{s}} 2^{ν(δ)} ∑_{ε≤δ} 2^{2(s−ν(δ))}D_{2}^{2}(S_{ε}) =
= ∑_{ε∈{0,1}^{s}} D_{2}^{2}(S_{ε}) ∑_{δ≥ε} 2^{2s}2^{−ν(δ)} =

= 4^{s} ∑_{ε∈{0,1}^{s}}(3/2)^{s−ν(ε)}(1/2)^{ν(ε)}D_{2}^{2}(S_{ε}) =
= 6^{s} ∑_{ε∈{0,1}^{s}} 3^{−ν(ε)}D_{2}^{2}(S_{ε}) ,

which was to be proved.

As a direct corollary of the theorem we obtain the required estimate of the type D̃_{2}(S) ≪ D_{2}(S): Corollary. Let S be a symmetric net having all its points strictly inside ℚ^{s}. Then

D̃_{2}(S) ≤ 8^{s/2}D_{2}(S) .

Proof. For a net S of the considered type all the discrepancies D_{2}(S_{ε}) pairwise coincide and are equal to D_{2}(S); therefore, in view of the theorem,

D̃_{2}^{2}(S) ≤ 6^{s}D_{2}^{2}(S) ∑_{ε∈{0,1}^{s}} 3^{−ν(ε)} =
= 6^{s}(4/3)^{s}D_{2}^{2}(S) = 8^{s}D_{2}^{2}(S) .

Note. A refinement of the proof allows us to write the inequality of the theorem in the form:

D̃_{s}^{2}(S) ≤ 3^{s} ∑_{ε∈{0,1}^{s}} D_{2}^{2}(S_{ε}) ;

in turn, this makes it possible to improve the constant of the corollary up to 6^{s/2}.

5 D̃_{2} versus D_{2}: Symmetric Nets. Estimate D_{2}(S) ≪ D̃_{2}(S)

To complete our comparison of L^{2}-discrepancies of symmetric nets, we are going to obtain now an inverse estimate of the type D_{2}(S) ≪ D̃_{2}(S). The “historical” aspect of the estimate was described in the previous section.

We start from the following lemma. Lemma 2. The following identity holds:

D_{2}^{2}(S) = 4^{−s} ∑_{m∈ℤ^{s}} \frac{π^{−2ν(m)}}{\overline{m}^{2}} | ∑_{k=1}^{N} ρ_{k} ∏_{j=1}^{s} c_{m_{j}}(x_{j}^{(k)}) − 1|^{2} ,

where

c_{m_{j}}(x_{j}^{(k)}) = \{ \begin{matrix}2(1 − x_{j}^{(k)}) ; & m_{j} = 0 , \\ 1 − e^{−2πim_{j}x_{j}^{(k)}} ; & m_{j} ≠ 0 . \end{matrix}

Proof. Confirmation of the lemma is obtained by applying Parseval’s equality to the function R(0, γ): if we set

b_{m_{j}} = \{ \begin{matrix}−i/π ; & m_{j} < 0 , \\ 1 ; & m_{j} = 0 , \\ i/π ; & m_{j} > 0 , \end{matrix}

then the Fourier coefficients of the function are

R̂(m) = ∫_{ℚ^{s}} R(0, γ)e^{−2πi<m·γ>}dγ =
= ∑_{k=1}^{N} ρ_{k} ∫_{γ>x^{(k)}} e^{−2πi<m·γ>}dγ − ∫_{ℚ^{s}} γ_{1} ⋯ γ_{s}e^{−2πi<m·γ>}dγ =

= ∑_{k=1}^{N} ρ_{k} ∏_{j=1}^{s} ∫_{x_{j}^{(k)}}^{1} e^{−2πim_{j}γ_{j}}dγ_{j} − ∏_{j=1}^{s} ∫_{0}^{1} γ_{j}e^{−2πim_{j}γ_{j}}dγ_{j} =

= ∑_{k=1}^{N} ρ_{k} ∏_{j=1}^{s} \frac{1}{2\overline{m}_{j}} c_{m_{j}}(x_{j}^{(k)})b_{m_{j}} − ∏_{j=1}^{s} \frac{1}{2\overline{m}_{j}} b_{m_{j}} =

= \frac{1}{2^{s}\overline{m}} (∑_{k=1}^{N} ρ_{k} ∏_{j=1}^{s} c_{m_{j}}(x_{j}^{(k)}) − 1) · ∏_{j=1}^{s} b_{m_{j}} ,

and the rest is obvious.

Theorem 4. Let S be a symmetric net having all its points strictly inside ℚ^{s}. Then

D_{2}(S) ≤ (5/4)^{s/2}D̃_{2}(S) .

Proof. We use the notions of Lemma 2, and also set |m| = (|m_{1}|, …, |m_{s}|), so that, for instance, the symbol ∑_{ε≤|m|} will denote the sum over all vectors ε ∈ {0, 1}^{s} with ε_{j} = 0 for all j under m_{j} = 0. In view of the symmetry of S we have:

∑_{k=1}^{N} ρ_{k} ∏_{j=1}^{s} c_{m_{j}}(x_{j}^{(k)}) =

= ∑_{k=1}^{N} ρ_{k} ∏_{m_{j}≠0} c_{m_{j}}(x_{j}^{(k)}) ∏_{m_{j}=0} \frac{1}{2} (c_{m_{j}}(x_{j}^{(k)}) + c_{m_{j}}(1 − x_{j}^{(k)})) =

= ∑_{k=1}^{N} ρ_{k} ∏_{m_{j}≠0} c_{m_{j}}(x_{j}^{(k)}) ,

and from Lemma 2,

D_{2}^{2}(S) = 4^{−s} ∑_{m} \frac{π^{−2ν(m)}}{\overline{m}^{2}} | ∑_{k=1}^{N} ρ_{k} ∏_{m_{j}≠0} c_{m_{j}}(x_{j}^{(k)}) − 1|^{2} =

= 4^{−s} ∑_{m} \frac{π^{−2ν(m)}}{\overline{m}^{2}} | ∑_{k=1}^{N} ρ_{k} ·
· ∑_{ε≤|m|}(−1)^{ν(ε)}e^{−2πi(m_{1}ε_{1}x_{1}^{(k)}+···+m_{s}ε_{s}x_{s}^{(k)})} − 1|^{2} =

= 4^{−s} ∑_{m} \frac{π^{−2ν(m)}}{\overline{m}^{2}} | \begin{matrix}∑ & ′ \\ ε≤|m| \end{matrix} (−1)^{ν(ε)}T ((m_{1}ε_{1}, …, m_{s}ε_{s})) +
+ (T (0) − 1)|^{2} ≤
≤ 4^{−s} ∑_{m} \frac{π^{−2ν(m)}}{\overline{m}^{2}} 2^{ν(m)}( \begin{matrix}∑ & ′ \\ ε≤|m| \end{matrix} |T ((m_{1}ε_{1}, …, m_{s}ε_{s}))|^{2} +
+ |T (0) − 1|^{2}) =
= 4^{−s} \begin{matrix}∑ & ′ \\ ε∈\{0,1\}^{s} \end{matrix} ∑_{|m|≥ε}(2/π^{2})^{ν(m)}|T ((m_{1}ε_{1}, …, m_{s}ε_{s}))|^{2} /\overline{m}^{2} +
+ 4^{−s}|T (0) − 1|^{2} ∑_{m} \frac{1}{\overline{m}^{2}} (2/π^{2})^{ν(m)} .

The second summand in the right-hand side may be calculated directly, while in the inner sum of the first summand one can execute direct summing over the variables m_{j} for indexes j under ε_{j} = 0; we obtain:

D_{2}^{2}(S) ≤ 4^{−s} \begin{matrix}∑ & ′ \\ ε \end{matrix} ∏_{ε_{j}=0} (1 + 2\frac{2}{π^{2}} \frac{π^{2}}{6} ) ·

· ∑_{m}^{∗}(2/π^{2})^{ν(m)}|T ((m_{1}ε_{1}, …, m_{s}ε_{s}))|^{2}/\overline{m}^{2} +
+ (5/12)^{s}|T (0) − 1|^{2} =  (11)
= 4^{−s}∑_{ε}′(5/3)^{s−ν(ε)} \begin{matrix}∑ & ∗ \\ m \end{matrix} (2/π^{2})^{ν(m)} \frac{|T (m)|^{2}}{\overline{m}^{2}} +
+ (5/12)^{s}|T (0) − 1|^{2} ,

where the symbol ∑_{m}^{∗} means summing over all vectors m, for which m_{j} accepts the single integer value 0, if ε_{j} = 0, and m_{j} accepts all non-zero integer values otherwise.

Furthermore, in (11) each summand of the form |T (m)|^{2}/\overline{m}^{2} with m ≠ 0 is encountered for exactly one value of ε, and for this value ν(m) = ν(ε); hence

D_{2}^{2}(S) ≤ 4^{−s}(5/3)^{s} \begin{matrix}∑ & ′ \\ m \end{matrix} \frac{|T (m)|^{2}}{\overline{m}^{2}} · (5/3)^{−ν(m)}(2/π^{2})^{ν(m)} +
+ (5/12)^{s}|T (0) − 1|^{2} ≤
≤ 3^{−s}(5/4)^{s} \begin{matrix}∑ & ′ \\ m \end{matrix} \frac{|T (m)|^{2}}{\overline{m}^{2}} · (6/5π^{2})^{ν(m)} +
+ 3^{−s}(5/4)^{s}|T (0) − 1|^{2} ≤
≤ 3^{−s}(5/4)^{s}( \begin{matrix}∑ & ′ \\ m \end{matrix} \frac{|T (m)|^{2}}{\overline{m}^{2}} · (3/2π^{2})^{ν(m)}(4/5)^{ν(m)} +
+ |T (0) − 1|^{2}) ,

and we have only to apply Theorem 1.

It is seen from our proof that for normalized net S the constant of Theorem 4 may be slightly improved: namely, if S is a normalized symmetric net, having all its points strictly inside ℚ^{s}, then D_{2}(S) ≤ (5/4)^{(s−1)/2}D̃_{2}(S).

6 Nets with D_{2}(S) = o(D̃_{2}(S))

We have seen so far that both one-dimensional and symmetric nets satisfy D̃_{2}(S) ≪ D_{2}(S). The same clearly applies to nets S, having L^{2}-discrepancies D_{2}(S + α) of the same order of value for all α ∈ ℚ^{s} (see note at the end of section 1). We now add one more example to this collection of nets with D̃_{2}(S) ≪ D_{2}(S).

As in section 4, denote by S_{ε} the net, obtained from S by means of the symmetry σ_{ε} relative to all the hyperplanes x_{j} = 1/2 with indexes j under condition ε_{j} = 0, and also denote by S′_{ε} the ν(ε)-dimensional net^{2} obtained from S by means of the projection π_{ε}, defined by

π_{ε} : x ↦ x′ , x′_{j} = \{ \begin{matrix}x_{j} ; & ε_{j} = 1 , \\ 0 ; & ε_{j} = 0 . \end{matrix}

Lemma 3. Let S be a net having all its points strictly inside ℚ^{s}. Then Weyl L^{2}- discrepancy D̃_{2}(S) may be estimated by “usual” L^{2}-discrepancies D_{2}(S′_{ε}) of projections of S as follows:

D̃_{2}^{2}(S) ≤ 12^{s} ∑_{ε∈{0,1}^{s}}(7/6)^{ν(ε)}D_{2}^{2}(S′_{ε}) .

Proof. Our lemma will follow immediately from Theorem 3 and the inequality

D_{2}^{2}(S_{ε}) ≤ 2^{s−ν(ε)} ∑_{δ∈{0,1}^{s}, δ≥ε} D_{2}^{2}(S′_{δ}) ,  (12)

since, assuming the inequality to be true, we obtain:

D̃_{2}^{2}(S) ≤ 6^{s} ∑_{ε∈{0,1}^{s}} 3^{−ν(ε)} · 2^{s−ν(ε)} ∑_{δ≥ε} D_{2}^{2}(S′_{δ}) ≤
≤ 12^{s} ∑_{δ∈{0,1}^{s}} D_{2}^{2}(S′_{δ}) ∑_{ε≤δ} 6^{−ν(ε)} =
= 12^{s} ∑_{δ∈{0,1}^{s}}(7/6)^{ν(δ)}D_{2}^{2}(S′_{δ}) .

Therefore, we need only to prove (12).

To this end, denote by R_{ε} and R′_{ε}, respectively, the local discrepancies of S_{ε} and S′_{ε}, and for ε, δ ∈ {0, 1}^{s} set also

u_{j} = \{ \begin{matrix}1 − γ_{j}; & ε_{j} = 0 \\ 0; & ε_{j} = 1 \end{matrix} , v_{j} = \{ \begin{matrix}1; & ε_{j} = 0 \\ γ_{j}; & ε_{j} = 1 \end{matrix} ,

z_{j} = \{ \begin{matrix}1; & ε_{j} = 0, δ_{j} = 0 \\ 1 − γ_{j}; & ε_{j} = 0, δ_{j} = 1 \\ γ_{j}; & ε_{j} = 1, δ_{j} = 1 \end{matrix} .

2strictly speaking, we have no definition of a “0-dimensional” net. To avoid problem arising for ε = 0, we put directly D_{2}^{2}(S′_{0}) = (ρ_{0} − 1)^{2} in the formulae below.

Combinatorial considerations show, that for almost all γ holds:

R_{ε}(0, γ) = R(u, v) = ∑_{δ≥ε}(−1)^{ν(δ)−ν(ε)}R(0, z) ,

and to complete the proof, it is sufficient to observe, that

∫_{ℚ^{s}} R^{2}(0, z)dγ = D_{2}^{2}(S′_{δ}).

Corollary. Let S be a net with all the points strictly inside ℚ^{s}, and satisfying for some constant C

D_{2}(S′_{ε}) ≤ CD_{2}(S) for all ε ∈ {0, 1}^{s}

(that is, the L^{2}-discrepancies of S projections are at most of the same order of value as the L^{2}-discrepancy of S itself). Then

D̃_{2}(S) ≤ 26^{s/2}CD_{2}(S) .

As one can see, we have now a large number of nets with D̃_{2}(S) ≪ D_{2}(S) (onedimensional ones and nets with “good” shifts, symmetries or projections). Does the estimate hold for all nets? Here is a counter-example. Example 2. Let s ≥ 2, and S = (X, ρ) vary over a sequence of s-dimensional nets with the number of nodes increasing to infinity and the Weyl supreme discrepancy decreasing to zero: N → ∞, D̃(S) → 0. Set

δ = (D̃(S))^{1/2s} → 0 ,
P = {x ∈ ℚ^{s} | x ≥ (1 − δ)1} ,

(so that δ and P depend on S) and consider new net S′ = (Y, ρ) with the same weights as S and the system of points Y, defined by

y^{(k)} = \{ \begin{matrix}x^{(k)} ; & x^{(k)} ∉ P , \\ (1 − δ)1 ; & x^{(k)} ∈ P , \end{matrix}

(compare with Example 1). Denote the local discrepancy of S′ by R′. It is easily seen, that

|R′(0, γ)| ≤ \{ \begin{matrix}D̃(S) ; & γ ∉ P , \\ 2(D̃(S) + δ^{s}) ; & γ ∈ P \end{matrix}

and therefore

D_{2}^{2}(S′) ≤ ∫_{γ∉P} D̃^{2}(S)dγ + 8 ∫_{γ∈P} (D̃^{2}(S) + δ^{2s})dγ ≤
≤ 8(D̃^{2}(S) + δ^{3s}) ≪ δ^{3s} .  (13)

On the other hand, if, for instance,

1 − δ < α_{1} < 1 − δ/2 ,

(14)

1/2 < α_{2}, …, α_{s} < 1 − δ, γ_{1}, …, γ_{s} > 1/2 ,

then Π(α, α + γ) does not contain the point (1 − δ)1, but contains the parallelepiped

Π((1 − δ/2, 1 − δ, …, 1 − δ), 1) ,

of the value 0.5δ^{s}, free of points of S′. Then local discrepancy of S′ in Π(α, α + γ) is at least 0.5δ^{s} − 2D(S) ≫ δ^{s}, and the value of the region (14) ≫ δ; therefore,

D̃_{2}^{2}(S′) ≫ δ · δ^{2s} = δ^{2s+1} .  (15)

From (13) and (15) we conclude, that for no constant C is D̃_{2}(S′) ≤ CD_{2}(S′) for all the nets S′.

7 Behavior of D_{2}(S) under Shifts, Projections and Symmetries of S

We’d like to finish our paper by considering once again Statements 1–3 from section 2 and Corollary 2 of Theorem 1, — this time from the following point of view: are the analogous properties satisfied for the “usual” L^{2}-discrepancy D_{2}(S) instead of the Weyl L^{2}-discrepancy D̃_{2}(S) and the diaphony F_{2}(S)? In other words, is the “usual” L^{2}-discrepancy D_{2}(S) invariant relative to shifts and symmetries and non-increasing under projections of a net, — at least, by order of value?

Statement 1′. For any constant C there exists an s-dimensional net S and a vector α ∈ ℚ^{s}, that satisfy:

D_{2}(S + α) > C · D_{2}(S) .

Proof. Suppose, on the contrary, D_{2} (S + α) ≤ CD_{2}(S) for all S, α. Then also D_{2}(S) ≤ CD_{2}(S + α), so

D_{2}(S) ≤ C (∫_{ℚ^{s}} D_{2}^{2}(S + α) dα)^{1/2} = CD̃_{2}(S) ,

in contradiction to Example 1.

Statement 2′.For any constant C and s ≥ 2 there exist a s-dimensional net S and some projection π such, that S′ = π(S) satisfies

D_{2}(S′) > C · D_{2}(S) .

Proof. Suppose, on the contrary, D_{2}(S′) ≤ CD_{2}(S) for all S′ = π(S). Then, in view of the corollary to Lemma 3, the following inequality is satisfied:

D̃_{2}(S) ≤ 26^{s/2}CD_{2}(S) ,

in contradiction to Example 2.

Statement 3′. For any constant C there exist a s-dimensional net S and some symmetry σ such that S′ = σ(S) satisfies

D_{2}(S′) > C · D_{2}(S) .

Proof. Suppose, on the contrary, D_{2}(S′) ≤ CD_{2}(S) for all S′ = σ(S). Then, if S has no points on the border of ℚ^{s}, in view of Theorem 3

D̃_{2}^{2} ≤ 6^{s} · C^{2}D_{2}^{2}(S) ∑_{ε∈{0,1}^{s}} 3^{−ν(ε)} ≤ C^{2}8^{s}D_{2}^{2}(S) ,

in contradiction to Example 2.

References

[1] Bykovsky V.A., Correct order of error of optimal cubature formulas in spaces with dominant derivation and L^{2}-discrepancy of nets. Preprint, Dalne-Vost. Nauch. Tsentr Acad. Nauk SSSR, Vladivostok, 1985.

[2] Kuipers L. and Niederreiter H., Uniform Distribution of Sequences. N.Y., 1974.

[3] Lev V.F., Diaphony and L^{2}-discrepancies of multidimensional nets. Math. Notes, 47(6)(1990), 45–54 [Russian].

[4] Proinov P.D., On the extreme and and L^{2}-discrepancies of symmetric finite sequences. Serdica Bulg. Math. Publ., 10(4)(1984), 376–383.

[5] Zinterhof P., Uber einige Abschatzungen bei der Approximation von Funktionen mit Gleichverteilungsmethoden. Sitzungsberg. Osterr. Akad. Wiss. Math.- naturwiss. Kl. II, 185(1976), 121–132.