# An additive combinatoric probability question

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:

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.

• @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? Jun 11 at 20:46
• 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.
Jun 12 at 6:00
• @mathworker21 I assume that can work, but how do we rigorously proved bounded on the intersection to calculate the symmetric difference Jun 12 at 8:23
• @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 Jun 12 at 8:25
• @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? Jun 12 at 8:28

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.)