Computer-assisted proof

Last updated

A computer-assisted proof is a mathematical proof that has been at least partially generated by computer.

Contents

Most computer-aided proofs to date have been implementations of large proofs-by-exhaustion of a mathematical theorem. The idea is to use a computer program to perform lengthy computations, and to provide a proof that the result of these computations implies the given theorem. In 1976, the four color theorem was the first major theorem to be verified using a computer program.

Attempts have also been made in the area of artificial intelligence research to create smaller, explicit, new proofs of mathematical theorems from the bottom up using automated reasoning techniques such as heuristic search. Such automated theorem provers have proved a number of new results and found new proofs for known theorems.[ citation needed ] Additionally, interactive proof assistants allow mathematicians to develop human-readable proofs which are nonetheless formally verified for correctness. Since these proofs are generally human-surveyable (albeit with difficulty, as with the proof of the Robbins conjecture) they do not share the controversial implications of computer-aided proofs-by-exhaustion.

Methods

One method for using computers in mathematical proofs is by means of so-called validated numerics or rigorous numerics. This means computing numerically yet with mathematical rigour. One uses set-valued arithmetic and inclusion principle[ clarify ] in order to ensure that the set-valued output of a numerical program encloses the solution of the original mathematical problem. This is done by controlling, enclosing and propagating round-off and truncation errors using for example interval arithmetic. More precisely, one reduces the computation to a sequence of elementary operations, say . In a computer, the result of each elementary operation is rounded off by the computer precision. However, one can construct an interval provided by upper and lower bounds on the result of an elementary operation. Then one proceeds by replacing numbers with intervals and performing elementary operations between such intervals of representable numbers.[ citation needed ]

Philosophical objections

Computer-assisted proofs are the subject of some controversy in the mathematical world, with Thomas Tymoczko first to articulate objections. Those who adhere to Tymoczko's arguments believe that lengthy computer-assisted proofs are not, in some sense, 'real' mathematical proofs because they involve so many logical steps that they are not practically verifiable by human beings, and that mathematicians are effectively being asked to replace logical deduction from assumed axioms with trust in an empirical computational process, which is potentially affected by errors in the computer program, as well as defects in the runtime environment and hardware. [1]

Other mathematicians believe that lengthy computer-assisted proofs should be regarded as calculations, rather than proofs: the proof algorithm itself should be proved valid, so that its use can then be regarded as a mere "verification". Arguments that computer-assisted proofs are subject to errors in their source programs, compilers, and hardware can be resolved by providing a formal proof of correctness for the computer program (an approach which was successfully applied to the four color theorem in 2005) as well as replicating the result using different programming languages, different compilers, and different computer hardware.

Another possible way of verifying computer-aided proofs is to generate their reasoning steps in a machine readable form, and then use a proof checker program to demonstrate their correctness. Since validating a given proof is much easier than finding a proof, the checker program is simpler than the original assistant program, and it is correspondingly easier to gain confidence into its correctness. However, this approach of using a computer program to prove the output of another program correct does not appeal to computer proof skeptics, who see it as adding another layer of complexity without addressing the perceived need for human understanding.

Another argument against computer-aided proofs is that they lack mathematical elegance—that they provide no insights or new and useful concepts. In fact, this is an argument that could be advanced against any lengthy proof by exhaustion.

An additional philosophical issue raised by computer-aided proofs is whether they make mathematics into a quasi-empirical science, where the scientific method becomes more important than the application of pure reason in the area of abstract mathematical concepts. This directly relates to the argument within mathematics as to whether mathematics is based on ideas, or "merely" an exercise in formal symbol manipulation. It also raises the question whether, if according to the Platonist view, all possible mathematical objects in some sense "already exist", whether computer-aided mathematics is an observational science like astronomy, rather than an experimental one like physics or chemistry. This controversy within mathematics is occurring at the same time as questions are being asked in the physics community about whether twenty-first century theoretical physics is becoming too mathematical, and leaving behind its experimental roots.

The emerging field of experimental mathematics is confronting this debate head-on by focusing on numerical experiments as its main tool for mathematical exploration.

Theorems proved with the help of computer programs

Inclusion in this list does not imply that a formal computer-checked proof exists, but rather, that a computer program has been involved in some way. See the main articles for details.

See also

Related Research Articles

Automated theorem proving is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs. Automated reasoning over mathematical proof was a major motivating factor for the development of computer science.

<span class="mw-page-title-main">Conjecture</span> Proposition in mathematics that is unproven

In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis or Fermat's conjecture, have shaped much of mathematical history as new areas of mathematics are developed in order to prove them.

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

