Sets of residues with only a single intersection under translation

Question

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.

Answer 1

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.