Infinite descent

The principle of infinite descent is a special mathematical proof procedure based on the principle of contradiction proof . This makes use of the fact that in the set of natural numbers there cannot be an infinite sequence of decreasing numbers, which is equivalent to the fact that every non-empty set of natural numbers has a smallest element. The principle of infinite descent is typically used to show that a given equation does not have an integer solution.

origin

The method of infinite descent was developed by Pierre de Fermat in the 17th century . He used the principle to prove some of his mathematical results. Among other things, the special case of Fermat's large theorem was proved by Fermat using this method. The case is closely related to the question of whether there are Pythagorean triples in which the area of ​​the right triangle with the numbers of the triple as side lengths is an integer square, see Congruent number # Fermat's theorem . ${\displaystyle n=4}$ ${\displaystyle n=4}$

The procedure was already known in ancient Greece (see the proof of the irrationality of the square root of 2 attributed to the Pythagoreans ), and examples can be found in the elements of Euclid. The method was taken up again in the theory of Diophantine equations in the 20th century (for example the Mordell-Weil theorem ).

General procedure

The task is to prove that a given mathematical problem has no solution in natural numbers. The proof now starts with the assumption of the existence of a solution. From this solution one constructs an even smaller solution with the help of the properties of the natural numbers and the problem. This process can be repeated, starting from the smaller solution that has just been found, and so one gets smaller and smaller solutions in the natural numbers. So one arrives at an infinite, descending sequence of natural numbers, which however cannot exist, because below a natural number there are only finitely many more. This contradiction shows that a wrong assumption was made. The only assumption made was the existence of a solution. This is the only possible source of error. Hence, there is no solution to this problem.

Comparison with the induction principle

The principle of proof of complete induction is equivalent to the statement that every non-empty set of natural numbers has a smallest element. The latter is equivalent to the statement that there cannot be infinite sequences of decreasing natural numbers:

If there are no infinite, descending sequences in the natural numbers, then every nonempty subset has a smallest element. If one had a non-empty subset without a smallest element, one could find an even smaller one for each element of this subset and thus construct an infinite, descending sequence.

Conversely, if every non-empty set of natural numbers has a smallest element, then there cannot be an infinite, descending sequence of natural numbers, for the set of terms of such a sequence could not have a smallest element.

Therefore, the principle of infinite descent is also based on the fact that every non-empty set of natural numbers has a smallest element.

Example of irrationality square root

To show: The root of 2 is irrational.

Proof: We assume that the square root of 2 is rational.

Rational numbers can be as a fraction of two natural numbers Write ${\displaystyle p,q}$

${\displaystyle {\sqrt {2}}={\frac {p}{q}}}$

${\displaystyle 2={\frac {p^{2}}{q^{2}}}}$

${\displaystyle 2q^{2}=p^{2}}$.

That is, divides 2 , and thus after Euclid's lemma also . With a natural applies ${\displaystyle p^{2}}$ ${\displaystyle p}$ ${\displaystyle r}$

${\displaystyle p=2r}$.

We can now set up the following equation

${\displaystyle 2q^{2}=4r^{2}}$

${\displaystyle q^{2}=2r^{2}}$.

Thus 2 also divides and . ${\displaystyle q^{2}}$ ${\displaystyle q}$

${\displaystyle q=2s}$

Overall it results

${\displaystyle {\sqrt {2}}={\frac {2r}{2s}}={\frac {r}{s}}}$.

We can see from the above representations by and ${\displaystyle p}$ ${\displaystyle q}$

${\displaystyle s={\frac {q}{2}}\Rightarrow s<q}$

${\displaystyle r={\frac {p}{2}}\Rightarrow r<p}$,

which would mean that there are even smaller ones for arbitrary ones , which represent the root of 2 as a fraction. ${\displaystyle p,q}$ ${\displaystyle r,s}$

With this we have the beginning of an infinite descent and the irrationality of is proven by the refutation of the opposite. ${\displaystyle {\sqrt {2}}}$

Example proof of the unsolvability of the Fermat equation for the power of 4

Instead of the case of the Fermat equation, the somewhat more general equation is treated. ${\displaystyle n=4}$ ${\displaystyle x^{4}+y^{4}=z^{2}}$

Suppose there were integer coprime ones as the solution of . The solution of the equation is the Pythagorean triple ${\displaystyle x,y,z}$ ${\displaystyle x^{4}+y^{4}=z^{2}}$

${\displaystyle y^{2}=2pq}$

${\displaystyle x^{2}=p^{2}-q^{2}}$

${\displaystyle z=p^{2}+q^{2}}$

where p, q are relatively prime. Since is a square, either p or q are even (and considering all possible cases of the second equation modulo 4 it follows that q is even). You also have a new Pythagorean triple for the second equation , namely ${\displaystyle 2pq}$ ${\displaystyle x^{2}=p^{2}-q^{2}}$ ${\displaystyle x^{2}+q^{2}=p^{2}}$

${\displaystyle x=r^{2}-s^{2}}$

${\displaystyle q=2rs}$

${\displaystyle p=r^{2}+s^{2}}$.

with coprime r, s. Since is a square, and . There applies and . Inserted in with results . Since v is less than z, we have the beginning of an infinite descent. ${\displaystyle 2pq}$ ${\displaystyle q=2u^{2}}$ ${\displaystyle p=v^{2}}$ ${\displaystyle q=2u^{2}=2rs}$ ${\displaystyle r=g^{2}}$ ${\displaystyle s=h^{2}}$ ${\displaystyle p=r^{2}+s^{2}}$ ${\displaystyle p=v^{2}}$ ${\displaystyle v^{2}=g^{4}+h^{4}}$

The solution for n = 4 was given by Fermat (published by Bernard Frénicle de Bessy in 1676) and later by Leonhard Euler (published in 1738), but not published by Fermat himself. The only surviving solution (in a margin note to his edition of Diophant's book) to a Diophantine problem from Fermat deals with a closely related problem, the Diophantine equation, and he used the method of infinite descent to show that there is no solution. This equation comes up when looking for a solution to the problem of whether a right triangle with integer sides has an area that is a whole square number. The sides of the triangle form a Pythagorean triple , with x, y coprime. The area is and should be the same . This requires each of the factors , , be a square , and . The unsolvability can be shown analogously to the Fermat equation for n = 4 by infinite descent. ${\displaystyle x^{4}-y^{4}=z^{2}}$ ${\displaystyle (x^{2}-y^{2},2xy,x^{2}+y^{2})}$ ${\displaystyle {\frac {1}{2}}2xy(x^{2}-y^{2})=xy(x^{2}-y^{2})}$ ${\displaystyle z^{2}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x^{2}-y^{2}}$ ${\displaystyle x=a^{2}}$ ${\displaystyle y=b^{2}}$ ${\displaystyle x^{2}-y^{2}=a^{4}-b^{4}=z^{2}}$

Fermat described the method in a letter to Christian Huygens (via Pierre de Carcavi ), noting that he first used it to show that a problem has no solution (such as that there is no Pythagorean triple whose corresponding triangle is an area which is an integer and a square), but then also to the much more difficult problem of showing that a solution exists (like that 4n + 1 is the sum of two squares).

Euler proved (as he communicated in a letter in 1753 and later published) that the Fermat equation was unsolvable for n = 3 with infinite descent, but the proof was considerably more difficult.

Web links

• Matroids Math Planet: The Infinite Descent

Individual evidence

1. ^ Fermat, Letter to Huygens 1659, quoted in André Weil, Number theory, an approach through history from Hammurapi to Legendre, Birkhäuser 1984, p. 75