Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 7

Problem 156

Statement. Does there exist a maximal Sidon set $A\subset \{1,\ldots,N\}$ of size $O(N^{1/3})$ ?

Status. Open.

Source. erdosproblems.com/156, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #156, https://www.erdosproblems.com/156.

References.

[ESS94] Erdős, P. and Sárközy, A. and Sós, T., On Sum Sets of Sidon Sets, I. Journal of Number Theory (1994), 329-347.
[Ru98b] Ruzsa, Imre Z., A small maximal Sidon set. Ramanujan J. (1998), 55-58.

Formalization. Statement in formal-conjectures.

Current assessment

No current assessment is recorded. The status above is imported from the dated site record. This page records no current literature search or independent assessment of proof coverage.

Research

Research guide for Problem 156 collects notes on the published sources and their arguments.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (48)

Additive Bases and Sidon Sets Bennett–Bohman: A note on the random greedy independent set algorithm Carlet: On APN Functions Whose Graphs are Maximal Sidon Sets Huber: Saturated Sidon Sets in Consecutive Intervals: The Eight-Mark Threshold Is 144 O'Bryant: A Complete Annotated Bibliography of Work Related to Sidon Sequences Singer: A theorem in finite projective geometry and some applications to number theory O'Bryant: A Complete Annotated Bibliography of Work Related to Sidon Sequences Bennett–Bohman: A note on the random greedy independent set algorithm Lemma 5.1 (p. 20): a fixed set containing no edge lies in the greedy set at step j with probability (j/N)^L(1+o(1))Theorem 1.1 (p. 3): the random greedy independent set has order at least N(log N/D)^{1/(r-1)}Theorem 1.2 (p. 5): at a fixed step the greedy independent set contains about |G|p^s edges of an admissible hypergraph G Carlet: On APN Functions Whose Graphs are Maximal Sidon Sets Corollary 3.2 (pp. 5-6): the Walsh form of the maximality criterion for APN graphs Corollary 5.1 (p. 8): graphs of plateaued APN functions are maximal Sidon sets Corollary 5.2 (p. 9): Im F + Im F is the whole space for plateaued APN functions with unbalanced components Proposition 3.1 (p. 5): an APN graph is a maximal Sidon set exactly when its triple sums cover the group Proposition 4.1 (p. 7): an APN graph is non-maximal exactly when one changed value keeps the function APN additive_bases/csajbok_2024_complete_3_term_arithmetic_progression_free additive_bases/czerwinski_2023_sidon_sets_sum_free_sets_linear additive_bases/erdos_1994_sum_sets_sidon_sets_i Problem 7 (p. 346): is there a maximal Sidon set in {1,...,n} of size ≪ n^{1/3}Theorem 3 (p. 337): H(n) ≤ 3n^{1/2} for n > n_0 Huber: Saturated Sidon Sets in Consecutive Intervals: The Eight-Mark Threshold Is 144 Lemma 12.1 (p. 9): a saturated witness at a first return contains both endpoints Lemma 2.2 (p. 2): exact criterion for a point to be blocked by a Golomb ruler Proposition 3.1 (p. 3): the ruler {7,47,67,68,70,74,103,119} is saturated in [144]Theorem 1.1 (p. 2): the largest interval length with a saturated eight-element Sidon set is 144 additive_bases/nagy_2022_thin_sidon_sets_nonlinearity_vectorial_boolean additive_bases/obryant_2004_complete_annotated_bibliography_work_related_sidon Definition 1 (p. 3): B_h^*[g] sequences, bounded ordered h-fold representation counts Theorem 5 (p. 10): the largest Sidon subset of [n] has ~ sqrt(n) elements additive_bases/redman_2021_small_maximal_sidon_set_z_2 Theorem 2.3: the set {(x, x^3)} covers every point of Z_2^(2n) outside it Omega(2^n) times Theorem 3.1: Z_2^n has a maximal Sidon set of size O((n 2^n)^(1/3))additive_bases/ruzsa_1998_small_maximal_sidon_set Lemma (p. 56): at least p/8 disjoint solutions of m = b_u + b_v - b_w mod q Theorem (p. 55): a maximal Sidon set in [1,N] with |A| << (N log N)^(1/3)additive_bases/sarkozy_1997_additive_representation_functions Problem 5.3 (p. 141): can a maximal Sidon set in [1, N] be embedded in a much larger B_2[g] set?additive_bases/silva_2005_maximal_sidon_sets_matroids Theorem 3 (p. 6): in a finite B_{2h-1,h-1}-set all maximal B_h-subsets have the same size Theorem 4 (p. 7): the B_h-subsets of a finite B_{2h-1,h-1}-set are the independent sets of a matroid Singer: A theorem in finite projective geometry and some applications to number theory Theorem (pp. 380-381, unnumbered): a perfect difference set of order m + 1 exists when m is a prime power additive_bases/thornburgh_2024_uniform_exclude_distributions_sidon_sets Theorem 1.4 (p. 2): translating local equivalence of the exclude distribution forces a maximal APN graph Theorem 1.5 (p. 2): APN plateaued functions with unbalanced components have uniform exclude distributions Theorem 1.6 (p. 3): the exclude distribution of Gold and Kasami graphs for even n

Graph