RUcore Resource Object
RUcore Resource Object
PDF-1(532.00 KB)
TitleSome applications of Freiman's inverse theorem
NameNguyen, Hoi H. (author), Vu, Van (chair), Kahn, Jeff (internal member), Szemeredi, Endre (internal member), Pemantle, Robin (outside member), Rutgers University, Graduate School - New Brunswick,
Degree Date2010
Date Created2010
SubjectMathematics,
Additive combinatorics,
Number theory,
Freiman, G. A.
DescriptionThe celebrated Freiman's inverse theorem in Additive Combinatorics asserts that an additive set of small doubling constant must have additive structure. This thesis contains two applications achieved by combining this theorem with a dyadic pigeonhole principle technique. 1. A finite set A of integers is square-sum-free if no subset of A sums up to a square. In 1986, Erdos posed the problem of determining the largest cardinality of a square-sum-free subset of {1,..., n}. Significantly improving earlier results, we show in Chapter 2 that this maximum cardinality is of order n^{1/3+o(1)}, which is asymptotically tight. 2. A classical result of Littlewood-Offord and Erdos from the 1940s asserts that if the v_i are non-zero, then the concentration probability of the (multi)set V={v_1,...,v_n},
ho(V) := sup_{x} P( v_1 eta_1+ ... + v_n eta_n=x), is of order O(n^{-1/2}), where eta_i are i.i.d. copies of a Bernoulli random variable. Motivated by problems concerning random matrices, Tao and Vu introduced the Inverse Littlewood-Offord problem. In the inverse problem, one would like to give a characterization of the set V, given that ho(V) is relatively large. In Chapter 3, we develop a method to attack the inverse problem. As an application, we strengthen several previous results of Tao and Vu, obtaining an almost optimal characterization for $V$. This implies several classical theorems, such as those of Sarkozy-Szemeredi, Halasz, and Stanley.
ho(V) := sup_{x} P( v_1 eta_1+ ... + v_n eta_n=x), is of order O(n^{-1/2}), where eta_i are i.i.d. copies of a Bernoulli random variable. Motivated by problems concerning random matrices, Tao and Vu introduced the Inverse Littlewood-Offord problem. In the inverse problem, one would like to give a characterization of the set V, given that ho(V) is relatively large. In Chapter 3, we develop a method to attack the inverse problem. As an application, we strengthen several previous results of Tao and Vu, obtaining an almost optimal characterization for $V$. This implies several classical theorems, such as those of Sarkozy-Szemeredi, Halasz, and Stanley.
NotePh.D.
NoteIncludes abstract
NoteVita
NoteIncludes bibliographical references
Noteby Hoi H. Nguyen
Genretheses
Persistent URLhttp://hdl.rutgers.edu/1782.2/rucore10001600001.ETD.000053124
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.