How many different numbers can be obtained as product of first $n$ natural numbers?

Question

Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set

$\{1^{a_1} \cdot 2^{a_2} \cdot \ldots \cdot n^{a_n}\mid a_i\geq 0, a_1+a_2+\ldots+a_n=m \}$.

How many results can be obtained?

Denote this number with $P(m,n)$ (the number of elements of the set defined above). For example, if $m=1$, then $P(1,n)=n$. Similarly, we have:

$P(m,1)=1$,

$P(m,2)=m+1$.

Moreover, if $n=p$ is prime then it is not difficult to see that $$P(m,p)=\sum_{i=0}^{m}P(i,p-1).$$ (We define $P(0,n)$ to be equal $1$ for any $n$.)

Furhter, using the above property one can obtain the values of $P(m,n)$, for some small values of $n$, for example for $n\leq 10$ we have:

$P(m,3)=\binom{m+2}{2}$;

$P(m,4)=(m+1)^2$;

$P(m,5)=\frac{(m+1)(m+2)(2m+3)}{6}$

$P(m,6)=(m+1){{m+2}\choose{2}}$;

$P(m,7)=\frac{(m+1)(m+2)(m+3)(3m+4)}{24}$;

$P(m,8)=\frac{(m+1)^2(m+2)(m+3)}{6}$;

$P(m,9)=\frac{(m+1)^2(m+2)^2}{4}$;

$P(m,10)=\frac{(m+1)^2(m+2)(2m+3)}{6}$.

Is there a general method that would give precise value of $P(m,n)$ for any $m$ and $n$? Or at least an approximation of $P(m,n)$?

Answer 1

If you fix $m$, this is known as the $m$-dimensional multiplication problem. In 2010 Koukoulopoulos showed that as $n\rightarrow \infty$ $$P(m,n)=\left|\lbrace a_1\cdots a_m\ :\ a_i\leq n \text{ for all } \ i\rbrace\right|\asymp \frac{n^{m+1}}{(\log n)^{c_m}(\log\log n)^{3/2}}$$ where $$c_{m}=\int_{1}^{\frac{k}{\log(m+1)}}\log x\text{d}x=\frac{\log(m+1)+m\log\left(m\right)-m\log\log(m+1)-m}{\log(m+1)}.$$ See this answer for more details.

For $m\rightarrow \infty$, and $n$ fixed your calculations show that the order of magnitude looks like $m^{\pi(n)}$ where $\pi(n)=\sum_{p\leq n}1$ denotes the number of primes less that $n$. By considering those primes $p\leq n$, it is easy to see that we have a lower bound for $P(n,m)$ of this form. In what follows, by using Rankin's trick I will obtain the bound $$P(n,m)\leq m^{\pi(n)} e^{2n}\ \ \ \ \ \ \ \ \ \ \ (1) $$ which holds for any $m$ and $n\geq 3$. (Of course this bound is only strong when $n$ is very small compared to $m$) From this, it follows that for $n$ fixed and $m\rightarrow \infty$ we obtain the correct order of magnitude $$P(n,m)\asymp m^{\pi(n)}.$$

Notice that every element in your set lies in ${1,\dots,n^m}$, and has no prime factor larger than $n$. Let $S(y)=\{n\in\mathbb{Z}:P(n)\leq y\}$ where $P(n)$ is the largest prime factor of $n$. Then $$P(n,m)\leq \sum_{\begin{array}{c} k\leq n^{m}\\ k\in S(n) \end{array}}1.$$

For any $\sigma>0$, since $\sum_{n=1,\ n\in S(y)}^\infty n^{-\sigma}=\prod_{p\leq y} \left(1-1/p^\sigma\right)^{-1}$, we have that $$P(n,m)\leq \sum_{\begin{array}{c} k\leq n^{m}\\ k\in S(n) \end{array}}\frac{n^{\sigma m}}{k^\sigma}=n^{\sigma m} \prod_{p\leq n}\left(1-\frac{1}{p^\sigma}\right)^{-1}.$$ Since $1-p^{-\sigma}\geq\frac{\sigma\log p}{2}$, it follows that $$\prod_{p\leq n}\left(1-p^{-\sigma}\right)^{-1}\leq2^{\pi(n)}\sigma^{-\pi(n)}\prod_{p\leq n}\frac{1}{\log p}\leq2^{\pi(n)}\sigma^{-\pi(n)}. $$

