Small Sets with Large Difference Sets

Abstract

For every $\epsilon >0$ and $k\in \mathbb{N}$, Haight constructed a set $A\subset {\mathbb{Z}}_N$ (${\mathbb{Z}}_N$ stands for the integers modulo $N$) for a suitable $N$, such that $A-A={\mathbb{Z}}_N$ and $|kA|<\epsilon N$. Recently, Nathanson posed the problem of constructing sets $A\subset {\mathbb{Z}}_N$ for given polynomials $p$ and $q$, such that $p(A)={\mathbb{Z}}_N$ and $|q(A)|<\epsilon N$, where $p(A)$ is the set $\{p(a_1,a_2,\dots ,a_n):a_1,a_2,\dots ,a_n\in A\}$, when $p$ has $n$ variables. In this paper, we give a partial answer to Nathanson's question. For every $k\in \mathbb{N}$ and $\epsilon >0$, we find a set $A\subset {\mathbb{Z}}_N$ for suitable $N$, such that $A-A={\mathbb{Z}}_N$, but $|A^2+kA|<\epsilon N$, where $A^2+kA=\{a_1{a}_2+b_1+b_2+\cdots +b_k:a_1,a_2,b_1,\dots ,b_k\in A\}$. We also extend this result to construct, for every $k\in \mathbb{N}$ and $\epsilon >0$, a set $A\subset {\mathbb{Z}}_N$ for suitable $N$, such that $A-A={\mathbb{Z}}_N$, but $|3A^2+kA|<\epsilon N$, where $3A^2+kA=\{a_1{a}_2+a_3{a}_4+a_5{a}_6+b_1+b_2+\cdots +b_k:a_1,\dots ,a_6,b_1,\dots ,b_k\in A\}$.

22 pages