A sharp inverse Littlewood-Offord theorem

Abstract

Random Structures & AlgorithmsVolume 37, Issue 4 p. 525-539 A sharp inverse Littlewood-Offord theorem Terence Tao, Terence Tao [email protected] Department of Mathematics, University of California, Los Angeles (UCLA), Los Angeles, California 90095-1555Search for more papers by this authorVan Vu, Corresponding Author Van Vu [email protected] Department of Mathematics, Rutgers University, Piscataway, New Jersey 08854Department of Mathematics, Rutgers University, Piscataway, New Jersey 08854Search for more papers by this author Terence Tao, Terence Tao [email protected] Department of Mathematics, University of California, Los Angeles (UCLA), Los Angeles, California 90095-1555Search for more papers by this authorVan Vu, Corresponding Author Van Vu [email protected] Department of Mathematics, Rutgers University, Piscataway, New Jersey 08854Department of Mathematics, Rutgers University, Piscataway, New Jersey 08854Search for more papers by this author First published: 25 October 2010 https://doi.org/10.1002/rsa.20327Citations: 26AboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Abstract Let ηi,i = 1,…,n be iid Bernoulli random variables. Given a multiset vof n numbers v1,…,vn, the concentration probability P1(v) of v is defined as P1(v) := supxP(v1η1+ …vnηn = x). A classical result of Littlewood–Offord and Erdős from the 1940s asserts that if the vi are nonzero, then this probability is at most O(n-1/2). Since then, many researchers obtained better bounds by assuming various restrictions on v. In this article, we give an asymptotically optimal characterization for all multisets v having large concentration probability. This allow us to strengthen or recover several previous results in a straightforward manner. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010 Citing Literature Volume37, Issue4December 2010Pages 525-539 RelatedInformation

Locations

• Random Structures and Algorithms - View
• arXiv (Cornell University) - View - PDF
• arXiv (Cornell University) - PDF
• Random Structures and Algorithms - View
• arXiv (Cornell University) - View - PDF
• arXiv (Cornell University) - PDF
• Random Structures and Algorithms - View
• arXiv (Cornell University) - View - PDF
• arXiv (Cornell University) - PDF