THE EXACT ORDER OF GENERALIZED DIAPHONY AND MULTIDIMENSIONAL NUMERICAL INTEGRATION

VSEVOLOD F. LEV

Abstract. For a point set in the multidimensional unit torus we introduce an L^{κ}-measure of uniformity of distribution, which for κ = 2 reduces to diaphony (and thus in this case essentially coincides with Weyl L^{2}-discrepancy). For κ ∈ [1, 2] we establish a sharp asymptotic for this new measure as the number of points of the set tends to infinity. Upper and lower-bound estimates are given also for κ > 2.

1. Introduction

Let S be a finite weighted point set in the s-dimensional unit torus 𝕀^{s}. How uniformly are the points of S distributed? This problem goes back to Weyl [18]. Since then, a number of measures for the uniformity of distribution have been proposed, the most widely studied are various versions of discrepancy. The most common kind of discrepancy is the L^{κ}-average of the local discrepancies on all aligned rectangular boxes with the “left bottom corner” at the origin:

D_{κ}(S) = ( ∫_{𝕀^{s}} | ∑_{x^{(k)}<x} ρ_{k} − V (x)|^{κ}dx)^{1/κ}.

(Here x^{(k)} are the points of the set S, ρ_{k} are the corresponding weights, V (x) is the volume of the aligned rectangular box with the “minimum” at the origin and the “maximum” at x, and the sum is extended over all points of S in this box.) An obvious drawback of this discrepancy is that it is biased in giving more attention to irregularities of distribution of S which are closer to the origin than to those far from it. This is harmless for the metric of L^{∞}, as the supremum of local discrepancies on all the boxes with the “left bottom corner” at x can easily be seen to be of the same order of magnitude for all x ∈ 𝕀^{s}. However, the situation changes drastically for κ < ∞, see [7].

A natural way to improve the definition is to average local discrepancies on all aligned rectangular boxes with “floating left bottom corner.” In fact, it is this kind of

1991 Mathematics Subject Classification. Primary: 11K38; Secondary: 11K70.

Key words and phrases. Diaphony, discrepancy, uniform distribution.

2 VSEVOLOD F. LEV

discrepancy which was originally considered in the pioneering paper of Weyl, and we call it Weyl discrepancy below. Unlike regular discrepancy, that of Weyl is invariant under translates and symmetry reflections of S, and is easier to handle due to its averaging nature; clearly, it is an L^{κ}-average of regular discrepancies of the translates S + x of S by all the vectors x ∈ 𝕀^{s}:

D̃_{κ}(S) = (∫_{𝕀^{s}} D_{κ}^{κ}(S + x) dx)^{1/κ} ,

where D_{κ} stands for the regular discrepancy, and D̃_{κ} for Weyl discrepancy.

Another (and undeservedly less known) measure of uniformity of distribution of S is diaphony, which we denote below F (S) and define formally in Section 3. It was introduced in 1976 by Zinterhof (see [20]), who used an analytical definition via absolutely convergent series and to the best of our knowledge, did not know that the analytic construction he brought into consideration also has a transparent geometric interpretation. This geometric face of diaphony was discovered almost 20 years later in [13], where it is shown that diaphony essentially (up to a bounded multiplicative factor) coincides with Weyl L^{2}-discrepancy. This allows one to use Weyl L^{2}-discrepancy and diaphony interchangeably, using either a geometrical or analytical definition, whichever is more convenient. It is worth mentioning that diaphony, like Weyl discrepancy, is invariant with respect to translates and symmetry reflections of S. To summarize, compared to the “usual” discrepancy, Weyl discrepancy and diaphony (which are two faces of the same coin)

– are more natural, giving non-biased treatment to all irregularities of S;

– are easier to handle due to the existence of equivalent definitions of distinct types and the averaging character of the geometric definition;

– have a number of nice invariance properties, which one expects a “good” measure of irregularity of distribution to possess and which the usual discrepancy lacks.

Since 1976, diaphony has been considered in numerous papers (see, for instance, the citations below and the references given there). Many authors use diaphony implicitly, without introducing any special notation, to study distribution problems. Most of the papers that explicitly investigate diaphony concentrate on the one-dimensional case or on estimates of diaphony of particular sequences (as, for instance, [2, 3, 14, 15, 16, 19]). A remarkable exception is the paper of Bykovsky [1], where the asymptotic behavior of F (S) is studied in general case, as N = |S| approaches infinity. Results of Bykovsky imply that

inf_{S} F (S) ≫ \frac{(ln N)^{(s−1)/2}}{N}

for any dimension s (with a constant depending only on s). However, the question sharpness of this estimate remained open for s > 1. In this paper we answer it in the affirmative.

Actually, we do not consider diaphony by itself, but instead introduce a parametric family of measures for the uniformity of distribution of S, diaphony F (S) being obtained for some particular values of the parameters. This is motivated primarily by the requirements of numerical integration applications. (One possible application is given in Theorem 1 below.) We extend the lower bound of Bykovsky to our generalized diaphony, and give a construction of S for which this lower bound is attained. In fact, this construction is borrowed from [4] where it was used to obtain lower-bound estimates of discrepancy; it can be characterized as a weighted version of Frolov’s algebraic nets (see [5]).

All our results are obtained in the general setting of weighted S.

2. Notation

