58
$\begingroup$

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.

$\endgroup$
7
  • 3
    $\begingroup$ Let $C=A-A$. Then $C$ is symmetric, meaning $-C=C$. $\endgroup$
    – Nick S
    Commented May 23, 2023 at 21:05
  • 9
    $\begingroup$ Crosspost: math.stackexchange.com/questions/4695157/… (it is OK to crosspost after an acceptable period, as you have done, but you should link to the other question) $\endgroup$ Commented May 24, 2023 at 8:53
  • 1
    $\begingroup$ (Incidentally, wouldn't it be a great feature if the stackexchange system would indicate relevant math.se questions, say with large text overlap, as closely related?) $\endgroup$ Commented May 24, 2023 at 8:55
  • 2
    $\begingroup$ You say that $0$ counts as a positive element. Does it also count as a negative one? \\ Also, I think that this probably is not a nt.number-theory question. $\endgroup$
    – LSpice
    Commented May 24, 2023 at 18:34
  • 6
    $\begingroup$ @LSpice: this question belongs to the area of additive combinatorics, which is often thought of as a part of the intersection of combinatorics and number theory. $\endgroup$ Commented May 24, 2023 at 19:06

2 Answers 2

75
$\begingroup$

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.

$\endgroup$
11
  • 12
    $\begingroup$ This is very nice! And it seems that you can push this further by extending the augmented large arithmetic progression part of $A''$ in order to give a construction with $ |(A+A-A) \cap (0, \infty)| = o(|A+A-A|). $ This is perhaps a little surprising, and disproves a conjecture that has been doing the rounds. The question was mentioned explicitly in Peter Bradshaw's recent PhD thesis. $\endgroup$ Commented May 25, 2023 at 13:13
  • 11
    $\begingroup$ Yes, I think you're right. For the record, the way I arrived at this construction was by studying how the set $A+A-A$ changed when a single point $x$ was added to $A$, and noting (for $x$ large enough) that this essentially amounted to adding a translate of $A+A$ to the negative real axis and translates of $A-A$ and $A$ to the positive real axis. This naturally suggested that "more sums than differences sets" could be used to create a counterexample. $\endgroup$
    – Terry Tao
    Commented May 25, 2023 at 14:46
  • 2
    $\begingroup$ What would be the smallest counter-example? $\endgroup$
    – Wlod AA
    Commented May 25, 2023 at 21:39
  • 4
    $\begingroup$ @WlodAA I would imagine that resolving this question completely would be prohibitively computationally expensive but one should able to generate explicit counterexamples (with something like $10^5$ elements, I estimate) using some explicit MSTD set constructions, such as those in core.ac.uk/download/pdf/18528431.pdf . Perhaps suitable for an undergraduate research project? $\endgroup$
    – Terry Tao
    Commented May 26, 2023 at 0:13
  • 8
    $\begingroup$ @TerryTao Thank you for your remarkable answer! With the help of your construction and the link you provided in your last comment I was finally able to create a counterexample with just 363 elements. I essentially took a MSTD set and in the last step of your construction I went up until 1000N instead of 50N. $\endgroup$ Commented May 27, 2023 at 15:52
5
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ I think the last line should be $F(a,b)=F(c,d) \Leftrightarrow G(a,d)=G(c,b)$, right? Also, you meant to use the set $D$ in the functions instead of $C$, correct? But yes, this is what we have to do and it is written in a very nice and compact way! $\endgroup$ Commented May 24, 2023 at 12:50
  • $\begingroup$ @TimoReichert Ty, fixed. $\endgroup$
    – Nick S
    Commented May 24, 2023 at 15:18
  • 2
    $\begingroup$ $|A-D|\le|A+D|$ is certainly not true for arbitrary sets of positive numbers $A$ and $D$: e.g., let $A=D=\{1,2,4\}$; then $A+D=\{2,3,4,5,6,8\}$ has $6$ elements, but $A-D=\{-3,-2,-1,0,1,2,3\}$ has $7$. More generally, if $A=D$ is a Sidon set with $n$ elements, then $|A+D|=(n+1)n/2$, but $|A-D|=n(n-1)+1$, which is almost twice as big. $\endgroup$ Commented May 24, 2023 at 15:37
  • 7
    $\begingroup$ I agree, I have already shown that we cannot prove the statement for $A + M$, where $M$ is an arbitrary symmetric set around 0. We would have to somehow use the fact that $M$ gets created by $A - A$. The counterexample I used for this was $M = \{-125, -121, -117, -113, -109, -106, 106, 109, 113, 117, 121, 125\}$ and $A = \{1, 4, 8, 12, 16, 20\}$, which produces the elements $\{-124, -121, -120, -117, -116, -113, -112, -109, -108, -105, -102, -101, -98, -97, -94, -93, -90, -89, -86, 107, 110, 113, 114, 117, 118, 121, 122, 125, 126, 129, 133, 137, 141, 145\}.$ 19 are negative and 15 positive. $\endgroup$ Commented May 24, 2023 at 16:57
  • 6
    $\begingroup$ @NickS If you delete your answer then we would lose Timo Reichert's useful comment. Maybe Timo should add this example to the question. $\endgroup$ Commented May 24, 2023 at 22:44

Your Answer

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

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