Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
7  
For $m=2$ see mathoverflow.net/questions/31663/…;. –  Ben Barber Dec 9 '13 at 14:34
1  
Do you have in mind that $P(m,n)$ for a fixed $n$ is a polynomial in $m$ (this seems like something one could prove without too much trouble) of degree $\pi(n)$ and (for example) you'd like to know its leading coefficient? Interesting question! –  Lucia Dec 9 '13 at 21:42
    
It turns out that this problem for fixed $n$ and large $m$ has a rich structure related to counting lattice points in convex polytopes. I added a tag to highlight this connection; see also my answer below. –  Lucia Dec 14 '13 at 1:48
    
It strikes me that $P(m,2) = \sum_{i=1}^{m+1} i^0$, $P(m,3) = \sum_{i=1}^{m+1} i^1$, $P(m,5) = \sum_{i=1}^{m+1} i^2$, and $P(m,9) = \sum_{i=1}^{m+1} i^3$. I wonder why. –  kundor Mar 7 at 1:42
add comment

3 Answers

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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