Deje $\textbf{Z}_n$ el conjunto $\{0, 1, \ldots, n - 1\}$ con la adición de mod $n$. Considere la posibilidad de subconjuntos $S_n$ $\textbf{Z}_n$ tal que $(S_n + k) \cap S_n$ es no vacío para cada $k$$\textbf{Z}_n$. Deje $f(n)$ denotar el mínimo número de elementos de un subconjunto. ¿Qué es$$\lim_{n \to \infty} {\ln f(n) \over \ln n} \text{ ?}$$
Respuesta
¿Demasiados anuncios?
El límite es de $1/2$.
Primero debemos reformular la condición de que $(S_n + k) \cap S_n$ es no vacío para todos los $k$, como sigue. Para cada $k$$\textbf{Z}_n$, hay elementos $x$ $y$ $S_n$ tal que $x - y \equiv k$ (mod $n$). Llamamos a $S_n$ una diferencia conjunto modulo $n$ si esta condición se cumple.
Para una diferencia set $S_n$ $m$ elementos, existen en la mayoría de las $m^2$ posibles diferencias. Esto demuestra que $(f(n))^2 \ge n$, y por lo tanto$${{\log f(n)}\over{\log n}} \ge {1\over2}.$$On the other hand, let$$T_n = \{1, 2, 3, \ldots, \lfloor\sqrt{n}\rfloor, 2\lfloor\sqrt{n}\rfloor, 3\lfloor\sqrt{n}\rfloor, \ldots, \lfloor\sqrt{n}\rfloor^2\}.$$We claim that for $n \ge 16$, $T_n$ is a difference set modulo $n$. Note that any integer from $0$ to $\lfloor\sqrt{n}\rfloor^2 - 1$, inclusive, is a difference of two elements of $T_n$. When $n \ge 16$, we have$$\lfloor\sqrt{n}\rfloor^2 > (\sqrt{n} - 1)^2 \ge n/2 + 1,$$so every integer from $0$ to $\lfloor n/2\rfloor$ is a difference of elements of $T_n$. but then their opposites are also differences, and thus all the integers $m$ satisfying$$-n/2 < m \le n/2$$are differences of elements in $T_n$. Since every $k$ in $\mathbb{Z}_n$ is equal (mod $n$) to such an integer $m$, $T_n$ is a difference set. The set $T_n$ has $2\lfloor\sqrt{n}\rfloor - 1 < 2\sqrt{n}$ elements, and so we have $f(n) < 2\sqrt{n}$, for $n \ge 16$. This implies$${{\log f(n)}\over{\log n}} < {1\over2} + {{\log 2}\over{\log n}}.$$We can now use the squeeze theorem to conclude that$$\lim_{n \to \infty} {{\log f(n)}\over{\log n}} = {1\over2}.$$
