Return to Answer

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

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

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.

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.

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

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.

Again consider the case when $n$ is fixed and $m$ tends to infinity. 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.

It still remains interesting to ask whether the answer is always a nice polynomial in $m$. Perhaps it is the Erhart polynomial of $m\cdot {\mathcal C}(n)$? There is of course an extensive literature on this (e.g. work of Barvinok and Woods), but I'm not an expert here.

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.

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.