This question is taken from the example sheet in the description of this video.
Let $\mathbb{Z}_n$ be the set of integers mod $n$, and for a subset $A \subseteq \mathbb{Z}_n$ and $x \in \mathbb{Z}_n$, let $A+x = \{a+x \in \mathbb{Z}_n \ | \ a \in A\}$. Let $A$ and $B$ be subsets of $\mathbb{Z}_n$.
- Prove that there exists an $x \in \mathbb{Z}_n$ such that $|(A+x) \cap B| \geqslant |A||B|/n$.
- Investigate the reverse inequality. (That is, try to find sets of given cardinality for which $\max_x |(A+x) \cap B|$ is as small as possible.)
My question concerns the second part of this question. For the first part, I found that $$ \mathbb{E}\Bigl[|(A+x) \cap B|\Bigr] = \frac{|A||B|}{n}, $$ where $x \in \mathbb{Z}_n$ is chosen uniformly. The inequality shown follows from the averaging argument.
For the second part, I tried some small examples and I think taking $A$ and $B$ to contain arithmetic progressions is the way to go. In particular, for $|A| = a$ and $|B| = b$, I suspect $A = \{0,1,\dots,a-1\}$ and $B = \{0,r,\dots,(b-1)r\}$ would make $\max_x|(A+x) \cap B|$ as small as possible, where $r = \lfloor{n/b\rfloor}$ (I took $A$ to contain consecutive integers and spread out the elements of $B$ "as much as possible"). With this, $|A \cap B| = \lceil{a/r\rceil}$ and in fact, $|(A+x) \cap B| \leqslant \lceil{a/r\rceil}$ (Intuitively, I imagine a clock that is almost evenly marked with the elements of $B$ and a cyclic interval that traverses around, i.e., $A+x$).
Does this construction of $A$ and $B$ make $\max_x|(A+x) \cap B|$ as small as possible? If so, how can I show it? Thanks!