Erdős Problem 154

References:

• erdosproblems.com/154
• [Li98] Lindström, Bernt, Well distribution of Sidon sets in residue classes. J. Number Theory (1998), 197-200.
• [Ko99] Kolountzakis, Mihail N., On the uniform distribution in residue classes of dense sets of integers with distinct sums. J. Number Theory (1999), 147-153.
• [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.

theorem Erdos154.erdos_154 : True ↔ ∀ (m : ℕ), 2 ≤ m → ∀ (N : ℕ → ℕ) (A : ℕ → Finset ℕ), Filter.Tendsto (fun (k : ℕ) => ↑(N k)) Filter.atTop Filter.atTop → (∀ (k x : ℕ), x ∈ A k → x ≤ N k) → (∀ (k : ℕ), IsSidon ↑(A k)) → Filter.Tendsto (fun (k : ℕ) => ↑(A k).card / √↑(N k)) Filter.atTop (nhds 1) → ∀ i < m, Filter.Tendsto (fun (k : ℕ) => ↑{s ∈ A k + A k | s % m = i}.card / ↑(A k + A k).card) Filter.atTop (nhds (1 / ↑m))

Let $A\subset \{1,\ldots,N\}$ be a Sidon set with $\lvert A\rvert\sim N^{1/2}$. Must $A+A$ be well-distributed over all small moduli? In particular, must about half the elements of $A+A$ be even and half odd?

The answer is yes. Lindström [Li98] proved the analogous statement for $A$ itself (see erdos_154.variants.lindstrom), later strengthened by Kolountzakis [Ko99]; well-distribution of $A+A$ then follows using the Sidon property.

We state the question for the sumset: for any sequence of Sidon sets $A_k\subseteq\{0,\ldots,N_k\}$ with $N_k\to\infty$ and $\lvert A_k\rvert\sim N_k^{1/2}$, and any modulus $m\geq 2$, the proportion of elements of $A_k+A_k$ congruent to $i\pmod m$ (i.e. the count divided by $\lvert A_k+A_k\rvert$) tends to $1/m$ for every residue $i<m$.

theorem Erdos154.erdos_154.variants.lindstrom (m : ℕ) (hm : 2 ≤ m) (N : ℕ → ℕ) (A : ℕ → Finset ℕ) : Filter.Tendsto (fun (k : ℕ) => ↑(N k)) Filter.atTop Filter.atTop → (∀ (k x : ℕ), x ∈ A k → x ≤ N k) → (∀ (k : ℕ), IsSidon ↑(A k)) → Filter.Tendsto (fun (k : ℕ) => ↑(A k).card / √↑(N k)) Filter.atTop (nhds 1) → ∀ i < m, Filter.Tendsto (fun (k : ℕ) => ↑{a ∈ A k | a % m = i}.card / √↑(N k)) Filter.atTop (nhds (1 / ↑m))

Lindström's result for $A$ itself [Li98], later strengthened by Kolountzakis [Ko99]: for any sequence of Sidon sets $A_k\subseteq\{0,\ldots,N_k\}$ with $N_k\to\infty$ and $\lvert A_k\rvert\sim N_k^{1/2}$, and any modulus $m\geq 2$, the number of elements of $A_k$ congruent to $i\pmod m$, divided by $N_k^{1/2}$, tends to $1/m$ for every residue $i<m$.

Well-distribution of $A+A$ (the actual question, erdos_154) follows from this using the Sidon property.