Fix s ∈ ℤ, s ≥ 1. We denote vectors of ℝ^{s} by lower italic or Greek letters, with or without superscripts; subscripts are reserved for vector coordinates (say, x_{j}^{(k)} is the j-th coordinate of the vector x^{(k)}). To distinguish them from scalars, the following two constant vectors will be written in boldface: 0 = (0, …, 0) and 1 = (1, …, 1). The s-dimensional unit cube is

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

here x ≥ 0 means x_{j} ≥ 0 (j = 1, …, s) and x < 1 means x_{j} < 1 (j = 1, …, s). Other vector inequalities below should be interpreted similarly.

By a net we mean a pair S = (X, ρ), where X is a finite set of points in 𝕀^{s}:

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

and ρ is a set of non-negative real weights, corresponding to these points:

ρ = {ρ_{k} ≥ 0 | k = 1, …, N}.

The pair (x^{(k)}, ρ_{k}) is called the k-th node of S. Numeration of nodes is not essential: we will not distinguish nets which differ only in the order of their nodes.

4 VSEVOLOD F. LEV

We put ρ_{0} = ρ_{1} + ⋯ + ρ_{N}. The case ρ_{0} = 0 is of no interest and we assume below that at least one of the weights is strictly positive. If ρ_{0} = 1 we say that S is normalized.

The exponential sum of S is the complex-valued function on ℤ^{s} defined by

T (m) = ∑_{k=1}^{N} ρ_{k}e^{2πi ⟨m,x^{(k)}⟩},

angular brackets standing for the standard inner product. Clearly, T (0) = ρ_{0}, and |T (m)| ≤ ρ_{0} for m ≠ 0.

For x ∈ ℝ, we write \overline{x} = max\{|x|, 1\}. For x, α ∈ ℝ^{s} we write

\overline{x} = \overline{x}_{1} ⋯ \overline{x}_{s}, \overline{x}^{α} = \overline{x}_{1}^{α_{1}} ⋯ \overline{x}_{s}^{α_{s}}.

3. Preliminaries

The original diaphony of Zinterhof was defined with a normalized net S in mind by

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

(here and below, primed sums extend over all non-zero vectors). Generalizing this definition, for α > 0, κ ≥ 1 and arbitrary (not necessarily normalized) S we consider

F_{κ,α}(S) = ( \begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \frac{|T (m)|^{κ}}{\overline{m}^{κα}} + |T (0) − 1|^{κ})^{1/κ}.

The second summand may look somewhat odd at first, but deeper examination shows that it arises very naturally (see Theorem 1 below or [13, Theorem 1]). Qualitatively, it allows one to exclude the situation where a poorly distributed net has small diaphony only because all its weights are very small. However, the principal part of the definition is, of course, the first summand: if it is small, we can make the entire diaphony small by normalizing the weights (save for the above mentioned exotic case of “very small weights”).

Without loss of generality, we assume that the coordinates of α are arranged in ascending order, and write r ∈ [1, s] for the number of appearances of the minimal coordinate:

α_{1} = ⋯ = α_{r} < α_{r+1} ≤ ⋯ ≤ α_{s}.

Throughout the paper, we assume κα_{1} > 1; since T (m) is bounded, this guarantees the absolute convergence of the series for F_{κ,α}.

THE EXACT ORDER OF GENERALIZED DIAPHONY 5

Our primary objective is to prove the following theorem, in which the constants depend on α and κ only (possible dependence of the constants on s is always assumed by default).

Main Theorem.

(i) Assume κ ∈ [1, 2], and let S be a net with N nodes. Then

F_{κ,α}(S) ≫ \frac{(ln N)^{(r−1)/κ}}{N^{α_{1}}} .

(ii) Assume κ ≥ 2, and let S be a net with N nodes. Then

F_{κ,α}(S) ≫ \frac{(ln N)^{(r−1)/κ}}{N^{α_{1}+(1/2−1/κ)}} .

(iii) For each κ ≥ 1, there exists a net S with N nodes (and even a normalized one) such that

F_{κ,α}(S) ≪ \frac{(ln N)^{(r−1)/κ}}{N^{α_{1}}} .

For κ ≤ 2 this theorem establishes the exact order of inf_{S} F_{κ,α}(S), the infimum being taken over all normalized net with N nodes. In particular, for the “usual” diaphony F (S) = F_{2,1}(S), it immediately implies

(1)  inf_{S} F (S) ≍ \frac{(ln N)^{(s−1)/2}}{N} ,

For κ > 2 we have a gap between the estimates. It is not clear what exactly in our argument gives rise to this gap.

The proof of Main Theorem will consist of two independent counterparts: the lower-bound estimate of F_{κ,α} (Section 4) and an explicit construction of S for which this estimate is attained (Section 5).

For the important special case κ = 2, α_{1} = ⋯ = α_{s}, the lower-bound estimate was obtained in [1] by Bykovsky. We show that the general case κ ≤ 2 reduces to this one (while the case κ > 2 requires certain additional considerations). To keep the paper self-contained, we then give a proof of this particular case. Our proof is inspired by that of Bykovsky, though it differs somewhat from the original; the idea behind both proofs comes from the classical paper of Roth [17].

As to the lower-bound estimate in (1), it was observed in [10] that there is another and immediate way to obtain it using Roth’s well-known lower-bound estimate for L^{2}-discrepancy. Namely, if S + x is the translate of S modulo 𝕀^{s} by a vector x ∈ 𝕀^{s}, and if D_{2}(S + x) is the L^{2}-discrepancy of S + x, then as shown in [10, 13]

