# Point sets with optimal order of extreme and periodic discrepancy

Ralph Kritzinger and Friedrich Pillichshammer The first author is supported by
the Austrian Science Fund (FWF), Project F5509-N26, which is a part of the
Special Research Program “Quasi-Monte Carlo Methods: Theory and Applications”.

###### Abstract

We study the extreme and the periodic $L_{p}$ discrepancy of point sets in the
$d$-dimensional unit cube. The extreme discrepancy uses arbitrary sub-
intervals of the unit cube as test sets, whereas the periodic discrepancy is
based on periodic intervals modulo one. This is in contrast to the classical
star discrepancy, which uses exclusively intervals that are anchored in the
origin as test sets. In a recent paper the authors together with Aicke
Hinrichs studied relations between the $L_{2}$ versions of these notions of
discrepancy and presented exact formulas for typical two-dimensional quasi-
Monte Carlo point sets. In this paper we study the general $L_{p}$ case and
deduce the exact order of magnitude of the respective minimal discrepancy in
the number $N$ of elements of the considered point sets, for arbitrary but
fixed dimension $d$, which is $(\log N)^{(d-1)/2}$.

Keywords: $L_{p}$ discrepancy, diaphony, digital nets MSC 2020: 11K38, 11K06,
11K31

##  1 Introduction

Let
$\mathcal{P}=\\{\boldsymbol{x}_{0},\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{N-1}\\}$
be an arbitrary $N$-element point set in the $d$-dimensional unit cube
$[0,1)^{d}$. For any measurable subset $B$ of $[0,1]^{d}$ the counting
function

$A(B,\mathcal{P}):=|\\{n\in\\{0,1,\ldots,N-1\\}\ :\ \boldsymbol{x}_{n}\in
B\\}|$

counts the number of elements from $\mathcal{P}$ that belong to the set $B$.
The local discrepancy of $\mathcal{P}$ with respect to a given measurable
“test set” $B$ is then given by

$A(B,\mathcal{P})-N\lambda(B),$

where $\lambda$ denotes the Lebesgue measure of $B$. A global discrepancy
measure is then obtained by considering a norm of the local discrepancy with
respect to a fixed class of test sets.

The classical star $L_{p}$ discrepancy uses as test sets exclusively the class
of axis-parallel squares that are anchored in the origin. The formal
definition is

$L_{p,N}^{{\rm
star}}(\mathcal{P}):=\left(\int_{[0,1]^{d}}\left|A([\boldsymbol{0},\boldsymbol{t}),\mathcal{P})-N\lambda([\boldsymbol{0},\boldsymbol{t}))\right|^{p}\,\mathrm{d}\boldsymbol{t}\right)^{1/p},$

where for $\boldsymbol{t}=(t_{1},t_{2},\ldots,t_{d})\in[0,1]^{d}$ we set
$[\boldsymbol{0},\boldsymbol{t})=[0,t_{1})\times[0,t_{2})\times\ldots\times[0,t_{d})$
with area $\lambda([\boldsymbol{0},\boldsymbol{t}))=t_{1}t_{2}\cdots t_{d}$.

The extreme $L_{p}$ discrepancy uses as test sets arbitrary axis-parallel
rectangles contained in the unit square. For
$\boldsymbol{x}=(x_{1},x_{2},\ldots,x_{d})$ and
$\boldsymbol{y}=(y_{1},y_{2},\ldots,y_{d})$ in $[0,1]^{d}$ and
$\boldsymbol{x}\leq\boldsymbol{y}$ let
$[\boldsymbol{x},\boldsymbol{y})=[x_{1},y_{1})\times[x_{2},y_{2})\times\ldots\times[x_{d},y_{d})$,
where $\boldsymbol{x}\leq\boldsymbol{y}$ means $x_{j}\leq y_{j}$ for all
$j\in\\{1,2,\ldots,d\\}$. The extreme $L_{p}$ discrepancy of $\mathcal{P}$ is
then defined as

$L_{p,N}^{\mathrm{extr}}(\mathcal{P}):=\left(\int_{[0,1]^{d}}\int_{[0,1]^{d},\,\boldsymbol{x}\leq\boldsymbol{y}}\left|A([\boldsymbol{x},\boldsymbol{y}),\mathcal{P})-N\lambda([\boldsymbol{x},\boldsymbol{y}))\right|^{p}\,\mathrm{d}\boldsymbol{x}\,\mathrm{d}\boldsymbol{y}\right)^{1/p}.$

Note that the only difference between standard and extreme $L_{p}$ discrepancy
is the use of anchored and arbitrary rectangles in $[0,1]^{d}$, respectively.

The periodic $L_{p}$ discrepancy uses periodic rectangles as test sets, which
are defined as follows: For $x,y\in[0,1]$ set

$I(x,y)=\begin{cases}[x,y)&\text{if $x\leq y$},\\\ [0,y)\cup[x,1)&\text{if
$x>y$,}\end{cases}$

and for $\boldsymbol{x},\boldsymbol{y}$ as above we set
$B(\boldsymbol{x},\boldsymbol{y})=I(x_{1},y_{1})\times
I(x_{2},y_{2})\times\ldots\times I(x_{d},y_{d})$. We define the periodic
$L_{p}$ discrepancy of $\mathcal{P}$ as

$L_{p,N}^{\mathrm{per}}(\mathcal{P}):=\left(\int_{[0,1]^{d}}\int_{[0,1]^{d}}\left|A(B(\boldsymbol{x},\boldsymbol{y}),\mathcal{P})-N\lambda(B(\boldsymbol{x},\boldsymbol{y}))\right|^{p}\,\mathrm{d}\boldsymbol{x}\,\mathrm{d}\boldsymbol{y}\right)^{1/p}.$

All three notions of discrepancy are quantitative measures for the
irregularity of distribution of point sets modulo one. Also, these
discrepancies have close relations to the worst-case integration error of
quasi-Monte Carlo rules in suitable reproducing kernel Hilbert spaces of
functions over $[0,1]^{d}$; see, e.g., [18] and the references therein. In the
case $p=2$ and $d=2$ these discrepancies have been studied in the recent paper
[18]. The main results are exact formulas for the respective $L_{2}$
discrepancies for the Hammersley point set (see [18, Theorem 8]) and for
rational lattices (see [18, Theorem 10]).

### Relations.

Note that due to the monotonicity of the $L_{p}$-norm we have for $1\leq p\leq
q<\infty$ for every $N$-element point set $\mathcal{P}$ in $[0,1)^{d}$ that

$L_{p,N}^{\bullet}(\mathcal{P})\leq
L_{q,N}^{\bullet}(\mathcal{P}),\quad\mbox{where $\bullet\in\\{{\rm star},{\rm
extr},{\rm per}\\}$.}$

The following bounds and relations between star, extreme and periodic
discrepancies are known (see [18, Sections 1 and 2]): For every $N$-element
point set $\mathcal{P}$ in $[0,1)^{d}$ we have

$L_{2,N}^{{\rm extr}}(\mathcal{P})\leq L_{2,N}^{{\rm
per}}(\mathcal{P})\quad\mbox{ and }\quad L_{2,N}^{{\rm extr}}(\mathcal{P})\leq
L_{2,N}^{{\rm star}}(\mathcal{P}).$

The left relation can be easily generalized for arbitrary $p\geq 1$ to

$L_{p,N}^{{\rm extr}}(\mathcal{P})\leq L_{p,N}^{{\rm per}}(\mathcal{P}).$ (1)

Furthermore, there exists a quantity $c_{d}>0$ such that for every $N$-element
point set $\mathcal{P}$ in $[0,1)^{d}$ we have

