Skip to main content

Sets of residues with only a single intersection under translation

A combinatorial game I am studying has given rise to the following question. Consider the group $\Bbb Z/n\Bbb Z$. What is the largest $m$ such that there exist $k$ sets m residues such that the intersection of a translation of each of these sets has at most 1 element? That is, if the sets are $A_1, \ldots A_m$, we require that for all $(c_1, \ldots, c_m)$ the intersection of $(A_i + c_i)$ for $1 \le i \le m$ has at most one element, where $A_i + c_i$ is set obtained by adding $c_i$ to every element in $A_i$. Alternatively, if it makes the answer simpler, we can ask what the smallest $n$ is given $m$ and $k$.

For $k=2$, the answer is simple. It is possible when $n\le m^2-m+1$ by making one set $\{0,1,\ldots, m-1\}$ and the other $\{0,m,\ldots, m(m-1)\}$. But it's not clear to me how to extend the construction to $k\ge 3$.

If there is a simple generalization to the case where the sets of residues can be different sizes, I'd be interested in that as well. That is, we are given $k$ and $(m_1, \ldots, m_k)$, where the $i$-th set must have size $m_i$, and we are to find the smallest $n$ for which the sets can have a single mutual intersection.

Thanks in advance for any help.

BPP
  • 675
  • 4
  • 16