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:

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.

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.

2more comments