$c_{d}(1+\log N)^{\frac{d-1}{2}}\leq L_{2,N}^{{\rm
extr}}(\mathcal{P})\leq\left\\{\begin{array}[]{l}L_{2,N}^{{\rm
per}}(\mathcal{P}),\\\\[5.0pt] L_{2,N}^{{\rm
star}}(\mathcal{P}).\end{array}\right.$ (2)

It is also well-known that for every $p\in(1,\infty)$ there exist $N$-element
point sets $\mathcal{P}$ in $[0,1)^{d}$ with the optimal order of star $L_{p}$
discrepancy, i.e., with

$L_{p,N}^{{\rm star}}(\mathcal{P})\leq C_{d,p}(1+\log N)^{\frac{d-1}{2}},$ (3)

where the positive quantity $C_{d,p}$ may only depend on $d$ and $p$ but is
independent of $N$. Explicit constructions are known and comprise certain
digital nets introduced by Chen and Skriganov [2] and Skriganov [29] and
higher order digital nets [4, 9, 10, 22].

So for $p=2$ the minimal extreme $L_{p}$ discrepancy for $N$-element point
sets in dimension $d$ is of exact order of magnitude $(1+\log
N)^{\frac{d-1}{2}}$. In more detail

$\inf_{\mathcal{P}\subseteq[0,1)^{d}\atop|\mathcal{P}|=N}L_{2,N}^{{\rm
extr}}(\mathcal{P})\asymp_{d}(1+\log N)^{\frac{d-1}{2}}.$ (4)

It is well-known that the same order of magnitude holds true for the star
$L_{p}$ discrepancy for any $p\in[2,\infty)$, see, e.g., [29]. For the
periodic discrepancy we only know the lower bound

$\inf_{\mathcal{P}\subseteq[0,1)^{d}\atop|\mathcal{P}|=N}L_{2,N}^{{\rm
per}}(\mathcal{P})\gtrsim_{d}(1+\log N)^{\frac{d-1}{2}};$ (5)

see, e.g., [18, Corollary 2] or [24]. A matching upper bound of the same order
of magnitude in arbitrary but fixed dimension is still missing (for more on
this we refer to Remark 12 in Section 4).

### Aim.

In this paper we continue our study of extreme and periodic discrepancy of
point sets in dimension $d$. In Section 3 we study the extreme $L_{p}$
discrepancy. The main tool is a Haar series approach in conjunction with the
Littlewood-Paley inequality. We show that for $p\in(1,\infty)$ the exact order
of the minimal extreme $L_{p}$ discrepancy for $N$-element point sets in
dimension $d$ is again $(1+\log N)^{\frac{d-1}{2}}$ (see Theorem 6). In
dimension $2$ we can even extend this result to $p=1$ (see Theorem 7 and
Corollary 8). Furthermore, as a byproduct, we find some easy proofs of already
known relations between standard and extreme discrepancy without going a
detour to numerical integration in function spaces as done in [18]. Finally,
with the help of the Haar series expansion of the extreme discrepancy we can
easily amplify our results about extreme discrepancy of $2$-dimensional point
sets beyond the Hammersley net. We prove exact formulas for the extreme
$L_{2}$ discrepancy of various digital nets in dimension 2 and show upper
bounds on the extreme $L_{p}$ discrepancy for the same nets (see Theorem 9).
The periodic discrepancy is studied in Section 4. The lower bound of order of
magnitude $(1+\log N)^{\frac{d-1}{2}}$ is easily established and follows
directly from the corresponding result for the extreme $L_{p}$ discrepancy
(see Corollary 11). Then we show that also the minimal periodic $L_{2}$
discrepancy ($p=2$) is of exact asymptotic order $(1+\log N)^{\frac{d-1}{2}}$
like the star and the extreme $L_{p}$ discrepancies and the optimal order of
magnitude can be achieved by means of digitally shifted digital nets (see
Theorem 15 and Corollary 17). The technical tool for this result is based on a
Walsh expansion of the periodic $L_{2}$ discrepancy. A corresponding result
beyond the case $p\leq 2$ is still missing. A consequence for the diaphony is
stated in Remark 18.

In Section 5 we briefly summarize the main results presented in this paper and
we also collect some open problems.

The constructions of point sets studied in this paper are based on the concept
of digitally shifted digital nets. We will recall the basic definitions in
Section 2. Readers who are familiar with this topic may move directly to
Section 3.

### Basic notations.

We denote by $\mathbb{N}$ the set of positive integers and by $\mathbb{N}_{0}$
the set of nonnegative integers, i.e., $\mathbb{N}_{0}=\mathbb{N}\cup\\{0\\}$.
For $d\in\mathbb{N}$ we write $[d]:=\\{1,2,\ldots,d\\}$. Subsets of $[d]$ are
denoted by $\mathfrak{u}$ or $\mathfrak{v}$. The complement of a subset
$\mathfrak{u}\subseteq[d]$ is $\mathfrak{u}^{c}=[d]\setminus\mathfrak{u}$.

For functions $f,g:D\subseteq\mathbb{N}\rightarrow\mathbb{R}^{+}$ we write
$g(N)\lesssim f(N)$ (or $g(N)\gtrsim f(N)$), if there exists a $C>0$ such that
$g(N)\leq Cf(N)$ (or $g(N)\geq Cf(N)$) for all $N\in D$. If we would like to
stress that the quantity $C$ may also depend on other variables than $N$, say
$\alpha_{1},\ldots,\alpha_{w}$, this will be indicated by writing
$\lesssim_{\alpha_{1},\ldots,\alpha_{w}}$ (or
$\gtrsim_{\alpha_{1},\ldots,\alpha_{w}}$). Furthermore, we also use
$f(N)\asymp g(N)$ which means that $f(N)\lesssim g(N)$ and $f(N)\gtrsim g(N)$
simultaneously.

##  2 Digital nets over $\mathbb{Z}_{b}$

The constructions of point sets considered in this paper are based on the
concept of digital nets which goes back to Niederreiter [27, 28]. There is a
whole theory on this type of constructions. Here we only present the most
basic definitions needed for the present paper. More information about digital
nets can be found in the books [8, 21, 28].

Throughout this paper let $b$ be a prime number and let $\mathbb{Z}_{b}$
denote the finite field with $b$ elements. We identify $\mathbb{Z}_{b}$ with
the set $\\{0,1,\ldots,b-1\\}$ equipped with arithmetic operations modulo $b$.

######  Definition 1.

Let $d,m\in\mathbb{N}$ and $t\in\\{0,1,\ldots,m\\}$. Choose $d$ $m\times m$
matrices $C_{1},\ldots,C_{d}$ over $\mathbb{Z}_{b}$ with the following
property: for any integers $\ell_{1},\ldots,\ell_{d}\in\mathbb{N}_{0}$ with
$\ell_{1}+\cdots+\ell_{d}=m-t$ the system of the

first |  $\ell_{1}$ rows of $C_{1}$, | together with the
---|---|---
$\vdots$
first |  $\ell_{d-1}$ rows of $C_{d-1}$, | together with the
first |  $\ell_{d}$ rows of $C_{d}$

is linearly independent over $\mathbb{Z}_{b}$.

Consider the following construction principle for point sets consisting of
$b^{m}$ points in $[0,1)^{d}$: represent $n\in\\{0,1,\ldots,b^{m}-1\\}$ in
base $b$, $n=n_{0}+n_{1}b+\cdots+n_{m-1}b^{m-1}$, where
$n_{j}\in\mathbb{Z}_{b}$ for $j\in\\{0,1,\ldots,m-1\\}$, and multiply the
matrix $C_{j}$, $j\in[d]$, with the digit-vector
$\vec{n}=(n_{0},\ldots,n_{m-1})^{\top}$,

$\displaystyle
C_{j}\vec{n}=:(y_{1}^{(j)},\ldots,y_{m}^{(j)})^{\top}\in\mathbb{Z}_{b}^{m}.$

Now set

$\displaystyle
x_{n}^{(j)}:=\frac{y_{1}^{(j)}}{b}+\cdots+\frac{y_{m}^{(j)}}{b^{m}}$

and

$\displaystyle\boldsymbol{x}_{n}=(x_{n}^{(1)},\ldots,x_{n}^{(d)}).$

The point set
$\\{\boldsymbol{x}_{0},\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{b^{m}-1}\\}$
is called a digital $(t,m,d)$-net over $\mathbb{Z}_{b}$ and the matrices
$C_{1},\ldots,C_{d}$ are called the generating matrices of the digital net.

We will also consider digitally shifted digital nets. In the following we
introduce the digital shift of depth $m$ for the one dimensional case. For
higher dimensions each coordinate is shifted independently and therefore one
just needs to apply the one dimensional shifting method to each coordinate
independently.

Let a point set $\mathcal{P}=\\{x_{0},\ldots,x_{N-1}\\}$ in $[0,1)$ be given.
Let

$x_{n}=\frac{x_{n,1}}{b}+\frac{x_{n,2}}{b^{2}}+\cdots+\frac{x_{n,m}}{b^{m}}$

be the binary digit expansion of $x_{n}$. Choose digits
$\sigma_{1},\ldots,\sigma_{m}\in\mathbb{Z}_{b}$ i.i.d. Then define

$z_{n,i}\equiv x_{n,i}+\sigma_{i}\pmod{b}\qquad\mbox{ for
}i\in\\{1,\ldots,m\\}$

with $z_{n,i}\in\mathbb{Z}_{b}$. Further, for $n\in\\{0,1,\ldots,N-1\\}$,
choose $\delta_{n}\in[0,\frac{1}{b^{m}})$ i.i.d. Then the randomized point set
$\widetilde{\mathcal{P}}=\\{z_{0},\ldots,z_{N-1}\\}$ is given by

$z_{n}=\frac{z_{n,1}}{b}+\cdots+\frac{z_{n,m}}{b^{m}}+\delta_{n}.$

This means we apply the same digital shift to the first $m$ digits, whereas
the following digits are shifted independently for each $x_{n}$. This kind of
shift is sometimes referred to as a digital shift of depth $m$ (see, e.g.,
[7]) and can be seen as a special case of the random $b$-ary digit-scrambling
of depth $m$ from [26, Section 2.4].

We will study the periodic $L_{2}$ discrepancy of digitally shifted digital
nets in Section 4. Sometimes, especially in dimension 2, the $\delta_{n}$ is
not needed and it suffices to consider digitally shifted digital nets of the
form $\widehat{\mathcal{P}}=\\{z_{0},\ldots,z_{b^{m}-1}\\}$ given by

$z_{n}=\frac{z_{n,1}}{b}+\cdots+\frac{z_{n,m}}{b^{m}}.$

Such nets will be also considered in Section 3.

##  3 The extreme discrepancy

Let $\mathcal{P}$ be a set of $N$ points in $[0,1)^{d}$. For
$\boldsymbol{x}\in[0,1]^{d}$ define

$D(\boldsymbol{x}):=A([\boldsymbol{0},\boldsymbol{x}),\mathcal{P})-N\lambda([\boldsymbol{0},\boldsymbol{x}))$

and for $\boldsymbol{x},\boldsymbol{y}\in[0,1]^{d}$ with
$\boldsymbol{x}\leq\boldsymbol{y}$ define

$\widetilde{D}(\boldsymbol{x},\boldsymbol{y})=A([\boldsymbol{x},\boldsymbol{y}),\mathcal{P})-N\lambda([\boldsymbol{x},\boldsymbol{y})).$

Obviously the interval $[\boldsymbol{x},\boldsymbol{y})$ can be written as a
union and difference of certain intervals anchored in the origin. This leads
to the following connection between the unanchored discrepancy function
$\widetilde{D}$ and the anchored version $D$. To state this relation, we
introduce some notation. For $\boldsymbol{x}=(x_{1},\ldots,x_{d})$,
$\boldsymbol{y}=(y_{1},\ldots,y_{d})$ and $\mathfrak{u}\subseteq[d]$ we define
the point
$(\boldsymbol{x}_{\mathfrak{u}},\boldsymbol{y}_{\mathfrak{u}^{c}}):=(z_{1},\ldots,z_{d})$,
where for $j\in[d]$ we put

$z_{j}=\left\\{\begin{array}[]{ll}x_{j}&\mbox{ if $j\in\mathfrak{u}$,}\\\
y_{j}&\mbox{ if $j\not\in\mathfrak{u}$.}\end{array}\right.$

Then, for $\boldsymbol{x}\leq\boldsymbol{y}$ we have

$\widetilde{D}(\boldsymbol{x},\boldsymbol{y})=\sum_{\mathfrak{u}\subseteq[d]}(-1)^{|\mathfrak{u}|}D((\boldsymbol{x}_{\mathfrak{u}},\boldsymbol{y}_{\mathfrak{u}^{c}})).$
(6)

We extend the right-hand side of (6) to arbitrary
$\boldsymbol{x},\boldsymbol{y}\in[0,1]^{d}$ (i.e., we do not demand
$\boldsymbol{x}\leq\boldsymbol{y}$) and write

$g(\boldsymbol{x},\boldsymbol{y})=\sum_{\mathfrak{u}\subseteq[d]}(-1)^{|\mathfrak{u}|}D((\boldsymbol{x}_{\mathfrak{u}},\boldsymbol{y}_{\mathfrak{u}^{c}})).$

For example, for $d=2$ we have

$g(x_{1},x_{2},y_{1},y_{2})=D(x_{1},x_{2})-D(x_{1},y_{2})-D(y_{1},x_{2})+D(y_{1},y_{2}).$

Note that for every $\mathfrak{v}\subseteq[d]$ we have

$(-1)^{|\mathfrak{v}|}g((\boldsymbol{x}_{\mathfrak{v}^{c}},\boldsymbol{y}_{\mathfrak{v}}),(\boldsymbol{x}_{\mathfrak{v}},\boldsymbol{y}_{\mathfrak{v}^{c}}))=g(\boldsymbol{x},\boldsymbol{y}).$
(7)

This can be seen in the following way: fix $\mathfrak{v}\subseteq[d]$ and take
an arbitrary vector
$(\boldsymbol{x}_{\mathfrak{u}},\boldsymbol{y}_{\mathfrak{u}^{c}})$ with
$\mathfrak{u}\subseteq[d]$. Now exchange $|\mathfrak{v}|$ many components
$x_{j}\leftrightarrow y_{j}$ for $j\in\mathfrak{v}$. Write
$\mathfrak{v}=\mathfrak{v}_{1}\cup\mathfrak{v}_{2}$ where
$\mathfrak{v}_{1}\subseteq\mathfrak{u}$ and
$\mathfrak{v}_{2}\subseteq\mathfrak{u}^{c}$. Then
$(\boldsymbol{x}_{\mathfrak{u}},\boldsymbol{y}_{\mathfrak{u}^{c}})$ in the
definition of $g(\boldsymbol{x},\boldsymbol{y})$ corresponds to

$(\boldsymbol{x}_{\mathfrak{u}\setminus\mathfrak{v}_{1}\cup\mathfrak{v}_{2}},\boldsymbol{y}_{\mathfrak{u}^{c}\setminus\mathfrak{v}_{2}\cup\mathfrak{v}_{1}})$

in the definition of
$g((\boldsymbol{x}_{\mathfrak{v}^{c}},\boldsymbol{y}_{\mathfrak{v}}),(\boldsymbol{x}_{\mathfrak{v}},\boldsymbol{y}_{\mathfrak{v}^{c}}))$.
But there might be a difference in the corresponding sign, since
$D((\boldsymbol{x}_{\mathfrak{u}},\boldsymbol{y}_{\mathfrak{u}^{c}}))$ appears
with the sign $(-1)^{|\mathfrak{u}|}$ in $g(\boldsymbol{x},\boldsymbol{y})$,
whereas
$D(\boldsymbol{x}_{\mathfrak{u}\setminus\mathfrak{v}_{1}\cup\mathfrak{v}_{2}},\boldsymbol{y}_{\mathfrak{u}^{c}\setminus\mathfrak{v}_{2}\cup\mathfrak{v}_{1}})$
has the sign
$(-1)^{|\mathfrak{u}\setminus\mathfrak{v}_{1}\cup\mathfrak{v}_{2}|}$ in the
definition of
$g((\boldsymbol{x}_{\mathfrak{v}^{c}},\boldsymbol{y}_{\mathfrak{v}}),(\boldsymbol{x}_{\mathfrak{v}},\boldsymbol{y}_{\mathfrak{v}^{c}}))$.
However, we have in any case that
$(-1)^{|\mathfrak{u}\setminus\mathfrak{v}_{1}\cup\mathfrak{v}_{2}|}=(-1)^{|\mathfrak{u}|+|\mathfrak{v}|}$,
because

$\displaystyle|\mathfrak{u}\setminus\mathfrak{v}_{1}\cup\mathfrak{v}_{2}|$
$\displaystyle=$
$\displaystyle|\mathfrak{u}\setminus\mathfrak{v}_{1}|+|\mathfrak{v}_{2}|$
$\displaystyle=$
$\displaystyle|\mathfrak{u}|-|\mathfrak{v}_{1}|+|\mathfrak{v}_{2}|$
$\displaystyle=$
$\displaystyle|\mathfrak{u}|-2|\mathfrak{v}_{1}|+|\mathfrak{v}|$
$\displaystyle\equiv$ $\displaystyle|\mathfrak{u}|+|\mathfrak{v}|\pmod{2}.$

and from this we observe easily the relation (7).

From (7) together with basic rules for integrals it follows that

$\displaystyle L_{p,N}^{\mathrm{extr}}(\mathcal{P})$ $\displaystyle=$
$\displaystyle\left(\int_{[0,1]^{d}}\int_{[0,1]^{d},\,\boldsymbol{x}\leq\boldsymbol{y}}|\widetilde{D}(\boldsymbol{x},\boldsymbol{y})|^{p}\,\mathrm{d}\boldsymbol{x}\,\mathrm{d}\boldsymbol{y}\right)^{1/p}$
(8) $\displaystyle=$
$\displaystyle\left(\frac{1}{2^{d}}\int_{[0,1]^{d}}\int_{[0,1]^{d}}|g(\boldsymbol{x},\boldsymbol{y})|^{p}\,\mathrm{d}\boldsymbol{x}\,\mathrm{d}\boldsymbol{y}\right)^{1/p}.$

Our aim is now to represent the extreme discrepancy in terms of Haar
functions. We introduce the basic definitions in the following paragraphs.

### The Haar function system (in base $2$).

To begin with, a dyadic interval of length $2^{-j},j\in{\mathbb{N}}_{0},$ in
$[0,1)$ is an interval of the form

$I=I_{j,m}:=\left[\frac{m}{2^{j}},\frac{m+1}{2^{j}}\right)\ \ \mbox{for }\
m=0,1,\ldots,2^{j}-1.$

We also define $I_{-1,0}:=[0,1)$. The left and right half of $I=I_{j,m}$ are
the dyadic intervals $I^{+}=I_{j,m}^{+}=I_{j+1,2m}$ and
$I^{-}=I_{j,m}^{-}=I_{j+1,2m+1}$, respectively. For $j\in\mathbb{N}_{0}$, the
Haar function $h_{I}=h_{j,m}$ with support $I$ is the function on $[0,1)$
which is $+1$ on the left half of $I$, $-1$ on the right half of $I$ and 0
outside of $I$. The $L_{\infty}$-normalized Haar system consists of all Haar
functions $h_{j,m}$ with $j\in{\mathbb{N}}_{0}$ and
$m\in\\{0,1,\ldots,2^{j}-1\\}$ together with the indicator function $h_{-1,0}$
of $[0,1)$. Normalized in $L_{2}([0,1))$ we obtain the orthonormal Haar basis
of $L_{2}([0,1))$. A crucial property of Haar functions we use in the
following is

$\int_{0}^{1}h_{j,m}(t)\,\mathrm{d}t=\begin{cases}1&\text{if $j=-1$,}\\\
0&\text{if $j\in\mathbb{N}_{0}$,}\end{cases}$

Let ${\mathbb{N}}_{-1}:=\\{-1,0,1,2,\ldots\\}$ and define
${\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},\dots,j_{d})\in{\mathbb{N}}_{-1}^{d}$ and
$\boldsymbol{m}=(m_{1},\dots,m_{d})\in{\mathbb{D}}_{\boldsymbol{j}}:={\mathbb{D}}_{j_{1}}\times\ldots\times{\mathbb{D}}_{j_{d}}$,
the Haar function $h_{\boldsymbol{j},\boldsymbol{m}}$ is given as the tensor
product

$h_{\boldsymbol{j},\boldsymbol{m}}(\boldsymbol{x}):=h_{j_{1},m_{1}}(x_{1})\,\cdots\,h_{j_{d},m_{d}}(x_{d})\
\ \ \mbox{ for }\boldsymbol{x}=(x_{1},\dots,x_{d})\in[0,1)^{d}.$

The boxes

$I_{\boldsymbol{j},\boldsymbol{m}}:=I_{j_{1},m_{1}}\times\ldots\times
I_{j_{d},m_{d}}$

are called dyadic boxes.

The $L_{\infty}$-normalized tensor Haar system consists of all Haar functions
$h_{\boldsymbol{j},\boldsymbol{m}}$ with
$\boldsymbol{j}\in{\mathbb{N}}_{-1}^{d}$ and
$\boldsymbol{m}\in{\mathbb{D}}_{\boldsymbol{j}}$. Normalized in
$L_{2}([0,1)^{d})$ we obtain the orthonormal Haar basis of $L_{2}([0,1)^{d})$.

Let $f\in L_{2}([0,1]^{d})$. Then Parseval’s identity states that

$\|f\|_{L_{2}([0,1]^{d})}=\sum_{\boldsymbol{j}\in\mathbb{N}_{-1}^{d}}2^{-|\boldsymbol{j}|}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}|\mu_{\boldsymbol{j},\boldsymbol{m}}(f)|^{2},$

where for $\boldsymbol{j}\in\mathbb{N}_{-1}^{d}$ and
$\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}$ the numbers

$\mu_{\boldsymbol{j},\boldsymbol{m}}(f):=\langle
f,h_{\boldsymbol{j},\boldsymbol{m}}\rangle=\int_{[0,1]^{d}}f(\boldsymbol{x})h_{\boldsymbol{j},\boldsymbol{m}}(\boldsymbol{x})\,\mathrm{d}\boldsymbol{x}$

are called the Haar coefficients of $f$.

### The Haar coefficients of the function $g$.

Let
$\boldsymbol{j}=(j_{1},\dots,j_{d},k_{1},\dots,k_{d})\in\mathbb{N}_{-1}^{2d}$
and $\boldsymbol{m}=(m_{1},\dots,m_{2d})\in\mathbb{D}_{\boldsymbol{j}}$. We
compute the Haar coefficient $\mu_{\boldsymbol{j},\boldsymbol{m}}(g)$ of $g$
which is defined as

$\mu_{\boldsymbol{j},\boldsymbol{m}}(g):=\int_{[0,1]^{d}}\int_{[0,1]^{d}}g(\boldsymbol{x},\boldsymbol{y})h_{\boldsymbol{j},\boldsymbol{m}}(\boldsymbol{x},\boldsymbol{y})\,\mathrm{d}\boldsymbol{x}\,\mathrm{d}\boldsymbol{y},$

where
$g(\boldsymbol{x},\boldsymbol{y})=g(x_{1},\dots,x_{d},y_{1},\dots,y_{d})$ and

$h_{\boldsymbol{j},\boldsymbol{m}}(\boldsymbol{x},\boldsymbol{y})=h_{j_{1},m_{1}}(x_{1})\cdots
h_{j_{d},m_{d}}(x_{d})h_{k_{1},m_{d+1}}(y_{1})\cdots h_{k_{d},m_{2d}}(y_{d}).$

######  Lemma 2.

Let $\boldsymbol{j}\in\mathbb{N}_{-1}^{2d}$ such that exactly $d$ components
of $\boldsymbol{j}$ are $-1$ and more precisely we have the following: for
every $i\in[d]$ we either have $j_{i}=-1$ or $k_{i}=-1$. Let
$\boldsymbol{j}^{\prime}=(j_{1}^{\prime},\dots,j_{d}^{\prime})\in\mathbb{N}_{0}^{d}$
such that for all $i\in[d]$ we have $j_{i}^{\prime}=\max\\{j_{i},k_{i}\\}$
(i.e. it is the number $j_{i}$ or $k_{i}$ which is not -1). Let further
$\boldsymbol{m}^{\prime}=(m_{1}^{\prime},\dots,m_{d}^{\prime})$ be such that
$m_{i}^{\prime}=m_{i}$ if $j_{i}^{\prime}=j_{i}$ and $m_{i}^{\prime}=m_{i+d}$
otherwise. Then we have

$|\mu_{\boldsymbol{j},\boldsymbol{m}}(g)|=|\mu_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}(D)|.$

In all other cases for $\boldsymbol{j}\in\mathbb{N}_{-1}^{2d}$ we have
$\mu_{\boldsymbol{j},\boldsymbol{m}}(g)=0$.

###### Proof.

Let $\boldsymbol{j}\in\mathbb{N}_{-1}^{2d}$. Assume that
$\kappa\in\\{0,1,\dots,2d\\}$ components of $\boldsymbol{j}$ are $-1$. We have

$\mu_{\boldsymbol{j},\boldsymbol{m}}(g)=\sum_{\mathfrak{u}\subseteq[d]}(-1)^{|\mathfrak{u}|}\left\langle
D((\boldsymbol{x}_{\mathfrak{u}},\boldsymbol{y}_{\mathfrak{u}^{c}})),h_{\boldsymbol{j},\boldsymbol{m}}\right\rangle,$

where

$\left\langle
D((\boldsymbol{x}_{\mathfrak{u}},\boldsymbol{y}_{\mathfrak{u}^{c}})),h_{\boldsymbol{j},\boldsymbol{m}}\right\rangle=\int_{[0,1]^{d}}\int_{[0,1]^{d}}D((\boldsymbol{x}_{\mathfrak{u}},\boldsymbol{y}_{\mathfrak{u}^{c}}))h_{\boldsymbol{j},\boldsymbol{m}}(\boldsymbol{x},\boldsymbol{y})\,\mathrm{d}\boldsymbol{x}\,\mathrm{d}\boldsymbol{y}.$

It is clear that for $\kappa<d$ we have $\left\langle
D((\boldsymbol{x}_{\mathfrak{u}},\boldsymbol{y}_{\mathfrak{u}^{c}})),h_{\boldsymbol{j},\boldsymbol{m}}\right\rangle=0$
for all $\mathfrak{u}\subseteq[d]$.

Next, let $\kappa>d$. Then, according to the pigeon-hole principle there
exists an $i\in[d]$ such that $j_{i}=k_{i}=-1$. Fix such an index $i$. Then we
have

