17
$\begingroup$

Let $A$ be a finite set. Define the symbols $+$ and $-$ as follows: $$A+A=\{a+b:a,b\in A\};$$ $$A-A=\{a-b:a,b\in A\}.$$ Prove or disprove $|A+A|\leq|A-A|$, where $|A|$ denotes the cardinality of $A$.

This is a seemingly correct conjecture. But surprisingly, it is false. A counterexample is $A=\{1,2,3,5,8,9,13,15,16\}$, then $A+A=\{2,3,\ldots,32\}\backslash\{27\}$, $|A+A|=30$ and $A-A=\{-15,-14,\ldots,15\}\backslash\{\pm9\}$, $|A-A|=29$.

Now here are my questions:

  1. What's special about that counterexample that made it different? And can we gain some insight from this into how to generate more counterexamples?
  2. Since $|A+A|\leq|A-A|$ is false, can we find the minimum/infimum of $\frac{|A+A|}{|A-A|}$?
$\endgroup$
5
  • $\begingroup$ $A$ does contain Fibonacci numbers. Maybe that's relevant? $\endgroup$ – Arthur Sep 5 '16 at 5:20
  • $\begingroup$ @Arthur Then is it possible to use Fibonacci numbers to generate more counterexamples? $\endgroup$ – Colescu Sep 5 '16 at 6:19
  • 3
    $\begingroup$ "This is a seemingly correct conjecture." Why does it seem true? $\endgroup$ – fleablood Sep 5 '16 at 6:22
  • 5
    $\begingroup$ @fleablood: Intuitively since $a+b=b+a$ but $a-b\neq b-a$ there are about twice as many potential differences as sums. $\endgroup$ – Stig Hemmer Sep 5 '16 at 8:14
  • $\begingroup$ I hadn't considered the doubling. But even so I still wouldn't assume it'd must be. Hypothetically it'd seem we could arrange it so that most of the a-b = a' - b' whereas most of the a+b are distinct (which is what the counterexample does). However doing so does seem to be more difficult than I would have thought. $\endgroup$ – fleablood Sep 5 '16 at 18:00
11
$\begingroup$

For $A \subset \mathbb{Z}$, $\frac{|A+A|}{|A-A|}$ has infimum $0$ and supremum $\infty$. Based on your example, we can show that $|A+A|/|A-A|$ can take both arbitrarily small and arbitrarily large positive values.

Let $B$ denote your example and consider $A = B^k \subset \mathbb{Z}^k$. Then $A+A = (B+B)^k$ and $A-A = (B-B)^k$, so $|A+A| = 30^k$ and $|A-A| = 29^k$. This means that $\frac{|A+A|}{|A-A|} = (\frac{30}{29})^k$, which can become arbitrarily large. To find an example in $\mathbb{Z}$, consider the map $\phi: \mathbb{Z}^k \to \mathbb{Z}$ given by $\phi: (a_1, \ldots, a_k) \mapsto a_1 + N \cdot a_2 + N^2 \cdot a_3 + \ldots + N^{k-1} a_k$, where $N$ is chosen sufficiently large. The sumset and the difference set of the image $\phi(A)$ of $A$ in $\mathbb{Z}$ then have the same sizes as the sumset and the difference set of $A$, because $\phi$ preserves the "additive structure" of $A$.

Similarly, to show that $|A+A|/|A-A|$ can take arbitrarily small values, start from an example $B \subset \mathbb{Z}$ satisfying $|B-B| > |B+B|$.

Bounds relating the size of the sumset with the size of the difference set. Although by the above an inequality of the form $|A-A| \geq k |A+A|$ is not possible, some inequalities that relate $|A-A|$ and $|A+A|$ have been proven. Two attractive examples are $$ |A+A|^{3/4} \leq |A-A| \leq |A+A|^{4/3} $$ and $$ \sigma(A)^{1/2} \leq \delta(A) \leq \sigma(A)^{2} $$ where $\sigma(A) = \frac{|A+A|}{|A|}$ and $\delta(A) = \frac{|A-A|}{|A|}$. You can read more about this in these lecture notes by Imre Ruzsa. Surprisingly, these bounds are symmetric although typically the difference set will be larger than the sumset.

Sets having more sums than differences. There is some literature available about sets $A$ with $|A-A| < |A+A|$. These sets are sometimes called MSTD-sets (for "more sums than differences"). For example, see this survey article. This article also provides some constructions for MSTD-sets.

$\endgroup$
2
  • $\begingroup$ Thanks for your brilliant answer! Can you tell me where to find the proofs of the two inequalities you posted? If they're on the lecture notes you provided, then on what page/section can I find the proofs? $\endgroup$ – Colescu Sep 5 '16 at 11:55
  • $\begingroup$ The first inequality and the upper bound of the second inequality are mentioned on page 16 (the proof should be in a Russian paper from 1973). The upper bound is also proven (this is an easy corollary of the Ruzsa triangle inequality). The lower bound is proven in this survey article arxiv.org/pdf/1212.0458v1.pdf (corollary 3.5). The book Additive Combinatorics by Tao and Vu is also an excellent reference for this subject. $\endgroup$ – user133281 Sep 5 '16 at 15:17

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.