<p>It's possible to show this for a different version of the problem, where <span class="math-container">$A$</span> and <span class="math-container">$B$</span> consist of sampling each element of <span class="math-container">$\{0,\ldots, d\}$</span> with probability <span class="math-container">$1/2$</span>.  I strongly suspect that this proof extends to <span class="math-container">$A$</span> and <span class="math-container">$B$</span> as actually defined in your question, just with more careful math.</p>
<p>The idea is to show that <span class="math-container">$2A$</span>, <span class="math-container">$2B$</span>, and <span class="math-container">$A+B$</span> each have all but <span class="math-container">$O(1)$</span> elements of <span class="math-container">$\{0, \ldots, 2d\}$</span> in expectation--that is to say, <span class="math-container">$\text{E}[\{0, \ldots, 2d\}\setminus (A+B)] = O(1)$</span>.  This immediately implies that their symmetric difference is also <span class="math-container">$O(1)$</span>.</p>
<p>Consider <span class="math-container">$i\in \{0, \ldots, d\}$</span>.  Then <span class="math-container">$i\notin A+B$</span> only if there is not a <span class="math-container">$j\in A$</span> and <span class="math-container">$k\in B$</span> with <span class="math-container">$j + k = i$</span>.<br />
For a given <span class="math-container">$i$</span>, the probability that either <span class="math-container">$j\notin A$</span> or <span class="math-container">$j-i\notin B$</span> is at most <span class="math-container">$3/4$</span>.
Since each element is chosen independently, we can multiply these probabilities, so
<span class="math-container">\begin{align*}
\Pr[i\notin A+B] &amp;\leq \prod_{j\leq i} \Pr(j\notin A \text{ or } i-j\notin B)\\
&amp;\leq (3/4)^{i+1}.
\end{align*}</span></p>
<p>A similar argument for <span class="math-container">$i\in\{d+1,\ldots, 2d\}$</span> gives <span class="math-container">$\Pr[i\notin A+B] \leq (3/4)^{2d-i + 1}$</span>.
Then <span class="math-container">$\text{E}[\{1, \ldots, 2d\}\setminus (A+B)] \leq 2\sum_{i=0}^d (3/4)^{i+1} \leq 8$</span>.</p>
<p>We can do almost the same for <span class="math-container">$2A$</span> or <span class="math-container">$2B$</span>.  However, we have to handle the case where <span class="math-container">$j = i/2$</span> separately (since <span class="math-container">$j\in A$</span> if and only if <span class="math-container">$j-i\in A$</span>).  For <span class="math-container">$j=i/2$</span>, the probability is <span class="math-container">$1/2\leq 3/4$</span>, so the math we did above is still an upper bound.  Then, <span class="math-container">$\text{E}[\{1, \ldots, 2d\}\setminus 2A] \leq 2\sum_{i=0}^d (3/4)^{i+1} \leq 8$</span>.</p>
<p>We should note that the elements in the symmetric difference are very likely to be within <span class="math-container">$O(1)$</span> of <span class="math-container">$0$</span> or <span class="math-container">$2d$</span>.</p>
<p>For a lower bound, we have
<span class="math-container">\begin{align*}
\text{E}[|(2A\cup 2B) \triangle (A+B)|] &amp;\geq \Pr(2d\in 2A\text{ and } 2d\notin (A+B))\\
&amp; = \Pr(d\in A \text{ and } d\notin B) = 1/4.
\end{align*}</span>
So the expected symmetric difference size is <span class="math-container">$\Theta(1)$</span>.</p>
<p>To extend the above bounds to your problem, where we sample without replacement so that <span class="math-container">$|A| = |B| = (d+1)/2$</span> deterministically, we need to handle that some of the above events are correlated. But intuitively this should not affect the bottom line.  For example, the probability that for some <span class="math-container">$j$</span> we do not have both <span class="math-container">$j\in A$</span> and <span class="math-container">$i-j\in B$</span>, should not significantly affect the probability that <span class="math-container">$j'\in A$</span> and <span class="math-container">$i-j'\in B$</span> for <span class="math-container">$j\neq j'$</span>.  (That said, if <span class="math-container">$i$</span> is large (say, <span class="math-container">$d/2$</span>), then these correlations <em>are</em> significant---but such an <span class="math-container">$i$</span> is extremely unlikely to be chosen anyway.)</p>

