1 Background
Let
$d,N$
be positive integers and let
${\mathcal{P}}_{N,d}$
be a point set in the
$d$
-dimensional unit cube
$[0,1)^{d}$
with
$N$
elements. The discrepancy function of
${\mathcal{P}}_{N,d}$
is defined as
$$\begin{eqnarray}\displaystyle D_{{\mathcal{P}}_{N,d}}(\boldsymbol{x})=\frac{1}{N}\mathop{\sum }_{\boldsymbol{z}\in {\mathcal{P}}_{N,d}}\unicode[STIX]{x1D712}_{[\mathbf{0},\boldsymbol{x})}(\boldsymbol{z})-x_{1}\cdots x_{d}. & & \displaystyle\end{eqnarray}$$
Here
$\unicode[STIX]{x1D712}_{A}$
denotes the characteristic function of a subset
$A\in \mathbb{R}^{d}$
. Thus
$D_{{\mathcal{P}}_{N,d}}(\boldsymbol{x})$
denotes the difference between the actual and expected proportions of points that fall into
$[\mathbf{0},\boldsymbol{x})=[0,x_{1})\times \cdots \times [0,x_{d})$
, where
$\boldsymbol{x}=(x_{1},\ldots ,x_{d})\in [0,1]^{d}$
.
We define the
$L_{p}$
-discrepancy of
${\mathcal{P}}_{N,d}$
as the
$L_{p}$
-norm of the discrepancy function, i.e.,
$$\begin{eqnarray}L_{p,N}({\mathcal{P}}_{N,d})=\Vert D_{{\mathcal{P}}_{N,d}}|L_{p}([0,1]^{d})\Vert \quad \text{for }p\in [1,\infty ].\end{eqnarray}$$
Let
${\mathcal{S}}_{d}$
be an infinite sequence in
$[0,1)^{d}$
and let
$N\in \mathbb{N}$
. We define the discrepancy function of
${\mathcal{S}}_{d}$
as
$D_{{\mathcal{S}}_{d}}^{N}(\boldsymbol{x})=D_{{\mathcal{P}}_{N,d}}(\boldsymbol{x})$
, where the point set
${\mathcal{P}}_{N,d}$
consists of the first
$N$
elements of
${\mathcal{S}}_{d}$
, and we define the
$L_{p}$
-discrepancy of
${\mathcal{S}}_{d}$
as
$$\begin{eqnarray}L_{p,N}({\mathcal{S}}_{d})=\Vert D_{{\mathcal{S}}_{d}}^{N}|L_{p}([0,1]^{d})\Vert \quad \text{for }p\in [1,\infty ].\end{eqnarray}$$
The
$L_{p}$
-discrepancy is a quantitative measure for the irregularity of distribution of finite point sets and of infinite sequences. The reader is referred to [Reference Beck and Chen1, Reference Drmota and Tichy17, Reference Kuipers and Niederreiter20] for extensive introductions to this topic.
The conceptual difference in the concept between the discrepancy of finite point sets and infinite sequences is pointed out in [Reference Matoušek27]: for finite point sets one is interested in the behaviour of the whole set
$\{\boldsymbol{x}_{0},\boldsymbol{x}_{1},\ldots ,\boldsymbol{x}_{N-1}\}$
with a fixed number of elements
$N$
, whereas for infinite sequences one is interested in the discrepancy of all initial segments
$\{\boldsymbol{x}_{0}\}$
,
$\{\boldsymbol{x}_{0},\boldsymbol{x}_{1}\}$
,
$\{\boldsymbol{x}_{0},\boldsymbol{x}_{1},\boldsymbol{x}_{2}\},\ldots ,\{\boldsymbol{x}_{0},\boldsymbol{x}_{1},\boldsymbol{x}_{2},\ldots ,\boldsymbol{x}_{N-1}\}$
, where
$N=2,3,4,\ldots .$
In this sense the discrepancy of finite point sets can be viewed as a static setting and the discrepancy of infinite sequences as a dynamic setting. In many situations, the difference between these two settings in discrepancy estimates comes at a cost of “one dimension”. In particular, this means that the dynamic setting in dimension
$d$
is related to the static setting in dimension
$d+1$
, although this connection is not so straightforward, especially in proving upper bounds. This observation will also be confirmed by our results.
It is well known from results of Roth [Reference Roth32] and Schmidt [Reference Schmidt35] that for every
$p\in (1,\infty ]$
and every
$d\in \mathbb{N}$
there exists a positive constant
$c_{p,d}$
with the following property: for every finite
$N$
-element point set
${\mathcal{P}}_{N,d}$
in
$[0,1)^{d}$
with
$N\geqslant 2$
we have
$$\begin{eqnarray}L_{p,N}({\mathcal{P}}_{N,d})\geqslant c_{p,d}\,N^{-1}(\log N)^{(d-1)/2}.\end{eqnarray}$$
These results were extended to infinite sequences by Proinov [Reference Proinov31] (see also [Reference Dick, Pillichshammer, Kritzer, Niederreiter, Pillichshammer and Winterhof16] for a proof). For every
$p\in (1,\infty ]$
and every
$d\in \mathbb{N}$
,
$d\geqslant 2$
, there exists a positive constant
$c_{p,d}$
with the following property: for every infinite sequence
${\mathcal{S}}_{d}$
in
$[0,1)^{d}$
we have
$$\begin{eqnarray}L_{p,N}({\mathcal{S}}_{d})\geqslant c_{p,d}\,N^{-1}(\log N)^{d/2}\quad \text{for infinitely many }N\in \mathbb{N}.\end{eqnarray}$$
The lower bound (1.2) for finite point sets is known to be best possible in the order of magnitude in
$N$
, i.e., for every
$d,N\in \mathbb{N}$
,
$N\geqslant 2$
, one can find (and explicitly construct) an
$N$
-element point set
${\mathcal{P}}_{N,d}$
in
$[0,1)^{d}$
with
$L_{p}$
-discrepancy of order
$$\begin{eqnarray}L_{p,N}({\mathcal{P}}_{N,d})\ll _{p,d}\,N^{-1}(\log N)^{(d-1)/2}.\end{eqnarray}$$
(For functions
$f,g:D\subseteq \mathbb{N}\rightarrow \mathbb{R}$
with
$g\geqslant 0$
the notation
$f(N)\ll g(N)$
means that there exists some
$C>0$
such that
$f(N)\leqslant Cg(N)$
for all
$N\in D$
. If we want to stress that
$C$
depends on some parameters, say
$a,b$
, then this is indicated by writing
$f(N)\ll _{a,b}g(N)$
. If we have
$f(N)\ll g(N)$
and
$g(N)\ll f(N)$
, then we write
$f(N)\asymp g(N)$
.)
The first proof of (1.4) was given by Roth [Reference Roth33] for
$p=2$
and arbitrary
$d$
and finally by Chen [Reference Chen7] in the general case, albeit using a probabilistic approach. Explicit constructions are due to Chen and Skriganov [Reference Chen and Skriganov8] and Skriganov [Reference Skriganov36] (the first time that for each
$1\leqslant p<\infty$
a construction method of an optimal point set is given), Dick and Pillichshammer [Reference Dick and Pillichshammer15], Dick [Reference Dick11] (the first proof where the construction method of the point set does not depend on
$p$
), and Markhasin [Reference Markhasin26].
It is also known that the lower bound (1.3) for infinite sequences is best possible for all
$p\in (1,\infty )$
. This was shown by the authors of the present paper in the recent work [Reference Dick, Hinrichs, Markhasin and Pillichshammer13] where explicit constructions
${\mathcal{S}}_{d}$
of infinite sequences in arbitrary dimensions
$d$
were provided whose
$L_{p}$
-discrepancy satisfies
$$\begin{eqnarray}L_{p,N}({\mathcal{S}}_{d})\ll _{p,d}\,N^{-1}(\log N)^{d/2}.\end{eqnarray}$$
The sequences and methods developed in [Reference Dick, Hinrichs, Markhasin and Pillichshammer13] are the fundamental basis for the results that will be presented in this paper (see, for example, Lemma 4.5).
On the other hand, the
$L_{\infty }$
-discrepancy remains elusive. We have constructions of infinite sequences
${\mathcal{S}}_{d}$
in
$[0,1)^{d}$
(for example order-1 digital
$(t,d)$
-sequences as presented in §4, see [Reference Dick and Pillichshammer14, Reference Niederreiter28, Reference Niederreiter29]) such that
$$\begin{eqnarray}\displaystyle L_{\infty ,N}({\mathcal{S}}_{d})\ll _{d}\,N^{-1}(\log N)^{d}. & & \displaystyle\end{eqnarray}$$
Regarding lower bounds, it is known that there exists some
$c_{d}>0$
and
$\unicode[STIX]{x1D702}_{d}\in (0,\frac{1}{2})$
such that for every sequence
${\mathcal{S}}_{d}$
in
$[0,1)^{d}$
we have
$$\begin{eqnarray}L_{\infty ,N}({\mathcal{S}}_{d})\geqslant c_{d}\,N^{-1}(\log N)^{d/2+\unicode[STIX]{x1D702}_{d}}\quad \text{for infinitely many }N\in \mathbb{N}.\end{eqnarray}$$
This result follows from a corresponding result for finite point sets by Bilyk et al [Reference Bilyk, Lacey and Vagharshakyan3]. For growing
$d$
the exponent
$\unicode[STIX]{x1D702}_{d}$
in this estimate tends to zero.
The quest for the exact order of the
$L_{\infty }$
-discrepancy in the multivariate case is a very demanding open question. Only for
$d=1$
it is known that the exact order of the
$L_{\infty }$
-discrepancy of infinite sequences is
$(\log N)/N$
. This follows from (1.6) together with a celebrated result of Schmidt [Reference Schmidt34].
2 Intermediate norms
It is now a natural and instructive question to ask what happens in intermediate spaces “close” to
$L_{\infty }$
. One standard example of such spaces is the space
$\text{BMO}^{d}$
, which stands for bounded mean oscillation. For the definition of this space we need the concept of Haar functions.
We define
$\mathbb{N}_{0}=\mathbb{N}\cup \{0\}$
and
$\mathbb{N}_{-1}=\mathbb{N}_{0}\cup \{-1\}$
. Let
$\mathbb{D}_{j}=\{0,1,\ldots ,2^{j}-1\}$
for
$j\in \mathbb{N}_{0}$
and
$\mathbb{D}_{-1}=\{0\}$
. For
$\,\boldsymbol{j}=(j_{1},\ldots ,j_{d})\in \mathbb{N}_{-1}^{d}$
let
$\mathbb{D}_{\boldsymbol{j}}=\mathbb{D}_{j_{1}}\times \cdots \times \mathbb{D}_{j_{d}}$
. For
$\,\boldsymbol{j}\in \mathbb{N}_{-1}^{d}$
we write
$|\,\boldsymbol{j}|=\max (j_{1},0)+\cdots +\max (j_{d},0)$
.
For
$j\in \mathbb{N}_{0}$
and
$m\in \mathbb{D}_{j}$
we call the interval
$I_{j,m}=[2^{-j}m,2^{-j}(m+1))$
the
$m$
th dyadic interval in
$[0,1)$
on level
$j$
. We put
$I_{-1,0}=[0,1)$
and call it the
$0$
th dyadic interval in
$[0,1)$
on level
$-1$
. Let
$I_{j,m}^{+}=I_{j+1,2m}$
and
$I_{j,m}^{-}=I_{j+1,2m+1}$
be the left and right half of
$I_{j,m}$
, respectively. For
$\,\boldsymbol{j}\in \mathbb{N}_{-1}^{d}$
and
$\boldsymbol{m}=(m_{1},\ldots ,m_{d})\in \mathbb{D}_{\boldsymbol{j}}$
we call
$I_{\boldsymbol{j},\boldsymbol{m}}=I_{j_{1},m_{1}}\times \cdots \times I_{j_{d},m_{d}}$
the
$\boldsymbol{m}$
th dyadic interval in
$[0,1)^{d}$
on level
$\,\boldsymbol{j}$
. We call the number
$|\,\boldsymbol{j}|$
the order of the dyadic interval
$I_{\boldsymbol{j},\boldsymbol{m}}$
. Its volume is
$2^{-|\,\boldsymbol{j}|}$
.
Let
$j\in \mathbb{N}_{0}$
and
$m\in \mathbb{D}_{j}$
. Let
$h_{j,m}$
be the function on
$[0,1)$
with support in
$I_{j,m}$
and the constant values
$1$
on
$I_{j,m}^{+}$
and
$-1$
on
$I_{j,m}^{-}$
. We put
$h_{-1,0}=\unicode[STIX]{x1D712}_{I_{-1,0}}$
on
$[0,1)$
. The function
$h_{j,m}$
is called the
$m$
th dyadic Haar function on level
$j$
.
Let
$\,\boldsymbol{j}\in \mathbb{N}_{-1}^{d}$
and
$\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}$
. The function
$h_{\boldsymbol{j},\boldsymbol{m}}$
given as the tensor product
$$\begin{eqnarray}h_{\boldsymbol{j},\boldsymbol{m}}(\boldsymbol{x})=h_{j_{1},m_{1}}(x_{1})\cdots h_{j_{d},m_{d}}(x_{d})\end{eqnarray}$$
for
$\boldsymbol{x}=(x_{1},\ldots ,x_{d})\in [0,1)^{d}$
is called a dyadic Haar function on
$[0,1)^{d}$
. The system of dyadic Haar functions
$h_{\boldsymbol{j},\boldsymbol{m}}$
for
$\,\boldsymbol{j}\in \mathbb{N}_{-1}^{d},\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}$
is called dyadic Haar basis on
$[0,1)^{d}$
.
It is well known that the system
$$\begin{eqnarray}\{2^{|\,\boldsymbol{j}|/2}h_{\boldsymbol{ j},\boldsymbol{m}}:\boldsymbol{j}\in \mathbb{N}_{-1}^{d},\,\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{ j}}\}\end{eqnarray}$$
is an orthonormal basis of
$L_{2}([0,1)^{d})$
, an unconditional basis of
$L_{p}([0,1)^{d})$
for
$1<p<\infty$
and a conditional basis of
$L_{1}([0,1)^{d})$
. For any function
$f\in L_{2}([0,1)^{d})$
we have Parseval’s identity
$$\begin{eqnarray}\Vert f|L_{2}([0,1)^{d})\Vert ^{2}=\mathop{\sum }_{\boldsymbol{j}\in \mathbb{N}_{-1}^{d}}2^{|\,\boldsymbol{j}|}\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}|\langle f,h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{2},\end{eqnarray}$$
where
$\langle \cdot ,\cdot \rangle$
denotes the usual
$L_{2}$
-inner product, i.e.,
$\langle f,g\rangle =\int _{[0,1]^{d}}f(\boldsymbol{x})g(\boldsymbol{x})\,d\boldsymbol{x}$
. The terms
$\langle f,h_{\boldsymbol{j},\boldsymbol{m}}\rangle$
are called the Haar coefficients of the function
$f$
.
For an integrable function
$f:[0,1]^{d}\rightarrow \mathbb{R}$
we define
$$\begin{eqnarray}\Vert f|\text{BMO}^{d}\Vert ^{2}=\sup _{U\subseteq [0,1)^{d}}\unicode[STIX]{x1D706}_{d}(U)^{-1}\mathop{\sum }_{\boldsymbol{j}\in \mathbb{N}_{0}^{d}}2^{|\,\boldsymbol{j}|}\mathop{\sum }_{\substack{ \boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}} \\ I_{\boldsymbol{j},\boldsymbol{m}}\subseteq U}}|\langle f,h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{2},\end{eqnarray}$$
where
$h_{\boldsymbol{j},\boldsymbol{m}}$
is the
$\boldsymbol{m}$
th dyadic Haar function on level
$\,\boldsymbol{j}$
,
$\unicode[STIX]{x1D706}_{d}$
is the
$d$
-dimensional Lebesgue measure and the supremum is taken over all measurable sets
$U\subseteq [0,1)^{d}$
.
The space
$\text{BMO}^{d}$
contains all integrable functions
$f$
with finite norm
$\Vert f|\text{BMO}^{d}\Vert$
. Note that strictly speaking
$\Vert f|\text{BMO}^{d}\Vert$
is only a seminorm, since it vanishes on linear combinations of functions which are constant in one or more coordinate directions. This means that formally we need to consider a factor space over such functions. For a more detailed study of the spaces
$\text{BMO}^{d}$
we refer to [Reference Chang and Fefferman5] and [Reference Chang, Wilson and Wolff6].
We consider the
$\text{BMO}$
-seminorm of the discrepancy function of infinite sequences and call this the
$\text{BMO}$
-discrepancy.
For finite point sets the following is shown in [Reference Bilyk and Markhasin4, Theorems 1.1 and 1.2]. Suppose that
$d\in \mathbb{N}$
. For every finite point set
${\mathcal{P}}_{N,d}$
in
$[0,1)^{d}$
,
$$\begin{eqnarray}\Vert D_{{\mathcal{P}}_{N,d}}|\text{BMO}^{d}\!\Vert \gg \,N^{-1}(\log N)^{(d-1)/2}\quad \text{ for all }N\in \mathbb{N}\setminus \{1\}.\end{eqnarray}$$
Furthermore, there exists a finite point set
${\mathcal{P}}_{N,d}$
in
$[0,1)^{d}$
such that
$$\begin{eqnarray}\Vert D_{{\mathcal{P}}_{N,d}}|\text{BMO}^{d}\!\Vert \ll _{d}\,N^{-1}(\log N)^{(d-1)/2}\quad \text{for all }N\in \mathbb{N}\setminus \{1\}.\end{eqnarray}$$
The first main result of this paper is a corresponding result for infinite sequences.
Theorem 2.1. Suppose that
$d\in \mathbb{N}$
. For every infinite sequence
${\mathcal{S}}_{d}$
in
$[0,1)^{d}$
,
$$\begin{eqnarray}\Vert D_{{\mathcal{S}}_{d}}^{N}|\text{BMO}^{d}\!\Vert \gg \,N^{-1}(\log N)^{d/2}\quad \text{for infinitely many }N\in \mathbb{N}.\end{eqnarray}$$
Furthermore, there exists an infinite sequence
${\mathcal{S}}_{d}$
in
$[0,1)^{d}$
such that
$$\begin{eqnarray}\Vert D_{{\mathcal{S}}_{d}}^{N}|\text{BMO}^{d}\!\Vert \ll _{d}\,N^{-1}(\log N)^{d/2}\quad \text{for all }N\in \mathbb{N}\setminus \{1\}.\end{eqnarray}$$
The proof of this result will be presented in §5.1.
As another example we study the exponential Orlicz norm, which is closer to the
$L_{\infty }$
-norm than any
$L_{p}$
-norm with
$1\leqslant p<\infty$
. Thus bounds on the exponential Orlicz norm of the discrepancy function shed more light on the behaviour of the
$L_{\infty }$
-norm. For a probability space
$(\unicode[STIX]{x1D6FA},P)$
, let
$\mathbb{E}$
denote the expectation over
$(\unicode[STIX]{x1D6FA},P)$
. To define the Orlicz norm, let
$\unicode[STIX]{x1D713}:[0,\infty )\rightarrow [0,\infty )$
be a convex function with
$\unicode[STIX]{x1D713}(x)=0$
if and only if
$x=0$
. The Orlicz norm
$L^{\unicode[STIX]{x1D713}}$
of a
$(\unicode[STIX]{x1D6FA},P)$
-measurable function
$f$
is now given by
$$\begin{eqnarray}\Vert f|L^{\unicode[STIX]{x1D713}}\Vert =\inf \{K>0:\mathbb{E}\unicode[STIX]{x1D713}(|f|/K)\leqslant 1\},\end{eqnarray}$$
where we set
$\inf \emptyset =\infty$
. The Orlicz space
$L^{\unicode[STIX]{x1D713}}$
consists of all functions
$f$
with finite Orlicz norm
$\Vert f|L^{\unicode[STIX]{x1D713}}\Vert$
.
For
$\unicode[STIX]{x1D6FC}>0$
, one obtains the exponential Orlicz norm
$\exp (L^{\unicode[STIX]{x1D6FC}})=L^{\unicode[STIX]{x1D713}_{\unicode[STIX]{x1D6FC}}}$
by choosing
$\unicode[STIX]{x1D713}_{\unicode[STIX]{x1D6FC}}$
to be a convex function which equals
$\exp (x^{\unicode[STIX]{x1D6FC}})-1$
for sufficiently large
$x$
, depending on
$\unicode[STIX]{x1D6FC}$
(for
$\unicode[STIX]{x1D6FC}\geqslant 1$
we can use
$\unicode[STIX]{x1D713}_{\unicode[STIX]{x1D6FC}}(x)=\exp (x^{\unicode[STIX]{x1D6FC}})-1$
for all
$x\geqslant 0$
). More information can be found in [Reference Lindenstrauss and Tzafriri22].
For finite point sets the following is shown in [Reference Bilyk and Markhasin4, Corollary 1.4] (see [Reference Bilyk, Lacey, Parissis and Vagharshakyan2, Theorem 1.4] for the case
$d=2$
). There exists a finite point set
${\mathcal{P}}_{N,d}$
in
$[0,1)^{d}$
such that
$$\begin{eqnarray}\displaystyle & & \displaystyle \Vert D_{{\mathcal{P}}_{N,d}}|\text{exp}(L^{\unicode[STIX]{x1D6FD}})\Vert ~\ll _{d}~N^{-1}(\log N)^{d-1-1/\unicode[STIX]{x1D6FD}}\quad \nonumber\\ \displaystyle & & \displaystyle \qquad \text{for all }N\in \mathbb{N}\setminus \{1\}\text{and for all }\frac{2}{d-1}\leqslant \unicode[STIX]{x1D6FD}<\infty .\nonumber\end{eqnarray}$$
We show a corresponding result for infinite sequences.
Theorem 2.2. There exists an infinite sequence
${\mathcal{S}}_{d}$
in
$[0,1)^{d}$
such that
$$\begin{eqnarray}\displaystyle & & \displaystyle \Vert D_{{\mathcal{S}}_{d}}^{N}|\text{exp}(L^{\unicode[STIX]{x1D6FD}})\Vert ~\ll _{d}~N^{-1}(\log N)^{d-1/\unicode[STIX]{x1D6FD}}\nonumber\\ \displaystyle & & \displaystyle \qquad \text{for all }N\in \mathbb{N}\setminus \{1\}\text{and for all }\frac{2}{d-1}\leqslant \unicode[STIX]{x1D6FD}<\infty .\nonumber\end{eqnarray}$$
From Proposition 2.3 below in conjunction with (1.3) it follows that for every infinite sequence
${\mathcal{S}}_{d}$
in
$[0,1)^{d}$
the discrepancy
$\Vert D_{{\mathcal{S}}_{d}}^{N}|\text{exp}(L^{\unicode[STIX]{x1D6FD}})\Vert$
is at least of order
$(\log N)^{d/2}/N$
for infinitely many
$N\in \mathbb{N}$
. However, a matching lower bound for
$\Vert D_{{\mathcal{S}}_{d}}^{N}|\text{exp}(L^{\unicode[STIX]{x1D6FD}})\Vert$
seems to be presently beyond reach, even for finite point sets as pointed out in [Reference Bilyk and Markhasin4] (see [Reference Bilyk and Markhasin4, Remark after Theorem 1.3] for a short discussion about this problem). There is only one singular result for finite point sets
${\mathcal{P}}_{N,2}$
in dimension
$d=2$
,
$\Vert D_{{\mathcal{P}}_{N,2}}|\text{exp}(L^{\unicode[STIX]{x1D6FD}})\Vert \geqslant c(\log N)^{1-1/\unicode[STIX]{x1D6FD}}/N$
for
$2\leqslant \unicode[STIX]{x1D6FD}<\infty$
and some
$c>0$
, according to [Reference Bilyk, Lacey, Parissis and Vagharshakyan2], for which the upper and lower bound match.
We close this section with some further technical results concerning the exponential Orlicz norm. The reader familiar with this topic may also skip straight to the beginning of the next section.
An equivalent way of stating the exponential Orlicz norm is using the following result, which can be shown using the Taylor series expansion of
$\exp (x)$
and Stirling’s formula.
Proposition 2.3. For any
$\unicode[STIX]{x1D6FD}>0$
, the following equivalence holds
$$\begin{eqnarray}\Vert f|\text{exp}(L^{\unicode[STIX]{x1D6FD}})\Vert \asymp _{d}\sup _{p>1}p^{-1/\unicode[STIX]{x1D6FD}}\Vert f|L_{p}([0,1]^{d})\Vert .\end{eqnarray}$$
Our proof will make use of the Littlewood–Paley inequality, which we state in the following as a lemma.
Lemma 2.4. Let
$1<p<\infty$
. Then for a function
$f:[0,1)^{d}\rightarrow \mathbb{R}$
we have
$$\begin{eqnarray}\Vert f|L_{p}([0,1)^{d})\Vert \ll _{d}\;p^{d/2}\Vert Sf|L_{p}([0,1)^{d})\Vert ,\end{eqnarray}$$
where the square function
$Sf$
is given by
$$\begin{eqnarray}Sf(\boldsymbol{x})=\biggl(\mathop{\sum }_{\boldsymbol{j}\in \mathbb{N}_{-1}^{d}}2^{2|\,\boldsymbol{j}|}\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}|\langle f,h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{2}\unicode[STIX]{x1D712}_{I_{\boldsymbol{j},\boldsymbol{m}}}\biggr)^{1/2}.\end{eqnarray}$$
If furthermore
$f$
is a hyperbolic sum of multiparameter Haar functions, i.e.,
$f\in \text{span}\{h_{\boldsymbol{j},\boldsymbol{m}}:|\,\boldsymbol{j}|=n\}$
for some
$n\in \mathbb{N}$
, then the exponent of
$p$
in (2.4) can be reduced to
$(d-1)/2$
.
An essential tool in the proof of the bound on the exponential Orlicz norm of the discrepancy function is the following hyperbolic Chang–Wilson–Wolff inequality. It relates the exponential Orlicz norm of a function to the
$L_{\infty }$
-norm of the corresponding square function. This inequality was also recently used in [Reference Bilyk and Markhasin4].
Proposition 2.5 (Hyperbolic Chang–Wilson–Wolff inequality).
Assume that
$f$
is a hyperbolic sum of multiparameter Haar functions, i.e.,
$f\in \text{span}\{h_{\boldsymbol{j},\boldsymbol{m}}:|\,\boldsymbol{j}|=n\}$
for some
$n\in \mathbb{N}$
. Then
$$\begin{eqnarray}\Vert f|\text{exp}(L^{2/(d-1)})\Vert \ll \Vert Sf|L_{\infty }([0,1)^{d})\Vert .\end{eqnarray}$$
The proof follows easily from the characterization in Proposition 2.3, Lemma 2.4 and the monotonicity of the
$L_{p}$
-norm.
Below we use the Hyperbolic Chang–Wilson–Wolff inequality to obtain bounds on the
$\exp (L^{2/(d-1)})$
-norm of the discrepancy function. To obtain the general result of Theorem 2.2 we need to interpolate between this result and the
$L_{\infty }$
-norm of the discrepancy function. Concretely, we use the following result [Reference Bilyk and Markhasin4, Proposition 2.4], where also a short proof can be found.
Proposition 2.6. Let
$0<\unicode[STIX]{x1D6FC}<\unicode[STIX]{x1D6FD}<\infty$
. Consider a function
$f\in L_{\infty }([0,1)^{d})$
. If
$f\in \exp (L^{\unicode[STIX]{x1D6FC}})$
, then also
$f\in \exp (L^{\unicode[STIX]{x1D6FD}})$
and we have
$$\begin{eqnarray}\Vert f|\text{exp}(L^{\unicode[STIX]{x1D6FD}})\Vert \ll \Vert f|\text{exp}(L^{\unicode[STIX]{x1D6FC}})\Vert ^{\unicode[STIX]{x1D6FC}/\unicode[STIX]{x1D6FD}}\Vert f|L_{\infty }([0,1)^{d})\Vert ^{1-\unicode[STIX]{x1D6FC}/\unicode[STIX]{x1D6FD}}.\end{eqnarray}$$
3 Besov and Triebel–Lizorkin spaces with dominating mixed smoothness
We are also interested in Besov spaces and Triebel–Lizorkin spaces with dominating mixed smoothness and their quasi-norm of the discrepancy function. The discrepancy of finite point sets in Besov spaces and Triebel–Lizorkin spaces and the corresponding integration orders where considered in [Reference Hinrichs18, Reference Markhasin23–Reference Markhasin26, Reference Triebel40, Reference Triebel41]. These spaces are particularly interesting, since they form natural scales of function spaces including the
$L_{p}$
-spaces and Sobolev spaces of, dominating mixed smoothness. To guide the reader not familiar with these function spaces we remark that the parameter
$s$
in the spaces
$S_{p,q}^{s}B$
and
$S_{p,q}^{s}F$
introduced below is the (dominating mixed) smoothness, the parameter
$p$
denotes integrability and
$q$
is a fine index, see [Reference Tao38]. It is remarkable that in the case
$s>0$
the results do not show the usual difference between the static setting of finite point sets and the dynamic setting of sequences considered here. Instead, the behaviour of the discrepancy is the same, compare (ii) in Theorems 3.1 and 3.2 with the corresponding results for point sets in the above mentioned references.
We follow [Reference Triebel40]. Let
$\mathfrak{S}(\mathbb{R}^{d})$
denote the Schwartz space and
$\mathfrak{S}^{\prime }(\mathbb{R}^{d})$
the space of tempered distributions on
$\mathbb{R}^{d}$
. For
$\unicode[STIX]{x1D711}\in \mathfrak{S}(\mathbb{R}^{d})$
we denote by
${\mathcal{F}}\unicode[STIX]{x1D711}$
the Fourier transform of
$\unicode[STIX]{x1D711}$
and extend it to
$\mathfrak{S}^{\prime }(\mathbb{R}^{d})$
in the usual way. For
$f\in \mathfrak{S}^{\prime }(\mathbb{R}^{d})$
the Fourier transform is given as
${\mathcal{F}}f(\unicode[STIX]{x1D711})=f({\mathcal{F}}\unicode[STIX]{x1D711}),\unicode[STIX]{x1D711}\in \mathfrak{S}(\mathbb{R}^{d})$
. Analogously we proceed with the inverse Fourier transform
${\mathcal{F}}^{-1}$
.
Let
$\unicode[STIX]{x1D711}_{0}\in \mathfrak{S}(\mathbb{R})$
satisfy
$\unicode[STIX]{x1D711}_{0}(x)=1$
for
$|x|\leqslant 1$
and
$\unicode[STIX]{x1D711}_{0}(x)=0$
for
$|x|>\frac{3}{2}$
. Let
$\unicode[STIX]{x1D711}_{k}(x)=\unicode[STIX]{x1D711}_{0}(2^{-k}x)-\unicode[STIX]{x1D711}_{0}(2^{-k+1}x)$
where
$x\in \mathbb{R},k\in \mathbb{N}$
and
$\unicode[STIX]{x1D711}_{\boldsymbol{k}}(\boldsymbol{x})=\unicode[STIX]{x1D711}_{k_{1}}(x_{1})\cdots \unicode[STIX]{x1D711}_{k_{d}}(x_{d})$
where
$\boldsymbol{k}=(k_{1},\ldots ,k_{d})\in \mathbb{N}_{0}^{d}$
and
$\boldsymbol{x}=(x_{1},\ldots ,x_{d})\in \mathbb{R}^{d}$
. The set of functions
$\{\unicode[STIX]{x1D711}_{\boldsymbol{k}}\}$
are a dyadic resolution of unity since
$$\begin{eqnarray}\mathop{\sum }_{\boldsymbol{k}\in \mathbb{N}_{0}^{d}}\unicode[STIX]{x1D711}_{\boldsymbol{k}}(\boldsymbol{x})=1\end{eqnarray}$$
for all
$\boldsymbol{x}\in \mathbb{R}^{d}$
. The functions
${\mathcal{F}}^{-1}(\unicode[STIX]{x1D711}_{\boldsymbol{k}}{\mathcal{F}}f)$
are entire analytic functions for every
$f\in \mathfrak{S}^{\prime }(\mathbb{R}^{d})$
.
Let
$0<p,q\leqslant \infty$
and
$s\in \mathbb{R}$
. The Besov space with dominating mixed smoothness
$S_{p,q}^{s}B(\mathbb{R}^{d})$
consists of all
$f\in \mathfrak{S}^{\prime }(\mathbb{R}^{d})$
with finite quasi-norm
$$\begin{eqnarray}\Vert f|S_{p,q}^{s}B(\mathbb{R}^{d})\Vert =\biggl(\mathop{\sum }_{\boldsymbol{k}\in \mathbb{N}_{0}^{d}}2^{s|\boldsymbol{k}|q}\Vert {\mathcal{F}}^{-1}(\unicode[STIX]{x1D711}_{\boldsymbol{ k}}{\mathcal{F}}f)|L_{p}(\mathbb{R}^{d})\Vert ^{q}\biggr)^{1/q}\end{eqnarray}$$
with the usual modification if
$q=\infty$
.
Let
$\mathfrak{D}([0,1)^{d})$
consist of all complex-valued infinitely differentiable functions on
$\mathbb{R}^{d}$
with compact support in the interior of
$[0,1)^{d}$
and let
$\mathfrak{D}^{\prime }([0,1)^{d})$
be its dual space of all distributions in
$[0,1)^{d}$
. The Besov space with dominating mixed smoothness
$S_{p,q}^{s}B([0,1)^{d})$
consists of all
$f\in \mathfrak{D}^{\prime }([0,1)^{d})$
with finite quasi-norm
$$\begin{eqnarray}\Vert f|S_{p,q}^{s}B([0,1)^{d})\Vert =\inf \{\Vert g|S_{p,q}^{s}B(\mathbb{R}^{d})\Vert :g\in S_{p,q}^{s}B(\mathbb{R}^{d}),g|_{[0,1)^{d}}=f\}.\end{eqnarray}$$
Theorem 3.1. Suppose that
$1\leqslant p,q<\infty$
and
$d\in \mathbb{N}$
.
-
(i) For every infinite sequence
${\mathcal{S}}_{d}$
in
$[0,1)^{d}$
, (3.3)Furthermore, there exists an infinite sequence
$$\begin{eqnarray}\displaystyle & & \displaystyle \displaystyle \Vert D_{{\mathcal{S}}_{d}}^{N}|S_{p,q}^{0}B([0,1)^{d})\Vert \gg _{p,q,d}\,N^{-1}(\log N)^{d/q}\nonumber\\ \displaystyle & & \displaystyle \quad \text{for infinitely many }N\in \mathbb{N}.\end{eqnarray}$$
${\mathcal{S}}_{d}$
in
$[0,1)^{d}$
such that (3.4)
$$\begin{eqnarray}\Vert D_{{\mathcal{S}}_{d}}^{N}|S_{p,q}^{0}B([0,1)^{d})\Vert \ll _{p,q,d}\,N^{-1}(\log N)^{d/q}\quad \text{for all }N\in \mathbb{N}\setminus \{1\}.\end{eqnarray}$$
-
(ii) Suppose further that
$0<s<1/p$
. For every infinite sequence
${\mathcal{S}}_{d}$
in
$[0,1)^{d}$
, (3.5)Furthermore, there exists an infinite sequence
$$\begin{eqnarray}\displaystyle & & \displaystyle \displaystyle \Vert D_{{\mathcal{S}}_{d}}^{N}|S_{p,q}^{s}B([0,1)^{d})\Vert ~\gg _{p,q,s,d}~N^{s-1}(\log N)^{(d-1)/q}\nonumber\\ \displaystyle & & \displaystyle \quad \text{for infinitely many }N\in \mathbb{N}.\end{eqnarray}$$
${\mathcal{S}}_{d}$
in
$[0,1)^{d}$
such that (3.6)
$$\begin{eqnarray}\displaystyle & & \displaystyle \displaystyle \Vert D_{{\mathcal{S}}_{d}}^{N}|S_{p,q}^{s}B([0,1)^{d})\Vert ~\ll _{p,q,s,d}~N^{s-1}(\log N)^{(d-1)/q}\nonumber\\ \displaystyle & & \displaystyle \displaystyle \quad \text{for all }N\in \mathbb{N}\setminus \{1\}.\end{eqnarray}$$
In the case
$d=1$
this result has been recently shown in [Reference Kritzinger19, Theorem 1] which is based on the symmetrized van der Corput sequence.
Let
$0<p<\infty$
,
$0<q\leqslant \infty$
and
$s\in \mathbb{R}$
. The Triebel–Lizorkin space with dominating mixed smoothness
$S_{p,q}^{s}F(\mathbb{R}^{d})$
consists of all
$f\in \mathfrak{S}^{\prime }(\mathbb{R}^{d})$
with finite quasi-norm
$$\begin{eqnarray}\Vert f|S_{p,q}^{s}F(\mathbb{R}^{d})\Vert =\biggl\|\biggl(\mathop{\sum }_{\boldsymbol{k}\in \mathbb{N}_{0}^{d}}2^{s|\boldsymbol{k}|q}|{\mathcal{F}}^{-1}(\unicode[STIX]{x1D711}_{\boldsymbol{ k}}{\mathcal{F}}f)(\cdot )|^{q}\biggr)^{1/q}\Bigg|L_{p}(\mathbb{R}^{d})\biggr\|\end{eqnarray}$$
with the usual modification if
$q=\infty$
.
The Triebel–Lizorkin space with dominating mixed smoothness
$S_{p,q}^{s}F([0,1)^{d})$
consists of all
$f\in \mathfrak{D}^{\prime }([0,1)^{d})$
with finite quasi-norm
$$\begin{eqnarray}\Vert f|S_{p,q}^{s}F([0,1)^{d})\Vert \,=\,\inf \{\Vert g|S_{p,q}^{s}F(\mathbb{R}^{d})\Vert \,:\,g\in S_{p,q}^{s}F(\mathbb{R}^{d}),g|_{[0,1)^{d}}=f\}.\end{eqnarray}$$
Theorem 3.2. Suppose that
$1\leqslant p,q<\infty$
and
$d\in \mathbb{N}$
.
-
(i) For every infinite sequence
${\mathcal{S}}_{d}$
in
$[0,1)^{d}$
, (3.9)Furthermore, there exists an infinite sequence
$$\begin{eqnarray}\displaystyle & & \displaystyle \displaystyle \Vert D_{{\mathcal{S}}_{d}}^{N}|S_{p,q}^{0}F([0,1)^{d})\Vert ~\gg _{p,q,d}~N^{-1}(\log N)^{d/q}\nonumber\\ \displaystyle & & \displaystyle \displaystyle \quad \text{for infinitely many }N\in \mathbb{N}.\end{eqnarray}$$
${\mathcal{S}}_{d}$
in
$[0,1)^{d}$
such that (3.10)
$$\begin{eqnarray}\Vert D_{{\mathcal{S}}_{d}}^{N}|S_{p,q}^{0}F([0,1)^{d})\Vert \ll _{p,q,d}\,N^{-1}(\log N)^{d/q}\quad \text{for all }N\in \mathbb{N}\setminus \{1\}.\end{eqnarray}$$
-
(ii) Suppose further that
$0<s<1/\text{min}(p,q)$
. For every infinite sequence
${\mathcal{S}}_{d}$
in
$[0,1)^{d}$
, (3.11)Furthermore, there exists an infinite sequence
$$\begin{eqnarray}\displaystyle & & \displaystyle \displaystyle \Vert D_{{\mathcal{S}}_{d}}^{N}|S_{p,q}^{s}F([0,1)^{d})\Vert ~\gg _{p,q,s,d}~N^{s-1}(\log N)^{(d-1)/q}\nonumber\\ \displaystyle & & \displaystyle \displaystyle \quad \text{for infinitely many }N\in \mathbb{N}.\end{eqnarray}$$
${\mathcal{S}}_{d}$
in
$[0,1)^{d}$
such that (3.12)
$$\begin{eqnarray}\Vert D_{{\mathcal{S}}_{d}}^{N}|S_{p,q}^{s}F([0,1)^{d})\Vert \geqslant c_{p,q,s,d}\,N^{s-1}(\log N)^{(d-1)/q}\quad \text{for all }N\in \mathbb{N}\setminus \{1\}.\end{eqnarray}$$
For
$0<p<\infty$
the spaces
$S_{p}^{s}W([0,1)^{d})=S_{p,2}^{s}F([0,1)^{d})$
are called Sobolev spaces with dominating mixed smoothness. Thus in the case
$q=2$
the above theorem implies results for Sobolev norms with dominating mixed smoothness.
We close this section with some further technical results about Besov and Triebel–Lizorkin spaces. The spaces
$S_{p,q}^{s}B(\mathbb{R}^{d}),S_{p,q}^{s}F(\mathbb{R}^{d}),\,S_{p,q}^{s}B([0,1)^{d})$
and
$S_{p,q}^{s}F([0,1)^{d})$
are quasi-Banach spaces. The following results will be helpful. The first one is an embedding result (see [Reference Triebel40] or [Reference Markhasin24, Corollary 1.13]), and the second one gives a characterization of the Besov spaces in terms of Haar bases (see [Reference Markhasin24, Theorem 2.11]).
Proposition 3.3. Let
$p,q\in (0,\infty )$
and
$s\in \mathbb{R}$
. Then we have
$$\begin{eqnarray}S_{\max (p,q),q}^{s}B([0,1)^{d}){\hookrightarrow}S_{p,q}^{s}F([0,1)^{d}){\hookrightarrow}S_{ min(p,q),q}^{s}B([0,1)^{d}).\end{eqnarray}$$
Proposition 3.4. Let
$p,q\in (0,\infty )$
,
$1/p-1<s<\min (1/p,1)$
and
$f\in S_{p,q}^{s}B([0,1)^{d})$
. Then
$$\begin{eqnarray}\Vert f|S_{p,q}^{s}B([0,1)^{d})\Vert ^{q}\asymp _{p,q,s,d}\mathop{\sum }_{\boldsymbol{j}\in \mathbb{N}_{-1}^{d}}2^{|\,\boldsymbol{j}|(s-1/p+1)q}\biggl(\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}|\langle f,h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{p}\biggr)^{q/p}.\end{eqnarray}$$
4 Upper bounds
The explicit constructions in Theorems 2.1, 2.2, 3.1 and 3.2 are all the same and are based on linear algebra over the finite field
$\mathbb{F}_{2}$
. In the subsequent section we provide a detailed introduction to the infinite sequences which lead to the optimal discrepancy bounds.
4.1 Digital nets and sequences
Niederreiter introduced the concepts of digital nets and sequences [Reference Niederreiter28] in 1987. A detailed overview of this topic can be found in the books [Reference Dick and Pillichshammer14, Reference Leobacher and Pillichshammer21, Reference Niederreiter29]. Here we restrict ourselves to the dyadic case. Let
$\mathbb{F}_{2}$
be the finite field of order 2 identified with the set
$\{0,1\}$
equipped with arithmetic operations modulo 2.
The digital construction scheme
We begin with the definition of digital nets according to Niederreiter, which we present here in a slightly more general form. For
$n,q,d\in \mathbb{N}$
with
$q\geqslant n$
let
$C_{1},\ldots ,C_{d}\in \mathbb{F}_{2}^{q\times n}$
be
$q\times n$
matrices over
$\mathbb{F}_{2}$
. For
$k\in \{0,\ldots ,2^{n}-1\}$
with dyadic expansion
$k=k_{0}+k_{1}2+\cdots +k_{n-1}2^{n-1}$
, where
$k_{j}\in \{0,1\}$
, we define the dyadic digit vector
$\vec{k}$
as
$\vec{k}=(k_{0},k_{1},\ldots ,k_{n-1})^{\top }\in \mathbb{F}_{2}^{n}$
(the symbol
$\top$
means the transpose of a vector or a matrix; hence
$\vec{k}$
is a column-vector). Then compute
$$\begin{eqnarray}C_{j}\vec{k}=:(x_{j,k,1},x_{j,k,2},\ldots ,x_{j,k,q})^{\top }\quad \text{for }j=1,\ldots ,d,\end{eqnarray}$$
where the matrix vector product is evaluated over
$\mathbb{F}_{2}$
, and put
$$\begin{eqnarray}x_{j,k}=x_{j,k,1}2^{-1}+x_{j,k,2}2^{-2}+\cdots +x_{j,k,q}2^{-q}\in [0,1).\end{eqnarray}$$
The
$k$
th point
$\boldsymbol{x}_{k}$
of the net
${\mathcal{P}}_{2^{n},d}$
is given by
$\boldsymbol{x}_{k}=(x_{1,k},\ldots ,x_{d,k})$
. A net
${\mathcal{P}}_{2^{n},d}$
constructed this way is called a digital net (over
$\mathbb{F}_{2}$
) with generating matrices
$C_{1},\ldots ,C_{d}$
. A digital net consists of
$2^{n}$
elements in
$[0,1)^{d}$
.
Next we recall the definition of digital sequences, which are infinite versions of digital nets. Let
$C_{1},\ldots ,C_{d}\in \mathbb{F}_{2}^{\mathbb{N}\times \mathbb{N}}$
be
$\mathbb{N}\times \mathbb{N}$
matrices over
$\mathbb{F}_{2}$
. For
$C_{j}=(c_{j,k,\ell })_{k,\ell \in \mathbb{N}}$
it is assumed that for each
$\ell \in \mathbb{N}$
there exists a
$K(\ell )\in \mathbb{N}$
such that
$c_{j,k,\ell }=0$
for all
$k>K(\ell )$
. For
$k\in \mathbb{N}_{0}$
with dyadic expansion
$k=k_{0}+k_{1}2+\cdots +k_{m-1}2^{m-1}\in \mathbb{N}_{0}$
, define the infinite dyadic digit vector of
$k$
by
$\vec{k}=(k_{0},k_{1},\ldots ,k_{m-1},0,0,\ldots )^{\top }\in \mathbb{F}_{2}^{\mathbb{N}}$
. Then compute
$$\begin{eqnarray}C_{j}\vec{k}=:(x_{j,k,1},x_{j,k,2},\ldots )^{\top }\quad \text{for }j=1,\ldots ,d,\end{eqnarray}$$
where the matrix vector product is evaluated over
$\mathbb{F}_{2}$
, and put
$$\begin{eqnarray}x_{j,k}=x_{j,k,1}2^{-1}+x_{j,k,2}2^{-2}+\cdots \in [0,1).\end{eqnarray}$$
The
$k$
th point
$\boldsymbol{x}_{k}$
of the sequence
${\mathcal{S}}_{d}$
is given by
$\boldsymbol{x}_{k}=(x_{1,k},\ldots ,x_{d,k})$
. We call a sequence
${\mathcal{S}}_{d}$
constructed this way a digital sequence (over
$\mathbb{F}_{2}$
) with generating matrices
$C_{1},\ldots ,C_{d}$
. Since
$c_{j,k,\ell }=0$
for all
$k$
large enough, the numbers
$x_{j,k}$
are always dyadic rationals, i.e., have a finite dyadic expansion.
Higher-order nets and sequences
The choice of the respective generating matrices is crucial for the distribution quality of digital nets and sequences. The following definitions put some restrictions on
$C_{1},\ldots ,C_{d}$
with the aim to quantify the quality of equidistribution of the digital net or sequence.
Definition 4.1. Let
$n,q,\unicode[STIX]{x1D6FC}\in \mathbb{N}$
with
$q\geqslant \unicode[STIX]{x1D6FC}n$
and let
$t$
be an integer such that
$0\leqslant t\leqslant \unicode[STIX]{x1D6FC}n$
. Let
$C_{1},\ldots ,C_{d}\in \mathbb{F}_{2}^{q\times n}$
. Denote the
$i$
th row vector of the matrix
$C_{j}$
by
$\vec{c}_{j,i}\in \mathbb{F}_{2}^{n}$
. If for all
$1\leqslant i_{j,\unicode[STIX]{x1D708}_{j}}<\cdots <i_{j,1}\leqslant q$
with
$$\begin{eqnarray}\mathop{\sum }_{j=1}^{d}\mathop{\sum }_{l=1}^{\min (\unicode[STIX]{x1D708}_{j},\unicode[STIX]{x1D6FC})}i_{j,l}\leqslant \unicode[STIX]{x1D6FC}n-t\end{eqnarray}$$
the vectors
$$\begin{eqnarray}\vec{c}_{1,i_{1,\unicode[STIX]{x1D708}_{1}}},\ldots ,\vec{c}_{1,i_{1,1}},\ldots ,\vec{c}_{d,i_{d,\unicode[STIX]{x1D708}_{d}}},\ldots ,\vec{c}_{d,i_{d,1}}\end{eqnarray}$$
are linearly independent over
$\mathbb{F}_{2}$
, then the digital net with generating matrices
$C_{1},\ldots ,C_{d}$
is called an order-
$\unicode[STIX]{x1D6FC}$
digital
$(t,n,d)$
-net over
$\mathbb{F}_{2}$
.
Furthermore, we consider digital sequences whose initial segments are order-
$\unicode[STIX]{x1D6FC}$
digital
$(t,n,d)$
-nets over
$\mathbb{F}_{2}$
.
Definition 4.2. Let
$\unicode[STIX]{x1D6FC}\in \mathbb{N}$
and let
$t\geqslant 0$
be an integer. Let
$C_{1},\ldots ,C_{d}\in \mathbb{F}_{2}^{\mathbb{N}\times \mathbb{N}}$
and let
$C_{j,\unicode[STIX]{x1D6FC}n\times n}$
denote the left upper
$\unicode[STIX]{x1D6FC}n\times n$
submatrix of
$C_{j}$
. If for all
$n>t/\unicode[STIX]{x1D6FC}$
the matrices
$C_{1,\unicode[STIX]{x1D6FC}n\times n},\ldots ,C_{d,\unicode[STIX]{x1D6FC}n\times n}$
generate an order-
$\unicode[STIX]{x1D6FC}$
digital
$(t,n,d)$
-net over
$\mathbb{F}_{2}$
, then the digital sequence with generating matrices
$C_{1},\ldots ,C_{d}$
is called an order-
$\unicode[STIX]{x1D6FC}$
digital
$(t,d)$
-sequence over
$\mathbb{F}_{2}$
.
Definition 4.1 shows that if
${\mathcal{P}}_{2^{n},d}$
is an order-
$\unicode[STIX]{x1D6FC}$
digital
$(t,n,d)$
-net, then for any
$t\leqslant t^{\prime }\leqslant \unicode[STIX]{x1D6FC}n$
,
${\mathcal{P}}_{2^{n},d}$
is also an order-
$\unicode[STIX]{x1D6FC}$
digital
$(t^{\prime },n,d)$
-net. An analogous result also applies to higher-order digital sequences.
We point out that a digital net can be an order-
$\unicode[STIX]{x1D6FC}$
digital
$(t,n,d)$
-net over
$\mathbb{F}_{2}$
and at the same time an order-
$\unicode[STIX]{x1D6FC}^{\prime }$
digital
$(t^{\prime },n,d)$
-net over
$\mathbb{F}_{2}$
for
$\unicode[STIX]{x1D6FC}^{\prime }\not =\unicode[STIX]{x1D6FC}$
. The quality parameter
$t$
may depend on
$\unicode[STIX]{x1D6FC}$
(i.e.,
$t=t(\unicode[STIX]{x1D6FC})$
). The same is true for digital sequences. In particular, [Reference Dick10, Theorem 4.10] implies that an order-
$\unicode[STIX]{x1D6FC}$
digital
$(t,n,d)$
-net is an order-
$\unicode[STIX]{x1D6FC}^{\prime }$
digital
$(t^{\prime },n,d)$
-net for all
$1\leqslant \unicode[STIX]{x1D6FC}^{\prime }\leqslant \unicode[STIX]{x1D6FC}$
with
$$\begin{eqnarray}t^{\prime }=\lceil t\unicode[STIX]{x1D6FC}^{\prime }/\unicode[STIX]{x1D6FC}\rceil \leqslant t.\end{eqnarray}$$
The same result applies to order-
$\unicode[STIX]{x1D6FC}$
digital
$(t,d)$
-sequences which are also order-
$\unicode[STIX]{x1D6FC}^{\prime }$
digital
$(t^{\prime },d)$
-sequences for
$1\leqslant \unicode[STIX]{x1D6FC}^{\prime }\leqslant \unicode[STIX]{x1D6FC}$
and
$t^{\prime }$
as above. In other words,
$t(\unicode[STIX]{x1D6FC}^{\prime })=\lceil t(\unicode[STIX]{x1D6FC})\unicode[STIX]{x1D6FC}^{\prime }/\unicode[STIX]{x1D6FC}\rceil$
for all
$1\leqslant \unicode[STIX]{x1D6FC}^{\prime }\leqslant \unicode[STIX]{x1D6FC}$
. For more details consult [Reference Dick9, Reference Dick10] or [Reference Dick and Pillichshammer14, Ch. 15].
Higher-order digital nets and sequences have also a geometrical interpretation. Roughly speaking the definitions imply that special intervals or unions of intervals of prescribed volume contain the correct share of points with respect to a perfect uniform distribution. See [Reference Dick and Pillichshammer14, Reference Niederreiter29] for the classical case
$\unicode[STIX]{x1D6FC}=1$
and [Reference Dick, Baldeaux, L’Ecuyer and Owen12] for general
$\unicode[STIX]{x1D6FC}$
. See also Lemma 4.4 below.
Explicit constructions of order-2 digital sequences
Explicit constructions of order-
$\unicode[STIX]{x1D6FC}$
digital nets and sequences have been provided by Dick [Reference Dick9, Reference Dick10]. For our purposes it suffices to consider only
$\unicode[STIX]{x1D6FC}=2$
.
We start with generating matrices
$C_{1},\ldots ,C_{2d}$
of a digital net or sequence. Let
$\vec{c}_{j,k}$
denote the
$k$
th row of
$C_{j}$
. We now define matrices
$E_{1},\ldots ,E_{d}$
, where the
$k$
th row of
$E_{j}$
is given by
$\vec{e}_{j,k}$
, in the following way. For all
$j\in \{1,2,\ldots ,d\}$
,
$u\in \mathbb{N}_{0}$
and
$v\in \{1,2\}$
let
$$\begin{eqnarray}\vec{e}_{j,2u+v}=\vec{c}_{2(j-1)+v,u+1}.\end{eqnarray}$$
We illustrate the construction for
$d=1$
. In this case we have
$$\begin{eqnarray}C_{1}=\left(\begin{array}{@{}c@{}}\vec{c}_{1,1}\\ \vec{c}_{1,2}\\ \vdots \end{array}\right),\qquad C_{2}=\left(\begin{array}{@{}c@{}}\vec{c}_{2,1}\\ \vec{c}_{2,2}\\ \vdots \end{array}\right)\Rightarrow E_{1}=\left(\begin{array}{@{}c@{}}\vec{c}_{1,1}\\ \vec{c}_{2,1}\\ \vec{c}_{1,2}\\ \vec{c}_{2,2}\\ \vdots \end{array}\right).\end{eqnarray}$$
This procedure is called interlacing (in this case the so-called interlacing factor is
$2$
).
Recall that above we assumed that
$c_{j,k,\ell }=0$
for all
$k>K(\ell )$
. Let
$E_{j}=(e_{j,k,\ell })_{k,\ell \in \mathbb{N}}$
. Then the construction yields that
$e_{j,k,\ell }=0$
for all
$k>2K(\ell )$
.
From [Reference Dick9, Theorems 4.11 and 4.12] we obtain the following result.
Proposition 4.3. If
$C_{1},\ldots ,C_{2d}\in \mathbb{F}_{2}^{\mathbb{N}\times \mathbb{N}}$
generate an order-1 digital
$(t^{\prime },2d)$
-sequence over
$\mathbb{F}_{2}$
, then
$E_{1},\ldots ,E_{d}\in \mathbb{F}_{2}^{\mathbb{N}\times \mathbb{N}}$
generate an order-2 digital
$(t,d)$
-sequence over
$\mathbb{F}_{2}$
with
$$\begin{eqnarray}t=2t^{\prime }+d.\end{eqnarray}$$
Examples of explicit constructions of suitable generating matrices over
$\mathbb{F}_{2}$
were obtained by Sobol’ [Reference Sobol’37], Niederreiter [Reference Niederreiter28, Reference Niederreiter29], Niederreiter and Xing [Reference Niederreiter and Xing30] and others. An overview is presented in [Reference Dick and Pillichshammer14, Ch. 8]. Any of these constructions is sufficient for our purpose, however, for completeness, we briefly describe a special case of Tezuka’s construction [Reference Tezuka39], which is a generalization of Sobol’s construction [Reference Sobol’37] and Niederreiter’s construction [Reference Niederreiter28] of the generating matrices.
We explain how to construct the entries
$c_{j,k,\ell }\in \mathbb{F}_{2}$
of the generator matrices
$C_{j}=(c_{j,k,\ell })_{k,\ell \geqslant 1}$
for
$j=1,2,\ldots ,d^{\prime }$
(for our purpose
$d^{\prime }=2d$
). To this end choose the polynomials
$p_{j}\in \mathbb{F}_{2}[x]$
for
$j=1,\ldots ,d^{\prime }$
to be the
$j$
th irreducible polynomial in a list of irreducible polynomials over
$\mathbb{F}_{2}$
that is sorted in increasing order according to their degree
$e_{j}=\deg (p_{j})$
, that is,
$e_{1}\leqslant e_{2}\leqslant \cdots \leqslant e_{d^{\prime }}$
(the ordering of polynomials with the same degree is irrelevant).
Let
$j\in \{1,\ldots ,d^{\prime }\}$
and
$k\in \mathbb{N}$
. Take
$i-1$
and
$z$
to be respectively the main term and remainder when we divide
$k-1$
by
$e_{j}$
, so that
$k-1=(i-1)e_{j}+z$
, with
$0\leqslant z<e_{j}$
. Now consider the Laurent series expansion
$$\begin{eqnarray}\frac{x^{e_{j}-z-1}}{p_{j}(x)^{i}}=\mathop{\sum }_{\ell =1}^{\infty }a_{\ell }(i,j,z)x^{-\ell }\in \mathbb{F}_{2}((x^{-1})).\end{eqnarray}$$
For
$\ell \in \mathbb{N}$
we set
$$\begin{eqnarray}c_{j,k,\ell }=a_{\ell }(i,j,z).\end{eqnarray}$$
Every digital sequence with generating matrices
$C_{j}=(c_{j,k,\ell })_{k,\ell \geqslant 1}$
for
$j=1,2,\ldots ,d^{\prime }$
found in this way is a special instance of a Sobol’ sequence which in turn is a special instance of so-called generalized Niederreiter sequences (see [Reference Tezuka39, (3)]). Note that in the construction above we always have
$c_{j,k,\ell }=0$
for all
$k>\ell$
. The
$t$
-value for these sequences is known to be
$t=\sum _{j=1}^{d^{\prime }}(e_{j}-1)$
, see [Reference Niederreiter29, Ch. 4.5] for the case of Niederreiter sequences.
Remark.
Let
$C_{1},\ldots ,C_{2d}$
be
$\mathbb{N}\times \mathbb{N}$
matrices which are constructed according to Tezuka’s method as described above. Let
$E_{1},\ldots ,E_{d}$
be the generator matrices of the corresponding order-2 digital sequence. Then we always have
$e_{j,k,\ell }=0$
for all
$k>2\ell$
, where
$e_{j,k,\ell }$
is the entry in row
$k$
and column
$\ell$
of the matrix
$E_{j}$
.
We point out that the explicit construction of the order-2 digital
$(t,d)$
-sequences
${\mathcal{S}}_{d}$
shown above, with generating matrices
$E_{i}=(e_{i,k,\ell })_{k,\ell \geqslant 1}$
for which
$e_{i,k,\ell }=0$
for all
$k>2\ell$
and for all
$i\in \{1,2,\ldots ,d\}$
, does not depend on the parameters
$p,q,s$
in Theorems 2.2, 3.1 and 3.2. Our explicit construction, which is based on Tezuka’s construction and the interlacing of the generating matrices, is also extensible in the dimension, i.e., if we have constructed the sequence
${\mathcal{S}}_{d}$
, we can add one more coordinate to obtain the sequence
${\mathcal{S}}_{d+1}$
. This means that we can define a sequence
${\mathcal{S}}_{\infty }$
of points in
$[0,1)^{\mathbb{N}}$
and obtain the sequence
${\mathcal{S}}_{d}$
,
$d\in \mathbb{N}$
, by projecting
${\mathcal{S}}_{\infty }$
to the first
$d$
coordinates (cf. [Reference Dick11]).
4.2 Some auxiliary results
A connection between higher-order digital nets over
$\mathbb{F}_{2}$
and dyadic intervals is given by the following result (see [Reference Dick, Hinrichs, Markhasin and Pillichshammer13, Lemma 3.1]).
Lemma 4.4. Let
${\mathcal{P}}_{2^{n},d}$
be an order-
$\unicode[STIX]{x1D6FC}$
digital
$(t,n,d)$
-net over
$\mathbb{F}_{2}$
. Then every dyadic interval of order
$n-\lceil t/\unicode[STIX]{x1D6FC}\rceil$
contains at most
$2^{\lceil t/\unicode[STIX]{x1D6FC}\rceil }$
points of
${\mathcal{P}}_{2^{n},d}$
.
Proof. As already mentioned, every order-
$\unicode[STIX]{x1D6FC}$
digital
$(t,n,d)$
-net over
$\mathbb{F}_{2}$
is an order-1 digital
$(\lceil t/\unicode[STIX]{x1D6FC}\rceil ,n,d)$
-net over
$\mathbb{F}_{2}$
. Then every dyadic interval of order
$n-\lceil t/\unicode[STIX]{x1D6FC}\rceil$
contains exactly
$2^{\lceil t/\unicode[STIX]{x1D6FC}\rceil }$
points of
${\mathcal{P}}_{2^{n},d}$
(see [Reference Dick and Pillichshammer14, Reference Niederreiter29]).◻
The following lemma, implicitly shown in [Reference Dick, Hinrichs, Markhasin and Pillichshammer13], is utmost important for our analysis. Throughout the paper let
$\text{ld}\,$
denote the logarithm in base
$2$
, i.e.,
$\text{ld}\,x=(\log x)/\text{log}\,2$
.
Lemma 4.5. Let
${\mathcal{S}}_{d}$
be an order-2 digital
$(t,d)$
-sequence over
$\mathbb{F}_{2}$
with generating matrices
$E_{i}=(e_{i,k,\ell })_{k,\ell \geqslant 1}$
for which
$e_{i,k,\ell }=0$
for all
$k>2\ell$
and for all
$i\in \{1,2,\ldots ,d\}$
and let
${\mathcal{P}}_{N,d}$
be the point set consisting of the first
$N$
elements of
${\mathcal{S}}_{d}$
.
-
(i) If
$|\,\boldsymbol{j}|+t/2\geqslant \text{ld}\,N$
we have: if
$I_{\boldsymbol{j},\boldsymbol{m}}$
contains points of
${\mathcal{P}}_{N,d}$
, then At least
$$\begin{eqnarray}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{ j},\boldsymbol{m}}\rangle |\ll 2^{t/2}\,N^{-1}2^{-|\,\boldsymbol{j}|}.\end{eqnarray}$$
$2^{|\,\boldsymbol{j}|}-N$
such intervals contain no points of
${\mathcal{P}}_{N,d}$
and in such cases we have
$$\begin{eqnarray}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{ j},\boldsymbol{m}}\rangle |\ll 2^{-2|\,\boldsymbol{j}|}.\end{eqnarray}$$
-
(ii) If
$|\,\boldsymbol{j}|+t/2<\text{ld}\,N$
, more precisely
$n_{\unicode[STIX]{x1D707}}\leqslant |\,\boldsymbol{j}|+t/2<n_{\unicode[STIX]{x1D707}+1}$
, where
$N=2^{n_{r}}+\cdots +2^{n_{1}}$
with
$n_{r}>\cdots >n_{1}\geqslant 0$
, then
$$\begin{eqnarray}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{ j},\boldsymbol{m}}\rangle |\ll 2^{t}\,N^{-1}(2^{-|\,\boldsymbol{j}|}+(2n_{\unicode[STIX]{x1D707}+1}-t-2|\,\boldsymbol{j}|)^{d-1}2^{-n_{\unicode[STIX]{x1D707}+1}}).\end{eqnarray}$$
Proof. This is [Reference Dick, Hinrichs, Markhasin and Pillichshammer13, equations (13), (14) and (16)]. ◻
Lemma 4.6. Let
$r\in \mathbb{N}_{0}$
and
$s\in \mathbb{N}$
. Then
$$\begin{eqnarray}\#\{(a_{1},\ldots ,a_{s})\in \mathbb{N}_{0}^{s}:a_{1}+\cdots +a_{s}=r\}\leqslant (r+1)^{s-1}.\end{eqnarray}$$
For a proof of this result we refer to [Reference Dick and Pillichshammer14, Proof of Lemma 16.26].
Lemma 4.7. Let
$K\in \mathbb{N}$
,
$A>1$
and
$q,s\geqslant 0$
. Then we have
$$\begin{eqnarray}\mathop{\sum }_{r=0}^{K-1}A^{r}(K-r)^{q}r^{s}\ll A^{K}\,K^{s},\end{eqnarray}$$
where the implicit constant is independent of
$K$
.
For a proof we refer to [Reference Markhasin26, Lemma 5.2].
The subsequent two lemmas are required in order to estimate the Haar coefficients of the discrepancy function. The first one is a special case of [Reference Markhasin25, Lemma 5.1].
Lemma 4.8. Let
$f(\boldsymbol{x})=x_{1}\cdots x_{d}$
for
$\boldsymbol{x}=(x_{1},\ldots ,x_{d})\in [0,1)^{d}$
. Let
$\,\boldsymbol{j}\in \mathbb{N}_{-1}^{d}$
and
$\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}$
. Then
$|\langle f,h_{\boldsymbol{j},\boldsymbol{m}}\rangle |\asymp 2^{-2|\,\boldsymbol{j}|}$
.
The next lemma is a special case of [Reference Markhasin25, Lemma 5.2].
Lemma 4.9. Let
$\boldsymbol{z}=(z_{1},\ldots ,z_{d})\in [0,1)^{d}$
and
$g(\boldsymbol{x})=\unicode[STIX]{x1D712}_{[\mathbf{0},\boldsymbol{x})}(\boldsymbol{z})$
for
$\boldsymbol{x}=(x_{1},\ldots ,x_{d})\in [0,1)^{d}$
. Let
$\,\boldsymbol{j}\in \mathbb{N}_{-1}^{d}$
and
$\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}$
. Then
$\langle g,h_{\boldsymbol{j},\boldsymbol{m}}\rangle =0$
if
$\boldsymbol{z}$
is not contained in the interior of the dyadic interval
$I_{\boldsymbol{j},\boldsymbol{m}}$
. If
$\boldsymbol{z}$
is contained in the interior of
$I_{\boldsymbol{j},\boldsymbol{m}}$
then
$|\langle g,h_{\boldsymbol{j},\boldsymbol{m}}\rangle |\ll 2^{-|\,\boldsymbol{j}|}$
.
In the case of finite digital nets over
$\mathbb{F}_{2}$
the number of elements is a fixed power of 2, e.g.,
$N=2^{m}$
. For infinite digital sequences one needs discrepancy bounds for general
$N\in \mathbb{N}$
. The general plan is to split the initial
$N$
-element segments of the sequence into parts such that each part has a digital net structure (this method was also used in the proof of Lemma 4.5 in [Reference Dick, Hinrichs, Markhasin and Pillichshammer13]). These parts are handled with methods developed for finite point sets. A similar approach was also used in [Reference Dick11, Reference Dick and Pillichshammer15], however, the major challenge in these papers is the handling of the interactions between digital nets of different size, which arises from squaring the discrepancy function. This approach leads to a complicated proof for the
$L_{2}$
discrepancy in [Reference Dick and Pillichshammer15] and even non-optimal results for the
$L_{p}$
discrepancy for general
$N$
in [Reference Dick11]. We overcome this problem by using a Haar series expansion of the discrepancy function which leads to a simpler bound on the various norms of the discrepancy function. See also [Reference Bilyk and Markhasin4, Reference Dick, Hinrichs, Markhasin and Pillichshammer13].
4.3 The proof of the upper bound in Theorem 2.1
Proof of equation (2.3) in Theorem 2.1.
The proof uses ideas from [Reference Bilyk and Markhasin4]. Let
$N=2^{n_{r}}+\cdots +2^{n_{1}}$
with
$n_{r}>\cdots >n_{1}\geqslant 0$
and let
${\mathcal{P}}_{N,d}$
be the point set which consists of the first
$N$
terms of
${\mathcal{S}}_{d}$
. We need to prove that
$$\begin{eqnarray}\unicode[STIX]{x1D706}_{d}(U)^{-1}\mathop{\sum }_{\boldsymbol{j}\in \mathbb{N}_{0}^{d}}2^{|\,\boldsymbol{j}|}\mathop{\sum }_{\substack{ \boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}} \\ I_{\boldsymbol{j},\boldsymbol{m}}\subseteq U}}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{ j},\boldsymbol{m}}\rangle |^{2}~\ll _{d}~2^{2t}N^{-2}(\log N)^{d}.\end{eqnarray}$$
It is clear that for each
$U\subseteq [0,1)^{d}$
and
$\,\boldsymbol{j}\in \mathbb{N}_{0}^{d}$
there are at most
$2^{|\,\boldsymbol{j}|}\unicode[STIX]{x1D706}_{d}(U)$
values of
$\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}$
such that
$I_{\boldsymbol{j},\boldsymbol{m}}\subseteq U$
.
We split the above sum over
$\,\boldsymbol{j}\in \mathbb{N}_{0}^{d}$
into three parts according to the size of
$|\,\boldsymbol{j}|$
.
First we consider those
$\,\boldsymbol{j}$
for which
$\text{ld}\,N-t/2\leqslant |\,\boldsymbol{j}|<\text{ld}\,N$
. From Lemma 4.5 we know that
$$\begin{eqnarray}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{ j},\boldsymbol{m}}\rangle |\ll 2^{t/2}\,N^{-1}2^{-|\,\boldsymbol{j}|}\end{eqnarray}$$
if
$I_{\boldsymbol{j},\boldsymbol{m}}$
contains points of
${\mathcal{P}}_{N,d}$
and
$$\begin{eqnarray}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{ j},\boldsymbol{m}}\rangle |\ll 2^{-2|\,\boldsymbol{j}|}\end{eqnarray}$$
otherwise. With these estimates we obtain
$$\begin{eqnarray}\displaystyle & & \displaystyle \unicode[STIX]{x1D706}_{d}(U)^{-1}\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{0}^{d} \\ \text{ld}\,N-t/2\leqslant |\,\boldsymbol{j}|<\text{ld}\,N}}2^{|\,\boldsymbol{j}|}\mathop{\sum }_{\substack{ \boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}} \\ I_{\boldsymbol{j},\boldsymbol{m}}\subseteq U}}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{2}\nonumber\\ \displaystyle & & \displaystyle \qquad \ll \unicode[STIX]{x1D706}_{d}(U)^{-1}\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{0}^{d} \\ \text{ld}\,N-t/2\leqslant |\,\boldsymbol{j}|<\text{ld}\,N}}\nonumber\\ \displaystyle & & \displaystyle \qquad \quad \times \,2^{|\,\boldsymbol{j}|}\biggl(\mathop{\sum }_{\substack{ \boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}} \\ I_{\boldsymbol{j},\boldsymbol{m}}\subseteq U \\ I_{\boldsymbol{j},\boldsymbol{m}}\cap {\mathcal{P}}_{N,d}\not =\emptyset }}2^{t}\,N^{-2}2^{-2|\,\boldsymbol{j}|}+\mathop{\sum }_{\substack{ \boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}} \\ I_{\boldsymbol{j},\boldsymbol{m}}\subseteq U \\ I_{\boldsymbol{j},\boldsymbol{m}}\cap {\mathcal{P}}_{N,d}=\emptyset }}2^{-4|\,\boldsymbol{j}|}\biggr)\nonumber\\ \displaystyle & & \displaystyle \qquad \leqslant \unicode[STIX]{x1D706}_{d}(U)^{-1}\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{0}^{d} \\ \text{ld}\,N-t/2\leqslant |\,\boldsymbol{j}|<\text{ld}\,N}}2^{|\,\boldsymbol{j}|}\max (2^{t}\,N^{-2}2^{-2|\,\boldsymbol{j}|},2^{-4|\,\boldsymbol{j}|})2^{|\,\boldsymbol{j}|}\unicode[STIX]{x1D706}_{d}(U)\nonumber\\ \displaystyle & & \displaystyle \qquad \ll 2^{t}\,N^{-2}\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{0}^{d} \\ \text{ld}\,N-t/2\leqslant |\,\boldsymbol{j}|<\text{ld}\,N}}1\ll 2^{t}\,N^{-2}\mathop{\sum }_{k<\text{ld}\,N}k^{d-1}\ll 2^{t}\,N^{-2}(\log N)^{d}.\nonumber\end{eqnarray}$$
Now we consider those
$\,\boldsymbol{j}\in \mathbb{N}_{0}^{d}$
for which
$|\,\boldsymbol{j}|<\text{ld}\,N-t/2$
. More precisely assume that we have
$$\begin{eqnarray}n_{\unicode[STIX]{x1D707}}\leqslant |\,\boldsymbol{j}|+t/2<n_{\unicode[STIX]{x1D707}+1}\end{eqnarray}$$
for some
$\unicode[STIX]{x1D707}\in \{0,1,\ldots ,r\}$
, where we set
$n_{0}=0$
and
$n_{r+1}=\text{ld}\,N$
. From Lemma 4.5 we know that
$$\begin{eqnarray}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{ j},\boldsymbol{m}}\rangle |\ll 2^{t}\,N^{-1}(2^{-|\,\boldsymbol{j}|}+(2n_{\unicode[STIX]{x1D707}+1}-t-2|\,\boldsymbol{j}|)^{d-1}2^{-n_{\unicode[STIX]{x1D707}+1}}).\end{eqnarray}$$
Then we have
$$\begin{eqnarray}\displaystyle & & \displaystyle \unicode[STIX]{x1D706}_{d}(U)^{-1}\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{0}^{d} \\ |\,\boldsymbol{j}|<\text{ld}\,N-t/2}}2^{|\,\boldsymbol{j}|}\mathop{\sum }_{\substack{ \boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}} \\ I_{\boldsymbol{j},\boldsymbol{m}}\subseteq U}}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{2}\nonumber\\ \displaystyle & & \displaystyle \qquad \ll \mathop{\sum }_{\unicode[STIX]{x1D707}=0}^{r}\!\!\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{0}^{d} \\ n_{\unicode[STIX]{x1D707}}\leqslant |\,\boldsymbol{j}|+t/2<n_{\unicode[STIX]{x1D707}+1}}}\!\!2^{2|\,\boldsymbol{j}|}\,2^{2t}\,N^{-2}(2^{-|\,\boldsymbol{j}|}+(2n_{\unicode[STIX]{x1D707}+1}-t-2|\,\boldsymbol{j}|)^{d-1}2^{-n_{\unicode[STIX]{x1D707}+1}})^{2}.\nonumber\end{eqnarray}$$
From here we can proceed in the same way as in [Reference Dick, Hinrichs, Markhasin and Pillichshammer13, Proof of Theorem 2.2]. This way we obtain
$$\begin{eqnarray}\unicode[STIX]{x1D706}_{d}(U)^{-1}\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{0}^{d} \\ |\,\boldsymbol{j}|<\text{ld}\,N-t/2}}2^{|\,\boldsymbol{j}|}\mathop{\sum }_{\substack{ \boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}} \\ I_{\boldsymbol{j},\boldsymbol{m}}\subseteq U}}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{ j},\boldsymbol{m}}\rangle |^{2}\ll 2^{2t}\,N^{-2}(\log N)^{d}.\end{eqnarray}$$
Finally we need to study the case
$|\,\boldsymbol{j}|\geqslant \text{ld}\,N$
which is the most involved one among the three cases considered. As in [Reference Bilyk and Markhasin4] we treat the counting part and the volume part of the discrepancy function separately. For the volume part
$L(\boldsymbol{x})=x_{1}\cdots x_{d}$
it is easy to show that
$|\langle L,h_{\boldsymbol{j},\boldsymbol{m}}\rangle |\asymp 2^{-2|\,\boldsymbol{j}|}$
. Thus we have
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D706}_{d}(U)^{-1}\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{0}^{d} \\ |\,\boldsymbol{j}|\geqslant \text{ld}\,N}}2^{|\,\boldsymbol{j}|}\mathop{\sum }_{\substack{ \boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}} \\ I_{\boldsymbol{j},\boldsymbol{m}}\subseteq U}}|\langle L,h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{2} & \ll & \displaystyle \mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{0}^{d} \\ |\,\boldsymbol{j}|\geqslant \text{ld}\,N}}2^{-2|\,\boldsymbol{j}|}\nonumber\\ \displaystyle & \ll & \displaystyle \mathop{\sum }_{k\geqslant \text{ld}\,N}k^{d-1}\,2^{-2k}\ll N^{-2}(\log N)^{d-1}.\nonumber\end{eqnarray}$$
Let
$C(\boldsymbol{x})=N^{-1}\sum _{\boldsymbol{z}\in {\mathcal{P}}_{N,d}}\unicode[STIX]{x1D712}_{[\mathbf{0},\boldsymbol{x})}(\boldsymbol{z})$
be the counting part of the discrepancy function.
Let
${\mathcal{J}}$
be the family of all dyadic intervals
$I_{\boldsymbol{j},\boldsymbol{m}}\subseteq U$
with
$|\,\boldsymbol{j}|\geqslant \text{ld}\,N$
such that
$\langle C,h_{\boldsymbol{j},\boldsymbol{m}}\rangle \not =0$
. Consider the subfamily
$\widetilde{{\mathcal{J}}}\subseteq {\mathcal{J}}$
of all maximal (with respect to inclusion) dyadic intervals in
${\mathcal{J}}$
. We show that we have
$$\begin{eqnarray}\mathop{\sum }_{I_{\boldsymbol{j},\boldsymbol{m}}\in \widetilde{{\mathcal{J}}}}\unicode[STIX]{x1D706}_{d}(I_{\boldsymbol{j},\boldsymbol{m}})\ll (\log N)^{d-1}\unicode[STIX]{x1D706}_{d}(U).\end{eqnarray}$$
To see this consider an interval
$I_{\boldsymbol{j},\boldsymbol{m}}\in {\mathcal{J}}$
. The condition
$\langle C,h_{\boldsymbol{j},\boldsymbol{m}}\rangle \not =0$
implies that the interior of
$I_{\boldsymbol{j},\boldsymbol{m}}$
contains at least one point of
${\mathcal{P}}_{N,d}$
. Now we need the assumption that the generating matrices
$E_{i}=(e_{i,k,\ell })_{k,\ell \geqslant 1}$
are chosen such that
$e_{i,k,\ell }=0$
for all
$k>2\ell$
and all
$i\in \{1,2,\ldots ,d\}$
. This implies that the points of
${\mathcal{P}}_{N,d}$
have binary coordinates of length
$2n$
(where
$n=\lfloor \text{ld}\,N\rfloor +1$
). Since the interior of
$I_{\boldsymbol{j},\boldsymbol{m}}$
contains at least one point of
${\mathcal{P}}_{N,d}$
we obtain that each side of
$I_{\boldsymbol{j},\boldsymbol{m}}$
has length at least
$2^{-2n}$
, i.e.,
$j_{i}\in \{0,1,\ldots ,2n\}$
for all
$i\in \{1,2,\ldots ,d\}$
.
Now fix
$r_{1},r_{2},\ldots ,r_{d-1}\in \{0,1,\ldots ,2n\}$
and consider the family
$\widetilde{{\mathcal{J}}}_{r_{1},\ldots ,r_{d-1}}\subseteq \widetilde{{\mathcal{J}}}$
of those intervals
$I_{\boldsymbol{j},\boldsymbol{m}}\in {\mathcal{J}}$
for which
$j_{i}=r_{i}$
for
$i\in \{1,2,\ldots ,d-1\}$
(i.e., with fixed lengths of their first
$d-1$
sides). If two of these intervals have a non-empty intersection, then their first
$d-1$
sides have to coincide and hence one would have to be contained in the other. This however contradicts the maximality of the intervals in
$\widetilde{{\mathcal{J}}}$
. Thus we have shown that the intervals in
$\widetilde{{\mathcal{J}}}_{r_{1},\ldots ,r_{d-1}}$
are pairwise disjoint. From this observation we find that
$$\begin{eqnarray}\displaystyle \mathop{\sum }_{I_{\boldsymbol{j},\boldsymbol{m}}\in \widetilde{{\mathcal{J}}}}\unicode[STIX]{x1D706}_{d}(I_{\boldsymbol{j},\boldsymbol{m}}) & = & \displaystyle \mathop{\sum }_{r_{1},\ldots ,r_{d-1}=0}^{2n}\mathop{\sum }_{I_{\boldsymbol{j},\boldsymbol{m}}\in \widetilde{{\mathcal{J}}}_{r_{1},\ldots ,r_{d-1}}}\unicode[STIX]{x1D706}_{d}(I_{\boldsymbol{j},\boldsymbol{m}})\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \mathop{\sum }_{r_{1},\ldots ,r_{d-1}=0}^{2n}\unicode[STIX]{x1D706}_{d}(U)\ll (2n)^{d-1}\unicode[STIX]{x1D706}_{d}(U),\nonumber\end{eqnarray}$$
which implies (4.5).
For dyadic intervals
$J$
, we define
$$\begin{eqnarray}C^{J}(\boldsymbol{x})=\mathop{\sum }_{\boldsymbol{z}\in {\mathcal{P}}_{N,d}\cap J}\unicode[STIX]{x1D712}_{[\mathbf{0},\boldsymbol{x})}(\boldsymbol{z}).\end{eqnarray}$$
It is easy to see that
$\langle C,h_{\boldsymbol{j},\boldsymbol{m}}\rangle =\langle C^{J},h_{\boldsymbol{j},\boldsymbol{m}}\rangle$
whenever
$I_{\boldsymbol{j},\boldsymbol{m}}\subseteq J$
. From
$n=\lfloor \text{ld}\,N\rfloor +1$
we know that
$N<2^{n}$
. Then the point set
${\mathcal{P}}_{N,d}$
of the first
$N$
elements of
${\mathcal{S}}_{d}$
is a subset of
${\mathcal{P}}_{2^{n},d}$
consisting of the first
$2^{n}$
elements of
${\mathcal{S}}_{d}$
. From the construction of
${\mathcal{S}}_{d}$
it follows that
${\mathcal{P}}_{2^{n},d}$
is an order-2 digital
$(t,n,d)$
-net over
$\mathbb{F}_{2}$
. Therefore, according to Lemma 4.4, in an interval
$I_{\boldsymbol{j},\boldsymbol{m}}$
there are at most
$2^{\lceil t/2\rceil }$
points of
${\mathcal{P}}_{2^{n},d}$
and hence there are at most
$2^{\lceil t/2\rceil }$
points of
${\mathcal{P}}_{N,d}$
in
$I_{\boldsymbol{j},\boldsymbol{m}}$
. Therefore, for any
$J\in \widetilde{{\mathcal{J}}}$
we have
$0\leqslant C^{J}(\boldsymbol{x})\leqslant 2^{\lceil t/2\rceil }N^{-1}$
, which implies
$$\begin{eqnarray}\Vert C^{J}\Vert _{L_{2}(J)}\leqslant \Vert 2^{\lceil t/2\rceil }N^{-1}\Vert _{L_{2}(J)}\leqslant N^{-1}2^{\lceil t/2\rceil }\unicode[STIX]{x1D706}_{d}(J)^{1/2}.\end{eqnarray}$$
Using the orthogonality of Haar functions, Bessel’s inequality, (4.5), and (4.6), we obtain
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D706}_{d}(U)^{-1}\mathop{\sum }_{I_{\boldsymbol{j},\boldsymbol{m}}\in {\mathcal{J}}}2^{|\,\boldsymbol{j}|}|\langle C,h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{2} & {\leqslant} & \displaystyle \unicode[STIX]{x1D706}_{d}(U)^{-1}\mathop{\sum }_{J\in \widetilde{{\mathcal{J}}}}\mathop{\sum }_{I_{\boldsymbol{j},\boldsymbol{m}}\subseteq J}2^{|\,\boldsymbol{j}|}|\langle C^{J},h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{2}\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \unicode[STIX]{x1D706}_{d}(U)^{-1}\mathop{\sum }_{J\in \widetilde{{\mathcal{J}}}}\Vert C^{J}\Vert _{L_{2}(J)}^{2}\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \unicode[STIX]{x1D706}_{d}(U)^{-1}\,2^{t+1}\,N^{-2}\mathop{\sum }_{J\in \widetilde{{\mathcal{J}}}}\unicode[STIX]{x1D706}_{d}(J)\nonumber\\ \displaystyle & \ll & \displaystyle 2^{t+1}\,N^{-2}(\log N)^{d-1}.\nonumber\end{eqnarray}$$
The result now follows by putting the three parts together and taking square roots. ◻
4.4 The proof of Theorem 2.2
Proof of Theorem 2.2.
We prove now the bound on the exponential Orlicz norm of the discrepancy function. Our proof uses ideas from [Reference Bilyk and Markhasin4]. Let again
$N=2^{n_{r}}+\cdots +2^{n_{1}}$
with
$n_{r}>\cdots >n_{1}\geqslant 0$
and let
${\mathcal{P}}_{N,d}$
be the point set which consists of the first
$N$
terms of
${\mathcal{S}}_{d}$
. We first restrict ourselves to the
$\exp (L^{2/(d-1)})$
-norm. The general result will follow directly by interpolating between the
$\exp (L^{2/(d-1)})$
-norm and the
$L_{\infty }$
-norm using Proposition 2.6 and the fact that for digital sequences we have
$$\begin{eqnarray}\Vert D_{{\mathcal{S}}_{d}}^{N}|L_{\infty }([0,1)^{d})\Vert \ll _{d}2^{t}\,N^{-1}(\log N)^{d},\end{eqnarray}$$
which follows from the fact that
${\mathcal{S}}_{d}$
is a digital
$(t^{\prime },d)$
-sequence (i.e., order-1 digital sequence) and [Reference Niederreiter29, Theorem 4.13].
We first use the Haar series expansion for the discrepancy function, the triangle inequality and the Chang–Wilson–Wolff inequality (Lemma 2.5) to obtain
$$\begin{eqnarray}\displaystyle & & \displaystyle \Vert D_{{\mathcal{S}}_{d}}^{N}|\text{exp}(L^{2/(d-1)})\Vert \nonumber\\ \displaystyle & & \displaystyle \quad =\biggl\|\mathop{\sum }_{k=0}^{\infty }\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|=k}}2^{|\,\boldsymbol{j}|}\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{j},\boldsymbol{m}}\rangle h_{\boldsymbol{j},\boldsymbol{m}}\Bigg|\text{exp}(L^{2/(d-1)})\biggr\|\nonumber\\ \displaystyle & & \displaystyle \quad \leqslant \mathop{\sum }_{k=0}^{\infty }\biggl\|\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|=k}}2^{|\,\boldsymbol{j}|}\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{j},\boldsymbol{m}}\rangle h_{\boldsymbol{j},\boldsymbol{m}}\Bigg|\text{exp}(L^{2/(d-1)})\biggr\|\nonumber\\ \displaystyle & & \displaystyle \quad \leqslant \mathop{\sum }_{k=0}^{\infty }\biggl\|\biggl(\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|=k}}2^{2|\,\boldsymbol{j}|}\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{2}\unicode[STIX]{x1D712}_{I_{\boldsymbol{j},\boldsymbol{m}}}\biggr)^{1/2}\Bigg|L_{\infty }([0,1)^{d})\biggr\|.\end{eqnarray}$$
To prove a bound on (4.7), we divide the sum over
$k$
into three parts, i.e., we consider the
$L_{\infty }$
-norm of the square function where
$|\,\boldsymbol{j}|$
lies in a certain range.
For
$\text{ld}\,N-t/2\leqslant |\,\boldsymbol{j}|<\text{ld}\,N$
, we have from Lemma 4.5 that
$$\begin{eqnarray}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{ j},\boldsymbol{m}}\rangle |\ll 2^{t/2}\,N^{-1}2^{-|\,\boldsymbol{j}|}\end{eqnarray}$$
if
$I_{\boldsymbol{j},\boldsymbol{m}}$
contains points of
${\mathcal{P}}_{N,d}$
and
$$\begin{eqnarray}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{ j},\boldsymbol{m}}\rangle |\ll 2^{-2|\,\boldsymbol{j}|}\end{eqnarray}$$
otherwise. Hence, for
$\text{ld}\,N-t/2\leqslant k<\text{ld}\,N$
we have
$$\begin{eqnarray}\displaystyle & & \displaystyle \sup _{\boldsymbol{x}\in [0,1)^{d}}\biggl(\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|=k}}2^{2|\,\boldsymbol{j}|}\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{2}\unicode[STIX]{x1D712}_{I_{\boldsymbol{j},\boldsymbol{m}}}\biggr)^{1/2}\nonumber\\ \displaystyle & & \displaystyle \qquad \ll \biggl(\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|=k}}\max \{2^{t}\,N^{-2},2^{-2|\,\boldsymbol{j}|}\}\biggr)^{1/2}\nonumber\\ \displaystyle & & \displaystyle \qquad \leqslant \biggl(2^{t}\,N^{-2}\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|=k}}1\biggr)^{1/2}\ll 2^{t/2}\,N^{-1}(\log N)^{(d-1)/2}.\nonumber\end{eqnarray}$$
Therefore
$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{\substack{ k\in \mathbb{N}_{0} \\ \text{ld}\,N-t/2\leqslant k<\text{ld}\,N}}\biggl\|\biggl(\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|=k}}2^{2|\,\boldsymbol{j}|}\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{2}\unicode[STIX]{x1D712}_{I_{\boldsymbol{j},\boldsymbol{m}}}\biggr)^{1/2}\Bigg|L_{\infty }([0,1)^{d})\biggr\|\nonumber\\ \displaystyle & & \displaystyle \qquad \qquad \ll 2^{t}\,N^{-1}(\log N)^{(d-1)/2}.\nonumber\end{eqnarray}$$
Next we consider the case where
$0\leqslant |\,\boldsymbol{j}|<\text{ld}\,N-t/2$
. Assume that we have
$$\begin{eqnarray}n_{\unicode[STIX]{x1D707}}\leqslant |\,\boldsymbol{j}|+t/2<n_{\unicode[STIX]{x1D707}+1},\end{eqnarray}$$
for some
$\unicode[STIX]{x1D707}\in \{0,1,\ldots ,r\}$
, where we set
$n_{r+1}=\text{ld}\,N$
and
$n_{0}=0$
. From Lemma 4.5 we have that
$$\begin{eqnarray}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{ j},\boldsymbol{m}}\rangle |\ll 2^{t}\,N^{-1}(2^{-|\,\boldsymbol{j}|}+(2n_{\unicode[STIX]{x1D707}+1}-t-2|\,\boldsymbol{j}|)^{d-1}2^{-n_{\unicode[STIX]{x1D707}+1}}).\end{eqnarray}$$
Hence, for
$n_{\unicode[STIX]{x1D707}}\leqslant k+t/2<n_{\unicode[STIX]{x1D707}+1}$
, we have
$$\begin{eqnarray}\displaystyle & & \displaystyle \sup _{\boldsymbol{x}\in [0,1)^{d}}\biggl(\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|=k}}2^{2|\,\boldsymbol{j}|}\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{2}\unicode[STIX]{x1D712}_{I_{\boldsymbol{j},\boldsymbol{m}}}\biggr)^{1/2}\nonumber\\ \displaystyle & & \displaystyle \qquad \ll 2^{t}\,N^{-1}\biggl(\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|=k}}2^{2|\,\boldsymbol{j}|}(2^{-|\,\boldsymbol{j}|}+(2n_{\unicode[STIX]{x1D707}+1}-t-2|\,\boldsymbol{j}|)^{d-1}2^{-n_{\unicode[STIX]{x1D707}+1}})^{2}\biggr)^{1/2},\nonumber\end{eqnarray}$$
and therefore we need to estimate
$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{\substack{ k\in \mathbb{N}_{0} \\ k\leqslant \text{ld}\,N-t/2}}\biggl\|\biggl(\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|=k}}2^{2|\,\boldsymbol{j}|}\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{2}\unicode[STIX]{x1D712}_{I_{\boldsymbol{j},\boldsymbol{m}}}\biggr)^{1/2}\Bigg|L_{\infty }([0,1)^{d})\biggr\|\nonumber\\ \displaystyle & & \displaystyle \qquad \ll 2^{t}\,N^{-1}\mathop{\sum }_{\unicode[STIX]{x1D707}=0}^{r}\mathop{\sum }_{\substack{ k\in \mathbb{N}_{0} \\ n_{\unicode[STIX]{x1D707}}\leqslant k+t/2<n_{\unicode[STIX]{x1D707}+1}}}\nonumber\\ \displaystyle & & \displaystyle \qquad \quad \times \,\biggl(\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|=k}}2^{2|\,\boldsymbol{j}|}(2^{-|\,\boldsymbol{j}|}+(2n_{\unicode[STIX]{x1D707}+1}-t-2|\,\boldsymbol{j}|)^{d-1}2^{-n_{\unicode[STIX]{x1D707}+1}})^{2}\biggr)^{1/2}\nonumber\\ \displaystyle & & \displaystyle \qquad \ll 2^{t}\,N^{-1}\mathop{\sum }_{\unicode[STIX]{x1D707}=0}^{r}\nonumber\\ \displaystyle & & \displaystyle \qquad \quad \times \,\mathop{\sum }_{\substack{ k\in \mathbb{N}_{0} \\ n_{\unicode[STIX]{x1D707}}\leqslant k+t/2<n_{\unicode[STIX]{x1D707}+1}}}(k^{d-1}2^{2k}(2^{-k}+(2n_{\unicode[STIX]{x1D707}+1}-t-2k)^{d-1}2^{-n_{\unicode[STIX]{x1D707}+1}})^{2})^{1/2}\nonumber\\ \displaystyle & & \displaystyle \qquad =2^{t}\,N^{-1}\mathop{\sum }_{\unicode[STIX]{x1D707}=0}^{r}\mathop{\sum }_{\substack{ k\in \mathbb{N}_{0} \\ n_{\unicode[STIX]{x1D707}}\leqslant k+t/2<n_{\unicode[STIX]{x1D707}+1}}}k^{(d-1)/2}(1+(2n_{\unicode[STIX]{x1D707}+1}-t-2k)^{d-1}2^{-n_{\unicode[STIX]{x1D707}+1}-k})\nonumber\\ \displaystyle & & \displaystyle \qquad \ll 2^{t}\,N^{-1}\mathop{\sum }_{k=0}^{\lceil \text{ld}\,N\rceil }k^{(d-1)/2}+2^{t}\,N^{-1}r\mathop{\sum }_{\ell =0}^{\lceil \text{ld}\,N\rceil }(2\ell -t)^{d-1}2^{-\ell }\nonumber\\ \displaystyle & & \displaystyle \qquad \ll 2^{t}\,N^{-1}(\log N)^{(d+1)/2}.\nonumber\end{eqnarray}$$
It remains to estimate the terms where
$k\geqslant \text{ld}\,N$
. As in [Reference Bilyk and Markhasin4] we treat the volume part of the discrepancy function separately from the counting part.
For the volume part
$L(\boldsymbol{x})=x_{1}\cdots x_{d}$
we have
$|\langle L,h_{\boldsymbol{j},\boldsymbol{m}}\rangle |\asymp 2^{-2|\,\boldsymbol{j}|}$
. Hence
$$\begin{eqnarray}\displaystyle & & \displaystyle \biggl\|\mathop{\sum }_{\substack{ k=0 \\ k\geqslant \text{ld}\,N}}^{\infty }\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|=k}}2^{|\,\boldsymbol{j}|}\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}\langle L,h_{\boldsymbol{j},\boldsymbol{m}}\rangle h_{\boldsymbol{j},\boldsymbol{m}}\Bigg|\text{exp}(L^{2/(d-1)})\biggr\|\nonumber\\ \displaystyle & & \displaystyle \qquad \leqslant \mathop{\sum }_{\substack{ k=0 \\ k\geqslant \text{ld}\,N}}^{\infty }\biggl\|\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|=k}}2^{|\,\boldsymbol{j}|}\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}\langle L,h_{\boldsymbol{j},\boldsymbol{m}}\rangle h_{\boldsymbol{j},\boldsymbol{m}}\Bigg|\text{exp}(L^{2/(d-1)})\biggr\|\nonumber\\ \displaystyle & & \displaystyle \qquad \leqslant \mathop{\sum }_{\substack{ k=0 \\ k\geqslant \text{ld}\,N}}^{\infty }\biggl\|\biggl(\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|=k}}2^{2|\,\boldsymbol{j}|}\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}|\langle L,h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{2}\unicode[STIX]{x1D712}_{I_{\boldsymbol{j},\boldsymbol{m}}}\biggr)^{1/2}\Bigg|L_{\infty }([0,1)^{d})\biggr\|\nonumber\\ \displaystyle & & \displaystyle \qquad \ll \mathop{\sum }_{\substack{ k=0 \\ k\geqslant \text{ld}\,N}}^{\infty }\biggl(\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|=k}}2^{-2|\,\boldsymbol{j}|}\biggr)^{1/2}\ll \mathop{\sum }_{\substack{ k=0 \\ k\geqslant \text{ld}\,N}}^{\infty }k^{(d-1)/2}2^{-k}\ll N^{-1}(\log N)^{(d-1)/2}.\nonumber\end{eqnarray}$$
It remains to estimate the counting part
$C(\boldsymbol{x})=N^{-1}\sum _{\boldsymbol{z}\in {\mathcal{P}}_{N,d}}\unicode[STIX]{x1D712}_{[\mathbf{0},\boldsymbol{x})}(\boldsymbol{z})$
. Let
$n\in \mathbb{N}$
be such that
$2^{n-1}<N\leqslant 2^{n}$
. Let again
${\mathcal{J}}$
be the set of all dyadic intervals
$I_{\boldsymbol{j},\boldsymbol{m}}$
with
$|\,\boldsymbol{j}|\geqslant n$
, i.e.,
$|I_{\boldsymbol{j},\boldsymbol{m}}|\leqslant 2^{-n}$
, such that
$\langle C,h_{\boldsymbol{j},\boldsymbol{m}}\rangle \neq 0$
. As above, this implies that for
$I_{\boldsymbol{j},\boldsymbol{m}}\in {\mathcal{J}}$
we have that at least one point of
${\mathcal{P}}_{N,d}$
lies in the interior of
$I_{\boldsymbol{j},\boldsymbol{m}}$
. Hence
$j_{k}\leqslant 2n$
, or in other words
$|I_{j_{k},m_{k}}|\geqslant 2^{-2n}$
, for each coordinate
$k=1,2,\ldots ,d$
.
We also define the unique parent of each
$I_{\boldsymbol{j},\boldsymbol{m}}\in {\mathcal{J}}$
, denoted by
$\widetilde{I}_{\boldsymbol{j},\boldsymbol{m}}$
, which satisfies: (i)
$I_{\boldsymbol{j},\boldsymbol{m}}\subseteq \widetilde{I}_{\boldsymbol{j}^{\prime },\boldsymbol{m}^{\prime }}$
; (ii)
$|\,\boldsymbol{j}^{\prime }|=n$
, i.e.,
$|\widetilde{I}_{\boldsymbol{j}^{\prime },\boldsymbol{m}^{\prime }}|=2^{-n}$
; and (iii)
$j_{k}=j_{k}^{\prime }$
(which implies that
$I_{j_{k},m_{k}}=\widetilde{I}_{j_{k}^{\prime },m_{k}^{\prime }}$
) for all
$k=1,2,\ldots ,d$
. In other words, to find the parent, we expand the
$d$
th side of
$I_{\boldsymbol{j},\boldsymbol{m}}$
to a dyadic interval such that the volume of the resulting interval has volume
$2^{-n}$
. By reordering the sum over the intervals with respect to their parents we obtain
$$\begin{eqnarray}\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|\geqslant n}}2^{|\,\boldsymbol{j}|}\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}\langle C,h_{\boldsymbol{j},\boldsymbol{m}}\rangle h_{\boldsymbol{j},\boldsymbol{m}}=\mathop{\sum }_{\substack{ \widetilde{I}_{\boldsymbol{ j}^{\prime },\boldsymbol{m}^{\prime }}:|\,\boldsymbol{j}^{\prime }|=n \\ j_{k}^{\prime }\leqslant 2n:k=1,\ldots ,d}}\mathop{\sum }_{\substack{ I_{\boldsymbol{j},\boldsymbol{m}}\subseteq \widetilde{I}_{\boldsymbol{j}^{\prime },\boldsymbol{m}^{\prime }} \\ j_{k}=j_{k}^{\prime }:k=1,\ldots ,d-1}}2^{|\,\boldsymbol{j}|}\langle C,h_{\boldsymbol{ j},\boldsymbol{m}}\rangle h_{\boldsymbol{j},\boldsymbol{m}}.\end{eqnarray}$$
For an arbitrary, but fixed, parent interval
$\widetilde{I}_{\boldsymbol{j}^{\prime },\boldsymbol{m}^{\prime }}$
we consider the innermost sum above
$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{\substack{ I_{\boldsymbol{j},\boldsymbol{m}}\subseteq \widetilde{I}_{\boldsymbol{j}^{\prime },\boldsymbol{m}^{\prime }} \\ j_{k}=j_{k}^{\prime }:k=1,\ldots ,d-1}}2^{|\,\boldsymbol{j}|}\langle C,h_{\boldsymbol{j},\boldsymbol{m}}\rangle h_{\boldsymbol{j},\boldsymbol{m}}\nonumber\\ \displaystyle & & \displaystyle \qquad =N^{-1}\mathop{\sum }_{\boldsymbol{z}\in {\mathcal{P}}_{N,d}\cap \widetilde{I}_{\boldsymbol{j}^{\prime },\boldsymbol{m}^{\prime }}}\mathop{\sum }_{\substack{ I_{\boldsymbol{j},\boldsymbol{m}}\subseteq \widetilde{I}_{\boldsymbol{j}^{\prime },\boldsymbol{m}^{\prime }} \\ j_{k}=j_{k}^{\prime }:k=1,\ldots ,d-1}}2^{|\,\boldsymbol{j}|}\langle \unicode[STIX]{x1D712}_{[\boldsymbol{z},\mathbf{1})},h_{\boldsymbol{j},\boldsymbol{m}}\rangle h_{\boldsymbol{j},\boldsymbol{m}}.\end{eqnarray}$$
The summands in the last sum split into products of one-dimensional factors
$$\begin{eqnarray}\displaystyle & & \displaystyle 2^{|\,\boldsymbol{j}|}\langle \unicode[STIX]{x1D712}_{[\boldsymbol{z},\mathbf{1})},h_{\boldsymbol{j},\boldsymbol{m}}\rangle h_{\boldsymbol{j},\boldsymbol{m}}(\boldsymbol{x})\nonumber\\ \displaystyle & & \displaystyle \qquad =\mathop{\prod }_{k=1}^{d}2^{j_{k}}\langle \unicode[STIX]{x1D712}_{[z_{k},1)},h_{j_{k},m_{k}}\rangle h_{j_{k},m_{k}}(x_{k})\nonumber\\ \displaystyle & & \displaystyle \qquad =\biggl(\mathop{\prod }_{k=1}^{d-1}2^{j_{k}^{\prime }}\langle \unicode[STIX]{x1D712}_{[z_{k},1)},h_{j_{k}^{\prime },m_{k}^{\prime }}\rangle h_{j_{k}^{\prime },m_{k}^{\prime }}(x_{k})\biggr)2^{j_{d}}\langle \unicode[STIX]{x1D712}_{[z_{d},1)},h_{j_{d},m_{d}}\rangle h_{j_{d},m_{d}}(x_{d})\nonumber\\ \displaystyle & & \displaystyle \qquad =2^{|\,\boldsymbol{j}_{\ast }^{\prime }|}\langle \unicode[STIX]{x1D712}_{[\boldsymbol{z}_{\ast },\mathbf{1})},h_{\boldsymbol{j}_{\ast }^{\prime },\boldsymbol{m}_{\ast }^{\prime }}\rangle 2^{j_{d}}\langle \unicode[STIX]{x1D712}_{[z_{d},1)},h_{j_{d},m_{d}}\rangle h_{j_{d},m_{d}}(x_{d}),\nonumber\end{eqnarray}$$
where by
$\ast$
we denote the projection of a
$d$
-dimensional vector to its first
$d-1$
coordinates (i.e., for instance,
$\boldsymbol{z}_{\ast }=(z_{1},\ldots ,z_{d-1})$
for
$\boldsymbol{z}=(z_{1},\ldots ,z_{d-1},z_{d})$
). Thus we can write the innermost sum on the right-hand side of (4.9) as
$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{\substack{ I_{\boldsymbol{j},\boldsymbol{m}}\subseteq \widetilde{I}_{\boldsymbol{j}^{\prime },\boldsymbol{m}^{\prime }} \\ j_{k}=j_{k}^{\prime }:k=1,\ldots ,d-1}}2^{|\,\boldsymbol{j}|}\langle \unicode[STIX]{x1D712}_{[\boldsymbol{z},\mathbf{1})},h_{\boldsymbol{j},\boldsymbol{m}}\rangle h_{\boldsymbol{j},\boldsymbol{m}}(\boldsymbol{x})\nonumber\\ \displaystyle & & \displaystyle \qquad =2^{|\,\boldsymbol{j}_{\ast }^{\prime }|}\langle \unicode[STIX]{x1D712}_{[\boldsymbol{z}_{\ast },\mathbf{1})},h_{\boldsymbol{j}_{\ast }^{\prime },\boldsymbol{m}_{\ast }^{\prime }}\rangle h_{\boldsymbol{j}_{\ast }^{\prime },\boldsymbol{m}_{\ast }^{\prime }}(x_{\ast })\mathop{\sum }_{I_{j_{d},m_{d}}\subseteq \widetilde{I}_{j_{d}^{\prime },m_{d}^{\prime }}}2^{j_{d}}\langle \unicode[STIX]{x1D712}_{[z_{d},1)},h_{j_{d},m_{d}}\rangle h_{j_{d},m_{d}}(x_{d}).\nonumber\end{eqnarray}$$
The last sum is now the Haar series expansion of the indicator function
$\unicode[STIX]{x1D712}_{[z_{d},1)}$
restricted to the interval
$\widetilde{I}_{j_{d}^{\prime },m_{d}^{\prime }}$
without the constant term, i.e., we have
$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{I_{j_{d},m_{d}}\subseteq \widetilde{I}_{j_{d}^{\prime },m_{d}^{\prime }}}2^{j_{d}}\langle \unicode[STIX]{x1D712}_{[z_{d},1)},h_{j_{d},m_{d}}\rangle h_{j_{d},m_{d}}(x_{d})\nonumber\\ \displaystyle & & \displaystyle \qquad =\unicode[STIX]{x1D712}_{\widetilde{I}_{j_{d}^{\prime },m_{d}^{\prime }}}(x_{d})(\unicode[STIX]{x1D712}_{[z_{d},1)}(x_{d})-2^{j_{d}^{\prime }}|[z_{d},1)\cap \widetilde{I}_{j_{d}^{\prime },m_{d}^{\prime }}|).\end{eqnarray}$$
Using the triangle inequality it follows that the last expression is bounded pointwise by
$2$
. Further we have
$|2^{|\,\boldsymbol{j}_{\ast }^{\prime }|}\langle \unicode[STIX]{x1D712}_{[\boldsymbol{z}_{\ast },\mathbf{1})},h_{\boldsymbol{j}_{\ast }^{\prime },\boldsymbol{m}_{\ast }^{\prime }}\rangle |\leqslant 1$
. Since there are at most
$2^{\lceil t/2\rceil }$
points of
${\mathcal{P}}_{N,d}$
in
$\widetilde{I}_{\boldsymbol{j}^{\prime },\boldsymbol{m}^{\prime }}$
, we obtain that
$$\begin{eqnarray}\mathop{\sum }_{\substack{ I_{\boldsymbol{j},\boldsymbol{m}}\subseteq \widetilde{I}_{\boldsymbol{j}^{\prime },\boldsymbol{m}^{\prime }} \\ j_{k}=j_{k}^{\prime }:k=1,\ldots ,d-1}}2^{|\,\boldsymbol{j}|}\langle C,h_{\boldsymbol{ j},\boldsymbol{m}}\rangle h_{\boldsymbol{j},\boldsymbol{m}}(\boldsymbol{x})=N^{-1}\unicode[STIX]{x1D6FC}_{j_{d}^{\prime }}(x_{d})h_{\boldsymbol{j}_{\ast }^{\prime },\boldsymbol{m}_{\ast }^{\prime }}(\boldsymbol{x}_{\ast }),\end{eqnarray}$$
where
$|\unicode[STIX]{x1D6FC}_{j_{d}^{\prime }}(x_{d})|\leqslant 2^{\lceil t/2\rceil +1}\ll 1$
.
Let now
$x_{d}$
be fixed. Equation (4.10) implies that for a given
$(d-1)$
-dimensional interval
$\widetilde{I}_{\boldsymbol{j}_{\ast }^{\prime },\boldsymbol{m}_{\ast }^{\prime }}$
there exists only one
$d$
-dimensional interval of the form
$\widetilde{I}_{\boldsymbol{j}^{\prime },\boldsymbol{m}^{\prime }}=\widetilde{I}_{\boldsymbol{j}_{\ast }^{\prime },\boldsymbol{m}_{\ast }^{\prime }}\times \widetilde{I}_{j_{d}^{\prime },m_{d}^{\prime }}$
with
$|\widetilde{I}_{\boldsymbol{j}^{\prime },\boldsymbol{m}^{\prime }}|=2^{-n}$
such that
$\unicode[STIX]{x1D6FC}_{j_{d}^{\prime }}(x_{d})\neq 0$
. We can now apply (4.8) and take the
$L_{p}$
-norm in the first
$d-1$
variables to obtain
$$\begin{eqnarray}\displaystyle & & \displaystyle \biggl\|\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|\geqslant n}}2^{|\,\boldsymbol{j}|}\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}\langle C,h_{\boldsymbol{j},\boldsymbol{m}}\rangle h_{\boldsymbol{j},\boldsymbol{m}}\Bigg|L_{p} ([0,1)\hspace{-1.99997pt}^{d-1} )\biggr\|\nonumber\\ \displaystyle & & \displaystyle \qquad =\biggl\|\mathop{\sum }_{\substack{ \widetilde{I}_{\boldsymbol{ j}^{\prime },\boldsymbol{m}^{\prime }}:|\,\boldsymbol{j}^{\prime }|=n \\ j_{k}^{\prime }\leqslant 2n:k=1,\ldots ,d}}\mathop{\sum }_{\substack{ I_{\boldsymbol{j},\boldsymbol{m}}\subseteq \widetilde{I}_{\boldsymbol{j}^{\prime },\boldsymbol{m}^{\prime }} \\ j_{k}=j_{k}^{\prime }:k=1,\ldots ,d-1}}2^{|\,\boldsymbol{j}|}\langle C,h_{\boldsymbol{j},\boldsymbol{m}}\rangle h_{\boldsymbol{j},\boldsymbol{m}}\Bigg|L_{p}([0,1)\hspace{-1.99997pt}^{d-1})\biggr\|\nonumber\\ \displaystyle & & \displaystyle \qquad =N^{-1}\biggl\|\mathop{\sum }_{\substack{ \widetilde{I}_{\boldsymbol{ j}_{\ast }^{\prime },\boldsymbol{m}_{\ast }^{\prime }}:|\,\boldsymbol{j}^{\prime }|=n \\ j_{k}^{\prime }\leqslant 2n:k=1,\ldots ,d-1}}\unicode[STIX]{x1D6FC}_{j_{d}^{\prime }}(x_{d})h_{\boldsymbol{j}_{\ast }^{\prime },\boldsymbol{m}_{\ast }^{\prime }}\Bigg|L_{p} ([0,1)^{d-1}\biggr\|\nonumber\\ \displaystyle & & \displaystyle \qquad \ll p^{(d-1)/2}\,N^{-1}\biggl\|\biggl(\mathop{\sum }_{\substack{ \widetilde{I}_{\boldsymbol{ j}_{\ast }^{\prime },\boldsymbol{m}_{\ast }^{\prime }}:|\,\boldsymbol{j}^{\prime }|=n \\ j_{k}^{\prime }\leqslant 2n:k=1,\ldots ,d-1}}|\unicode[STIX]{x1D6FC}_{j_{d}^{\prime }}(x_{d})|^{2}\unicode[STIX]{x1D712}_{\widetilde{I}_{\boldsymbol{j}_{\ast }^{\prime },\boldsymbol{m}_{\ast }^{\prime }}}\biggr)^{1/2}\Bigg|L_{p}([0,1)\hspace{-1.99997pt}^{d-1})\biggr\|\nonumber\\ \displaystyle & & \displaystyle \qquad \ll p^{(d-1)/2}n^{(d-1)/2}\,N^{-1},\nonumber\end{eqnarray}$$
where in the penultimate step we have employed the
$(d-1)$
-dimensional Littlewood–Paley inequality (see Lemma 2.4) and in the last step the fact that the number of choices of
$\,\boldsymbol{j}_{\ast }^{\prime }$
is of order
$n^{d-1}$
at most.
By integrating this bound with respect to the last variable
$x_{d}$
and using Proposition 2.3 we obtain
$$\begin{eqnarray}\biggl\|\mathop{\sum }_{\substack{ \boldsymbol{j}\in \mathbb{N}_{-1}^{d} \\ |\,\boldsymbol{j}|\geqslant n}}2^{|\,\boldsymbol{j}|}\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}\langle C_{{\mathcal{P}}_{N,d}},h_{\boldsymbol{j},\boldsymbol{m}}\rangle h_{\boldsymbol{j},\boldsymbol{m}}\Bigg|\text{exp}(L^{2/(d-1)})\biggr\|\ll N^{-1}n^{(d-1)/2},\end{eqnarray}$$
from which the result now follows. ◻
4.5 The proof of the upper bounds in Theorem 3.1
Proof of equations (3.4) and (3.6) in Theorem 3.1.
According to Proposition 3.4 we have
$$\begin{eqnarray}\Vert D_{{\mathcal{S}}_{d}}^{N}|S_{p,q}^{s}B\Vert ^{q}~\ll _{p,q,s,d}~\mathop{\sum }_{\boldsymbol{j}\in \mathbb{N}_{-1}^{d}}2^{|\,\boldsymbol{j}|(s-1/p+1)q}\biggl(\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{ j},\boldsymbol{m}}\rangle |^{p}\biggr)^{q/p}.\end{eqnarray}$$
Let
$|\,\boldsymbol{j}|+t/2\geqslant \text{ld}\,N$
, then according to Lemma 4.5 we have
$$\begin{eqnarray}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{ j},\boldsymbol{m}}\rangle |\ll 2^{t/2}\,N^{-1}2^{-|\,\boldsymbol{j}|}\end{eqnarray}$$
and for a fixed
$\,\boldsymbol{j}$
, at least
$2^{|\,\boldsymbol{j}|}-N$
intervals
$I_{\boldsymbol{j},\boldsymbol{m}}$
contain no points of
${\mathcal{P}}_{N,d}$
(the point set consisting of the first
$N$
elements of
${\mathcal{S}}_{d}$
) and in such cases we have according to Lemma 4.5
$$\begin{eqnarray}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{ j},\boldsymbol{m}}\rangle |\ll 2^{-2|\,\boldsymbol{j}|}.\end{eqnarray}$$
Now we estimate (4.11) by applying Minkowski’s inequality to obtain
$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{|\,\boldsymbol{j}|+t/2\geqslant \text{ld}\,N}2^{|\,\boldsymbol{j}|(s-1/p+1)q}\biggl(\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{p}\biggr)^{q/p}\nonumber\\ \displaystyle & & \displaystyle \qquad \ll \mathop{\sum }_{|\,\boldsymbol{j}|+t/2\geqslant \text{ld}\,N}2^{|\,\boldsymbol{j}|(s-1/p+1)q}(N2^{pt/2}\,N^{-p}2^{-p|\,\boldsymbol{j}|})^{q/p}\nonumber\\ \displaystyle & & \displaystyle \qquad \quad +\mathop{\sum }_{|\,\boldsymbol{j}|+t/2\geqslant \text{ld}\,N}2^{|\,\boldsymbol{j}|(s-1/p+1)q}(\max \{2^{|\,\boldsymbol{j}|}-N,0\}2^{-2p|\,\boldsymbol{j}|})^{q/p}\nonumber\\ \displaystyle & & \displaystyle \qquad \leqslant N^{q/p-q}2^{qt/2}\mathop{\sum }_{|\,\boldsymbol{j}|+t/2\geqslant \text{ld}\,N}2^{|\,\boldsymbol{j}|(s-1/p)q}+\mathop{\sum }_{|\,\boldsymbol{j}|+t/2\geqslant \text{ld}\,N}2^{|\,\boldsymbol{j}|(s-1)q}\nonumber\\ \displaystyle & & \displaystyle \qquad \ll N^{q/p-q}2^{qt/2}N^{(s-1/p)q}2^{-t/2(s-1/p)q}(\log N)^{d-1}\nonumber\\ \displaystyle & & \displaystyle \qquad \quad +\,N^{(s-1)q}2^{-t/2(s-1)q}(\log N)^{d-1}\nonumber\\ \displaystyle & & \displaystyle \qquad \leqslant 2^{(1-s+1/p)tq/2}N^{(s-1)q}(\log N)^{d-1}.\end{eqnarray}$$
Now let
$n_{r}>\cdots >n_{\unicode[STIX]{x1D707}+1}\geqslant |\,\boldsymbol{j}|+t/2>n_{\unicode[STIX]{x1D707}}>\cdots >n_{1}$
. Then according to Lemma 4.5 we have
$$\begin{eqnarray}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{ j},\boldsymbol{m}}\rangle |\ll 2^{t}\,N^{-1}(2^{-|\,\boldsymbol{j}|}+(2n_{\unicode[STIX]{x1D707}+1}-t-2|\,\boldsymbol{j}|)^{d-1}2^{-n_{\unicode[STIX]{x1D707}+1}}).\end{eqnarray}$$
We use this bound to estimate the terms of (4.11) for which
$|\,\boldsymbol{j}|+t/2<\text{ld}\,N$
(again we set
$n_{0}=0,\,n_{r+1}=\text{ld}\,N$
). We use Minkowski’s inequality
$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{|\,\boldsymbol{j}|+t/2<\text{ld}\,N}2^{|\,\boldsymbol{j}|(s-1/p+1)q}\biggl(\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{p}\biggr)^{q/p}\nonumber\\ \displaystyle & & \displaystyle \qquad =\mathop{\sum }_{\unicode[STIX]{x1D707}=0}^{r}\mathop{\sum }_{n_{\unicode[STIX]{x1D707}}\leqslant |\,\boldsymbol{j}|+t/2<n_{\unicode[STIX]{x1D707}+1}}2^{|\,\boldsymbol{j}|(s-1/p+1)q}\biggl(\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{p}\biggr)^{q/p}\nonumber\\ \displaystyle & & \displaystyle \qquad \ll \mathop{\sum }_{\unicode[STIX]{x1D707}=0}^{r}\mathop{\sum }_{n_{\unicode[STIX]{x1D707}}\leqslant |\,\boldsymbol{j}|+t/2<n_{\unicode[STIX]{x1D707}+1}}2^{|\,\boldsymbol{j}|(s-1/p+1)q}2^{q|\,\boldsymbol{j}|/p}\,2^{qt}\,N^{-q}\nonumber\\ \displaystyle & & \displaystyle \qquad \quad \times \,(2^{-|\,\boldsymbol{j}|}+(2n_{\unicode[STIX]{x1D707}+1}-t-2|j|)^{d-1}2^{-n_{\unicode[STIX]{x1D707}+1}})^{\lceil q\rceil }\nonumber\\ \displaystyle & & \displaystyle \qquad =2^{qt}\,N^{-q}\mathop{\sum }_{\unicode[STIX]{x1D707}=0}^{r}\mathop{\sum }_{n_{\unicode[STIX]{x1D707}}\leqslant |\,\boldsymbol{j}|+t/2<n_{\unicode[STIX]{x1D707}+1}}2^{|\,\boldsymbol{j}|(s+1)q}\nonumber\\ \displaystyle & & \displaystyle \qquad \quad \times \,\mathop{\sum }_{i=0}^{\lceil q\rceil }2^{-|\,\boldsymbol{j}|i}2^{-n_{\unicode[STIX]{x1D707}+1}(\lceil q\rceil -i)}(2n_{\unicode[STIX]{x1D707}+1}-t-2|\,\boldsymbol{j}|)^{(d-1)(\lceil q\rceil -i)}\nonumber\\ \displaystyle & & \displaystyle \qquad \leqslant 2^{qt}\,N^{-q}\mathop{\sum }_{\unicode[STIX]{x1D707}=0}^{r}\mathop{\sum }_{i=0}^{\lceil q\rceil }2^{-n_{\unicode[STIX]{x1D707}+1}(\lceil q\rceil -i)}\nonumber\\ \displaystyle & & \displaystyle \qquad \quad \times \,\mathop{\sum }_{n_{\unicode[STIX]{x1D707}}\leqslant |\,\boldsymbol{j}|+t/2<n_{\unicode[STIX]{x1D707}+1}}2^{|\,\boldsymbol{j}|(sq+\lceil q\rceil -i)}(2n_{\unicode[STIX]{x1D707}+1}-t-2|\,\boldsymbol{j}|)^{(d-1)(\lceil q\rceil -i)}\nonumber\\ \displaystyle & & \displaystyle\end{eqnarray}$$
and obtain from Lemmas 4.6 and 4.7 for
$s>0$
$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{|\,\boldsymbol{j}|+t/2<\text{ld}\,N}2^{|\,\boldsymbol{j}|(s-1/p+1)q}\biggl(\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{p}\biggr)^{q/p}\nonumber\\ \displaystyle & & \displaystyle \qquad \ll 2^{qt}\,N^{-q}\mathop{\sum }_{\unicode[STIX]{x1D707}=0}^{r}\mathop{\sum }_{i=0}^{\lceil q\rceil }2^{-n_{\unicode[STIX]{x1D707}+1}(\lceil q\rceil -i)}2^{(n_{\unicode[STIX]{x1D707}+1}-t/2)(sq+\lceil q\rceil -i)}(\log N)^{d-1}\nonumber\\ \displaystyle & & \displaystyle \qquad \leqslant 2^{qt}\,N^{-q}2^{-tsq/2-t\lceil q\rceil /2}\mathop{\sum }_{\unicode[STIX]{x1D707}=0}^{r}2^{n_{\unicode[STIX]{x1D707}+1}sq}\mathop{\sum }_{i=0}^{\lceil q\rceil }2^{ti/2}(\log N)^{d-1}\nonumber\\ \displaystyle & & \displaystyle \qquad \ll 2^{qt-tsq/2}\,N^{-q}2^{n_{r+1}sq}(\log N)^{d-1}=2^{tq(1-s/2)}\,N^{(s-1)q}(\log N)^{d-1}.\nonumber\\ \displaystyle & & \displaystyle\end{eqnarray}$$
The case
$s=0$
needs to be handled slightly differently. We continue from (4.13) and obtain
$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\sum }_{|\,\boldsymbol{j}|+t/2<\text{ld}\,N}2^{|\,\boldsymbol{j}|(-1/p+1)q}\biggl(\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{p}\biggr)^{q/p}\nonumber\\ \displaystyle & & \displaystyle \qquad \ll 2^{qt}\,N^{-q}\mathop{\sum }_{\unicode[STIX]{x1D707}=0}^{r}\mathop{\sum }_{i=0}^{\lceil q\rceil -1}2^{-n_{\unicode[STIX]{x1D707}+1}(\lceil q\rceil -i)}\nonumber\\ \displaystyle & & \displaystyle \qquad \quad \times \,\mathop{\sum }_{n_{\unicode[STIX]{x1D707}}\leqslant |\,\boldsymbol{j}|+t/2<n_{\unicode[STIX]{x1D707}+1}}2^{|\,\boldsymbol{j}|(\lceil q\rceil -i)}(2n_{\unicode[STIX]{x1D707}+1}-t-2|\,\boldsymbol{j}|)^{(d-1)(\lceil q\rceil -i)}\nonumber\\ \displaystyle & & \displaystyle \qquad \quad +\,2^{qt}\,N^{-q}\mathop{\sum }_{\unicode[STIX]{x1D707}=0}^{r}\mathop{\sum }_{n_{\unicode[STIX]{x1D707}}\leqslant |\,\boldsymbol{j}|+t/2<n_{\unicode[STIX]{x1D707}+1}}(2n_{\unicode[STIX]{x1D707}+1}-t-2|\,\boldsymbol{j}|)\nonumber\\ \displaystyle & & \displaystyle \qquad \ll 2^{qt}\,N^{-q}(\log N)^{d}+2^{qt}N^{-q}\nonumber\\ \displaystyle & & \displaystyle \qquad \quad \times \,\mathop{\sum }_{\unicode[STIX]{x1D707}=0}^{r}(n_{\unicode[STIX]{x1D707}+1}-n_{\unicode[STIX]{x1D707}})(\log N)^{d-1}\ll 2^{qt}\,N^{-q}(\log N)^{d}.\end{eqnarray}$$
Combining (4.12), (4.14) and (4.15) we obtain
$$\begin{eqnarray}\displaystyle \Vert D_{{\mathcal{S}}_{d}}^{N}|S_{p,q}^{s}B\Vert ^{q}~\ll _{p,q,s,d}~\left\{\begin{array}{@{}ll@{}}2^{tq}N^{-q}\,(\log N)^{d}\quad & \text{if }s=0,\\ 2^{tq}N^{(s-1)q}\,(\log N)^{d-1}\quad & \text{if }0<s<1/p,\end{array}\right. & & \displaystyle \nonumber\end{eqnarray}$$
and the result follows. ◻
4.6 The proof of the upper bounds in Theorem 3.2
Proof of equations (3.10) and (3.12) in Theorem 3.2.
From Proposition 3.3 we know that
$$\begin{eqnarray}S_{\max (p,q),q}^{s}B{\hookrightarrow}S_{p,q}^{s}F.\end{eqnarray}$$
Thus we have
$$\begin{eqnarray}\displaystyle \Vert D_{{\mathcal{S}}_{d}}^{N}|S_{p,q}^{s}F\Vert & \ll & \displaystyle \Vert D_{{\mathcal{S}}_{d}}^{N}|S_{\max (p,q),q}^{s}B\Vert \nonumber\\ \displaystyle & \ll & \displaystyle \left\{\begin{array}{@{}ll@{}}2^{t}N^{-1}\,(\log N)^{d/q}\quad & \text{ if }s=0,\\ 2^{t}N^{(s-1)}\,(\log N)^{(d-1)/q}\quad & \text{ if }0<s<1/\text{max}(p,q).\square\end{array}\right.\nonumber\end{eqnarray}$$
5 Lower bounds
In this section we prove the lower bounds on the respective norms of the discrepancy function of arbitrary sequences in the unit cube.
5.1 The proof of the lower bound in Theorem 2.1
To prove equation (2.2) we actually prove a lower bound for a norm close to the
$L_{2}$
-norm of
$f$
which is dominated by the
$\text{BMO}$
-norm. For simplicity of notation, let us consider here the
$L_{2}$
-normalized version of the Haar system consisting of the functions
$g_{\boldsymbol{j},\boldsymbol{m}}=2^{|\,\boldsymbol{j}|/2}h_{\boldsymbol{j},\boldsymbol{m}}$
. Moreover, for a subset
${\mathcal{E}}$
of indices
$(\,\boldsymbol{j},\boldsymbol{m})$
with
$\,\boldsymbol{j}\in \mathbb{N}_{-1}^{d},\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}$
let
$P_{{\mathcal{E}}}f$
denote the orthogonal projection of
$f\in L_{2}([0,1]^{d})$
onto the span of
$\{g_{\boldsymbol{j},\boldsymbol{m}}\,:\,(\,\boldsymbol{j},\boldsymbol{m})\in {\mathcal{E}}\}$
and let
$\Vert f|{\mathcal{E}}\Vert =\Vert P_{{\mathcal{E}}}f|L_{2}\Vert$
. Then Parseval’s equality yields
$$\begin{eqnarray}\Vert f|{\mathcal{E}}\Vert ^{2}=\mathop{\sum }_{(\,\boldsymbol{j},\boldsymbol{m})\in {\mathcal{E}}}\langle f,g_{\boldsymbol{j},\boldsymbol{m}}\rangle ^{2}.\end{eqnarray}$$
We also fix the index sets
$$\begin{eqnarray}{\mathcal{D}}^{d}=\{(\,\boldsymbol{j},\boldsymbol{m}):\boldsymbol{j}\in \mathbb{N}_{-1}^{d},\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{ j}}\}\quad \text{and}\quad {\mathcal{D}}_{0}^{d}=\{(\,\boldsymbol{j},\boldsymbol{m}):\boldsymbol{j}\in \mathbb{N}_{0}^{d},\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{ j}}\}.\end{eqnarray}$$
Considering
$U=[0,1)^{d}$
in the definition (2.1) of the
$\text{BMO}$
-norm, we obviously have
$$\begin{eqnarray}\Vert f|\text{BMO}^{d}\Vert \geqslant \Vert f|{\mathcal{D}}_{0}^{d}\Vert .\end{eqnarray}$$
Now the lower bound (2.2) in Theorem 2.1 follows immediately from the next lemma.
Lemma 5.1. For every
$d\in \mathbb{N}$
there exists a positive constant
$c_{d}>0$
with the following property: for every infinite sequence
${\mathcal{S}}_{d}$
in
$[0,1)^{d}$
we have
$$\begin{eqnarray}\Vert D_{{\mathcal{S}}_{d}}^{N}|{\mathcal{D}}_{0}^{d}\Vert \geqslant c_{d}\,N^{-1}(\log N)^{d/2}\quad \text{for infinitely many }N\in \mathbb{N}.\end{eqnarray}$$
For the proof we combine the following lemma with the method of Proinov.
Lemma 5.2. Let
$f:[0,1]^{d+1}\rightarrow \mathbb{R}$
be in
$L_{2}([0,1]^{d})$
. Then we have
$$\begin{eqnarray}\Vert f|{\mathcal{D}}_{0}^{d+1}\Vert \leqslant \sup _{t_{d+1}\in [0,1]}\Vert f(\cdot ,t_{d+1})|{\mathcal{D}}_{0}^{d}\Vert .\end{eqnarray}$$
Proof. We are going to show the identity
$$\begin{eqnarray}\int _{0}^{1}\Vert f(\cdot ,t_{d+1})|{\mathcal{D}}_{0}^{d}\Vert ^{2}\,dt_{d+1}=\Vert f|{\mathcal{E}}^{d+1}\Vert ^{2},\end{eqnarray}$$
where
$$\begin{eqnarray}{\mathcal{E}}^{d+1}=\{(\,\boldsymbol{j},\boldsymbol{m}):\boldsymbol{j}\in \mathbb{N}_{0}^{d}\times \mathbb{N}_{-1},\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}\}.\end{eqnarray}$$
Then the claimed inequality is a consequence of (5.1) together with the obvious inequalities
$$\begin{eqnarray}\displaystyle \Vert f|{\mathcal{D}}_{0}^{d+1}\Vert \leqslant \Vert f|{\mathcal{E}}^{d+1}\Vert & & \displaystyle \nonumber\end{eqnarray}$$
and
$$\begin{eqnarray}\displaystyle \int _{0}^{1}\Vert f(\cdot ,t_{d+1})|{\mathcal{D}}_{0}^{d}\Vert ^{2}\,dt_{d+1}\leqslant \sup _{t_{d+1}\in [0,1]}\Vert f(\cdot ,t_{d+1})|{\mathcal{D}}_{0}^{d}\Vert ^{2}. & & \displaystyle \nonumber\end{eqnarray}$$
For the proof of (5.1), let
$$\begin{eqnarray}f=\mathop{\sum }_{(\,\boldsymbol{j},\boldsymbol{m})\in {\mathcal{D}}^{d+1}}a_{\boldsymbol{j},\boldsymbol{m}}g_{\boldsymbol{j},\boldsymbol{m}}\end{eqnarray}$$
be the Haar decomposition of
$f$
which converges in
$L_{2}$
and, therefore, almost everywhere. For each
$(\,\boldsymbol{j},\boldsymbol{m})\in {\mathcal{D}}^{d+1}$
with
$\,\boldsymbol{j}=(j_{1},\ldots ,j_{d},j_{d+1})$
and
$\boldsymbol{m}=(m_{1},\ldots ,m_{d},m_{d+1})$
, we let
$\,\boldsymbol{j}_{\ast }=(j_{1},\ldots ,j_{d})$
and
$\boldsymbol{m}_{\ast }=(m_{1},\ldots ,m_{d})$
. Then
$$\begin{eqnarray}f(\cdot ,t_{d+1})=\mathop{\sum }_{(\,\boldsymbol{j}_{\ast },\boldsymbol{m}_{\ast })\in {\mathcal{D}}^{d}}b_{\boldsymbol{j}_{\ast },\boldsymbol{m}_{\ast }}(t_{d+1})g_{\boldsymbol{j}_{\ast },\boldsymbol{m}_{\ast }}\end{eqnarray}$$
in
$L_{2}([0,1]^{d})$
for almost every
$t_{d+1}\in [0,1]$
, where
$$\begin{eqnarray}b_{\boldsymbol{j}_{\ast },\boldsymbol{m}_{\ast }}(t_{d+1})=\mathop{\sum }_{(j_{d+1},m_{d+1})\in {\mathcal{D}}^{1}}a_{\boldsymbol{j},\boldsymbol{m}}g_{j_{d+1},m_{d+1}}(t_{d+1}).\end{eqnarray}$$
It follows that
$$\begin{eqnarray}\Vert f(\cdot ,t_{d+1})|{\mathcal{D}}_{0}^{d}\Vert ^{2}=\mathop{\sum }_{(\,\boldsymbol{j}_{\ast },\boldsymbol{m}_{\ast })\in {\mathcal{D}}_{0}^{d}}b_{\boldsymbol{j}_{\ast },\boldsymbol{m}_{\ast }}(t_{d+1})^{2}.\end{eqnarray}$$
By integrating over
$t_{d+1}\in [0,1]$
and using the orthogonality of the one-dimensional Haar system we finally conclude that
$$\begin{eqnarray}\displaystyle \int _{0}^{1}\Vert f(\cdot ,t_{d+1})|{\mathcal{D}}_{0}^{d}\Vert ^{2}\,dt_{d+1} & = & \displaystyle \mathop{\sum }_{(\,\boldsymbol{j}_{\ast },\boldsymbol{m}_{\ast })\in {\mathcal{D}}_{0}^{d}}\int _{0}^{1}b_{\boldsymbol{j}_{\ast },\boldsymbol{m}_{\ast }}(t_{d+1})^{2}\,dt_{d+1}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{(\,\boldsymbol{j}_{\ast },\boldsymbol{m}_{\ast })\in {\mathcal{D}}_{0}^{d}}\,\mathop{\sum }_{(j_{d+1},m_{d+1})\in {\mathcal{D}}^{1}}a_{\boldsymbol{j},\boldsymbol{m}}^{2}=\Vert f|{\mathcal{E}}^{d+1}\Vert ^{2}.\square\nonumber\end{eqnarray}$$
Additionally, we need the following lower bound for finite point sets.
Proposition 5.3. For every
$d\in \mathbb{N}$
there exists a positive constant
$c_{d}>0$
with the following property: for every integer
$N\geqslant 2$
and every
$N$
-element point set
${\mathcal{P}}_{N,d}$
in
$[0,1)^{d}$
we have
$$\begin{eqnarray}\Vert D_{{\mathcal{P}}_{N,d}}|{\mathcal{D}}_{0}^{d}\Vert \geqslant c_{d}\,N^{-1}(\log N)^{(d-1)/2}.\end{eqnarray}$$
This has been shown in [Reference Bilyk, Lacey, Parissis and Vagharshakyan2] for
$d=2$
and [Reference Bilyk and Markhasin4] for
$d\geqslant 3$
with the
$\text{BMO}^{d}$
-norm instead of the
${\mathcal{D}}_{0}^{d}$
-norm. But the proofs actually work literally for the
${\mathcal{D}}_{0}^{d}$
-norm. The proof of the following result relies on Proinov’s idea.
Lemma 5.4. For
$d\in \mathbb{N}$
let
${\mathcal{S}}_{d}=(\boldsymbol{y}_{k})_{k\geqslant 0}$
, where
$\boldsymbol{y}_{k}=(y_{1,k},\ldots ,y_{d,k})$
for
$k\in \mathbb{N}_{0}$
, be an arbitrary sequence in
$[0,1)^{d}$
. Then for every
$N\in \mathbb{N}$
there exists an
$n\in \{1,2,\ldots ,N\}$
such that
$$\begin{eqnarray}n\Vert D_{{\mathcal{S}}_{d}}^{n}|{\mathcal{D}}_{0}^{d}\Vert +1\geqslant N\Vert D_{{\mathcal{P}}_{N,d+1}}|{\mathcal{D}}_{0}^{d+1}\Vert\end{eqnarray}$$
where
${\mathcal{P}}_{N,d+1}$
is the finite point set in
$[0,1)^{d+1}$
consisting of the points
$$\begin{eqnarray}\boldsymbol{x}_{k}=(y_{1,k},\ldots ,y_{d,k},k/N)\quad \text{for }k=0,1,\ldots ,N-1.\end{eqnarray}$$
Proof. Choose
$n\in \{1,2,\ldots ,N\}$
such that
$$\begin{eqnarray}\Vert nD_{{\mathcal{S}}_{d}}^{n}|{\mathcal{D}}_{0}^{d}\Vert =\max _{k=1,2,\ldots ,N}\Vert kD_{{\mathcal{S}}_{d}}^{k}|{\mathcal{D}}_{0}^{d}\Vert .\end{eqnarray}$$
Consider a subinterval of the
$(d+1)$
-dimensional unit cube of the form
$E=\prod _{i=1}^{d+1}[0,t_{i})$
with
$\boldsymbol{t}=(t_{1},t_{2},\ldots ,t_{d+1})\in [0,1)^{d+1}$
and put
$$\begin{eqnarray}m=m(t_{d+1}):=\lceil Nt_{d+1}\rceil \in \{1,2,\ldots ,N\}.\end{eqnarray}$$
Then a point
$\boldsymbol{x}_{k}$
,
$k=0,1,\ldots ,N-1$
, belongs to
$E$
, if and only if
$\boldsymbol{y}_{k}\in \prod _{i=1}^{d}[0,t_{i})$
and
$0\leqslant k<Nt_{d+1}$
. Writing
$E_{\ast }=\prod _{i=1}^{d}[0,t_{i})$
we have
$$\begin{eqnarray}\mathop{\sum }_{\boldsymbol{z}\in {\mathcal{P}}_{N,d+1}}\unicode[STIX]{x1D712}_{E}(\boldsymbol{z})=\mathop{\sum }_{\boldsymbol{y}\in {\mathcal{P}}_{m,d}}\unicode[STIX]{x1D712}_{E_{\ast }}(\boldsymbol{y}),\end{eqnarray}$$
where
${\mathcal{P}}_{m,d}$
is the point set which consists of the first
$m$
terms of the sequence
${\mathcal{S}}_{d}$
. Therefore we have
$$\begin{eqnarray}\displaystyle ND_{{\mathcal{P}}_{N,d+1}}(\boldsymbol{t}) & = & \displaystyle \mathop{\sum }_{\boldsymbol{z}\in {\mathcal{P}}_{N,d+1}}\unicode[STIX]{x1D712}_{E}(\boldsymbol{z})-Nt_{1}t_{2}\cdots t_{d+1}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{\boldsymbol{y}\in {\mathcal{P}}_{m,d}}\unicode[STIX]{x1D712}_{E_{\ast }}(\boldsymbol{y})-mt_{1}t_{2}\cdots t_{d}+mt_{1}t_{2}\cdots t_{d}-Nt_{1}t_{2}\cdots t_{d+1}\nonumber\\ \displaystyle & = & \displaystyle mD_{{\mathcal{P}}_{m,d}}(\boldsymbol{t}_{\ast })+t_{1}t_{2}\cdots t_{d}(m-Nt_{d+1}),\nonumber\end{eqnarray}$$
where
$\boldsymbol{t}_{\ast }=(t_{1},\ldots ,t_{d})$
. With
$$\begin{eqnarray}\unicode[STIX]{x1D711}(\boldsymbol{t})=t_{1}t_{2}\cdots t_{d}(m-Nt_{d+1})=t_{1}t_{2}\cdots t_{d}(m(t_{d+1})-Nt_{d+1})\end{eqnarray}$$
we obtain
$$\begin{eqnarray}ND_{{\mathcal{P}}_{N,d+1}}(\boldsymbol{t})=mD_{{\mathcal{P}}_{m,d}}(\boldsymbol{t}_{\ast })+\unicode[STIX]{x1D711}(\boldsymbol{t}).\end{eqnarray}$$
From the definition of
$m$
it is clear that
$|m-Nt_{d+1}|\leqslant 1$
and, therefore, also
$|\unicode[STIX]{x1D711}(\boldsymbol{t})|\leqslant 1$
. It follows that
$$\begin{eqnarray}\displaystyle N\Vert D_{{\mathcal{P}}_{N,d+1}}|{\mathcal{D}}_{0}^{d+1}\Vert & {\leqslant} & \displaystyle \Vert mD_{{\mathcal{S}}_{d}}^{m}|{\mathcal{D}}_{0}^{d+1}\Vert +\Vert \unicode[STIX]{x1D711}|{\mathcal{D}}_{0}^{d+1}\Vert \nonumber\\ \displaystyle & {\leqslant} & \displaystyle \Vert mD_{{\mathcal{S}}_{d}}^{m}|{\mathcal{D}}_{0}^{d+1}\Vert +\Vert \unicode[STIX]{x1D711}|L_{2}\Vert \leqslant \Vert mD_{{\mathcal{S}}_{d}}^{m}|{\mathcal{D}}_{0}^{d+1}\Vert +1.\nonumber\end{eqnarray}$$
Using Lemma 5.2 we obtain
$$\begin{eqnarray}\Vert m(\cdot )D_{{\mathcal{S}}_{d}}^{m(\cdot )}|{\mathcal{D}}_{0}^{d+1}\Vert +1\leqslant \sup _{t_{d+1}\in [0,1]}\Vert m(t_{d+1})D_{{\mathcal{S}}_{d}}^{m(t_{d+1})}|{\mathcal{D}}_{0}^{d}\Vert +1\leqslant \Vert nD_{{\mathcal{S}}_{d}}^{n}|{\mathcal{D}}_{0}^{d}\Vert +1.\end{eqnarray}$$
This implies the result. ◻
Now we can give the proof of Lemma 5.1 which also finishes the proof of equation (2.2) in Theorem 2.1.
Proof of Lemma 5.1.
We use the notation from Lemma 5.4. For the finite point set
${\mathcal{P}}_{N,d+1}$
in
$[0,1)^{d+1}$
we obtain from Proposition 5.3 that
$$\begin{eqnarray}N\Vert D_{{\mathcal{P}}_{N,d+1}}|{\mathcal{D}}_{0}^{d+1}\Vert \geqslant c_{d+1}(\log N)^{d/2}\end{eqnarray}$$
for some real
$c_{d+1}>0$
which is independent of
$N$
. According to Lemma 5.4 there exists an
$n\in \{1,2,\ldots ,N\}$
such that
$$\begin{eqnarray}n\Vert D_{{\mathcal{S}}_{d}}^{n}|{\mathcal{D}}_{0}^{d}\Vert +1\geqslant N\Vert D_{{\mathcal{P}}_{N,d+1}}|{\mathcal{D}}_{0}^{d+1}\Vert \geqslant c_{d+1}(\log N)^{d/2}.\end{eqnarray}$$
Thus we have shown that for every
$N\in \mathbb{N}$
there exists an
$n\in \{1,2,\ldots ,N\}$
such that
$$\begin{eqnarray}n\Vert D_{{\mathcal{S}}_{d}}^{n}|{\mathcal{D}}_{0}^{d}\Vert +1\geqslant c_{d+1}(\log n)^{d/2}.\end{eqnarray}$$
It remains to show that (5.5) holds for infinitely many
$n\in \mathbb{N}$
. Assume to the contrary that (5.5) holds for finitely many
$n\in \mathbb{N}$
only and let
$m$
be the largest integer with this property. Then choose
$N\in \mathbb{N}$
large enough such that
$$\begin{eqnarray}c_{d+1}(\log N)^{d/2}>\max _{k=1,2,\ldots ,m}k\Vert D_{{\mathcal{S}}_{d}}^{k}|{\mathcal{D}}_{0}^{d}\Vert +1.\end{eqnarray}$$
For this
$N$
we can find an
$n\in \{1,2,\ldots ,N\}$
for which (5.4) and (5.5) hold true. However, (5.4) implies that
$n>m$
which leads to a contradiction since
$m$
is the largest integer such that (5.5) is true. Thus we have shown that (5.5) holds for infinitely many
$n\in \mathbb{N}$
and this completes the proof. ◻
5.2 The proof of the lower bounds in Theorems 3.1 and 3.2
Before we give the proof we collect some auxiliary results.
Lemma 5.5. Let
$p,q\in (0,\infty )$
and
$0\leqslant s<1/p$
. For every
$d\in \mathbb{N}$
there exists a positive constant
$c_{p,q,s,d}>0$
with the following property: for every infinite sequence
${\mathcal{S}}_{d}$
in
$[0,1)^{d}$
and every
$N\in \mathbb{N}$
we have
$$\begin{eqnarray}\Vert D_{{\mathcal{S}}_{d}}^{N}|S_{p,q}^{s}B([0,1)^{d})\Vert \geqslant c_{p,q,s,d}\,N^{s-1}(\log N)^{(d-1)/q}.\end{eqnarray}$$
Proof. We apply Proposition 3.4 and the now classical idea of Roth’s proof of the bound on the
$L_{2}$
-discrepancy [Reference Roth32]. Fix an arbitrary infinite sequence
${\mathcal{S}}_{d}$
. Then for every
$N\in \mathbb{N}$
we can choose
$n\in \mathbb{N}$
such that
$2N\leqslant 2^{n}<4N$
. Let
$\,\boldsymbol{j}\in \mathbb{N}_{0}^{d}$
with
$|\,\boldsymbol{j}|=n$
. Then there are at least
$2^{n-1}=2^{|\,\boldsymbol{j}|-1}$
values of
$\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}$
for which
$I_{\boldsymbol{j},\boldsymbol{m}}\cap {\mathcal{P}}_{N,d}=\emptyset$
, where
${\mathcal{P}}_{N,d}$
is again the set consisting of the first
$N$
elements of
${\mathcal{S}}_{d}$
. For such
$I_{\boldsymbol{j},\boldsymbol{m}}$
which do not contain any points of
${\mathcal{P}}_{N,d}$
we give the Haar coefficients as
$|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{j},\boldsymbol{m}}\rangle |\asymp 2^{-2|\,\boldsymbol{j}|}$
, relying on Lemma 4.8 and 4.9. We apply Proposition 3.4 to obtain (with some constant
$c>0$
)
$$\begin{eqnarray}\displaystyle \Vert D_{{\mathcal{S}}_{d}}^{N}|S_{p,q}^{s}B([0,1)^{d})\Vert ^{q} & \asymp & \displaystyle \mathop{\sum }_{\boldsymbol{j}\in \mathbb{N}_{-1}^{d}}2^{|\,\boldsymbol{j}|(s-1/p+1)q}\biggl(\mathop{\sum }_{\boldsymbol{m}\in \mathbb{D}_{\boldsymbol{j}}}|\langle D_{{\mathcal{S}}_{d}}^{N},h_{\boldsymbol{j},\boldsymbol{m}}\rangle |^{p}\biggr)^{q/p}\nonumber\\ \displaystyle & {\geqslant} & \displaystyle c\,\mathop{\sum }_{|\,\boldsymbol{j}|=n}2^{|\,\boldsymbol{j}|(s-1/p+1)q}\,2^{-2|\,\boldsymbol{j}|q}\,2^{(|\,\boldsymbol{j}|-1)q/p}\nonumber\\ \displaystyle & \asymp & \displaystyle \mathop{\sum }_{|\,\boldsymbol{j}|=n}2^{|\,\boldsymbol{j}|(s-1)q}\asymp n^{d-1}2^{n(s-1)q}.\square\nonumber\end{eqnarray}$$
Lemma 5.6. Let
$p,q\in (0,\infty )$
. Let
$f:[0,1]^{d+1}\rightarrow \mathbb{R}$
be in
$S_{p,q}^{0}B([0,1]^{d})$
. Then we have
$$\begin{eqnarray}\Vert f|S_{p,q}^{0}B([0,1]^{d+1})\Vert \leqslant \sup _{t_{d+1}\in [0,1]}\Vert f(\cdot ,t_{d+1})|S_{p,q}^{0}B([0,1]^{d})\Vert .\end{eqnarray}$$
Proof. We write
$\langle f,g\rangle _{d}$
to keep track of the dimension. We have
$$\begin{eqnarray}\displaystyle |\langle f,h_{\boldsymbol{j},\boldsymbol{m}}\rangle _{d+1}| & = & \displaystyle |\langle \langle f,h_{\boldsymbol{j}^{\prime },\boldsymbol{m}^{\prime }}\rangle _{d},h_{\boldsymbol{j}_{d+1},\boldsymbol{m}_{d+1}}\rangle _{1}|\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \sup _{t_{d+1}\in [0,1]}|\langle f(\cdot ,t_{d+1}),h_{\boldsymbol{j}^{\prime },\boldsymbol{m}^{\prime }}\rangle _{d}|2^{-\text{max}(j_{d+1},0)}.\nonumber\end{eqnarray}$$
The result then follows from the fact that
$\mathbb{D}_{j_{d+1}}$
contains
$2^{j_{d+1}}$
elements and Proposition 3.4.◻
We need the following lower bound for finite point sets from [Reference Triebel40].
Proposition 5.7. For every
$d\in \mathbb{N}$
and all
$1\leqslant p,q<\infty$
and
$1/p-1<s<1/p$
there exists a positive constant
$c_{p,q,s,d}>0$
with the following property: for every integer
$N\geqslant 2$
and every
$N$
-element point set
${\mathcal{P}}_{N,d}$
in
$[0,1)^{d}$
we have
$$\begin{eqnarray}\Vert D_{{\mathcal{P}}_{N,d}}|S_{p,q}^{s}B([0,1)^{d})\Vert \geqslant c_{p,q,s,d}\,N^{s-1}\,(\log N)^{(d-1)/q}.\end{eqnarray}$$
Lemma 5.8. Let
$1\leqslant p,q<\infty$
. For
$d\in \mathbb{N}$
let
${\mathcal{S}}_{d}=(\boldsymbol{y}_{k})_{k\geqslant 0}$
, where
$\boldsymbol{y}_{k}=(y_{1,k},\ldots ,y_{d,k})$
for
$k\in \mathbb{N}_{0}$
, be an arbitrary sequence in
$[0,1)^{d}$
. Then for every
$N\in \mathbb{N}$
there exists an
$n\in \{1,2,\ldots ,N\}$
such that
$$\begin{eqnarray}n\Vert D_{{\mathcal{S}}_{d}}^{n}|S_{p,q}^{0}B([0,1)^{d})\Vert +1\geqslant N\Vert D_{{\mathcal{P}}_{N,d+1}}|S_{p,q}^{0}B([0,1)^{d+1})\Vert ,\end{eqnarray}$$
where
${\mathcal{P}}_{N,d+1}$
is the finite point set in
$[0,1)^{d+1}$
consisting of the points
$$\begin{eqnarray}\boldsymbol{x}_{k}=(y_{1,k},\ldots ,y_{d,k},k/N)\quad \text{for }k=0,1,\ldots ,N-1.\end{eqnarray}$$
Proof. The proof is analogous to the proof of Lemma 5.4. We choose
$n\in \{1,2,\ldots ,N\}$
such that
$$\begin{eqnarray}\Vert nD_{{\mathcal{S}}_{d}}^{n}|S_{p,q}^{0}B([0,1)^{d})\Vert =\max _{k=1,\ldots ,N}\Vert kD_{{\mathcal{S}}_{d}}^{k}|S_{p,q}^{0}B([0,1)^{d})\Vert .\end{eqnarray}$$
For
$\boldsymbol{t}\in [0,1)^{d+1}$
we have (5.3)
$$\begin{eqnarray}ND_{{\mathcal{P}}_{N,d+1}}(\boldsymbol{t})=mD_{{\mathcal{P}}_{m,d}}(\boldsymbol{t}_{\ast })+\unicode[STIX]{x1D711}(\boldsymbol{t})\end{eqnarray}$$
(see the proof of Lemma 5.4 for the notation). Then analogously to the proof of Lemma 5.4 we show that
$$\begin{eqnarray}N\Vert D_{{\mathcal{P}}_{N,d+1}}|S_{p,q}^{0}B([0,1)^{d+1})\Vert \leqslant \Vert mD_{{\mathcal{S}}_{d}}^{m}|S_{p,q}^{0}B([0,1)^{d+1})\Vert +1.\end{eqnarray}$$
Finally we use Lemma 5.6 to obtain
$$\begin{eqnarray}\displaystyle \Vert m(\cdot )D_{{\mathcal{S}}_{d}}^{m(\cdot )}|S_{p,q}^{0}B([0,1)^{d+1})\Vert & {\leqslant} & \displaystyle \sup _{t_{d+1}\in [0,1]}\Vert m(t_{d+1})D_{{\mathcal{S}}_{d}}^{m(t_{d+1})}|S_{p,q}^{0}B([0,1)^{d})\Vert \nonumber\\ \displaystyle & {\leqslant} & \displaystyle \Vert nD_{{\mathcal{S}}_{d}}^{n}|S_{p,q}^{0}B([0,1)^{d})\Vert .\square\nonumber\end{eqnarray}$$
Proof of equations (3.3) and (3.5) in Theorem 3.1.
The case where
$s>0$
is covered by Lemma 5.5, hence we only have to consider the case
$s=0$
. We use the notation from Lemma 5.4. For the finite point set
${\mathcal{P}}_{N,d+1}$
in
$[0,1)^{d+1}$
we obtain from Proposition 5.7 that
$$\begin{eqnarray}N\Vert D_{{\mathcal{P}}_{N,d+1}}|S_{p,q}^{0}B([0,1)^{d+1})\Vert \geqslant c_{p,q,0,d+1}(\log N)^{d/q}\end{eqnarray}$$
for some constant
$c_{p,q,0,d+1}>0$
which is independent of
$N$
. Now we apply Lemma 5.8 and obtain an
$n\in \{1,2,\ldots ,N\}$
such that
$$\begin{eqnarray}\displaystyle n\Vert D_{{\mathcal{S}}_{d}}^{n}|S_{p,q}^{0}B([0,1)^{d})\Vert +1 & {\geqslant} & \displaystyle N\Vert D_{{\mathcal{P}}_{N,d+1}}|S_{p,q}^{0}B([0,1)^{d+1})\Vert \nonumber\\ \displaystyle & {\geqslant} & \displaystyle c_{p,q,0,d+1}(\log N)^{d/q}.\end{eqnarray}$$
The proof that there are infinitely many
$n\in \mathbb{N}$
for which the (5.6) holds works analogously to the proof of Lemma 5.1.◻
Proof of equations (3.9) and (3.11) in Theorem 3.2.
We apply Proposition 3.3, namely
$S_{p,q}^{s}F{\hookrightarrow}S_{\min (p,q),q}^{s}B$
and we have for a constant
$c>0$
from Theorem 3.1
$$\begin{eqnarray}\displaystyle & & \displaystyle \Vert D_{{\mathcal{S}}_{d}}^{N}|S_{p,q}^{s}F\Vert \nonumber\\ \displaystyle & & \displaystyle \qquad \geqslant c\,\Vert D_{{\mathcal{S}}_{d}}^{N}|S_{\min (p,q),q}^{s}B\Vert \nonumber\\ \displaystyle & & \displaystyle \qquad \geqslant c_{p,q,s,d}\,\left\{\begin{array}{@{}ll@{}}N^{-1}\,(\log N)^{d/q}\quad & \text{ if }s=0,\\ N^{(s-1)}\,(\log N)^{(d-1)/q}\quad & \text{ if }0<s<1/\text{min}(p,q).\square\end{array}\right.\nonumber\end{eqnarray}$$
Acknowledgements
The authors would like to thank William Chen for his very helpful remarks and suggestions.
