Diophantine equation $(x+y)(x+y+1) - kxy = 0$

The following came up in my solution to this question, but buried in the comments, so maybe it's worth a question of its own. Consider the Diophantine equation $$ (x+y)(x+y+1) - kxy = 0$$ For $k=5$ and $k=6$ the positive integer solutions are given by successive terms of OEIS sequences A032908 and A101265 respectively. Are there positive integer solutions for any other positive integers $k$?

I know there are solutions if you remove the positivity requirement, but I've been unable to find any with positive integers. If my programming is correct, I've been able to rule out all $k \le 500$.

Solution 1:

I think it can be proven using Vieta jumping method that in order for

$k=\dfrac{(x+y)(x+y+1)}{xy}$

to be an integer for positive integers $x$ and $y$ the only values $k$ can take are $5, 6$.

Ok, we have

$x^2+y^2+x+y=(k-2)xy$

Vieta jumping is the key of the solving this problem. The idea of this method is that if $(x_0, y_0)$ is a solution to the equation, we will create another smaller solution $(x_1, y_1)$ in terms of $x_0$ and $y_0$, in a way that $x_1+y_1<x_0+y_0$ and then we make a smaller pair $(x_2, y_2)$ in terms of $x_1$ and $y_1$, and so on. We can't repeat this jumping downwards indefinitely, because natural numbers are limited from down. Hence we must end this procedure at some point, say $x_n, y_n$. If we can find $x_n, y_n$ then we can finally reconstruct $x_0, y_0$ by jumping upwards from $x_n, y_n$.

To apply this method to the equation, rewrite the equation as a quadratic in terms of $x$

$x^2+(1-my)x+y^2+y=0$

where $m=k-2>0$. Suppose that $(x_0, y_0)$ is a solution to the above equation, with $x_0 \ge y_0$. If we let $y=y_0$ in the quadratic, equation will have two solutions for $x$: $x=x_0$ and $x=x^*$. Then we will have: $x_0+x^*=my_0-1$ and $x_0 x^*=y_0^2+y_0$ from the first one, you can see that $x^*=my_0-1-x_0$ is an integer, and from second $x^*=\frac{y_0^2+y_0}{x_0}$ is positive.

Therewith, if $x_0 \ge \frac{y_0^2+y_0}{y_0}=y_0+1 $, then $x^*=\frac{y_0^2+y_0}{x_0} \le y_0$, and we can choose $ (x_1, y_1)=(y_0, x^*)$ as a smaller solution to the equation.

Repeating this procedure as mentioned above, we will encounter a solution $(x_n, y_n)$ where $x_n< \frac{y_n^2+y_n}{y_n}=y_n+1$, and we can no longer jump downwards. Now we must find the possible values of smallest solutions i.e. possible values of $(x_n, y_n)$. Note that $y_n \le x_n <y_n+1$. It follows that $x_n=y_n$, put this back in the original equation:

$x_n^2+(1-m x_n)x_n+x_n^2+x_n=0$

$x_n+1-m x_n+x_n+1=0$

$m=\frac{2(x_n+1)}{x_n}$

Therefore $x_n |2(x_n+1)$ or $ x_n| 2(x_n+1)-2x_n=2$ which gives us $x_n=1, 2$ with $m=4, 3$ and $k=6, 5$, respectively. So we must reconstruct solutions using two cases: $(x_n, y_n)=(1, 1)$ with $k=6$ and $(x_n, y_n)=(2, 2)$ with $k=5$.

Note that $(x_n, y_n)=(y_{n-1}, (k-2)y_{n-1}-x_{n-1}-1)$ and since $x_n=y_{n-1}$ we get $(x_{n-1}, y_{n-1})= ((k-2)x_n-y_n-1, x_n)$.

These result will reproduce OEIS sequences A032908 and A101265.

Solution 2:

This really is Vieta Jumping, I ought to have put that first line. I put about five pictures of the relevant hyperbolas at the end of this post.

Actual reference: In 1907, A. Hurwitz wrote Über eine Aufgabe der unbestimmten Analysis, in Archiv der Mathematik und Physik, pages 185-196. I give a summary and a little discussion at https://mathoverflow.net/questions/84927/conjecture-on-markov-hurwitz-diophantine-equation

We will be carefully examining the part $x,y > 0$ in the graph of $$ x^2 - q x y + y^2 + x + y = 0, $$ especially what happens as we get near the origin. Note that for $q=3$ we get the integer point $(2,2),$ for $q=4$ we get the lattice point $(1,1),$ but for $q=5$ we seem to miss any integer points. It turns out that is all that needs to be proved, that for $q \geq 5$ we get no lattice points near the origin. Technique written out very well in Hurwitz (1907).

In the fourth image, we see how the Hurwitz fundamental solutions lie between $y = \frac{qx-1}{2}$ and $x = \frac{qy-1}{2}$ along the curve $ x^2 - q x y + y^2 + x + y = 0, $ and that both $x,y < 1$ there. So that proves it.

