Double-jump phase transition for the reverse Littlewood--Offord problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915219364642816 |
|---|---|
| author | Hollom, Lawrence Portier, Julien Souza, Victor |
| author_facet | Hollom, Lawrence Portier, Julien Souza, Victor |
| contents | Erdő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 $σ= \varepsilon_1 v_1 + \dotsb + \varepsilon_n v_n$ satisfies $\|σ\|_2 \leq 1$ with probability $Ω(1/n)$. While this conjecture is false for even $n$, Beck has proved that $\|σ\|_2 \leq \sqrt{2}$ always holds with probability $Ω(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, \dotsc, v_n$ for which $\|σ\|_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 $\|σ\|_2 \leq 1 + δ$ with probability $Ω_δ(1/n)$, for all $δ> 0$. This shows that when $n$ is odd, the minimum probability that $\|σ\|_2 \leq r$ exhibits a double-jump phase transition at $r = 1$, as we can also show that $\|σ\|_2 \leq 1$ occurs with probability at least $Ω((1/2+μ)^n)$ for some $μ> 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 $\|σ\|_2 \leq \sqrt{2}$. We also make some progress on the higher dimensional versions of these questions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_24202 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Double-jump phase transition for the reverse Littlewood--Offord problem Hollom, Lawrence Portier, Julien Souza, Victor Combinatorics Probability Erdő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 $σ= \varepsilon_1 v_1 + \dotsb + \varepsilon_n v_n$ satisfies $\|σ\|_2 \leq 1$ with probability $Ω(1/n)$. While this conjecture is false for even $n$, Beck has proved that $\|σ\|_2 \leq \sqrt{2}$ always holds with probability $Ω(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, \dotsc, v_n$ for which $\|σ\|_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 $\|σ\|_2 \leq 1 + δ$ with probability $Ω_δ(1/n)$, for all $δ> 0$. This shows that when $n$ is odd, the minimum probability that $\|σ\|_2 \leq r$ exhibits a double-jump phase transition at $r = 1$, as we can also show that $\|σ\|_2 \leq 1$ occurs with probability at least $Ω((1/2+μ)^n)$ for some $μ> 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 $\|σ\|_2 \leq \sqrt{2}$. We also make some progress on the higher dimensional versions of these questions. |
| title | Double-jump phase transition for the reverse Littlewood--Offord problem |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2503.24202 |