On the Small Ball Inequality in all dimensions

Let h_R denote an L^∞ normalized Haar function adapted to a dyadic rectangle R ⊂ [0, 1]^d. We show that for choices of coefficients α (R), we have the following lower bound on the L^∞ norms of the sums of such functions, where the sum is over rectangles of a fixed volume:n^{frac(d - 1, 2) - η} {norm of matrix} under(∑, | R | = 2^{- n}) α (R) h_R (x) {norm of matrix}_{L∞ ([0, 1]d)} ≳ 2^{- n} under(∑, | R | = 2^{- n}) | α (R) |, for some 0 < η < frac(1, 2) . The point of interest is the dependence upon the logarithm of the volume of the rectangles. With n^{(d - 1) / 2} on the left above, the inequality is trivial, while it is conjectured that the inequality holds with n^{(d - 2) / 2}. This is known in the case of d = 2 [Michel Talagrand, The small ball problem for the Brownian sheet, Ann. Probab. 22 (3) (1994) 1331-1354, MR 95k:60049], and a recent paper of two of the authors [Dmitriy Bilyk, Michael T. Lacey, On the Small Ball Inequality in three dimensions, Duke Math. J., (2006), in press, arXiv: math.CA/0609815] proves a partial result towards the conjecture in three dimensions. In this paper, we show that the argument of [Dmitriy Bilyk, Michael T. Lacey, On the Small Ball Inequality in three dimensions, Duke Math. J., (2006), in press, arXiv: math.CA/0609815] can be extended to arbitrary dimension. We also prove related results in the subjects of the irregularity of distribution, and approximation theory. The authors are unaware of any prior results on these questions in any dimension d ≥ 4.