infinite descent
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a proof by infinite descent, also known as Fermat's method of descent, is a particular kind of
proof by contradiction In logic and mathematics, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction. Proof by contradiction is also known as ...
used to show that a statement cannot possibly hold for any number, by showing that if the statement were to hold for a number, then the same would be true for a smaller number, leading to an infinite descent and ultimately a contradiction. It is a method which relies on the
well-ordering principle In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element. In other words, the set of positive integers is well-ordered by its "natural" or "magnitude" order in which x precedes y i ...
, and is often used to show that a given equation, such as a
Diophantine equation In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a c ...
, has no solutions. Typically, one shows that if a solution to a problem existed, which in some sense was related to one or more
natural numbers In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal n ...
, it would necessarily imply that a second solution existed, which was related to one or more 'smaller' natural numbers. This in turn would imply a third solution related to smaller natural numbers, implying a fourth solution, therefore a fifth solution, and so on. However, there cannot be an infinity of ever-smaller natural numbers, and therefore by
mathematical induction Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ...  all hold. Informal metaphors help ...
, the original premise—that any solution exists— is incorrect: its correctness produces a
contradiction In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle's ...
. An alternative way to express this is to assume one or more solutions or examples exists, from which a smallest solution or example—a
minimal counterexample In mathematics, a minimal counterexample is the smallest example which falsifies a claim, and a proof by minimal counterexample is a method of proof which combines the use of a minimal counterexample with the ideas of proof by induction and proof ...
—can then be inferred. Once there, one would try to prove that if a smallest solution exists, then it must imply the existence of a smaller solution (in some sense), which again proves that the existence of any solution would lead to a contradiction. The earliest uses of the method of infinite descent appear in Euclid's ''Elements''. A typical example is Proposition 31 of Book 7, in which
Euclid Euclid (; grc-gre, Wikt:Εὐκλείδης, Εὐκλείδης; BC) was an ancient Greek mathematician active as a geometer and logician. Considered the "father of geometry", he is chiefly known for the ''Euclid's Elements, Elements'' trea ...
proves that every composite integer is divided (in Euclid's terminology "measured") by some prime number. The method was much later developed by
Fermat Pierre de Fermat (; between 31 October and 6 December 1607 – 12 January 1665) was a French mathematician who is given credit for early developments that led to infinitesimal calculus, including his technique of adequality. In particular, he i ...
, who coined the term and often used it for
Diophantine equation In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a c ...
s. Two typical examples are showing the non-solvability of the Diophantine equation ''r''2 + ''s''4 = ''t''4 and proving
Fermat's theorem on sums of two squares In additive number theory, Fermat's theorem on sums of two squares states that an odd prime ''p'' can be expressed as: :p = x^2 + y^2, with ''x'' and ''y'' integers, if and only if :p \equiv 1 \pmod. The prime numbers for which this is true ar ...
, which states that an odd prime ''p'' can be expressed as a sum of two
squares In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90- degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length a ...
when ''p'' ≡ 1 (
mod Mod, MOD or mods may refer to: Places * Modesto City–County Airport, Stanislaus County, California, US Arts, entertainment, and media Music * Mods (band), a Norwegian rock band * M.O.D. (Method of Destruction), a band from New York City, US ...
 4) (see proof). 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 An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...
). In some cases, to the modern eye, his "method of infinite descent" is an exploitation of the
inversion Inversion or inversions may refer to: Arts * , a French gay magazine (1924/1925) * ''Inversion'' (artwork), a 2005 temporary sculpture in Houston, Texas * Inversion (music), a term with various meanings in music theory and musical set theory * ...
of the doubling function for
rational point In number theory and algebraic geometry, a rational point of an algebraic variety is a point whose coordinates belong to a given field. If the field is not mentioned, the field of rational numbers is generally understood. If the field is the field ...
s on an elliptic curve ''E''. The context is of a hypothetical non-trivial rational point on ''E''. Doubling a point on ''E'' roughly doubles the length of the numbers required to write it (as number of digits), so that a "halving" a point gives a rational with smaller terms. Since the terms are positive, they cannot decrease forever.


