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


1 Answer 1


It's clear that for some $k\in\{1,2,3\}$, we have $\frac{a_k}{x_k} \geq \frac{1}{3}$, i.e. $x_k \leq 3a_k$.

To avoid dealing with indices let me denote $C:=a_k$, $w:=x_k$ (so $w\leq 3C$), and $A,B$ and $u,v$ be such that $\{A,B,C\} = \{a_1, a_2, a_3\}$, $\{u,v,w\} = \{x_1,x_2,x_3\}$, and $$\frac{A}{u} + \frac{B}{v} + \frac{C}{w} = 1.$$ Equivalently, we have $$\frac{A}{u} + \frac{B}{v} = \frac{p}{w},$$ where $p:=w-C$. The latter equality is equivalent to $puv - Awv - Bwu = 0$ and then $$(pu - wA)(pv-wB) = w^2AB.$$ For each value of $w\in [1,3C]$, the last equation has at most $4d(w^2AB)=O((C^2AB)^\epsilon)$ solutions (for any $\epsilon>0$), where $d(\cdot)$ is the number of divisors.

Hence, $$N(a_1,a_2,a_3) = O(a_1(a_1^2a_2a_3)^\epsilon).$$

If more specific bound is needed, we can use, for example, $d(w^2AB) \leq 4(w^2AB)^{1/3}$, implying that the number of solutions for a fixed $k$ is bounded by $$16(AB)^{1/3}\sum_{w=1}^{3C} w^{2/3} \leq \frac{48}{5} (3C+1)^{5/3} (AB)^{1/3} \leq 100 a_1^{7/3}.$$ Correspondingly, $$N(a_1,a_2,a_3) \leq 300 a_1^{7/3}.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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