Results on Sidon and Bh Sequences Open Access
Lee, Sangjune (2012)
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 S ⊂ R 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
| School | |
|---|---|
| Department | |
| Degree | |
| Submission | |
| Language |
|
| Research Field | |
| Keyword | |
| Committee Chair / Thesis Advisor | |
| Committee Members |
Primary PDF
| Thumbnail | Title | Date Uploaded | Actions |
|---|---|---|---|
|
|
Results on Sidon and Bh Sequences () | 2018-08-28 16:26:27 -0400 |
|
Supplemental Files
| Thumbnail | Title | Date Uploaded | Actions |
|---|