Sets with few differences in abelian groups

For a finite abelian group $G$ and positive integers $m$ and $h$, we let $$\rho(G, m, h) = \min \{|hA| \; : \; A \subseteq G, |A|=m\}$$ and $$\rho_{\pm} (G, m, h) = \min \{|h_{\pm} A| \; : \; A \subseteq G, |A|=m\},$$ where $hA$ and $h_{\pm} A$ denote the $h$-fold sumset and the $h$-fold signed sumset of $A$, respectively. The study of $\rho(G, m, h)$ has a 200-year-old history and is now known for all $G$, $m$, and $h$. Here we prove that $\rho_{\pm}(G, m, h)$ equals $\rho (...

Let $h$ be a positive integer and let $\varepsilon > 0$. The Haight-Ruzsa method produces a positive integer $m^*$ and a subset $A$ of the additive abelian group $\mathbf{Z}/m^*\mathbf{Z}$ such that the difference set is large in the sense that $A-A = \mathbf{Z}/m^*\mathbf{Z}$ and $h$-fold sumset is small in the sense that $|hA| < \varepsilon m^*$. This note describes, and in a modest way extends, the Haight-Ruzsa argument, and constructs sets with more differences than multi...

We prove an elementary additive combinatorics inequality, which says that if $A$ is a subset of an Abelian group, which has, in some strong sense, large doubling, then the difference set A-A has a large subset, which has small doubling.

Let A be a subset of an abelian group G. We say that A is sum-free if there do not exist x,y and z in A satisfying x + y = z. We determine, for any G, the cardinality of the largest sum-free subset of G. This equals c(G)|G| where c(G) is a constant depending on G and lying in the interval [2/7,1/2]. We also estimate the number of sum-free subsets of G. It turns out that log_2 of this number is c(G)|G| + o(|G|), which is tight up to the o-term. For certain abelian groups, ...

Let $G$ be an additive abelian group. Let $A=\{a_{0}, a_{1},\ldots, a_{k-1}\}$ be a nonempty finite subset of $G$. For a positive integer $h$ satisfying $1\leq h\leq k$, we let \[h\hat{}_{\underline{+}}A:=\{\Sigma_{i=0}^{k-1}\lambda_{i} a_{i}: (\lambda_{0},\lambda_{1}, \ldots, \lambda_{k-1}) \in \{-1,0,1\}^{k},~\Sigma_{i=0}^{k-1}|\lambda_{i}|=h \},\] be the restricted signed sumset of $A$. The direct problem for the restricted signed sumset $h\hat{}_{\underline{+}}A$ is to fi...

For a positive integer $h$ and a subset $A$ of a given finite abelian group, we let $hA$, $h \hat{\;} A$, and $h_{\pm}A$ denote the $h$-fold sumset, restricted sumset, and signed sumset of $A$, respectively. Here we review some of what is known and not yet known about the minimum sizes of these three types of sumsets, as well as their corresponding critical numbers. In particular, we discuss several new open direct and inverse problems.

We investigate subsets with small sumset in arbitrary abelian groups. For an abelian group $G$ and an $n$-element subset $Y \subseteq G$ we show that if $m \ll s^2/(\log n)^2$, then the number of subsets $A \subseteq Y$ with $|A| = s$ and $|A + A| \leq m$ is at most \[2^{o(s)}\binom{\frac{m+\beta}{2}}{s},\] where $\beta$ is the size of the largest subgroup of $G$ of size at most $\left(1+o(1)\right)m$. This bound is sharp for $\mathbb{Z}$ and many other groups. Our result imp...

Given a group $G$, we say that a set $A \subseteq G$ has more sums than differences (MSTD) if $|A+A| > |A-A|$, has more differences than sums (MDTS) if $|A+A| < |A-A|$, or is sum-difference balanced if $|A+A| = |A-A|$. A problem of recent interest has been to understand the frequencies of these type of subsets. The seventh author and Vissuet studied the problem for arbitrary finite groups $G$ and proved that almost all subsets $A\subseteq G$ are sum-difference balanced as $...

Given a finite abelian group $G$, consider the complete graph on the set of all elements of $G$. Find a Hamiltonian cycle in this graph and for each pair of consecutive vertices along the cycle compute their sum. What are the smallest and the largest possible number of sums that can emerge in this way? What is the expected number of sums if the cycle is chosen randomly? How the answers change if an orientation is given to the cycle and differences (instead of sums) are comput...

Let $A$ be a subset of the cyclic group $\mathbf{Z}/p\mathbf{Z}$ with $p$ prime. It is a well-studied problem to determine how small $|A|$ can be if there is no unique sum in $A+A$, meaning that for every two elements $a_1,a_2\in A$, there exist $a_1',a_2'\in A$ such that $a_1+a_2=a_1'+a_2'$ and $\{a_1,a_2\}\neq \{a_1',a_2'\}$. Let $m(p)$ be the size of a smallest subset of $\mathbf{Z}/p\mathbf{Z}$ with no unique sum. The previous best known bounds are $\log p \ll m(p)\ll \sq...