<span class="mw-page-title-main">Number theory</span> Mathematics of integer properties

Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mathematics is the queen of the sciences—and number theory is the queen of mathematics." Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers, or defined as generalizations of the integers.

Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of the mathematical field of combinatorics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a question of the form: "how big must some structure be to guarantee that a particular property holds?"

Computer science is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. One well known subject classification system for computer science is the ACM Computing Classification System devised by the Association for Computing Machinery.

Experimental mathematics is an approach to mathematics in which computation is used to investigate mathematical objects and identify properties and patterns. It has been defined as "that branch of mathematics that concerns itself ultimately with the codification and transmission of insights within the mathematical community through the use of experimental exploration of conjectures and more informal beliefs and a careful analysis of the data acquired in this pursuit."

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

<span class="mw-page-title-main">Happy ending problem</span> Five coplanar points have a subset forming a convex quadrilateral

In mathematics, the "happy ending problem" is the following statement:

In computer science, in particular in knowledge representation and reasoning and metalogic, the area of automated reasoning is dedicated to understanding different aspects of reasoning. The study of automated reasoning helps produce computer programs that allow computers to reason completely, or nearly completely, automatically. Although automated reasoning is considered a sub-field of artificial intelligence, it also has connections with theoretical computer science and philosophy.

In mathematics, an impossibility theorem is a theorem that demonstrates a problem or general set of problems cannot be solved. These are also known as proofs of impossibility, negative proofs, or negative results. Impossibility theorems often resolve decades or centuries of work spent looking for a solution by proving there is no solution. Proving that something is impossible is usually much harder than the opposite task, as it is often necessary to develop a proof that works in general, rather than to just show a particular example. Impossibility theorems are usually expressible as negative existential propositions or universal propositions in logic.

Van der Waerden's theorem states that for any positive integers r and k there exists a positive integer N such that if the integers {1, 2, ..., N} are colored, each with one of r different colors, then there are at least k integers in arithmetic progression all of the same color. The smallest such N is the van der Waerden numberW(r, k).

<span class="mw-page-title-main">Mutilated chessboard problem</span> On domino tiling after removing two corners

The mutilated chessboard problem is a tiling puzzle posed by Max Black in 1946 that asks:

Suppose a standard 8×8 chessboard has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes of size 2×1 so as to cover all of these squares?

In computer science and formal methods, a SAT solver is a computer program which aims to solve the Boolean satisfiability problem. On input a formula over Boolean variables, such as "(x or y) and (x or not y)", a SAT solver outputs whether the formula is satisfiable, meaning that there are possible values of x and y which make the formula true, or unsatisfiable, meaning that there are no such values of x and y. In this case, the formula is satisfiable when x is true, so the solver should return "satisfiable". Since the introduction of algorithms for SAT in the 1960s, modern SAT solvers have grown into complex software artifacts involving a large number of heuristics and program optimizations to work efficiently.

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether an arbitrary program eventually halts when run.

<span class="mw-page-title-main">Fermat's Last Theorem</span> 17th-century conjecture proved by Andrew Wiles in 1994

In number theory, Fermat's Last Theorem states that no three positive integers a, b, and c satisfy the equation an + bn = cn for any integer value of n greater than 2. The cases n = 1 and n = 2 have been known since antiquity to have infinitely many solutions.

The Boolean Pythagorean triples problem is a problem from Ramsey theory about whether the positive integers can be colored red and blue so that no Pythagorean triples consist of all red or all blue members. The Boolean Pythagorean triples problem was solved by Marijn Heule, Oliver Kullmann and Victor W. Marek in May 2016 through a computer-assisted proof.

Marienus Johannes Hendrikus Heule is a Dutch computer scientist at Carnegie Mellon University who studies SAT solvers. Heule has used these solvers to resolve mathematical conjectures such as the Boolean Pythagorean triples problem, Schur's theorem number 5, and Keller's conjecture in dimension seven.

