Littlewood-Offord bounds on the symmetric groups and applications

Viet H. Do, Hoi H. Nguyen, Kiet H. Phan, Tuan Tran, Van H. Vu · 2025

Read Littlewood-Offord bounds on the symmetric groups and applications by Viet H. Do, Hoi H. Nguyen, Kiet H. Phan, Tuan Tran, Van H. Vu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-21779.txt.

Introduction

Viet H. Do, Hoi H. Nguyen, Van H. Vu, and their co-authors begin a systematic study of anti-concentration for random permutations. Anti-concentration asks how unlikely a random quantity is to land in a tiny window. Most classical theory assumes the randomness comes from independent variables; a permutation, where every choice constrains the rest, is different.

Their variable is a sum where one fixed vector's entries are permuted against another fixed vector. On the discrete side, they characterize exactly which vector pairs allow the sum to hit a single value with large probability. On the continuous side, they bound the chance the sum falls in a short interval, with sub-gaussian decay. The inverse theorems strengthen earlier anti-concentration bounds. Applications follow: extremal points of random permutation polynomials are few, only logarithmically many in the degree. And permutation-row random matrices are nonsingular with high probability.

Catalog record

CREATORViet H. Do, Hoi H. Nguyen, Kiet H. Phan, Tuan Tran, Van H. Vu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE150 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-21779

Browse the full library · About the Tower of Babel