Conjuntos de residuos con una única intersección bajo traslación

Question

Un juego combinatorio que estoy estudiando ha dado lugar a la siguiente pregunta. Consideremos el grupo $\Bbb Z/n\Bbb Z$ . ¿Cuál es el mayor $m$ tal que existe $k$ conjuntos de $m$ residuos tales que la intersección de una traslación de cada uno de estos conjuntos tenga como máximo 1 elemento? Es decir, si los conjuntos son $A_1, \ldots A_k$ exigimos que para todo $(c_1, \ldots, c_k)$ la intersección de $(A_i + c_i)$ para $1 \le i \le k$ tiene como máximo un elemento, donde $A_i + c_i$ se obtiene sumando $c_i$ a cada elemento de $A_i$ . Alternativamente, si simplifica la respuesta, podemos preguntar cuál es el menor $n$ se da $m$ y $k$ .

Para $k=2$ la respuesta es sencilla. Es posible cuando $n\ge m^2$ haciendo un conjunto $\{0,1,\ldots, m-1\}$ y el otro $\{0,m,\ldots, m(m-1)\}$ . Pero no me queda claro cómo extender la construcción a $k\ge 3$ .

Si existe una generalización sencilla para el caso en que los conjuntos de residuos puedan ser de distintos tamaños, también me interesaría. Es decir, se nos da $k$ y $(m_1, \ldots, m_k)$ donde el $i$ -ésimo conjunto debe tener tamaño $m_i$ y debemos encontrar el menor $n$ para los que los conjuntos pueden tener una única intersección mutua.

Gracias de antemano por cualquier ayuda.

Answer 1

Es necesario y suficiente que para cualquier $d\in\Bbb Z/n\Bbb Z$ existe $i\in\{1,2,\dots,k\}$ tal que $d\notin (A_i-A_i)$ . En otras palabras, $$\bigcap_{i=1}^k (A_i-A_i) = \{0\}.$$ Esto es válido incluso para conjuntos de distintos tamaños.

---

Desde $| A_i-A_i|\geq |A_i| = m$ obtenemos una condición necesaria: $n-1\leq k(n-m)$ es decir $$m\leq \frac{(k-1)n+1}k.$$ Para tamaños de conjunto variables, es $$n\geq \frac{m_1+\cdots+m_k-1}{k-1}.$$

---

Otra condición necesaria puede obtenerse de la observación de que para cualquier $a\in\Bbb Z/n\Bbb Z$ existe $m^k$ vectores $(c_1,\dots,c_k)$ tal que $a\in \bigcap (A_i+c_i)$ . Dado que estos vectores deben ser distintos para distintos $a$ tenemos $n\cdot m^k\leq n^k$ es decir $$m\leq n^{(k-1)/k}.$$ Esta condición implica que el ejemplo dado para $k=2$ es óptimo cuando $m^2\leq n<(m+1)^2$ .

Para tamaños de conjunto variables, se cumple la última condición: $$n\geq (m_1\cdots m_k)^{1/(k-1)}.$$

---

En cuanto a la construcción, la siguiente simplificación de la idea de Gerhard hace el trabajo para un determinado $k$ aunque no es necesariamente óptimo.

Tome cualquier número entero $0<b_1<b_2<\dots<b_k$ set $n:=\mathrm{LCM}(b_1,\dots,b_k)$ , $m:=\frac{n}{b_k}$ y seleccione $A_i$ como cualquier subconjunto de $b_i(\Bbb Z/n\Bbb Z)$ con $|A_i|=m$ . De hecho, en este entorno, para cualquier $d\in\Bbb Z/n\Bbb Z$ existe $i\in\{1,2,\dots,k\}$ tal que $b_i\nmid d$ lo que implica que $d\notin (A_i-A_i)$ . Para el ejemplo de Gerhard con $k=3$ y $b_1=5$ , $b_2=6$ y $b_3=7$ tenemos $n=210$ y $m=30$ .

Si además nos dan $n$ esta construcción se vuelve más complicada ya que tenemos que elegir $k$ números $0<b_1<b_2<\dots<b_k$ con el menor $b_k$ posible tal que $n\mid \mathrm{LCM}(b_1,\dots,b_k)$ . Es evidente que $b_k$ no puede ser menor que el mayor divisor de primera potencia $n$ . También se deduce que aquí no tiene sentido tener $k$ mayor que el número de primos distintos que dividen a $n$ ya que $b_i$ que son las potencias primos distintas que forman la factorización prima de $n$ hacer el trabajo.