F (S) ≍ (∫_{𝕀^{s}} D_{2}^{2}(S + x)dx)^{1/2} ,

and the estimate in question now follows from Roth’s

D_{2}(S + x) ≫ \frac{(ln N)^{(s−1)/2}}{N}

(uniformly in x).

We turn to the numerical integration problem. For M > 0 and τ ∈ [1, ∞], denote by E_{τ,α}(M) the class of all continuous 𝕀^{s}-periodic functions f: ℝ^{s} → ℝ with Fourier coefficients f̂ satisfying

( ∑_{m∈ℤ^{s}} |f̂(m)\overline{m}^{α}|^{τ})^{1/τ} ≤ M

(with the standard interpretation for τ = ∞). This classifies 𝕀^{s}-periodic functions according to the rate of decrease of their Fourier coefficients.

It can easily be shown that the error of numerical integration on E_{τ,α}(M) using a net S is intimately related to the generalized diaphony F_{κ,α}(S), where κ is the conjugate to τ: 1/κ + 1/τ = 1.

Theorem 1. Assume κα_{1} > 1. Then

sup_{f∈E_{τ,α}(M)} |∫_{𝕀^{s}} f(x) dx − ∑_{k=1}^{N} ρ_{k}f(x^{(k)})| = MF_{κ,α}(S).

The quantity on the left is the maximal possible error which can occur when we approximate the integral of a function from E_{τ,α}(M) by a finite sum over the points of S = (X, ρ). The proof will be given in Section 6.

Theorem 1 along with our Main Theorem solve the problem of numerical integration on E_{τ,α}(M) as follows:

Corollary 1. Let τ ∈ [2, ∞] and assume α_{1} > 1 − 1/τ. Then

inf_{S} sup_{f∈E_{τ,α}(M)} |∫_{𝕀^{s}} f(x) dx − ∑_{k=1}^{N} ρ_{k}f(x^{(k)})| ≍ M \frac{(ln N)^{(r−1)(1−1/τ)}}{N^{α_{1}}} ,

the infimum being taken over all normalized nets with N nodes.

For κ ≤ 2, the results of this paper were obtained in [8] (using a somewhat more complicated argument) and announced without proof in [12]. The case κ > 2 has never been considered before.

THE EXACT ORDER OF GENERALIZED DIAPHONY 7

4. Lower-bound estimate of F_{κ,α}(S)

Let S be a net with N nodes. If T (0) < 1/2 then F_{κ,α}(S) > 1/2 by the definition and so the lower-bound estimate of Main Theorem is trivial. Otherwise, dividing all the weights of S by ρ_{0} = T (0) (which may increase the diaphony at most twice) we get into the situation when S is normalized.

We first consider the case κ ∈ [1, 2] and prove that

(2)  \begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \frac{|T (m)|^{κ}}{\overline{m}^{κα}} ≫ \frac{(ln N)^{r−1}}{N^{κα_{1}}} .

We can assume r = s. For, if S′ is the net in 𝕀^{r} obtained by the projection of the points of S onto the first r coordinates, if T′ is the exponential sum of S′, and if α′ = (α_{1}, …, α_{r}), then the sum ^{∑ ′}_{m∈ℤ^{r}} |T′(m)|^{κ}/\overline{m}^{κα′} is included into the sum on the left-hand side of (2) when m_{r+1} = ⋯ = m_{s} = 0, and hence (2) will follow from the analogous estimate for S′.

Next, we can replace |T (m)|^{κ} on the left-hand side of (2) by |T (m)|^{2}, since |T (m)| ≤ T (0) = 1 (as S is normalized). Therefore, it suffices to prove

(3)  \begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \frac{|T (m)|^{2}}{\overline{m}^{κα}} ≫ \frac{(ln N)^{s−1}}{N^{κα_{1}}}

under the assumptions α_{1} = ⋯ = α_{s}, T (0) = 1.

Fix a non-negative function φ: ℝ → ℝ with finite support, having derivatives of any order and satisfying φ(0) = 2, ∫_{−∞}^{∞} φ(x)dx = 1 (the values of φ(0) and of the integral have no special meaning; those indicated above are chosen to somewhat simplify the calculations below). For t ∈ ℝ^{s}, 0 < t < 1 and x ∈ ℝ^{s} we define

φ_{t}(x) = ∑_{n∈ℤ^{s}} φ(\frac{x_{1} + n_{1}}{t_{1}} ) ⋯ φ(\frac{x_{s} + n_{s}}{t_{s}} ),

Φ_{t}(x) = ∑_{k=1}^{N} ρ_{k}φ_{t}(x − x^{(k)}).

(Note that for any x the series for φ_{t}(x) actually has only a finite number of non-zero terms.) Obviously, both φ_{t} and Φ_{t} are 𝕀^{s}-periodic.

Consider the Fourier expansion of Φ_{t}:

Φ_{t}(x) = ∑_{m∈ℤ^{s}} Φ̂_{t}(m)e^{2πi ⟨m,x⟩}.

Since Φ_{t}(x) is smooth, the series on the right-hand side converges absolutely, and therefore

(4)  ∑_{k=1}^{N} ρ_{k}Φ_{t}(x^{(k)}) = ∑_{m∈ℤ^{s}} Φ̂_{t}(m) ∑_{k=1}^{N} ρ_{k}e^{2πi ⟨m,x^{(k)}⟩} = ∑_{m∈ℤ^{s}} Φ̂_{t}(m)T (m).

