On the Small Ball Inequality in Three Dimensions

Abstract

We prove an inequality related to questions in Approximation Theory, Probability Theory, and to Irregularities of Distribution. Let $h_R$ denote an $L^{\infty }$ normalized Haar function adapted to a dyadic rectangle $R\subset [0,1{]}^3$. We show that there is a postive $\eta$ so that for all integers $n$, and coefficients $\alpha (R)$ we have 2 ^{-n} \sum_{\abs{R}=2 ^{-n}} \abs{α(R)} {}\lesssim{} n ^{1 - η} \NOrm \sum_{\abs{R}=2 ^{-n}} α(R) h_R >.\infty . This is an improvement over the `trivial' estimate by an amount of $n^{-\eta }$, and the optimal value of $\eta$ (which we do not prove) would be $\eta =\frac{1}{2}$. There is a corresponding lower bound on the $L^{\infty }$ norm of the Discrepancy function of an arbitary distribution of a finite number of points in the unit cube in three dimensions. The prior result, in dimension 3, is that of J{ó}zsef Beck \cite{MR1032337}, in which the improvement over the trivial estimate was logarithmic in $n$. We find several simplifications and extensions of Beck's argument to prove the result above.

30 pages. Final version of the paper. To appear in Duke Math J