Double‐jump phase transition for the reverse Littlewood–Offord problem

Source abstract

Abstract Erdős conjectured in 1945 that for any unit vectors in and signs taken independently and uniformly in , the random Rademacher sum satisfies with probability . While this conjecture is false for even , Beck has proved that always holds with probability . Recently, He, Juškevičius, Narayanan, and Spiro conjectured that the Erdős' conjecture holds when is odd. We disprove this conjecture by exhibiting vectors for which occurs with probability . On the other hand, a relaxed version of their conjecture holds: we show that we always have with probability , for all . This shows that when is odd, the minimum probability that exhibits a double‐jump phase transition at , as we can also show that occurs with probability at least for some . Additionally, and using a different construction, we give a negative answer to a question of Beck and two other questions of He, Juškevičius, Narayanan, and Spiro, concerning the optimal constructions minimising the probability that . We also make some progress on the higher dimensional versions of these questions.