The Fourier coefficients Φ̂_{t}(m) may be evaluated as follows:

Φ̂_{t}(m) = ∑_{k=1}^{N} ρ_{k} ∫_{𝕀^{s}} φ_{t}(x − x^{(k)})e^{−2πi ⟨m,x⟩}dx

= ∑_{k=1}^{N} ρ_{k}e^{−2πi ⟨m,x^{(k)}⟩} ∫_{𝕀^{s}} φ_{t}(x − x^{(k)})e^{−2πi ⟨m,x−x^{(k)}⟩}dx

= T (−m) ∫_{𝕀^{s}} φ_{t}(x)e^{−2πi ⟨m,x⟩}dx

= T (−m) ∑_{n∈ℤ^{s}} ∏_{j=1}^{s} ∫_{0}^{1} φ(\frac{x_{j} + n_{j}}{t_{j}} )e^{−2πi m_{j}x_{j}}dx_{j}

= T (−m) ∏_{j=1}^{s} ∑_{n_{j}∈ℤ}∫_{0}^{1} φ(\frac{x_{j} + n_{j}}{t_{j}} )e^{−2πi m_{j}x_{j}}dx_{j}

= T (−m) ∏_{j=1}^{s} ∫_{−∞}^{∞} φ(x_{j}/t_{j})e^{−2πi m_{j}x_{j}}dx_{j}

= T (−m)t_{1} ⋯ t_{s} ∏_{j=1}^{s} ∫_{−∞}^{∞} φ(x_{j})e^{−2πi m_{j}t_{j}x_{j}}dx_{j}. (5)

In particular,

(6)  Φ̂_{t}(0) = t_{1} ⋯ t_{s}.

We now return to (4) and estimate the sum on the left-hand side from below:

(7)  ∑_{k=1}^{N} ρ_{k}Φ_{t}(x^{(k)}) ≥ ∑_{k=1}^{N} ρ_{k}^{2}φ_{t}(0) ≥ 2^{s} ∑_{k=1}^{N} ρ_{k}^{2} ≥ \frac{2^{s}}{N} (∑_{k=1}^{N} ρ_{k})^{2} = \frac{2^{s}}{N} .

Then, for t_{1} ⋯ t_{s} ≤ 1/N from (4), (6) and (7) we obtain

(8)  \begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} T (m)Φ̂(m) ≥ \frac{2^{s} − 1}{N}.

To estimate Φ̂(m), we use (5). If |m_{j}t_{j}| > 1, then integrating by parts c + 1 times on the right-hand side of (5) (with a sufficiently large integer c, say c = ⌈κα_{s}⌉) we

THE EXACT ORDER OF GENERALIZED DIAPHONY 9

obtain

∫_{−∞}^{∞} φ(x_{j})e^{−2πi m_{j}t_{j}x_{j}}dx_{j} ≪ \frac{1}{\overline{m_{j}t_{j}}^{c+1}}

(with a constant depending only on φ and c), and of course, this holds also if |m_{j}t_{j}| ≤ 1. Therefore,

|Φ̂_{t}(m)| ≪ t_{1} ⋯ t_{s} \frac{|T (m)|}{(\overline{t_{1}m_{1}} ⋯ \overline{t_{s}m_{s}})^{c+1}} ,

and substitution into (8) gives

t_{1} ⋯ t_{s} \begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \frac{|T (m)|^{2}}{(\overline{t_{1}m_{1}} ⋯ \overline{t_{s}m_{s}})^{c+1}} ≫ \frac{1}{N} .

Recalling that t_{1} ⋯ t_{s} ≤ 1/N, c ≥ κα_{1} we obtain

\begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \frac{|T (m)|^{2}}{(\overline{t_{1}m_{1}} ⋯ \overline{t_{s}m_{s}})^{κα_{1}+1}} ≫ 1.

To prove (3) it remains to integrate this last inequality over the region

Ω_{s}(N) = \{t ∈ 𝕀^{s} | \frac{1}{2N} ≤ t_{1} ⋯ t_{s} ≤ \frac{1}{N} \}

using the following technical lemma:

Lemma 1. Let K ∈ ℝ and c ∈ ℝ, c > 1. Then (i)

∫_{Ω_{s}(K)} dt ≫ \frac{(ln K)^{s−1}}{K} (K ≥ 1),

(ii)

∫_{Ω_{s}(K)} \frac{dt}{(\overline{t_{1}m_{1}} ⋯ \overline{t_{s}m_{s}})^{c+1}} ≪ \frac{K^{c−1}}{(\overline{m}_{1} ⋯ \overline{m}_{s})^{c}} (K > 0),

where the constants depend only on s and c.

Proof. (i) We denote the integral by I_{s}(K) and use induction on s. The case s = 1 is trivial. Let s ≥ 2. Then

I_{s}(K) ≥ ∫_{1/K}^{1} (∫_{1/(2Kt_{s})≤t_{1}···t_{s−1}≤1/(Kt_{s})} dt_{1} ⋯ dt_{s−1}) dt_{s}

= ∫_{1/K}^{1} I_{s−1}(Kt_{s})dt_{s}

≫ \frac{1}{K} ∫_{1/K}^{1} \frac{(ln Kt_{s})^{s−2}}{t_{s}} dt_{s}

≥ \frac{1}{K} ∫_{1/\sqrt{K}}^{1} \frac{(ln \sqrt{K})^{s−2}}{t_{s}} dt_{s}

