An additive combinatoric probability question

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.

Answer 1

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