# Erdos multiplication table problem in $\mathbb{Z} / p\mathbb{Z}$

Let $p$ be a prime, let $k\geq2$ and let $(2p)^{\frac{1}{k}} \leq N << p$. Let $A_N = \{\bar{a} : 1 \leq a \leq N\}$, where $\bar{a} := a + p\mathbb{Z} \in \mathbb{Z} / p\mathbb{Z}$. Consider $A_N^k = \{ \bar{a}_1\cdot...\cdot\bar{a}_k : \bar{a}_i \in A_N\$for all $i\}$.
What is known about $|A_N^k|$ ?
I am especially interested in asymptotic (in $p$) lower bounds for when $N=C \cdot p^{\frac{1}{k}+\epsilon}$ or $N=C \cdot p^{\frac{1}{k}}\cdot \log ^c p$ (other than the lower bounds inherited from the original multiplication table problem for $N^\prime = p^{\frac{1}{k}} < N$).

## 1 Answer

MR2235360 (2007c:11094) Garaev, M. Z., Character sums in short intervals and the multiplication table modulo a large prime, Monatsh. Math. 148 (2006), no. 2, 127–138, proves (quoting the review by Konyagin) that for $\pi(X)(1+o(1))$ primes $p$, $p<X$, there are $p(1+o(1))$ residue classes modulo $p$ of the form $xy\pmod p$, where $1\le x,y\le p^{1/2}(\log p)^{1.087}$.

MR2334952 (2008j:11140) Garaev, M. Z.; Karatsuba, A. A., The representation of residue classes by products of small integers, Proc. Edinb. Math. Soc. (2) 50 (2007), no. 2, 363–375, goes farther, and (again quoting Konyagin) proves that for any prime $p$ and for $N=p^{1/2+o(1)}$ the set of $xy\pmod p$, $1\le x,y\le N$, contains $(1+o(1))$ residue classes modulo $p$.

Following up the references in MathSciNet leads to more recent work. For example, MR3479546 Cilleruelo, J.; Garaev, M. Z., Congruences involving product of intervals and sets with small multiplicative doubling modulo a prime and applications, Math. Proc. Cambridge Philos. Soc. 160 (2016), no. 3, 477–494, shows (as per reviewer Leonardis) every nonzero residue modulo $p$ can be written as a product of three residues, each between 1 and any $H>p^{0.625+\epsilon}$.