View source for 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
\begin{equation}\label{eq:1}
\phi(\alpha;\omega) = |V| - \frac{N(V)}{N}\,,
\end{equation}
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 [[#References|[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 [[#References|[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 [[#References|[4]]],
$$
N D_N(\omega) > C_1 \sqrt{\log N} \ .
$$
The final result [[#References|[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 [[#References|[6]]]–[[#References|[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 [[#References|[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) \ .
$$


====Comments====
See also [[Distribution modulo one]]; [[Distribution modulo one, higher-dimensional]]; [[Uniform distribution]].

====References====
<table>
<TR><TD valign="top">[1]</TD> <TD valign="top">  H. Weyl,   "Ueber die Gleichverteilung von Zahlen mod Eins"  ''Math. Ann.'' , '''77'''  (1916)  pp. 313–352</TD></TR>
<TR><TD valign="top">[2]</TD> <TD valign="top">  J.G. van der Corput,   "Verteilungsfunktionen"  ''Proc. Koninkl. Ned. Akad. Wet. A'' , '''38''' :  8  (1935)  pp. 813–821; 1058–1066</TD></TR>
<TR><TD valign="top">[3]</TD> <TD valign="top">  T. van Aardenne-Ehrenfest,   "On the impossibility of a just distribution"  ''Indag. Math.'' , '''11'''  (1949)  pp. 264–269</TD></TR>
<TR><TD valign="top">[4]</TD> <TD valign="top">  K.F. Roth,   "On irregularities of distribution"  ''Mathematika'' , '''1'''  (1954)  pp. 73–79  {{ZBL|0057.28604}}</TD></TR>
<TR><TD valign="top">[5]</TD> <TD valign="top">  W.M. Schmidt,   "Irregularities of distribution VII"  ''Acta Arithm.'' , '''21'''  (1972)  pp. 45–50</TD></TR>
<TR><TD valign="top">[6]</TD> <TD valign="top">  J.H. Halton,   "On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals"  ''Numer. Math.'' , '''2''' :  2  (1960)  pp. 84–90</TD></TR>
<TR><TD valign="top">[7]</TD> <TD valign="top">  I.M. Sobol',   "The distribution of points in a cube and the approximate evaluation of integrals"  ''USSR Comp. Math. and Math. Phys.'' , '''7''' :  4  (1967)  pp. 86–112  ''Zh. Vychisl. Mat. i Mat. Fiz.'' , '''7''' :  4  (1967)  pp. 784–802</TD></TR>
<TR><TD valign="top">[8]</TD> <TD valign="top">  N.M. Korobov,   "Number-theoretical methods in approximate analysis" , Moscow  (1963)  (In Russian)</TD></TR>
<TR><TD valign="top">[9]</TD> <TD valign="top">  L. Kuipers,   H. Niederreiter,   "Uniform distribution of sequences" , Wiley  (1974) {{ZBL|0281.10001}}; repr. Dover (2006) ISBN 0-486-45019-8 </TD></TR>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Beck,   W.L. Chen,   "Irregularities of distribution" , Cambridge Univ. Press  (1987)  {{ZBL|0617.10039}}</TD></TR>
</table>

{{TEX|done}}