Abstract
Let ξ be a real random variable with mean zero and variance one and A ={a 1; …; a n } be a multi-set in R d. The random sum
where ξ i are iid copies of ξ is of fundamental importance in probability and its applications.
We discuss the small ball problem, the aim of which is to estimate the maximum probability that S A belongs to a ball with given small radius, following the discovery made by Littlewood-Offord and Erdős almost 70 years ago. We will mainly focus on recent developments that characterize the structure of those sets A where the small ball probability is relatively large. Applications of these results include full solutions or significant progresses of many open problems in different areas.
The first author is supported by research grant DMS-1256802.
The second author is supported by research grants DMS-0901216 and AFOSAR-FA-9550-12-1-0083.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
C. Bordenave and D. Chafai, Around the circular law, Probab. Surveys 9 (2012), 1–89.
J. Bourgain, V. Vu and P. M. Wood, On the singularity probability of discrete random matrices, Journal of Functional Analysis 258 (2010), no.2, 559–603.
A. T. Bharucha-Reid and M. Sambandham, Random polynomials, Academic Press, Orlando, 1986.
K. Costello, T. Tao and V. Vu, Random symmetric matrices are almost surely non-singular, Duke Math. J. 135 (2006), 395–413.
A. Edelman, Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl. 9 (1988), no. 4, 543–560.
P. Erdős, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898–902.
P. Erdős and L. Moser, Elementary Problems and Solutions, Amer. Math. Monthly, 54 (1947), no. 4, 229–230.
C. G. Esséen, On the Kolmogorov-Rogozin inequality for the concentration function, Z. Wahrsch. Verw. Gebiete 5 (1966), 210–216.
P. Frankl and Z. Füredi, Solution of the Littlewood-Offord problem in high dimensions, Ann. of Math. (2) 128 (1988), no. 2, 259–270.
G. Freiman, Foundations of a Structural Theory of Set Addition, Translations of Mathematical Monographs 37, Amer. Math. Soc, Providence, RI, USA, 1973.
O. Friedland and S. Sodin, Bounds on the concentration function in terms of Diophantine approximation, C. R. Math. Acad. Sci. Paris 345 (2007), no. 9, 513–518.
H. Goldstine and J. von Neumann, Numerical inverting of matrices of high order, Bull. Amer. Math. Soc. 53 (1947), 1021–1099.
F. Götze and A. Tikhomirov, The circular law for random matrices, Ann. Probab. 38 (2010), no. 4, 1444–1491.
J. Griggs, The Littlewood-Offord problem: tightest packing and an M-part Sperner theorem, Europ. J. Combin. 1 (1980), 225–234.
D. S. Gunderson, V. Rödl and A. Sidorenko, Extremal problems for sets forming Boolean algebras and complete partite hypergraphs, J. Combin. Theory Ser. A 88 (1999), 342–367.
G. Halász, Estimates for the concentration function of combinatorial number theory and probability, Period. Math. Hungar. 8 (1977), no. 3-4, 197–211.
D. Hilbert, Über die Irreduzibilität ganzer rationaler Funktionen mit ganzzahligen Koeffizienten, J. Reine Angew. Math. 110 (1892), 104–129.
J. Kahn, J. Komlós and E. Szemerédi, On the probability that a random ±1 matrix is singular, J. Amer. Math. Soc. 8 (1995), 223–240.
G. Katona, On a conjecture of Erdős and a stronger form of Sperner’s theorem. Studia Sci. Math. Hungar 1 (1966), 59–63.
D. Kleitman, On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors, Advances in Math. 5 1970 155–157 (1970).
D. Kleitman, Some new results on the Littlewood-Offord problem, J. Combinatorial Theory Ser. A 20 (1976), no. 1, 89–113.
D. Kleitman, On a lemma of Littlewood and Offord on the distribution of certain sums, Math. Z. 90 1965 251–259.
J. Komlós, On the determinant of (0; 1) matrices, Studia Sci. Math. Hungar. 2 (1967), 7–22.
J. Komlós, On the determinant of random matrices, Studia Sci. Math. Hungar. 3 (1968), 387–399.
A. Kolmogorov, Two uniform limit theorems for sums of independent random variables, Theor. Probab. Appl. 1 (1956), 384–394.
A. Kolmogorov, Sur les propriétés des fonctions de concentrations de M. P. Lévy, Ann. Inst. H. Poincaré 16 (1958), 27–34.
J. E. Littlewood and A. C. Offord, On the number of real roots of a random algebraic equation. III. Rec. Math. Mat. Sbornik N.S. 12, (1943). 277–286.
S. Muroga, I. Toda, and S. Takasu, Theory of majority decision elements, J. Franklin Inst., 271, 376–418, 1961.
S. Muroga, Threshold logic and its applications, Wiley-Interscience, New York, 1971.
H. Nguyen, Inverse Littlewood-Offord problems and the singularity of random symmetric matrices, Duke Mathematics Journal Vol. 161, 4 (2012), 545–586.
H. Nguyen, A new approach to an old problem of Erdős and Moser, Journal of Combinatorial Theory, Series A 119 (2012) 977–993.
H. Nguyen and V. Vu, Optimal Littlewood-Offord theorems, Advances in Math., Vol. 226 6 (2011), 5298–5319.
A. Pajor and L. Pastur, On the limiting empirical measure of eigenvalues of the sum of rank one matrices with log-concave distribution, Studia Math. 195 (2009), no. 1, 11–29.
R. A. Proctor, Solution of two difficult combinatorial problems with linear algebra, Amer. Math. Monthly 89 (1982), no. 10, 721–734.
B. A. Rogozin, An estimate for concentration functions, Theor. Probab. Appl. 6 (1961), 94–97.
M. Rudelson, Invertibility of random matrices: Norm of the inverse, Annals of Mathematics, 168 (2008), no. 2, 575–600.
M. Rudelson and R. Vershynin, The Littlewood-Offord Problem and invertibility of random matrices, Advances in Mathematics 218 (2008), 600–633.
M. Rudelson and R. Vershynin, Smallest singular value of a random rectangular matrix, Communications on Pure and Applied Mathematics 62 (2009), 1707–1739.
M. Rudelson and R. Vershynin, Non-asymptotic theory of random matrices: extreme singular values, Proceedings of the International Congress of Mathematicians. Volume III, 1576–1602, Hindustan Book Agency, New Delhi, 2010.
A. Sali, Strong from of an M-part Sperner theorem, European J. Combinatorics 4 (1983), 179–183.
A. Sali, A Sperner type theorem, Order 2 (1985), 13–127.
A. Sárközy and E. Szemerédi, Über ein Problem von Erdős und Moser, Acta Arithmetica 11 (1965), 205–208.
A. A. Sherstov, Communication lower bounds using dual polynomials, Bulletin of the EATCS, 95, 59–93, 2008.
D. A. Spielman and S. H. Teng, Smoothed analysis of algorithms, Proceedings of the International Congress of Mathematicians, Vol. I, 597–606, Higher Ed. Press, Beijing, 2002.
D. A. Spielman and S. H. Teng, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, J. ACM 51 (2004), no. 3, 385–463.
R. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property, SIAM J. Algebraic Discrete Methods 1 (1980), no. 2, 168–184.
E. Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hungar. 20 (1969), 199–245.
T. Tao and V. Vu, On random ±1 matrices: singularity and determinant, Random Structures Algorithms 28 (2006), 1–23.
T. Tao and V. Vu, On the singularity probability of random Bernoulli matrices, Journal of the A. M. S 20 (2007), 603–673.
T. Tao and V. Vu, Random matrices: The Circular Law, Communication in Contemporary Mathematics 10 (2008), 261–307.
T. Tao and V. Vu, From the Littlewood-Offord problem to the circular law: universality of the spectral distribution of random matrices, Bull. Amer. Math. Soc. (N.S.) 46 (2009), no. 3, 377–396.
T. Tao and V. Vu, Inverse Littlewood-Offord theorems and the condition number of random matrices, Annals of Mathematics (2) 169 (2009), no. 2, 595–632.
T. Tao and V. Vu, On the permanent of random Bernoulli matrices, Adv. Math. 220 (2009), 657–669.
T. Tao and V. Vu, A sharp inverse Littlewood-Offord theorem, Random Structures Algorithms 37 (2010), no. 4, 525–539.
T. Tao and V. Vu, Smooth analysis of the condition number and the least singular value, Mathematics of Computation 79 (2010), 2333–2352.
T. Tao and V. Vu, Random matrices: the distribution of the smallest singular values, Geom. Funct. Anal. 20 (2010), no. 1, 260–297.
T. Tao and V. Vu, Random matrices: universality of ESDs and the circular law, Ann. Probab. 38 (2010), no. 5 p. 2023–2065, with an appendix by M. Krishnapur.
T. Tao and V. Vu, The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi, Combinatorica 32 (2012), no. 3, 363–372.
T. Tao and V. Vu, Additive Combinatorics, Cambridge Univ. Press, 2006.
L. G. Valiant, Graph-theoretic arguments in low-level complexity, In Proceedings of the 6th MFCS, Lecture Notes in Computer Science, 53, p. 162–176, New York/Berlin, 1977, Springer-Verlag.
E. Viola, On the power of small depth computation, Foundations and Trends in Theoretical Computer Science, 5(1), 1–72, 2009.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 János Bolyai Mathematical Society and Springer-Verlag
About this chapter
Cite this chapter
Nguyen, H.H., Vu, V.H. (2013). Small Ball Probability, Inverse Theorems, and Applications. In: Lovász, L., Ruzsa, I.Z., Sós, V.T. (eds) Erdős Centennial. Bolyai Society Mathematical Studies, vol 25. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39286-3_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-39286-3_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39285-6
Online ISBN: 978-3-642-39286-3
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)