Discrepancy Theorem

Let $s_1$, $s_2$, ... be an infinite series of real numbers lying between 0 and 1. Then corresponding to any arbitrarily large $K$, there exists a positive integer $n$ and two subintervals of equal length such that the number of $s_\nu$ with $\nu=1$, 2, ..., $n$ which lie in one of the subintervals differs from the number of such $s_\nu$ that lie in the other subinterval by more than $K$ (van der Corput 1935ab, van Aardenne-Ehrenfest 1945, 1949, Roth 1954).

This statement can be refined as follows. Let $N$ be a large integer and $s_1$, $s_2$, ..., $s_N$ be a sequence of $N$ real numbers lying between 0 and 1. Then for any integer $1\leq n\leq N$ and any real number $\alpha$ satisfying $0<\alpha<1$, let $D_n(\alpha)$ denote the number of $s_\nu$ with $\nu=1$, 2, ..., $n$ that satisfy $0\leq s_\nu<\alpha$. Then there exist $n$ and $\alpha$ such that

$$\vert D_n(\alpha)-n\alpha\vert>c_1{\ln\ln N\over\ln\ln\ln N}$$

where $c_1$ is a positive constant.

This result can be further strengthened, which is most easily done by reformulating the problem. Let $N>1$ be an integer and $P_1$, $P_2$, ..., $P_N$ be $N$ (not necessarily distinct) points in the square $0\leq x\leq 1$, $0\leq y\leq 1$. Then

$$\int_0^1\int_0^1 [S(x,y)-Nxy]^2\,dx\,dy>c_2\ln N,$$

where $c_2$ is a positive constant and $S(u,v)$ is the number of points in the rectangle $0\leq x<u$, $0\leq y<v$ (Roth 1954). Therefore,

$$\vert S(x,y)-Nxy\vert>c_3\sqrt{\ln N},$$

and the original result can be stated as the fact that there exist $n$ and $\alpha$ such that

$$\vert D_n(\alpha)-n\alpha\vert>c_4\sqrt{\ln N}\,.$$

The randomly distributed points shown in the above squares have $\vert S(x,y)-Nxy\vert^2=6.40$ and 9.11, respectively.

Similarly, the discrepancy of a set of $N$ points in a unit $d$-Hypercube satisfies

$$\vert S(x,y)-Nxy\vert>c(\ln N)^{(d-1)/2}$$

(Roth 1954, 1976, 1979, 1980).

See also 18-Point Problem, Cube Point Picking

References

Berlekamp, E. R. and Graham, R. L. ``Irregularities in the Distributions of Finite Sequences.'' J. Number Th. 2, 152-161, 1970.

Roth, K. F. ``On Irregularities of Distribution.'' Mathematika 1, 73-79, 1954.

Roth, K. F. ``On Irregularities of Distribution. II.'' Comm. Pure Appl. Math. 29, 739-744, 1976.

Roth, K. F. ``On Irregularities of Distribution. III.'' Acta Arith. 35, 373-384, 1979.

Roth, K. F. ``On Irregularities of Distribution. IV.'' Acta Arith. 37, 67-75, 1980.

van Aardenne-Ehrenfest, T. ``Proof of the Impossibility of a Just Distribution of an Infinite Sequence Over an Interval.'' Proc. Kon. Ned. Akad. Wetensch. 48, 3-8, 1945.

van Aardenne-Ehrenfest, T. Proc. Kon. Ned. Akad. Wetensch. 52, 734-739, 1949.

van der Corput, J. G. Proc. Kon. Ned. Akad. Wetensch. 38, 813-821, 1935a.

van der Corput, J. G. Proc. Kon. Ned. Akad. Wetensch. 38, 1058-1066, 1935b.