CC BY-SA 4.0
2023-06-12T18:52:18.670Z
2023-06-12T18:52:18.670Z
SamM
<p>Let <span class="math-container">$A,B \subset [d]$</span>, where <span class="math-container">$[d] = \{0,...,d \}$</span>, such that <span class="math-container">$A\cap B = \phi$</span> and <span class="math-container">$|A| = |B| = \frac{d+1}{2}$</span>. I was studying the size of <span class="math-container">$|(2A \cup 2B) \triangle (A+B)|$</span>, where <span class="math-container">$\triangle$</span> is the symmetric difference, for a research problem. Note that <span class="math-container">$2A = \{a+b | a,b \in A \}$</span> and <span class="math-container">$A+B = \{a+b | a \in A, b\in B  \} $</span>. I ran some simulations for random subsets of <span class="math-container">$A, B$</span> for different sizes of <span class="math-container">$d$</span> and found the following results:
<a href="https://i.sstatic.net/UmsDy.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/UmsDy.png" alt="array of experimental results" /></a></p>
<p>where <span class="math-container">$C = 2A \cup 2B$</span> and <span class="math-container">$D = A+B$</span>. Here I have shown the results for a single iteration but on running multiple iterations, the value remained pretty similar. I conjecture that for randomized subsets <span class="math-container">$A,B\subset [d]$</span> satisfying the above property, <span class="math-container">$\mathbb{E}\left[|(2A\cup 2B)\triangle (A+B)|\right] \in \mathcal{O}(1)$</span>.</p>
<p>I have been trying to prove such conjecture for some time but have been unable to. Any help would be appreciated.</p>

CC BY-SA 4.0
2023-06-11T20:46:34.713Z
@RishabhKothary Do you think it's true that $\mathbb{E}\big[|2A \cup 2B|\big] = 2d-\mathcal{O}(1)$ and $\mathbb{E}\big[|A+B|\big] = 2d-\mathcal{O}(1)$? If so, why not try to prove each individually?
mathworker21
CC BY-SA 4.0
2023-06-12T06:00:07.040Z
This sounds like a question about pure math, with no CS content.  Why do you believe it needs to be answered from a CS perspective?
D.W.
CC BY-SA 4.0
2023-06-12T08:23:52.027Z
@mathworker21 I assume that can work, but how do we rigorously proved bounded on the intersection to calculate the symmetric difference
Rishabh Kothary
CC BY-SA 4.0
2023-06-12T08:25:53.903Z
@D.W. I assumed that CS Theorists like discrete math problems and specialise in them, so I asked in this forum. But I guess a pure math forum would be more apt for this problem
Rishabh Kothary
CC BY-SA 4.0
2023-06-12T08:28:53.070Z
@RishabhKothary What? If both $\mathbb{E}\big[|2A\cup 2B|\big] = 2d-\mathcal{O}(1)$ and $\mathbb{E}\big[|A+B|\big] = 2d-\mathcal{O}(1)$, then $\mathbb{E}\left[\left|(2A\cup 2B)\triangle (A+B)\right|\right] = \mathcal{O}(1)$. Do you not agree?
mathworker21
CC BY-SA 4.0
2023-06-12T08:29:51.937Z
Intuitively it makes sense, proving it formally is something I don't see clearly
Rishabh Kothary
CC BY-SA 4.0
2023-06-12T08:35:54.550Z
That follows via a straightforward triangle inequality.  But if you can't see that: Why don't you try to prove each of those individually, and [edit] your question to show a proof for each of those or where you got stuck and what progress you made?
D.W.
<co.combinatorics><pr.probability>
An additive combinatoric probability question
Rishabh Kothary
# An additive combinatoric probability question

(Asked by: username_0 on 2023-06-11)