Part of a careful proof is to confirm that the Hurwitz mappings below, also called Vieta Jumping, do not magically take us from the hyperbola branch in the first quadrant to the other branch, which passes through the origin and contains other integer solutions as well. It suffices to show that the largest value of $y$ on that branch is smaller than $1.$ This occurs, by implicit differentiation, where $2x-qy+1 = 0,$ or $$y = \frac{1}{q}(2x+1),$$ with $q \geq 3$ no matter what. When $x < 0,$ $2x+1 < 1,$ finally $ \frac{1}{q}(2x+1) < 1.$ That is, while there really is a solution at $(0,0),$ there are no integer solutions with $xy < 0.$

Hurwitz: given a solution with $x,y > 0$ integers, we get a solution that usually shrinks $x+y$ with either $$ (x,y) \mapsto (qx-y-1,x), $$ or $$ (x,y) \mapsto (y,qy-x-1). $$ I should add that Hurwitz did not bother about the order of the variables, he passed very quickly over the case of two variables. I wrote the "jumps" this way so as to keep on the same half-branch ($y \geq x$ or $x \geq y$) of the hyperbola in the first quadrant, so as to fit in with some presentations I found of Vieta jumping; I will leave them written this way, but it hardly matters.

Since $x,y>0,$ we know that both $qx-y-1,$ $qy-x-1$ are positive as well; there are no solutions with $xy<0,$ and when one of $x,y$ is $0,$ the other is $0$ or $-1.$ We keep applying these transformations to get a sequence of solutions, until we reach a fundamental solution, at the minimum of $x+y,$ i.e. $qx-y-1 \geq y$ and $qy-x-1 \geq x,$ or $$ y \leq \frac{qx-1}{2} \; \; \mbox{AND} \; \; x \leq \frac{qy-1}{2}, $$ which are the extra pair of lines I drew in the final two pictures. We do not need to pay much attention to whether $x$ or $y$ is larger, really.

I added in a picture with my $q=9,$ the entire arc is even more firmly within the strict standard unit square, that is $x,y < 1.$ The $y$ coordinate at $x = (2y+1)/ q$ satisfies $$ (q^2 - 4)y^2 - (2q+4)y - (q+1) = 0. $$ For $q=3,4$ the positive root exceeds $1.$ However, for $q \geq 5,$ the positive root is smaller than one. For $q=5,$ $y = \frac{14 + 10 \sqrt 7}{42} \approx 0.963,$ so true for $q=5.$ Then $$ y < \frac{1 + \sqrt{q+2}}{q-2}, $$ and that inequality finishes the proof for $q \geq 6.$

Wednesday, September 2. I found a prettier way to to the final bound on the positive value of $y,$ or, rather, show that it is strictly below $1.$ We have, where the Hurwitz bounding line $x = (2y+1)/ q$ meets the hyperbola in the first quadrant, $$ (q^2 - 4)y^2 - (2q+4)y - (q+1) = 0. $$ Subtract $1$ from both sides, we have $$ (q^2 - 4)y^2 - (2q+4)y - (q+2) = -1. $$ Next divide through by $(q+2),$ for $$ (q - 2)y^2 - 2y - 1 = \frac{-1}{q+2} < 0. $$ For the left hand side to be negative with $y$ positive, the quadratic formula says we need strict $$ \color{blue}{ y < \frac{1 + \sqrt{q-1}}{q-2}}. $$ For $q=5$ this says $y<1,$ exactly what we need. For $q > 5$ the restriction is stronger still.

Solution 3:

For the equation:

$$(x+y)(x+y+1)=kxy$$

Use the standard approach of using Pell equations. If you use solutions of this equation.

$$p^2-k(k-4)s^2=1$$

Decisions can be recorded.

$$x=-(p^2+2kps+k(k-4)s^2)(p^2+2(k-2)ps+k(k-4)s^2)$$

$$y=-4ps(p^2+2kps+k(k-4)s^2)$$

If this equation Pell.

$$p^2-k(k-4)s^2=\pm1$$

Then decisions can be recorded.

$$x=\pm2(p-ks)s$$

Or.

$$x=\mp(p^2+2(k-1)ps+k(k-2)s^2)$$

For this.

$$y=\mp2(p+ks)s$$

Number $p,s - $ can have any sign.

An interesting case of when. $k=4$

The formulas can be seen that while the $s$ can be anything. And $p=\pm1$

Solution 4:

What I got so far: First, solve for $x$: $$ x=\frac{k y-2 y-1\pm\sqrt{k^2 y^2-4 k y^2-2 k y+1}}{2} $$ $x$ is only an integer, if the discriminant is a perfect square, so: $$ k^2 y^2-4 k y^2-2 k y+1=z^2 $$ Solving this for $y$: $$ y=\frac{k\pm\sqrt{k^2 z^2-4 k z^2+4 k}}{k^2-4 k} $$ This can only happen if: $$ k^2 z^2-4 k z^2+4 k=w^2\Rightarrow w^2-(k-4)kz^2=4k $$ Which is a Pell equation. If we have $w$ and $z$, then (if I made no mistakes): $$ x=\frac{1}{4} \left(\frac{4-w}{k-4}-\frac{w}{k}+2 z\right)\qquad y=\frac{k-w}{(k-4) k} $$ $$ x=\frac{1}{4} \left(\frac{w}{k}+\frac{w+4}{k-4}-2 z\right)\qquad y=\frac{k+w}{(k-4) k} $$ Will give us the solutions