≫ \frac{(ln K)^{s−2}}{K} ∫_{1/\sqrt{K}}^{1} \frac{dt_{s}}{t_{s}}

≫ \frac{(ln K)^{s−1}}{K} .

(ii) We denote the integral by J_{s}(K) and use induction on s. Observe, that \overline{t_{j}m_{j}} = max\{1, |t_{j}m_{j}|\} ≥ max\{t_{j}, t_{j}|m_{j}|\} = t_{j}\overline{m}_{j}, and hence

J_{1}(K) ≤ ∫_{1/2K}^{1/K} \frac{dt_{1}}{\overline{t_{1}m_{1}}^{c}} ≤ \frac{1}{\overline{m}_{1}^{c}} ∫_{1/2K}^{1/K} \frac{dt_{1}}{t_{1}^{c}} ≪ \frac{K^{c−1}}{\overline{m}_{1}^{c}} .

Now let s ≥ 2. If K < 1/2, then Ω_{s}(K) is empty and the proof is complete. If 1/2 ≤ K ≤ 1 and t ∈ Ω_{s}(K), then t_{j} ≥ 1/(2K) ≥ 1/2 (j = 1, …, s) and thus \overline{t_{j}m_{j}} ≥ t_{j}\overline{m}_{j} ≥ \overline{m}_{j}/2, hence

J_{s}(K) ≪ \frac{1}{(\overline{m}_{1} ⋯ \overline{m}_{s})^{c+1}} ≪ \frac{K^{c−1}}{(\overline{m}_{1} ⋯ \overline{m}_{s})^{c}} .

Finally, if K > 1, then by the induction hypothesis

J_{s}(K) = ∫_{1/2K}^{1} \frac{1}{\overline{t_{s}m_{s}}^{c+1}} (∫_{1/(2Kt_{s})≤t_{1}···t_{s−1}≤1/(Kt_{s})} \frac{dt_{1} ⋯ dt_{s−1}}{(\overline{m_{1}t_{1}} ⋯ \overline{m_{s−1}t_{s−1}})^{c+1}} ) dt_{s}

≪ \frac{K^{c−1}}{(\overline{m}_{1} ⋯ \overline{m}_{s−1})^{c}} ∫_{1/2K}^{1} \frac{t_{s}^{c−1}}{\overline{t_{s}m_{s}}^{c+1}} dt_{s},

and it suffices to observe that

∫_{1/2K}^{1} \frac{t_{s}^{c−1}}{\overline{t_{s}m_{s}}^{c+1}} dt_{s} ≤ ∫_{0}^{1/\overline{m}_{s}} + ∫_{1/\overline{m}_{s}}^{1} = ∫_{0}^{1/\overline{m}_{s}} t_{s}^{c−1}dt_{s} + \frac{1}{\overline{m}_{s}^{c+1}} ∫_{1/\overline{m}_{s}}^{1} \frac{dt_{s}}{t_{s}^{2}} ≪ \frac{1}{\overline{m}_{s}^{c}} .

□

We now return to the proof of the Main Theorem and consider the case κ > 2. As above, we may assume r = s, and using the same argument we get

\begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \frac{|T (m)|^{2}}{(\overline{t_{1}m_{1}} ⋯ \overline{t_{s}m_{s}})^{c+2}} ≫ 1

for any positive integer c. The problem is that the sum we wish to estimate incorporates |T (m)|^{κ} ≤ |T (m)|^{2}. To overcome this difficulty, we define τ by 1/(κ/2)+1/τ = 1 and use Hölder’s inequality to obtain

( \begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \frac{|T (m)|^{κ}}{(\overline{t_{1}m_{1}} ⋯ \overline{t_{s}m_{s}})^{cκ/2}} )^{2/κ}( \begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \frac{1}{(\overline{t_{1}m_{1}} ⋯ \overline{t_{s}m_{s}})^{2τ}} )^{1/τ} ≫ 1.

But

\begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \frac{1}{(\overline{t_{1}m_{1}} ⋯ \overline{t_{s}m_{s}})^{2τ}} ≤ ∑_{m∈ℤ^{s}} \frac{1}{(\overline{t_{1}m_{1}} ⋯ \overline{t_{s}m_{s}})^{2}}

= ∏_{j=1}^{s} ∑_{m_{j}∈ℤ} \frac{1}{\overline{t_{j}m_{j}}^{2}}

≪ \frac{1}{t_{1} ⋯ t_{s}}

≤ 2N

for t_{1} ⋯ t_{s} ≥ 1/(2N); hence,

\begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \frac{|T (m)|^{κ}}{(\overline{t_{1}m_{1}} ⋯ \overline{t_{s}m_{s}})^{cκ/2}} ≫ N^{−κ/(2τ)} = N^{1−κ/2}.

Since c is arbitrary, it follows that

\begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \frac{|T (m)|^{κ}}{(\overline{t_{1}m_{1}} ⋯ \overline{t_{s}m_{s}})^{κα_{1}+1}} ≫ N^{1−κ/2},

and Lemma 1 now gives

\begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \frac{|T (m)|^{κ}}{\overline{m}^{κα}} ≫ \frac{(ln N)^{s−1}}{N^{κα_{1}+(κ/2−1)}} ,

which was to be proved.

5. Nets with small order of F_{κ,α}(S)

First, note that constructing a net with small F_{κ,α}(S) we may ignore the issue of normality: if a net S satisfies

(9)  F_{κ,α}(S) ≪ \frac{(ln N)^{(r−1)/κ}}{N^{α_{1}}}

12 VSEVOLOD F. LEV

then automatically T (0) ≥ 1/2 for sufficiently large N, and so the net obtained by a normalization of S will also satisfy (9).

We now describe a construction of nets, proposed by Dobrovolsky in [4]. Denote by 𝕂^{s} the doubled unit cube:

𝕂^{s} = {x ∈ ℝ^{s} | −1 ≤ x < 1}.

For a real non-singular matrix A ∈ M_{s×s}[ℝ] let Λ = {A^{t}n | n ∈ ℤ^{s}} be the lattice, generated by A, and let Λ^{∗} = {A^{−1}n | n ∈ ℤ^{s}} be the dual lattice. The set of points of our net is the set of fractional parts of all those points of Λ^{∗} which fall into 𝕂^{s}:

X = {{A^{−1}n} | n ∈ A𝕂^{s} ∩ ℤ^{s}}.

To define the weights, we fix a non-negative function ψ: ℝ → ℝ, having derivatives of any order, vanishing outside [−1, 1] and satisfying ψ(x) + ψ(x − 1) = 1 for every real x ∈ [0, 1] (the existence of such functions can be easily verified). Next, we define Ψ: ℝ^{s} → ℝ by Ψ(x) = ψ(x_{1}) ⋯ ψ(x_{s}). Now, with each point x = {A^{−1}n} ∈ X we associate the weight ρ(x) = Ψ(A^{−1}n)/ det Λ.

Let S(Λ) be the net obtained in this way. Denote

δ_{m} = \begin{cases}1 & if m = 0, \\ 0 & otherwise. \end{cases}

Lemma 2. For m ∈ ℤ^{s} the exponential sum of S(Λ) is

T (m) = δ_{m} + \begin{matrix}∑ & ′ \\ z∈Λ \end{matrix} ∫_{𝕂^{s}} Ψ(x)e^{2πi ⟨m−z,x⟩}dx.

Proof. Using the multidimensional Poisson summation formula and then changing the variable of integration, we get:

T (m) = \frac{1}{det Λ} ∑_{n∈A𝕂^{s}∩ℤ^{s}} Ψ(A^{−1}n)e^{2πi ⟨m,A^{−1}n⟩}

= \frac{1}{det Λ} ∑_{n∈ℤ^{s}} ∫_{A𝕂^{s}} Ψ(A^{−1}x)e^{2πi ⟨m,A^{−1}x⟩}e^{−2πi ⟨n,x⟩}dx

= ∑_{n∈ℤ^{s}} ∫_{𝕂^{s}} Ψ(x)e^{2πi ⟨m,x⟩}e^{−2πi ⟨n,Ax⟩}dx

= ∑_{n∈ℤ^{s}} ∫_{𝕂^{s}} Ψ(x)e^{2πi ⟨m−A^{t}n,x⟩}dx

= ∑_{z∈Λ} ∫_{𝕂^{s}} Ψ(x)e^{2πi ⟨m−z,x⟩}dx,

THE EXACT ORDER OF GENERALIZED DIAPHONY 13

since A^{t}n varies over all the points of Λ. It remains to evaluate the term with z = 0:

∫_{𝕂^{s}} Ψ(x)e^{2πi ⟨m,x⟩}dx = ∏_{j=1}^{s} ∫_{−1}^{1} ψ(x_{j})e^{2πi m_{j}x_{j}}dx_{j}

= ∏_{j=1}^{s} (∫_{0}^{1} ψ(x_{j} − 1)e^{2πi m_{j}x_{j}}dx_{j} + ∫_{0}^{1} ψ(x_{j})e^{2πi m_{j}x_{j}}dx_{j})

= ∏_{j=1}^{s} ∫_{0}^{1} e^{2πi m_{j}x_{j}}dx_{j} = δ_{m}.

□

Corollary 2. For m ∈ ℤ^{s} we have:

T (m) = δ_{m} + O( \begin{matrix}∑ & ′ \\ z∈Λ \end{matrix} \frac{1}{\overline{z − m}^{κα}} )

where the constant depends only on α and κ. Proof. We fix a sufficiently large integer c (say, c = ⌈κα_{s}⌉) and use Lemma 2, integrating by parts c times over x_{j} for all j satisfying |m_{j} − z_{j}| > 1. □

Denote

ζ_{Λ}(α) = \begin{matrix}∑ & ′ \\ z∈Λ \end{matrix} \frac{1}{\overline{z}^{α}} .

Proposition 1. Assume ζ_{Λ}(κα) ≤ C for a positive constant C. Then

F_{κ,α}^{κ}(S(Λ)) ≪ ζ_{Λ}(κα)

with the constant depending on C, α, κ. Proof. By Corollary 2,

|T (0) − 1|^{κ} ≪ (ζ_{Λ}(κα))^{κ} ≪ ζ_{Λ}(κα)

and hence also T (0) = O(1). Thus applying Corollary 2 once again we obtain

\begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \frac{|T (m)|^{κ}}{\overline{m}^{κα}} ≤ (T (0))^{κ−1} \begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \frac{|T (m)|}{\overline{m}^{κα}}

≪ \begin{matrix}∑ & ′ \\ m∈ℤ^{s} \end{matrix} \begin{matrix}∑ & ′ \\ z∈Λ \end{matrix} \frac{1}{\overline{m}^{κα}\overline{z − m}^{κα}}

