let $x_{1},x_{2},\cdots,x_{n}$ be such that $$n\ge 3,x_{1}\le x_{2}\le\cdots \le x_{n},$$ $$x_{1}x_{2}x_{3}\cdots x_{n}=x_{1}+x_{2}+\cdots +x_{n}.$$

Let the number of ordered pairs of postive integers $(x_{1},x_{2},\cdots,x_{n})$ be $f(n)$.

Show that: $$\left\lfloor{\dfrac{\sigma{(n-1)}+1}{2}}\right\rfloor\le f(n)<\left\lfloor{\dfrac{\sigma{(n-1)}+1}{2}}\right\rfloor +n$$

where $\lfloor{x}\rfloor$ is the largest integer not greater than $x$ and $\sigma(n)$ is the number of (positive) divisors of n.


For the LHS: if $d\mid(n-1)$ and $d\geq\frac{n-1}{d}$, then by choosing $x_n=d+1$, $x_{n-1}=\frac{n-1}{d}+1$ and all the other $(n-2)$ variables equal to one we get: $$ \prod_{i=1}^{n} x_i = n-1+d+\frac{n-1}{d}+1 = (d+1)+\left(\frac{n-1}{d}+1\right)+(n-2)=\sum_{i=1}^{n} x_i$$ as wanted. We have $d(n-1)/2$ choices if $(n-1)$ is not a square and $(d(n-1)+1)/2$ otherwise. Since we accounted for all the possibilities $(x_1,x_2,\ldots,x_{n-1},x_n)=(1,1,\ldots,a,b)$, in order to prove the RHS we just need to bound the number of solutions that have three or more coordinates different from one. Since $y_1,\ldots,y_m\geq 2$ implies $$\prod_{i=1}^{m}y_i =\prod_{i=1}^{m}(1+(y_1-1))\geq\sum_{i=1}^{m}y_i+2^m-2m,$$ if $(1,1,\ldots,y_1,\ldots,y_m)$ is a solution with the last $m$ coordinates $\geq 2$, then $2^m-m \leq n$, so $m$ is bounded by $1+\log_2 n$. If we manage to prove that $y_m$ cannot be too big, too, we are almost done. Since: $$ m y_m + (n-m)\geq\sum x_i =\prod x_i \geq 2^{m-1} y_m,$$ by assuming $m\geq 3$ we have $y_m\leq\frac{n-m}{2^{m-1}-m}\leq\frac{n-m}{2^{m-3}}$, so the number of solutions with $m\geq 3$ is bounded by: $$\sum_{m=3}^{\left\lfloor 1+\log_2 n\right\rfloor}\frac{(8n-8m)^m}{2^{m^2} m!}=O(n^3),$$ still too much. Anyway, the multi-dimensional Dirichlet hyperbola method gives that the number of $(z_1,\ldots,z_m)\in\mathbb{N}_{\geq 2}^m$ such that $$\prod_{i=1}^{m}z_i-\sum_{i=1}^{m}z_1 = L$$ is $L\log L+O(L)$, hence the number of solution with three or more coordinates greater than two is bounded by: $$\sum_{m=3}^{\lfloor 1+\log_2 n\rfloor}\frac{2(n-m)\log(n-m)}{m!}\leq\frac{1}{2}n\log n$$ that is just a logarithmic factor apart from what we want to prove.

A convexity argument set the question. The algebraic variety in ${\mathbb{R}_{+}^{m}}$ given by: $$ \prod_{i=1}^{m}z_i-\sum_{i=1}^{m}z_i = L $$ is convex, hence it cannot have more than $m$ integer points on it. As a consequence, the number of solutions with three or more coordinates greater than two is bounded by: $$\sum_{m=3}^{\lfloor 1+\log_2(n)\rfloor}\!\!\!m\leq\frac{(1+\log_2 n)^2}{2}.$$ In conclusion, for any $n\geq 6$:

$$\left\lfloor\frac{d(n-1)+1}{2}\right\rfloor\leq f(n)< \left\lfloor\frac{d(n-1)+1}{2}\right\rfloor+\log_2^2 n.$$

The remaining cases $n=3,4,5$ are easy to check by hand.

  • 2
    $\begingroup$ @math110 Don't forget to award the bounty ;-) $\endgroup$ – user146010 Jul 11 '14 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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