For a finite set A of positive reals, prove that the set A + A - A contains at least as many positive as negative elements

Question

I am currently working on a proof that would need to use the following theorem that I cannot prove:

"Let $A$ be a finite set of positive real numbers. Then, the set $A + A - A$ contains at least as many positive elements as negative elements. ($0$ is counted as a positive element)"

To clarify: The set $A + A - A$ is defined as $\{a_1 + a_2 - a_3\mid a_1, a_2, a_3 \in A \}$.

For example: If $A = \{2,5\}$. Then $A+A-A = \{-1, 2, 5, 8\}$.

The nature of this problem lies in the duplicates that can occur. Intuitively I think that the theorem should be true since we add an element of $A$ two times but subtract an element only one time. However, it seems to me that it is very hard to prove.

Here is the idea I have been working on so far (which might be the wrong way to go about this):

Let $A = \{a_1, a_2,\dotsc,a_n\}$. We first look at the set $A-A$. This set is symmetric around zero. For every element $x$ in $A-A$, $-x$ also occurs in $A-A$. This means that for every negative element, there also exists a unique positive element.

Next we look at the set $a_1 + A - A$. This just shifts $A-A$ to the right. Some negative elements might change into positive ones, but we do not care about that. What is important is, that every positive element stays positive. Therefore again, this set contains more or equally as many positive than negative elements.

My next idea is to look at the set $a_2 + A - A$ and take the union with the set $a_1 + A - A$. I want to do this with every $a_i$. That means in the end I take the following union: $\bigcup\limits_{i=1}^{n}a_i + A - A$ which is exactly $ A+A-A$.

I want to prove at each step that there are still more or equally as many positive than negative elements in the current union of sets. My idea to do this is to think of the following: Since $A-A$ is symmetric around $0$, I can split $A-A$ into elements that are $>0$ and elements that are $<0$ (we do not care about the $0$). These two subsets have the same size. If we add an $a_i$ to a positive element, we have two cases:

1. Case: We get a new element that does not already occur in our union of sets. In this case we do not have to do anything.

2. Case: We get a duplicate. In this case we need to show that we also get a unique duplicate if we add $a_i$ to a certain negative element.

My method for the second case was: If $a_i + x_1 = y$ and $y$ is a duplicate, then there exists an $a_j$ such that $a_j + x_2 = y$. Since $x_1$ and $x_2$ are contained in the set $A - A$, we know that $-x_1$ and $-x_2$ are also contained in the set $A - A$. Now we see that $a_i + (-x_2)$ also produces a duplicate that originates from the negative number $-x_2$, since $a_i + (-x_2) = a_j + (-x_1)$.

This method does actually always find a negative duplicate, however it is not unique in very specific cases. It is possible that two different positive duplicates refer to the same negative duplicate.

Example (a real example would be too big, so assume that $A$ contains $3$, $4$ and $6$ and assume that $A - A$ contains $4$, $5$ and $7$ and therefore also $-4$, $-5$, and $-7$):

• $4 + A - A$ contains $4 + 4 = 8$ (and $4 + (-5) = -1$)

• $6 + A - A$ contains $6 + 4 = 10$ (and $6 + (-7) = -1$)

• $3 + A - A$ contains $3 + 5 = 8$ and $3 + 7 = 10$. Both of these duplicates refer to the same negative duplicate $3 + (-4) = -1$.

Although this case is very specific, it kind of destroys my whole proof unfortunately.

If somebody has an idea for this problem, maybe even with a completely different method, I would be very grateful to hear and also very excited to discuss it.

On a side note: For my project, it would suffice to show that

$$ \left(\begin{array}{@{}c@{}} \text{Number of positive}\\ \text{elements in $A + A - A$}\\ \end{array}\right) \geq c\cdot \left(\begin{array}{@{}c@{}} \text{Number of elements}\\ \text{in $A + A - A$}\\ \end{array}\right) $$ where $c>0$ does not depend on $A$. I think it is true for $c = \frac{1}{2}$.

