Obryant 2004 complete annotated bibliography work related sidon

../

definition_1: O'Bryant's survey notation: a set is a B_h^[g] sequence when every coefficient of the h-th power of its generating series is at most g, so the Sidon sets are the B_2^[2] sets.

definition_3: O'Bryant's survey convention that a B_h[g] sequence is a B_h^[h!g] sequence and a B_h sequence is a B_h[1] sequence, with the warning that many authors use B_h^[h!(g+1)-1] instead.

question_p17: The first open question of the survey's Section 9 asks whether a bounded ordered representation function must vanish infinitely often, which the survey equates with Erdős's USD 500 question on additive bases.

theorem_5: The classical asymptotic sigma_2 = 1 as stated and proved in O'Bryant's survey: the largest Sidon subset of [n] has asymptotically sqrt(n) elements, with the upper bound r < n^{1/2} + n^{1/4} + 1 from the proof.

theorem_6: O'Bryant's survey collects nine bounds on the largest B_2^*[g] subset of the integers modulo n, upper bounds for g = 2, 3, 4 and for even and odd g and lower bounds from the Ruzsa, Bose and Singer constructions and a product rule.

---

Kevin O'Bryant, A Complete Annotated Bibliography of Work Related to Sidon Sequences. Electronic Journal of Combinatorics 11 (2004), Dynamic Survey DS11, DOI 10.37236/32. arXiv:math/0407117.

This is a survey plus annotated bibliography rather than a research paper: it fixes notation for generalized Sidon sequences B_h^[g] via the coefficients of (sum z^a)^h being bounded by g (with B_h[g] meaning B_h^[h!g]), then walks through general constructions (Section 3), state-of-the-art density results for finite and infinite Sidon sets (Sections 4 and 5), structure of maximally thick Sidon sets and their sumsets (Section 6), Sidon subsets of prescribed sets such as squares and fifth powers (Section 7), and two further open questions (Section 9). No new theorems are proved; the value is the curated, cross-referenced map of results with a uniform notation, addressing the well-known search problem that 'Sidon set' and 'B_2 set' name the same object while harmonic analysts use 'Sidon set' for something else. For problem 158 the review notes archived this as the exact literature map that a 2026 computational note had miscited under a different author and title: it locates Stöhr's 1955 strengthening of an unpublished liminf result of Erdős for infinite Sidon sets and accurately summarizes the Kolountzakis and Cilleruelo-Trujillo results on infinite B_2[g] sets.

Source: https://arxiv.org/abs/math/0407117.

Source and version

The copy read for this card is arXiv:math/0407117v1 (8 July 2004), 38 pages, fetched from https://arxiv.org/pdf/math/0407117v1 (525,861 bytes). Its published form is the Electronic Journal of Combinatorics dynamic survey DS11 (submitted May 3, 2004; accepted July 8, 2004; published July 26, 2004), https://doi.org/10.37236/32, 39 pages. The DS11 edition (551,780 bytes) was also read; the comparison and the page mapping below were read from it against the arXiv v1, so that a DS11 locator resolves in the arXiv v1. The arXiv posting predates final acceptance: its title page reads "Accepted pending revision: May 17, 2004" and its running footer "to appear in" the journal. The arXiv record carries no license field, so arXiv's assumed license applies (arXiv:math/0407117), every other right reserved.

The versions differ in three places. DS11 adds two bibliography entries in §10, [122] and [123], so the arXiv entries [122]–[127] are DS11 [124]–[129] and the body's references to them shift with them: the arXiv [124] cited on pp. 10 and 16 is DS11 [126]; the arXiv [125] cited on pp. 4, 6, 7, 10, 12 and 15 and in the captions of Figures 5 and 6 is DS11 [127]; the arXiv [126] in the list on p. 8 is DS11 [128]; and the arXiv [127] cited on p. 17 is DS11 [129]. Entries [1]–[121] carry the same numbers in both. In §4.1, DS11 extends Figure 5 (shortest Sidon sequences, p. 12) from k ≤ 11 to k ≤ 13 and replaces the bounds "≤ 92" and "≤ 123" in Figure 6 (p. 13) with the exact values 86 and 107, crediting a personal communication in both captions; the prose around the two figures is reflowed across pp. 12–13. The title page and running footer differ as described above. Section numbering (§1–10, with §3.1–3.6 and §4.1–4.3) and the labeled statements (Definitions 1–3, Conjecture 4, Theorems 5–6) are the same in both.

