# 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.

• The answer seems to be related to the covering density of the set $\{1, \dots, n\}$ in the multiplicative group generated by $1, \dots, n$ (viewed as a lattice). Jul 18 '16 at 14:56
• By the way, would you be prepared to share your probabilistic argument? I'd be interested to see this alternative approach. Oct 6 '16 at 14:19
• @OliverRoche-Newton Of course, a small price to pay for your excellent reference! Choose $A$ at random uniformly with probability $q$. Then $\mathbb{P}(x \notin A \{1 , \ldots , n\}) = (1-q)^n$. Apply the union bound to get $\mathbb{P}(\exists \ x \notin A \cdot \{1 , \ldots , n\}) \leq n(1-q)^n$. Choose $q$ to be about $\log p / n$ and with high probability $A$ will have size $p \log p / n$. Oct 7 '16 at 13:48

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$.

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.