References

  1. ↑ Tymoczko, Thomas (1979), "The Four-Color Problem and its Mathematical Significance", The Journal of Philosophy , 76 (2): 57–83, doi:10.2307/2025976, JSTOR   2025976 .
  2. ↑ Boyce, William M. (March 1969). "Commuting Functions with No Common Fixed Point" (PDF). Transactions of the American Mathematical Society. 137: 77–92. doi:10.1090/S0002-9947-1969-0236331-5.
  3. ↑ Gonthier, Georges (2008), "Formal Proof—The Four-Color Theorem" (PDF), Notices of the American Mathematical Society , 55 (11): 1382–1393, MR   2463991, archived (PDF) from the original on 2011-08-05
  4. ↑ Hass, J.; Hutchings, M.; Schlafly, R. (1995). "The double bubble conjecture". Electronic Research Announcements of the American Mathematical Society. 1 (3): 98–102. CiteSeerX   10.1.1.527.8616 . doi:10.1090/S1079-6762-95-03001-0.
  5. ↑ Kouril, Michal (2006). A Backtracking Framework for Beowulf Clusters with an Extension to Multi-Cluster Computation and Sat Benchmark Problem Implementation (Ph.D. thesis). University of Cincinnati.
  6. ↑ Kouril, Michal (2012). "Computing the van der Waerden number W(3,4)=293". Integers. 12: A46. MR   3083419.
  7. ↑ Kouril, Michal (2015). "Leveraging FPGA clusters for SAT computations". Parallel Computing: On the Road to Exascale: 525–532.
  8. ↑ Ahmed, Tanbir (2009). "Some new van der Waerden numbers and some van der Waerden-type numbers". Integers. 9: A6. doi:10.1515/integ.2009.007. MR   2506138. S2CID   122129059.
  9. 1 2 Ahmed, Tanbir (2010). "Two new van der Waerden numbers w(2;3,17) and w(2;3,18)". Integers. 10 (4): 369–377. doi:10.1515/integ.2010.032. MR   2684128. S2CID   124272560.
  10. ↑ Ahmed, Tanbir (2012). "On computation of exact van der Waerden numbers". Integers. 12 (3): 417–425. doi:10.1515/integ.2011.112. MR   2955523. S2CID   11811448.
  11. ↑ Ahmed, Tanbir (2013). "Some More Van der Waerden numbers". Journal of Integer Sequences. 16 (4): 13.4.4. MR   3056628.
  12. ↑ Ahmed, Tanbir; Kullmann, Oliver; Snevily, Hunter (2014). "On the van der Waerden numbers w(2;3,t)". Discrete Applied Mathematics . 174 (2014): 27–51. arXiv: 1102.5433 . doi: 10.1016/j.dam.2014.05.007 . MR   3215454.
  13. ↑ "God's Number is 20". cube20.org. July 2010. Retrieved 2023-10-18.
  14. ↑ Cesare, Chris (1 October 2015). "Maths whizz solves a master's riddle". Nature. 526 (7571): 19–20. Bibcode:2015Natur.526...19C. doi: 10.1038/nature.2015.18441 . PMID   26432222.
  15. ↑ Lamb, Evelyn (26 May 2016). "Two-hundred-terabyte maths proof is largest ever". Nature. 534 (7605): 17–18. Bibcode:2016Natur.534...17L. doi: 10.1038/nature.2016.19990 . PMID   27251254.
  16. ↑ Celletti, A.; Chierchia, L. (1987). "Rigorous estimates for a computer-assisted KAM theory". Journal of Mathematical Physics. 28 (9): 2078–86. Bibcode:1987JMP....28.2078C. doi:10.1063/1.527418.
  17. ↑ Figueras, J.L.; Haro, A.; Luque, A. (2017). "Rigorous computer-assisted application of KAM theory: a modern approach". Foundations of Computational Mathematics. 17 (5): 1123–93. arXiv: 1601.00084 . doi:10.1007/s10208-016-9339-3. hdl:2445/192693. S2CID   28258285.
  18. ↑ Heule, Marijn J. H. (2017). "Schur Number Five". arXiv: 1711.08076 [cs.LO].
  19. ↑ "Schur Number Five". www.cs.utexas.edu. Retrieved 2021-10-06.
  20. ↑ Brakensiek, Joshua; Heule, Marijn; Mackey, John; Narváez, David (2020). "The Resolution of Keller's Conjecture". In Peltier, Nicolas; Sofronie-Stokkermans, Viorica (eds.). Automated Reasoning. Lecture Notes in Computer Science. Vol. 12166. Springer. pp. 48–65. doi:10.1007/978-3-030-51074-9_4. ISBN   978-3-030-51074-9. PMC   7324133 .
  21. ↑ Hartnett, Kevin (2020-08-19). "Computer Search Settles 90-Year-Old Math Problem". Quanta Magazine. Retrieved 2021-10-08.
  22. ↑ Subercaseaux, Bernardo; Heule, Marijn J. H. (2023-01-23). "The Packing Chromatic Number of the Infinite Square Grid is 15". arXiv: 2301.09757 [cs.DM].
  23. ↑ Hartnett, Kevin (2023-04-20). "The Number 15 Describes the Secret Limit of an Infinite Grid". Quanta Magazine. Retrieved 2023-04-20.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.