A nonuniform Littlewood-Offord inequality for all norms. (English) Zbl 1470.60069
Summary: Let \(\mathbf{v}_i\) be vectors in \(\mathbb{R}^d\) and \(\{ \varepsilon_i \}\) be independent Rademacher random variables. Then the Littlewood-Offord problem entails finding the best upper bound for \(\sup_{\mathbf{x} \in \mathbb{R}^d} \mathbb{P} \left( \sum \varepsilon_i \mathbf{v}_i = \mathbf{x} \right)\). Generalizing the uniform bounds of Littlewood-Offord, Erdős and Kleitman, a recent result of D. Dzindzalieta and T. Juškevičius [Discrete Math. 343, No. 7, Article ID 111891, 4 p. (2020; Zbl 1434.60039)] provides a non-uniform bound that is optimal in its dependence on \(\| \mathbf{x} \|_2\). In this short note, we provide a simple alternative proof of their result. Furthermore, our proof demonstrates that the bound applies to any norm on \(\mathbb{R}^d\), not just the \(\ell_2\) norm. This resolves a conjecture of Dzindzalieta and Juškevičius.
Citations:
Zbl 1434.60039References:
| [1] | Bandeira, A. S.; Ferber, A.; Kwan, M., Resilience for the Littlewood-Offord problem, Adv. Math., 319, 292-312 (2017) · Zbl 1427.60016 |
| [2] | Dzindzalieta, D.; Juškevičius, T., A non-uniform Littlewood-Offord inequality, Discrete Math., 343, 7, Article 111891 pp. (2020), 5 · Zbl 1434.60039 |
| [3] | Erdös, P., On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc., 51, 898-902 (1945) · Zbl 0063.01270 |
| [4] | Erdos, P.; Moser, L., Elementary problems and solutions: Solutions: E736, Amer. Math. Monthly, 54, 4, 229-230 (1947) |
| [5] | Ferber, A.; Jain, V.; Luh, K.; Samotij, W., On the counting problem in inverse Littlewood-Offord theory (2019), arXiv preprint arXiv:1904.10425 |
| [6] | Halász, G., Estimates for the concentration function of combinatorial number theory and probability, Period. Math. Hungar., 8, 3-4, 197-211 (1977) · Zbl 0336.10050 |
| [7] | Kleitman, D. J., On a combinatorial conjecture of Erdős, J. Combin. Theory, 1, 2, 209-214 (1966) · Zbl 0148.01105 |
| [8] | Littlewood, J. E.; Offord, A. C., On the number of real roots of a random algebraic equation III, Rec. Math. [Mat. Sbornik] N.S., 12, 54, 277-286 (1943) · Zbl 0061.01801 |
| [9] | Megginson, R. E., An Introduction to Banach Space Theory, Vol. 183 (2012), Springer Science & Business Media |
| [10] | Milner, E. C., A combinatorial theorem on systems of sets, J. Lond. Math. Soc., 1, 1, 204-206 (1968) · Zbl 0155.02804 |
| [11] | Nguyen, H.; Vu, V., Optimal inverse Littlewood-Offord theorems, Adv. Math., 226, 6, 5298-5319 (2011) · Zbl 1268.11020 |
| [12] | Rudelson, M.; Vershynin, R., The Littlewood-Offord problem and invertibility of random matrices, Adv. Math., 218, 2, 600-633 (2008) · Zbl 1139.15015 |
| [13] | Stanley, R. P., Weyl groups, the hard Lefschetz theorem, and the sperner property, SIAM J. Algebr. Discrete Methods, 1, 2, 168-184 (1980) · Zbl 0502.05004 |
| [14] | Tao, T.; Vu, V. H., Inverse Littlewood-Offord theorems and the condition number of random discrete matrices, Ann. Math. (2), 169, 2, 595-632 (2009) · Zbl 1250.60023 |
| [15] | Tiep, P. H.; Vu, V. H., Non-abelian Littlewood-Offord inequalities, Adv. Math., 302, 1233-1250 (2016) · Zbl 1346.05295 |
| [16] | Tikhomirov, K., Singularity of random Bernoulli matrices, Ann. of Math. (2), 191, 2, 593-634 (2020) · Zbl 1458.15023 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
