Home
Resource
Some applications of Freiman's inverse theorem
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(532.00 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Nguyen, Hoi H.. Some applications of Freiman's inverse theorem. Retrieved from https://doi.org/doi:10.7282/T3S46S1V

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

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
Date Created2010
Other Date2010 (degree)
SubjectMathematics, Additive combinatorics, Number theory, Freiman, G. A.
Extentvii, 80 p.
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.
NotePh.D.
NoteIncludes abstract
NoteVita
NoteIncludes bibliographical references
Noteby Hoi H. Nguyen
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T3S46S1V
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.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024