Let $a_1 \geq a_2 \geq a_3$ be given positive integers and let $N(a_1,a_2,a_3)$ be the number of solutions $(x_1,x_2,x_3)$ of the equation $$\dfrac{a_1}{x_1}+\dfrac{a_2}{x_2}+\dfrac{a_3}{x_3} = 1$$where $x_1,x_2,$ and $x_3$ are positive integers. Show that $$N(a_1,a_2,a_3) \leq 6a_1a_2(3+\ln(2a_1)).$$


Let's denote by $N_{pqr}$ the number of solutions for which $\dfrac{a_p}{x_p} \geq \dfrac{a_q}{x_q} \geq \dfrac{a_r}{x_r}$, where $(p,q,r)$ is one of six permutations of $(1,2,3)$. It is clearly enough to prove that $N_{pqr} + N_{qpr} \leq 2a_1a_2(3+\ln(2a_1)).$ First, from $$\dfrac{3a_p}{x_p} \geq \dfrac{a_p}{x_p}+\dfrac{a_q}{x_q}+\dfrac{a_r}{x_r} = 1 \qquad \text{and} \qquad \dfrac{a_p}{x_p} < 1$$
we get $a_p+1 \leq x_p \leq 3a_p$. Similarly, for fixed $x_p$, we have $$ \dfrac{2a_q}{x_q} \geq \dfrac{a_q}{x_q}+\dfrac{a_r}{x_r} = 1 - \dfrac{a_p}{x_p} \qquad \text{and} \qquad \dfrac{a_q}{x_q} \leq \min\left(\dfrac{a_p}{x_p}, 1- \dfrac{a_p}{x_p}\right),$$ which gives $\max\left(\dfrac{a_q \cdot x_p}{a_p}, \dfrac{a_q \cdot x_p}{x_p-a_q}\right) \leq x_q \leq \dfrac{2a_q \cdot x_p}{x_p-a_q}$, i.e., if $a_p+1 \leq x_p \leq 2a_p$ there are at most $\dfrac{a_q \cdot x_p}{x_p-a_q}+\dfrac{1}{2}$ possible values for $x_q$ (since there are $[2x]-[x] = \left[x+\dfrac{1}{2}\right]$ integers between $x$ and $2x$), and if $2a_p+1 \leq x_p \leq3a_p$, at most $\dfrac{2a_q \cdot x_p}{x_p-a_p}-\dfrac{a_q \cdot x_p}{a_p}+1$ possible values for $x_q$.

Lemma 1. We have $$\displaystyle \sum_{k=1}^n \left(\dfrac{1}{k}+\dfrac{2}{k+n}\right ) \leq \ln(2n) + 2 -\ln(2).$$

Proof. We prove by induction on $n$. The case $n=1$ holds trivially since $2 \leq 2$. Now assume the result holds for some $m$. First we compute \begin{align*} \sum_{k=1}^{m+1} \left( \dfrac{1}{k} + \dfrac{2}{k+m+1}\right) = \dfrac{1}{m+1} + \dfrac{2}{2m+2} + \sum_{k=1}^m \frac{1}{k} + \sum_{k=1}^{m} \dfrac{2}{k+m+1}\tag{1}\end{align*} and see that by shifting the index we get $(1)$ to be \begin{align*}\dfrac{2}{m+1} + \sum_{k=1}^m \dfrac{1}{k} + \sum_{k=2}^{m+1} \dfrac{2}{k+m} &= \sum_{k=1}^m \dfrac{1}{k} + \sum_{k=1}^{m+1} \dfrac{2}{k+m} \\&= \sum_{k=1}^m\left( \dfrac{1}{k} + \dfrac{2}{k+m}\right) + \dfrac{2}{2m+1} \tag{2}\end{align*} Finally, applying the induction hypothesis we see that $(2)$ is $$\leq \ln(n) + 2 + \dfrac{2}{2m+1} = \ln(m+1) +2 + \left( \dfrac{2}{2m+1} + \ln(m) - \ln(m+1) \right)$$ and hence we are left to show that $$\dfrac{2}{2m+1} - \ln\left(1 + \dfrac{1}{m}\right) = \dfrac{2}{2m+1} + \ln(m) - \ln(m+1) \leq 0.$$

To prove this, we first derive the identity $\log(1+x) \leq \dfrac{2x}{x+2}$. Let $f(x) = \log(1+x)-\dfrac{2x}{x+2}$, and then $f'(x) = \dfrac{1}{1+x}-\dfrac{4}{(x+2)^2} = \dfrac{x^2}{(1+x)(x+2)} \geq 0$. Therefore $f(x) \geq f(0) = 0$ for $x \geq 0$ implying the result if we substitute in $x=\dfrac{1}{m}$. $\square$

Given $x_p$ and $x_q, x_r$ is uniquely determined. Hence

\begin{align*}N_{pqr} &\leq \sum_{x_p = a_p + 1}^{2a_p} \Bigg (\dfrac{a_p \cdot x_p}{x_p-a_p} + \dfrac{1}{2} \Bigg ) + \sum_{x_p = 2a_p+1}^{3a_p} \Bigg( \dfrac{2a_q \cdot x_p}{x_p - a_p} - \dfrac{a_q \cdot x_p}{a_p}+1 \Bigg ) \\&= \dfrac{3a_p}{2}+a_q \sum_{k = 1}^{a_p} \Bigg [ \dfrac{k+a_p}{k} + \Bigg (\dfrac{2(k+2a_p)}{k+a_p} - \dfrac{k+2a_p}{a_p} \Bigg ) \Bigg ] \\&= \dfrac{3a_p}{2}+a_q \sum_{k = 1}^{a_p} \Bigg [1 - \dfrac{k}{a_p}+a_p \Bigg (\dfrac{1}{k}+\dfrac{2}{k+a_p} \Bigg ) \Bigg ]\\&= \dfrac{3a_p}{2}-\dfrac{a_q}{2}+a_pa_q \Bigg (\dfrac{1}{2}+\sum_{k = 1}^{a_p} \Bigg (\dfrac{1}{k}+\dfrac{2}{k+a_p} \Bigg ) \Bigg ) \\&\leq a_pa_q \Bigg (\dfrac{3}{2a_q}-\dfrac{1}{2a_p}+\ln(2a_p)+\dfrac{5}{2}-\ln(2) \Bigg ).\end{align*}

Therefore, $N_{pqr} + N_{qpr} \leq 2a_pa_q(1+0.5+\ln(2a_p)+2-\ln(2)) < 2a_1a_2(2.81+\ln(2a_1))$.

My question is if there are other ways to obtain a similar bound or if this way gives the best bound. Obviously I had solved the question but I am wondering if we can obtain a stronger estimate. Another solution I had heard of used the fact that $(x,2x]$ cannot contain more than $x$ integers, which is false in general, but this gives the weaker estimate of $N \leq 6a_1a_2(9/2-\ln{2}+\ln{2a_1})$.


Your Answer

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

Browse other questions tagged or ask your own question.