Combinatorial number theory, what is $\lim_{n \to \infty} {\ln f(n)\over \ln n}$?

Question

Let $\textbf{Z}_n$ be the set $\{0, 1, \ldots, n - 1\}$ with addition mod $n$. Consider subsets $S_n$ of $\textbf{Z}_n$ such that $(S_n + k) \cap S_n$ is nonempty for every $k$ in $\textbf{Z}_n$. Let $f(n)$ denote the minimal number of elements in such a subset. What is$$\lim_{n \to \infty} {\ln f(n) \over \ln n} \text{ ?}$$

Answer 1

The limit is $1/2$.

First we rephrase the condition that $(S_n + k) \cap S_n$ is nonempty for all $k$, as follows. For every $k$ in $\textbf{Z}_n$, there are elements $x$ and $y$ in $S_n$ such that $x - y \equiv k$ (mod $n$). We call $S_n$ a difference set modulo $n$ if this condition is satisfied.

For a difference set $S_n$ with $m$ elements, there are at most $m^2$ possible differences. This shows that $(f(n))^2 \ge n$, and therefore$${{\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}.$$