:: wikimiki.org ::

Conjecture

Conjecture

In mathematics, a conjecture is a mathematical statement which has been proposed as a true statement, but which no one has yet been able to prove or disprove. Once a conjecture has been proven, it becomes known as a theorem, and it joins the realm of known mathematical facts. Until that point in time, mathematicians must be extremely careful about their use of a conjecture within logical structures.

Famous conjectures

Until its proof in 1995, the most famous of all conjectures was the mis-named Fermat's last theorem - this conjecture became a true theorem only after its proof. In the process, a special case of the Taniyama-Shimura conjecture, itself a longstanding open problem, was proven; this conjecture has since been completely proven. Other famous conjectures include:
- There are no odd perfect numbers
- Goldbach's conjecture
- The twin prime conjecture
- The Collatz conjecture
- The Riemann hypothesis
- P ≠ NP
- The Poincaré conjecture
- The abc conjecture The Langlands program is a far-reaching web of 'unifying conjectures' that link different subfields of mathematics, e.g. number theory and the representation theory of Lie groups; some of these conjectures have since been proved.

Counterexamples

Unlike the empirical sciences, mathematics is based on provable truth; one cannot apply the adage about "the exception that proves the rule". Although many of the most famous conjectures have been tested across an astounding range of numbers, this is no guarantee against a single counterexample, which would immediately disprove the conjecture. For example, the Collatz conjecture, which concerns whether or not certain sequences of integers terminate, has been tested for all integers up to 1.2 × 10 ¹² (over a million millions); however, it still has only the status of a conjecture -- perhaps there is a counterexample awaiting researchers at 1.2 × 10¹² + 1.

Use of conjectures in conditional proofs

Sometimes a conjecture is called a hypothesis when it is used frequently and repeatedly as an assumption in proofs of other results. For example, the Riemann hypothesis is a conjecture from number theory that (amongst other things) makes predictions about the distribution of prime numbers. Few number theorists doubt that the Riemann hypothesis is true (it is said that Atle Selberg is, and J. E. Littlewood was, sceptical). In anticipation of its eventual proof, some have proceeded to develop further proofs which are contingent on the truth of this conjecture. These are called conditional proofs: the conjectures assumed appear in the hypotheses of the theorem, for the time being. These "proofs", however, would fall apart if it turned out that the hypothesis was false, so there is considerable interest in verifying the truth or falsity of conjectures of this type. There is also something of a question mark over conditional proofs and their 'professional' status in mathematics; are they real work? In the end they must be judged as one possible problem solving technique amongst many: they amount to reducing a question to a question we have not already solved, as opposed to the standard reduction to a question we already know how to solve.

Undecidable conjectures

Not every conjecture ends up being proven true or false. The continuum hypothesis, which tries to ascertain the relative cardinality of certain infinite sets, was eventually shown to be undecidable (or independent) from the generally accepted set of axioms of set theory. It is therefore possible to adopt this statement, or its negation, as a new axiom in a consistent manner (much as we can take Euclid's parallel postulate as either true or false). In this case, if a proof uses this statement, researchers will often look for a new proof that doesn't require the hypothesis (in the same way that it is desirable that statements in Euclidean geometry be proved using only the axioms of neutral geometry, i.e. no parallel postulate.) The one major exception to this in practice is the axiom of choice -- unless studying this axiom in particular, the majority of researchers do not usually worry whether a result requires the axiom of choice.

Usage outside of mathematics

Conjectural means presumed to be real, true, or genuine, mostly based on inconclusive grounds (cf. hypothetical). The term was used by Karl Popper, in the context of scientific philosophy.

Mathematics

Mathematics is often defined as the study of topics such as quantity, structure, space, and change. Another view, held by many mathematicians, is that mathematics is the body of knowledge justified by deductive reasoning, starting from axioms and definitions. Practical mathematics, in nearly every society, is used for such purposes as accounting, measuring land, or predicting astronomical events. Mathematical discovery or research often involves discovering and cataloging patterns, without regard for application. The remarkable fact that the "purest" mathematics often turns out to have practical applications is what Eugene Wigner has called "the unreasonable effectiveness of mathematics." Today, the natural sciences, engineering, economics, and medicine depend heavily on new mathematical discoveries. The word "mathematics" comes from the Greek μάθημα (máthema) meaning "science, knowledge, or learning" and μαθηματικός (mathematikós) meaning "fond of learning". It is often abbreviated maths in Commonwealth English and math in North American English.

History

:Main article: History of mathematics The evolution of mathematics might be seen to be an ever-increasing series of abstractions, or alternatively an expansion of subject matter. The first abstraction was probably that of numbers. The realization that two apples and two oranges do have something in common, namely that they fill the hands of exactly one person, was a breakthrough in human thought. In addition to recognizing how to count concrete objects, prehistoric peoples also recognized how to count abstract quantities, like time -- days, seasons, years. Arithmetic (e.g. addition, subtraction, multiplication and division), naturally followed. Monolithic monuments testify to a knowledge of geometry. Further steps need writing or some other system for recording numbers such as tallies or the knotted strings called khipu used by the Inca empire to store numerical data. Numeral systems have been many and diverse. Historically, the major disciplines within mathematics arose, from the start of recorded history, out of the need to do calculations on taxation and commerce, to understand the relationships among numbers, to measure land, and to predict astronomical events. These needs can be roughly related to the broad subdivision of mathematics, into the studies of quantity, structure, space, and change. Mathematics since has been much extended, and there has been a fruitful interaction between mathematics and science, to the benefit of both. Mathematical discoveries have been made throughout history and continue to be made today.

Inspiration, pure and applied mathematics, and aesthetics

Mathematics arises wherever there are difficult problems that involve quantity, structure, space, or change. At first these were found in commerce, land measurement and later astronomy; nowadays, all sciences suggest problems studied by mathematicians, and many problems arise within mathematics itself. Newton invented infinitesimal calculus and Feynman his Feynman path integral using a combination of reasoning and physical insight, and today's string theory also inspires new mathematics. Some mathematics is only relevant in the area that inspired it, and is applied to solve further problems in that area. But often mathematics inspired by one area proves useful in many areas, and joins the general stock of mathematical concepts. As in most areas of study, the explosion of knowledge in the scientific age has led to specialization in mathematics. One major distinction is between pure mathematics and applied mathematics. Within applied mathematics, two major areas have split off and become disciplines in their own right, statistics and computer science. Many mathematicians talk about the elegance of mathematics, its intrinsic aesthetics and inner beauty. Simplicity and generality are valued. There is beauty also in a clever proof, such as Euclid's proof that there are infinitely many prime numbers, and in a numerical method that speeds calculation, such as the fast Fourier transform. G. H. Hardy in "A Mathematicians Apology" expressed the belief that these esthetic considerations are, in themselves, sufficient to justify the study of pure mathematics. Main article: Mathematical beauty.

Notation, language, and rigor

Mathematical writing is not easily accessible to the layperson. A Brief History of Time, Stephen Hawking's 1988 bestseller, contained a single mathematical equation. This was the author's compromise with the publisher's advice, that each equation would halve the sales. The reasons for the inaccessibility even of carefully-expressed mathematics can be partially explained. Contemporary mathematicians strive to be as clear as possible in the things they say and especially in the things they write (this they have in common with lawyers). They refer to rigor. To accomplish rigor, mathematicians have extended natural language. There is precisely-defined vocabulary for referring to mathematical objects, and stating certain common relations. There is an accompanying mathematical notation which, like musical notation, has a definite content and also has a strict grammar (under the influence of computer science, more often now called syntax). Some of the terms used in mathematics are also common outside mathematics, such as ring, group and category; but are not such that one can infer the meanings. Some are specific to mathematics, such as homotopy and Hilbert space. It was said that Henri Poincaré was only elected to the Académie Française so that he could tell them how to define automorphe in their dictionary. Rigor is fundamentally a matter of mathematical proof. Mathematicians want their theorems to follow mechanically from axioms by means of formal axiomatic reasoning. This is to avoid mistaken 'theorems', based on fallible intuitions; of which plenty of examples have occurred in the history of the subject (for example, in mathematical analysis). Axioms in traditional thought were 'self-evident truths', but that conception turns out not to be workable in pushing the mathematical boundaries. At a formal level, an axiom is just a string of symbols, which has an intrinsic meaning only in the context of all derivable formulas of an axiomatic system. It was the goal of Hilbert's program to put all of mathematics on a firm axiomatic basis, but according to Gödel's incompleteness theorem every (strong enough) axiom system has undecidable formulas; and so a final axiomatization of mathematics is unavailable. Nonetheless mathematics is often imagined to be (as far as its formal content) nothing but set theory in some axiomatization, in the sense that every mathematical statement or proof could be cast into formulas within set theory.

Is mathematics a science?

Carl Friedrich Gauss referred to mathematics as the Queen of the Sciences. The mathematician-physicist Leon M. Lederman has quipped: "The physicists defer only to mathematicians, and the mathematicians defer only to God (though you may be hard pressed to find a mathematician that modest)." If one considers science to be strictly about the physical world, then mathematics, or at least pure mathematics, is not a science. An alternative view is that certain scientific fields (such as theoretical physics) are mathematics with axioms that are intended to correspond to reality. In fact, the theoretical physicist, J. M. Ziman, proposed that science is public knowledge and thus includes mathematics. [http://info.med.yale.edu/therarad/summers/ziman.htm] In any case, mathematics shares much in common with many fields in the physical sciences, notably the exploration of the logical consequences of assumptions. Intuition and experimentation also play a role in the formulation of conjectures in both mathematics and the (other) sciences.

Overview of fields of mathematics

As noted above, the major disciplines within mathematics first arose out of the need to do calculations in commerce, to understand the relationships between numbers, to measure land, and to predict astronomical events. These four needs can be roughly related to the broad subdivision of mathematics into the study of quantity, structure, space, and change (i.e. arithmetic, algebra, geometry and analysis). In addition to these main concerns, there are also subdivisions dedicated to exploring links from the heart of mathematics to other fields: to logic, to set theory (foundations) and to the empirical mathematics of the various sciences (applied mathematics). The study of quantity starts with numbers, first the familiar natural numbers and integers and their arithmetical operations, which are characterized in arithmetic. The deeper properties of whole numbers are studied in number theory. The study of structure began with investigations of Pythagorean triples. Neolithic monuments on the British Isles are constructed using Pythagorean triples. Eventually, this led to the invention of more abstract numbers, such as the square root of two. The deeper structural properties of numbers are studied in abstract algebra and the investigation of groups, rings, fields and other abstract number systems. Included is the important concept of vectors, generalized to vector spaces and studied in linear algebra. The study of vectors combines three of the fundamental areas of mathematics, quantity, structure, and space. The study of space originates with geometry, beginning with Euclidean geometry. Trigonometry combines space and number. The modern study of space generalizes these ideas to include higher-dimensional geometry, non-Euclidean geometries (which play a central role in general relativity) and topology. Quantity and space both play a role in analytic geometry, differential geometry, and algebraic geometry. Within differential geometry are the concepts of fiber bundles, calculus on manifolds. Within algebraic geometry is the description of geometric objects as solution sets of polynomal equations, combining the concepts of quantity and space, and also the study of topological groups, which combine structure and space. Lie groups are used to study space, structure, and change. Topology in all its many ramifications may be the greatest growth area in 20th century mathematics. Understanding and describing change is a common theme in the natural sciences, and calculus was developed as a most useful tool. The central concept used to describe a changing quantity is that of a function. Many problems lead quite naturally to relations between a quantity and its rate of change, and the methods of differential equations. The numbers used to represent continuous quantities are the real numbers, and the detailed study of their properties and the properties of real-valued functions is known as real analysis. These have been generalized, with the inclusion of the square root of negative one, to the complex numbers, which are studied in complex analysis. Functional analysis focuses attention on (typically infinite-dimensional) spaces of functions. One of many applications of functional analysis is quantum mechanics. Many phenomena in nature can be described by dynamical systems; chaos theory makes precise the ways in which many of these systems exhibit unpredictable yet still deterministic behavior. Beyond quantity, structure, space, and change are areas of pure mathematics that can be approached only by deductive reasoning. In order to clarify the foundations of mathematics, the fields of mathematical logic and set theory were developed. Mathematical logic, which divides into recursion theory, model theory, and proof theory, is now closely linked to computer science. When electronic computers were first conceived, several essential theoretical concepts in computer science were shaped by mathematicians, leading to the fields of computability theory, computational complexity theory, and information theory. Many of those topics are now investigated in theoretical computer science. Discrete mathematics is the common name for the fields of mathematics most generally useful in computer science. An important field in applied mathematics is statistics, which uses probability theory as a tool and allows the description, analysis, and prediction of phenomena where chance plays a part. It is used in all the sciences. Numerical analysis investigates methods for using computers to efficiently solve a broad range of mathematical problems that are typically beyond human capacity, and taking rounding errors or other sources of error into account to obtain credible answers.

Major themes in mathematics

An alphabetical and subclassified list of mathematical topics is available. The following list of themes and links gives just one possible view. For a fuller treatment, see Areas of mathematics or the list of lists of mathematical topics.

Change

:Ways to express and handle change in mathematical functions, and changes between numbers. : :Arithmetic – Calculus – Vector calculus – Analysis – Differential equations – Dynamical systems – Chaos theory – List of functions

Foundations and methods

:Approaches to understanding the nature of mathematics. :philosophy of mathematics – mathematical intuitionism – mathematical constructivism – foundations of mathematics – set theory – symbolic logic – model theory – category theory – Logic – reverse mathematics – table of mathematical symbols

Discrete mathematics

:Discrete mathematics involves techniques that apply to objects that can only take on specific, separated values. : :Combinatorics – Naive set theory – Theory of computation– Cryptography – Graph theory

Applied mathematics

:Applied mathematics uses the full knowledge of mathematics to solve real-world problems. :Mathematical physics – Mechanics – Fluid mechanics – Numerical analysis – Optimization – Probability – Statistics – Mathematical economics – Financial mathematics – Game theory – Mathematical biology – Cryptography – Information theory

Important theorems

:These theorems have interested mathematicians and non-mathematicians alike. :See list of theorems for more :Pythagorean theorem – Fermat's last theorem – Gödel's incompleteness theorems – Fundamental theorem of arithmetic – Fundamental theorem of algebra – Fundamental theorem of calculus – Cantor's diagonal argument – Four color theorem – Zorn's lemma – Euler's identity – classification theorems of surfaces – Gauss-Bonnet theorem – Quadratic reciprocity – Riemann-Roch theorem.

Important conjectures

See list of conjectures for more :These are some of the major unsolved problems in mathematics. :Goldbach's conjecture – Twin Prime Conjecture – Riemann hypothesis – Poincaré conjecture – Collatz conjecture – P=NP? – open Hilbert problems.

History and the world of mathematicians

Mathematics and other fields

:Mathematics and architecture – Mathematics and education – Mathematics of musical scales

Common misconceptions

Mathematics is not a closed intellectual system, in which everything has already been worked out. There is no shortage of open problems. Pseudomathematics is a form of mathematics-like activity undertaken outside academia, and occasionally by mathematicians themselves. It often consists of determined attacks on famous questions, consisting of proof-attempts made in an isolated way (that is, long papers not supported by previously published theory). The relationship to generally-accepted mathematics is similar to that between pseudoscience and real science. The misconceptions involved are normally based on:
- misunderstanding of the implications of mathematical rigour;
- attempts to circumvent the usual criteria for publication of mathematical papers in a learned journal after peer review, with assumptions of bias;
- lack of familiarity with, and therefore underestimation of, the existing literature. The case of Kurt Heegner's work shows that the mathematical establishment is neither infallible, nor unwilling to admit error in assessing 'amateur' work. And like astronomy, mathematics owes much to amateur contributors such as Fermat and Mersenne. Mathematics is not accountancy. Although arithmetic computation is crucial to accountants, their main concern is to verify that computations are correct through a system of doublechecks. Advances in abstract mathematics are mostly irrelevant to the efficiency of concrete bookkeeping, but the use of computers clearly does matter. Mathematics is not numerology. Numerology uses modular arithmetic to reduce names and dates down to numbers, but assigns emotions or traits to these numbers intuitively or on the basis of traditions. Mathematical concepts and theorems need not correspond to anything in the physical world. In the case of geometry, for example, it is not relevant to mathematics to know whether points and lines exist in any physical sense, as geometry starts from axioms and postulates about abstract entities called "points" and "lines" that we feed into the system. While these axioms are derived from our perceptions and experience, they are not dependent on them. And yet, mathematics is extremely useful for solving real-world problems. It is this fact that led Eugene Wigner to write an essay on The Unreasonable Effectiveness of Mathematics in the Natural Sciences. Mathematics is not about unrestricted theorem proving, any more than literature is about the construction of grammatically correct sentences. However, theorems are elements of formal theories, and in some cases computers can generate proofs of these theorems more or less automatically, by means of automated theorem provers. These techniques have proven useful in formal verification of programs and hardware designs. However, they are unlikely to generate (in the near term, at least) mathematics with any widely recognized aesthetic value.

Bibliography

- Benson, Donald C., The Moment Of Proof: Mathematical Epiphanies (1999).
- Courant, R. and H. Robbins, What Is Mathematics? (1941);
- Davis, Philip J. and Hersh, Reuben, The Mathematical Experience. Birkhäuser, Boston, Mass., 1980. A gentle introduction to the world of mathematics.
- Boyer, Carl B., History of Mathematics, Wiley, 2nd edition 1998 available, 1st edition 1968 . A concise history of mathematics from the Concept of Number to contemporary Mathematics.
- Gullberg, Jan, Mathematics--From the Birth of Numbers. W.W. Norton, 1996. An encyclopedic overview of mathematics presented in clear, simple language.
- Hazewinkel, Michiel (ed.), Encyclopaedia of Mathematics. Kluwer Academic Publishers 2000. A translated and expanded version of a Soviet math encyclopedia, in ten (expensive) volumes, the most complete and authoritative work available. Also in paperback and on CD-ROM.
- Kline, M., Mathematical Thought from Ancient to Modern Times (1973).
- Pappas, Theoni, The Joy Of Mathematics (1989).

External links

- [http://www.cut-the-knot.org/ Interactive Mathematics Miscellany and Puzzles] — A collection of articles on various math topics, with interactive Java illustrations at cut-the-knot
- Rusin, Dave: [http://www.math-atlas.org/ The Mathematical Atlas]. A guided tour through the various branches of modern mathematics.
- Stefanov, Alexandre: [http://us.geocities.com/alex_stef/mylist.html Textbooks in Mathematics]. A list of free online textbooks and lecture notes in mathematics.
- Weisstein, Eric et al.: [http://www.mathworld.com/ MathWorld: World of Mathematics]. An online encyclopedia of mathematics.
- Polyanin, Andrei: [http://eqworld.ipmnet.ru/ EqWorld: The World of Mathematical Equations]. An online resource focusing on algebraic, ordinary differential, partial differential (mathematical physics), integral, and other mathematical equations.
- A mathematical thesaurus maintained by the [http://nrich.maths.org/ NRICH] project at the University of Cambridge (UK), [http://thesaurus.maths.org/ Connecting Mathematics]
- [http://planetmath.org/ Planet Math]. An online math encyclopedia under construction, focusing on modern mathematics. Uses the GFDL, allowing article exchange with Wikipedia. Uses TeX markup.
- [http://www.mathforge.net/ Mathforge]. A news-blog with topics ranging from popular mathematics to popular physics to computer science and education.
- [http://www.youngmath.net/concerns Young Mathematicians Network (YMN)]. A math-blog "Serving the Community of Young Mathematicians". Topics include: Math News, Grad and Undergrad Life, Job Search, Career, Work & Family, Teaching, Research, Misc...
- [http://metamath.org/ Metamath]. A site and a language, that formalize math from its foundations.
- [http://world.std.com/~reinhold/dir/mathmovies.html Math in the Movies]. A guide to major motion pictures with scenes of real mathematics
- [http://math.cofc.edu/faculty/kasman/MATHFICT/default.html Mathematics in fiction]. Links to works of fiction that refer to mathematics or mathematicians.
- [http://www.mathhelpforum.com/math-help Math Help Forum]. A forum, for math help, math discussion and debate.
- [http://www.sosmath.com/CBB S.O.S. Mathematics Cyberboard] a math help forum which incorporates a LaTeX extension, making it easier for members to write and display math formulae.
- [http://www-history.mcs.st-and.ac.uk/~history/ Mathematician Bibliography]. Extensive history and quotes from all famous mathematicians.
- [http://www.physicsmathforums.com/ Physics Math Forums]
- Category:School subjects fiu-vro:Matõmaatiga zh-min-nan:Sò·-ha̍k ko:수학 ms:Matematik ja:数学 simple:Mathematics th:คณิตศาสตร์

Mathematical proof

In mathematics, a proof is a demonstration that, given certain axioms, some statement of interest is necessarily true. Proofs employ logic but usually include some amount of natural language which of course admits some ambiguity. In fact, the vast majority of proofs in written mathematics can be considered as applications of informal logic. In the context of proof theory, where purely formal proofs are considered, such not entirely formal demonstrations in mathematics are often called "social proofs". The distinction has led to much examination of current and historical mathematical practice, quasi-empiricism in mathematics, and so-called folk mathematics (in both senses of that term). The philosophy of mathematics is concerned with the role of language and logic in proofs, and mathematics as a language. Regardless of one's attitude to formalism, the result that is proved to be true is a theorem; in a completely formal proof it would be the final line, and the complete proof shows how it follows from the axioms alone. Once a theorem is proved, it can be used as the basis to prove further statements. The so-called foundations of mathematics are those statements one cannot, or need not, prove. These were once the primary study of philosophers of mathematics. Today focus is more on practice, i.e. acceptable techniques. Some common proof techniques are:
- Direct proof: where the conclusion is established by logically combining the axioms, definitions and earlier theorems
- Proof by induction: where a base case is proved, and an induction rule used to prove an (often infinite) series of other cases
- Proof by contradiction (also known as reductio ad absurdum): where it is shown that if some statement were false, a logical contradiction occurs, hence the statement must be true.
- Proof by construction: constructing a concrete example with a property to show that something having that property exists.
- Proof by exhaustion: where the conclusion is established by dividing it into a finite number of cases and proving each one separately A probabilistic proof should mean a proof in which an example is shown to exist by methods of probability theory - not an argument that a theorem is 'probably' true. The latter type of reasoning can be called a 'plausibility argument'; in the case of the Collatz conjecture it is clear how far that is from a genuine proof. Probabilistic proof is one of many ways to show existence theorems, other than proof by construction. A combinatorial proof establishes the equivalence of different expressions by showing that they count the same object in different ways. Usually a one-to-one correspondence is used to show that the two interpretations give the same result. If we are trying to prove, for example, "Some X satisfies f(X)", an existence or nonconstructive proof will prove that there is a X that satisfies f(X), but does not explain how such an X will be obtained. A constructive proof, conversely, will do so. A statement which is thought to be true but has not been proven yet is known as a conjecture. Sometimes it is possible to prove that a certain statement cannot possibly be proven from a given set of axioms; see for instance the continuum hypothesis. In most axiom systems, there are statements which can neither be proven nor disproven; see Gödel's incompleteness theorem.

Theorem

A theorem is a proposition that has been or is to be proved on the basis of explicit assumptions. Proving theorems is a central activity of mathematicians. Note that "theorem" is distinct from "theory". A theorem generally has a set-up – a number of conditions, which may be listed in the theorem or described beforehand. Then it has a conclusion – a mathematical statement which is true under the given set up. The proof, though necessary to the statement's classification as a theorem, is not considered part of the theorem. In general, a mathematical statement must be non-trivial to be called a theorem. Less important statements are called:
- lemma: a statement that forms part of the proof of a larger theorem. The distinction between theorems and lemmas is rather arbitrary, since one mathematician's major result is another's minor claim. Gauss' lemma and Zorn's lemma, for example, are interesting enough per se that some authors present the nominal lemma without going on to use it in the proof of any theorem.
- corollary: a proposition that follows with little or no proof from one already proven. A proposition B is a corollary of a proposition or theorem A if B can be deduced quickly and easily from A.
- proposition: a result not associated with any particular theorem.
- claim: a very minor, but necessary or interesting, result, which may be part of the proof of another statement. Despite the name, claims are proven.
- remark: similar to claim. Usually presented without proof, which is assumed to be obvious. A mathematical statement which is believed to be true but has not been proven is known as a conjecture. As noted above, a theorem requires some sort of logical framework. This will consist of a basic set of axioms (see axiomatic system), as well as a process of inference, which allows one to derive new theorems from axioms and other theorems that have been derived earlier. In propositional logic, any proven statement is called a theorem. Informally speaking, most such theorems are not of any particular interest; what makes a mathematical result worth the title 'theorem' is not really an easy matter.

Fermat's last theorem

Fermat's last theorem (sometimes abbreviated as FLT and also called Fermat's great theorem) is one of the most famous theorems in the history of mathematics. It states that: :There are no non-zero integers x, y, and z such that

x^n + y^n = z^n

in which n is an integer greater than 2. The 17th-century mathematician Pierre de Fermat wrote about this in 1637 in his copy of Claude-Gaspar Bachet's translation of the famous Arithmetica of Diophantus: "I have a truly marvellous proof of this proposition which this margin is too narrow to contain." (Original Latin: "Cuius rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet.") However, no correct proof was found for 357 years. This statement is significant because all the other theorems proposed by Fermat were settled, either by proofs he supplied, or by rigorous proofs found afterwards. Mathematicians were long baffled, for they were unable either to prove or to disprove it. The theorem was not the last that Fermat conjectured, but the last to be proved. The theorem is generally thought to be the mathematical result that has provoked the largest number of incorrect proofs, perhaps because it is easy to understand.

Mathematical context

Fermat's last theorem is a generalization of the Diophantine equation a² + b² = c², which is linked to the Pythagorean theorem. Ancient Chinese, Greeks and Babylonians knew that this equation has integer solutions, such as (3,4,5) (3² + 4² = 5²) or (5,12,13). These solutions are known as Pythagorean triples, and there exist an infinite number of them (even excluding trivial solutions for which a, b and c have a common divisor). According to Fermat's last theorem, no such solution exists when the exponent 2 is replaced by a larger integer. While the theorem itself has no known direct use (i.e., it has not been used to prove any other theorem), it has been shown to be connected to many other topics in mathematics, and is not merely an unimportant mathematical curiosity. Moreover, the search for a proof has initiated research about many important mathematical topics.

Early history

The theorem needs only to be proven for n=4 and in the cases where n is a prime number. For various special exponents n, the theorem had been proven over the years, but the general case remained elusive. Fermat himself proved the case n=4, while Euler proved the theorem for n=3. The case n=5 was proved by Dirichlet and Legendre in 1825, and the case n=7 by Gabriel Lamé in 1839. In 1983 Gerd Faltings proved the Mordell conjecture, which implies that for any n > 2, there are at most finitely many coprime integers a, b and c with aⁿ + bⁿ = cⁿ.

The proof

Using sophisticated tools from algebraic geometry (in particular elliptic curves and modular forms), Galois theory and Hecke algebras, the English mathematician Andrew Wiles, from Princeton University, with help from his former student Richard Taylor, devised a proof of Fermat's last theorem that was published in 1995 in the journal Annals of Mathematics. In 1986, Ken Ribet had proved Gerhard Frey's epsilon conjecture that every counterexample aⁿ + bⁿ = cⁿ to Fermat's last theorem would yield an elliptic curve defined as:

y^2 = x(x - a^n)(x + b^n),

which would provide a counterexample to the Taniyama-Shimura conjecture. This latter conjecture proposes a deep connection between elliptic curves and modular forms. Andrew Wiles and Richard Taylor were able to establish a special case of the Taniyama-Shimura conjecture sufficient to exclude such counterexamples arising from Fermat's last theorem. The story of the proof is almost as remarkable as the mystery of the theorem itself. Wiles spent seven years working out nearly all the details by himself and with utter secrecy (except for a final review stage for which he enlisted the help of his Princeton colleague, Nick Katz). When he announced his proof over the course of three lectures delivered at Cambridge University on June 21-23 1993, he amazed his audience with the number of ideas and constructions used in his proof. Unfortunately, upon closer inspection a serious error was discovered: it seemed to lead to the breakdown of this original proof. Wiles and Taylor then spent about a year trying to revive the proof. In September 1994, they were able to resurrect the proof with some different, discarded techniques that Wiles had used in his earlier attempts.

Did Fermat really have a proof?

This is the note that Fermat wrote in the margin of Arithmetica:

Cubum autem in duos cubos, aut quadrato-quadratum in duos quadrato-quadratos,
et generaliter nullam in infinitum ultra quadratum potestatem in duos eiusdem
nominis fas est dividere cuius rei demonstrationem mirabilem sane detexi.
Hanc marginis exigitas non caperet.

(It is impossible to separate a cube into two cubes, or a fourth power into two
fourth powers, or in general, any power higher than the second into two like
powers. I have discovered a truly marvelous proof of this, which this margin
is too narrow to contain.)

There is considerable doubt over whether Fermat's claim to have "a truly marvellous proof" was correct. The length of Wiles's proof is about 200 pages and is beyond the understanding of most mathematicians today. It is quite possible that there is a proof that is both essentially shorter, and more elementary in its methods; initial proofs of major results are typically not the most direct. Math institutions still receive many papers, some say in the thousands, claiming to have found such a proof and these are often subject to media attention. The methods used by Wiles were unknown when Fermat was writing, and most believe it is unlikely that Fermat managed to derive all the necessary mathematics to demonstrate a solution. In the words of Andrew Wiles, "it's impossible; this is a 20th century proof". Alternatives are that there is a simpler proof that all other mathematicians up until this point have missed, or that Fermat was mistaken. A plausible faulty proof that might have been accessible to Fermat has been suggested. It is based on the mistaken assumption that unique factorization works in all rings of integral elements of algebraic number fields. This is an acceptable explanation to many experts in number theory, on the grounds that subsequent mathematicians of stature working in the field followed the same path. The fact that Fermat never published an attempted proof, or even publicly announced that he had one, does suggest that he may have had later thoughts, and simply neglected to cross out his private marginal note. In addition, later in his life, Fermat published a proof for the case :

a^4 + b^4 = c^4

. If he really had come up with a proof for the general theorem, it is perhaps less likely that he would have published a proof for a special case, unless this special case could be used to prove the general theorem. On the other hand, the academic conventions of his time were not those that applied from the middle of the eighteenth century, and this argument cannot be taken as definitive. Academic publishing was only then just starting to develop, and mathematicians commonly withheld mathematical techniques to maintain their superiority to other mathematicians. Fermat did not publish proofs for the vast majority of his theorems, including those theorems for which mathematical historians believe he actually had a proof.

Trivia

In "The Royale", an episode of Star Trek: The Next Generation, Captain Picard states that the theorem had gone unsolved for 800 years. Wiles' proof was released five years after the particular episode aired. This was subsequently mentioned in a Star Trek: Deep Space Nine episode called "Facets" during June 1995 in which Jadzia Dax comments that one of her previous hosts, Tobin Dax, had "the most original approach to the proof since Wiles over 300 years ago." [http://www.twiztv.com/scripts/ds9/season3/ds9-325.txt] This reference was generally understood by fans to be a subtle correction for "The Royale". Fermat's last theorem appears on the blackboard as a homework assignment in the classroom scene of the 2000 movie Bedazzled. For those who are in the know, this would truly be a math homework assignment assigned by the Devil. A sum, proved impossible by the theorem, appears in an episode of the Simpsons, "Treehouse of Horror VI". In the three-dimensional world in "Homer³", the equation 1782¹² + 1841¹² = 1922¹² is visible, just as the dimension begins to collapse. The joke is that the twelfth root of the sum does evaluate to 1922 due to rounding errors when plugged into most handheld calculators. The solving of Fermat's last theorem was also the subject of an Off-Broadway musical titled Fermat's Last Tango that opened at the York Theatre at St. Peter's Church on December 6, 2000 and closed on December 31. Joanne Sydney Lessner and Joshua Rosenblum wrote the book and lyrics to the show, and Rosenblum also composed the music; Mel Marvin directed. In the cast were Gilles Chiasson, Edwardyne Cowan, Mitchell Kantor, Jonathan Rabb, Chris Thompson, Christianne Tisdale, and Carrie Wilshusen. The show stuck closely to the historical details of the Theorem and its proof, though the names of both Wiles and his wife were changed (to Daniel and Anna Keane). In Tom Stoppard's play Arcadia, Septimus Hodge poses the problem of proving Fermat's last theorem to the precocious Thomasina Coverly (who is perhaps a mathematical prodigy), in an attempt to keep her busy. Thomasina's (perhaps perceptive) response is simple — that Fermat had no proof, and it was a joke to drive posterity mad. Arthur Porges' short story, "The Devil and Simon Flagg", features a mathematician who bargains with the Devil that the latter cannot produce a proof of Fermat's last theorem within twenty-four hours. The story was first published in 1954 in Magazine of Fantasy and Science Fiction.

Notes

# There are infinitely many positive natural numbers a, b, and c such that

a^n + b^n = c^ \;

in which n is any natural number. # If n is not an odd prime number, nor 4, it has factors that are one of those. Let any such factor be p, and let m be n/p. Now we can express the equation as

(a^m)^p + (b^m)^p = (c^m)^p

. If we can prove the case with exponent p, exponent n is simply a subset of that case.

External links and references

- Nova [http://www.pbs.org/wgbh/nova/transcripts/2414proof.html "The Proof" Transcript] PBS Airdate: October 28, 1997
- Wiles, Andrew (1995). [http://math.stanford.edu/~lekheng/flt/wiles.pdf Modular elliptic curves and Fermat's last theorem], Annals of Mathematics (141) (3), 443-551 ([http://www.lacim.uqam.ca/~plouffe/OEIS/archive_in_pdf/001_flt.pdf alternative link]).
- Taylor, Richard & Wiles, Andrew (1995). [http://www.math.harvard.edu/~rtaylor/hecke.ps Ring theoretic properties of certain Hecke algebras], Annals of Mathematics (141) (3), 553-572.
- Faltings, Gerd (1995). [http://www.ams.org/notices/199507/faltings.pdf The Proof of Fermat's last theorem by R. Taylor and A. Wiles], Notices of the AMS (42) (7), 743-746.
- Daney, Charles (2003). [http://cgd.best.vwh.net/home/flt/flt01.htm The Mathematics of Fermat's last theorem]. Retrieved Aug. 5, 2004.
- O'Connor, J. J. & and Robertson, E. F. (1996). [http://www-gap.dcs.st-and.ac.uk/~history/HistTopics/Fermat%27s_last_theorem.html Fermat's last theorem. The history of the problem]. Retrieved Aug. 5, 2004.
- Shay, David (2003). [http://fermat.workjoke.com/ Fermat's last theorem. The story, the history and the mystery]. Retrieved Aug. 5, 2004.
- Freeman, Larry (2005). [http://www.fermatslasttheorem.blogspot.com Fermat's Last Theorem Blog]. A blog that covers the history of Fermat's Last Theorem from Pierre Fermat to Andrew Wiles.
- Kisby, Adam William (2004). [http://ne-plus-ultra.net/index.php?option=com_content&task=view&id=112&Itemid=26/ Fermat's Last Theorem Revisited: A Marginal Proof in Ten Steps]. Parody.

Bibliography and further reading

- Singh, Simon (hardcover, 1998). Fermat's Enigma. Bantam Books. ISBN 0802713319 (previously published under the title Fermat's Last Theorem).
- Aczel, Amir D. (hardcover, 1996) Fermat's Last Theorem: Unlocking the Secret of an Ancient Mathematical Problem. Four Walls Eight Windows. ISBN 1568580770.
- Bell, Eric T. (1961) The Last Problem. New-York: Simon and Schuster. ISBN 0883854511 (edition of 1998).
- Benson, Donald C. (paperback, 1999). The Moment of Proof: Mathematical Epiphanies. Oxford University Press. ISBN 0195139194. Category:Number theory Category:Mathematical theorems ko:페르마의 마지막 정리 ja:フェルマーの最終定理 th:ทฤษฎีบทสุดท้ายของแฟร์มาต์

Taniyama-Shimura theorem

The Taniyama–Shimura theorem establishes an important connection between elliptic curves, which are objects from algebraic geometry, and modular forms, which are certain periodic holomorphic functions investigated in number theory. Despite the name, which is a carry over from when it was the Taniyama–Shimura conjecture, the theorem is the work of Andrew Wiles, Christophe Breuil, Brian Conrad, Fred Diamond, and Richard Taylor. If p is a prime number and E is an elliptic curve over Q (the field of rational numbers), we can reduce the equation defining E modulo p; for all but finitely many values of p we will get an elliptic curve over the finite field F_p, with n_p elements, say. One then considers the sequence :a_p = n_p − p, which is an important invariant of the elliptic curve E. Every modular form also gives rise to a sequence of numbers, by Fourier transform. An elliptic curve whose sequence agrees with that from a modular form is called modular. The Taniyama–Shimura theorem states: :"All elliptic curves over Q are modular." This theorem was first conjectured by Yutaka Taniyama in September 1955. With Goro Shimura he improved its rigor until 1957. Taniyama died in 1958. In the 1960s it became associated with the Langlands program of unifying conjectures in mathematics, and was a key component thereof. The conjecture was picked up and promoted by André Weil in the 1970s, and Weil's name was associated with it in some quarters. Despite the clear interest, the depth of the question was not appreciated until later developments. It attracted considerable interest in the 1980s when Gerhard Frey suggested that the Taniyama–Shimura conjecture (as it was then called) implies Fermat's last theorem. He did this by attempting to show that any counterexample to Fermat's last theorem would give rise to a non-modular elliptic curve. Ken Ribet later proved this result. In 1995, Andrew Wiles and Richard Taylor proved a special case of the Taniyama–Shimura theorem (the case of semistable elliptic curves) which was strong enough to yield a proof of Fermat's Last Theorem. The full Taniyama–Shimura theorem was finally proved in 1999 by Breuil, Conrad, Diamond, and Taylor who, building on Wiles' work, incrementally chipped away at the remaining cases until the full result was proved. Several theorems in number theory similar to Fermat's last theorem follow from the Taniyama–Shimura theorem. For example: no cube can be written as a sum of two coprime n-th powers, n ≥ 3. (The case n = 3 was already known by Euler.) In March 1996 Wiles shared the Wolf Prize with Robert Langlands. Although neither of them had originated or finished the proof of the full theorem that had enabled their achievements, they were recognized as having had the decisive influences that led to its proof.

References

- Henri Darmon: [http://www.ams.org/notices/199911/comm-darmon.pdf A Proof of the Full Shimura-Taniyama-Weil Conjecture Is Announced], Notices of the American Mathematical Society, Vol. 46 (1999), No. 11. Contains a gentle introduction to the theorem and an outline of the proof.
- Brian Conrad, Fred Diamond, Richard Taylor: [http://abel.math.harvard.edu/~rtaylor/cdt.dvi Modularity of certain potentially Barsotti-Tate Galois representations], Journal of the American Mathematical Society 12 (1999), pp. 521–567. Contains the proof. Category:Algebraic curves Category:Riemann surfaces Category:Modular forms Category:Theorems ja:谷山・志村定理

Perfect number

In mathematics, a perfect number is defined as an integer which is the sum of its proper positive divisors, excluding itself. Six (6) is the first perfect number, because 1, 2 and 3 are its proper positive divisors and 1 + 2 + 3 = 6. The next perfect number is 28 = 1 + 2 + 4 + 7 + 14. The next perfect numbers are 496 and 8128 . These first four perfect numbers were the only ones known to the ancient Greeks.

Even perfect numbers

Euclid discovered that the first four perfect numbers are generated by the formula 2ⁿ⁻¹(2ⁿ − 1): :for n = 2: 2¹(2² − 1) = 6 :for n = 3: 2²(2³ − 1) = 28 :for n = 5: 2⁴(2⁵ − 1) = 496 :for n = 7: 2⁶(2⁷ − 1) = 8128 Noticing that 2ⁿ − 1 is a prime number in each instance, Euclid proved that the formula 2ⁿ⁻¹(2ⁿ − 1) gives an even perfect number whenever 2ⁿ − 1 is prime. Ancient mathematicians made many assumptions about perfect numbers based on the four they knew. Most of the assumptions were wrong. One of these assumptions was that since 2, 3, 5, and 7 are precisely the first four primes, the fifth perfect number would be obtained when n = 11, the fifth prime. However, 2¹¹ − 1 = 2047 = 23 · 89 is not prime and therefore n = 11 does not yield a perfect number. Two other wrong assumptions were:
- The fifth perfect number would have five digits since the first four had 1, 2, 3, and 4 digits respectively.
- The perfect numbers would alternately end in 6 or 8. The fifth perfect number (

33550336=2^(2^-1)

) has 8 digits, thus debunking the first assumption. For the second assumption, the fifth perfect number indeed ends with a 6. However, the sixth (8 589 869 056) also ends in a 6. It has been shown that the last digit of any even perfect number must be 6 or 8. In order for

2^n-1

to be prime, it is necessary that

n

should be prime. Prime numbers of the form 2ⁿ − 1 are known as Mersenne primes, after the seventeenth-century monk Marin Mersenne, who studied number theory and perfect numbers. Two millennia after Euclid, Euler proved that the formula 2ⁿ⁻¹(2ⁿ − 1) will yield all the even perfect numbers. Thus, every Mersenne prime will yield a distinct even perfect number—there is a concrete one-to-one association between even perfect numbers and Mersenne primes. This result is often referred to as the "Euclid-Euler Theorem." Only finitely many Mersenne primes are presently known, and it is unknown whether there are infinitely many of them. Thus it also remains uncertain whether there are infinitely many even perfect numbers. Every even perfect number is a triangular number. Since any even perfect number has the form 2ⁿ⁻¹(2ⁿ − 1), it is the sum of all natural numbers up to 2ⁿ − 1. This follows from the general formula stating that the sum of the first m positive integers equals (m² + m)/2. Furthermore, any even perfect number except the first one is the sum of the first 2^(n−1)/2 odd cubes: :

6 = 2^1(2^2-1) = 1+2+3, \,

28 = 2^2(2^3-1) = 1+2+3+4+5+6+7 = 1^3+3^3, \,

496 = 2^4(2^5-1) = 1+2+3+\cdots+29+30+31 = 1^3+3^3+5^3+7^3, \,

8128 = 2^6(2^7-1) = 1+2+3+\cdots+125+126+127 = 1^3+3^3+5^3+7^3+9^3+11^3+13^3+15^3. \,

Another interesting fact is that the reciprocals of the factors of a perfect number add up to 2:
- For 6, we have

1/6 + 1/3 + 1/2+ 1/1 = 2

;
- For 28, we have

1/28 + 1/14 + 1/7 + 1/4 + 1/2 + 1/1 = 2

, etc.

Odd perfect numbers

It is unknown whether there are any odd perfect numbers. Various results have been obtained, but none that have helped to locate one or otherwise resolve the question of their existence. Recently, Carl Pomerance and Joshua Zelinsky have both presented heuristics which strongly suggest that no odd perfect numbers exist. Any odd perfect number N must satisfy the following conditions:
- N is of the form ::

N=q^ p_1^ \ldots p_k^,

:where q, p₁, …, p_k are distinct primes and q ≡ α ≡ 1 (mod 4) (Euler).
- N is bigger than 10³⁰⁰.
- N is of the form 4j + 1 (A. Stern, 1896)
- N has at least 8 distinct prime factors (and at least 11 if it is not divisible by 3) (Peter Hagis).
- N has at least 75 prime factors in total, including repetitions (Kevin Hare, 2005).
- N has at least one prime factor greater than 10⁷, two prime factors greater than 10⁴, and three prime factors greater than 100.
- N is less than

2^

where n=k+1 is the number of distinct prime factors.
- N is of the form 12j + 1 or 36j + 9 (Jacques Touchard). (An elementary proof was discovered by Judy A. Holdener)

References

- Kevin Hare, New techniques for bounds on the total number of prime factors of an odd perfect number. Preprint, 2005. Available from [http://www.math.uwaterloo.ca/~kghare/Preprints/ his webpage].

External links

- David Moews: [http://djm.cc/amicable.html Perfect, amicable and sociable numbers]
- [http://www-history.mcs.st-andrews.ac.uk/HistTopics/Perfect_numbers.html Perfect numbers - History and Theory]
- [http://mathworld.wolfram.com/PerfectNumber.html Perfect Number - from MathWorld]
- [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000396 List of Perfect Numbers] at the On-Line Encyclopedia of Integer Sequences Category:Integer sequences Category:Unsolved problems in mathematics ko:완전수 ja:完全数

Riemann hypothesis

In mathematics, the Riemann hypothesis (also called the Riemann zeta hypothesis), first formulated by Bernhard Riemann in 1859, is one of the most famous of all unsolved problems. It has been an open question for well over a century, despite attracting concentrated efforts from many outstanding mathematicians. Unlike some other celebrated problems, it is more attractive to professionals in the field than to amateurs. The Riemann hypothesis is a conjecture about the distribution of the zeros of the Riemann zeta function ζ(s). The Riemann zeta function is defined for all complex numbers s ≠ 1. It has certain so-called "trivial" zeros for s = −2, s = −4, s = −6, ... The Riemann hypothesis is concerned with the non-trivial zeros, and states that: :The real part of any non-trivial zero of the Riemann zeta function is ½. Thus the non-trivial zeros should lie on the so-called critical line ½ + it with t a real number and i the imaginary unit. The Riemann zeta function along the critical line is sometimes studied in terms of the Z function, whose real zeros correspond to the zeros of the zeta function on the critical line. Z function The Riemann hypothesis is one of the most important open problems of contemporary mathematics; a $1,000,000 prize has been offered by the Clay Mathematics Institute for a proof. Most mathematicians believe the Riemann hypothesis to be true. (J. E. Littlewood and Atle Selberg have been reported as skeptical.) In 2004, Xavier Gourdon and Patrick Demichel verified the Riemann hypothesis through the first ten trillion non-trivial zeros using the Odlyzko-Schönhage algorithm.

History

Riemann mentioned the conjecture that became known as the Riemann hypothesis in his 1859 paper On the Number of Primes Less Than a Given Magnitude, but as it was not essential to his central purpose in that paper, he did not attempt a proof. Riemann knew that the non-trivial zeros of the zeta function were symmetrically distributed about the line s = ½ + it, and he knew that all of its non-trivial zeros must lie in the range 0 ≤ Re(s) ≤ 1. In 1896 Hadamard and de la Vallée-Poussin independently proved that no zeros could lie on the line Re(s) = 1, so all non-trivial zeros must lie in the interior of the critical strip 0 < Re(s) < 1. This was a key step in the first complete proofs of the prime number theorem. In 1900 Hilbert included the Riemann hypothesis in his famous list of 23 unsolved problems - it is part of Problem 8 in Hilbert's list. He said of the problem: "If I were to awaken after having slept for a thousand years, my first question would be: Has the Riemann hypothesis been proven?". In 1914 Hardy proved that an infinite number of zeros lie on the critical line Re(s) = ½. However, it was still possible that an infinite number (and possibly the majority) of non-trivial zeros could lie elsewhere in the critical strip. Later work by Hardy and Littlewood in 1921 and by Selberg in 1942 gave estimates for the average density of zeros on the critical line. Recent work has focused on the explicit calculation of the locations of large numbers of zeros (in the hope of finding a counterexample) and placing upper bounds on the proportion of zeros that can lie away from the critical line (in the hope of reducing this to zero).

The Riemann hypothesis and primes

The traditional formulation of the Riemann hypothesis obscures somewhat the true importance of the conjecture. The zeta function has a deep connection to the distribution of prime numbers and Helge von Koch proved in 1901 that the Riemann hypothesis is equivalent to the following considerable strengthening of the prime number theorem: :

\pi(x) = \int_2^x \frac + O\left(\sqrt x\,\ln(x)\right)\quad \quad x\rightarrow\infty

where, π(x) is the prime-counting function, ln(x) is the natural logarithm of x, and the O-notation is the Landau symbol. The zeroes of the Riemann zeta function and the prime numbers satisfy a certain duality property, known as the explicit formulae which show that in the language of Fourier analysis the zeros of the zeta function can be regarded as the harmonic frequencies in the distribution of primes. The Riemann hypothesis can be generalized in various ways by replacing the Riemann zeta function by the formally similar global L-functions. None of these generalizations has been proven or disproven. See generalized Riemann hypothesis.

Other consequences of the Riemann hypothesis

The practical uses of the Riemann hypothesis include many propositions which are stated to be true under the Riemann hypothesis, and some which can be shown to be equivalent to the Riemann hypothesis. One is the rate of growth in the error term of the prime number theorem given above. Other formulations equivalent to the Riemann hypothesis involve the Möbius function μ. The statement that the equation :

\frac = \sum_^\infty \frac

is valid for every s with real part greater than ½, with the sum on the right hand side converging, is equivalent to the Riemann hypothesis. From this we can also conclude that if the Mertens function is defined by :

M(x) = \sum_ \mu(n)

then the claim that :

M(x) = o(x^e) \,

for every exponent :e > ½ is equivalent to the Riemann hypothesis. This puts a rather tight bound on the growth of M, since even with no hypothesis we can conclude :

M(x) = \Omega(x^\frac)

(For the meaning of these symbols, see Big O notation.) The Riemann hypothesis is equivalent to certain conjectures about the rate of growth of other multiplicative functions aside from μ(n). For instance, if σ(n) is the divisor function, given by :

\sigma(n) = \sum_ d

then :

\sigma(n) < e^\gamma n \ln \ln n \,

for n > 5040 (Guy Robin, 1984). A related bound was given by Jeffrey Lagarias in 2002, who proved that the Riemann hypothesis is equivalent to the statement that :

\sigma(n) \le H_n + \ln(H_n)e^

for every natural number n, where

H_n

is the harmonic number. Other functions, such as the Riesz function, have conjectured rates of growth equivalent to the Riemann hypothesis as well. Two other equivalent statements to the Riemann hypothesis involve the Farey sequence. If F_n is the Farey sequence of order n, beginning with 1/n and up to 1/1, then the claim that :

\sum_^m|F_n(i) - i/m| = o(n^e)

is equivalent to the Riemann hypothesis. Here

m = \sum_^n\phi(i)

is the number of terms in the Farey sequence of order n, and e>½. Similarly, equivalent to the Riemann hypothesis is :

\sum_^m(F_n(i) - i/m)^2 = o(n^e),

where now :e > −1. The Riemann hypothesis is equivalent to certain conjectures of group theory. For instance, if g(n) is the maximal order of elements of the symmetric group S_n of degree n, then the Riemann hypothesis is equivalent to the bound, for all n greater than some M, of :

\ln g(n) < \sqrt.

The Riemann hypothesis is equivalent to the statement that

\zeta'(s)

has no zeros in the strip :

0 < \Re(s) < \frac12

. That ζ has only simple zeros on the critical line is equivalent to its derivative having no zeros on the critical line, so under the usual hypotheses on ζ we can extend the zero-free region to

0 < \Re(s) \le \frac12

. This approach has been fruitful; refining it allowed Norman Levinson to prove his strengthening of the critical line theorem. Stronger conjectures than the Riemann hypothesis have also been formulated, but they have a tendency to be disproven. Paul Turan showed that if the sums :

\sum_^M n^

have no zeros when the real part of s is greater than one then the Riemann hypothesis is true, but Hugh Montgomery showed the premise is false. Another stronger conjecture, the Mertens conjecture, has also been disproven. The Riemann hypothesis has various weaker consequences as well; one is the Lindelöf hypothesis on the rate of growth of the zeta function on the critical line, which says :

\zeta\left(\frac12 + it\right) = o(t^e)

where :e > 0; in other words :

\left|\zeta\left(\frac12+it\right)\right|

grows more slowly than any positive exponent. Another conjecture is the large prime gap conjecture; Cramér proved that on the Riemann hypothesis we have that the largest gaps between successive prime numbers is

O(\sqrt \ln p)

. On average, the gap is merely

O(\ln p)

and numerical evidence does not suggest it can grow nearly as fast as the Riemann hypothesis seems to allow, much less as fast as the best that can at present be shown without it.

Attempted proofs of the Riemann hypothesis

In June 2004, Louis De Branges de Bourcia of Purdue University, the same mathematician who solved the Bieberbach conjecture, claimed to have proved the Riemann hypothesis in an "Apology for the proof of the Riemann Hypothesis" [http://www.math.purdue.edu/ftp_pub/branges/apology.pdf]. He has in the past announced a proof a number of times, but all of his previous attempts at this proof have failed. [http://mathworld.wolfram.com/RiemannHypothesis.html] The proof's method has been tried before unsuccessfully. Linked is Conrey and Li's counterexample on the problems in the earlier version of his proof. [http://arxiv.org/abs/math.NT/9812166] The example involves a numerical calculation. The authors also give a non-numerical counterexample, due to Peter Sarnak. On the other hand, De Branges's successful proof of the Bieberbach conjecture was also preceded by his failed proofs of it. Matthew Watkins has a collection of proposed proofs [http://www.maths.ex.ac.uk/~mwatkins/zeta/RHproofs.htm].

Possible connection with operator theory

See main article Hilbert-Pólya conjecture It has long been speculated that the correct way to derive the Riemann hypothesis has been to find a self-adjoint operator, from the existence of which the statement on the real parts of the zeroes of ζ(s) would follow when one applies the criterion on real eigenvalues. This has led to many investigations; but has not yet proven fruitful.

Searching for ζ-function zeroes

There is a long history of computational attempts to explore as many zeroes of the ζ-function as possible. As of 2005, the largest of these is ZetaGrid, a distributed computing project, which checks over a billion zeros a day. So far, every single one of them has failed to be a counterexample to the Riemann hypothesis.

References

Historical references

- Bernhard Riemann, [http://www.claymath.org/millennium/Riemann_Hypothesis/1859_manuscript/ Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse], (1859) Monatsberichte der Berliner Akademie. (This site provides both a facsimile of the original manuscripts, as well as English translations.)
- Jacques Hadamard, Sur la distribution des zéros de la fonction ζ(s) et ses conséqunces arithmétiques, Bulliten Societé Mathematique de France 14 (1896) pp 199-220.

Modern technical references

- H. M. Edwards, Riemann's Zeta Function, Academic Press, 1974. (Reprinted by Dover Publications, 2001 ISBN 0-486-41740-9)
- E. C. Titchmarsh, The Theory of the Riemann Zeta Function, second revised (Heath-Brown) edition, Oxford University Press, 1986
- (A relationship in terms of Harmonic numbers.)
- (no author credited), [http://numbers.computation.free.fr/Constants/Miscellaneous/zetazeroscompute.html Computation of zeros of the Zeta function] (2004). (Reviews the GUE hypothesis, provides an extensive bibliography as well).
- Karl Sabbagh, The Riemann Hypothesis : the greatest unsolved problem in mathematics, (2003) Farrar, Straus and Giroux, ISBN 0374250073. Also (2004) First American paperback edition.

Popular literature

- Clay Mathematics Institute, [http://www.claymath.org/millennium/ Millennium Problems], (2000) (Announcement of the million dollar rewards for solutions to famous problems in mathematics)
- Ed Pegg, Jr., [http://www.maa.org/editorial/mathgames/mathgames_10_18_04.html Ten Trillion Zeta Zeros], (2004) Math Games website. (A discussion of Xavier Gourdon's calculation of the first ten trillion non-trivial zeros.)
- Marcus du Sautoy, The Music of the Primes, HarperCollins, 2003
- Daniel Rockmore, Stalking the Riemann Hypothesis : The Quest to Find the Hidden Law of Prime Numbers, Pantheon Books, New York, 2005. ISBN 037542136X.
- John Derbyshire, [http://www.nap.edu/catalog/10532.html Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics] , Joseph Henry Press (April 23, 2003), ISBN 0309085497. (448 page book at a non-specialist level, can be read online for free.)
- [http://www.zetagrid.net/ Zetagrid] (2002) (A distributed computing project that attempted to disprove Riemann's hypothesis; closed in January 2005.)
- de Vries, [http://math-it.org/Mathematik/Riemann/RiemannApplet.html The Graph of the Riemann Zeta function ζ(s)] (2004). (A simple animated java applet.) ja:リーマン予想 ko:%EB%A6%AC%EB%A7%8C_%EA%B0%80%EC%84%A4 Category:Zeta and L-functions Category:Conjectures Category:Hilbert's problems Category:Unsolved problems in mathematics

Complexity classes P and NP

Computational complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps does it take to solve a problem) and space (how much memory does it take to solve a problem). In this theory, the class P consists of all those decision problems that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input; the class NP consists of all those decision problems whose positive solutions can be verified in polynomial time given the right information, or equivalently, whose solution can be found in polynomial time on a non-deterministic machine. Arguably, the biggest open question in theoretical computer science concerns the relationship between those two classes: :Is P equal to NP? In a 2002 poll of 100 researchers, 61 believed the answer is no, 9 believed the answer is yes, 22 were unsure, and 8 believed the question may be independent of the currently accepted axioms, and so impossible to prove or disprove.[http://www.cs.umd.edu/~gasarch/papers/poll.ps] A USD 1,000,000 prize has been offered for a correct solution. An important role in this discussion is played by the set of NP-complete problems (or NPC) which can be loosely described as those problems in NP that are the least likely to be in P. (See NP-complete for the exact definition.) Most theoretical computer scientists currently believe that the relationship among the classes P, NP, and NPC is as shown in the picture, with the P and NPC classes disjoint. In essence, the P = NP question asks: if positive solutions to a YES/NO problem can be verified quickly, can the answers also be computed quickly? Here is an example to get a feeling for the question. Given a large number Y, we might ask whether Y is a composite number. For example, we might ask whether the number 53308290611 has nontrivial factors. The answer is YES, though it would take a fair amount of work to find a factor by hand. On the other hand, if someone claims that the answer is "YES, because 224737 is a divisor of 53308290611", then we can quickly check that with a single division. Verifying that a number is a divisor is much easier than finding the divisor in the first place. The information needed to verify a positive answer is also called a certificate. So we conclude that given the right certificates, positive answers to our problem can be verified quickly (i.e. in polynomial time) and that's why this problem is in NP. Although this particular problem was recently shown to be in P as well (see references for "PRIMES is in P" below), this is not at all obvious, and there are many other similar problems that are not believed to be in P. The restriction to YES/NO problems doesn't really make a difference; even if we allow more complicated answers, the resulting problem (whether FP = FNP) is equivalent.

Formal definitions

More formally, a decision problem is a problem that takes as input some string and requires as output either YES or NO. If there is an algorithm (say a Turing machine, or a LISP or Pascal program with unbounded memory) which is able to produce the correct answer for any input string of length n in at most n^k steps, where k is some constant independent of the input string, then we say that the problem can be solved in polynomial time and we place it in the class P. Intuitively, we think of the problems in P as those that can be solved reasonably quickly. Now suppose there is an algorithm A(w,C) which takes two arguments, a string w which is an input string to our decision problem, and a string C which is a "proposed certificate", and such that A produces a YES/NO answer in at most n^k steps (where n is the length of w and k doesn't depend on w). Suppose furthermore that : w is a YES instance of the decision problem if and only if there exists C such that A(w,C) returns YES. Then we say that the problem can be solved in non-deterministic polynomial time and we place it in the class NP. We think of the algorithm A as a verifier of proposed certificates which runs reasonably fast. (Note that the abbreviation NP stands for "Non-deterministic Polynomial" and not for "Non-Polynomial".)

NP-complete

To attack the P = NP question, the concept of NP-completeness is very useful. Informally, the NP-complete problems are the "toughest" problems in NP in the sense that they are the ones most likely not to be in P. This is because any problem in NP can be transformed, in polynomial time, into an instance of any specific NP-complete problem. For instance, the decision problem version of the traveling salesman problem is NP-complete. So any instance of any problem in NP can be transformed mechanically into an instance of the traveling salesman problem, in polynomial time. So, if the traveling salesman problem turned out to be in P, then P = NP! The traveling salesman problem is one of many such NP-complete problems. If any NP-complete problem is in P, then it would follow that P = NP. Unfortunately, many important problems have been shown to be NP-complete and not a single fast algorithm for any of them is known.

Still harder problems

Although it is unknown whether P=NP, problems outside of P are known. The problem of finding the best move in Chess or Go (on an n by n board) is EXPTIME-complete. Because it can be shown that P ≠ EXPTIME, these problems are outside P, and so require more than polynomial time. In fact, by the time hierarchy theorem, they cannot be solved in significantly less than exponential time. The problem of deciding the truth of a statement in Presburger arithmetic is even harder. Fischer and Rabin proved in 1974 that every algorithm which decides the truth of Presburger statements has a runtime of at least 2^(2^(cn)) for some constant c. Here, n is the length of the Presburger statement. Hence, the problem is known to need more than exponential run time. Even more difficult are the undecidable problems, such as the halting problem. They cannot be solved in general given any amount of time.

Is P really tractable?

All of the above discussion has assumed that P means "easy" and "not in P" means "hard". While this is a common and reasonably accurate assumption in complexity theory, it is not always true in practice, for several reasons:
- It ignores constant factors. A problem that takes time 10¹⁰⁰⁰n is in P (it is linear time), but is completely intractable in practice. A problem that takes time 10^-100002ⁿ is not in P (it is exponential time), but is very tractable for values of n up into the thousands.
- It ignores the size of the exponents. A problem with time n¹⁰⁰⁰ is in P, yet intractable. Problems have been proven to exist in P that require arbitrarily large exponents (see time hierarchy theorem). A problem with time 2^n/1000 is not in P, yet is tractable for n up into the thousands.
- It only considers worst-case times. There might be a problem that arises in the real world such that most of the time, it can be solved in time n, but on very rare occasions you'll see an instance of the problem that takes time 2ⁿ. This problem might have an average time that is polynomial, but the worst case is exponential, so the problem wouldn't be in P.
- It only considers deterministic solutions. There might be a problem that you can solve quickly if you accept a tiny error probability, but a guaranteed correct answer is much harder to get. The problem would not belong to P even though in practice it can be solved fast. This is in fact a common approach to attack problems in NP not known to be in P (see RP, BPP). Even if P=BPP, as many researchers believe, it is often considerably easier to find probabilistic algorithms.
- New computing models such as quantum computers may be able to quickly solve

Conjecture

Famous conjectures

Counterexamples

Use of conjectures in conditional proofs

Undecidable conjectures

Usage outside of mathematics

See also

Mathematics

History

Inspiration, pure and applied mathematics, and aesthetics

Notation, language, and rigor

Is mathematics a science?

Overview of fields of mathematics

Major themes in mathematics

Quantity

Structure

Space

Change

Foundations and methods

Discrete mathematics

Applied mathematics

Important theorems

Important conjectures

History and the world of mathematicians

Mathematics and other fields

Common misconceptions

See also

Bibliography

External links

Mathematical proof

See also

Theorem

See also

Fermat's last theorem

Mathematical context

Early history

The proof

Did Fermat really have a proof?

Trivia

Notes

See also

External links and references

Bibliography and further reading

Taniyama-Shimura theorem

References

Perfect number

Even perfect numbers

Odd perfect numbers

See also

References

External links

Riemann hypothesis

History

The Riemann hypothesis and primes

Other consequences of the Riemann hypothesis

Attempted proofs of the Riemann hypothesis

Possible connection with operator theory

Searching for ζ-function zeroes

References

Historical references

Modern technical references

Popular literature

Complexity classes P and NP

Formal definitions

NP-complete

Still harder problems

Is P really tractable?