# 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.

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