Number theory

In the
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777 ...
of the twentieth century, the infinite descent method was taken up again, and pushed to a point where it connected with the main thrust of
algebraic number theory Algebraic number theory is a branch of number theory that uses the techniques of abstract algebra to study the integers, rational numbers, and their generalizations. Number-theoretic questions are expressed in terms of properties of algebraic ob ...
and the study of
L-function In mathematics, an ''L''-function is a meromorphic function on the complex plane, associated to one out of several categories of mathematical objects. An ''L''-series is a Dirichlet series, usually convergent on a half-plane, that may give ris ...
s. The structural result of
Mordell Louis Joel Mordell (28 January 1888 – 12 March 1972) was an American-born British mathematician, known for pioneering research in number theory. He was born in Philadelphia, United States, in a Jewish family of Lithuanian extraction. Educatio ...
, that the rational points on an elliptic curve ''E'' form a
finitely-generated abelian group In abstract algebra, an abelian group (G,+) is called finitely generated if there exist finitely many elements x_1,\dots,x_s in G such that every x in G can be written in the form x = n_1x_1 + n_2x_2 + \cdots + n_sx_s for some integers n_1,\dots, n ...
, used an infinite descent argument based on ''E''/2''E'' in Fermat's style. To extend this to the case of an
abelian variety In mathematics, particularly in algebraic geometry, complex analysis and algebraic number theory, an abelian variety is a projective algebraic variety that is also an algebraic group, i.e., has a group law that can be defined by regular func ...
''A'',
André Weil André Weil (; ; 6 May 1906 – 6 August 1998) was a French mathematician, known for his foundational work in number theory and algebraic geometry. He was a founding member and the ''de facto'' early leader of the mathematical Bourbaki group. Th ...
had to make more explicit the way of quantifying the size of a solution, by means of a
height function A height function is a function that quantifies the complexity of mathematical objects. In Diophantine geometry, height functions quantify the size of solutions to Diophantine equations and are typically functions from a set of points on algebraic ...
– a concept that became foundational. To show that ''A''(''Q'')/2''A''(''Q'') is finite, which is certainly a necessary condition for the finite generation of the group ''A''(''Q'') of rational points of ''A'', one must do calculations in what later was recognised as
Galois cohomology In mathematics, Galois cohomology is the study of the group cohomology of Galois modules, that is, the application of homological algebra to modules for Galois groups. A Galois group ''G'' associated to a field extension ''L''/''K'' acts in a nat ...
. In this way, abstractly-defined cohomology groups in the theory become identified with ''descents'' in the tradition of Fermat. The Mordell–Weil theorem was at the start of what later became a very extensive theory.


Application examples


Irrationality of

