4
$\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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Apr 18, 2020 at 19:31
  • $\begingroup$ hmm, seems you are right $\endgroup$
    – George Shakan
    Commented 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
    Commented Apr 19, 2020 at 6:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .