Littlewood-offord bounds on the symmetric groups and applications

Thời gian: 9h sáng Thứ 5, ngày  26/03/2026
Địa điểm: Phòng 507 nhà A6
Link online Zoom:  https://us06web.zoom.us/j/89134062450?pwd=io7luDnBIrkYTZLXvCuwAKdJPokluC.1

Meeting ID:   891 3406 2450
Passcode: 123456

Tóm tắt: We study the anti-concentration of the random sum $ S_{\pi} = \sum_{i=1}^{n} v_i w_{\pi(i)}$, where $ \pi $ is a uniformly random permutation. We establish a near-optimal characterization of the vectors $ v = (v_1, \dots, v_n)$ and $w = (w_1, \dots, w_n)$ under the condition that $ \sup_{x} P(S_{\pi} = x) \ge n^{-C}$. Among other things, our result shows that when the entries $ v_i $ and $ w_i$ are all distinct, we have $\sup_{x} P(S_{\pi} = x) \le n^{-5/2+o(1)} $, addressing a question posed by Alon--Pohoata--Zhu. We also provide quantitative probability bounds for the events $ |S_{\pi} - L| \le r$ and their joint distributions for various choices of $v_i$  and $w_i$, with particular attention to the dependence on both $ r $ and $L$, which is shown to be optimal. As an application, we prove that the number of (fixed-order) real critical points of random polynomials $ P_{\pi}(x) = \sum_i w_{\pi(i)} x^i $ is of order $O(\log n) $ under some natural conditions on $w_{i}$. This significantly extends a result of Soze from real roots to critical points. In joint work with Hoi Nguyen, Kiet Phan, Tuan Tran and Van Vu.