12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Dongryul Kim Jul 18 '16 at 14:56
  • $\begingroup$ By the way, would you be prepared to share your probabilistic argument? I'd be interested to see this alternative approach. $\endgroup$ – Oliver Roche-Newton Oct 6 '16 at 14:19
  • 1
    $\begingroup$ @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$. $\endgroup$ – George Shakan Oct 7 '16 at 13:48
8
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.