# How to prove $\left\lfloor\frac{\sigma{(n-1)}+1}{2}\right\rfloor\le f(n)<\left\lfloor\frac{\sigma{(n-1)}+1}{2}\right\rfloor+n$

Question:

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.

## 1 Answer

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.

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