Edit: Here is a counterexample that I found with your help: $A = \{1, 2, 4, 5, 9, 12, 13, 17, 21, 24, 25, 29, 33, 37, 40, 41, 45, 49, 53, 56, 57, 61, 65, 69, 72, 73, 77, 81, 85, 88, 89, 93, 97, 101, 104, 105, 109, 113, 117, 120, 121, 125, 129, 133, 136, 137, 141, 145, 149, 152, 153, 157, 161, 165, 168, 169, 173, 177, 181, 184, 185, 189, 193, 197, 200, 201, 205, 209, 213, 216, 217, 221, 225, 229, 232, 233, 237, 241, 245, 248, 249, 253, 257, 261, 264, 265, 269, 273, 277, 280, 281, 285, 289, 293, 296, 297, 301, 305, 309, 312, 313, 317, 321, 325, 328, 329, 333, 337, 341, 344, 345, 349, 353, 357, 360, 361, 365, 369, 373, 376, 377, 381, 385, 389, 392, 393, 397, 401, 405, 408, 409, 413, 417, 421, 424, 425, 429, 433, 437, 440, 441, 445, 449, 453, 456, 457, 461, 465, 469, 472, 473, 477, 481, 485, 488, 489, 493, 497, 501, 504, 505, 509, 513, 517, 520, 521, 525, 529, 533, 536, 537, 541, 545, 549, 552, 553, 557, 561, 565, 568, 569, 573, 577, 581, 584, 585, 589, 593, 597, 600, 601, 605, 609, 613, 616, 617, 621, 625, 629, 632, 633, 637, 641, 645, 648, 649, 653, 657, 661, 664, 665, 669, 673, 677, 680, 681, 685, 689, 693, 696, 697, 701, 705, 709, 712, 713, 717, 721, 725, 728, 729, 733, 737, 741, 744, 745, 749, 753, 757, 760, 761, 765, 769, 773, 776, 777, 781, 785, 789, 792, 793, 797, 801, 805, 809, 813, 817, 820, 821, 825, 828, 829, 830, 848, 4250, 8500, 12750, 17000, 21250, 25500, 29750, 34000, 38250, 42500, 46750, 51000, 55250, 59500, 63750, 68000, 72250, 76500, 80750, 85000, 89250, 93500, 97750, 102000, 106250, 110500, 114750, 119000, 123250, 127500, 131750, 136000, 140250, 144500, 148750, 153000, 157250, 161500, 165750, 170000, 174250, 178500, 182750, 187000, 191250, 195500, 199750, 204000, 208250, 212500, 216750, 221000, 225250, 229500, 233750, 238000, 242250, 246500, 250750, 255000, 259250, 263500, 267750, 272000, 276250, 280500, 284750, 289000, 293250, 297500, 301750, 306000, 310250, 314500, 318750, 323000, 327250, 331500, 335750, 340000, 344250, 348500, 352750, 357000, 361250, 365500, 369750, 374000, 378250, 382500, 386750, 391000, 395250, 399500, 403750, 408000, 412250, 416500, 420750\}$

With this set $A + A - A$ contains 164039 positive and 164834 negative elements.

Answer 1

Here is a counterexample. We first need a "more sums than differences" construction:

Lemma. For any $\varepsilon>0$ there exists a cyclic group ${\bf Z}/N{\bf Z}$ and a non-empty subset $A \subset {\bf Z}/N{\bf Z}$ such that $A+A = {\bf Z}/N{\bf Z}$ but $|A-A| \leq \varepsilon N$.

Proof. There are many constructions; here is just one. We first observe if $p$ is a large prime then we can achieve this claim with $N=p$ and $\varepsilon = 1-2/p$ by a probabilistic construction, namely by selecting $A$ to consist of one element at random for each of the $\lfloor \frac{p}{3}\rfloor$ pairs $\{ 3j, 3j+1\}$ for $0 \leq j < \frac{p-2}{3}$. $A-A$ will surely avoid $\pm 1$, whilst $A+A$ will equal all of ${\bf Z}/p{\bf Z}$ with exponentially high probability by a standard union bound argument.

