Let $A,B$ be nonempty sets of a finite additive group $Z$.Show that there exists an $x\in Z$ such that $1-|A\cap (B+x)|/|Z|\leq(1-|A|/|Z|)(1-|B|/|Z|)$

67 Views Asked by At

Let $A,B$ be nonempty sets of a finite additive group $Z$.Show that there exists an $x\in Z$ such that $$1-\frac{|A\cap (B+x)|}{|Z|}\leq \left(1-\frac{|A|}{|Z|}\right)\left(1-\frac{|B|}{|Z|}\right)$$ and a $y\in Z$ such that $$1-\frac{|A\cap (B+y)|}{|Z|}\geq \left(1-\frac{|A|}{|Z|}\right)\left(1-\frac{|B|}{|Z|}\right)$$

This exercise is from Tao and Vu's Additive Combinatorics and here is what I have tried: Randomly pick an $y\in Z$, and assume $|A|\geq |B|$, then we have $|A\cap (B+x)|\leq |A|$. Hence $$1-\frac{|A\cap (B+y)|}{|Z|}\geq \left(1-\frac{|A|}{|Z|}\right)\geq \left(1-\frac{|A|}{|Z|}\right)\left(1-\frac{|B|}{|Z|}\right)$$ Taking expectation w.r.t. $y$ and the result follows. The case $|B|\geq |A|$ is similar. But I have no idea how to get the upper bound. Thanks in advance.