Discrepancy Theorem
Let 
, 
, ... be an infinite series of real numbers lying between 0 and 1. Then corresponding to any arbitrarilylarge 
, 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 subintervalby 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 realnumbers 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.
- Alexander-Conway Polynomial
- Alexander Ideal
- Alexander Invariant
- Alexander Matrix
- Alexander Polynomial
- Alexander's Horned Sphere
- Alexander-Spanier Cohomology
- Alexander's Theorem
- Algebra
- Algebraic Closure
- Algebraic Coding Theory
- Algebraic Curve
- Algebraic Function
- Algebraic Function Field
- Algebraic Geometry
- Algebraic Integer
- Algebraic Invariant
- Algebraic Knot
- Algebraic Link
- Algebraic Number
- Algebraic Number Field
- Algebraic Surface
- Algebraic Tangle
- Algebraic Topology
- Algebraic Variety