反向Littlewood--Offord问题中的双跳跃相变

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

摘要 Abstract

Erdős在1945年猜测,对于$\mathbb{R}^2$中任意单位向量$v_1, \dotsc, v_n$以及独立均匀取值于$\{-1,1\}$的符号$\varepsilon_1, \dotsc, \varepsilon_n$,随机Rademacher和$\sigma = \varepsilon_1 v_1 + \dotsb + \varepsilon_n v_n$满足$\|\sigma\|_2 \leq 1$的概率为$\Omega(1/n)$。虽然该猜想对偶数$n$不成立,但Beck证明了$\|\sigma\|_2 \leq \sqrt{2}$总是成立,且概率为$\Omega(1/n)$。最近,He、Juškevičius、Narayanan和Spiro猜测该猜想对奇数$n$成立。我们通过构造向量$v_1, \dotsc, v_n$证明了$\|\sigma\|_2 \leq 1$发生的概率仅为$O(1/n^{3/2})$,从而否定了这一猜测。另一方面,其近似版本成立:我们证明了对于所有$\delta > 0$,总存在$\Omega_\delta(1/n)$的概率使得$\|\sigma\|_2 \leq 1 + \delta$成立。这表明当$n$为奇数时,$\|\sigma\|_2 \leq r$的最小概率在$r=1$处出现双跳跃相变,因为我们还可以证明$\|\sigma\|_2 \leq 1$发生的概率至少为$\Omega((1/2+\mu)^n)$,其中$\mu > 0$。此外,使用不同的构造方法,我们回答了Beck提出的一个问题以及He、Juškevičius、Narayanan和Spiro提出的另外两个问题,这些问题涉及使$\|\sigma\|_2 \leq \sqrt{2}$的概率最小化的最优构造。我们还对这些问题的高维版本取得了一些进展。

Erd\H{o}s conjectured in 1945 that for any unit vectors $v_1, \dotsc, v_n$ in $\mathbb{R}^2$ and signs $\varepsilon_1, \dotsc, \varepsilon_n$ taken independently and uniformly in $\{-1,1\}$, the random Rademacher sum $\sigma = \varepsilon_1 v_1 + \dotsb + \varepsilon_n v_n$ satisfies $\|\sigma\|_2 \leq 1$ with probability $\Omega(1/n)$. While this conjecture is false for even $n$, Beck has proved that $\|\sigma\|_2 \leq \sqrt{2}$ always holds with probability $\Omega(1/n)$. Recently, He, Ju\v{s}kevi\v{c}ius, Narayanan, and Spiro conjectured that the Erd\H{o}s' conjecture holds when $n$ is odd. We disprove this conjecture by exhibiting vectors $v_1, \dotsc, v_n$ for which $\|\sigma\|_2 \leq 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 $\|\sigma\|_2 \leq 1 + \delta$ with probability $\Omega_\delta(1/n)$, for all $\delta > 0$. This shows that when $n$ is odd, the minimum probability that $\|\sigma\|_2 \leq r$ exhibits a double-jump phase transition at $r = 1$, as we can also show that $\|\sigma\|_2 \leq 1$ occurs with probability at least $\Omega((1/2+\mu)^n)$ for some $\mu > 0$. Additionally, and using a different construction, we give a negative answer to a question of Beck and two other questions of He, Ju\v{s}kevi\v{c}ius, Narayanan, and Spiro, concerning the optimal constructions minimising the probability that $\|\sigma\|_2 \leq \sqrt{2}$. We also make some progress on the higher dimensional versions of these questions.