2025/12/25 by Viet H. Do, Do, Viet H., Hoi H. Nguyen +7
Mathematics · #Random Matrices and Applications #Stochastic processes and statistical mechanics #Markov Chains and Monte Carlo Methods
paper · doi:10.48550/arxiv.2512.21779
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π = ∑i=1n wi vπ(i), where w=(w1,…,wn) and v=(v1,…,vn) 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 supx P(Sπ=x) is polynomially large. On the continuous side, we study the small-ball event |Sπ-L|≤ δ. 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 supx P(Sπ=x) ≤ 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~\citeSoze1, 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.