0
$\begingroup$

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

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.

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

1 Answer 1

2
$\begingroup$

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

$\endgroup$

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.