Choosing $\sigma=\pi(n)/m$, it follows that $$P(n,m)\leq m^{\pi(n)}n^{\pi(n)}2^{\pi(n)}\pi(n)^{-\pi(n)}.$$ Applying the Brun-Titchmarsh theorem, we obtain equation $(1)$ for all $m,n$ with $n\geq 3$.

Answer 2

I'll consider the problem when $n$ is fixed and $m$ tends to infinity. Here the examples provided by the OP seem to suggest that $P(m,n)$ behaves like a polynomial in $m$ of degree $\pi(n)$. I'll prove that (again thinking that $n$ is small, and $m$ is large) $$ (1+o(1)) \frac{m^{\pi(n)}}{\pi(n)!} \prod_{p\le n} \lfloor \frac{\log n}{\log p}\rfloor \le P(m,n) \le (1+o(1)) \frac{m^{\pi(n)}}{\pi(n)!} \prod_{p\le n} \frac{\log n}{\log p}. $$ For example when $n=10$ this shows that $$ P(m,10) \le (1+o(1)) \frac{m^4}{24} \frac{(\log 10)^4}{(\log 2)(\log 3)(\log 5)(\log 7)} = (0.4911\ldots+o(1)) m^4, $$ and $$ P(m,10) \ge (1+o(1)) \frac{m^4}{4}, $$ which are in keeping with the asymptotic $P(m,10) \sim m^4/3$ found in the question.

Edit: Here is a better upper bound for $P(m,n)$: $$ P(m,n) \le (1+o(1)) \frac{m^{\pi(n)}}{\pi(n)!} \prod_{p\le n} \lfloor \frac{\log n}{\log p}\rfloor (\pi(n))^{\pi(\sqrt{n})}. $$ Combining the upper and lower bounds, we now have for fixed $n$ and $m$ large $$ P(m,n) = \frac{m^{\pi(n)}}{\pi(n)!} \exp(O(\sqrt{n})). $$

Now for the proofs. For the original upper bound, as observed by Eric Naslund, one has $P(m,n) \le \Psi(n^m,n)$ where $\Psi(x,y)$ denotes the number of integers below $x$ all of whose prime factors lie below $y$. Naturally $\Psi(x,y)$ has been extensively studied. In the range we are interested in, $y$ is kept very small (less than $\log x$) and $x$ is much bigger. Here the problem of counting smooth numbers should be thought of as a problem of counting lattice points inside a high dimensional ``tetrahedron." This is an old idea, and for smooth numbers was worked out by Ennola. There is a paper by Granville in Aequationes Math. which discusses such lattice point problems in many related situations: see http://www.dms.umontreal.ca/~andrew/PDF/tetrahedron.pdf (specifically, eqn (2.4) there). Note that $\Psi(n^m,n)$ counts all lattice points in $\pi(n)$ dimensional space such that the coordinates are nonnegative and $\sum_{p\le n} a_p \log p \le m\log n$. The number of such lattice points is asymptotically the volume of this tetrahedron, and this gives our upper bound.

As for the lower bound, I claim that any number of the form $\prod_{p\le n} p^{a_p}$ with the property that $a_p$'s are non-negative integers and
$$ \sum_{p\le n} a_p \Big(\lfloor \frac{\log n}{\log p} \rfloor\Big)^{-1} \le m-\pi(n), $$ is counted in $P(m,n)$. To see this, for each prime $p\le n$ put $b_p=\lfloor \log n/\log p\rfloor$ and use $[a_p/b_p]$ values of $p^{b_p}$ and one extra power of $p$ to get the exponents to add up to $a_p$; the assumed inequality guarantees that at most $m$ numbers are used in doing this. So once again we are counting the lattice points in a tetrahedron, and computing the volume of this tetrahedron we obtain the lower bound.