The proof that the
square root of 2 The square root of 2 (approximately 1.4142) is a positive real number that, when multiplied by itself, equals the number 2. It may be written in mathematics as \sqrt or 2^, and is an algebraic number. Technically, it should be called the princip ...
() is
irrational Irrationality is cognition, thinking, talking, or acting without inclusion of rationality. It is more specifically described as an action or opinion given through inadequate use of reason, or through emotional distress or cognitive deficiency. T ...
(i.e. cannot be expressed as a fraction of two whole numbers) was discovered by the
ancient Greek Ancient Greek includes the forms of the Greek language used in ancient Greece and the ancient world from around 1500 BC to 300 BC. It is often roughly divided into the following periods: Mycenaean Greek (), Dark Ages (), the Archaic peri ...
s, and is perhaps the earliest known example of a proof by infinite descent.
Pythagoreans Pythagoreanism originated in the 6th century BC, based on and around the teachings and beliefs held by Pythagoras and his followers, the Pythagoreans. Pythagoras established the first Pythagorean community in the ancient Greek colony of Kroton, ...
discovered that the diagonal of a square is incommensurable with its side, or in modern language, that the square root of two is
irrational Irrationality is cognition, thinking, talking, or acting without inclusion of rationality. It is more specifically described as an action or opinion given through inadequate use of reason, or through emotional distress or cognitive deficiency. T ...
. Little is known with certainty about the time or circumstances of this discovery, but the name of
Hippasus Hippasus of Metapontum (; grc-gre, Ἵππασος ὁ Μεταποντῖνος, ''Híppasos''; c. 530 – c. 450 BC) was a Greek philosopher and early follower of Pythagoras. Little is known about his life or his beliefs, but he is sometimes c ...
of Metapontum is often mentioned. For a while, the Pythagoreans treated as an official secret the discovery that the square root of two is irrational, and, according to legend, Hippasus was murdered for divulging it. The square root of two is occasionally called "Pythagoras' number" or "Pythagoras' Constant", for example . The
ancient Greek Ancient Greek includes the forms of the Greek language used in ancient Greece and the ancient world from around 1500 BC to 300 BC. It is often roughly divided into the following periods: Mycenaean Greek (), Dark Ages (), the Archaic peri ...
s, not having
algebra Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics. Elementary a ...
, worked out a geometric proof by infinite descent (
John Horton Conway John Horton Conway (26 December 1937 – 11 April 2020) was an English mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He also made contributions to many branches ...
presented another geometric proof by infinite descent that may be more accessible). The following is an
algebra Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics. Elementary a ...
ic proof along similar lines: Suppose that were
rational Rationality is the quality of being guided by or based on reasons. In this regard, a person acts rationally if they have a good reason for what they do or a belief is rational if it is based on strong evidence. This quality can apply to an abili ...
. Then it could be written as :\sqrt = \frac for two natural numbers, and . Then squaring would give :2 = \frac, :2q^2 = p^2, so 2 must divide ''p''2. Because 2 is a
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
, it must also divide ''p'', by
Euclid's lemma In algebra and number theory, Euclid's lemma is a lemma that captures a fundamental property of prime numbers, namely: For example, if , , , then , and since this is divisible by 19, the lemma implies that one or both of 133 or 143 must be as w ...
. So ''p'' = 2''r'', for some integer ''r''. But then, :2q^2 = (2r)^2 = 4r^2, :q^2 = 2r^2, which shows that 2 must divide ''q'' as well. So ''q'' = 2''s'' for some integer ''s''. This gives :\frac=\frac=\frac. Therefore, if could be written as a rational number, then it could always be written as a rational number with smaller parts, which itself could be written with yet-smaller parts, ''
ad infinitum ''Ad infinitum'' is a Latin phrase meaning "to infinity" or "forevermore". Description In context, it usually means "continue forever, without limit" and this can be used to describe a non-terminating process, a non-terminating ''repeating'' pro ...
''. But this is impossible in the set of natural numbers. Since is a
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
, which can be either rational or irrational, the only option left is for to be irrational. (Alternatively, this proves that if were rational, no "smallest" representation as a fraction could exist, as any attempt to find a "smallest" representation ''p''/''q'' would imply that a smaller one existed, which is a similar contradiction.)


Irrationality of if it is not an integer

For positive integer ''k'', suppose that is not an integer, but is rational and can be expressed as for natural numbers ''m'' and ''n'', and let ''q'' be the largest integer less than (that is, ''q'' is the
floor A floor is the bottom surface of a room or vehicle. Floors vary from simple dirt in a cave to many layered surfaces made with modern technology. Floors may be stone, wood, bamboo, metal or any other material that can support the expected load ...
of ). Then :\begin \sqrt k &=\frac mn\\ pt&=\frac\\ pt&=\frac\\ pt&=\frac\\ pt&=\frac \end The numerator and denominator were each multiplied by the expression ( − ''q'')—which is positive but less than 1—and then simplified independently. So, the resulting products, say ''m′'' and ''n′'', are themselves integers, and are less than ''m'' and ''n'' respectively. Therefore, no matter what natural numbers ''m'' and ''n'' are used to express , there exist smaller natural numbers ''m′'' < ''m'' and ''n′'' < ''n'' that have the same ratio. But infinite descent on the natural numbers is impossible, so this disproves the original assumption that could be expressed as a ratio of natural numbers.


