## Discrepancy Theorem

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

This statement can be refined as follows. Let be a large integer and , , ..., be a sequence of real numbers lying between 0 and 1. Then for any integer and any real number satisfying , let denote the number of with , 2, ..., that satisfy . Then there exist and such that

where is a positive constant.

This result can be further strengthened, which is most easily done by reformulating the problem. Let be an integer and , , ..., be (not necessarily distinct) points in the square , . Then

where is a positive constant and is the number of points in the rectangle , (Roth 1954). Therefore,

and the original result can be stated as the fact that there exist and such that

The randomly distributed points shown in the above squares have and 9.11, respectively.

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

(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.

© 1996-9 Eric W. Weisstein
1999-05-24