$\displaystyle\mu_{\boldsymbol{j},\boldsymbol{m}}(g)=$
$\displaystyle\sum_{\mathfrak{u}\subseteq[d]}(-1)^{|\mathfrak{u}|}\left\langle
D((\boldsymbol{x}_{\mathfrak{u}},\boldsymbol{y}_{\mathfrak{u}^{c}})),h_{\boldsymbol{j},\boldsymbol{m}}\right\rangle$
$\displaystyle=$
$\displaystyle\sum_{\mathfrak{u}\subseteq[d]\setminus\\{i\\}}\left[(-1)^{|\mathfrak{u}|+1}\left\langle
D((\boldsymbol{x}_{\mathfrak{u}\cup\\{i\\}},\boldsymbol{y}_{\mathfrak{u}^{c}})),h_{\boldsymbol{j},\boldsymbol{m}}\right\rangle+(-1)^{|\mathfrak{u}|}\left\langle
D((\boldsymbol{x}_{\mathfrak{u}},\boldsymbol{y}_{\mathfrak{u}^{c}\cup\\{i\\}})),h_{\boldsymbol{j},\boldsymbol{m}}\right\rangle\right]$
$\displaystyle=$ $\displaystyle 0,$

since obviously

$\displaystyle\left\langle
D((\boldsymbol{x}_{\mathfrak{u}\cup\\{i\\}},\boldsymbol{y}_{\mathfrak{u}^{c}})),h_{\boldsymbol{j},\boldsymbol{m}}\right\rangle=\left\langle
D((\boldsymbol{x}_{\mathfrak{u}},\boldsymbol{y}_{\mathfrak{u}^{c}\cup\\{i\\}})),h_{\boldsymbol{j},\boldsymbol{m}}\right\rangle.$

This can be immediately seen observing that the integral over $y_{i}$ in the
first Haar coefficient has no effect (delivers a factor 1). The same is true
for $x_{i}$ in the second Haar coefficient. Now relabelling the variable
$y_{i}$ to $x_{i}$ in the second integral yields the above identity.

Finally, consider the case that $\kappa=d$. Let
$\boldsymbol{j}\in\mathbb{N}_{-1}^{2d}$ be such that for every $i\in[d]$ we
either have $j_{i}=-1$ or $k_{i}=-1$. Then there is exactly one subset
$\mathfrak{u}\subseteq[d]$ such that $\left\langle
D((\boldsymbol{x}_{\mathfrak{u}},\boldsymbol{y}_{\mathfrak{u}^{c}})),h_{\boldsymbol{j},\boldsymbol{m}}\right\rangle$
is not (necessarily) zero. This particular set $\mathfrak{u}$ consists of
exactly those indices $i\in[d]$ for which $k_{i}=-1$, i.e.

$\mathfrak{u}=\\{i\in[d]\ :\ k_{i}=-1\\}.$

For this set $\mathfrak{u}$ we have

$\left\langle
D((\boldsymbol{x}_{\mathfrak{u}},\boldsymbol{y}_{\mathfrak{u}^{c}})),h_{\boldsymbol{j},\boldsymbol{m}}\right\rangle=\mu_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}(D)$

with $\boldsymbol{j}^{\prime}$ and $\boldsymbol{m}^{\prime}$ given as above
and hence

$\mu_{\boldsymbol{j},\boldsymbol{m}}(g)=(-1)^{|\mathfrak{u}|}\mu_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}(D).$

From this the result follows and the proof is complete. ∎

### Haar representation of the extreme $L_{p}$ discrepancy.

Lemma 2 yields the following results on the extreme $L_{p}$ discrepancy of
point sets in $[0,1)^{d}$ which is crucial for most other results on extreme
discrepancy in this section.

######  Proposition 3.

Let $\mathcal{P}$ be an $N$-element point set in $[0,1)^{d}$ and $D$ its
anchored discrepancy function with Haar coefficients
$\mu_{\boldsymbol{j},\boldsymbol{m}}=\mu_{\boldsymbol{j},\boldsymbol{m}}(D)$
for $\boldsymbol{j}\in\mathbb{N}_{-1}^{d}$ and
$\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}$. Then we have

$(L_{2,N}^{\mathrm{extr}}(\mathcal{P}))^{2}=\sum_{\boldsymbol{j}\in\mathbb{N}_{0}^{d}}2^{|\boldsymbol{j}|}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}|\mu_{\boldsymbol{j},\boldsymbol{m}}|^{2}.$
(9)

For arbitrary $p\in(1,\infty)$ we have

$L_{p,N}^{\mathrm{extr}}(\mathcal{P})\asymp_{p,d}\left\|\left(\sum_{\boldsymbol{j}\in\mathbb{N}_{0}^{d}}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}2^{2|\boldsymbol{j}|}|\mu_{\boldsymbol{j},\boldsymbol{m}}|^{2}\,{\mathbf{1}}_{I_{\boldsymbol{j},\boldsymbol{m}}}\right)^{1/2}\right\|_{L_{p}([0,1]^{d})},$
(10)

where the implied factors depend only on $p$ and $d$, but not on $N$.

###### Proof.

First we prove the formula (9) for the extreme $L_{2}$ discrepancy. By (8),
Parseval’s identity and Lemma 2 we have

$\displaystyle(L_{2,N}^{\mathrm{extr}}(\mathcal{P}))^{2}=$
$\displaystyle\frac{1}{2^{d}}\|g\|_{L_{2}([0,1]^{2d})}^{2}$ $\displaystyle=$
$\displaystyle\frac{1}{2^{d}}\sum_{\boldsymbol{j}\in\mathbb{N}_{-1}^{2d}}2^{|\boldsymbol{j}|}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}|\mu_{\boldsymbol{j},\boldsymbol{m}}(g)|^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2^{d}}\sum_{\mathfrak{u}\subseteq[d]}\sum_{\boldsymbol{j}^{\prime}=(j_{1}^{\prime},\dots,j_{d}^{\prime})\in\mathbb{N}_{0}^{d}}\sum_{\begin{subarray}{c}\boldsymbol{j}=(j_{1},\dots,j_{d},k_{1},\dots,k_{d})\in\mathbb{N}_{-1}^{2d}\\\
\text{for\, }i\in[d]:\\\ (j_{i},k_{i})=(j_{i}^{\prime},-1)\text{\,if
\,}i\not\in\mathfrak{u}\\\ (j_{i},k_{i})=(-1,j_{i}^{\prime})\text{\,if
\,}i\in\mathfrak{u}\end{subarray}}2^{|\boldsymbol{j}^{\prime}|}\sum_{\boldsymbol{m}^{\prime}\in\mathbb{D}_{\boldsymbol{j}^{\prime}}}|\mu_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}(D)|^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2^{d}}\sum_{\mathfrak{u}\subseteq[d]}\sum_{\boldsymbol{j}^{\prime}\in\mathbb{N}_{0}^{d}}2^{|\boldsymbol{j}^{\prime}|}\sum_{\boldsymbol{m}^{\prime}\in\mathbb{D}_{\boldsymbol{j}^{\prime}}}|\mu_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}|^{2}$
$\displaystyle=$
$\displaystyle\sum_{\boldsymbol{j}^{\prime}\in\mathbb{N}_{0}^{d}}2^{|\boldsymbol{j}^{\prime}|}\sum_{\boldsymbol{m}^{\prime}\in\mathbb{D}_{\boldsymbol{j}^{\prime}}}|\mu_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}|^{2}.$

This completes the proof of (9).

In order to prove formula (10) for the extreme $L_{p}$ discrepancy we make use
of the Littlewood-Paley inequality which provides a tool which can be used to
replace Parseval’s equality and Bessel’s inequality for functions in
$L_{p}([0,1]^{d})$ with $p\in(1,\infty)$. It involves the square function
$S(f)$ of a function $f\in L_{p}([0,1]^{d})$ which is given as

$S(f)=\left(\sum_{\boldsymbol{j}\in\mathbb{N}_{-1}^{d}}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}2^{2|\boldsymbol{j}|}\,\langle
f,h_{\boldsymbol{j},\boldsymbol{m}}\rangle^{2}\,{\mathbf{1}}_{I_{\boldsymbol{j},\boldsymbol{m}}}\right)^{1/2},$

where ${\mathbf{1}}_{I}$ is the indicator function of $I$. Let
$p\in(1,\infty)$ and let $f\in L_{p}([0,1]^{d})$. Then the Littlewood-Paley
inequality states

$\|S(f)\|_{L_{p}}\asymp_{p,d}\|f\|_{L_{p}}.$

By (8), the Littlewood-Paley inequality and Lemma 2 we have similarly as in
the proof of (9) that

$\displaystyle L_{p,N}^{\mathrm{extr}}(\mathcal{P})$ $\displaystyle=$
$\displaystyle\frac{1}{2^{d/p}}\|g\|_{L_{p}([0,1]^{2d})}\asymp_{p,d}\|S(g)\|_{L_{p}([0,1]^{2d})}$
$\displaystyle=$
$\displaystyle\left\|\left(\sum_{\boldsymbol{j}\in\mathbb{N}_{-1}^{2d}}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}2^{2|\boldsymbol{j}|}|\mu_{\boldsymbol{j},\boldsymbol{m}}(g)|^{2}\,{\mathbf{1}}_{I_{\boldsymbol{j},\boldsymbol{m}}}\right)^{1/2}\right\|_{L_{p}([0,1]^{2d})}$
$\displaystyle=$
$\displaystyle\left\|\left(2^{d}\sum_{\boldsymbol{j}^{\prime}\in\mathbb{N}_{0}^{d}}\sum_{\boldsymbol{m}^{\prime}\in\mathbb{D}_{\boldsymbol{j}^{\prime}}}2^{2|\boldsymbol{j}^{\prime}|}|\mu_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}(D)|^{2}\,{\mathbf{1}}_{I_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}}\right)^{1/2}\right\|_{L_{p}([0,1]^{d})}$
$\displaystyle\asymp_{d}$
$\displaystyle\left\|\left(\sum_{\boldsymbol{j}^{\prime}\in\mathbb{N}_{0}^{d}}\sum_{\boldsymbol{m}^{\prime}\in\mathbb{D}_{\boldsymbol{j}^{\prime}}}2^{2|\boldsymbol{j}^{\prime}|}|\mu_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}|^{2}\,{\mathbf{1}}_{I_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}}\right)^{1/2}\right\|_{L_{p}([0,1]^{d})}.$

This completes the proof of Proposition 3. ∎

We deduce two corollaries from Proposition 3. First, one can see in the same
way as for the star $L_{p}$ discrepancy, that also the extreme $L_{p}$
discrepancy satisfies a general lower bound of Roth-type.

######  Corollary 4.

Let $p>1$. For every $N$-element point set $\mathcal{P}$ in $[0,1)^{d}$ we
have

$L_{p,N}^{{\rm extr}}(\mathcal{P})\gtrsim_{p,d}(1+\log N)^{\frac{d-1}{2}}.$

###### Proof.

Starting from Eq. (10) in Proposition 3 the proof follows exactly the lines of
[5, Proof of Theorem 3.6]. ∎

Since

$(L_{2,N}^{{\rm
star}}(\mathcal{P}))^{2}=\sum_{\boldsymbol{j}\in\mathbb{N}_{-1}^{d}}2^{|\boldsymbol{j}|}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}|\mu_{\boldsymbol{j},\boldsymbol{m}}|^{2},$

we immediately obtain $L_{2,N}^{\mathrm{extr}}(\mathcal{P})\leq L_{2,N}^{{\rm
star}}(\mathcal{P})$ for every point set $\mathcal{P}$ in $[0,1]^{d}$ as
recently discovered in [18] by relating these discrepancy notions to the
worst-case integration errors in certain Hilbert spaces. Now we can even
extend this result to some extent to general $p\in(1,\infty)$.

######  Corollary 5.

For every $p\in(1,\infty)$ and for every $N$-element point set $\mathcal{P}$
in $[0,1)^{d}$ we have

$L_{p,N}^{\mathrm{extr}}(\mathcal{P})\lesssim_{p,d}L_{p,N}^{\mathrm{star}}(\mathcal{P}).$

###### Proof.

Obviously,

$\displaystyle 0$ $\displaystyle\leq$
$\displaystyle\left(\sum_{\boldsymbol{j}\in\mathbb{N}_{0}^{d}}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}2^{2|\boldsymbol{j}|}|\mu_{\boldsymbol{j},\boldsymbol{m}}|^{2}\,{\mathbf{1}}_{I_{\boldsymbol{j},\boldsymbol{m}}}\right)^{1/2}$
$\displaystyle\leq$
$\displaystyle\left(\sum_{\boldsymbol{j}\in\mathbb{N}_{-1}^{d}}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}2^{2|\boldsymbol{j}|}|\mu_{\boldsymbol{j},\boldsymbol{m}}|^{2}\,{\mathbf{1}}_{I_{\boldsymbol{j},\boldsymbol{m}}}\right)^{1/2}.$

Since for $L_{p}$-functions $0\leq f\leq g$ we always have
$\|f\|_{L_{p}}\leq\|g\|_{L_{p}}$ we obtain

$\displaystyle L_{p,N}^{\mathrm{extr}}(\mathcal{P})$
$\displaystyle\lesssim_{p,d}$
$\displaystyle\left\|\left(\sum_{\boldsymbol{j}\in\mathbb{N}_{0}^{d}}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}2^{2|\boldsymbol{j}|}|\mu_{\boldsymbol{j},\boldsymbol{m}}|^{2}\,{\mathbf{1}}_{I_{\boldsymbol{j},\boldsymbol{m}}}\right)^{1/2}\right\|_{L_{p}([0,1]^{d})}$
$\displaystyle\leq$
$\displaystyle\left\|\left(\sum_{\boldsymbol{j}\in\mathbb{N}_{-1}^{d}}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}2^{2|\boldsymbol{j}|}|\mu_{\boldsymbol{j},\boldsymbol{m}}|^{2}\,{\mathbf{1}}_{I_{\boldsymbol{j},\boldsymbol{m}}}\right)^{1/2}\right\|_{L_{p}([0,1]^{d})}$
$\displaystyle\lesssim_{p,d}$ $\displaystyle
L_{p,N}^{\mathrm{star}}(\mathcal{P}).$

Here the first estimate follows from Proposition 3 and the final estimate
follows from the corresponding and well-known “Littlewood-Paley” result for
the standard $L_{p}$ discrepancy (see, e.g., [17]). This completes the proof.
∎

As a consequence, all point sets and sequences with the optimal order of star
$L_{p}$ discrepancy also achieve the optimal order of extreme $L_{p}$
discrepancy as well. This means that we can extend Eq. (4) to general
$p\in(1,\infty)$. Combining (3), Corollary 5 and the lower bound from
Corollary 4 we obtain:

######  Theorem 6.

For every $p\in(1,\infty)$ and every $d,N\in\mathbb{N}$ we have

$\inf_{\mathcal{P}\subseteq[0,1)^{d}\atop|\mathcal{P}|=N}L_{p,N}^{{\rm
extr}}(\mathcal{P})\asymp_{d,p}(1+\log N)^{\frac{d-1}{2}}.$

### The extreme $L_{1}$ discrepancy for dimension two.

In dimension $d=2$ we can prove the lower bound even for $p=1$. For the proof
we also use a method introduced by Halász [15] for the star $L_{1}$
discrepancy.

According to (8) the extreme $L_{1}$ discrepancy of $\mathcal{P}$ in
$[0,1)^{2}$ can be calculated via

$L_{1,N}^{\mathrm{extr}}(\mathcal{P})=\frac{1}{4}\|g\|_{L_{1}([0,1]^{4})},$

where

$g(x_{1},x_{2},y_{1},y_{2})=D(x_{1},x_{2})-D(x_{1},y_{2})-D(y_{1},x_{2})+D(y_{1},y_{2}).$

From the proof of Lemma 2 we find the following crucial observation: Let
$\boldsymbol{j}=(j_{1},j_{2},-1,-1)$ with $j_{1},j_{2}\in\mathbb{N}_{0}$ and
$\boldsymbol{m}=(m_{1},m_{2},0,0)\in\mathbb{D}_{\boldsymbol{j}}$. Set
$\boldsymbol{j}^{\prime}=(j_{1},j_{2})$ and
$\boldsymbol{m}^{\prime}=(m_{1},m_{2})\in\mathbb{D}_{\boldsymbol{j}^{\prime}}$.
Then we have

$\displaystyle\langle g,h_{\boldsymbol{j},\boldsymbol{m}}\rangle$
$\displaystyle=$
$\displaystyle\int_{[0,1]^{4}}(D(x_{1},x_{2})-D(x_{1},y_{2})-D(y_{1},x_{2})+D(y_{1},y_{2}))$
(11) $\displaystyle\hskip 28.45274pt\times
h_{j_{1},m_{1}}(x_{1})h_{j_{2},m_{2}}(x_{2})h_{-1,0}(y_{1})h_{-1,0}(y_{2})\,\mathrm{d}(x_{1},x_{2},y_{1},y_{2})$
$\displaystyle=$
$\displaystyle\int_{[0,1]^{2}}D(x_{1},x_{2})h_{j_{1},m_{1}}(x_{1})h_{j_{2},m_{2}}(x_{2})\,\mathrm{d}(x_{1},x_{2})$
$\displaystyle=$ $\displaystyle\langle
D,h_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}\rangle.$

