3
$\begingroup$

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?

$\endgroup$
6
  • 2
    $\begingroup$ 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)$. $\endgroup$ Apr 16 '20 at 11:10
  • $\begingroup$ @GeorgeShakan: Thanks, good examples - but still fall a little short of what I need: can $|2A|$ be smaller than, say, $2.25|A|$? $\endgroup$
    – Seva
    Apr 16 '20 at 12:36
  • 2
    $\begingroup$ In the integers, can you use Freiman's $3k-3$ theorem to rule this out? I didn't check. $\endgroup$ Apr 16 '20 at 12:41
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Seva
    Apr 16 '20 at 13:32
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 16 '20 at 14:12
1
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ Great, thank you! (And please, fix the reference...) $\endgroup$
    – Seva
    Apr 17 '20 at 17:57
  • $\begingroup$ 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? $\endgroup$
    – Seva
    Apr 18 '20 at 19:31
  • $\begingroup$ hmm, seems you are right $\endgroup$ Apr 19 '20 at 0:16
  • $\begingroup$ 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. $\endgroup$
    – Seva
    Apr 19 '20 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.