Results on Sidon and Bh Sequences Open Access

Lee, Sangjune (2012)

Permanent URL: https://etd.library.emory.edu/concern/etds/2227mq519?locale=en
Published

Abstract

A set A of non-negative integers is a Sidon set if all the sums a1 + a2, with a1 ≤ a2 and a1, a2 ∈ A, are distinct. In this dissertation, we deal with results on the number of Sidon sets in [n] = {0,1, ··· ,n - 1} and the maximum size of Sidon sets in sparse random subsets of [n] or N (the set of natural numbers). We also consider a natural generalization of Sidon sets called Bh-sets with h ≥ 2. A set A of non-negative integers is called a Bh-set if all the sums a1 + a2 + ··· + ah, with a1 ≤ a2 ≤ ··· ≤ ah and ai ∈ A, are distinct.

The first question in this dissertation was suggested by Cameron-Erdős in 1990. They proposed the problem of estimating the number of Sidon sets contained in [n]. We obtain an upper bound 2c√n on the number of Sidon sets which is sharp up to a constant factor in the exponent when compared to the previous lower bound 2(1+o(1))√n.

Next, we investigate the maximum size of Sidon sets contained in sparse random sets R ⊂ [n]. Let R = [n]m be a uniformly chosen, random m- element subset of [n]. Let F([n]m) = max{|S|: S ⊂ [n]m is Sidon}. Fix a constant 0 ≤ a ≤ 1 and suppose m=(1+o(1))na. We show that there is a constant b = b(a) for which
F ([n]m) = nb+o(1) (1)
almost surely and we obtain what b = b(a) is. Surprisingly, between two points a = 1/3 and a = 2/3, the function b = b(a) is constant.

Next, we deal with infinite Sidon sets in sparse random subsets of N. Fix 0 < δ ≤ 1,and let R=Rδ be the set obtained by choosing each element i ⊂ N independently with probability i-1+δ. We show that for every 0 < δ ≤ 2/3 there exists a constant c = c(δ) such that a random set R satisfies the following with probability 1:

  • Every Sidon set SR satisfies that |S ∩ [n]| ≤ nc+o(1) for every sufficiently large n.
  • There exists a large Sidon set S ⊂ R such that |S ∩ [n]| ≥ nc+o(1) for every sufficiently large n.

Table of Contents

Contents
1 Introduction 1
2 Finite Sidon sets 5
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 A problem of Cameron and Erd}os . . . . . . . . . . . . . 6
2.1.2 Probabilistic results . . . . . . . . . . . . . . . . . . . . . 7
2.2 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1 Statement of the main results . . . . . . . . . . . . . . . 8
2.2.2 The uniform model and the binomial model . . . . . . . 11
2.2.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 The number of Sidon sets . . . . . . . . . . . . . . . . . . . . . 13
2.3.1 Independent sets in dense graphs . . . . . . . . . . . . . 13
2.3.2 Proof of Theorem 2.2.1 . . . . . . . . . . . . . . . . . . . 15
2.3.3 Proof of Theorem 2.2.2 . . . . . . . . . . . . . . . . . . . 19
2.4 The upper bounds in Theorems 2.2.5{2.2.7 . . . . . . . . . . . . 21
2.4.1 Proof of the upper bound in Theorem 2.2.5 . . . . . . . . 21
2.4.2 Proof of the upper bound in Theorem 2.2.6 . . . . . . . . 23
2.4.3 Proof of the upper bounds in Theorem 2.2.7 . . . . . . . 24
2.5 Nontrivial solutions in random sets . . . . . . . . . . . . . . . . 26
2.5.1 Estimating the number of nontrivial solutions . . . . . . 26
2.5.2 The Kim{Vu polynomial concentration result . . . . . . 27
2.5.3 Proof of Lemma 2.5.3 . . . . . . . . . . . . . . . . . . . . 28
2.6 Proof of Theorem 2.2.3 . . . . . . . . . . . . . . . . . . . . . . . 33
2.6.1 Theorem 2.2.3 for smaller p = p(n) . . . . . . . . . . . . 33
2.6.2 Theorem 2.2.3 for larger p = p(n) . . . . . . . . . . . . . 33
2.7 The lower bounds in Theorems 2.2.5{2.2.7 . . . . . . . . . . . . 34
2.7.1 Proofs of the lower bounds in Theorems 2.2.5 and 2.2.6 34
2.7.2 Proof of the lower bound in Theorem 2.2.7 . . . . . . . . 35
2.7.3 Proof of Lemma 2.7.2 . . . . . . . . . . . . . . . . . . . . 37
3 Finite Bh-sets 41
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.1.1 A generalization of a problem of Cameron and Erd}os . . 42
3.1.2 Probabilistic results . . . . . . . . . . . . . . . . . . . . . 43
3.2 Rened results . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2.1 A renement of Theorem 3.1.1 . . . . . . . . . . . . . . . 45
3.2.2 A renement of Theorem 3.1.4 . . . . . . . . . . . . . . . 46
3.3 Proof of Theorem 3.2.1 . . . . . . . . . . . . . . . . . . . . . . . 49
3.3.1 Proof of Lemma 3.3.2 . . . . . . . . . . . . . . . . . . . . 57
3.3.2 Proof of Lemma 3.3.4 . . . . . . . . . . . . . . . . . . . . 59
3.3.3 Proof of Corollary 3.3.10 . . . . . . . . . . . . . . . . . . 60
3.3.4 Proof of Lemma 3.3.12 . . . . . . . . . . . . . . . . . . . 62
3.4 Lower bounds of Theorem 3.1.4 . . . . . . . . . . . . . . . . . . 69
4 Innite Sidon sets 73
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.2 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.3 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.3.1 Sidon quadruples . . . . . . . . . . . . . . . . . . . . . . 77
4.3.2 A maximum Sidon subset of a random set in [n]. . . . . 77
4.3.3 Borel{Cantelli lemma . . . . . . . . . . . . . . . . . . . . 78
4.3.4 The size of a random set R in an interval . . . . . . . . . 79
4.3.5 The Kim{Vu polynomial concentration result . . . . . . 81
4.4 Proof of Lemma 4.2.1 . . . . . . . . . . . . . . . . . . . . . . . . 82
4.5 Proof of Lemma 4.2.2 (a) and (b) . . . . . . . . . . . . . . . . . 86
4.5.1 Proof of Lemma 4.2.2 (a) and (b) . . . . . . . . . . . . . 86
4.5.2 Proof of Lemma 4.5.4 . . . . . . . . . . . . . . . . . . . . 91
4.5.3 Proof of Claim 4.5.6 . . . . . . . . . . . . . . . . . . . . 94
Bibliography 103

About this Dissertation

Rights statement
  • Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
School
Department
Degree
Submission
Language
  • English
Research field
Keyword
Committee Chair / Thesis Advisor
Committee Members
Last modified

Primary PDF

Supplemental Files