What is the smallest cardinality of a self-linked set in a finite cyclic group? A subset $A$ of a group $G$ is defined to be self-linked if $A\cap gA\ne\emptyset$ for all $g\in G$. This happens if and only if $AA^{-1}=G$.
For a finite group $G$ denote by $sl(G)$ the smallest cardinality of a self-linked set in $G$. It is clear that $sl(G)\ge \sqrt{|G|}$. A more accurate lower bound is $sl(G)\ge \frac{1+\sqrt{4|G|-3}}2$. By a classical result of Singer (1938), for any power $q=p^k$  of a prime number $p$, the cyclic group $C_n$ of cardinality $n=1+q+q^2$ contains a self-linked subset of cardinality $1+q$, which implies that $sl(C_n)=1+q=\frac{1+\sqrt{4n-3}}2$. So, for such numbers $n$ the lower bound $\frac{1+\sqrt{4n-3}}2$ is exact.
In this paper we prove the upper bound $sl(C_n)\le \sqrt{2n}$ holding for all $n\ne 4$.
Problem 1. Is $sl(C_n)=(1+o(1))\sqrt{n}$?
This problem is equivalent to
Problem 2. Does the limit $\lim_{n\to\infty}{sl(C_n)}/{\sqrt{n}}$ exist?
If the answer to Problems 1,2 are negative, then we can also ask
Problem 3. Evaluate the constant $\lambda:=\limsup_{n\to\infty}{sl(C_n)}/{\sqrt{n}}$.
At the moment it is known that $1\le\lambda\le\sqrt{2}$. 
 A: The difference cover problem has been better studied in the context of $\mathbf{Z}$. Redei, Renyi, and others in the 40s asked for the size of the smallest set $A$ such that $A-A$ covers $\{1,2,\dots,N\}$. They proved an upper bound of roughly $\sqrt{8/3} \sqrt{N}$. To prove this they combined Singer's construction of a perfect difference set with the "perfect ruler" $\{0,1,4,6\}$ (which has difference set $\{-6,\dots,6\}$ each with multiplicity one). This was later improved by Leech and Golay to $\sqrt{8/3 - \epsilon}\sqrt{N}$ (for explicit but not very large $\epsilon$). More interestingly, Redei and Renyi proved a nontrivial lower bound of the form $\sqrt{2 + \frac{4}{3\pi}}\sqrt{N}$.
The upper bound can easily be ported to the cyclic problem by taking $N\approx n/2$ and reducing the set $A$ modulo $n$. This proves an upper bound of roughly $\sqrt{4/3}\sqrt{n}$. However, because of the nontrivial lower bound, this proof technique cannot prove $(1+o(1))\sqrt{n}$. Indeed I think it suggests caution.
