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?

Improve this question
$\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$
    – George Shakan
    Apr 16, 2020 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, 2020 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$
    – George Shakan
    Apr 16, 2020 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, 2020 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$
    – George Shakan
    Apr 16, 2020 at 14:12

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Great, thank you! (And please, fix the reference...) $\endgroup$
    – Seva
    Apr 17, 2020 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, 2020 at 19:31
  • $\begingroup$ hmm, seems you are right $\endgroup$
    – George Shakan
    Apr 19, 2020 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, 2020 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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