Page mapping: the two versions share their page numbers. §1–§9 occupy pp. 1–17 in both, with Definitions 1–3 on p. 3, Conjecture 4 on p. 4, Theorem 5 on p. 10 and Theorem 6 on p. 15; §10 begins on p. 17 in both, and each of the entries [1]–[121] sits on the same pages in both (entry [49] on p. 25, entry [92] beginning on p. 31 with its annotation on p. 32). The versions diverge only at the end of the bibliography: p. 37 holds DS11 [122]–[126] and arXiv [122]–[124], p. 38 the remaining entries, and DS11's last annotation runs onto p. 39. Locators on this card and in its consumers are given by section, label or entry number below [122] and name the same statement in either version; a page number cited from DS11 elsewhere in the corpus resolves to the same page of the arXiv v1.

Bears on.

• #156: the survey states no result on small maximal Sidon sets; it reports, in the annotation of entry [92] (pp. 31–32), the cited author's abstract for a maximal Sidon subset of $[N]$ with $\ll(N\log N)^{1/3}$ elements, without proof. Theorem 5 bounds only the largest Sidon subsets of $[N]$.
• #158: notation and survey only. The problem's sets are the infinite $B_2[2]$ sets of Definition 3; §5 (pp. 15–16) reports Stöhr's strengthening of Erdős's liminf result for Sidon sets and constructions of dense infinite $B_2^*[g]$ sets, none of which decides the problem.
• #864: the Sidon sets of Theorem 5 satisfy the problem's condition, so its lower half gives admissible sets of size $(1+o(1))\sqrt N$, below the conjectured $\frac{2}{\sqrt3}\sqrt N$; its upper half does not apply to the problem's sets. Entry [49] (p. 25) reports quasi-Sidon sets of size $\sim\sqrt{4n/3}$ under a weaker condition. The survey does not mention the problem.
• #28: for subsets of $\mathbb N$ and with the zeros of $\mathcal A^*$ counted at positive integers, the first question of §9 (Question, p. 17) answered yes is the problem's statement; the survey equates it with a USD 500 question of Erdős and records it as open.

Results.

• Definition 1 (p. 3): $B_h^*[g]$ sequences, whose ordered $h$-fold representation counts are at most $g$; Sidon sets are the $B_2^*[2]$ sets, and $\mathcal A^*\le2$ everywhere exactly when $\mathcal A^\circ(k)\le1$ for all $k\ne0$.
• Definition 3 (p. 3): $B_h[g]$ means $B_h^*[h!g]$.
• Theorem 5 (p. 10): the largest Sidon subset of $[n]$ has $\sim\sqrt n$ elements, $\sigma_2=1$.
• Theorem 6 (p. 15): nine known bounds on $C_2(g,n)$, the largest $B_2^*[g]$ set modulo $n$.
• Question (p. 17): must a bounded $\mathcal A^*$ vanish infinitely often.

Further statements surveyed but not given pages: Conjecture 4 (p. 4) on the greedy sequence; the density bounds compiled in §§4–5 (pp. 8–16); and the second question of §9 (p. 17), whether $|\mathcal A+\mathcal A|/|\mathcal A|^2>c$ forces a large $B_2^*[g]$ subset, with $g$ and 'large' depending only on $c$.

Overview

