Götze F., Zaitsev A. Yu. Improved applications of Arak's inequalities to the Littlewood–Offord problem

F. Götze   ; A. Yu. Zaitsev

Zapiski Nauchnykh Seminarov POMI, Probability and statistics. Part 36, Tome 535 (2024), pp. 70-91

Résumé

Let $X_1,\ldots,X_n$ be independent identically distributed random variables. In this paper we study the behavior of concentration functions of weighted sums $\sum\limits_{k=1}^{n}X_ka_k $ with respect to the arithmetic structure of coefficients $a_k$ in the context of the Littlewood–Offord problem. We discuss the relations between the inverse principles proposed by Nguyen, Tao and Vu and similar principles formulated by Arak in his papers from the 1980's. We state some improved (more general and more precise) consequences of Arak's inequalities applying our recent bound in the Littlewood–Offord problem. Moreover, we also obtain an improvement of the estimates used in Rudelson and Vershynin's least common denominator method. \vskip.0cm

Bibliographie

[1] T. V. Arak, “O sblizhenii $n$-kratnykh svertok raspredelenii, imeyuschikh neotritsatelnuyu kharakteristicheskuyu funktsiyu, s soprovozhdayuschimi zakonami”, Teoriya veroyatn. i ee primen., 25:2 (1980), 225–246 | MR | Zbl

[2] T. V. Arak, “On the convergence rate in Kolmogorov's uniform limit theorem. I”, Teoriya veroyatn. i ee primen., 26:2 (1981), 225–245 | MR | Zbl

[3] T. V. Arak, A. Yu. Zaitsev, “Ravnomernye predelnye teoremy dlya summ nezavisimykh sluchainykh velichin”, Tr. MIAN SSSR, 174, 1986 | MR | Zbl

[4] M. Campos, M. Jenssen, M. Michelen, J. Sahasrabudhe, “The singularity probability of a random symmetric matrix is exponentially small”, J. Amer. Math. Soc., 2024 (Published electronically: January 19, 2024) | MR

[5] M. Campos, M. Jenssen, M. Michelen, J. Sahasrabudhe, “The least singular value of a random symmetric matrix”, Forum of Mathematics, Pi, Cambridge University Press, 2024 (Published online by 23 January, 2024) | MR

[6] Yu. S. Eliseeva, “Mnogomernye otsenki funktsii kontsentratsii vzveshennykh summ nezavisimykh odinakovo raspredelennykh sluchainykh velichin”, Zap. nauchn. semin. POMI, 412, 2013, 121–137

[7] Yu. S. Eliseeva, A. Yu. Zaitsev, “Otsenki funktsii kontsentratsii vzveshennykh summ nezavisimykh odinakovo raspredelennykh sluchainykh velichin”, Teoriya veroyatn. i ee primen., 57:4 (2012), 768–777 | DOI | MR

[8] Yu. S. Eliseeva, F. Gëttse, A. Yu. Zaitsev, “Otsenki funktsii kontsentratsii v probleme Littlvuda–Offorda”, Zap. nauchn. semin. POMI, 420, 2013, 50–69

[9] P. Erdös, “On a lemma of Littlewood and Offord”, Bull. Amer. Math. Soc., 51:12 (1945), 898–902 | DOI | MR | Zbl

[10] C.-G. Esséen, “On the Kolmogorov–Rogozin inequality for the concentration function”, Z. Wahrscheinlichkeitstheorie Verw. Geb., 5 (1966), 210–216 | DOI | MR | Zbl

[11] C.-G. Esséen, “On the concentration function of a sum of independent random variables”, Z. Wahrscheinlichkeitstheorie Verw. Geb., 9 (1968), 290–308 | DOI | MR | Zbl

[12] O. Friedland, S. Sodin, “Bounds on the concentration function in terms of Diophantine approximation”, C. R. Math. Acad. Sci. Paris, 345 (2007), 513–518 | DOI | MR | Zbl

