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

Problem statement
---------------
Let $h(N)$ be the maximum size of a Sidon set in $\{1,\ldots,N\}$. Is it true that, for every $\epsilon>0$,\[h(N) = N^{1/2}+O_\epsilon(N^\epsilon)?\]

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).

Benchmarks / known results (from comments)
----------------------------------------
- It may even be true that $h(N)=N^{1/2}+O(1)$, but Erd\H{o}s remarks this is
  perhaps too optimistic.
- Erd\H{o}s and Tur\'{a}n proved an upper bound of $N^{1/2}+O(N^{1/4})$, with
  an alternative proof by Lindstr\"{o}m.
- Both proofs in fact give\[h(N) \leq N^{1/2}+N^{1/4}+1.\]Balogh, F\"{u}redi,
  and Roy improved the bound in the error term to $0.998N^{1/4}$.
- The current record is\[h(N)\leq N^{1/2}+0.98183N^{1/4}+O(1),\]due to Carter,
  Hunter, and O'Bryant.