Now for the improved upper bound. Divide the primes below $n$ into the sets $P_{k}=\{n^{1/(k+1)}<p\le n^{1/k}\}$ for $1\le k\le \log n/\log 2$. Suppose a number $N=\prod_{p\le n} p^{a_p}$ is counted in $P(m,n)$. Then we see that for each $1\le k\le \log n/\log 2$ we must have $\sum_{p\in P_k} a_p \le km$. The number of non-negative $a_p$ with $\sum_{p\in P_k} a_p\le km$ is $\binom{km+|P_k|}{km}=\binom{km+|P_k|}{|P_k|}$. Thus we conclude that $$ P(m,n) \le \prod_{k\le \log n/\log 2} \binom{km+|P_k|}{|P_k|}. $$ Now for $k=1$ we have $$ \binom{m+|P_1|}{|P_1|} = (1+o(1)) \frac{m^{|P_1|}}{|P_1|!} \le (1+o(1)) \frac{m^{|P_1|}}{\pi(n)!} \pi(n)^{\pi(\sqrt{n})}. $$ And for larger $k$ simply use that $$ \binom{km+|P_k|}{|P_k|} \le (1+o(1))(km)^{|P_k|}. $$ The new upper bound follows.

Answer 3

I add this as a new answer as it has a somewhat different flavor from my previous response. Moreover the bounds given there may still be useful. Thanks also to Edgardo for a useful discussion.

We consider the case when $n$ is fixed and $m$ is large. First we translate the problem into one of counting lattice points in certain polytopes. It will then follow from work of Khovanskii that for $P(m,n)$ here (for $m$ large) is given by a polynomial in $m$ of degree $\pi(n)$ and whose leading coefficient will be described below. It may be that for $P(m,n)$ is in fact a polynomial from the start, and maybe just the Erhart polynomial attached to a convex polytope defined below (this last point now seems unlikely; see the remark at the end of the answer).

To each natural number below $n$ associate a vector in ${\Bbb Z}^{\pi(n)}$ with non-negative coordinates corresponding to the exponents in the prime factorization of that number. Thus when $n=5$ we have the vectors $(0,0,0)$, $(1,0,0)$, $(0,1,0)$, $(2,0,0)$ and $(0,0,1)$. Let ${\mathcal C}(n)$ denote the convex hull of these $n$ vectors. If a number $N$ is written as a product of $m$ numbers below $n$, then the prime factorization of $N$ gives a vector which is contained in the set ${\mathcal C}(n)$ dilated by $m$. Therefore it follows that the $P(m,n)$ is at most the number of lattice points contained in $m\cdot {\mathcal C}(n)$ which is asymptotically $$ m^{\pi(n)} \text{Vol}({\mathcal C}(n)). $$

Further note that any vector in $(m-n)\cdot {\mathcal C}(n)$ can be expressed as a sum of at most $m$ of the $n$ vectors corresponding to $1$ to $n$. Therefore $P(m,n)$ is at least as large as the number of lattice points contained in $(m-n) \cdot {\mathcal C}(n)$ and this also is asymptotically $$ m^{\pi(n)} \text{Vol}({\mathcal C}(n)). $$

Thus we have shown that $P(m,n) \sim m^{\pi(n)} \text{Vol}({\mathcal C}(n))$. My previous answer may be seen as giving upper and lower bounds for the volume of ${\mathcal C}(n)$ by bounding it from above and below by simplices.

In view of the above translation, we see that the problem may be phrased generally as follows: Given a commutative semigroup $G$ and two finite subsets $A$ and $B$ of $G$, consider all elements that are the sum of an element of $B$ and $N$ elements of $A$; call this set $B+N*A$. Theorem 1 of Khovanskii's paper (Newton polyhedron, Hilbert polynomial, and Sums of Finite sets; translation from Russian of his paper in Functional analysis & Applications 1992) then shows that the number of elements in $B+N*A$ is a polynomial in $N$ for large $N$. Khovanskii also considers the special situation when $G$ is ${\Bbb Z}^n$ and $A$ is a finite subset of $G$ which generates all of $G$. This is the situation of the problem at hand, and his work in Section 3 of the cited paper is along the lines of the argument I gave above. Another interesting paper on this topic is the work of Barvinok and Woods (Short rational generating functions for lattice point problems) which led me to Khovanskii's paper.

Edit: See also my related question An integrality question about expressing an integer as a product of numbers below $n$ ; especially Ilya Bogdanov's excellent example which indicates that $P(m,n)$ for larger values of $n$ is perhaps not a polynomial from the start and also probably not the Erhart polynomial for ${\mathcal C}(n)$.