Non-solvability of ''r''2 + ''s''4 = ''t''4 and its permutations

The non-solvability of r^2 + s^4 =t^4 in integers is sufficient to show the non-solvability of q^4 + s^4 =t^4 in integers, which is a special case of
Fermat's Last Theorem In number theory, Fermat's Last Theorem (sometimes called Fermat's conjecture, especially in older texts) states that no three positive integers , , and satisfy the equation for any integer value of greater than 2. The cases and have been k ...
, and the historical proofs of the latter proceeded by more broadly proving the former using infinite descent. The following more recent proof demonstrates both of these impossibilities by proving still more broadly that a
Pythagorean triangle A Pythagorean triple consists of three positive integers , , and , such that . Such a triple is commonly written , and a well-known example is . If is a Pythagorean triple, then so is for any positive integer . A primitive Pythagorean triple is ...
cannot have any two of its sides each either a square or twice a square, since there is no smallest such triangle: Suppose there exists such a Pythagorean triangle. Then it can be scaled down to give a primitive (i.e., with no common factors other than 1) Pythagorean triangle with the same property. Primitive Pythagorean triangles' sides can be written as x=2ab, y=a^2-b^2, z=a^2+b^2, with ''a'' and ''b''
relatively prime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
and with ''a+b'' odd and hence ''y'' and ''z'' both odd. The property that ''y'' and ''z'' are each odd means that neither ''y'' nor ''z'' can be twice a square. Furthermore, if ''x'' is a square or twice a square, then each of ''a'' and ''b'' is a square or twice a square. There are three cases, depending on which two sides are postulated to each be a square or twice a square: *''y'' and ''z'': In this case ''y'' and ''z'' are both squares. But then the right triangle with legs \sqrt and b^2 and hypotenuse a^2 also would have integer sides including a square leg (b^2) and a square hypotenuse (a^2), and would have a smaller hypotenuse (a^2 compared to z=a^2+b^2). *''z'' and ''x'': ''z'' is a square. The integer right triangle with legs a and b and hypotenuse \sqrt also would have two sides (a and b) each of which is a square or twice a square, and a smaller hypotenuse (\sqrt compared to . *''y'' and ''x'': ''y'' is a square. The integer right triangle with legs b and \sqrt and hypotenuse a would have two sides (''b'' and ''a'') each of which is a square or twice a square, with a smaller hypotenuse than the original triangle (a compared to z=a^2+b^2). In any of these cases, one Pythagorean triangle with two sides each of which is a square or twice a square has led to a smaller one, which in turn would lead to a smaller one, etc.; since such a sequence cannot go on infinitely, the original premise that such a triangle exists must be wrong. This implies that the equations :r^2 + s^4 = t^4, :r^4 + s^2 =t^4, and :r^4 + s^4 =t^2 cannot have non-trivial solutions, since non-trivial solutions would give Pythagorean triangles with two sides being squares. For other similar proofs by infinite descent for the ''n'' = 4 case of Fermat's Theorem, see the articles by Grant and Perella and Barbara.Barbara, Roy, "Fermat's last theorem in the case ''n'' = 4", ''Mathematical Gazette'' 91, July 2007, 260–262.


See also

*
Vieta jumping In number theory, Vieta jumping, also known as root flipping, is a proof technique. It is most often used for problems in which a relation between two integers is given, along with a statement to prove about its solutions. In particular, it can be ...


References


Further reading

* * {{DEFAULTSORT:Infinite Descent Diophantine equations Mathematical proofs Mathematical terminology