≤ \begin{matrix}∑ & ′ \\ z∈Λ \end{matrix} ∏_{j=1}^{s} ∑_{m_{j}∈ℤ} \frac{1}{(\overline{m}_{j}\overline{z_{j} − m_{j}})^{κα_{j}}} ,

and it can be easily seen (see, for instance, [6, Chapter I, Section 2]) that the inner sum is bounded by 1/\overline{z}_{j}^{κα_{j}}. □

An important characteristic of Λ which determines the quality of S(Λ) is

q(Λ) = min_{z∈Λ}′ \overline{z}

(here z assumes non-zero points of Λ). The following lemma was proved in the particular case α_{1} = ⋯ = α_{s} in [4], and in the general case in [9, 11].

Lemma 3. Assume q(Λ) ≥ 2 and α_{1} > 1. Then

ζ_{Λ}(α) ≪ \frac{(ln q(Λ))^{r−1}}{(q(Λ))^{α_{1}}} .

Corollary 3. Assume q(Λ) ≥ 2. Then

F_{κ,α}^{κ}(S(Λ)) ≪ \frac{(ln q(Λ))^{r−1}}{(q(Λ))^{κα_{1}}} .

We are now in a position to choose the matrix A. Let A = μA_{0}, where μ is a real factor, tending to infinity, and A_{0} is a fixed matrix of special form, described below. To emphasize the dependence on μ, we will write S_{μ}, q_{μ} instead of S(Λ), q(Λ), and let N_{μ} be the number of nodes of S_{μ}. Since N_{μ} is the number of integer points in μA_{0}𝕂^{s}, we have

(10)  N_{μ} = 2^{s}μ^{s}| det A_{0}|(1 + o(1)).

Following the remarkable idea of Frolov [5], we choose

A_{0} = (\begin{matrix}ω_{1}^{(1)} & … & ω_{1}^{(s)} \\ ⋮ & & ⋮ \\ ω_{s}^{(1)} & … & ω_{s}^{(s)} \end{matrix}) ,

where ω_{1}^{(1)}, …, ω_{s}^{(1)} is an integer algebraic basis of some fixed real extension of the field of rational numbers, and ω_{1}^{(j)}, …, ω_{s}^{(j)} (j = 2, …, s) are the conjugate bases. Then coordinates of any non-zero point z ∈ Λ are of the form

z_{j} = μ(n_{1}ω_{1}^{(j)} + ⋯ + n_{s}ω_{s}^{(j)}) (j = 1, …, s)

(for some non-zero n ∈ ℤ^{s}), and hence

\overline{z} ≥ |z_{1} ⋯ z_{s}| = μ^{s}| ∏_{j=1}^{s}(n_{1}ω_{1}^{(j)} + ⋯ + n_{s}ω_{s}^{(j)})|.

But the product on the right-hand side is the norm of a non-zero algebraic integer, hence \overline{z} ≥ μ^{s} and q_{μ} ≥ μ^{s} ≫ N_{μ}. Therefore by Corollary 3

F_{κ,α}^{κ}(S_{μ}) ≪ \frac{(ln N_{μ})^{r−1}}{N_{μ}^{κα_{1}}} .

The only problem remaining is that we cannot guarantee that for any given N there exists μ such that N_{μ} = N. This can be easily dealt with as follows. By (10), we can always find μ in such a way that

(11)  N_{μ} ≤ N < N_{μ}(1 + o(1)).

Now, based on the net S_{μ} = (X, ρ), we build another net S̃ = (X̃, ρ̃) with precisely N nodes defining

(x̃^{(k)}, ρ̃_{k}) = \begin{cases}(x^{(k)}, ρ_{k}) & k = 1, …, N_{μ}, \\ (0, 0) & k = N_{μ} + 1, …, N. \end{cases}

Obviously, the exponential sum of S̃ coincides with that of S, and therefore

F_{κ,α}(S̃) = F_{κ,α}(S_{μ}) ≪ \frac{(ln N_{μ})^{(r−1)/κ}}{N_{μ}^{α_{1}}} ≪ \frac{(ln N)^{(r−1)/κ}}{N^{α_{1}}} ,

completing the proof.

6. Numerical integration of functions with constrained Fourier coefficients

Recall that for M > 0, τ ∈ [1, ∞] we defined E_{τ,α}(M) as the class of all those continuous 𝕀^{s}-periodic functions f: ℝ^{s} → ℝ with Fourier coefficients f̂ satisfying

( ∑_{m∈ℤ^{s}} |f̂(m)\overline{m}^{α}|^{τ})^{1/τ} ≤ M.

For f ∈ E_{τ,α}(M) denote

R(f; S) = ∑_{k=1}^{N} ρ_{k}f(x^{(k)}) − ∫_{𝕀^{s}} f(x)dx

(the error of numerical integration of f on the net S) and let

R(E_{τ,α}(M); S) = sup_{f∈E_{τ,α}(M)} |R(f; S)|

(the error of numerical integration of E_{τ,α}(M) on S).

Proof of Theorem 1. We consider only the case τ < ∞; the modifications to be made for τ = ∞ are obvious. For brevity, we write t(m) = T (m), if m ≠ 0, and t(0) = T (0) − 1. Since

