Problem #198: If $A\subset \mathbb{N}$ is a Sidon set then must the...

---

Progress

The answer is no; Erdős and Graham report this was proved by Baumgartner, presumably referring to the paper [Ba75], which does not state this exactly, but the following simple construction is implicit in [Ba75].

Let $P_1,P_2,\ldots$ be an enumeration of all countably many infinite arithmetic progressions. We choose $a_1$ to be the minimal element of $P_1\cap \mathbb{N}$, and in general choose $a_n$ to be an element of $P_n\cap \mathbb{N}$ such that $a_n>2a_{n-1}$. By construction $A=\{a_1<a_2<\cdots\}$ contains at least one element from every infinite arithmetic progression, and is a lacunary set, so is certainly Sidon.

AlphaProof has found the following explicit construction:\[A = \{ (n+1)!+n : n\geq 0\}.\]This is a Sidon set, and intersects every arithmetic progression, since for any $a,d\in \mathbb{N}$,\[(a+d+1)!+(a+d)\in A,\]and $d$ divides $(a+d+1)!+d$.

See also [199].

This problem has been formalised in Lean as part of the Google DeepMind Formal Conjectures project.