Discrepancy of lattice points in round convex bodies

by Gyula Karolyi


Consider a sequence P of N points and a family F of
measurable test sets in the unit square. For an element
A of F, the discrepancy of P with respect to A is
the difference between the "actual number" of points
in A (that is, |P\cap A|) and the "expected number"
of such points, which is N times the area of A.
Taking the supremum over all test sets we get the
discrepancy of P with respect to F.

According to the Schmidt-Halasz-Wagner theorem, in
case of axis-parallel rectangles the discrepancy is
always at least clogN for some positive constant c.
Moreover, explicit number theoretic constructions show
that this lower bound cannot be improved upon. Note that
the discrepancy of a random point set would be roughly
\sqrt{N}.

Due to the work of Beck, Matousek, Roth, Schmidt, Welzl,
and more, similar results exist for various families F.
However, apart from the above example, no explicit constructions
are known that match the lower bounds. For example, with
respect to circles in the unit square, every N-element
sequence has a discrepancy at least N^{1/4}, but
this order of magnitude can only be justified by the
probabilistic method. With respect to all convex regions
the discrepancy jumps up to roughly N^{1/3}.

For a fixed constant r>1, the convex region A with
smooth (C^2) boundary is called r-round, if the ratio
between the largest and smallest curvature around the
boundary does not exceed r. Let F=F(r) be the family
of all r-round convex regions in the unit square.
Based on a beautiful combinatorial idea of Schmidt
we prove that every N-sequence has a discrepancy
at least c(r)N^{1/3} with respect to F(r). Using a
result of Barany and Larman we also show that
appropriately scaled grids meet this lower bound.