A great challenge in the analysis of the discrepancy function D_N is to obtain universal lower bounds on the L-infty norm of D_N in dimensions d geq 3. It follows from the average case bound of Klaus Roth that the L-infty norm of D_N is at least (log
N) ^{(d-1)/2}. It is conjectured that the L-infty bound is significantly larger, but the only definitive result is that of Wolfgang Schmidt in dimension d=2. Partial improvements of the Roth exponent (d-1)/2 in higher dimensions have been established by the authors and Armen Vagharshakyan. We survey these results, the underlying methods, and some of their connections to other subjects in probability, approximation theory, and analysis.
In the present paper, we study the geometric discrepancy with respect to families of rotated rectangles. The well-known extremal cases are the axis-parallel rectangles (logarithmic discrepancy) and rectangles rotated in all possible directions (polyn
omial discrepancy). We study several intermediate situations: lacunary sequences of directions, lacunary sets of finite order, and sets with small Minkowski dimension. In each of these cases, extensions of a lemma due to Davenport allow us to construct appropriate rotations of the integer lattice which yield small discrepancy.
The Small Ball Inequality is a conjectural lower bound on sums the L-infinity norm of sums of Haar functions supported on dyadic rectangles of a fixed volume in the unit cube. The conjecture is fundamental to questions in discrepancy theory, approxim
ation theory and probability theory. In this article, we concentrate on a special case of the conjecture, and give the best known lower bound in dimension 3, using a conditional expectation argument.
Let A_N be an N-point distribution in the unit square in the Euclidean plane. We consider the Discrepancy function D_N(x) in two dimensions with respect to rectangles with lower left corner anchored at the origin and upper right corner at the point x
. This is the difference between the actual number of points of A_N in such a rectangle and the expected number of points - N x_1x_2 - in the rectangle. We prove sharp estimates for the BMO norm and the exponential squared Orlicz norm of D_N(x). For example we show that necessarily ||D_N||_(expL^2) >c(logN)^(1/2) for some aboslute constant c>0. On the other hand we use a digit scrambled version of the van der Corput set to show that this bound is tight in the case N=2^n, for some positive integer n. These results unify the corresponding classical results of Roth and Schmidt in a sharp fashion.
In [13], K. Roth showed that the expected value of the $L^2$ discrepancy of the cyclic shifts of the $N$ point van der Corput set is bounded by a constant multiple of $sqrt{log N}$, thus guaranteeing the existence of a shift with asymptotically minim
al $L^2$ discrepancy, [11]. In the present paper, we construct a specific example of such a shift.
When is the composition of paraproducts bounded? This is an important, and difficult question, related to to a question of Sarason on composition of Hankel matrices, and the two-weight problem for the Hilbert transform. We consider randomized variant
s of this question, finding non-classical characterizations, for dyadic paraproducts.
