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 of $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\_k$, we require that for all $(c\_1, \ldots, c\_k)$ the intersection of $(A\_i + c\_i)$ for $1 \le i \le k$ 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\ge m^2$ 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.



Sets of residues with only a single intersection under translation
It is necessary and sufficient that for any nonzero $d\in\Bbb Z/n\Bbb Z$, there exists $i\in\{1,2,\dots,k\}$ such that $d\notin (A\_i-A\_i)$. In other words,
$$\bigcap\_{i=1}^k (A\_i-A\_i) = \{0\}.$$
This holds even for sets of varying sizes.




---


Since $| A\_i-A\_i|\geq |A\_i| = m$, we get a necessary condition: $n-1\leq k(n-m)$, that is
$$m\leq \frac{(k-1)n+1}k.$$
For varying set sizes, it is
$$n\geq \frac{m\_1+\cdots+m\_k-1}{k-1}.$$




---


Another necessary condition can be obtained from the observation that for any $a\in\Bbb Z/n\Bbb Z$, there exist $m^k$ vectors $(c\_1,\dots,c\_k)$ such that $a\in \bigcap (A\_i+c\_i)$. Since these vectors must be distinct for distinct $a$, we have $n\cdot m^k\leq n^k$, that is
$$m\leq n^{(k-1)/k}.$$
This condition implies that the given example for $k=2$ is optimal when $m^2\leq n<(m+1)^2$.


For varying set sizes, the last condition takes form:
$$n\geq (m\_1\cdots m\_k)^{1/(k-1)}.$$




---


As for the construction, the following streamlining of Gerhard's idea does the job for a given $k$, although it's not necessarily optimal.


Take any integers $0<b\_1<b\_2<\dots<b\_k$, set $n:=\mathrm{LCM}(b\_1,\dots,b\_k)$, $m:=\frac{n}{b\_k}$, and select $A\_i$ as any subset of $b\_i(\Bbb Z/n\Bbb Z)$ with $|A\_i|=m$. Indeed, in this setting, for any nonzero $d\in\Bbb Z/n\Bbb Z$, there exists $i\in\{1,2,\dots,k\}$ such that $b\_i\nmid d$, implying that $d\notin (A\_i-A\_i)$.
For Gerhard's example with $k=3$ and $b\_1=5$, $b\_2=6$, and $b\_3=7$, we have $n=210$ and $m=30$.


If we are also given $n$, this construction becomes more tricky as we need to pick $k$ numbers $0<b\_1<b\_2<\dots<b\_k$ with the smallest $b\_k$ possible such that $n\mid \mathrm{LCM}(b\_1,\dots,b\_k)$. It is clear that $b\_k$ cannot be smaller than the largest primepower dividing $n$. It also follows that here it does not make sense to have $k$ greater than the number of distinct primes dividing $n$, since $b\_i$ being the distinct primepowers forming the prime factorization of $n$ do the job.