Taking Cartesian products of these examples and using the Chinese remainder theorem, one can achieve the claim for $\varepsilon = \prod_{k=1}^K (1-\frac{2}{p_k})$ for any sequence $p_1,\dots,p_K$ of sufficiently large distinct primes. By Mertens' theorem (or Euler's theorem) this product can be arbitrarily small, and the claim follows. $\Box$

Corollary. For any $\varepsilon>0$ there exists $N > 1$ and $A' \subset \{1,\dots,2N\}$ such that $|A'+A'| \geq N$ and $|A'-A'| = O(\varepsilon N)$.

Proof Take $A' := \{ 1 \leq n \leq 2N: n \hbox{ mod } N \in A \}$, where $A$ is as in the previous lemma; note that $A'+A'$ then contains $\{N+1,\dots,2N\}$. $\Box$

Now let $\varepsilon>0$ be a sufficiently small quantity (for instance one can take $\varepsilon = \frac{1}{100}$), and $A' \subset \{1,\dots,2N\}$ be as in the above corollary, then $|A'| \leq |A'-A'| \ll \varepsilon N$, hence $\varepsilon N \gg 1$. If we take

$$ A'' := A' \cup \{ 10N, 20N, 30N, 40N, 50N \}$$ then $|A''| = O(\varepsilon N)$, and $A''+A''-A''$ contains the set $$ A'+A' - \{10N, 20N, 30N, 40N, 50N \}$$ which has cardinality at least $5N$ and consists entirely of negative numbers. On the other hand, the positive elements of $A''+A''-A''$ are contained in the union of $\{1,\dots,4N\}$, the set $$ \{10N, 20N, 30N, 40N, 50N \} + A'-A',$$ the set $$ \{10N, 20N, 30N, 40N, 50N \} + \{10N, 20N, 30N, 40N, 50N \} - A''$$ and the set $$ \{10N, 20N, 30N, 40N, 50N \} + A'' - \{10N, 20N, 30N, 40N, 50N \},$$ and hence the number of positive elements is at most $4N + O(\varepsilon N)$. For $\varepsilon$ small enough we obtain a counterexample.

EDIT: On the other hand, if one counts elements of the set $A+A-A$ with multiplicity (i.e., one studies the convolution $1_A * 1_A * 1_{-A}$ rather than the sumset $A+A-A$), then it is certainly the case that at least half of the elements (counting multiplicity) are positive. This is because for any $a_1,a_2,a_3 \in A$, at least one of $a_1+a_2-a_3$ and $a_1+a_3-a_2$ is positive. Averaging this fact over all choices of $a_1,a_2,a_3$ gives the claim.

SECOND EDIT: as mentioned by Oliver in comments, (a slight modification of) this construction answers the first question of Section 4.3 of this thesis of Peter Bradshaw in the negative.

Answer 2

The following idea may work, the last step looks heuristic though.

Let $A=\{a_1, \ldots, a_n \}$ and let $$C:= \{0 , \pm \alpha_1, \ldots \pm \alpha_k \}$$ with $\alpha_1, \ldots, \alpha_k >0$.

Let $D:= \{ \alpha_1, \ldots, \alpha_k \}$.

Then $$ (A+A-A)_+=\{x \in A+A-A : x >0 \} \supseteq A+D \\ (A+A-A)_-=\{x \in A+A-A : x <0 \} \subseteq A-D \\ $$ So, if we can prove that $|A-D| \leq |A+D|$ you are done.

Now, define $$ F: A \times D \to A+D , F(x,y)= x+y \\ G: A \times D \to A-D, G(x,y)=x-y \,. $$ These functions satisfy $F(a,b)=F(c,d) \Leftrightarrow G(a,d)=G(c,d)$. If this can be used to show that $F,G$ have equal cardinality ranges, you are done; if not, I should delete this.