# Discrepancy

of a sequence $\omega=(\mathbf{x}_1,\ldots,\mathbf{x}_N)$ of points from the unit $s$-dimensional cube $K_s = \{\mathbf{x} : 0 \le x_\nu < 1\,,\ \nu=1,\ldots,s \}$

The norm of the functional $$\label{eq:1} \phi(\alpha;\omega) = |V| - \frac{N(V)}{N}\,,$$ calculated in some metric. Here, $|V|$ and $N(V)$ are, respectively, the volume of the domain $V = \{\mathbf{x} : 0 \le x_\nu < \alpha_\nu\,,\ \nu=1,\ldots,s \}$ and the number of the points of $\omega$ belonging to $V$. If one considers the distribution of the points of $\omega$ over domains of the type $V = \{\mathbf{x} : \alpha_\nu \le x_\nu < \beta_\nu\,,\ \nu=1,\ldots,s \}$, then, in formula (1), $\phi(\alpha;\omega)$ is usually replaced by $\phi(\alpha,\beta;\omega)$.

The following norms of the functional \eqref{eq:1} are most often used: $$D_N(\omega) = \sup_{\alpha,\beta\in K_s} |\phi(\alpha,\beta;\omega)|\ ,$$ $$D_N^*(\omega) = \sup_{\alpha\in K_s} |\phi(\alpha;\omega)|\ ,$$ $$D_N(\omega,L_p) = \left({ \int_0^1\cdots\int_0^1 |\phi(\alpha;\omega)|^p d\alpha_1\ldots d\alpha_s }\right)^{1/p} \ .$$

A sequence $\omega=(\mathbf{x}_1,\ldots,\mathbf{x}_N,\ldots)$ of points from the $s$-dimensional unit cube $K_s$ is uniformly distributed if and only if [1] $$\lim_{N\rightarrow\infty} D_N(\omega) = 0 \ .$$

For any infinite sequence $\omega=(x_1,\ldots,x_N,\ldots)$ of one-dimensional points the following theorem [3] is valid: $$\limsup N D_N(\omega) = \infty \ .$$ For any such sequence $\omega$ it is possible to find a sequence $N_1,\ldots,N_k,\ldots$ such that for $N = N_k$ one has [4], $$N D_N(\omega) > C_1 \sqrt{\log N} \ .$$ The final result [5] for infinite sequences of one-dimensional points is that for $N = N_k$: $$N D_N(\omega) > C_2 \log N \ .$$

Studies were made of the discrepancies of various concrete sequences [6][8], and the estimates from above $$N D_N(\omega,L_2) \le C_3(s) \log^{s+1} N \ ,$$ $$N D_N(\omega) \le C_4(s) \log^s N$$ were obtained, respectively, for finite and infinite sequences, as well as an estimate from below [4]: For any sequence of $N$ points, the following inequality is valid: $$N D_N(\omega,L_2) \ge C_5(s) \log^{(s+1)/2} N \ .$$

For any infinite sequence $\omega = \{\mathbf{x}_n \in K_s \}$ it is possible to find a sequence of numbers $N_1,\ldots,N_k,\ldots$ such that for $N = N_k$ one has $$N D_N(\omega,L_2) \ge C_6(s) \log^{s/2} N \ .$$

Also, $$D_N(\omega) \ge D_N(\omega,L_2) \ .$$