Star discrepancy, digital nets, and digital sequences

Fix an integer dimension $d\ge 1$. A point multiset is a finite ordered list $P=(x_0,\dots ,x_{N-1})$ with $N\ge 1$ and $x_i=(x_{i1},\dots ,x_{id})\in [0,1{)}^d$; repeated points are counted with their multiplicities. For $u=(u_1,\dots ,u_d)\in [0,1{]}^d$, its anchored half-open box and its volume are $B(u):={\prod }_{j=1}^d[0,u_j),\mathrm{vol}(B(u)):={\prod }_{j=1}^d{u}_j\mathrm{.}$ The star discrepancy of $P$ is $D_N^{\ast }(P):={\sup }_{u\in [0,1{]}^d}\mid \frac{1}{N}{\sum }_{i=0}^{N-1}{\mathbf{1}}_{B(u)}(x_i)-{\prod }_{j=1}^d{u}_j\mid \mathrm{.}$ An infinite sequence $(x_n{)}_{n\ge 0}$ in $[0,1{)}^d$ is uniformly distributed if $D_N^{\ast }(x_0,\dots ,x_{N-1})\to 0$ as $N\to \mathrm{\infty }$. For a bounded Riemann-integrable $f:[0,1{]}^d\to \mathbb{R}$, the cube integral and the point-set cube quadrature are $I_d(f):={\int }_{[0,1{]}^d}f(x)dx,Q_P(f):=\frac{1}{N}{\sum }_{i=0}^{N-1}f(x_i),$ where $I_d$ is the Riemann integral of The lower and upper Darboux integrals over a nondegenerate rectangle in ${\mathbb{R}}^m$. No randomness is part of $Q_P$.

Let $b\ge 2$ be an integer. A base-$b$ elementary interval in dimension $d$ is $E={\prod }_{j=1}^d[a_j{b}^{-k_j},(a_j+1)b^{-k_j}),$ where each $k_j\ge 0$ and each $a_j$ is an integer with $0\le a_j<b^{k_j}$. For integers $m\ge 0$ and $0\le t\le m$, a point multiset $P$ is a $(t,m,d)$-net in base $b$ if it has $b^m$ entries and every base-$b$ elementary interval with ${\sum }_{j=1}^d{k}_j=m-t$ contains exactly $b^t$ entries, counted with multiplicity. A sequence $(x_n{)}_{n\ge 0}$ in $[0,1{)}^d$ is a $(t,d)$-sequence in base $b$ if for every $m\ge t$ and $k\ge 0$, the aligned block $(x_{k{b}^m},\dots ,x_{(k+1)b^m-1})$ is a $(t,m,d)$-net.

For a prime integer $p$, we have $p\ge 2$ (Prime and composite integers: $p$ is prime when $p>1$ and its only positive divisors are $1$ and $p$). Write ${\mathbb{F}}_p:=\mathbb{Z}\mathrm{/}p\mathbb{Z}$, which is a field by For every prime $p$, the two operations on $\mathbb{Z}\mathrm{/}p$ make it a field. By Division with remainder in $\mathbb{Z}$: for $a\in \mathbb{Z}$ and $b>0$ there are unique $q,r\in \mathbb{Z}$ with $a=qb+r$ and $0\le r<b$, each residue class has exactly one representative in $\{0,\dots ,p-1\}$, and every $n\in \{0,\dots ,p^m-1\}$ has a unique base-$p$ expansion $n={\sum }_{r=1}^m{n}_{r-1}{p}^{r-1}$ with digits $n_{r-1}\in \{0,\dots ,p-1\}$. The integer powers use Integer powers $a^m$. A digital point set in base $p$ is generated from matrices $C_1,\dots ,C_d\in {\mathbb{F}}_p^{m\times m}$ as follows. For each such $n$, let $v(n)=(n_0,\dots ,n_{m-1}{)}^T\in {\mathbb{F}}_p^m$, interpreting each digit as its residue class, and compute $y^{(j)}=C_{j}v(n)$ in ${\mathbb{F}}_p^m$. Taking the unique representatives $y_r^{(j)}\in \{0,\dots ,p-1\}$, set $x_{n,j}:={\sum }_{r=1}^m{y}_r^{(j)}{p}^{-r}\mathrm{.}$ Since $0\le y_r^{(j)}\le p-1$, the finite geometric sum gives $0\le x_{n,j}\le {\sum }_{r=1}^m(p-1)p^{-r}=1-p^{-m}<1$; the identity follows by telescoping with the integer-power laws Laws of integer exponents, and $p^{-m}>0$ by Monotonicity of $x\mapsto x^n$ and of $n\mapsto a^n$ and Inverses of positives are positive, and reciprocation reverses order. It is a digital $(t,m,d)$-net only if this generated point multiset also satisfies the stated $(t,m,d)$-net counting condition; arbitrary generator matrices need not do so.

A digital sequence is generated by infinite matrices $C_j=(c_{r,k}^{(j)}{)}_{r,k\ge 1}$ over ${\mathbb{F}}_p$. For each $n\ge 0$, pad its finite base-$p$ expansion with zero digits and, for every $r,j$, compute the finite field sum $y_{r,j}(n)={\sum }_{k\ge 1}{c}_{r,k}^{(j)}{n}_{k-1}$; only finitely many summands are nonzero. Let ${\tilde{y}}_{r,j}(n)\in \{0,\dots ,p-1\}$ be its unique integer representative. The output coordinate is the real series $x_{n,j}:={\sum }_{r=1}^{\mathrm{\infty }}{\tilde{y}}_{r,j}(n)p^{-r}\mathrm{.}$ This series is defined by Series, partial sums, convergence and the sum, divergence, and the tail series and converges: its terms satisfy $0\le {\tilde{y}}_{r,j}(n)p^{-r}\le (p-1)p^{-r}$; since $p\ge 2$, Inverses of positives are positive, and reciprocation reverses order gives $p^{-1}\in (0,1)$, and the bounding geometric series ${\sum }_{r=1}^{\mathrm{\infty }}(p-1)p^{-r}$ converges to $1$ by For $\mathrm{\mid }r\mathrm{\mid }<1$, ${\sum }_{k\ge 0}{r}^k=1\mathrm{/}(1-r)$, and for $\mathrm{\mid }r\mathrm{\mid }\ge 1$ the series diverges. The comparison theorem If $0\le a_k\le b_k$ eventually, convergence of $\sum b_k$ gives convergence of $\sum a_k$, and divergence of $\sum a_k$ gives divergence of $\sum b_k$ therefore gives convergence of the output series. Its sum lies in $[0,1]$; the resulting points are required to lie in $[0,1{)}^d$. It is a digital $(t,d)$-sequence when it also satisfies the aligned-block net condition above. No discrepancy rate follows from these definitions alone.