# Unique representation and sumsets

Let $$A$$ be a finite, nonempty subset of an abelian group, and let $$2A:=\{a+b\colon a,b\in A\}$$ and $$A-A:=\{a-b\colon a,b\in A\}$$ denote the sumset and the difference set of $$A$$, respectively.

If every non-zero element of $$A-A$$ has a unique representation as $$a-b$$ with $$a,b\in A$$, then all sums $$a+b$$ are pairwise distinct; as a result, $$A$$ is a Sidon set and $$|2A|=\frac12|A|(|A|+1)$$. Suppose now that only, say, $$k$$ elements of $$A-A$$ are known to be uniquely representable; how large must $$|2A|$$ be in this case? I am specifically interested in the situation where $$k=|A|+1$$.

Another way to cast the problem is as follows. If there is a group element with a unique representation in $$A-A$$, then $$|2A|\ge 2|A|-1$$. How large must $$|2A|$$ be given that $$A-A$$ has at least $$|A|+1$$ uniquely representable elements?

• Ah, a much better example: take $A = \{1 , \ldots , n\} e_1 \cup e_2 \cup e_3 \subset \mathbb{Z}^3$. This shows $|2A|$ can be as small as $4|A| - O(1)$. Apr 16 '20 at 11:10
• @GeorgeShakan: Thanks, good examples - but still fall a little short of what I need: can $|2A|$ be smaller than, say, $2.25|A|$?
– Seva
Apr 16 '20 at 12:36
• In the integers, can you use Freiman's $3k-3$ theorem to rule this out? I didn't check. Apr 16 '20 at 12:41
• @GeorgeShakan: yes, this seems to be true for the integers. Suppose that $\{0,l\}\subset A\subset[0,l]$, and write $|A|=n$ and $|2A|=Cn$. Ignoring the $O(1)$-terms, since $|2A|<3|A|$, we have $l<(C-1)n$. If $g<l/2$ is uniquely representable, then $g\le|[1,2g]\setminus A|\le l-n$. Thus, the interval $[l-n,l/2]$ does not contain any uniquely representable integers, and similarly for the interval $[l/2,n]$. Hence, there are at most $2(l-n)<2(C-2)n$ such integers, and this is less than $n$ provided $C<2.5$.
– Seva
Apr 16 '20 at 13:32
• Ah one can improve the $4|A|$ to $3|A|$ in the comment above by working over $\mathbb{F}_2^n$ and replacing the arithmetic progression with a subgroup. It is easy to show that the hard case is $|A\cap A+(s-s')| \geq (1-.25)|A|$ for all $s,s'\in U$ where $U$ is the set of elements with unique representation. Apr 16 '20 at 14:12

One can have $$|2A|$$ as small as $$2|A|$$. Take $$A = H \cup \{g\}$$ where $$H$$ is a subgroup, $$g \notin H$$ and$$g \neq -g$$. Then $$|A+A| = 2|A| + O(1)$$ while $$g+H$$ and $$H - g$$ all have a unique representative in $$A-A$$.

On the other hand, I can show if the number of uniquely representable elements of $$A-A$$ is at least $$|A|$$ and $$|A+A| \leq (7/3)|A|$$, then there is a subgroup, $$H$$, of size at most $$(3/2)|A|$$ such that the unique representatives lie in a coset of $$H$$. I'll adopt notation from Tao and Vu (mostly Chapter 2). Let

$$U : = \{x \in G : r_{A-A}(x) =1\}.$$

Let $$g, h\in U$$. By the Bonferroni inequalities, we have

$$|A+A| \geq |A| + |A+g| + |A+h| - |A\cap(A+g)| - |A\cap(A+h)| - |(A+g) \cap (A+h)|.$$ As $$g,h \in U$$, we have $$|A\cap(A+g)| = |A \cap (A+h)| = 1$$ and so

$$|A+A| \geq 3|A| - 2 - r_{A-A}(g-h).$$

Thus if $$r_{A-A}(g-h) \leq (1-\epsilon)|A|$$

we have $$|A+A| \geq (2+\epsilon)|A| - 2.$$

So we suppose for all $$g,h\in U$$,

$$\tag{1}\label{1} r_{A-A}(g-h) \geq (1-\epsilon)|A|.$$

Note that \eqref{1} implies that $$U-U \subset {\rm Sym}_{1-\epsilon}(A).$$ Markov implies $$|{\rm Sym}_{1-\epsilon}(A)| \leq \frac{|A|}{1-\epsilon},$$ and so by assumption $$|U-U| \leq \frac{|A|}{1-\epsilon} \leq \frac{|U|}{1-\epsilon}.$$ Suppose now that $$(1-\epsilon)^{-1} \leq 3/2$$ (i.e. $$\epsilon \leq 1/3$$). Then by baby Freiman (see Theorem 1.5.2), we have that $$U \subset H + t,$$ for some $$H \leq G$$, with $$|H| \leq (3/2)|A|$$ and $$t \in G$$.

• Great, thank you! (And please, fix the reference...)
– Seva
Apr 17 '20 at 17:57
• Upon a second look, I am still a little uncertain. Applying Bonferroni, you seem to assume that $A,A+g$ and $A+f$ are subsets of $2A$ - which, in general, is not the case. It is my understanding that in fact, you find $f$ and $g$ so as to have $f=a-c$ and $g=b-c$ with some $a,b,c\in A$, and then consider $(A+a)\cup(A+b)\cup(A+c)$. However, in this case it is not true that $r(g-h)$ is large for any $f$ and $g$ (but only for $f$ and $g$ which can be represented as above). Could you explain?
– Seva
Apr 18 '20 at 19:31
• hmm, seems you are right Apr 19 '20 at 0:16
• Still, there is an interesting property which seems to follow this way: namely, the unique representation graph is triangle-free. Incidentally, in your example the URG is a star.
– Seva
Apr 19 '20 at 6:40