Cardinalities of $g$-difference sets

Abstract

Let $\hat{I}{\cdot }_g(n)$ be the smallest cardinality that $A\subseteq \mathbb{Z}$ can have if $A$ is a $g$-difference basis for $[n]$ (i.e, if, for each $x\in [n]$, there are {\em at least} $g$ solutions to $a_1-a_2=x$ ). We prove that the finite, non-zero limit $\underset{n\to \infty }{\lim }\frac{\hat{I}{\cdot }_g(n)}{\sqrt{n}}$ exists, answering a question of Kravitz. We also investigate a similar problem in the setting of a vector space over a finite field. Let $\hat{I}{\pm }_g(n)$ be the largest cardinality that $A\subseteq [n]$ can have if, for all nonzero $x$, $a_1-a_2=x$ has {\em at most} $g$ solutions. We also prove that $\hat{I}{\pm }_g(n)=\sqrt{gn}(1+o_g(1))$ as $n\to \infty$.