A GENERALIZED FAULHABER INEQUALITY, IMPROVED BRACKETING COVERS, AND APPLICATIONS TO DISCREPANCY

Abstract

We prove a generalized Faulhaber inequality to bound the sums of the j-th powers of the first n (possibly shifted) natural numbers. With the help of this inequality we are able to improve the known bounds for bracketing numbers of d-dimensional axis-parallel boxes anchored in 0 (or, put differently, of lower left orthants intersected with the d-dimensional unit cube [0, 1](d)). We use these improved bracketing numbers to establish new bounds for the star-discrepancy of negatively dependent random point sets and its expectation. We apply our findings also to the weighted star-discrepancy.