Problem 39 — Visual explainer (undergrad)
=========================================

Problem statement
---------------
Is there an infinite Sidon set $A\subset \mathbb{N}$ such that\[\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}\]for all $\epsilon>0$?

Picture
-------
[Given objects + constraints]  --->  [Count / structure]  --->  [Show bound / existence]

Question: what to look at
------------------------
- Restate the problem as: given the constraint, what asymptotic bound or
  structure must follow?
- Use the comments as benchmarks (best known bounds / constructions).

Notation (if it appears above)
-----------------------------
- `\gg` / `>>` means "at least a constant times" (for large parameters).

Benchmarks / known results (from comments)
----------------------------------------
- The trivial greedy construction achieves $\gg N^{1/3}$.
- The first improvement on this was achieved by Ajtai, Koml\'{o}s, and
  Szemer\'{e}di, who found an infinite Sidon set with growth rate $\gg (N\log
  N)^{1/3}$.
- The current best bound of $\gg N^{\sqrt{2}-1+o(1)}$ is due to Ruzsa.
- Erd\H{o}s had offered \$25 for any construction which achieves $N^{c}$ for
  some $c>1/3$.