Translations of Nets and Relationship between Supreme and L^{κ}-discrepancies

Vsevolod F. Lev ^{∗}

Abstract As it is shown in [1], in case of κ = 2 the L^{κ}-discrepancy of a net may substantially (by the order of value) vary under translations of the net modulo the unit cube ℚ^{s}. Here for every κ ≥ 1 we prove that the supremum of L^{κ}-discrepancies of all such translated nets coincides (up to a multiplicative constant) with the supreme discrepancy:

sup_{α∈ℚ^{s}} D_{κ}(S + α) ≍ D_{∞}(S) .

1 Notation

We use the notation of [1].

Vectors in ℝ^{s} are denoted by small Latin or Greek letters, as x^{(k)}, α, and so on. Lower indexes are reserved for vectors coordinates, as x_{1}^{(k)}, α_{s}. The two following vectors are written in bold to distinguish from scalars: 0 = (0, …, 0) and 1 = (1, …, 1). The number of non-zero coordinates of x is denoted by ν(x): for instance, ν(0) = 0, ν(1) = s.

The s-dimensional unit cube ℚ^{s} is the set

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

or, equally,

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

By a net S = (X, ρ) we shall mean a finite weighted set of points in ℚ^{s}, that is, a system of points

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

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

and system of real weights, corresponding to these points:

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

The pair (x^{(k)}, ρ_{k}) is said to be the k-th node of the net S. By ρ_{0} we will denote the sum of the net’s weights: ρ_{0} = ρ_{1} + ⋯ + ρ_{N}. A net having the sum of its weights equal to 1 (that is, a net with ρ_{0} = 1) we shall refer to as a normed one.

By S + α we denote the translation of the net S by the vector α modulo ℚ^{s}, that is the new net (X + α, ρ) with the nodes

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

(the inner figure parentheses stand here for vector’s fractional part, that is, the vector of fractional parts of coordinates). Obviously, S+α_{1} = S+α_{2} for α_{1} ≡ α_{2} (mod ℚ^{s}).

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

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

(this cell is non-empty only if u < v). Let us denote its volume by |Π(u, v)| and introduce the local discrepancy of the 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, lying in Π(u, v) “modulo the unit cube”, that is, over those points x^{(k)}, some integer translation of which lies in Π(u, v)). Clearly, local discrepancy R(u, v) is invariant with respect to translations of Π(u, v) by any integer vector. Also, local discrepancy has the property of finite additivity: if Π(u, v) = ∪Π(u_{i}, v_{i}) is a finite union of pairwise disjoint cells, then R(u, v) = ∑ R(u_{i}, v_{i}).

For κ ∈ [1; ∞] we define L^{κ}-discrepancy of net S by

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

that is

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

1it should be pointed out, that our main result (see next section) includes, as a particular case, nets with “traditional” weights: ρ_{1} = … = ρ_{N} = 1/N.

if κ < ∞, and

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

The value defined by (4) is called supreme discrepancy, and traditionally denoted simply by D(S).

We put also

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

(the Weyl supreme discrepancy).

As a direct corollary from the definitions, we have:

D̃(S) = sup_{α∈ℚ^{s}} D(S + α) .  (6)

Indeed, if R_{α} denotes the local discrepancy of S − α, then, as follows from (1),

R_{α}(0, γ) = R(α, α + γ) ,

so

sup_{α∈ℚ^{s}} D(S − α) = D̃(S) ,

and observing that S − α = S + {−α}, we obtain (6).

2 The Main Theorem

For a fixed κ and given normalized net S we are going to investigate the behavior of discrepancies D_{κ}(S + α), when α varies over ℚ^{s}. The aim of this paper is to prove the following result. Theorem 1. Let constants A_{s} be defined by

A_{0} = 1, A_{s} = ∑_{i=0}^{s−1} ( \begin{matrix}s \\ i \end{matrix} ) A_{i} (s = 1, 2, …) ,

and let S be s-dimensional normalized net. Then

\frac{1}{2^{s}A_{s}} D̃(S) ≤ sup_{α∈ℚ^{s}} D_{κ}(S + α) ≤ D̃(S) .  (7)

