# An integrality question about expressing an integer as a product of numbers below $n$

Let $n\ge 2$ be a natural number. Suppose that $N$ is a natural number, composed only of primes below $n$, and that can be expressed as $$N= \prod_{j=1}^{n} j^{x_j}$$ where $x_1$, $\ldots$, $x_n$ are non-negative rational numbers with $\sum_{j}x_j \in {\Bbb N}$. Does there necessarily exist a representation of $N$ as $$N=\prod_{j=1}^{n} j^{a_j}$$ where $a_1$, $\ldots$, $a_n$ are non-negative integers with $\sum_{j} a_j=\sum_j x_j$?

Let me also give the interpretation in terms of lattice points in polytopes in case that is easier to think about. For each natural number below $n$ associate a point in ${\Bbb Z}^{\pi(n)}$ corresponding to the exponents in the prime factorization of $n$. So $1$ corresponds to $(0,0,\ldots,0)$, $2$ corresponds to $(1,0,\ldots,0)$ and so on. Let ${\mathcal C}(n)$ denote the convex hull of these lattice points. Suppose we know that a number $N$ corresponds to a lattice point in ${\mathcal C}(n)$ dilated by a factor $m \in {\Bbb N}$. Can that lattice point then be written as a sum of $m$ lattice points from ${\mathcal C}(n)$? In general it is not true that the lattice points in the dilate of a set must fall in the $m$-fold sumset. Is it true in this special situation?

Note: I had originally overlooked the condition that $N$ should be composed only of primes below $n$. This subtlety was pointed out by The Masked Avenger, and at the same time Greg Martin produced an excellent example to show why it is necessary. Thanks to both of them, and with apologies to Greg for the oversight. Greg also provided a solution even when $N$ is composed only of primes below $N$. Here the problem is that the situation for numbers permits more relations than the situation for polytopes which is what I kept thinking about. So I've moved the goalpost one more time (sorry) by asking whether rationality of $x_j$ implies integrality. If this also has a simple counterexample, then I give up!

(Note: the condition that $\sum_j x_j \in {\Bbb N}$ is necessary, else as Christian Elsholtz kindly pointed out one has the counterexample $1^0\times 2^{1/2}\times 3^0\times 4^{1/4}=2$.)

This problem arose in connection with the recent MO question: How many different numbers can be obtained as product of first $n$ natural numbers? If the problem posed here has a positive answer, then it would follow (in the notation of the linked question) that $P(m,n)$ is the Erhart polynomial (in $m$) of a certain convex polytope ${\mathcal C}(n)$.

• Uh, what prevents $1^{1/4}$ to appear in Christian's example? Can't you tweak the exponent of 1 to meet your conditions? – The Masked Avenger Dec 14 '13 at 19:59
• If you use $1^{1/4}$ then $2$ can indeed just be written as $2^1$ (all other exponents are zero) and the exponents do add up. – Lucia Dec 14 '13 at 20:01
• Some of the subtleties are striking me now. Here is an important case to consider. Let N be so represented, except that the (set of) primes with nonzero exponent are disjoint from the (set of) prime factors of N. Is it even possible that the sum of the exponents is rational, let alone equal to the sum from a standard factorization? – The Masked Avenger Dec 14 '13 at 20:10
• From Gelfond Schneider, I expect not, but I am out of (err) my field here. – The Masked Avenger Dec 14 '13 at 20:14
• @TheMaskedAvenger -- I don't want it to be that subtle! Assume that the $x_j$'s are all rational and add up to an integer. Does it then follow that there is an integral representation? Or simply assume that $N$ is composed only of primes up to $n$. – Lucia Dec 14 '13 at 20:15

It seems that here is an example for rational exponents.

Let $n=2209=47^2>3^7>2^{11}$, and $N=4\,385\,664=2^7\cdot 3^6\cdot 47=2048^{7/11}\cdot 2187^{6/7}\cdot 2209^{1/2}\cdot 1^{1/154}$ with $7/11+6/7+1/2+1/154=2$. If $N=ab$ with $a,b\leq 47^2$, then 47 divides one of $a$ and $b$ (say, $a=47k$); since $a,b\leq 47^2$ we have $47\geq k\geq 40$ (the right estimate is quite rough). But there is no product of powers of 2 and 3 in this interval.

• Excellent! Thanks. That does exactly what I was asking. – Lucia Dec 15 '13 at 11:28

No. Set $$x=\frac32, \quad y=\frac{\log(32/25)}{\log(16/9)}, \quad\text{and }z=\frac{\log(25/24)}{\log(16/9)}.$$ Then $2^x 3^y 4^z = 5$ and $x+y+z=2$, yet there is no way to write $5$ as a product of integers not exceeding $4$.

This might seem like a crazy coincidence, but it's not: for any integers $a<b<c<d$, the set of $(x,y,z)\in\mathbb R^3$ such that $$a^x b^y c^z = d \quad\text{and}\quad x+y+z=2$$ is the solution of a system of two linear equations. (Really! Take logarithms of the first one....) And under mild conditions (perhaps simply $c>\sqrt d$), the set of solutions will contain $(x,y,z)$ that are all nonnegative.

The same method can produce counterexamples to the updated claim as well: note that $48$ is composed only of primes not exceeding $7$, but cannot be written as the product of $2$ integers not exceeding $7$. Yet $2^u4^v7^w = 48$ where \begin{align*} u&=\frac{-110 \log 2-28 \log 3+55 \log 7}{28 \log 2}\\ v&=\frac{111 \log 2+28 \log 3-55 \log 7}{28 \log 2}\\ w&=\frac{55}{28} \end{align*} sum to $2$ and are all positive.

• Thank you that is an excellent answer to my original question, but I had overlooked a subtlety as pointed out by TheMaskedAvenger. I really had in mind that $N$ is genuinely composed only of primes up to $n$ (so that one is in the polytope situation). Your answer came in as I was editing the question after TheMaskedAvenger's comment. Sorry about that. – Lucia Dec 14 '13 at 20:35
• If I read Lucia's intent correctly, the matter is simply bookkeepping of exponents of primes dividing N. In this simpler case, I think the x_i can be "piled on" the largest prime power, and any difference placed on 1's exponent. – The Masked Avenger Dec 14 '13 at 20:59
• @TheMaskedAvenger: That will only show that there is a representation with $\sum a_j$ being not more than $\sum x_j$ plus $n$. It's not at all clear that you can get $\sum a_j$ to be at most $\sum x_j$ (so that you can pile the difference on the $1$ exponent). – Lucia Dec 14 '13 at 21:01
• @Lucia: took me a little longer, but I broke this one too >:) – Greg Martin Dec 14 '13 at 22:27
• Yeah, that's harder. I searched quickly for counterexamples, with $n=9$ (actually I ignored $j=5$ and $j=7$) and $X=\sum x_j=2,3,4,5,6$. There are a few integers less than $9^6$ that cannot be written as the product of $X=6$ integers not exceeding $9$; but none of them seem to arise from a nonnegative linear combination of the lattice points corresponding to $\{1,2,3,4,6,8,9\}$. I suspect if there were such a missing integer (with $X$ larger) of the form $2^m3^n$ with $m<2n$, then we might be in business for a counterexample. The closest I found (for $X=6$) was $2^{11}3^5$. – Greg Martin Dec 14 '13 at 23:28