Are there any "nontrivial" sets with small difference sets?

Question

I'm trying to find finite sets $S$ of natural numbers with "small" difference sets. One option is just taking an arithmetic progression $S = \{0, , \ldots, n-1\}$. Then $|S - S| = 2 |S| - 1$, which is, I think, the smallest possible difference set. However, I'm not able to find examples that stray too far from that mold. According to some computer tests, all the subsets $S \subset \{0, \ldots, 20\}$ that have difference sets with $|S - S| \leq 2.1 |S|$ that are not arithmetic progressions look like $$ \{0,1,2,3,4,5,6,7,8,9,11\} $$ and there are no such subsets with $|S - S| \leq 2.05 |S|$. I've run some subsets of $\{0, \ldots, 30\}$ and am getting similar results. When I chance my criterion to be, for instance, $|S - S| \leq 2|S|^{1.1}$ (or some other polynomial of degree $< 2$), I get basically the same sets: ones that look like arithmetic progressions.

My question is then, is it possible to find large sets with small difference sets that are not very similar to arithmetic progressions? Or, is there a theorem relating the size of $|S - S|$ to how "close" $S$ must be to an arithmetic progression?

I'm aware of Freiman's theorem. Ideally there would be a version that instead of working with $|A + A| < K|A|$, worked with $|A + A| < K|A|^r$ for $1 \leq r < 2$.

Freiman's theorem states that (roughly) that letting $n = |A|$, if $|A - A| \leq \alpha n$, then $A$ is contained in a generalized arithmetic progression of dimension $d = O(e^\alpha)$ and length $C = O\left(e^{e^{\alpha}}n\right)$. Rusza stated, and Tao implied, that the correct bounds should be about $d \sim \alpha$ and $C \sim e^{\alpha}$, for a progression of dimension $\alpha$ and length $e^\alpha n$. So I'm revising my question to make it a little more precise:

Are there "very large" finite sets $A \subset \mathbb{Z}$ of size $n = |A|$ such that $|A - A| \leq 4|A|$ (for instance) such that the smallest generalized progression containing $A$ has size at least $e^4n$?

Answer 1

For very small constants there are quite precise results, but I would not know one that works for $4$ specifically. Yet since you only give this as "for instance" let me mention a result for $3$ that goes in the direction you ask about (but the structure is really nice).

It is known that if $|A-A| \le 3|A|-4 $ then $A$ is contained in an arithmetic progression of length $|A-A| - |A|+1$; this is a variant of Freiman's famous $3k-4$ theorem.

This is sharp, as an example of the form $\{0, 1, \dots , n-1 \} \cup \{m, m+ 1, \dots , m+ n-1 \} $ shows. Note this is two dimensional progression.

And, if $|A-A| = 3|A|-3$ one has a complete description, too. Namely, for $A$ a set of nonnegative integers containing $0$ and such that the GCD of all elements is $1$ (note we can always reduce to this case) one has:

• $|A| \ge 1 + \max A /2$, or

• $A$ is the union of two arithmetic progressions with the same common difference.

See "A generalization of Freiman's 3k−3 Theorem," by Hamidoune and Plagne, Acta Arith. 103 (2002), 147-156