The right-hand side estimate is, of course, the trivial part of the theorem (since, in view of (2) and (6),

sup_{α∈ℚ^{s}} D_{κ}(S + α) ≤ sup_{α∈ℚ^{s}} D_{∞}(S + α) = D̃(S) ).

So is the left-hand side estimate in case of κ = ∞, and we suppose below κ < ∞.

The next statement shows, that D̃(S) in (7) may be easily replaced by more usual D(S).

Statement 1. The following estimates hold:

D(S) ≤ D̃(S) ≤ 3^{s}D(S) .

Proof. The estimate from below is trivial in view of (6). To obtain the estimate from above, we fix α, γ ∈ ℚ^{s} and prove, that |R(α, α+γ)| ≤ 3^{s}D(S) — then our result will follow from (5). Since R(α, α + γ) is semi-continues function of α, we may suppose α > 0.

Let ε run over all the 2^{s} integer vectors with coordinates 0 and 1: ε ∈ {0, 1}^{s}. Then obviously Π(α, α + γ) is the pairwise disjoint union

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

For given α, γ, ε define u, v ∈ ℚ^{s} by

u_{i} = max{α_{i} − ε_{i}, 0},
v_{i} = min{α_{i} + γ_{i} − ε_{i}, 1},

so the intersections in the right-hand side of (8) are Π(u, v) and we obtain:

R(α, α + γ) = ∑_{ε=0}^{1} R(u, v) .  (9)

Observe now, that u_{i} = 0 if and only if ε_{i} = 1, and let μ_{i} accept the only value μ_{i} = 0 in this case, and μ_{i} run over the two values 0, 1 otherwise: μ ∈ {0, 1}^{s}, 0 ≤ μ ≤ 1−ε. Then combinatorial considerations show that

R(u, v) = ∑_{μ=0}^{1−ε}(−1)^{ν(μ)}R(0, w) ,  (10)

where