Definition 1 (§2) defines $B_h^*[g]$ by bounding the ordered $h$-fold representation function; thus Sidon sets are $B_2^*[2]$ sets. Definitions 2–3 (§2) fix the extremal notation and related conventions. Sections 3–8 survey constructions, finite and infinite size bounds, distribution, restricted sets, and generalizations; §10 supplies the annotated bibliography.

The principal self-contained result is Theorem 5 (§4.1): "The largest Sidon subset of $[n]$ has $\sim\sqrt n$ elements, i.e., $\sigma_2=1$" (p. 10). Its upper-bound proof counts distinct short differences and compares their minimum possible sum with a telescoping upper bound; its lower-bound proof verifies Ruzsa's construction modulo $p^2-p$. Section 3.1 describes the greedy Sidon sequence and cites Stöhr's bound on its $k$th element. Sections 3.2–3.4 describe modular constructions; Theorem 6 (§4.3) collects bounds for their cyclic-group extremal counterparts. These results concern large Sidon sets. The small maximal-set result relevant to E156 appears only as the cited author's abstract in the annotation of Ruzsa's 1998 paper, entry [92] of §10: a maximal Sidon subset of $[N]$ with $\lesssim(N\log N)^{1/3}$ elements. The survey gives no proof of that claim.

Relation to E156

This source bears on Problem 156.

For E156, write $A\subseteq[N]$ and use the paper's notation $A\in B_2^*[2]$ (Definition 1, §2). A Sidon set $A$ is inclusion-maximal in $[N]$ exactly when every $x\in[N]\setminus A$ satisfies $x+a=b+c$ for some $a,b,c\in A$, or $2x=b+c$ for some $b,c\in A$: either equality is a repeated sum after adjoining $x$. Consequently $[N]\setminus A\subseteq(A+A-A)\cup\{x:2x\in A+A\}$, giving $N-|A|\le |A|^3+|A|(|A|+1)/2$ and the necessary scale $|A|=\Omega(N^{1/3})$. This covering criterion is a direct deduction from Definition 1, not a stated theorem of the survey.

Entry [92] of §10 (Ruzsa, 1998) is the direct lead: its annotation reports a construction at the larger scale $O((N\log N)^{1/3})$, but supplies neither its construction nor a way to remove the logarithm. The greedy construction (§3.1) yields inclusion-maximal initial segments when stopped at $N$; Stöhr's cited cubic bound on its elements gives no $O(N^{1/3})$ upper bound on their cardinality. Theorem 5 (§4.1) bounds the largest Sidon subset of $[N]$ and likewise does not establish the small maximal set sought in E156.

Relation to E864

This source bears on Problem 864.

In E864's notation, $\mathcal A^*(s)=2r_A(s)-\mathbf1_{s/2\in A}$. Thus Theorem 5 applies when every $r_A(s)\le1$, but an E864-admissible set may have one exceptional sum with arbitrarily many representations as $N$ grows; it need not satisfy any fixed $B_2^*[g]$ condition. Theorem 5 therefore gives no $2/\sqrt3$ upper bound for $M(N)$.

If $k=|A|$ and the exceptional sum has $t$ representations, those unordered pairs are disjoint apart from a possible diagonal pair, so $t\le\lceil k/2\rceil$ and $|A+A|=\binom{k+1}{2}-(t-1)$. Consequently an E864 set with $k\to\infty$ is quasi-Sidon in the sense described in entry [49] of §10 (Erdős and Freud, 1991). That entry reports quasi-Sidon sets of size $\sim(2/\sqrt3)\sqrt N$, but its quasi-Sidon condition allows collisions at many sums; the annotation does not establish E864's one-exception construction. The matching lower construction is stated on the E864 page, not proved in this survey.

The difference-counting method of Theorem 5 is a possible starting point for an upper bound. Repeated differences in an E864 set arise from representations of its exceptional sum, and there can be many such repetitions, so the theorem's distinct-difference count cannot simply be reused. The survey provides notation, constructions, and nearby results, but no bound excluding $M(N)>(2/\sqrt3+\varepsilon)\sqrt N$.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.