Proof By Infinite Descent

Proof By Infinite Descent

In mathematics, a proof by infinite descent is a particular kind of proof by contradiction which relies on the facts that the natural numbers are well ordered and that there are only a finite number of them that are smaller than any given one. One typical application is to show that a given equation has no solutions.

Assuming an example with a particular property exists, one shows that another exists that is in some sense 'smaller' as measured by a natural number. Then by mathematical induction (infinitely repeating the same step), one shows there are a yet smaller, then a yet even smaller, example, and hence there must be an infinitude of ever smaller examples. Since there are only a finite number of natural numbers smaller than the size of the initially postulated example, this is impossible—it is a contradiction, so no such initial example can exist.

This illustrative description can be restated in terms of a minimal counterexample, giving a more common type of proof formulation. We suppose a 'smallest' solution and then derive a smaller one — thereby getting a contradiction.

The method was developed by and much used for Diophantine equations by Fermat. Two typical examples are showing the non-solvability of the Diophantine equation r2 + s4 = t4 and proving that any prime p such that p ≡ 1 (mod 4) can be expressed as a sum of two squares. In some cases, to a modern eye, what he was using was (in effect) the doubling mapping on an elliptic curve. More precisely, his method of infinite descent was an exploitation in particular of the possibility of halving rational points on an elliptic curve E by inversion of the doubling formulae. The context is of a hypothetical rational point on E with large co-ordinates. Doubling a point on E roughly doubles the length of the numbers required to write it (as number of digits): so that a 'halved' point is quite clearly smaller. In this way Fermat was able to show the non-existence of solutions in many cases of Diophantine equations of classical interest (for example, the problem of four perfect squares in arithmetic progression).