Tomaszewski's Problem on Randomly Signed Sums: Breaking the 3/8 Barrier

  • Ravi B. Boppana
  • Ron Holzman
Keywords: Combinatorial probability, Probabilistic inequalities


Let $v_1$, $v_2$, ..., $v_n$ be real numbers whose squares add up to 1.  Consider the $2^n$ signed sums of the form $S = \sum \pm v_i$.  Holzman and Kleitman (1992) proved that at least 3/8 of these sums satisfy $|S| \le 1$.  This 3/8 bound seems to be the best their method can achieve.  Using a different method, we improve the bound to 13/32, thus breaking the 3/8 barrier.

Author Biographies

Ravi B. Boppana, Massachusetts Institute of Technology
Research Affiliate, Mathematics Department
Ron Holzman, Technion - Israel Institute of Technology
Professor, Department of Mathematics
Article Number