Small set such that $\{1 , \ldots , n\} \cdot A = \mathbb{Z} / p \mathbb{Z}$ Let $p$ be a large prime and $n < p$. What is the smallest size of a set $A \subset \mathbb{Z} / p \mathbb{Z}$ such that $A \cdot \{1 , \ldots , n\} = \mathbb{Z} / p \mathbb{Z}$? Here $\cdot$ denotes the product set $X\cdot Y = \{xy : x \in X , y \in Y\}$. 
Trivial bounds are $$p/n \leq |A| \leq p,$$ and using the probabilistic method one can improve the upper bound to $|A| \ll (p/n) \log p$, just a logarithm away from the lower bound.  
 A: I believe that the answer to this question can be found in this paper of Chen, Shparlinski and Winterhof. See Theorem 2 on page 6. It seems they give a contruction of a set with size $|A| \leq \frac{2p}{n}$ such that $A \cdot \{1,2,\dots,n\}=\mathbb Z_p$.
A: Let me elaborate on the comment above. Consider the multiplicative group $G^\times \subset \mathbb{Q}$ generated by the integers $1, 2, \dots, n$. This is a finitely generated free abelian group, and hence can be identified (non-canonically) to some $\mathbb{Z}^d$. The set $S = \{1, 2, \dots, n\}$ is a finite subset of $G^\times$. Let $\delta_n$ be the translational covering density of $S \subset G^\times$ (the minimal density of $A \subset G^\times$ subject to $A \cdot S = G^\times$). 
Now I claim the following:

For fixed $n$, the answer is asymptotically $\lvert A \rvert = \delta_n p$. 

To avoid over-complicating the proof, I shall give only a sketch. 
There is a natural group homomorphism $\phi : G^\times \to (\mathbb{Z}/p\mathbb{Z})^\times$. First observe that if $A \cdot \{1, \dots, n\} = \mathbb{Z}/p\mathbb{Z}$ then the inverse image $\phi^{-1}(A)$ becomes a covering of $G^\times$ by $S$. Thus the density of $\phi^{-1}(A)$ in $G$ is at most $\delta_n$. By the same reason, $\phi^{-1}(c A)$ has density at most $\delta$. Averaging this inequality over $c \in \mathbb{Z}/p\mathbb{Z}$ yields $\lvert A \setminus \{0\} \rvert \ge \delta_n (p-1)$. We thus get $$\lvert A \rvert \ge 1 + \delta_n(p-1).$$
We now explicitly construct the set $A$, given the $B \subseteq G^\times$ with density $\delta_n$ and $B \cdot S = G^\times$. Consider the sub-lattice $\Lambda_p = \phi^{-1}(1) \subseteq G^\times$. Given any $1 \neq x \in G^\times$, there exist only finitely many primes $p$ such that $x \in \Lambda_p$, because only finitely many primes divide $x-1$. Thus the minimum distance of $\Lambda_p$ tends to infinity as $p \to \infty$. (We use an arbitrary Euclidean norm on $G^\times \cong \mathbb{Z}^d$) 
Look at the Voronoi cell $V \subset G^\times$ of $0 \in \Lambda_p$. This cell is a fundamental region of $\Lambda_p$ and will contain all vectors of length smaller than $r_p$, where $r_p \to \infty$ as $p \to \infty$. Consider all elements $b \in B$ (the optimal covering) such that $(b \cdot S) \cap V \neq \emptyset$, and let the set of such elements be $B_0$. Because $V$ is the intersection of a lattice and a convex polytope containing a large ball, the size of $B_0$ will be asymptotically $\delta_n \det \Lambda_p$. Also, by definition, $B_0 \cdot S \supseteq V$. Let the image of $B_0$ under $\phi$ be $A_0$. Then asymptotically $\lvert A_0 \rvert \sim \delta_n \lvert \operatorname{im} \phi \rvert$ and $A_0 \cdot \{1, \dots, n\}$ contains $\operatorname{im} \phi$. Taking representatives of the cosets of $(\mathbb{Z}/p\mathbb{Z})^\times / \operatorname{im} \phi$ and multiplying them to $A_0$ gives a set $A \subseteq \mathbb{Z}/p\mathbb{Z}$ such that $A \cdot \{1, \dots, n\} = \mathbb{Z}/p\mathbb{Z}$ and $\lvert A \rvert \sim \delta_n p$. Therefore $$\lvert A \rvert \ll \delta_n p.$$

So the problem reduces to finding the covering density of a some set. Obviously, one has $\delta_n \ge 1/n$. On the other hand, 

For any prime $q \le n+1$, we have $\delta_n \le 1/(q-1)$. 

We give the explicit construction. Consider the set
$$ A = \{ x \in G^\times : x / q^{\nu_q(x)} \equiv 1 \pmod{q} \} \subset G^\times. $$
Then we have a partition $G^\times = A \amalg 2A \amalg \cdots \amalg (q-1)A$. Hence the density of $A$ is $1/(q-1)$ and $A$ is a covering. Thus $\delta_n \le 1/(q-1)$. 
Of course, this is not a tight bound; for example if $n = 5$ then $\delta_n = 1/5$. It seems likely that $\delta_n = 1/n$ for every $n$, but a construction doesn't look easy. 