Let $A,B \subset [d]$, where $[d] = \{0,...,d \}$, such that $A\cap B = \phi$ and $|A| = |B| = \frac{d+1}{2}$. I was studying the size of $|(2A \cup 2B) \triangle (A+B)|$, where $\triangle$ is the symmetric difference, for a research problem. Note that $2A = \{a+b | a,b \in A \}$ and $A+B = \{a+b | a \in A, b\in B \} $. I ran some simulations for random subsets of $A, B$ for different sizes of $d$ and found the following results:
[![array of experimental results](https://i.sstatic.net/UmsDy.png)](https://i.sstatic.net/UmsDy.png)

where $C = 2A \cup 2B$ and $D = A+B$. Here I have shown the results for a single iteration but on running multiple iterations, the value remained pretty similar. I conjecture that for randomized subsets $A,B\subset [d]$ satisfying the above property, $\mathbb{E}\left[|(2A\cup 2B)\triangle (A+B)|\right] \in \mathcal{O}(1)$.

I have been trying to prove such conjecture for some time but have been unable to. Any help would be appreciated.

**Tags:** co.combinatorics, pr.probability

> **Comments:**
> **username_1**: @RishabhKothary Do you think it's true that $\mathbb{E}\big[|2A \cup 2B|\big] = 2d-\mathcal{O}(1)$ and $\mathbb{E}\big[|A+B|\big] = 2d-\mathcal{O}(1)$? If so, why not try to prove each individually?  
> **username_2**: This sounds like a question about pure math, with no CS content.  Why do you believe it needs to be answered from a CS perspective?  
> **username_0**: @username_1 I assume that can work, but how do we rigorously proved bounded on the intersection to calculate the symmetric difference  
> **username_0**: @username_2 I assumed that CS Theorists like discrete math problems and specialise in them, so I asked in this forum. But I guess a pure math forum would be more apt for this problem  
> **username_1**: @RishabhKothary What? If both $\mathbb{E}\big[|2A\cup 2B|\big] = 2d-\mathcal{O}(1)$ and $\mathbb{E}\big[|A+B|\big] = 2d-\mathcal{O}(1)$, then $\mathbb{E}\left[\left|(2A\cup 2B)\triangle (A+B)\right|\right] = \mathcal{O}(1)$. Do you not agree?  
> **username_0**: Intuitively it makes sense, proving it formally is something I don't see clearly  
> **username_2**: That follows via a straightforward triangle inequality.  But if you can't see that: Why don't you try to prove each of those individually, and [edit] your question to show a proof for each of those or where you got stuck and what progress you made?  

---

## 1 answers

### Answer by username_3 on 2023-06-12. Score: 2

It's possible to show this for a different version of the problem, where $A$ and $B$ consist of sampling each element of $\{0,\ldots, d\}$ with probability $1/2$. I strongly suspect that this proof extends to $A$ and $B$ as actually defined in your question, just with more careful math.

The idea is to show that $2A$, $2B$, and $A+B$ each have all but $O(1)$ elements of $\{0, \ldots, 2d\}$ in expectation--that is to say, $\text{E}[\{0, \ldots, 2d\}\setminus (A+B)] = O(1)$. This immediately implies that their symmetric difference is also $O(1)$.

Consider $i\in \{0, \ldots, d\}$. Then $i\notin A+B$ only if there is not a $j\in A$ and $k\in B$ with $j + k = i$.  
For a given $i$, the probability that either $j\notin A$ or $j-i\notin B$ is at most $3/4$.
Since each element is chosen independently, we can multiply these probabilities, so
\begin{align\*}
\Pr[i\notin A+B] &\leq \prod\_{j\leq i} \Pr(j\notin A \text{ or } i-j\notin B)\\
&\leq (3/4)^{i+1}.
\end{align\*}

A similar argument for $i\in\{d+1,\ldots, 2d\}$ gives $\Pr[i\notin A+B] \leq (3/4)^{2d-i + 1}$.
Then $\text{E}[\{1, \ldots, 2d\}\setminus (A+B)] \leq 2\sum\_{i=0}^d (3/4)^{i+1} \leq 8$.

We can do almost the same for $2A$ or $2B$. However, we have to handle the case where $j = i/2$ separately (since $j\in A$ if and only if $j-i\in A$). For $j=i/2$, the probability is $1/2\leq 3/4$, so the math we did above is still an upper bound. Then, $\text{E}[\{1, \ldots, 2d\}\setminus 2A] \leq 2\sum\_{i=0}^d (3/4)^{i+1} \leq 8$.

We should note that the elements in the symmetric difference are very likely to be within $O(1)$ of $0$ or $2d$.

For a lower bound, we have
\begin{align\*}
\text{E}[|(2A\cup 2B) \triangle (A+B)|] &\geq \Pr(2d\in 2A\text{ and } 2d\notin (A+B))\\
& = \Pr(d\in A \text{ and } d\notin B) = 1/4.
\end{align\*}
So the expected symmetric difference size is $\Theta(1)$.

To extend the above bounds to your problem, where we sample without replacement so that $|A| = |B| = (d+1)/2$ deterministically, we need to handle that some of the above events are correlated. But intuitively this should not affect the bottom line. For example, the probability that for some $j$ we do not have both $j\in A$ and $i-j\in B$, should not significantly affect the probability that $j'\in A$ and $i-j'\in B$ for $j\neq j'$. (That said, if $i$ is large (say, $d/2$), then these correlations *are* significant---but such an $i$ is extremely unlikely to be chosen anyway.)


---

