On the signed small ball inequality

Let $h_R$ denote an $L^infty$ normalized Haar function adapted to a dyadic rectangle $Rsubset [0,1]^d$. We show that for all choices of coefficients $alpha(R) in {pm 1}$, we have the following lower bound on the $L^infty$ norms of the sums of such functions, where the sum is over rectangles of a fixed volume. $$n^{eta(d)} lt sum_{|R| = 2^{-n}} left|left|alpha(R) h_R(x) ight| ight| , ext{for all} eta(d) < frac{d-1}{2} + frac{1}{8d}$$ where the implied constant is independent of $ngeq 1$. The inequality above (without restriction on the coefficients) arises in connection to several areas, such as Probabilities, Approximation, and Discrepancy. With $eta(d) = (d-1)/2$, the inequality above follows from orthogonality, while it is conjectured that the inequality holds with $eta(d) = d/2$. This is known and proved in (Talagrand, 1994) in the case of $d= 2$, and recent papers of the of the authors (Bilyk and Lacey, 2006), (Bilyk et al., 2007) prove that in higher dimensions one can take $eta(d)> (d 1)/2$, without specifying a particular value of $eta$. The restriction $alpha(R) in {pm 1}$ allows us to significantly simplify our prior arguments and to find an explicit value of $eta(d)$.