∑_{m∈ℤ^{s}} |f̂(m)| = ∑_{m∈ℤ^{s}} |f̂(m)\overline{m}^{α}| \frac{1}{\overline{m}^{α}} ≤ ( ∑_{m∈ℤ^{s}} |f̂(m)\overline{m}^{α}|^{τ})^{1/τ}( ∑_{m∈ℤ^{s}} \frac{1}{\overline{m}^{κα}} )^{1/κ},

the assumption κα_{1} > 1 ensures the absolute convergence of the Fourier series for f, and therefore (as in (4))

∑_{k=1}^{N} ρ_{k}f(x^{(k)}) = ∑_{m∈ℤ^{s}} f̂(m)T (m) = ∑_{m∈ℤ^{s}} f̂(m)t(m) + f̂(0),

R(f; S) = ∑_{m∈ℤ^{s}} f̂(m)t(m) = ∑_{m∈ℤ^{s}} f̂(m)\overline{m}^{α} \frac{t(m)}{\overline{m}^{α}}.

The estimate

|R(f; S)| ≤ MF_{κ,α}(S)

now follows by the inequality of Hölder. The equality is attained for the function f defined by

f̂(m) = \begin{cases}C \overline{t(m)} |t(m)|^{κ−2}/\overline{m}^{κα} & if t(m) ≠ 0, \\ 0 & otherwise, \end{cases}

where C is a real positive normalizing factor (which, of course, could be written out explicitly). Note, that f is real since f̂(−m) = \overline{f̂(m)}. □

References

[1] V.A. Bykovsky, ‘On the right order of error of optimal cubature formulas in the spaces with dominating derivation and L^{2}-discrepancy of nets’, Preprint, Dalnevost. Science Center of the USSR Acad. of Sciences, Vladivostok, 1985 [Russian].

[2] H. Chaix and H. Faure, ‘Discripance et diaphonie en dimension un’ (French) [‘Discrepancy and diaphony in dimension one’], Acta Arith., 63 (1993), no. 2, 103–141.

[3] H. Chaix and H. Faure, ‘Discripance et diaphonie des suites de van der Corput giniralisies. III’ (French) [‘Discrepancy and diaphony of the generalized van der Corput sequences. III’], C. R. Acad. Sci. Paris Sér. I Math., 312 (1991), no. 11, 755–758.

[4] N.M. Dobrovolsky, Number-theoretic nets and their applications, Diss. kand. phis.-math. nauk, Tula, 1984 [Russian].

[5] K.K. Frolov, ‘Upper-bound error estimates on classes of functions’, Dokl. Akad. Nauk SSSR, 231 (1976), no. 4, 818–821 [Russian].

[6] N.M. Korobov, Number-theoretic methods in numerical analysis, Fizmatgiz, Moscow, 1963 [Russian].

[7] V.F. Lev, ‘Translations of nets and relationship between Supreme and L^{κ}-discrepancies’, Acta Math. Hungar., 70 (1996), no. 1–2, 1–12.

[8] , ‘On quadrature formulas for classes with restrictions on Fourier coefficients’, Deposited to VINITI (USSR) 27.8.1987, no. 6294-B87 [Russian].

[9] , ‘Hyperbolic zeta-function of general form’, Deposited to VINITI (USSR) 27.8.1987, no. 6296-B87 [Russian].

[10] , ‘Diaphony and L^{2}-discrepancies of multidimensional nets’, Mat. Zametki, 47 (1990), no. 6, 45–54 [Russian]. English translation in: Math. Notes, 47 (1990), no. 5–6, 556–564.

[11] , ‘Hyperbolic zeta-function of general form’, Mat. Zametki, 48 (1990), no. 5, 148–150 [Russian].

[12] , ‘Quadrature formulas for classes with restrictions on Fourier coefficients’, Mat. Zametki, 49 (1991), no. 2, 144–147 [Russian]. English translation in: Math. Notes, 49 (1991), no. 1–2, 219–221.

[13] , ‘On two versions of L^{2}-discrepancy and geometrical interpretation of diaphony’, Acta Math. Hungar., 69 (1995), no. 4, 281–300.

[14] G. Paghs, ‘Van der Corput sequences, Kakutani transforms and one-dimensional numerical integration’, J. Comput. Appl. Math., 44 (1992), no. 1, 21–39.

[15] P.D. Proĭnov and V.S. Grozdanov, ‘On the Diaphony of the Van der Corput-Halton Sequence’, J. Number Theory, 30 (1988), 94–104.

[16] P.D. Proĭnov and E.Y. Atanassov, ‘On the distribution of the van der Corput generalized sequences’, C. R. Acad. Sci. Paris Sér. I Math., 307 (1988), no. 18, 895–900.

[17] K.F. Roth, ‘On irregularities of distribution. I’, Mathematika, 1 (1954), 73–79.

[18] H. Weyl, ‘Über die Gleichverteilung von Zahlen mod. Eins’, Math. Ann., 77 (1916), 313–352.

[19] Y.-J. Xiao, ‘Suites iquiriparties associies aux automorphismes du tore’ (French) [‘Uniformly distributed sequences associated with the translations on a torus’], C. R. Acad. Sci. Paris Sér. I Math., 311 (1990), no. 10, 579–582.

[20] P. Zinterhof, ‘Über einige Abschätzungen bei der Approximation von Funktionen mit Gleichverteilungsmethoden’ (German), sterreich. Akad. Wiss. Math.-Natur. Kl. S.-B. II, 185 (1976), no. 1–3, 121–132.

Dept. of Mathematics, The University of Georgia, 30605 Athens, GA

E-mail address: seva@@math.uga.edu