[Math] Underlying structure behind the infamous IMO 1988 Problem 6

ac.commutative-algebraag.algebraic-geometryalgebraic-number-theorynt.number-theory

This is the infamous Problem 6 from the 1988 IMO which has recently been popularised by the YouTube channel Numberphile:

Let $a$ and $b$ be positive integers such that $ab + 1$ divides $a^{2} + b^{2}$. Show that $\frac {a^{2} + b^{2}}{ab + 1}$ is the square of an integer.

The elementary proof is well known and based on infinite descent using Vieta jumping.

What are non-elementary ways of solving it? Which mathematical structure is useful in creating the context for this problem? Is there an insight of the type where, once the problem is put into the right algebraic context, the solution is obvious?

What I have in mind is: notice, for example, how most of the steps in Euler's proof of the Fermat's prime sum of squares theorem become trivial once re-interpreted in the ring $\mathbb Z [i] $, the infinite descent itself being replaced by Euclidean division. Is something similar applicable here?

Best Answer

Indefinite binary quadratic forms, integer coefficients and discriminant not a square, possess an automorphism group; taking the Hessian matrix $H,$ an automorphism element is an integer matrix $P$ such that $P^T H P = H.$ The oriented part ($P$ has positive determinant) is infinite cyclic. For the form $A x^2 + B xy + C y^2,$ with discriminant $\Delta= B^2 - 4 AC$ positive but not a square, Hessian $$ H = \left( \begin{array}{cc} 2A & B \\ B & 2 C \end{array} \right), $$ all positive determinant $P$ are given by integer solutions to $\tau^2 - \Delta \sigma^2 = 4,$ with $$ P = \left( \begin{array}{cc} \frac{\tau - B \sigma}{2} & - C \sigma \\ A \sigma & \frac{\tau + B \sigma}{2} \end{array} \right) $$

For the case of $x^2 + Bxy+y^2$ with $B^2 > 4,$ the automorphisms take on the familiar Vieta appearance, and the negative determinant ones can be taken to be interchanging the variables. With a fixed target $T,$ any expression $x^2 + B xy + y^2 = T$ can be transported, by automorphisms, to a region satisfying desired inequalities. These desired solutions can be thought of as representative points in a group orbit. Siegel's description of counting solutions comes down to counting the representative solutions, that is the number of orbits, as the number of literal representations of a fixed target number is infinite.

Probably worth pointing out that finding a generator for the (oriented part) of the automorphism group requires solving $\tau^2 - \Delta \sigma^2 = 4,$ where $\Delta > 0$ is not a square. This would be a bit much. However, for the special case $x^2 + B xy + y^2,$ the discriminant is $\Delta = B^2 - 4,$ so that $B^2 - \Delta 1^2 = 4.$ There is also the single-variable "jumping" argument, done extremely well in Hurwitz 1907

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

LEMMA 1

Given integers $$ M \geq m > 0, $$ along with positive integers $x,y$ with $$ x^2 - Mxy + y^2 = m. $$ Then $m$ is a square.

PROOF.

First note that we cannot have integers $xy < 0$ with $ x^2 - Mxy + y^2 = m, $ since then $ x^2 - Mxy + y^2 \geq 1 + M + 1 = M + 2 > m.$ If we have a solution with $x > 0$ and $xy \leq 0,$ it follows that $y=0.$

This is the Vieta jumping part, with some extra care about inequalities. We begin with $$ y > x $$ and $$ y < Mx. $$ We have $$ x^2 - Mxy + y^2 > 0, $$ $$ x^2 > Mxy - y^2 = y(Mx - y) > x(Mx-y), $$ $$ x > Mx - y > 0. $$ That is, the jump $$ (x,y) \mapsto (Mx - y,x) $$ takes us from one ordered solution to another ordered solution while strictly decreasing $x+y.$ Within a finite number of such jumps we violate the conditions we were preserving; we reach a solution $(x,y)$ with $y \geq Mx,$ that is $x > 0$ but $Mx-y \leq 0.$ Since $(Mx - y,x) $ is another solution we know that $Mx-y = 0.$ Therefore $x^2 = m$ and $m$ is a square.

......

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

This one takes a little more work.

LEMMA 2

Given integers $$ m > 0, \; \; M \geq m+3, $$ there are no integers $x,y$ with $$ x^2 - Mxy + y^2 = -m. $$

The contrapositive of lemma 2 is that when there are solutions, $M \leq m+2.$ The bound is sharp, achieved at $x=y=1 \; .$ As a side note, if $M \leq 2,$ then $x^2 - M xy + y^2$ is positive or positive semi-definite. So, the contrapositive gives the other example at the wikipedia article, that if $xy$ divides $x^2 + y^2 + 1$ and $x,y >0,$ then actually $x^2 + y^2 + 1 = 3xy.$

Compare the contrapositive with Lemma 3 below...

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

This one took a whole bunch more work. I also needed some help from Gerry Myerson.

LEMMA 3

Given integers $$ m > 0, \; \; M > 0, $$ such that there are integers $x,y$ with $$ x^2 - Mxy + y^2 = -Mm, $$ then $$ M \leq (m+1)^2 + 1 \; . $$ The bound is sharp, achieved with $x=1, \; y=m+1 \; .$