The anti-concentration phenomenon with respect to random permutations
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_ | 1866914410839146496 |
|---|---|
| author | Do, Viet H. Nguyen, Hoi H. Phan, Kiet H. Tran, Tuan Vu, Van H. |
| author_facet | Do, Viet H. Nguyen, Hoi H. Phan, Kiet H. Tran, Tuan Vu, Van H. |
| contents | The anti-concentration phenomenon in probability theory has been intensively studied in recent years, with applications across many areas of mathematics. In most existing works, the ambient probability space is a product space generated by independent random variables.
In this paper, we initiate a systematic study of anti-concentration when the ambient space is the symmetric group, equipped with the uniform measure. Concretely, we focus on the random sum $S_π = \sum_{i=1}^{n} w_i\, v_{π(i)}$, where $w=(w_1,\dots,w_n)$ and $v=(v_1,\dots,v_n)$ are fixed vectors and $π$ is a uniformly random permutation. The paper contains several new results, addressing both discrete and continuous anti-concentration phenomena.
On the discrete side, we establish a near-optimal structural characterization of the vectors $w$ and $v$ under the assumption that the concentration probability $\sup_x P(S_π=x)$ is polynomially large. On the continuous side, we study the small-ball event $|S_π-L|\le δ$. Our results exhibit sub-gaussian decay in $L$.
Our results have applications in various areas. First, we use our inverse theorems to derive and strengthen a number of previous anti-concentration bounds. In particular, we show that if both $w$ and $v$ have distinct entries, then $\sup_x P(S_π=x) \le n^{-5/2+o(1)}$. Next, we apply our new results to study random polynomials, and prove that the number of extremal points of random permutation polynomials is bounded by $O(\log n)$, extending results of S{ö}ze~\cite{Soze1, Soze2}. In the final application, we prove that random matrices whose rows are independent random permutations of a fixed non-degenerate vector are nonsingular with high probability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_21779 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The anti-concentration phenomenon with respect to random permutations Do, Viet H. Nguyen, Hoi H. Phan, Kiet H. Tran, Tuan Vu, Van H. Combinatorics Probability The anti-concentration phenomenon in probability theory has been intensively studied in recent years, with applications across many areas of mathematics. In most existing works, the ambient probability space is a product space generated by independent random variables. In this paper, we initiate a systematic study of anti-concentration when the ambient space is the symmetric group, equipped with the uniform measure. Concretely, we focus on the random sum $S_π = \sum_{i=1}^{n} w_i\, v_{π(i)}$, where $w=(w_1,\dots,w_n)$ and $v=(v_1,\dots,v_n)$ are fixed vectors and $π$ is a uniformly random permutation. The paper contains several new results, addressing both discrete and continuous anti-concentration phenomena. On the discrete side, we establish a near-optimal structural characterization of the vectors $w$ and $v$ under the assumption that the concentration probability $\sup_x P(S_π=x)$ is polynomially large. On the continuous side, we study the small-ball event $|S_π-L|\le δ$. Our results exhibit sub-gaussian decay in $L$. Our results have applications in various areas. First, we use our inverse theorems to derive and strengthen a number of previous anti-concentration bounds. In particular, we show that if both $w$ and $v$ have distinct entries, then $\sup_x P(S_π=x) \le n^{-5/2+o(1)}$. Next, we apply our new results to study random polynomials, and prove that the number of extremal points of random permutation polynomials is bounded by $O(\log n)$, extending results of S{ö}ze~\cite{Soze1, Soze2}. In the final application, we prove that random matrices whose rows are independent random permutations of a fixed non-degenerate vector are nonsingular with high probability. |
| title | The anti-concentration phenomenon with respect to random permutations |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2512.21779 |