This is a rewording in combinatorial language of a question posed on another forum. The original was posed as a probabilistic problem.


**Problem set up:**


Consider for a fixed prime $p$, the multiplicative group $\mathbb Z\_{p-1}^{\times}$ of integers modulo $p$. Define, for each pair $j \neq k \in \mathbb Z\_{p-1}^{\times}$, the *correlation coefficient* $C\_{j, k} \in [0, 1]$ by


$$C\_{j, k} := \sup\_{E \subset \mathbb Z^{\times}\_{p-1}} |\frac{p|jE \cap kE| - |E|^2}{p^2}|$$



> 
> **Question:** For each fixed $p$, for which $j, k$ is the minimum of the above expression achieved? Can we nontrivially bound the minimum above by a function of $p$?
> 
> 
> 



On independence of multiples of $\mathbb Z_p$
This is half an answer that I got by forgetting the outside absolute value signs; however, it shouldn't be hard to figure out how to correct it for that.


Fix $j, k$, and let $1 \leq n \leq p - 1$. Let $m = ord\_p(k j^{-1})$. Then I claim that if $m|n$, we can choose $E$ of size $n$ such that $jE = kE$; otherwise, I claim that we can choose $E$ of size $n$ such that $|jE \backslash kE| = 1$ (and that we can't find $E$ of size $n$ with $jE = kE$).


The first claim is easy: divide $\mathbb{U}\_p$ into $\langle k j^{-1}\rangle$-cosets. Take $E$ to be the union of any $\frac{n}{m}$ of them; then by the definition of cosets, $jE = kE$. That also shows why we can't do this if $m\not| n$. But we can choose $\lfloor \frac{n}{m}\rfloor$ cosets, and then one additional element $u$ in one more coset; we then "fill out" $E$ by adding $(k j^{-1})^n u$ for $n = 0, 1, \dots$ until we get a total of $n$ elements. Then $kE$ will not include $ju$, but will include $j (k j^{-1})^n$ for $n \geq 1$, so $|jE \cap kE| = n - 1$.


We now turn to the formula.
\begin{equation}
C\_{j, k} := \sup\_{E \subset \mathbb Z^{\times}\_{p-1}} \frac{p|jE \cap kE| - |E|^2}{p^2}
\end{equation}


I could explicitly calculate this, but it's not hard to see that in fact each term for the supremum is minimized when we choose $k j^{-1}$ to be a generator, in which case $|jE \cap kE| = n - 1$. So we are now looking for


\begin{equation}
C\_{\text{gen}} := \sup\_{1 \leq n \leq p - 1} \frac{p(n - 1) - n^2}{p^2}
\end{equation}
But now this is just maximizing a quadratic, and it's not hard to see that the maximum happens when $n = \frac{p}{2}$. Well, when it's either of the closest integers to $\frac{p}{2}$, i.e. either $\frac{p - 1}{2}$ or $\frac{p + 1}{2}$, in which case the number is $\frac{p^2 - 4p + 1}{4 p^2}$.




---


Here's the other half. In the first half, we tried to maximize $|jE \cap kE|$ while keeping $|E|$ constant; in this half, we will try to minimize it. By pigeonhole principle, $|jE \cap kE| \geq \max(2 |E| - (p - 1), 0)$. If $ord\_p(k j^{-1})$ is even (and if $p$ is odd, the generator will always have even order), it's not hard to attain this bound for any given $|E|$; for each $\langle k j^{-1}\rangle$-coset, pick one of the two $\langle (k j^{-1})^2\rangle$-cosets. If $|E| \leq \frac{p - 1}{2}$, then just choose enough elements from that one sub-coset; if $E \geq \frac{p - 1}{2}$, then choose all of the elements from that one sub-coset, and just enough from the other to get $|E| = n$.


We then get that $C'\_{gen} = \max(\sup\_{1 \leq n \leq \frac{p - 1}{2}} \frac{n^2}{p^2}, \sup\_{\frac{p - 1}{2} \leq n \leq p - 1} \frac{n^2 - p(2n - (p - 1))}{p^2})$


In both cases, this is maximized when $n = \frac{p - 1}{2}$, with a final answer of $\frac{p^2 - 2\*p + 1}{p^2}$.


