3
$\begingroup$

Given $A,B \subset[0,...,d]$ such that $A \cap B = \phi$. Can we show $$ |(2A \cup 2B) \triangle (A + B)| \geq \Omega_d({\rm poly}(|A|,|B|))$$ where $2A = A+A, 2B = B+B$ and we are taking the minkowski sum. Also note that $\triangle$ is the symmetric difference.

There are results which show that $|A+B| \geq \Omega_d({\rm poly}(|A|,|B|))$ as illustrated in Estimate of Minkowski sum. Thus if $|A| << |B|$ then $2A \cup 2B$ will dominate $A+B$ and we have $$|(2A \cup 2B) \triangle (A + B)| \geq \Omega_d({\rm poly}(|A|,|B|)).$$ The interesting case is when $|A| \sim |B|$, where we can't use techniques as before. Any help in solving this question would be appreciated.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Let $A$ contain all numbers congruent to $0,1,3\mod 6$ and $B$ contain all numbers congruent to $2,4,5\mod 6$. Then the symmetric difference appears only near the ends of $[0,2d]$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you that was a very nice counter example. $\endgroup$
    – Rishabh Kothary
    Commented Oct 25 at 16:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .