#156: a 28-year-old log factor, and exactly why nobody's shaved it off
The target (erdosproblems.com/156, [ESS94]). A Sidon set has no repeated pairwise sums. A greedy Sidon set in {1,...,N}, extended until nothing more can be added, is automatically maximal and has size ≫N^(1/3) — cheap. The question asks whether a maximal Sidon set can be built as small as O(N^(1/3)). Ruzsa (1998) got O((N log N)^(1/3)) — one log factor above the target, unimproved in the literature since. HONEST DECLINE, but a genuinely useful one: literature search confirmed the record hasn't moved, and reconstructing Ruzsa's method (it isn't freely available in full) from first principles and its known descendants pins down exactly why the log is there.
Where the log actually comes from. Ruzsa's construction: embed a dense Singer-difference-set Sidon set into a small ambient group of size M, then randomly lift it into {1,...,N}. Average-degree counting alone only needs M≫N^(2/3) — that would give the target O(N^(1/3)). But guaranteeing every one of the ~N points gets covered (not just almost all of them) needs a union bound over N events, and that union bound is exactly what forces M up by a factor of log N — coupon-collector, not Sidon combinatorics. Ruzsa's (N log N)^(1/3) falls out of balancing √M + N/M with that M. Nobody has shown the log is necessary — only that this specific covering method needs it.
The real find: a verified sibling result the tracker doesn't mention. Redman, Rose, and Walker (arXiv:2109.00292, SIAM J. Discrete Math. 2022) prove the exact group-theoretic analogue in Z₂ⁿ: a maximal Sidon set of size O((n·2ⁿ)^(1/3)) — same "log-like" factor (n = log|G|), same construction template, explicitly adapted from Ruzsa's method. We verified the citation directly: real paper, real authors, matches the claimed bound exactly. They also note that Bennett–Bohman random-greedy analysis of the analogous covering process predicts this factor is tight in the group setting — suggestive, not a proof, but it's the first piece of evidence either direction on whether Ruzsa's log is real or just an artifact of one particular argument.
What's still open. Whether the log factor is a genuine barrier or an artifact of the union-bound method remains unknown for both the integer and group versions. No stronger lower bound than the trivial Ω(N^(1/3)) exists for any maximal Sidon set; no O(N^(1/3)) construction exists either. 28 years, one log factor, still standing.