Double-jump phase transition for the reverse Littlewood--Offord problem

Abstract

Erdős conjectured in 1945 that for any unit vectors $v_1,\dots ,v_n$ in ${\mathbb{R}}^2$ and signs ${\epsilon }_1,\dots ,{\epsilon }_n$ taken independently and uniformly in $\{-1,1\}$, the random Rademacher sum $\ddot{I}ƒ={\epsilon }_1{v}_1+\cdots +{\epsilon }_n{v}_n$ satisfies $\Vert \ddot{I}ƒ{\Vert }_2\le 1$ with probability $\hat{I}\text{c◯}(1/n)$. While this conjecture is false for even $n$, Beck has proved that $\Vert \ddot{I}ƒ{\Vert }_2\le \sqrt{2}$ always holds with probability $\hat{I}\text{c◯}(1/n)$. Recently, He, JuÅ¡kevičius, Narayanan, and Spiro conjectured that the Erdős' conjecture holds when $n$ is odd. We disprove this conjecture by exhibiting vectors $v_1,\dots ,v_n$ for which $\Vert \ddot{I}ƒ{\Vert }_2\le 1$ occurs with probability $O(1/n^{3/2})$. On the other hand, an approximated version of their conjecture holds: we show that we always have $\Vert \ddot{I}ƒ{\Vert }_2\le 1+\hat{I}´$ with probability $\hat{I}{\text{c◯}}_{\hat{I}}´(1/n)$, for all $\hat{I}´>0$. This shows that when $n$ is odd, the minimum probability that $\Vert \ddot{I}ƒ{\Vert }_2\le r$ exhibits a double-jump phase transition at $r=1$, as we can also show that $\Vert \ddot{I}ƒ{\Vert }_2\le 1$ occurs with probability at least $\hat{I}\text{c◯}((1/2+\hat{I}¼{)}^n)$ for some $\hat{I}¼>0$. 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 $\Vert \ddot{I}ƒ{\Vert }_2\le \sqrt{2}$. We also make some progress on the higher dimensional versions of these questions.