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

Abstract

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.

Version 3 improves the lower bound from 13/32 = 0.40625 to 0.406259. This version is the same as the journal version, except for formatting. 10 pages

References in corpus (3)

• On a conjecture concerning the sum of independent Rademacher random variables
• On a sum of centered random variables with nonreducing variances
• Linear combinations of Rademacher random variables