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


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


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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