Popular differences and generalized Sidon sets

Abstract

For a subset $A\subseteq [N]$, we define the representation function $r_{A-A}(d):=\#\{(a,a^{\prime })\in A\times A:d=a-a^{\prime }\}$ and define $M_D(A):={\max }_{1\le d<D}{r}_{A-A}(d)$ for $D>1$. We study the smallest possible value of $M_D(A)$ as $A$ ranges over all possible subsets of $[N]$ with a given size. We give explicit asymptotic expressions with constant coefficients determined for a large range of $D$. We shall also see how this problem connects to a well-known problem about generalized Sidon sets.

15 pages, questions added