The multiplication table problem in large dimensions

Abstract

For $N\ge 2$ and $k\ge 1$, let $M_k(N):=\#\{x_1\cdots x_k:x_i\in \{1,\dots ,N\}\text{ for all }i\}$ be the $k$-dimensional multiplication table. Given $N$, Khovanskii's theorem implies that $M_k(N)$ agrees, for all sufficiently large $k$, with a polynomial in $k$ of degree $\pi (N)$. We determine the asymptotic size of its leading coefficient, proving that, as $N\to \infty$, with $k$ sufficiently large relative to $N$, \[ M_k(N) = \exp\bigg((2π+o(1))\frac{\sqrt{N}}{\log N}\bigg)\frac{k^{π(N)}}{π(N)!}. \] We also study the analogous problem when the factors are restricted to $y$-smooth integers. For $y=o(\log N)$, we prove that the number of distinct products of $k$ such integers up to $N$ is asymptotic to the number of $y$-smooth integers up to $N^k$, uniformly for $k\ge 1$.

20 pages