[13] F. Gëttse, Yu. S. Eliseeva, A. Yu. Zaitsev, “Neravenstva Araka dlya funktsii kontsentratsii i problema Littlvuda–Offorda”, Teoriya veroyatn. i ee primen., 62:2 (2017), 241–266 | DOI

[14] F. Götze, A. Yu. Zaitsev, “New applications of Arak's inequalities to the Littlewood–Offord problem”, Eur. J. Math., 4:2 (2018), 639–663 | DOI | MR | Zbl

[15] F. Götze, A. Yu. Zaitsev, “A new bound in the Littlewood–Offord problem”, Mathematics, 10:10 (2022), 1740 | DOI | MR

[16] B. Green, Notes on progressions and convex geometry, Preprint, 2005

[17] V. Khengartner, R. Teodoresku, Funktsii kontsentratsii, Nauka, M., 1980 | MR

[18] A. N. Kolmogorov, “Dve ravnomernye predelnye teoremy dlya summ nezavisimykh slagaemykh”, Teoriya veroyatn. i ee primen., 1:4 (1956), 384–394

[19] G. V. Livshyts, K. Tikhomirov, R. Vershynin, “The smallest singular value of inhomogeneous square random matrices”, Ann. Probab., 49 (2021), 1286–1309 | DOI | MR | Zbl

[20] J. E. Littlewood, A. C. Offord, “On the number of real roots of a random algebraic equation (III)”, Matem. sb., 12(54):3 (1943), 277–286 | MR | Zbl

[21] Hoi Nguyen, Van Vu, “Optimal inverse Littlewood–Offord theorems”, Adv. Math., 226:6 (2011), 5298–5319 | DOI | MR | Zbl

[22] Hoi Nguyen, Van Vu, “Small ball probabilities, inverse theorems and applications”, Erdös Centennial Proceeding, eds. Lovász L., et. al., Springer, 2013, 409–463 | MR | Zbl

[23] V. V. Petrov, Predelnye teoremy dlya summ nezavisimykh sluchainykh velichin, Nauka, M., 1987

[24] M. Rudelson, R. Vershynin, “The Littlewood–Offord problem and invertibility of random matrices”, Adv. Math., 218 (2008), 600–633 | DOI | MR | Zbl

[25] M. Rudelson, R. Vershynin, “The smallest singular value of a random rectangular matrix”, Comm. Pure Appl. Math., 62 (2009), 1707–1739 | DOI | MR | Zbl

[26] T. Tao, Van Vu, Additive Combinatorics, Cambridge Univ. Press, 2006 | MR | Zbl

[27] T. Tao, Van Vu, “John-type theorems for generalized arithmetic progressions and iterated sumsets”, Adv. Math., 219:2 (2008), 428–449 | DOI | MR | Zbl

[28] T. Tao, Van Vu, “Inverse Littlewood–Offord theorems and the condition number of random discrete matrices”, Ann. Math. (2), 169:2 (2009), 595–632 | DOI | MR | Zbl

[29] T. Tao, Van Vu, “From the Littlewood–Offord problem to the circular law: universality of the spectral distribution of random matrices”, Bull. Amer. Math. Soc., 46 (2009), 377–396 | DOI | MR | Zbl

[30] T. Tao, Van Vu, “A sharp inverse Littlewood–Offord theorem”, Random Structures Algorithms, 37:4 (2010), 525–539 | DOI | MR | Zbl

[31] K. Tikhomirov, “Singularity of random Bernoulli matrices”, Ann. Math. (2), 191:2 (2020), 593–634 | DOI | MR | Zbl

[32] R. Vershynin, “Invertibility of symmetric random matrices”, Random Structures Algorithms, 44 (2014), 135–182 | DOI | MR | Zbl

[33] A. Yu. Zaitsev, “Neravenstva Araka dlya obobschennykh arifmeticheskikh progressii”, Zap. nauchn. semin. POMI, 454, 2016, 151–157