Four-dimensional Haar functions of this form clearly behave like two-
dimensional Haar functions, which is important for the product rule to hold
(which says that the product of intersecting two-dimensional Haar functions is
a Haar function again.) Based on this observation we can prove the following
lower bound on the extreme $L_{1}$ discrepancy of two-dimensional point sets.

######  Theorem 7.

There exists a constant $c>0$ such that for every $N$-element point set
$\mathcal{P}$ in the unit square we have

$L_{1,N}^{\mathrm{extr}}(\mathcal{P})\geq c\sqrt{\log{N}}.$

###### Proof.

Let $n\in\mathbb{N}$ such that $2^{n-1}\leq 2N\leq 2^{n}$. For
$k\in\\{0,1,\dots,n\\}$ we introduce the functions

$f_{k}:=\sum_{\boldsymbol{j}=(k,n-k,-1,-1)}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}\varepsilon_{\boldsymbol{j},\boldsymbol{m}}h_{\boldsymbol{j},\boldsymbol{m}}.$

For $\boldsymbol{j}=(k,n-k,-1,-1)$ and
$\boldsymbol{m}=(m_{1},m_{2},0,0)\in\mathbb{D}_{\boldsymbol{j}}$ we set
$\boldsymbol{j}^{\prime}=(k,n-k)$ and
$\boldsymbol{m}^{\prime}=(m_{1},m_{2})\in\mathbb{D}_{\boldsymbol{j}^{\prime}}$.
The signs $\varepsilon_{\boldsymbol{j},\boldsymbol{m}}$ are chosen such that
$\varepsilon_{\boldsymbol{j},\boldsymbol{m}}=-1$ if $\mathcal{P}\cap
I_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}=\emptyset$ and
$\varepsilon_{\boldsymbol{j},\boldsymbol{m}}=0$ otherwise. Then we have (using
(11))

$\displaystyle\langle g,f_{k}\rangle=$
$\displaystyle-\sum_{\boldsymbol{j}=(k,n-k,-1,-1)}\sum_{\begin{subarray}{c}\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}\\\
\mathcal{P}\cap
I_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}=\emptyset\end{subarray}}\langle
g,h_{\boldsymbol{j},\boldsymbol{m}}\rangle=-\sum_{\boldsymbol{j}^{\prime}=(k,n-k)}\sum_{\begin{subarray}{c}\boldsymbol{m}^{\prime}\in\mathbb{D}_{\boldsymbol{j}^{\prime}}\\\
\mathcal{P}\cap
I_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}=\emptyset\end{subarray}}\langle
D,h_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}\rangle$ $\displaystyle=$
$\displaystyle\sum_{\boldsymbol{j}^{\prime}=(k,n-k)}\sum_{\begin{subarray}{c}\boldsymbol{m}^{\prime}\in\mathbb{D}_{\boldsymbol{j}^{\prime}}\\\
\mathcal{P}\cap
I_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}=\emptyset\end{subarray}}N2^{-2|\boldsymbol{j}^{\prime}|-4}\geq
2^{n-2}2^{n-1}2^{-2n-4}=2^{-7}.$ (12)

Here we used that at least $2^{n-1}$ of the $2^{n}$ boxes
$I_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}$ must be empty and the
well-known and easily checked fact that $\langle
D,h_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}\rangle=-N2^{-2|\boldsymbol{j}^{\prime}|-4}$
if $I_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}$ is empty.

The rest of the proof works completely the same as Halasz’ proof on the
standard $L_{1}$ discrepancy of two-dimensional point sets from [15]. We
introduce the Riesz product

$F:=\prod_{k=0}^{n}\left(1+\frac{\mathtt{i}\gamma}{\sqrt{n+1}}f_{k}\right)-1=\frac{\mathtt{i}\gamma}{\sqrt{n+1}}\sum_{k=0}^{n}f_{k}+F_{>n},$

where $F_{>n}=F_{2}+\dots+F_{n}$ with

$F_{k}=\left(\frac{\mathtt{i}\gamma}{\sqrt{n+1}}\right)^{k}\sum_{0\leq
l_{1}<\dots<l_{k}\leq n}f_{l_{1}}\cdots f_{l_{k}}$

for $k\in\\{0,1,\dots,n\\}$. Clearly, with (3) we have

$|\langle g,F\rangle|\geq\frac{\gamma}{\sqrt{n+1}}\left|\sum_{k=0}^{n}\langle
g,f_{k}\rangle\right|-|\langle
g,F_{>n}\rangle|\geq\frac{\gamma}{2^{7}}\sqrt{n+1}-|\langle g,F_{>n}\rangle|.$

For $\boldsymbol{r}=(r_{1},r_{2})\in\mathbb{N}_{0}^{2}$ with $r_{1}+r_{2}=r$
we call a function of the form

$f_{\boldsymbol{r}}:=\sum_{\boldsymbol{j}=(r_{1},r_{2},-1,-1)}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}\varepsilon_{\boldsymbol{j},\boldsymbol{m}}h_{\boldsymbol{j},\boldsymbol{m}}$

with coefficients $\varepsilon_{\boldsymbol{j},\boldsymbol{m}}\in\\{-1,0,1\\}$
an $r$-function. (Therefore the $f_{k}$ from above are $r$-functions with
$\boldsymbol{r}=(k,n-k,-1,-1)$ and $r=n$.) For an $r$-function we have

$\displaystyle|\langle g,f_{\boldsymbol{r}}\rangle|\leq$
$\displaystyle\sum_{\boldsymbol{j}=(r_{1},r_{2},-1,-1)}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}|\langle
g,h_{\boldsymbol{j},\boldsymbol{m}}\rangle|$ $\displaystyle=$
$\displaystyle\sum_{\boldsymbol{j}^{\prime}=(r_{1},r_{2})}\sum_{\boldsymbol{m}^{\prime}\in\mathbb{D}_{\boldsymbol{j}^{\prime}}}|\langle
D,h_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}\rangle|$
$\displaystyle\leq$
$\displaystyle\sum_{\boldsymbol{j}^{\prime}=(r_{1},r_{2})}\sum_{\boldsymbol{m}^{\prime}\in\mathbb{D}_{\boldsymbol{j}^{\prime}}}\left|\left\langle\sum_{\boldsymbol{z}\in\mathcal{P}}\boldsymbol{1}_{[\boldsymbol{0},\boldsymbol{x})}(\boldsymbol{z}),h_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}\right\rangle\right|+\sum_{\boldsymbol{j}^{\prime}=(r_{1},r_{2})}\sum_{\boldsymbol{m}^{\prime}\in\mathbb{D}_{\boldsymbol{j}^{\prime}}}|\langle
Nx_{1}x_{2},h_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}\rangle|$
$\displaystyle\leq$
$\displaystyle\sum_{\boldsymbol{j}^{\prime}=(r_{1},r_{2})}\sum_{\boldsymbol{z}\in\mathcal{P}}\sum_{\begin{subarray}{c}\boldsymbol{m}^{\prime}\in\mathbb{D}_{\boldsymbol{j}^{\prime}}\\\
\boldsymbol{z}\in\mathcal{P}\cap
I_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}\end{subarray}}\underbrace{|\langle\boldsymbol{1}_{[\boldsymbol{0},\boldsymbol{x})}(\boldsymbol{z}),h_{\boldsymbol{j}^{\prime},\boldsymbol{m}^{\prime}}\rangle|}_{\leq
2^{-|\boldsymbol{j}^{\prime}|}}+\sum_{\boldsymbol{j}^{\prime}=(r_{1},r_{2})}\sum_{\boldsymbol{m}^{\prime}\in\mathbb{D}_{\boldsymbol{j}^{\prime}}}\frac{N}{2^{2|\boldsymbol{j}^{\prime}|+4}}$
$\displaystyle\leq$
$\displaystyle\frac{N}{2^{|\boldsymbol{j}^{\prime}|}}+\frac{2^{|\boldsymbol{j}^{\prime}|}N}{2^{2|\boldsymbol{j}^{\prime}|+4}}$
$\displaystyle\lesssim$ $\displaystyle\frac{N}{2^{r}}.$ (13)

Now, by the fact that products of two-dimensional Haar functions of same size
which intersect are Haar functions again and since four-dimensional Haar
functions with $\boldsymbol{j}=(j_{1},j_{2},-1,-1)$ behave like two-
dimensional Haar functions, we find that $f_{l_{1}}\cdots f_{l_{k}}$ for
$0\leq l_{1}<\dots<l_{k}\leq n$ is an $r$-function again, with corresponding
vector $\boldsymbol{s}=(n-l_{1},l_{k},-1,-1)$, i.e. $s=n-l_{1}+l_{k}$. The
parameter $s$ can have the values $n+1,n+2,\dots,2n$. A term $f_{l_{1}}\cdots
f_{l_{k}}$ is an $r$-function with parameter $s$ if we have $n-l_{1}+l_{k}=s$
and $l_{k}\leq n$; i.e., if there are $2n-s+1$ possible choices for $l_{1}$ to
guarantee both conditions ($l_{1}\in\\{0,1,\dots,2n-s\\}$). For the remaining
$(k-2)$ indices $l_{2},\dots,l_{k-1}$ we have $s-n-1$ possible values they can
take, which can be selected in $\binom{s-n-1}{k-2}$ many ways.

Choose $\gamma\leq\frac{1}{2}$. Then we obtain (using (3))

$\displaystyle|\langle g,F_{>n}\rangle|\leq$
$\displaystyle\sum_{k=2}^{n}|\langle g,F_{k}\rangle|$ $\displaystyle\leq$
$\displaystyle\sum_{k=2}^{n}\left(\frac{\gamma}{\sqrt{n+1}}\right)^{k}\sum_{0\leq
l_{1}<\cdots<l_{k}\leq n}|\langle g,f_{l_{1}}\cdots f_{l_{k}}\rangle|$
$\displaystyle\leq$
$\displaystyle\sum_{s=n+1}^{2n}\sum_{k=2}^{n}\left(\frac{\gamma}{\sqrt{n+1}}\right)^{k}\sum_{0\leq
l_{1}<\cdots<l_{k}\leq n\atop s=n-l_{1}+l_{k}}\frac{N}{2^{s}}$
$\displaystyle\leq$
$\displaystyle\sum_{s=n+1}^{2n}(2n-s+1)\sum_{k=2}^{s-n+1}\binom{s-n-1}{k-2}\left(\frac{\gamma}{\sqrt{n+1}}\right)^{k}\frac{N}{2^{s}}$
$\displaystyle\leq$
$\displaystyle\left(\frac{\gamma}{\sqrt{n+1}}\right)^{2}n\sum_{s=n+1}^{2n}\sum_{k=0}^{s-n-1}\binom{s-n-1}{k}\left(\frac{\gamma}{\sqrt{n+1}}\right)^{k}\frac{N}{2^{s}}$
$\displaystyle=$
$\displaystyle\frac{\gamma^{2}n}{n+1}\sum_{s=n+1}^{2n}\left(1+\frac{\gamma}{\sqrt{n+1}}\right)^{s-n-1}\frac{N}{2^{s}}$
$\displaystyle=$
$\displaystyle\frac{\gamma^{2}n}{n+1}\sum_{s=n+1}^{2n}\left(\frac{1}{2}+\frac{\gamma}{2\sqrt{n+1}}\right)^{s-n-1}\frac{N}{2^{n+1}}$
$\displaystyle\leq$
$\displaystyle\gamma^{2}\sum_{s=n+1}^{\infty}\left(\frac{1}{2}+\frac{\gamma}{2\sqrt{n+1}}\right)^{s-n-1}$
$\displaystyle\leq$
$\displaystyle\gamma^{2}\sum_{s=n+1}^{\infty}\left(\frac{3}{4}\right)^{s-n-1}$
$\displaystyle=$ $\displaystyle 4\gamma^{2}$ $\displaystyle\leq$
$\displaystyle 1.$

Therefore $|\langle g,F\rangle|\gtrsim\sqrt{n+1}$. On the other hand, we also
have

$\|F\|_{L_{\infty}([0,1]^{4})}\leq\left(1+\frac{\gamma^{2}}{n+1}\right)^{\frac{n+1}{2}}+1\leq\mathrm{e}^{\frac{\gamma^{2}}{2}}+1\lesssim
1.$

Therefore,

$L_{1,N}^{\mathrm{extr}}(\mathcal{P})=\frac{1}{4}\|g\|_{L_{4}([0,1]^{4})}\gtrsim\frac{|\langle
g,F\rangle|}{\|F\|_{L_{\infty}([0,1]^{4})}}\gtrsim\sqrt{n+1}\gtrsim\sqrt{\log{N}}.$

∎

As a consequence we obtain the following corollary:

######  Corollary 8.

For every $p\in[1,\infty)$ we have

$\inf_{\mathcal{P}\subseteq[0,1)^{2}\atop|\mathcal{P}|=N}L_{p,N}^{{\rm
extr}}(\mathcal{P})\asymp_{d,p}(1+\log N)^{1/2}.$

### Extreme discrepancy of digital nets in dimension 2.

Proposition 3 demonstrates that a calculation of the Haar coefficients of the
anchored discrepancy function of a point set yields not only results on the
standard $L_{p}$ discrepancy, but also on the extreme $L_{p}$ discrepancy. For
the latter it even suffices to evaluate only those coefficients where
$\boldsymbol{j}\in\mathbb{N}_{0}^{d}$. The Haar coefficients of the
discrepancy function of certain digital nets have been computed exactly in
[19]. We use these results to obtain exact formulas for the extreme $L_{2}$
discrepancy of these nets. We introduce the relevant nets.

  * •

We study digital $(0,m,2)$-nets generated by the following $m\times m$
matrices over $\mathbb{Z}_{2}$:

$C_{1}=\begin{pmatrix}0&0&0&\cdots&0&0&1\\\ 0&0&0&\cdots&0&1&0\\\
0&0&0&\cdots&1&0&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\\\
0&0&1&\cdots&0&0&0\\\ 0&1&0&\cdots&0&0&0\\\ 1&0&0&\cdots&0&0&0\\\
\end{pmatrix}\text{\, and\, \,}C_{2}=\begin{pmatrix}1&0&0&\cdots&0&0&a_{1}\\\
0&1&0&\cdots&0&0&a_{2}\\\ 0&0&1&\cdots&0&0&a_{3}\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\\\
0&0&0&\cdots&1&0&a_{m-2}\\\ 0&0&0&\cdots&0&1&a_{m-1}\\\ 0&0&0&\cdots&0&0&1\\\
\end{pmatrix}.$ (14)

We study the discrepancy of the digital net
$\mathcal{P}_{\boldsymbol{a}}(\boldsymbol{\sigma})$ with
$\boldsymbol{a}=(a_{1},\dots,a_{m-1})^{\top}\in\mathbb{Z}_{2}^{m-1}$,
generated by $C_{1}$ and $C_{2}$ and digitally shifted by
$\boldsymbol{\sigma}=(\sigma_{1},\dots,\sigma_{m})^{\top}\in\mathbb{Z}_{2}^{m}$.
The set $\mathcal{P}_{\boldsymbol{a}}(\boldsymbol{\sigma})$ can be written as

$\mathcal{P}_{\boldsymbol{a}}(\boldsymbol{\sigma})=\left\\{\bigg{(}\frac{t_{m}}{2}+\dots+\frac{t_{1}}{2^{m}},\frac{b_{1}}{2}+\dots+\frac{b_{m}}{2^{m}}\bigg{)}\
:\ t_{1},\dots,t_{m}\in\\{0,1\\}\right\\},$

where $b_{k}=t_{k}\oplus a_{k}t_{m}\oplus\sigma_{m}$ for
$k\in\\{1,\dots,m-1\\}$ and $b_{m}=t_{m}\oplus\sigma_{m}$. The operation
$\oplus$ denotes addition modulo 2.

  * •

We also consider symmetrized versions of shifted digital nets, which we define
as follows:

$\widetilde{\mathcal{P}}_{\boldsymbol{a}}(\boldsymbol{\sigma}):=\mathcal{P}_{\boldsymbol{a}}(\boldsymbol{\sigma})\cup\mathcal{P}_{\boldsymbol{a}}(\boldsymbol{\sigma}^{*})=\mathcal{P}_{\boldsymbol{a}}(\boldsymbol{\sigma})\cup\\{(x,1-2^{-m}-y):(x,y)\in\mathcal{P}_{\boldsymbol{a}}(\boldsymbol{\sigma})\\},$

where $\boldsymbol{\sigma}^{*}=(\sigma_{1}\oplus 1,\dots,\sigma_{m}\oplus
1)^{\top}$.

  * •

Finally we introduce the class of digital $(0,m,2)$-nets
$\mathcal{P}_{\boldsymbol{c}}$ which are generated by $C_{1}$ as above and
matrices $C_{2}$ of the form

$C_{2}=\begin{pmatrix}1&c_{1}&c_{1}&\cdots&c_{1}&c_{1}&c_{1}\\\
0&1&c_{2}&\cdots&c_{2}&c_{2}&c_{2}\\\ 0&0&1&\cdots&c_{3}&c_{3}&c_{3}\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\\\
0&0&0&\cdots&1&c_{m-2}&c_{m-2}\\\ 0&0&0&\cdots&0&1&c_{m-1}\\\
0&0&0&\cdots&0&0&1\\\ \end{pmatrix},$