w_{i} = \{ \begin{matrix}v_{i} ; & μ_{i} = 0 , \\ u_{i} ; & μ_{i} = 1 . \end{matrix}

¿From (9), (10) and (4) we obtain now:

|R(α, α + γ)| ≤ ∑_{ε=0}^{1} ∑_{μ=0}^{1−ε} D(S) = D(S) · ∏_{i=1}^{s} ∑_{ε_{i}=0}^{1} ∑_{μ_{i}=0}^{1−ε_{i}} 1 = 3^{s}D(S) ,

and the result follows.

The above statement shows, that the extreme discrepancy may not substantially (by the order of value) vary under translations of net:

Corollary. Let α ∈ ℚ^{s}; then

D(S + α) ≤ 3^{s}D(S), D(S) ≤ 3^{s}D(S + α) .

Note also, that Statement 1 may be combined with Theorem 1 as follows:

Theorem 1′. The relation holds:

sup_{α∈ℚ^{s}} D_{κ}(S + a) ≍ D(S) ,

where the constants in the sign ≍ depend only on the dimension s.

The rest of the paper is devoted to the proof of Theorem 1.

3 Reduction to κ-independent Function

Our proof is based on consideration of the function f(S) of a given net S, constructed as follows:

f(S) = 2^{s} ∑_{k=1}^{N} ρ_{k}(1 − x_{1}^{(k)}) … (1 − x_{s}^{(k)}) − 1 .

Lemma 1. The estimate holds:

D_{κ}(S) ≥ 2^{−s}|f(S)| .

Proof. In view of (3) we have:

D_{κ}(S) ≥ D_{1}(S) ≥
≥ |∫_{ℚ^{s}} R(0, γ) dγ| = |∑_{k=1}^{N} ρ_{k} ∫_{x^{(k)}}^{1} dγ − ∫_{ℚ^{s}} γ_{1} … γ_{s} dγ| =
= |2^{−s}f(S)| .

The estimate of Lemma 1 may seem to be too rough; nevertheless, it is sufficient for our purposes. Moreover, from now on we forget about D_{κ}(S) and work with f(S) only.

We start from the one-dimensional case.

4 The One-Dimensional Case

During this section, we consider only 1-dimensional vectors. For shortness, in this case we write directly x^{(k)}, α, … instead of x_{1}^{(k)}, α_{1}, ….

We have also to introduce a few new notations. For α, γ, c ∈ ℚ^{1}, x ∈ ℝ^{1} and given net S = (X, ρ) put

δ_{α,γ}(x) = \{ \begin{matrix}1 & ; x ∈ [α, α + γ[ (mod 1) , \\ 0 & ; x ∉ [α, α + γ[ (mod 1) , \end{matrix}
r(α, γ) = ∑_{k=1}^{N} ρ_{k}(δ_{α,γ}(x^{(k)}) − γ) =
= ∑_{α≤x^{(k)}<α+γ (mod 1)} ρ_{k} − ρ_{0}γ ,
d̃(S) = sup_{α,γ} |r(α, γ)| ,
g_{c}(S) = ∑_{k=1}^{N} ρ_{k}(x^{(k)} − \frac{1}{2}) + c .

Clearly, f(S) = −2g_{c}(S) for some c, and in normalized case r(α, γ) = R(α, γ), d̃(S) = D̃(S).

Lemma 2. The equality holds:

r(α, γ) = ∑_{k=1}^{N} ρ_{k}({x^{(k)} − α − γ} − {x^{(k)} − α}) .

Proof. For any x ∈ ℝ we have:

\{x − γ\} − x + γ = \{ \begin{matrix}1 & ; 0 ≤ x < γ , \\ 0 & ; γ ≤ x < 1 , \end{matrix}
\{x − γ\} − \{x\} + γ = \{ \begin{matrix}1 & ; 0 ≤ x < γ (mod 1) , \\ 0 & ; γ ≤ x < 1 (mod 1) , \end{matrix}
\{x − α − γ\} − \{x − α\} + γ = \{ \begin{matrix}1 & ; x ∈ [α; α + γ[ (mod 1) , \\ 0 & ; x ∉ [α; α + γ[ (mod 1) , \end{matrix}
{x − α − γ} − {x − α} = δ_{α,γ}(x) − γ,

and the proof completes by summing the last equality over the net S. Lemma 3. The double inequality holds:

max(|c|, \frac{1}{2}d̃(S)) ≤ sup_{α∈ℚ^{s}} |g_{c}(S + α)| ≤ |c| + d̃(S) .

Proof. We have:

∫_{0}^{1} g_{0}(S + α) dα = ∑_{k=1}^{N} ρ_{k} ∫_{0}^{1} (\{x^{(k)} + α\} − \frac{1}{2}) dα = 0 ;

hence g_{0}(S + α) accepts both non-negative and non-positive values, and the first of the estimates from below follows from

g_{c}(S + α) = g_{0}(S + α) + c .  (11)

Then, by Lemma 2,

g_{c}(S − α − γ) − g_{c}(S − α) = r(α, γ) ,  (12)

which gives the second of the estimates from below.

In case of c = 0, it also follows from (12) that

|g_{0}(S + α)| ≤ d̃(S)  (13)

(since, as it was mentioned above, g_{0}(S + α) accepts values of both signs). From (11) and (13) we obtain the estimate from above of the lemma.

Note, that Lemma 3 sets the exact order of the supremum of absolute values of g_{c}(S + α):

sup_{α∈ℚ^{s}} |g_{c}(S + α)| ≍ max(|c|, d̃(S)) .

In fact, the estimate from above will never be used in future and was added only for the sake of completeness.

Our proof of Theorem 1 will be an inductive one, and the next corollary of Lemma 3 provides us both with induction base and with means we need to execute the induction step.

Corollary. The following estimates hold:

sup_{α} |2 ∑_{k=1}^{N} ρ_{k}(1 − {x^{(k)} + α}) − 1| ≥ |ρ_{0} − 1| ,  (14)

sup_{α} |2 ∑_{k=1}^{N} ρ_{k}(1 − {x^{(k)} + α}) + c| ≥ sup_{α,γ} |∑_{k=1}^{N} ρ_{k}(δ_{α,γ}(x^{(k)}) − γ)| .  (15)

Proof. It is sufficient to observe, that

2 ∑_{k=1}^{N} ρ_{k}(1 − {x^{(k)} + α}) − 1 = −2g_{c_{1}}(S + α) ,

where c_{1} = (1 − ρ_{0})/2, and

2 ∑_{k=1}^{N} ρ_{k}(1 − {x^{(k)} + α}) + c = −2g_{c_{2}}(S + α)

for some constant c_{2}.

We could, of course, simplify (14) and (15) as follows:

sup_{α} |f(S + α)| ≥ |ρ_{0} − 1| ,  (14′)

sup_{α} |f(S + α) + c| ≥ d̃(S) .  (15′)

However, such a simplification is undesirable in view of the way we are going to utilize this corollary.

Note also, that (15′) evidently proves Theorem 1 in 1-dimensional case: using Lemma 1 and observing, that d̃(S) = D̃(S) for normalized nets, we obtain (for c = 0):

sup_{α} D_{κ}(S + α) ≥ 2^{−1} sup_{α} |f(S + α)| ≥ \frac{1}{2} d̃(S) = \frac{1}{2} D̃(S) .

5 The General s-Dimensional Case

For ε ∈ {0, 1}^{s}, ε ≠ 1 (that is ν(ε) < s) let S_{ε} denote the projection of S onto the face of ℚ^{s}

{x ∈ ℚ^{s} | 0 ≤ x_{j} ≤ 1 − ε_{j} ; j = 1, …, s} ,

so that

D̃(S_{ε}) = sup_{α,γ} |∑_{k=1}^{N} ρ_{k} ∏_{ε_{j}=0} δ_{α_{j},γ_{j}}(x_{j}^{(k)}) − ∏_{ε_{j}=0} γ_{j}|

(here α, γ ∈ ℚ^{s}, and the sign ∏_{ε_{j}=0} means product over all j under condition ε_{j} = 0).

Lemma 4. For ε ≠ 1 we have:

sup_{α} |f(S + α)| ≥ sup_{α} |f(S_{ε} + α)| ,

where left-hand side sup is calculated over all s-dimensional, and right-hand side sup — over all (s − ν(ε))-dimensional vectors α.

Proof. It is sufficient to consider the case of ε = (0, …, 0, 1). Then, in view of (14),

sup_{α∈ℚ^{s}} |f(S + α)| =

= sup_{α_{1},...,α_{s−1}} sup_{α_{s}} |2 ∑_{k=1}^{N} (2^{s−1}ρ_{k} ∏_{j=1}^{s−1}(1 − {x_{j}^{(k)} + α_{j}})) (1 − {x_{s}^{(k)} + α_{s}}) − 1| ≥

≥ sup_{α_{1},...,α_{s−1}} |∑_{k=1}^{N} (2^{s−1}ρ_{k} ∏_{j=1}^{s−1}(1 − {x_{j}^{(k)} + α_{j}}) − 1| = sup_{α∈ℚ^{s−1}} |f(S_{ε} + α)| .

The following lemma with its corollary, based on inequality (15), plays the central role in our proof.

Lemma 5. The estimate holds

sup_{α} |f(S + α)| ≥ sup_{α,γ} |∑_{k=1}^{N} ρ_{k} ∏_{j=1}^{s} (δ_{α_{j},γ_{j}}(x_{j}^{(k)}) − γ_{j})| .  (16)

Proof. Calculating consequently sup by α_{s}, α_{s−1}, …, α_{1} and using inequality (15) (first time with c = 1, then with c = 0) we obtain:

sup_{α} |f(S + α)| =

= sup_{α_{1},...,α_{s−1}} sup_{α_{s}} |2 ∑_{k=1}^{N} (2^{s−1}ρ_{k} ∏_{j=1}^{s−1}(1 − {x_{j}^{(k)} + α_{j}})) · (1 − {x_{s}^{(k)} + α_{s}}) − 1| ≥

≥ sup_{α_{s},γ_{s}} sup_{α_{1},...,α_{s−1}} |∑_{k=1}^{N} 2^{s−1}ρ_{k} ∏_{j=1}^{s−1}(1 − {x_{j}^{(k)} + α_{j}}) · (δ_{α_{s},γ_{s}}(x_{s}^{(k)}) − γ_{s})| ≥ ⋯ ≥

≥ sup_{α_{s},γ_{s}} ⋯ sup_{α_{1},γ_{1}} |∑_{k=1}^{N} 2^{0}ρ_{k}(δ_{α_{1},γ_{1}}(x_{1}^{(k)}) − γ_{1}) · . . . · (δ_{α_{s},γ_{s}}(x_{s}^{(k)}) − γ_{s})| ,

which was to be proved.

Corollary. For S normalized holds

sup_{α} |f(S + α)| ≥ D̃(S) − ∑_{ε}′′ D̃(S_{ε})

(where the symbol ∑′′_{ε} means summing over all ε ∈ {0, 1}^{s}, except for ε = 0 and ε = 1).

Proof. Consider the right-hand side of (16). We have:

∏_{j=1}^{s}(δ_{α_{j},γ_{j}}(x_{j}^{(k)}) − γ_{j}) = ∑_{ε=0}^{1}(−1)^{ν(ε)} ∏_{ε_{j}=0} δ_{α_{j},γ_{j}}(x_{j}^{(k)}) ∏_{ε_{j}=1} γ_{j} =

= ∑_{ε=0}^{1}(−1)^{ν(ε)} ∏_{ε_{j}=1} γ_{j}( ∏_{ε_{j}=0} δ_{α_{j},γ_{j}}(x_{j}^{(k)}) − ∏_{ε_{j}=0} γ_{j}) .

It follows, in view of the fact that S is normalized, that

|∑_{k=1}^{N} ρ_{k} ∏_{j=1}^{s}(δ_{α_{j},γ_{j}}(x_{j}^{(k)}) − γ_{j})| =

= |∑_{ε=0}^{1}(−1)^{ν(ε)} ∏_{ε_{j}=1} γ_{j} · ( ∑_{k=1}^{N} ρ_{k} ∏_{ε_{j}=0} δ_{α_{j},γ_{j}}(x_{j}^{(k)}) − ∏_{ε_{j}=0} γ_{j})| ≥

≥ |∑_{k=1}^{N} ρ_{k} ∏_{j=1}^{s} δ_{α_{j},γ_{j}}(x_{j}^{(k)}) − ∏_{j=1}^{s} γ_{j}| − ∑_{ε}′′ |∑_{k=1}^{N} ρ_{k} ∏_{ε_{j}=0} δ_{α_{j},γ_{j}}(x_{j}^{(k)}) − ∏_{ε_{j}=0} γ_{j}| ≥

≥ |∑_{k=1}^{N} ρ_{k} ∏_{j=1}^{s} δ_{α_{j},γ_{j}}(x_{j}^{(k)}) − ∏_{j=1}^{s} γ_{j}| − ∑_{ε}′′ D̃(S_{ε}) ,

and the result follows from Lemma 5.

We can now prove our main theorem. Proof of Theorem 1. Let S be a normalized s-dimensional net. In view of Lemma 1, it is sufficient to prove, that

sup_{α} |f(S + α)| ≥ \frac{1}{A_{s}} D̃(S) ,  (17)

and we shall do it now by means of induction by s.

For s = 1 the inequality (17), as it was already mentioned above, follows from (15′) (for c = 0). Let s ≥ 2. For ε ≠ 0, 1 by Lemma 4 and the induction hypothesis,

sup_{α} |f(S + α)| ≥ sup_{α} |f(S_{ε} + α)| ≥ \frac{1}{A_{s−ν(ε)}} D̃(S_{ε}) ,

(since S_{ε} is (s − ν(ε))-dimensional net), hence

A_{s−ν(ε)} · sup_{α} |f(S + α)| ≥ D̃(S_{ε}) ;  (18)

on the other hand, by Lemma 5,

sup_{α} |f(S + α)| ≥ D̃(S) − ∑_{ε}′′ D̃(S_{ε}) .  (19)

Summing up inequalities (18) for all ε ≠ 0, 1 and adding (19), we obtain:

(1 + ∑_{ε}′′A_{s−ν(ε)}) · sup_{α} |f(S + α)| ≥ D̃(S) ;

but

1 + ∑_{ε}′′A_{s−ν(ε)} = 1 + ∑_{j=1}^{s−1} ( \begin{matrix}s \\ i \end{matrix} ) A_{j} = A_{s} ,

which finishes induction and proves (17). Note. It is easy to obtain the following estimate for the order of growth of A_{s}:

A_{s} < \frac{s!}{(ln 2)^{s}} , s = 1, 2, …

References

[1] Lev V.F., On two versions of L^{2}-discrepancy and geometrical interpretation of diaphony. Acta Math. Hungarica, 70(1-2)(1996).