where $\boldsymbol{c}=(c_{1},\dots,c_{m-1})^{\top}\in\mathbb{Z}_{2}^{m-1}$. If
$\boldsymbol{c}=(1,\dots,1)^{\top}$, the corresponding digital net
$\mathcal{P}_{\boldsymbol{1}}$ is sometimes called upper-$\boldsymbol{1}$-net.

######  Theorem 9.

We have

$\displaystyle(L_{2,2^{m}}^{\mathrm{extr}}(\mathcal{P}_{\boldsymbol{a}}(\boldsymbol{\sigma})))^{2}=\frac{m}{64}+\frac{1}{72}-\frac{1}{9\cdot
4^{m+2}}+\frac{1}{192}\sum_{k=1}^{m-2}a_{k}(2-2^{2k-2m+2})$

and

$\displaystyle(L_{2,2^{m+1}}^{\mathrm{extr}}(\widetilde{\mathcal{P}}_{\boldsymbol{a}}(\boldsymbol{\sigma}))^{2}=\frac{m+1}{24}-\frac{5}{9\cdot
2^{4^{m+1}}}-\frac{1}{2^{2m+3}}\sum_{k=1}^{m-1}a_{k}2^{2k}.$

For the upper-$\boldsymbol{1}$-net we have

$\displaystyle(L_{2,2^{m}}^{\mathrm{extr}}(\mathcal{P}_{\boldsymbol{1}}))^{2}=\frac{m}{64}+\frac{1}{72}-\frac{1}{9\cdot
4^{m+2}}.$

For general $p\in(1,\infty)$ we have

$L_{p,N}^{\mathrm{extr}}(\mathcal{P})\lesssim_{p}\sqrt{\log N},$

where
$\mathcal{P}\in\\{\mathcal{P}_{\boldsymbol{a}}(\boldsymbol{\sigma}),\mathcal{P}_{\boldsymbol{c}}\\}$
and $N=2^{m}$ or
$\mathcal{P}=\widetilde{\mathcal{P}}_{\boldsymbol{a}}(\boldsymbol{\sigma})$
and $N=2^{m+1}$. Hence, all these nets achieve the optimal order of extreme
$L_{p}$ discrepancy, which is $\sqrt{\log{N}}$, according to Theorem 7.

###### Proof.

Since the Haar coefficients of the respective discrepancy functions have
already been computed, there is not much left to do. Just add the expressions
given in [19, Lemmas 8-13] to obtain the result for $(L_{2,2^{m}}^{{\rm
extr}}(\mathcal{P}_{\boldsymbol{a}}(\boldsymbol{\sigma})))^{2}$. Caution:
before applying the results from [19, Lemmas 8-13] here, they have to be
multiplied with $2^{2m}$ since in [19] a normalized version of the discrepancy
function is considered.

Adding the results on the sums over $\mathcal{J}_{8}$ to $\mathcal{J}_{13}$ as
stated in [19, Lemma 14] (again multiplied with $2^{2(m+1)}$) yields the
formula for $(L_{2,2^{m+1}}^{{\rm
extr}}(\widetilde{\mathcal{P}}_{\boldsymbol{a}}(\boldsymbol{\sigma}))^{2}$.

The Haar coefficients of the discrepancy function of the
upper-$\boldsymbol{1}$-net have not been published so far; therefore we state
the relevant results:

  * •

Let $\mathcal{J}_{1}=\\{(j_{1},0):0\leq j_{1}\leq n-3\\}$. Then

$\sum_{\boldsymbol{j}\in\mathcal{J}_{1}}2^{|\boldsymbol{j}|}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}|\mu_{\boldsymbol{j}\boldsymbol{m}}|^{2}=0.$

  * •

Let $\mathcal{J}_{2}=\\{(j_{1},j_{2}):j_{1}\geq 0,j_{2}\geq 1,j_{1}+j_{2}\leq
n-3\\}$. Then

$\sum_{\boldsymbol{j}\in\mathcal{J}_{2}}2^{|\boldsymbol{j}|}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}|\mu_{\boldsymbol{j}\boldsymbol{m}}|^{2}=\frac{1}{3}4^{-2n-5}\left(3n\cdot
4^{n}-5\cdot 2^{2n+1}+64\right).$

  * •

Let $\mathcal{J}_{3}=\\{(j_{1},j_{2}):j_{1}\geq 0,j_{2}\geq
1,j_{1}+j_{2}=n-2\\}$. Then

$\sum_{\boldsymbol{j}\in\mathcal{J}_{3}}2^{|\boldsymbol{j}|}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}|\mu_{\boldsymbol{j}\boldsymbol{m}}|^{2}=\frac{1}{9}4^{-2n-5}\left(21\cdot
n4^{n}-2(5\cdot 4^{n}+256)\right).$

  * •

Let $\mathcal{J}_{4}=\\{(n-2,0)\\}$. Then

$\sum_{\boldsymbol{j}\in\mathcal{J}_{4}}2^{|\boldsymbol{j}|}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}|\mu_{\boldsymbol{j}\boldsymbol{m}}|^{2}=\frac{1}{3}4^{2n-4}(4^{n}+32).$

  * •

Let $\mathcal{J}_{5}=\\{(j_{1},j_{2}):j_{1}\geq 0,j_{2}\geq
1,j_{1}+j_{2}=n-1\\}$. Then

$\sum_{\boldsymbol{j}\in\mathcal{J}_{5}}2^{|\boldsymbol{j}|}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}|\mu_{\boldsymbol{j}\boldsymbol{m}}|^{2}=\frac{1}{27}2^{-4n-7}\left(3n(5\cdot
4^{n}+32)-7\cdot 4^{n}-128\right).$

  * •

Let $\mathcal{J}_{6}=\\{(n-1,0)\\}$. Then

$\sum_{\boldsymbol{j}\in\mathcal{J}_{6}}2^{|\boldsymbol{j}|}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}|\mu_{\boldsymbol{j}\boldsymbol{m}}|^{2}=\frac{1}{3}4^{-2n-3}(4^{n}+8).$

  * •

Let $\mathcal{J}_{7}=\\{(j_{1},j_{2}):j_{1}\geq n\text{\, or \,}j_{2}\geq
n\\}$. Then

$\sum_{\boldsymbol{j}\in\mathcal{J}_{7}}2^{|\boldsymbol{j}|}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}|\mu_{\boldsymbol{j}\boldsymbol{m}}|^{2}=\frac{1}{9}4^{-4n-4}(4\cdot
2^{2n+1}-1).$

  * •

Let $\mathcal{J}_{8}=\\{(j_{1},j_{2}):j_{1}+j_{2}\geq n\text{\, and \,}1\leq
j_{1},j_{2}\leq n-1\\}$. Then

$\sum_{\boldsymbol{j}\in\mathcal{J}_{8}}2^{|\boldsymbol{j}|}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}|\mu_{\boldsymbol{j}\boldsymbol{m}}|^{2}=\frac{1}{27}4^{-2n-2}-\frac{1}{27}4^{-n-2}-\frac{1}{9}n4^{-2n-1}+\frac{5}{9}n4^{-n-3}.$

Since $\mathcal{J}_{1},\dots,\mathcal{J}_{8}$ form a partition of
$\mathbb{N}_{0}^{2}$, we have

$(L_{2,2^{m}}^{\mathrm{extr}}(\mathcal{P}_{\boldsymbol{1}}))^{2}=\sum_{i=1}^{8}\sum_{\boldsymbol{j}\in\mathcal{J}_{i}}2^{|\boldsymbol{j}|}\sum_{\boldsymbol{m}\in\mathbb{D}_{\boldsymbol{j}}}|\mu_{\boldsymbol{j}\boldsymbol{m}}|^{2}.$

Inserting the above expressions for the single sub-sums yields the desired
result.

The claim on the extreme $L_{p}$ discrepancy follows from the mentioned
results on the relevant Haar coefficients and the second part of Proposition
3. The relevant Haar coefficients of the local discrepancy of the nets
$\mathcal{P}_{\boldsymbol{c}}$ can be found in [20, Lemma 3.2]. ∎

######  Remark 10.

We discuss the results in Theorem 9.

  * •

We remark that the digital shift $\boldsymbol{\sigma}$ has no effect at all on
the extreme $L_{2}$ discrepancy of
$\mathcal{P}_{\boldsymbol{a}}(\boldsymbol{\sigma})$. It would be interesting
to know if this is a general rule which holds for all digital nets. Note that
for the star $L_{2}$ discrepancy the shift is often crucial and can even
reduce the order in $N$ for certain nets (see, e.g., [25]). However, it seems
that the only Haar coefficients that “see” the shift are those for
$\boldsymbol{j}\in\mathbb{N}_{-1}^{2}\setminus\mathbb{N}_{0}^{2}$.

  * •

Note that the Hammersley point set with $2^{m}$ elements has exactly the same
extreme $L_{2}$ discrepancy as the upper-$\boldsymbol{1}$-net with the same
number of points (for the result on the Hammersley point set see [18, Theorem
8] or choose $\boldsymbol{a}=(0,\dots,0)$ in the present Theorem 9). However,
the Hammersley point set has a much higher star $L_{2}$ discrepancy, which is
of order $\log{N}$, whereas the $L_{2}$ discrepancy of
$\mathcal{P}_{\boldsymbol{1}}$ is of optimal order $\sqrt{\log{N}}$ (see
[20]). The large $L_{2}$ discrepancy of the Hammersley point set is caused by
the Haar coefficient $\mu_{(-1,-1),(0,0)}$.

  * •

For the symmetrized nets
$\widetilde{\mathcal{P}}_{\boldsymbol{a}}(\boldsymbol{\sigma})$ we have
$L_{2,2^{m+1}}^{{\rm
star}}(\widetilde{\mathcal{P}}_{\boldsymbol{a}}(\boldsymbol{\sigma}))=\frac{m}{24}+\mathcal{O}(1)$
as well as
$L_{2,2^{m+1}}^{\mathrm{extr}}(\widetilde{\mathcal{P}}_{\boldsymbol{a}}(\boldsymbol{\sigma}))=\frac{m}{24}+\mathcal{O}(1)$;
hence the difference between the two $L_{2}$ discrepancies is not significant
for these point sets. That is due to the fact that for the nets
$\mathcal{P}_{\boldsymbol{a}}(\boldsymbol{\sigma})$ the symmetrization has the
effect to reduce the contribution of the Haar coefficients for
$\boldsymbol{j}\in\mathbb{N}_{-1}^{2}\setminus\mathbb{N}_{0}^{2}$ to the
$L_{2}$ discrepancy to order $\mathcal{O}(1)$ already.

  * •

The result on $\mathcal{P}_{\boldsymbol{a}}(\boldsymbol{\sigma})$ demonstrates
that the Hammersley point set is not the digital $(0,m,2)$-net with largest
extreme $L_{2}$ discrepancy. If we choose $\boldsymbol{a}=(0,\dots,0)$ (in
which case $\mathcal{P}_{\boldsymbol{a}}(\boldsymbol{\sigma})$ is the shifted
Hammersley point set), then $(L_{2,2^{m}}^{{\rm
extr}}(\mathcal{P}_{\boldsymbol{a}}(\boldsymbol{\sigma})))^{2}=\frac{m}{64}+\mathcal{O}(1)$,
while for $\boldsymbol{a}=(1,\dots,1)$ we only get $(L_{2,2^{m}}^{{\rm
extr}}(\mathcal{P}_{\boldsymbol{a}}(\boldsymbol{\sigma})))^{2}=\frac{m}{48}+\mathcal{O}(1)$.

  * •

Open problem: Find a digital $(0,m,2)$-net which does not achieve the optimal
order of extreme $L_{2}$ or $L_{p}$ discrepancy or prove that there is no such
net.

##  4 Periodic $L_{p}$ discrepancy

Now we turn our attention to the periodic $L_{p}$ discrepancy. For $p=2$ the
lower bound of order of magnitude $(\log N)^{(d-1)/2}$ for $N$-element point
sets in $[0,1)^{d}$ is well established (see (5)). However, combining (1) and
Corollary 4 and Theorem 7, respectively, this lower bound can be even obtained
for the periodic $L_{p}$ discrepancy for general $p>1$.

######  Corollary 11.

Let $p>1$. For every $N$-element point set $\mathcal{P}$ in $[0,1)^{d}$ we
have

$L_{p,N}^{{\rm per}}(\mathcal{P})\gtrsim_{p,d}(1+\log N)^{\frac{d-1}{2}}.$

For $d=2$ the result even holds true for $p=1$.

We show that this lower bound is best possible in the order of magnitude in
$N$ for fixed dimension $d$ and $p\leq 2$. In the following we will consider
the periodic $L_{2}$ discrepancy only. Unfortunately, we cannot apply the
simple argument used for the extreme $L_{2}$ discrepancy here, since in
general we do not know whether the periodic $L_{2}$ discrepancy is dominated
by the star $L_{2}$ discrepancy. (We remark that Lev [23] showed that for
certain symmetrized point sets $\mathcal{P}^{{\rm sym}}$ it is indeed true
that $L_{2,N}^{{\rm per}}(\mathcal{P}^{{\rm sym}})\lesssim
L_{2,N}(\mathcal{P}^{{\rm sym}})$. However, it is not known if any of the
point sets of optimal star $L_{2}$ discrepancy satisfies these symmetry
properties.)

It is a known fact that the periodic $L_{2}$ discrepancy can be expressed in
terms of exponential sums. For
$\mathcal{P}=\\{\boldsymbol{x}_{0},\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{N-1}\\}$
in $[0,1)^{d}$ we have

$(L_{2,N}^{{\rm
per}}(\mathcal{P}))^{2}=\frac{1}{3^{d}}\sum_{\boldsymbol{k}\in\mathbb{Z}^{d}\setminus\\{\boldsymbol{0}\\}}\frac{1}{r(\boldsymbol{k})^{2}}\left|\sum_{n=0}^{N-1}\exp(2\pi\mathtt{i}\boldsymbol{k}\cdot\boldsymbol{x}_{n})\right|^{2},$
(15)

where $\mathtt{i}=\sqrt{-1}$ and where for
$\boldsymbol{k}=(k_{1},\ldots,k_{d})\in\mathbb{Z}^{d}$ we set

$r(\boldsymbol{k})=\prod_{j=1}^{d}r(k_{j})\ \ \ \mbox{ and }\ \
r(k_{j})=\left\\{\begin{array}[]{ll}1&\mbox{ if $k_{j}=0$},\\\
\frac{2\pi|k_{j}|}{\sqrt{6}}&\mbox{ if $k_{j}\not=0$.}\end{array}\right.$

For a proof of this relation see [23, Theorem 1] or [16, p. 390]. Formula (15)
shows that the periodic $L_{2}$ discrepancy, normalized by $N$, is – up to a
multiplicative factor – exactly the diaphony which is a well-known measure for
the irregularity of distribution of point sets and which was introduced by
Zinterhof [31] in the year 1976 (see also [11] and the forthcoming Remark 18).

######  Remark 12.

We recall that Lev [24] studied a slightly more general notion of diaphony
which involve certain weights and which he called generalized diaphony. For a
certain choice of weights this generalized diaphony coincides with the
“classical Zinterhof diaphony” and therefore – up to multiplicative factors –
with the periodic discrepancy studied in the present chapter. He was able to
determine the exact order of magnitude in $N$ for fixed dimension $d$ (see
[24, Main Theorem]). While the lower bounds hold for any of the involved
weights and therefore also for the periodic $L_{2}$ discrepancy considered in
the present paper, the upper bounds are achieved only for certain weights
which do not comprise the setting considered here. Just as a side note, the
construction is based on Frolov’s construction of lattices from [13].

Now we re-write (15) further and get this way

$\displaystyle(L_{2,N}^{{\rm per}}(\mathcal{P}))^{2}$ $\displaystyle=$
$\displaystyle\frac{1}{3^{d}}\sum_{\boldsymbol{k}\in\mathbb{Z}^{d}\setminus\\{\boldsymbol{0}\\}}\frac{1}{r(\boldsymbol{k})^{2}}\left|\sum_{n=0}^{N-1}\exp(2\pi\mathtt{i}\boldsymbol{k}\cdot\boldsymbol{x}_{n})\right|^{2}$
$\displaystyle=$
$\displaystyle-\frac{N^{2}}{3^{d}}+\frac{1}{3^{d}}\sum_{n,p=0}^{N-1}K_{d}(\boldsymbol{x}_{n},\boldsymbol{x}_{p}),$

where

$K_{d}(\boldsymbol{x},\boldsymbol{y}):=\sum_{\boldsymbol{k}\in\mathbb{Z}^{d}}\frac{1}{r(\boldsymbol{k})^{2}}\exp(2\pi\mathtt{i}\boldsymbol{k}\cdot(\boldsymbol{x}-\boldsymbol{y})).$

Our aim is now to find a Walsh-series representation of the periodic $L_{2}$
discrepancy.

### Walsh functions in base $b$.

For $k\in\mathbb{N}_{0}$ with $b$-adic representation

$k=\kappa_{a-1}b^{a-1}+\cdots+\kappa_{1}b+\kappa_{0},$

with $\kappa_{i}\in\mathbb{Z}_{b}$, we define the ($b$-adic) Walsh function
${\rm wal}_{k}:[0,1)\rightarrow\\{z\in\mathbb{C}\ :\ |z|=1\\}$ by

${\rm wal}_{k}(x):={\rm
e}^{2\pi\mathtt{i}(\xi_{1}\kappa_{0}+\cdots+\xi_{a}\kappa_{a-1})/b},$

for $x\in[0,1)$ with $b$-adic representation
$x=\frac{\xi_{1}}{b}+\frac{\xi_{2}}{b^{2}}+\cdots$, with
$\xi_{i}\in\mathbb{Z}_{b}$, (unique in the sense that infinitely many of the
$\xi_{i}$ must be different from $b-1$).

For dimension $d\geq 2$, $\boldsymbol{x}=(x_{1},\ldots,x_{d})\in[0,1)^{d}$ and
$\boldsymbol{k}=(k_{1},\ldots,k_{d})\in\mathbb{N}_{0}^{d}$ we define ${\rm
wal}_{\boldsymbol{k}}:[0,1)^{d}\rightarrow\\{z\in\mathbb{C}\ :\ |z|=1\\}$ by

${\rm wal}_{\boldsymbol{k}}(\boldsymbol{x}):=\prod_{j=1}^{d}{\rm
wal}_{k_{j}}(x_{j}).$

Information about basic properties of Walsh functions, especially in the
context of digital nets, can be found in [8, Appendix A].

### Walsh series expansion.

Now we expand $K_{d}(\boldsymbol{x},\boldsymbol{y})$ into a Walsh series. Fix
a prime number $b$. We have

$K_{d}(\boldsymbol{x},\boldsymbol{y})=\sum_{\boldsymbol{k},\boldsymbol{\ell}\in\mathbb{N}_{0}^{d}}\rho_{b}(\boldsymbol{k},\boldsymbol{\ell}){\rm
wal}_{\boldsymbol{k}}(\boldsymbol{x})\overline{{\rm
wal}_{\boldsymbol{\ell}}(\boldsymbol{y})},$

where

$\rho_{b}(\boldsymbol{k},\boldsymbol{\ell})=\int_{[0,1]^{2d}}K_{d}(\boldsymbol{x},\boldsymbol{y})\overline{{\rm
wal}_{\boldsymbol{k}}(\boldsymbol{x})}{\rm
wal}_{\boldsymbol{\ell}}(\boldsymbol{y})\,\mathrm{d}\boldsymbol{x}\,\mathrm{d}\boldsymbol{y}.$

Due to the multiplicative structure of $K_{d}$ and of the multi-dimensional
Walsh functions, for $\boldsymbol{k}=(k_{1},\ldots,k_{d})$ and
$\boldsymbol{\ell}=(\ell_{1},\ldots,\ell_{d})$ in $\mathbb{N}_{0}^{d}$ we have

$\rho_{b}(\boldsymbol{k},\boldsymbol{\ell})=\prod_{j=1}^{d}\rho_{b}(k_{j},\ell_{j}),$

where, for $d=1$ and $k,\ell\in\mathbb{N}_{0}$,

$\displaystyle\rho_{b}(k,\ell)$ $\displaystyle=$
$\displaystyle\int_{[0,1]^{2}}K_{1}(x,y)\overline{{\rm wal}_{k_{j}}(x)}{\rm
wal}_{\ell_{j}}(y)\,\mathrm{d}x\,\mathrm{d}y$ $\displaystyle=$
$\displaystyle\int_{0}^{1}\int_{0}^{1}\sum_{h=-\infty}^{\infty}\frac{1}{r(h)^{2}}\exp(2\pi\mathtt{i}h(x-y))\overline{{\rm
wal}_{k}(x)}{\rm wal}_{\ell}(y)\,\mathrm{d}x\,\mathrm{d}y$ $\displaystyle=$
$\displaystyle\sum_{h=-\infty}^{\infty}\frac{1}{r(h)^{2}}\overline{\left(\int_{0}^{1}\exp(-2\pi\mathtt{i}hx){\rm
wal}_{k}(x)\,\mathrm{d}x\right)}\left(\int_{0}^{1}\exp(-2\pi\mathtt{i}hy){\rm
wal}_{\ell}(y)\,\mathrm{d}y\right).$

Put

$\beta_{h,k}:=\int_{0}^{1}\exp(-2\pi\mathtt{i}hx){\rm
wal}_{k}(x)\,\mathrm{d}x.$

Note that $\beta_{0,0}=1$, $\beta_{0,k}=0$ for $k\in\mathbb{N}$ and
$\beta_{h,0}=0$ for $h\in\mathbb{Z}\setminus\\{0\\}$. Then we can write

$\rho_{b}(k,\ell)=\sum_{h=-\infty}^{\infty}\frac{\overline{\beta}_{h,k}\beta_{h,\ell}}{r(h)^{2}}$

and, in particular, $\rho_{b}(0,0)=1$ and $\rho_{b}(0,\ell)=\rho_{b}(k,0)=0$
for $k,\ell\in\mathbb{N}$. For $k,\ell\in\mathbb{N}$ we have

$\rho_{b}(k,\ell)=\sum_{h=-\infty\atop
h\not=0}^{\infty}\frac{\overline{\beta}_{h,k}\beta_{h,\ell}}{r(h)^{2}}=\frac{3}{2\pi^{2}}\sum_{h=-\infty\atop
h\not=0}^{\infty}\frac{\overline{\beta}_{h,k}\beta_{h,\ell}}{h^{2}}.$

Using the Walsh series expansion of $K_{d}(\cdot,\cdot)$ we can write the
periodic $L_{2}$ discrepancy as

$\displaystyle(L_{2,N}^{{\rm
per}}(\mathcal{P}))^{2}=-\frac{N^{2}}{3^{d}}+\frac{1}{3^{d}}\sum_{n,p=0}^{N-1}\sum_{\boldsymbol{k},\boldsymbol{\ell}\in\mathbb{N}_{0}^{d}}\rho_{b}(\boldsymbol{k},\boldsymbol{\ell}){\rm
wal}_{\boldsymbol{k}}(\boldsymbol{x}_{n})\overline{{\rm
wal}_{\boldsymbol{\ell}}(\boldsymbol{x}_{p})}.$ (16)

Unfortunately, the coefficients $\rho_{b}(k,\ell)$ for $k\not=\ell$ (the “non-
diagonal terms”) are rather difficult to handle. However, one can get rid of
them if one considers the root mean square of digitally shifted point sets
with respect to all digital shifts of depth $m$. This follows immediately from
the following lemma.

######  Lemma 13.

Let $x_{1},x_{2}\in[0,1)$ and let $z_{1},z_{2}\in[0,1)$ be the points obtained
after applying an i.i.d. random digital shift of depth $m$ to $x_{1}$ and
$x_{2}$. Then we have

$\mathbb{E}[{\rm wal}_{k}(z_{1})\overline{{\rm
wal}_{l}(z_{2})}]=\left\\{\begin{array}[]{ll}{\rm
wal}_{k}(x_{1})\overline{{\rm wal}_{k}(x_{2})}&\mbox{if }0\leq k=l<b^{m},\\\
0&\mbox{otherwise}.\end{array}\right.$

###### Proof.

A proof of this lemma in the case $b=2$ is given in [7, Lemma 3]. For general
prime $b$ the proof follows the same arguments. ∎

Let
$\mathcal{P}=\\{\boldsymbol{x}_{0},\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{N-1}\\}$
be a point set in $[0,1)^{d}$ and let
$\widetilde{\mathcal{P}}=\\{\boldsymbol{z}_{0},\boldsymbol{z}_{1},\ldots,\boldsymbol{z}_{N-1}\\}$
be the digitally shifted (of depth $m$) version thereof. Then, applying Lemma
13 to (16), we obtain

$\displaystyle\mathbb{E}[(L_{2,N}^{{\rm per}}(\widetilde{\mathcal{P}}))^{2}]$
$\displaystyle=$
$\displaystyle-\frac{N^{2}}{3^{d}}+\frac{1}{3^{d}}\sum_{n,p=0}^{N-1}\sum_{\boldsymbol{k},\boldsymbol{\ell}\in\mathbb{N}_{0}^{d}}\rho_{b}(\boldsymbol{k},\boldsymbol{\ell})\mathbb{E}[{\rm
wal}_{\boldsymbol{k}}(\boldsymbol{z}_{n})\overline{{\rm
wal}_{\boldsymbol{\ell}}(\boldsymbol{z}_{p})}]$ (17) $\displaystyle=$
$\displaystyle-\frac{N^{2}}{3^{d}}+\frac{1}{3^{d}}\sum_{n,p=0}^{N-1}\sum_{\boldsymbol{k}\in\\{0,1,\ldots,b^{m}-1\\}^{d}}\rho_{b}(\boldsymbol{k},\boldsymbol{k}){\rm
wal}_{\boldsymbol{k}}(\boldsymbol{x}_{n})\overline{{\rm
wal}_{\boldsymbol{k}}(\boldsymbol{x}_{p})}$ $\displaystyle=$
$\displaystyle-\frac{N^{2}}{3^{d}}+\frac{1}{3^{d}}\sum_{\boldsymbol{k}\in\\{0,1,\ldots,b^{m}-1\\}^{d}}\rho_{b}(\boldsymbol{k},\boldsymbol{k})\left|\sum_{n=0}^{N-1}{\rm
wal}_{\boldsymbol{k}}(\boldsymbol{x}_{n})\right|^{2}.$

In this formula only the “diagonal terms” $\rho_{b}(k,k)$ appear. These terms
can be explicitly computed. In the following we simplify the notation and
write $\rho_{b}(k):=\rho_{b}(k,k)$ for $k\in\mathbb{N}_{0}$.

######  Lemma 14.

For $k\in\mathbb{N}$ we have

$\rho_{b}(k)=\left\\{\begin{array}[]{ll}\frac{3}{b^{2a}}\left(-\frac{1}{3}+\frac{1}{2\sin^{2}(\kappa_{a-1}\pi/b)}\right)&\mbox{
if $k=\kappa_{a-1}b^{a-1}$ with $a\in\mathbb{N}$ and
$\kappa_{a-1}\in\mathbb{Z}_{b}^{*}$},\\\\[10.00002pt]
\frac{3}{b^{2a}}\left(-\frac{1}{3}+\frac{1}{\sin^{2}(\kappa_{a-1}\pi/b)}\right)&\mbox{
if $k=\kappa_{a-1}b^{a-1}+k^{\prime}$ with $a\in\mathbb{N}$,
$\kappa_{a-1}\in\mathbb{Z}_{b}^{*}$}\\\ &\mbox{ and $1\leq
k^{\prime}<b^{a-1}$},\end{array}\right.$

where $\mathbb{Z}_{b}^{*}:=\mathbb{Z}_{b}\setminus\\{0\\}$.

###### Proof.

For $k\in\mathbb{N}$ we have

$\displaystyle\rho_{b}(k)$ $\displaystyle=$
$\displaystyle\int_{0}^{1}\int_{0}^{1}\sum_{h=-\infty}^{\infty}\frac{1}{r(h)^{2}}\exp(2\pi\mathtt{i}h(x-y))\overline{{\rm
wal}_{k}(x)}{\rm wal}_{k}(y)\,\mathrm{d}x\,\mathrm{d}y$ $\displaystyle=$
$\displaystyle\int_{0}^{1}\int_{0}^{1}\left(1+\frac{3}{2\pi^{2}}\sum_{h=-\infty\atop
h\not=0}^{\infty}\frac{1}{h^{2}}\exp(2\pi\mathtt{i}h(x-y))\right)\overline{{\rm
wal}_{k}(x)}{\rm wal}_{k}(y)\,\mathrm{d}x\,\mathrm{d}y.$

The second Bernoulli polynomial is given by $B_{2}(x)=x^{2}-x+\frac{1}{6}$ and
it is well known, that this polynomial has the Fourier expansion

$B_{2}(x)=\frac{1}{2\pi^{2}}\sum_{h=-\infty\atop
h\not=0}^{\infty}\frac{\exp(2\pi\mathtt{i}hx)}{h^{2}}\quad\quad\mbox{for
$x\in(0,1)$.}$

From this we see that

$\displaystyle\rho_{b}(k)$ $\displaystyle=$
$\displaystyle\int_{0}^{1}\int_{0}^{1}\left(1+3B_{2}(|x-y|)\right)\overline{{\rm
wal}_{k}(x)}{\rm wal}_{k}(y)\,\mathrm{d}x\,\mathrm{d}y$ $\displaystyle=$
$\displaystyle\int_{0}^{1}\int_{0}^{1}\left(\frac{3}{2}+3|x-y|^{2}-3|x-y|\right)\overline{{\rm
wal}_{k}(x)}{\rm wal}_{k}(y)\,\mathrm{d}x\,\mathrm{d}y$ $\displaystyle=$
$\displaystyle 3\int_{0}^{1}\int_{0}^{1}|x-y|^{2}\ \overline{{\rm
wal}_{k}(x)}{\rm
wal}_{k}(y)\,\mathrm{d}x\,\mathrm{d}y-3\int_{0}^{1}\int_{0}^{1}|x-y|\
\overline{{\rm wal}_{k}(x)}{\rm wal}_{k}(y)\,\mathrm{d}x\,\mathrm{d}y.$

It follows from [7, Appendix A] that for
$k=\kappa_{a-1}b^{a-1}+\cdots+\kappa_{1}b+\kappa_{0}$, with
$\kappa_{a-1}\in\mathbb{Z}_{b}^{*}$ we have

$\int_{0}^{1}\int_{0}^{1}|x-y|\ \overline{{\rm wal}_{k}(x)}{\rm
wal}_{k}(y)\,\mathrm{d}x\,\mathrm{d}y=\frac{1}{b^{2a}}\left(\frac{1}{3}-\frac{1}{\sin^{2}(\kappa_{a-1}\pi/b)}\right).$

Inserting this we obtain further

$\displaystyle\rho_{b}(k)$ $\displaystyle=$
$\displaystyle-6\int_{0}^{1}x\,\overline{{\rm
wal}_{k}(x)}\,\mathrm{d}x\int_{0}^{1}y\,{\rm
wal}_{k}(y)\,\mathrm{d}y-\frac{3}{b^{2a}}\left(\frac{1}{3}-\frac{1}{\sin^{2}(\kappa_{a-1}\pi/b)}\right)$
(18) $\displaystyle=$ $\displaystyle-6\left(\int_{0}^{1}x\,\overline{{\rm
wal}_{k}(x)}\,\mathrm{d}x\right)^{2}-\frac{1}{b^{2a}}\left(1-\frac{3}{\sin^{2}(\kappa_{a-1}\pi/b)}\right)$

where $k=\kappa_{a-1}b^{a-1}+\cdots+\kappa_{1}b+\kappa_{0}$, with
$\kappa_{a-1}\in\mathbb{Z}_{b}^{*}$. We have

$\int_{0}^{1}x\,\overline{{\rm
wal}_{k}(x)}\,\mathrm{d}x=\left\\{\begin{array}[]{ll}\frac{1}{b^{a}({\rm
e}^{-2\pi\mathtt{i}\kappa_{a-1}/b}-1)}&\mbox{ if $k=\kappa_{a-1}b^{a-1}$ with
$\kappa_{a-1}\in\mathbb{Z}_{b}^{*}$},\\\ 0&\mbox{
otherwise}.\end{array}\right.$

Hence

$\left(\int_{0}^{1}x\,\overline{{\rm
wal}_{k}(x)}\,\mathrm{d}x\right)^{2}=\left\\{\begin{array}[]{ll}\frac{1}{4b^{2a}\sin^{2}(\kappa_{a-1}\pi/b)}&\mbox{
if $k=\kappa_{a-1}b^{a-1}$ with $\kappa_{a-1}\in\mathbb{Z}_{b}^{*}$},\\\
0&\mbox{ otherwise}.\end{array}\right.$

Inserting this result into (18) gives the desired result. ∎

### Periodic discrepancy of digitally shifted digital nets.

Now assume that we are given a digital $(t,m,d)$-net over $\mathbb{Z}_{b}$,
where $b$ is the same prime number as used in the definition of the Walsh
functions. Denote the $m\times m$ generating matrices of the digital net by
$C_{1},C_{2},\ldots,C_{d}$. The dual net is defined as

$\mathcal{D}=\mathcal{D}(C_{1},\ldots,C_{d})=\\{(k_{1},\ldots,k_{d})\in\mathbb{N}_{0}^{d}\
:\ C_{1}^{\top}\vec{k}_{1}+\cdots+C_{d}^{\top}\vec{k}_{d}=\vec{0}\\}.$

Here, for $k\in\mathbb{N}_{0}$ with $b$-adic expansion
$k=\kappa_{0}+\kappa_{1}b+\kappa_{2}b^{2}+\cdots$ with digits
$\kappa_{i}\in\mathbb{Z}_{b}$, $i\in\mathbb{N}_{0}$, we write
$\vec{k}=(\kappa_{0},\kappa_{1},\ldots,\kappa_{m-1})^{\top}$. It is well known
(see, e.g., [8, Lemma 4.75]), that for a digital net
$\\{\boldsymbol{x}_{0},\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{b^{m}-1}\\}$
we have

$\sum_{n=0}^{b^{m}-1}{\rm
wal}_{\boldsymbol{k}}(\boldsymbol{x}_{n})=\left\\{\begin{array}[]{ll}b^{m}&\mbox{
if $\boldsymbol{k}\in\mathcal{D}$,}\\\ 0&\mbox{ if
$\boldsymbol{k}\not\in\mathcal{D}$.}\end{array}\right.$

From (17) we therefore obtain

$\displaystyle\mathbb{E}[(L_{2,b^{m}}^{{\rm
per}}(\widetilde{\mathcal{P}}))^{2}]=\frac{b^{2m}}{3^{d}}\sum_{\boldsymbol{k}\in\mathcal{D}^{*}\cap\\{0,1,\ldots,b^{m}-1\\}^{d}}\rho_{b}(\boldsymbol{k}),$

where $\mathcal{D}^{*}:=\mathcal{D}\setminus\\{\boldsymbol{0}\\}$. We re-write
the above expression further since this will be useful for the following
considerations. We can write

$\displaystyle\mathbb{E}[(L_{2,b^{m}}^{{\rm
per}}(\widetilde{\mathcal{P}}))^{2}]=\frac{b^{2m}}{3^{d}}\sum_{\emptyset\not=\mathfrak{u}\subseteq[d]}\mathcal{B}(\mathfrak{u}),$
(19)

where

$\mathcal{B}(\mathfrak{u}):=\sum_{\boldsymbol{k}_{\mathfrak{u}}\\{1,\ldots,b^{m}-1\\}^{|\mathfrak{u}|}\atop\sum_{j\in\mathfrak{u}}C_{j}^{\top}\vec{k}_{j}=\vec{0}}\prod_{j\in\mathfrak{u}}\rho_{b}(k_{j}).$

######  Theorem 15.

Let $\mathcal{P}$ be a digital $(t,m,d)$-net over $\mathbb{Z}_{b}$ and let
$\widetilde{\mathcal{P}}$ be a digitally shifted (of depth $m$) version of
this net. Then the mean-square periodic $L_{2}$ discrepancy over all digital
shifts of depth $m$ is bounded as

$\displaystyle\mathbb{E}[(L_{2,b^{m}}^{{\rm
per}}(\widetilde{\mathcal{P}}))^{2}]\leq
b^{2t}(m-t)^{d-1}\left(\frac{1+b^{2}}{3}\right)^{d}.$

For the proof of Theorem 15 we need a further lemma.

######  Lemma 16.

Let $C_{1},\ldots,C_{d}$ be the generating matrices of a digital $(t,m,d)$-net
over $\mathbb{Z}_{b}$. Further define $\mathcal{B}$ as above. Then for any
$\mathfrak{u}\subseteq[d]$, $\mathfrak{u}\not=\emptyset$, we have

$\mathcal{B}(\mathfrak{u})\leq\frac{b^{2t}}{b^{2m}}(m-t)^{|\mathfrak{u}|-1}b^{2|\mathfrak{u}|}.$

###### Proof.

We use the method from [3, Proof of Lemma 7]. To simplify the notation we show
the result only for $\mathfrak{u}=[d]$. The other cases follow by the same
arguments. We have, for
$k_{j}=\kappa_{j,0}+\kappa_{j,1}b+\cdots+\kappa_{j,a_{j}-1}b^{a_{j}-1}$ and
$k_{j,a_{j}-1}\in\mathbb{Z}_{b}^{*}$ for $j\in[d]$,

$\displaystyle\mathcal{B}([d])$ $\displaystyle=$
$\displaystyle\underbrace{\sum_{k_{1}=1}^{b^{m}-1}\ldots\sum_{k_{d}=1}^{b^{m}-1}}_{C_{1}^{\top}\vec{k}_{1}+\cdots+C_{d}^{\top}\vec{k}_{d}=\vec{0}}\prod_{j=1}^{d}\rho_{b}(k_{j})$
$\displaystyle=$
$\displaystyle\sum_{a_{1},\ldots,a_{d}=1}^{m}\prod_{j=1}^{d}\frac{3}{b^{2a_{j}}}\underbrace{\sum_{k_{1}=b^{a_{1}-1}}^{b^{a_{1}}-1}\ldots\sum_{k_{d}=b^{a_{d}-1}}^{b^{a_{d}}-1}}_{C_{1}^{\top}\vec{k}_{1}+\cdots+C_{d}^{\top}\vec{k}_{d}=\vec{0}}\prod_{j=1}^{d}\left(-\frac{1}{3}+\frac{1}{z(k_{j})\sin^{2}(\kappa_{a_{j}-1}\pi/b)}\right),$

where $z(k_{j})=2$, if $k_{j}^{\prime}=0$ and $z(k_{j})=1$ otherwise (remember
that
$k_{j}^{\prime}=\kappa_{j,0}+\kappa_{j,1}b+\cdots+\kappa_{j,a_{j}-2}b^{a_{j}-2}$).
Hence

$\mathcal{B}([d])\leq\sum_{a_{1},\ldots,a_{d}=1}^{m}\prod_{j=1}^{d}\frac{3}{b^{2a_{j}}}\underbrace{\sum_{k_{1}=b^{a_{1}-1}}^{b^{a_{1}}-1}\ldots\sum_{k_{d}=b^{a_{d}-1}}^{b^{a_{d}}-1}}_{C_{1}^{\top}\vec{k}_{1}+\cdots+C_{d}^{\top}\vec{k}_{d}=\vec{0}}\prod_{j=1}^{d}\left(-\frac{1}{3}+\frac{1}{\sin^{2}(\kappa_{a_{j}-1}\pi/b)}\right).$
(20)

For $j\in[d]$ and $i\in[m]$ let $\vec{c}_{j,i}^{\;\top}$ denote the $i$-th row
vector of the matrix $C_{j}$. For $b^{a_{j}-1}\leq k_{j}\leq b^{a_{j}}-1$, the
$b$-adic digit expansion of $k_{j}$ is of the form

$k_{j}=\kappa_{j,0}+\kappa_{j,1}b+\cdots+\kappa_{j,a_{j}-2}b^{a_{j}-2}+\kappa_{j,a_{j}-1}b^{a_{j}-1}$

with $\kappa_{j,a_{j}-1}\in\mathbb{Z}_{b}^{*}$. Hence the condition in sum
(20) can be written as

$\displaystyle\vec{c}_{1,1}\kappa_{1,0}+\cdots+\vec{c}_{1,a_{1}-1}\kappa_{1,a_{1}-2}+\vec{c}_{1,a_{1}}\kappa_{1,a_{1}-1}+$
$\displaystyle\vec{c}_{2,1}\kappa_{2,0}+\cdots+\vec{c}_{2,a_{2}-1}\kappa_{2,a_{2}-2}+\vec{c}_{2,a_{2}}\kappa_{2,a_{2}-1}+$
$\displaystyle\vdots$ (21)
$\displaystyle\vec{c}_{s,1}\kappa_{d,0}+\cdots+\vec{c}_{d,a_{d}-1}\kappa_{d,a_{d}-2}+\vec{c}_{d,a_{d}}\kappa_{d,a_{d}-1}\hskip
8.5359pt$ $\displaystyle=$ $\displaystyle\vec{0}.$

Since by the digital $(t,m,d)$-net property (see Definition 1) the vectors

$\vec{c}_{1,1},\ldots,\vec{c}_{1,a_{1}},\ldots,\vec{c}_{d,1},\ldots,\vec{c}_{d,a_{d}}$

are linearly independent as long as $a_{1}+\cdots+a_{d}\leq m-t,$ we must have

$a_{1}+\cdots+a_{d}\geq m-t+1.$ (22)

Let now $A$ denote the $m\times(a_{1}+\cdots+a_{d}-d)$ matrix with the column
vectors given by
$\vec{c}_{1,1},\ldots,\vec{c}_{1,a_{1}-1},\ldots,\vec{c}_{d,1},\ldots,\vec{c}_{d,a_{d}-1}$,
i.e.,

$A:=(\vec{c}_{1,1},\ldots,\vec{c}_{1,a_{1}-1},\ldots,\vec{c}_{d,1},\ldots,\vec{c}_{d,a_{d}-1}).$

Further let

$\vec{f}_{\kappa_{1,a_{1}-1},\ldots,\kappa_{d,a_{d}-1}}:=-(\vec{c}_{1,a_{1}}\kappa_{1,a_{1}-1}+\cdots+\vec{c}_{d,a_{d}}\kappa_{d,a_{d}-1})\in\mathbb{Z}_{b}^{m}$

and

$\vec{k}:=(\kappa_{1,0},\ldots,\kappa_{1,a_{1}-2},\ldots,\kappa_{d,0},\ldots,\kappa_{d,a_{d}-2})^{\top}\in\mathbb{Z}_{b}^{a_{1}+\cdots+a_{d}-d}.$

Then the linear equation system (4) can be written as

$A\vec{k}=\vec{f}_{\kappa_{1,a_{1}-1},\ldots,\kappa_{d,a_{d}-1}}$ (23)

and hence

$\displaystyle\underbrace{\sum_{k_{1}=b^{a_{1}-1}}^{b^{a_{1}}-1}\ldots\sum_{k_{d}=b^{a_{d}-1}}^{b^{a_{d}}-1}}_{C_{1}^{\top}\vec{k}_{1}+\cdots+C_{d}^{\top}\vec{k}_{d}=\vec{0}}\prod_{j=1}^{d}\left(-\frac{1}{3}+\frac{1}{\sin^{2}(\kappa_{a_{j}-1}\pi/b)}\right)$
$\displaystyle=$
$\displaystyle\sum_{\kappa_{1,a_{1}-1},\ldots,\kappa_{d,a_{d}-1}=1}^{b-1}\prod_{j=1}^{d}\left(-\frac{1}{3}+\frac{1}{\sin^{2}(\kappa_{j,a_{j}-1}\pi/b)}\right)\sum_{\vec{k}\in\mathbb{Z}_{b}^{a_{1}+\cdots+a_{d}-d}\atop
A\vec{k}=\vec{f}_{\kappa_{1,a_{1}-1},\ldots,\kappa_{d,a_{d}-1}}}1$
$\displaystyle=$
$\displaystyle\sum_{\kappa_{1,a_{1}-1},\ldots,\kappa_{d,a_{d}-1}=1}^{b-1}\prod_{j=1}^{d}\left(-\frac{1}{3}+\frac{1}{\sin^{2}(\kappa_{j,a_{j}-1}\pi/b)}\right)\\#\\{\vec{k}\in\mathbb{Z}_{b}^{a_{1}+\cdots+a_{d}-d}\
:\ A\vec{k}=\vec{f}_{\kappa_{1,a_{1}-1},\ldots,\kappa_{d,a_{d}-1}}\\}.$

By the definition of the matrix $A$ and since $C_{1},\ldots,C_{d}$ are the
generating matrices of a digital $(t,m,d)$-net over $\mathbb{Z}_{b}$ we have

${\rm rank}(A)=\left\\{\begin{array}[]{ll}a_{1}+\cdots+a_{d}-d&\mbox{ if
}a_{1}+\cdots+a_{d}-d\leq m-t,\\\ \geq m-t&\mbox{ else}.\end{array}\right.$

Let $L$ denote the linear space of solutions of the homogeneous system
$A\vec{k}=\vec{0}$ and let ${\rm dim}(L)$ denote the dimension of $L$. Then it
follows that

${\rm dim}(L)=\left\\{\begin{array}[]{ll}0&\mbox{ if }a_{1}+\cdots+a_{d}-d\leq
m-t,\\\ \leq a_{1}+\cdots+a_{d}-d-m+t&\mbox{ else}.\end{array}\right.$

Hence if $a_{1}+\cdots+a_{d}-d\leq m-t$ we find that the system (23) has at
most 1 solution and if $a_{1}+\cdots+a_{d}-d>m-t$ the system (23) has at most
$b^{a_{1}+\cdots+a_{d}-d-m+t}$ solutions, i.e.,

$\displaystyle\underbrace{\sum_{k_{1}=b^{a_{1}-1}}^{b^{a_{1}}-1}\ldots\sum_{k_{d}=b^{a_{d}-1}}^{b^{a_{d}}-1}}_{C_{1}^{\top}\vec{k}_{1}+\cdots+C_{d}^{\top}\vec{k}_{d}=\vec{0}}\prod_{j=1}^{d}\left(-\frac{1}{3}+\frac{1}{\sin^{2}(\kappa_{a_{j}-1}\pi/b)}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{\kappa_{1,a_{1}-1},\ldots,\kappa_{d,a_{d}-1}=1}^{b-1}\prod_{j=1}^{d}\left(-\frac{1}{3}+\frac{1}{\sin^{2}(\kappa_{j,a_{j}-1}\pi/b)}\right)$
$\displaystyle\hskip 56.9055pt\times\left\\{\begin{array}[]{ll}1&\mbox{ if
}a_{1}+\cdots+a_{d}-d\leq m-t,\\\ b^{a_{1}+\cdots+a_{d}-d-m+t}&\mbox{ if
}a_{1}+\cdots+a_{d}-d>m-t.\end{array}\right.$

In [6, Appendix C] it is shown that
$\sum_{\kappa=1}^{b-1}\frac{1}{\sin^{2}(\kappa\pi/b)}=\frac{b^{2}-1}{3}$.
Hence

$\displaystyle\underbrace{\sum_{k_{1}=b^{a_{1}-1}}^{b^{a_{1}}-1}\ldots\sum_{k_{d}=b^{a_{d}-1}}^{b^{a_{d}}-1}}_{C_{1}^{\top}\vec{k}_{1}+\cdots+C_{d}^{\top}\vec{k}_{d}=\vec{0}}\prod_{j=1}^{d}\left(-\frac{1}{3}+\frac{1}{\sin^{2}(\kappa_{a_{j}-1}\pi/b)}\right)$
$\displaystyle\leq$
$\displaystyle\left(\frac{b^{2}-b}{3}\right)^{d}\times\left\\{\begin{array}[]{ll}1&\mbox{
if }a_{1}+\cdots+a_{d}\leq m-t+d,\\\ b^{a_{1}+\cdots+a_{d}-d-m+t}&\mbox{ if
}a_{1}+\cdots+a_{d}>m-t+d.\end{array}\right.$

Therefore together with condition (22) we obtain

$\displaystyle\mathcal{B}([d])\leq(b^{2}-b)^{d}\left(\sum_{a_{1},\ldots,a_{d}=1\atop
m-t+1\leq a_{1}+\cdots+a_{d}\leq
m-t+d}^{m}\frac{1}{b^{2(a_{1}+\cdots+a_{d})}}+\sum_{a_{1},\ldots,a_{d}=1\atop
a_{1}+\cdots+a_{d}>m-t+d}^{m}\frac{b^{a_{1}+\cdots+a_{d}-d-m+t}}{b^{2(a_{1}+\cdots+a_{d})}}\right).$

Now we have to estimate the two sums in the above expression. First we have

$\displaystyle\Sigma_{1}$ $\displaystyle:=$
$\displaystyle\sum_{a_{1},\ldots,a_{d}=1\atop
a_{1}+\cdots+a_{d}>m-t+d}^{m}\frac{b^{a_{1}+\cdots+a_{d}-d-m+t}}{b^{2(a_{1}+\cdots+a_{d})}}$
$\displaystyle=$
$\displaystyle\frac{b^{t}}{b^{m+d}}\sum_{l=m-t+d+1}^{dm}\frac{1}{b^{l}}\sum_{a_{1},\ldots,a_{d}=1\atop
a_{1}+\cdots+a_{d}=l}^{m}1$ $\displaystyle=$
$\displaystyle\frac{b^{t}}{b^{m+d}}\sum_{l=m-t+1}^{d(m-1)}\frac{1}{b^{l+d}}\sum_{a_{1},\ldots,a_{d}=0\atop
a_{1}+\cdots+a_{d}=l}^{m-1}1$ $\displaystyle\leq$
$\displaystyle\frac{b^{t}}{b^{m+2d}}\sum_{l=m-t+1}^{\infty}{l+d-1\choose
d-1}\frac{1}{b^{l}},$

where we used the fact that for fixed $l$ the number of non-negative integer
solutions of $a_{1}+\cdots+a_{d}=l$ is given by ${l+d-1\choose d-1}$.

It follows from the binomial theorem (see, e.g., [7, Lemma 6]) that for $b>1$
and integers $d,t_{0}>0$ we have

$\sum_{l=t_{0}}^{\infty}{l+d-1\choose d-1}\frac{1}{b^{l}}\leq
b^{-t_{0}}{t_{0}+d-1\choose d-1}\left(\frac{b-1}{b}\right)^{-d}.$ (26)

Using (26) we now obtain

$\displaystyle\Sigma_{1}$ $\displaystyle\leq$
$\displaystyle\frac{b^{t}}{b^{m+2d}}\frac{1}{b^{m-t+1}}{m-t+d\choose
d-1}\left(\frac{b-1}{b}\right)^{-d}$ (27) $\displaystyle=$
$\displaystyle\frac{b^{2t}}{b^{2m}}\frac{1}{b(b^{2}-b)^{d}}{m-t+d\choose
d-1}.$

Finally, since

${m-t+d\choose d-1}=\frac{(m-t+2)(m-t+3)\cdots(m-t+d)}{1\cdot
2\cdots(d-1)}\leq(m-t+2)^{d-1},$

we obtain

$\Sigma_{1}\leq\frac{b^{2t}}{b^{2m}}\frac{1}{b(b^{2}-b)^{d}}(m-t+2)^{d-1}.$

Now we estimate

$\Sigma_{2}:=\sum_{a_{1},\ldots,a_{d}=1\atop m-t+1\leq a_{1}+\cdots+a_{d}\leq
m-t+d}^{m}\frac{1}{b^{2(a_{1}+\cdots+a_{d})}}.$

If $m-t\geq d-1$ we proceed similarly to above and obtain

$\displaystyle\Sigma_{2}$ $\displaystyle=$
$\displaystyle\sum_{l=m-t-d+1}^{m-t}{l+d-1\choose d-1}\frac{1}{b^{2(l+d)}}$
(28) $\displaystyle\leq$ $\displaystyle\frac{1}{b^{2(m-t+1)}}{m-t\choose
d-1}\left(\frac{b^{2}-1}{b^{2}}\right)^{-d}$ $\displaystyle=$
$\displaystyle\frac{b^{2d}}{b^{2}(b^{2}-1)^{d}}\frac{b^{2t}}{b^{2m}}{m-t\choose
d-1}.$

If $m-t<d-1$, then we have

$\displaystyle\Sigma_{2}$ $\displaystyle=$
$\displaystyle\sum_{l=d}^{m-t+d}\frac{1}{b^{2l}}\sum_{a_{1},\ldots,a_{d}=1\atop
a_{1}+\cdots+a_{d}=l}^{m}1$ (29) $\displaystyle\leq$
$\displaystyle\sum_{l=0}^{m-t}\frac{1}{b^{2(l+d)}}\sum_{a_{1},\ldots,a_{d}=0\atop
a_{1}+\cdots+a_{d}=l}^{m-1}1$ $\displaystyle\leq$
$\displaystyle\frac{1}{b^{2d}}\sum_{l=0}^{\infty}{l+d-1\choose
d-1}\frac{1}{b^{2l}}$ $\displaystyle=$
$\displaystyle\frac{1}{b^{2d}}\frac{b^{2d}}{(b^{2}-1)^{d}}$
$\displaystyle\leq$
$\displaystyle\frac{b^{2d}}{b^{2}(b^{2}-1)^{d}}\frac{b^{2t}}{b^{2m}},$ (30)

where we used $b^{2-2d}\leq b^{2t-2m}$ in the last step. Hence we have in any
case

$\Sigma_{2}\leq\frac{b^{2d}}{b^{2}(b^{2}-1)^{d}}\frac{b^{2t}}{b^{2m}}\max\left(1,{m-t\choose
d-1}\right).$

Putting things together we finally obtain

$\displaystyle\mathcal{B}([d])$ $\displaystyle\leq$
$\displaystyle(b^{2}-b)^{d}\left(\frac{b^{2d}}{b^{2}(b^{2}-1)^{d}}\frac{b^{2t}}{b^{2m}}\max\left(1,{m-t\choose
d-1}\right)+\frac{b^{2t}}{b^{2m}}\frac{1}{b(b^{2}-b)^{d}}(m-t+2)^{d-1}\right)$
$\displaystyle\leq$
$\displaystyle\frac{b^{2t}}{b^{2m}}\left(\frac{b^{3d}}{b^{2}(b+1)^{d}}\max\left(1,{m-t\choose
d-1}\right)+\frac{1}{b}(m-t+2)^{d-1}\right)$ $\displaystyle\leq$
$\displaystyle\frac{b^{2t}}{b^{2m}}\left(\frac{b^{2d}}{b^{2}}(m-t)^{d-1}+\frac{1}{b}(m-t+2)^{d-1}\right)$
$\displaystyle=$
$\displaystyle\frac{b^{2t}}{b^{2m}}(m-t)^{d-1}\left(b^{2(d-1)}+\frac{1}{b}\left(1+\frac{2}{m-t}\right)^{d-1}\right)$
$\displaystyle\leq$
$\displaystyle\frac{b^{2t}}{b^{2m}}(m-t)^{d-1}\left(b^{2(d-1)}+\frac{1}{b}3^{d-1}\right)$
$\displaystyle\leq$ $\displaystyle\frac{b^{2t}}{b^{2m}}(m-t)^{d-1}b^{2d}.$

∎

Now we can give the proof of Theorem 15.

###### Proof of Theorem 15.

Using (19) and Lemma 16 we obtain

$\displaystyle\mathbb{E}[(L_{2,b^{m}}^{{\rm
per}}(\widetilde{\mathcal{P}}))^{2}]\leq\frac{b^{2t}}{3^{d}}\sum_{\emptyset\not=\mathfrak{u}\subseteq[d]}(m-t)^{|\mathfrak{u}|-1}b^{2|\mathfrak{u}|}\leq
b^{2t}(m-t)^{d-1}\left(\frac{1+b^{2}}{3}\right)^{d}.$

This finishes the proof of Theorem 15. ∎

Theorem 15 implies that the lower bound (5) is best possible.

######  Corollary 17.

Let $p\in[1,2]$. For every $m,d\in\mathbb{N}$ with $m,d\geq 2$ and every prime
number $b\geq d-1$ we have

$\inf_{\mathcal{P}\subseteq[0,1)^{d}\atop|\mathcal{P}|=N}L_{p,N}^{{\rm
per}}(\mathcal{P})\lesssim_{d,b}(\log N)^{\frac{d-1}{2}},\quad\quad\mbox{
where $N=b^{m}$.}$

Hence, the lower bound from Corollary 11 is best possible for all $p\in(1,2]$.

###### Proof.

It is known that for every $m,d\in\mathbb{N}$, $m,d\geq 2$, and every prime
number $b\geq d-1$ there exists a digital $(0,m,d)$-net $\mathcal{P}$ in base
$b$ (constructions are due to Faure [12] and Niederreiter [27]; see also [8,
21, 28]). According to Theorem 15 there exists a digital shift of depth $m$,
such that the digitally shifted point set $\widetilde{\mathcal{P}}$ has
periodic $L_{2}$ discrepancy

$(L_{2,b^{m}}^{{\rm
per}}(\widetilde{\mathcal{P}}))^{2}\leq\left(\frac{1+b^{2}}{3}\right)^{d}m^{d-1}.$

Taking the square root yields the desired result. ∎

Note that it can be shown that a digitally shifted digital $(t,m,d)$-net over
$\mathbb{Z}_{b}$ is a $(t,m,d)$-net in base $b$ with the same $t$-parameter,
however, in general not a digital one (just adapt the proof of [6, Lemma 3]).
So the point set $\widetilde{\mathcal{P}}$ appearing in the proof of Corollary
17 is a $(0,m,d)$-net in base $b$.

######  Remark 18 (Diaphony).

We already mentioned the relation between periodic $L_{2}$ discrepancy and
diaphony. As usual, see for example [11, Section 1.2.3], we denote the
diaphony by $F_{N}$,

$F_{N}(\mathcal{P}):=\left(\sum_{\boldsymbol{k}\in\mathbb{Z}^{d}\setminus\\{\boldsymbol{0}\\}}\frac{1}{\rho(\boldsymbol{k})^{2}}\left|\frac{1}{N}\sum_{n=0}^{N-1}\exp(2\pi\mathtt{i}\boldsymbol{k}\cdot\boldsymbol{x}_{n})\right|^{2}\right),$

where for $\boldsymbol{k}=(k_{1},\ldots,k_{d})\in\mathbb{Z}^{d}$ we set
$\rho(\boldsymbol{k})=\prod_{j=1}^{d}\max(1,|k_{j}|)$. Then Theorem 15 also
implies that for every $m,d\in\mathbb{N}$ with $m,d\geq 2$ and every prime
number $b\geq d-1$ there exists an $N=b^{m}$ element point set $\mathcal{P}$
in $[0,1)^{d}$ such that

$F_{N}(\mathcal{P})\lesssim_{d}\frac{(\log N)^{\frac{d-1}{2}}}{N}.$ (31)

Previously, such a result was known only for $d=2$; see [14, 30]. The bound
(31) is best possible in the order of magnitude in $N$. According to [24] this
has been first shown by Bykovsky [1] (however, we do not have access to this
paper). Later proofs can be also found in [18, 24].

##  5 Summary and open problems

We summarize the main results about the order of magnitude of the minimal
$L_{p}$ discrepancy in $N$ and for fixed dimension $d$.

  * •

Star and extreme discrepancy: For every $p\in(1,\infty)$ and every
$d,N\in\mathbb{N}$ we have

$\inf_{\mathcal{P}\subseteq[0,1)^{d}\atop|\mathcal{P}|=N}L_{p,N}^{\bullet}(\mathcal{P})\asymp_{d,p}(1+\log
N)^{\frac{d-1}{2}},\quad\mbox{where }\bullet\in\\{{\rm star,extr}\\}.$

For $d=2$ the result even holds true for $p=1$.

  * •

Periodic $L_{p}$ discrepancy: For the periodic $L_{p}$ discrepancy for every
$p\in(1,\infty)$ and every $d,N\in\mathbb{N}$ we have

$\inf_{\mathcal{P}\subseteq[0,1)^{d}\atop|\mathcal{P}|=N}L_{p,N}^{{\rm
per}}(\mathcal{P})\gtrsim_{d,p}(1+\log N)^{\frac{d-1}{2}}.$

Again, for $d=2$ the result holds true also for $p=1$. In the other direction
so far we only have the following result. For every $p\in[1,2]$, every
$d,m\in\mathbb{N}$ with $d,m\geq 2$ and every prime number $b\geq d-1$ we have

$\inf_{\mathcal{P}\subseteq[0,1)^{d}\atop|\mathcal{P}|=N}L_{p,N}^{{\rm
per}}(\mathcal{P})\lesssim_{d}(1+\log N)^{\frac{d-1}{2}},\quad\mbox{where
$N=b^{m}$.}$ (32)

It remains an open problem to extend (32) to arbitrary $N\in\mathbb{N}$ (i.e.,
not only prime powers) and to arbitrary $p\in[1,\infty)$. In this context we
also mention the still open problem of finding for every $N\geq 2$ explicit
constructions of $N$-point sets in $[0,1)^{d}$ with the optimal order of
diaphony $F_{N}$, which is $(\log N)^{\frac{d-1}{2}}/N$.

Still there are also some open questions about relations between the three
notions of $L_{p}$ discrepancy. In particular, let $\mathcal{P}$ be an
arbitrary $N$-point set in $[0,1)^{d}$. Then the following questions arise
(see also [18]):

  * •

Is is true that $L_{p,N}^{{\rm extr}}(\mathcal{P})\asymp_{p,d}L_{p,N}^{{\rm
per}}(\mathcal{P})$? This is true for $d=1$. Note also that $L_{p,N}^{{\rm
extr}}(\mathcal{P})\leq L_{p,N}^{{\rm per}}(\mathcal{P})$.

  * •

Is it true that $L_{p,N}^{{\rm per}}(\mathcal{P})\lesssim_{p,d}L_{p,N}^{{\rm
star}}(\mathcal{P})$? Note that a corresponding inequality the other way round
is not true in general.

## References

  * [1] V.A. Bykovsky: On the right order of error of optimal cubature formulas in the spaces with dominating derivation and $L^{2}$-discrepancy of nets. Prepring, Dalnevost. Science Center of the USSR Acad. of Sciences, Vladivostok, 1985. [In Russian]
  * [2] W.W.L. Chen and M.M. Skriganov: Explicit constructions in the classical mean squares problem in irregularity of point distribution. J. Reine Angew. Math. 545: 67–95, 2002.
  * [3] Cristea L.L., Dick J., Pillichshammer F., On the mean square weighted $\mathcal{L}_{2}$ discrepancy of randomized digital nets in prime base. J. Complexity, 22: 605–629, 2006.
  * [4] J. Dick, A. Hinrichs, L. Markhasin, F. Pillichshammer, Optimal $L_{p}$ discrepancy bounds for second order digital sequences. Israel J. Math.: Israel Journal of Mathematics 221: 489–510, 2017.
  * [5] J. Dick, A. Hinrichs, and F. Pillichshammer: Proof techniques in quasi-Monte Carlo theory. J. Complexity 31: 327–371, 2015.
  * [6] J. Dick and F. Pillichshammer: Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces. J. Complexity 21: 149–195, 2005.
  * [7] J. Dick and F. Pillichshammer: On the mean square weighted $\mathcal{L}_{2}$ discrepancy of randomized digital $(t,m,s)$-nets over $\mathbb{Z}_{2}$. Acta Arith. 117(4): 371–403, 2005.
  * [8] J. Dick and F. Pillichshammer: Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press, Cambridge, 2010.
  * [9] J. Dick, F. Pillichshammer, Optimal $\mathcal{L}_{2}$ discrepancy bounds for higher order digital sequences over the finite field $\mathbb{F}_{2}$. Acta Arith. 162: 65–99, 2014.
  * [10] J. Dick, F. Pillichshammer, Explicit constructions of point sets and sequences with low discrepancy. In: P. Kritzer, H. Niederreiter, F. Pillichshammer, A. Winterhof (eds.), Uniform distribution and quasi-Monte Carlo methods - Discrepancy, Integration and Applications, Radon Series of Computational and Applied Mathematics, pp. 63–86, De Gruyter, 2014.
  * [11] M. Drmota and R. F. Tichy: Sequences, Discrepancies and Applications. Lecture Notes in Mathematics, vol. 1651, Springer, Berlin, 1997.
  * [12] H. Faure: Discrépance de suites associées à un système de numération (en dimension s). (French) Acta Arith. 41(4): 337–351, 1982.
  * [13] K.K. Frolov: Upper bounds for the errors of quadrature formulae on classes of functions. (Russian) Dokl. Akad. Nauk SSSR 231(4): 818–821, 1976.
  * [14] V.S. Grozdanov: On the diaphony of two-dimensional finite sequences. C. R. Acad. Bulgare Sci. 48(4): 15–18, 1995.
  * [15] G. Halász: On Roth’s method in the theory of irregularities of point distributions. Recent progress in analytic number theory, Vol. 2 (Durham, 1979), pp. 79–94, Academic Press, London-New York, 1981.
  * [16] A. Hinrichs and J. Oettershagen: Optimal point sets for quasi-Monte Carlo integration of bivariate periodic functions with bounded mixed derivatives. Monte Carlo and quasi-Monte Carlo methods, pp. 385–405, Springer Proc. Math. Stat., 163, Springer, [Cham], 2016.
  * [17] A. Hinrichs, R. Kritzinger, and F. Pillichshammer: Optimal order of $L_{p}$ discrepancy of digit shifted Hammersley point sets in dimension 2. Unif. Distrib. Theory 10(1): 115–133, 2015.
  * [18] A. Hinrichs, R. Kritzinger, and F. Pillichshammer: Extreme and periodic $L_{2}$ discrepancy of plane point sets. Acta Arith. 199.2: 163–198, 2021.
  * [19] R. Kritzinger, Finding exact formula for the $L_{2}$ discrepancy of digital $(0,n,2)$-nets via Haar functions, 151–187, 2019.
  * [20] R. Kritzinger, F. Pillichshammer, Digital nets in dimension two with the optimal order of $L_{p}$ discrepancy, J. Théor. Nombres Bordeaux, 179–204, 2019.
  * [21] G. Leobacher and F Pillichshammer: Introduction to quasi-Monte Carlo integration and applications. Compact Textbooks in Mathematics. Birkhäuser/Springer, Cham, 2014.
  * [22] L. Markhasin, $L_{p}$\- and $S_{p,q}^{r}B$ discrepancy of (order 2) digital nets. Acta Arith. 168: 139-159, 2015.
  * [23] V.F. Lev: On two versions of $L^{2}$-discrepancy and geometrical interpretation of diaphony. Acta Math. Hungar. 69(4): 281–300, 1995.
  * [24] V.F. Lev: The exact order of generalized diaphony and multidimensional numerical integration. J. Austral. Math. Soc. Ser. A 66(1): 1–17, 1999.
  * [25] P. Kritzer and F. Pillichshammer: An exact formula for the $L_{2}$-discrepancy of the shifted Hammersley point set. Unif. Distrib. Theory 1: 1–13, 2006.
  * [26] Matoušek, J., Geometric Discrepancy. Algorithms and Combinatorics 18, Springer Verlag, Berlin, 1999.
  * [27] Niederreiter, H., Point sets and sequences with small discrepancy. Monatsh. Math., 104: 273–337, 1987.
  * [28] Niederreiter, H., Random Number Generation and Quasi-Monte Carlo Methods. No. 63 in CBMS-NSF Series in Applied Mathematics, SIAM, Philadelphia, 1992.
  * [29] M. M. Skriganov, Harmonic analysis on totally disconnected groups and irregularities of point distributions. J. Reine Angew. Math. 600: 25–49, 2006.
  * [30] Y.-J. Xiao: The diaphony and the star-diaphony of some two-dimensional sequences. Monte Carlo and quasi-Monte Carlo methods 1998 (Claremont, CA), 459–470, Springer, Berlin, 2000.
  * [31] P. Zinterhof: Über einige Abschätzungen bei der Approximation von Funktionen mit Gleichverteilungsmethoden (German). Österr. Akad. Wiss. Math.-Naturwiss. Kl. S.-B. II 185: 121–132, 1976.

Author’s address: Institute of Financial Mathematics and Applied Number
Theory, Johannes Kepler University Linz, Austria, 4040 Linz, Altenberger
Straße 69. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>