Mathematical proof

From Wikipedia, the free encyclopedia

 

P. Oxy. 29, one of the oldest surviving fragments of Euclid's Elements, a textbook used for millennia to teach proof-writing techniques. The diagram accompanies Book II, Proposition 5.

 

In mathematics, a proof is an inferential argument for a mathematical statement. In the argument, other previously established statements, such as theorems, can be used. In principle, a proof can be traced back to self-evident or assumed statements, known as axioms, along with accepted rules of inference. Axioms may be treated as conditions that must be met before the statement applies. Proofs are examples of exhaustive deductive reasoning or inductive reasoning and are distinguished from empirical arguments or non-exhaustive inductive reasoning (or "reasonable expectation"). A proof must demonstrate that a statement is always true (occasionally by listing all possible cases and showing that it holds in each), rather than enumerate many confirmatory cases. An unproved proposition that is believed to be true is known as a conjecture.

Proofs employ logic but usually include some amount of natural language which usually admits some ambiguity. In fact, the vast majority of proofs in written mathematics can be considered as applications of rigorous informal logic. Purely formal proofs, written in symbolic language instead of natural language, are considered in proof theory. The distinction between formal and informal proofs 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.

History and etymology

The word "proof" comes from the Latin probare meaning "to test". Related modern words are the English "probe", "probation", and "probability", the Spanish probar (to smell or taste, or (lesser use) touch or test), Italian provare (to try), and the German probieren (to try). The early use of "probity" was in the presentation of legal evidence. A person of authority, such as a nobleman, was said to have probity, whereby the evidence was by his relative authority, which outweighed empirical testimony.

Plausibility arguments using heuristic devices such as pictures and analogies preceded strict mathematical proof. It is likely that the idea of demonstrating a conclusion first arose in connection with geometry, which originally meant the same as "land measurement". The development of mathematical proof is primarily the product of ancient Greek mathematics, and one of the greatest achievements thereof. Thales (624–546 BCE) and Hippocrates of Chios (c470-410 BCE) proved some theorems in geometry. Eudoxus (408–355 BCE) and Theaetetus (417–369 BCE) formulated theorems but did not prove them. Aristotle (384–322 BCE) said definitions should describe the concept being defined in terms of other concepts already known. Mathematical proofs were revolutionized by Euclid (300 BCE), who introduced the axiomatic method still in use today, starting with undefined terms and axioms (propositions regarding the undefined terms assumed to be self-evidently true from the Greek "axios" meaning "something worthy"), and used these to prove theorems using deductive logic. His book, the Elements, was read by anyone who was considered educated in the West until the middle of the 20th century. In addition to theorems of geometry, such as the Pythagorean theorem, the Elements also covers number theory, including a proof that the square root of two is irrational and that there are infinitely many prime numbers.

Further advances took place in medieval Islamic mathematics. While earlier Greek proofs were largely geometric demonstrations, the development of arithmetic and algebra by Islamic mathematicians allowed more general proofs that no longer depended on geometry. In the 10th century CE, the Iraqi mathematician Al-Hashimi provided general proofs for numbers (rather than geometric demonstrations) as he considered multiplication, division, etc. for "lines." He used this method to provide a proof of the existence of irrational numbers. An inductive proof for arithmetic sequences was introduced in the Al-Fakhri (1000) by Al-Karaji, who used it to prove the binomial theorem and properties of Pascal's triangle. Alhazen also developed the method of proof by contradiction, as the first attempt at proving the Euclidean parallel postulate.

Modern proof theory treats proofs as inductively defined data structures. There is no longer an assumption that axioms are "true" in any sense; this allows for parallel mathematical theories built on alternate sets of axioms (see Axiomatic set theory and Non-Euclidean geometry for examples).

Nature and purpose

As practiced, a proof is expressed in natural language and is a rigorous argument intended to convince the audience of the truth of a statement. The standard of rigor is not absolute and has varied throughout history. A proof can be presented differently depending on the intended audience. In order to gain acceptance, a proof has to meet communal statements of rigor; an argument considered vague or incomplete may be rejected.

The concept of a proof is formalized in the field of mathematical logic. A formal proof is written in a formal language instead of a natural language. A formal proof is defined as sequence of formulas in a formal language, in which each formula is a logical consequence of preceding formulas. Having a definition of formal proof makes the concept of proof amenable to study. Indeed, the field of proof theory studies formal proofs and their properties, for example, the property that a statement has a formal proof. An application of proof theory is to show that certain undecidable statements are not provable.

The definition of a formal proof is intended to capture the concept of proofs as written in the practice of mathematics. The soundness of this definition amounts to the belief that a published proof can, in principle, be converted into a formal proof. However, outside the field of automated proof assistants, this is rarely done in practice. A classic question in philosophy asks whether mathematical proofs are analytic or synthetic. Kant, who introduced the analytic-synthetic distinction, believed mathematical proofs are synthetic.

Proofs may be viewed as aesthetic objects, admired for their mathematical beauty. The mathematician Paul Erdős was known for describing proofs he found particularly elegant as coming from "The Book", a hypothetical tome containing the most beautiful method(s) of proving each theorem. The book Proofs from THE BOOK, published in 2003, is devoted to presenting 32 proofs its editors find particularly pleasing.

Methods

Direct proof

In direct proof, the conclusion is established by logically combining the axioms, definitions, and earlier theorems. For example, direct proof can be used to establish that the sum of two even integers is always even:

Consider two even integers x and y. Since they are even, they can be written as x = 2a and y = 2b, respectively, for integers a and b. Then the sum x + y = 2a + 2b = 2(a+b). Therefore x+y has 2 as a factor and, by definition, is even. Hence the sum of any two even integers is even.

This proof uses the definition of even integers, the integer properties of closure under addition and multiplication, and distributivity.

Proof by mathematical induction

Despite its name, mathematical induction is a method of deduction, not a form of inductive reasoning. In proof by mathematical induction, a single "base case" is proved, and an "induction rule" is proved that establishes that any arbitrary case implies the next case. Since in principle the induction rule can be applied repeatedly starting from the proved base case, we see that all (usually infinitely many) cases are provable. This avoids having to prove each case individually. A variant of mathematical induction is proof by infinite descent, which can be used, for example, to prove the irrationality of the square root of two.

A common application of proof by mathematical induction is to prove that a property known to hold for one number holds for all natural numbers: Let N = {1,2,3,4,...} be the set of natural numbers, and P(n) be a mathematical statement involving the natural number n belonging to N such that

• (i) P(1) is true, i.e., P(n) is true for n = 1.
• (ii) P(n+1) is true whenever P(n) is true, i.e., P(n) is true implies that P(n+1) is true.
• Then P(n) is true for all natural numbers n.

For example, we can prove by induction that all positive integers of the form 2n − 1 are odd. Let P(n) represent "2n − 1 is odd":

(i) For n = 1, 2n − 1 = 2(1) − 1 = 1, and 1 is odd, since it leaves a remainder of 1 when divided by 2. Thus P(1) is true.

(ii) For any n, if 2n − 1 is odd (P(n)), then (2n − 1) + 2 must also be odd, because adding 2 to an odd number results in an odd number. But (2n − 1) + 2 = 2n + 1 = 2(n+1) − 1, so 2(n+1) − 1 is odd (P(n+1)). So P(n) implies P(n+1).

Thus 2n − 1 is odd, for all positive integers n.

The shorter phrase "proof by induction" is often used instead of "proof by mathematical induction".

Proof by contraposition

Proof by contraposition infers the conclusion "if p then q" from the premise "if not q then not p". The statement "if not q then not p" is called the contrapositive of the statement "if p then q". For example, contraposition can be used to establish that, given an integer ${\displaystyle x}$, if ${\displaystyle x^{2}}$ is even, then ${\displaystyle x}$ is even:

Suppose ${\displaystyle x}$ is not even. Then ${\displaystyle x}$ is odd. The product of two odd numbers is odd, hence ${\displaystyle x^{2}=x\cdot x}$ is odd. Thus ${\displaystyle x^{2}}$ is not even. Thus, if ${\displaystyle x^{2}}$ is even, the supposition must be false, so ${\displaystyle x}$ has to be even.

Proof by contradiction

In proof by contradiction (also known as reductio ad absurdum, Latin for "by reduction to the absurd"), it is shown that if some statement were true, a logical contradiction occurs, hence the statement must be false. A famous example of proof by contradiction shows that ${\displaystyle {\sqrt {2}}}$ is an irrational number:

Suppose that ${\displaystyle {\sqrt {2}}}$ were a rational number, so by definition ${\displaystyle {\sqrt {2}}={a \over b}}$ where a and b are non-zero integers with no common factor. (If there is a common factor, divide both numerator and denominator by that factor to remove it, and repeat until no common factor remains. By the method of infinite descent, this process must terminate.) Thus, ${\displaystyle b{\sqrt {2}}=a}$. Squaring both sides yields 2b² = a². Since 2 divides the left hand side, 2 must also divide the right hand side (otherwise an even number would equal an odd number). So a² is even, which implies that a must also be even. So we can write a = 2c, where c is also an integer. Substitution into the original equation yields 2b² = (2c)² = 4c². Dividing both sides by 2 yields b² = 2c². But then, by the same argument as before, 2 divides b², so b must be even. However, if a and b are both even, they have a common factor, namely 2. This contradicts our initial supposition, so we are forced to conclude that ${\displaystyle {\sqrt {2}}}$ is an irrational number.

Proof by construction

Proof by construction, or proof by example, is the construction of a concrete example with a property to show that something having that property exists. Joseph Liouville, for instance, proved the existence of transcendental numbers by constructing an explicit example. It can also be used to construct a counterexample to disprove a proposition that all elements have a certain property.

Proof by exhaustion

In proof by exhaustion, the conclusion is established by dividing it into a finite number of cases and proving each one separately. The number of cases sometimes can become very large. For example, the first proof of the four color theorem was a proof by exhaustion with 1,936 cases. This proof was controversial because the majority of the cases were checked by a computer program, not by hand. The shortest known proof of the four color theorem as of 2011 still has over 600 cases.

Probabilistic proof

A probabilistic proof is one in which an example is shown to exist, with certainty, by using methods of probability theory. Probabilistic proof, like proof by construction, is one of many ways to show existence theorems.

This is not to be confused with an argument that a theorem is 'probably' true, a 'plausibility argument'. The work on the Collatz conjecture shows how far plausibility is from genuine proof.

While most mathematicians do not think that probabilistic evidence ever counts as a genuine mathematical proof, a few mathematicians and philosophers have argued that at least some types of probabilistic evidence (such as Rabin's probabilistic algorithm for testing primality) are as good as genuine mathematical proofs.

Combinatorial proof

A combinatorial proof establishes the equivalence of different expressions by showing that they count the same object in different ways. Often a bijection between two sets is used to show that the expressions for their two sizes are equal. Alternatively, a double counting argument provides two different expressions for the size of a single set, again showing that the two expressions are equal.

Nonconstructive proof

A nonconstructive proof establishes that a mathematical object with a certain property exists without explaining how such an object can be found. Often, this takes the form of a proof by contradiction in which the nonexistence of the object is proved to be impossible. In contrast, a constructive proof establishes that a particular object exists by providing a method of finding it. A famous example of a nonconstructive proof shows that there exist two irrational numbers a and b such that ${\displaystyle a^{b}}$ is a rational number:

Either ${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$ is a rational number and we are done (take ${\displaystyle a=b={\sqrt {2}}}$), or ${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$ is irrational so we can write ${\displaystyle a={\sqrt {2}}^{\sqrt {2}}}$ and ${\displaystyle b={\sqrt {2}}}$. This then gives ${\displaystyle \left({\sqrt {2}}^{\sqrt {2}}\right)^{\sqrt {2}}={\sqrt {2}}^{2}=2}$, which is thus a rational of the form ${\displaystyle a^{b}.}$

Statistical proofs in pure mathematics

The expression "statistical proof" may be used technically or colloquially in areas of pure mathematics, such as involving cryptography, chaotic series, and probabilistic or analytic number theory. It is less commonly used to refer to a mathematical proof in the branch of mathematics known as mathematical statistics. See also "Statistical proof using data" section below.

Computer-assisted proofs

Until the twentieth century it was assumed that any proof could, in principle, be checked by a competent mathematician to confirm its validity. However, computers are now used both to prove theorems and to carry out calculations that are too long for any human or team of humans to check; the first proof of the four color theorem is an example of a computer-assisted proof. Some mathematicians are concerned that the possibility of an error in a computer program or a run-time error in its calculations calls the validity of such computer-assisted proofs into question. In practice, the chances of an error invalidating a computer-assisted proof can be reduced by incorporating redundancy and self-checks into calculations, and by developing multiple independent approaches and programs. Errors can never be completely ruled out in case of verification of a proof by humans either, especially if the proof contains natural language and requires deep mathematical insight.

Undecidable statements

A statement that is neither provable nor disprovable from a set of axioms is called undecidable (from those axioms). One example is the parallel postulate, which is neither provable nor refutable from the remaining axioms of Euclidean geometry.

Mathematicians have shown there are many statements that are neither provable nor disprovable in Zermelo-Fraenkel set theory with the axiom of choice (ZFC), the standard system of set theory in mathematics (assuming that ZFC is consistent); see list of statements undecidable in ZFC.

Gödel's (first) incompleteness theorem shows that many axiom systems of mathematical interest will have undecidable statements.

Heuristic mathematics and experimental mathematics

While early mathematicians such as Eudoxus of Cnidus did not use proofs, from Euclid to the foundational mathematics developments of the late 19th and 20th centuries, proofs were an essential part of mathematics. With the increase in computing power in the 1960s, significant work began to be done investigating mathematical objects outside of the proof-theorem framework, in experimental mathematics. Early pioneers of these methods intended the work ultimately to be embedded in a classical proof-theorem framework, e.g. the early development of fractal geometry, which was ultimately so embedded.

Related concepts

Visual proof

Although not a formal proof, a visual demonstration of a mathematical theorem is sometimes called a "proof without words". The left-hand picture below is an example of a historic visual proof of the Pythagorean theorem in the case of the (3,4,5) triangle.

• 

  Visual proof for the (3, 4, 5) triangle as in the Zhoubi Suanjing 500–200 BC.
  
• 

  Animated visual proof for the Pythagorean theorem by rearrangement.
  
• 

  A second animated proof of the Pythagorean theorem.
  

Some illusory visual proofs, such as the missing square puzzle, can be constructed in a way which appear to prove a supposed mathematical fact but only do so under the presence of tiny errors (for example, supposedly straight lines which actually bend slightly) which are unnoticeable until the entire picture is closely examined, with lengths and angles precisely measured or calculated.

Elementary proof

An elementary proof is a proof which only uses basic techniques. More specifically, the term is used in number theory to refer to proofs that make no use of complex analysis. For some time it was thought that certain theorems, like the prime number theorem, could only be proved using "higher" mathematics. However, over time, many of these results have been reproved using only elementary techniques.

Two-column proof

A two-column proof published in 1913

A particular way of organising a proof using two parallel columns is often used in elementary geometry classes in the United States. The proof is written as a series of lines in two columns. In each line, the left-hand column contains a proposition, while the right-hand column contains a brief explanation of how the corresponding proposition in the left-hand column is either an axiom, a hypothesis, or can be logically derived from previous propositions. The left-hand column is typically headed "Statements" and the right-hand column is typically headed "Reasons".

Colloquial use of "mathematical proof"

The expression "mathematical proof" is used by lay people to refer to using mathematical methods or arguing with mathematical objects, such as numbers, to demonstrate something about everyday life, or when data used in an argument is numerical. It is sometimes also used to mean a "statistical proof" (below), especially when used to argue from data.

Statistical proof using data

"Statistical proof" from data refers to the application of statistics, data analysis, or Bayesian analysis to infer propositions regarding the probability of data. While using mathematical proof to establish theorems in statistics, it is usually not a mathematical proof in that the assumptions from which probability statements are derived require empirical evidence from outside mathematics to verify. In physics, in addition to statistical methods, "statistical proof" can refer to the specialized mathematical methods of physics applied to analyze data in a particle physics experiment or observational study in physical cosmology. "Statistical proof" may also refer to raw data or a convincing diagram involving data, such as scatter plots, when the data or diagram is adequately convincing without further analysis.

Inductive logic proofs and Bayesian analysis

Proofs using inductive logic, while considered mathematical in nature, seek to establish propositions with a degree of certainty, which acts in a similar manner to probability, and may be less than full certainty. Inductive logic should not be confused with mathematical induction.

Bayesian analysis uses Bayes' theorem to update a person's assessment of likelihoods of hypotheses when new evidence or information is acquired.

Proofs as mental objects

Psychologism views mathematical proofs as psychological or mental objects. Mathematician philosophers, such as Leibniz, Frege, and Carnap have variously criticized this view and attempted to develop a semantics for what they considered to be the language of thought, whereby standards of mathematical proof might be applied to empirical science.

Influence of mathematical proof methods outside mathematics

Philosopher-mathematicians such as Spinoza have attempted to formulate philosophical arguments in an axiomatic manner, whereby mathematical proof standards could be applied to argumentation in general philosophy. Other mathematician-philosophers have tried to use standards of mathematical proof and reason, without empiricism, to arrive at statements outside of mathematics, but having the certainty of propositions deduced in a mathematical proof, such as Descartes' cogito argument.

Ending a proof

Sometimes, the abbreviation "Q.E.D." is written to indicate the end of a proof. This abbreviation stands for "Quod Erat Demonstrandum", which is Latin for "that which was to be demonstrated". A more common^{[citation needed]} alternative is to use a square or a rectangle, such as □ or ∎, known as a "tombstone" or "halmos" after its eponym Paul Halmos. Often, "which was to be shown" is verbally stated when writing "QED", "□", or "∎" during an oral presentation.

MIT Assesses the Technical Feasibility of the Mars One Mission

By Jennifer Chu, MIT News October 14, 2014

Original link:  https://scitechdaily.com/mit-assesses-technical-feasibility-mars-one-mission/ 

 

The non-profit company Mars One plans to establish the first human settlement on Mars by 2025. Pictured is an artist’s rendering of a series of habitats. Solar panels (in the foreground), would supply the colony’s electricity, while a system to extract water from the soil (in the background) would supply drinking water.

A new independent assessment of the Mars One Mission from MIT engineers reveals that the project may have to take a step back, at least to reconsider the mission’s technical feasibility.

In 2012, the “Mars One” project, led by a Dutch nonprofit, announced plans to establish the first human colony on the Red Planet by 2025. The mission would initially send four astronauts on a one-way trip to Mars, where they would spend the rest of their lives building the first permanent human settlement.

It’s a bold vision — particularly since Mars One claims that the entire mission can be built upon technologies that already exist. As its website states, establishing humans on Mars would be “the next giant leap for mankind.”

But engineers at MIT say the project may have to take a step back, at least to reconsider the mission’s technical feasibility.

The MIT researchers developed a detailed settlement-analysis tool to assess the feasibility of the Mars One mission, and found that new technologies will be needed to keep humans alive on Mars.

For example, if all food is obtained from locally grown crops, as Mars One envisions, the vegetation would produce unsafe levels of oxygen, which would set off a series of events that would eventually cause human inhabitants to suffocate. To avoid this scenario, a system to remove excess oxygen would have to be implemented — a technology that has not yet been developed for use in space.

Similarly, the Mars Phoenix lander discovered evidence of ice on the Martian surface in 2008, suggesting that future settlers might be able to melt ice for drinking water — another Mars One goal. But according to the MIT analysis, current technologies designed to “bake” water from soil are not yet ready for deployment, particularly in space.

The team also performed an integrated analysis of spare-parts resupply — how many spare parts would have to be delivered to a Martian colony at each opportunity to keep it going. The researchers found that as the colony grows, spare parts would quickly dominate future deliveries to Mars, making up as much as 62 percent of payloads from Earth.

As for the actual voyage to Mars, the team also calculated the number of rockets required to establish the first four settlers and subsequent crews on the planet, as well as the journey’s cost.

According to the Mars One plan, six Falcon Heavy rockets would be required to send up initial supplies, before the astronauts’ arrival. But the MIT assessment found that number to be “overly optimistic”: The team determined that the needed supplies would instead require 15 Falcon Heavy rockets. The transportation cost for this leg of the mission alone, combined with the astronauts’ launch, would be $4.5 billion — a cost that would grow with additional crews and supplies to Mars. The researchers say this estimate does not include the cost of developing and purchasing equipment for the mission, which would further increase the overall cost.

Olivier de Weck, an MIT professor of aeronautics and astronautics and engineering systems, says the prospect of building a human settlement on Mars is an exciting one. To make this goal a reality, however, will require innovations in a number of technologies and a rigorous systems perspective, he says.

“We’re not saying, black and white, Mars One is infeasible,” de Weck says. “But we do think it’s not really feasible under the assumptions they’ve made. We’re pointing to technologies that could be helpful to invest in with high priority, to move them along the feasibility path.”

“One of the great insights we were able to get was just how hard it is to pull this [mission] off,” says graduate student Sydney Do. “There are just so many unknowns. And to give anyone confidence that they’re going to get there and stay alive — there’s still a lot of work that needs to be done.”

Do and de Weck presented their analysis this month at the International Astronautical Congress in Toronto. Co-authors include MIT graduate students Koki Ho, Andrew Owens, and Samuel Schreiner.

Simulating a day on Mars

The group took a systems-based approach in analyzing the Mars One mission, first assessing various aspects of the mission’s architecture, such as its habitat, life-support systems, spare-parts requirements, and transportation logistics, then looking at how each component contributes to the whole system.

For the habitat portion, Do simulated the day-to-day life of a Mars colonist. Based on the typical work schedule, activity levels, and metabolic rates of astronauts on the International Space Station (ISS), Do estimated that a settler would have to consume about 3,040 calories daily to stay alive and healthy on Mars. He then determined crops that would provide a reasonably balanced diet, including beans, lettuce, peanuts, potatoes, and rice.

Do calculated that producing enough of these crops to sustain astronauts over the long term would require about 200 square meters of growing area, compared with Mars One’s estimate of 50 square meters. If, as the project plans, crops are cultivated within the settlers’ habitat, Do found that they would produce unsafe levels of oxygen that would exceed fire safety thresholds, requiring continuous introduction of nitrogen to reduce the oxygen level. Over time, this would deplete nitrogen tanks, leaving the habitat without a gas to compensate for leaks.

As the air inside the habitat continued to leak, the total atmospheric pressure would drop, creating an oppressive environment that would suffocate the first settler within an estimated 68 days.

Possible solutions, Do says, might include either developing a technology to extract excess oxygen or isolating the crops in a separate greenhouse. The team even considered using nitrogen extracted from the Martian atmosphere, but found that doing so would require a prohibitively large system. Surprisingly, the cheapest option found was to supply all the food required from Earth.

“We found carrying food is always cheaper than growing it locally,” Do says. “On Mars, you need lighting and watering systems, and for lighting, we found it requires 875 LED systems, which fail over time. So you need to provide spare parts for that, making the initial system heavier.”

Twisting the knobs

As the team found, spare parts, over time, would substantially inflate the cost of initial and future missions to Mars. Owens, who assessed the resupply of spare parts, based his analysis on reliability data derived from NASA repair logs for given components on the ISS.

“The ISS is based on the idea that if something breaks, you can call home and get a new part quickly,” says Owens. “If you want a spare part on Mars, you have to send it when a launch window is open, every 26 months, and then wait 180 days for it to get there. If you could make spares in-situ, that would be a massive savings.”

Owens points to technologies such as 3-D printing, which may enable settlers to manufacture spare parts on Mars. But the technology as it exists today is not advanced enough to reproduce the exact dimensions and functions of many space-rated parts. The MIT analysis found that 3-D printers will have to improve by leaps, or else the entire Mars settlement infrastructure will have to be redesigned so that its parts can be printed with existing technology.

While this analysis may make the Mars One program look daunting, the researchers say the settlement-analysis tool they’ve developed may help determine the feasibility of various scenarios. For example, rather than sending crews on one-way trips to the planet, what would the overall mission cost be if crews were occasionally replaced?

“Mars One is a pretty radical idea,” Schreiner says. “Now we’ve built a tool that we can play around with, and we can twist some of the knobs to see how the cost and feasibility of the mission changes.”

Tracy Gill, a technology strategy manager at NASA, says the tool may be applicable for assessing other missions to Mars, and points to a few scenarios that the group may want to explore using the settlement-analysis tool.

“This [tool] can provide a benefit to mission planners by allowing them to evaluate a larger spectrum of mission architectures with better confidence in their analysis,” says Gill, who did not contribute to the research. “Included among those architectures would be options ranging from completely growing all food in situ with bioregenerative systems, to packaging all food products from Earth, to various combination of those two extremes.“

Some of the students on this project were supported by NASA fellowships.

Related Research Paper: An Independent Assessment of the Technical Feasibility of the Mars One Mission Plan

Image: Bryan Versteeg/Mars One

Sieve of Eratosthenes

From Wikipedia, the free encyclopedia

 

Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime's square).

In mathematics, the sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit.

It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime. This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.

The earliest known reference to the sieve (Ancient Greek: κόσκινον Ἐρατοσθένους, kóskinon Eratosthénous) is in Nicomachus of Gerasa's Introduction to Arithmetic, which describes it and attributes it to Eratosthenes of Cyrene, a Greek mathematician.

One of a number of prime number sieves, it is one of the most efficient ways to find all of the smaller primes. It may be used to find primes in arithmetic progressions.

Overview

Sift the Two's and Sift the Three's,
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime.

Anonymous
 

A prime number is a natural number that has exactly two distinct natural number divisors: 1 and itself.

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

1. Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
   
2. Initially, let p equal 2, the smallest prime number.
   
3. Enumerate the multiples of p by counting to n from 2p in increments of p, and mark them in the list (these will be 2p, 3p, 4p, ...; the p itself should not be marked).
   
4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
   
5. When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.

The main idea here is that every value given to p will be prime, because if it were composite it would be marked as a multiple of some other, smaller prime. Note that some of the numbers may be marked more than once (e.g., 15 will be marked both for 3 and 5).

As a refinement, it is sufficient to mark the numbers in step 3 starting from p², as all the smaller multiples of p will have already been marked at that point. This means that the algorithm is allowed to terminate in step 4 when p² is greater than n.

Another refinement is to initially list odd numbers only, (3, 5, ..., n), and count in increments of 2p from p² in step 3, thus marking only odd multiples of p. This actually appears in the original algorithm. This can be generalized with wheel factorization, forming the initial list only from numbers coprime with the first few primes and not just from odds (i.e., numbers coprime with 2), and counting in the correspondingly adjusted increments so that only such multiples of p are generated that are coprime with those small primes, in the first place.

Algorithm and variants

Pseudocode

The sieve of Eratosthenes can be expressed in pseudocode, as follows:

 Input: an integer n > 1.
 
 Let A be an array of Boolean values, indexed by integers 2 to n,
 initially all set to true.
 
 for i = 2, 3, 4, ..., not exceeding √n:
   if A[i] is true:
     for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n:
       A[j] := false.
 
 Output: all i such that A[i] is true.

This algorithm produces all primes not greater than n. It includes a common optimization, which is to start enumerating the multiples of each prime i from i². The time complexity of this algorithm is O(n log log n), provided the array update is an O(1) operation, as is usually the case.

Segmented sieve

As Sorenson notes, the problem with the sieve of Eratosthenes is not the number of operations it performs but rather its memory requirements. For large n, the range of primes may not fit in memory; worse, even for moderate n, its cache use is highly suboptimal. The algorithm walks through the entire array A, exhibiting almost no locality of reference.

A solution to these problems is offered by segmented sieves, where only portions of the range are sieved at a time. These have been known since the 1970s, and work as follows:

1. Divide the range 2 through n into segments of some size Δ ≤ √n.
   
2. Find the primes in the first (i.e. the lowest) segment, using the regular sieve.
   
3. For each of the following segments, in increasing order, with m being the segment's topmost value, find the primes in it as follows:
   
   
   1. Set up a Boolean array of size Δ, and
   2. Eliminate from it the multiples of each prime p ≤ √m found so far, by calculating the lowest multiple of p between m - Δ and m, and enumerating its multiples in steps of p as usual, marking the corresponding positions in the array as non-prime.

If Δ is chosen to be √n, the space complexity of the algorithm is O(√n), while the time complexity is the same as that of the regular sieve.

For ranges with upper limit n so large that the sieving primes below √n as required by the page segmented sieve of Eratosthenes cannot fit in memory, a slower but much more space-efficient sieve like the sieve of Sorenson can be used instead.

Incremental sieve

An incremental formulation of the sieve generates primes indefinitely (i.e., without an upper bound) by interleaving the generation of primes with the generation of their multiples (so that primes can be found in gaps between the multiples), where the multiples of each prime p are generated directly by counting up from the square of the prime in increments of p (or 2p for odd primes). The generation must be initiated only when the prime's square is reached, to avoid adverse effects on efficiency. It can be expressed symbolically under the dataflow paradigm as

  primes = [2, 3, ...]\[[p², p²+p, ...] for p in primes],

using list comprehension notation with \ denoting set subtraction of arithmetic progressions of numbers.

Primes can also be produced by iteratively sieving out the composites through divisibility testing by sequential primes, one prime at a time. It is not the sieve of Eratosthenes but is often confused with it, even though the sieve of Eratosthenes directly generates the composites instead of testing for them. Trial division has worse theoretical complexity than that of the sieve of Eratosthenes in generating ranges of primes.

When testing each prime, the optimal trial division algorithm uses all prime numbers not exceeding its square root, whereas the sieve of Eratosthenes produces each composite from its prime factors only, and gets the primes "for free", between the composites. The widely known 1975 functional sieve code by David Turner is often presented as an example of the sieve of Eratosthenes but is actually a sub-optimal trial division sieve.

Computational analysis

The work performed by this algorithm is almost entirely the operations to cull the composite number representations which for the basic non-optimized version is the sum of the range divided by each of the primes up to that range or

${\displaystyle n\sum _{p\leq n}{\frac {1}{p}},}$

where n is the sieving range in this and all further analysis.

By rearranging Mertens' second theorem, this is equal to n ( log log n + M ) as n approaches infinity, where M is the Meissel–Mertens constant of about

0.2614972128476427837554268386086958590516...

The optimization of starting at the square of each prime and only culling for primes less than the square root changes the "n" in the above expression to √n (or n^1/2) and not culling until the square means that the sum of the base primes each minus two is subtracted from the operations. As the sum of the first x primes is 1/2x² log x and the prime number theorem says that x is approximately x/log x, then the sum of primes to n is n²/2 log n, and therefore the sum of base primes to √n is 1/log n expressed as a factor of n. The extra offset of two per base prime is 2π(√n), where π is the prime-counting function in this case, or 4√n/log n; expressing this as a factor of n as are the other terms, this is 4/√n log n. Combining all of this, the expression for the number of optimized operations without wheel factorization is

${\displaystyle \log \log n-{\frac {1}{\log n}}\left(1-{\frac {4}{\sqrt {n}}}\right)+M-\log 2.}$

For the wheel factorization cases, there is a further offset of the operations not done of

${\displaystyle \sum _{p\leq x}{\frac {1}{p}}}$

where x is the highest wheel prime and a constant factor of the whole expression is applied which is the fraction of remaining prime candidates as compared to the repeating wheel circumference. The wheel circumference is

${\displaystyle \prod _{p\leq x}p}$

and it can easily be determined that this wheel factor is

${\displaystyle \prod _{p\leq x}{\frac {p-1}{p}}}$

as p − 1/p is the fraction of remaining candidates for the highest wheel prime, x, and each succeeding smaller prime leaves its corresponding fraction of the previous combined fraction.

Combining all of the above analysis, the total number of operations for a sieving range up to n including wheel factorization for primes up to x is approximately

${\displaystyle \prod _{p\leq x}{\frac {p-1}{p}}\left(\log \log n-{\frac {1}{\log n}}\left(1-{\frac {4}{\sqrt {n}}}\right)+M-\log 2-\sum _{p\leq x}{\frac {1}{p}}\right)}$.

To show that the above expression is a good approximation to the number of composite number cull operations performed by the algorithm, following is a table showing the actually measured number of operations for a practical implementation of the sieve of Eratosthenes as compared to the number of operations predicted from the above expression with both expressed as a fraction of the range (rounded to four decimal places) for different sieve ranges and wheel factorizations (Note that the last column is a maximum practical wheel as to the size of the wheel gaps Look Up Table - almost 10 million values):

n	no wheel		odds		2/3/5 wheel		2/3/5/7 wheel		2/3/5/7/11/13/17/19 wheel
103	1.4090	1.3745	0.4510	0.4372	0.1000	0.0909	0.0580	0.0453	0.0060	—
104	1.6962	1.6844	0.5972	0.5922	0.1764	0.1736	0.1176	0.1161	0.0473	0.0391
105	1.9299	1.9261	0.7148	0.7130	0.2388	0.2381	0.1719	0.1714	0.0799	0.0805
106	2.1218	2.1220	0.8109	0.8110	0.2902	0.2903	0.2161	0.2162	0.1134	0.1140
107	2.2850	2.2863	0.8925	0.8932	0.3337	0.3341	0.2534	0.2538	0.1419	0.1421
108	2.4257	2.4276	0.9628	0.9638	0.3713	0.3718	0.2856	0.2860	0.1660	0.1662

The above table shows that the above expression is a very good approximation to the total number of culling operations for sieve ranges of about a hundred thousand (10⁵) and above.

Algorithmic complexity

The sieve of Eratosthenes is a popular way to benchmark computer performance. As can be seen from the above by removing all constant offsets and constant factors and ignoring terms that tend to zero as n approaches infinity, the time complexity of calculating all primes below n in the random access machine model is O(n log log n) operations, a direct consequence of the fact that the prime harmonic series asymptotically approaches log log n. It has an exponential time complexity with regard to input size, though, which makes it a pseudo-polynomial algorithm. The basic algorithm requires O(n) of memory.

The bit complexity of the algorithm is O(n (log n) (log log n)) bit operations with a memory requirement of O(n).

The normally implemented page segmented version has the same operational complexity of O(n log log n) as the non-segmented version but reduces the space requirements to the very minimal size of the segment page plus the memory required to store the base primes less than the square root of the range used to cull composites from successive page segments of size O(√n/log n).

A special rarely if ever implemented segmented version of the sieve of Eratosthenes, with basic optimizations, uses O(n) operations and O(√nlog log n/log n) bits of memory.

To show that the above approximation in complexity is not very accurate even for about as large as practical a range, the following is a table of the estimated number of operations as a fraction of the range rounded to four places, the calculated ratio for a factor of ten change in range based on this estimate, and the factor based on the log log n estimate for various ranges and wheel factorizations (the combo column uses a frequently practically used pre-cull by the maximum wheel factorization but only the 2/3/5/7 wheel for the wheel factor as the full factorization is difficult to implement efficiently for page segmentation):

n	no wheel			odds			2/3/5 wheel			2/3/5/7 wheel			combo wheel			2/3/5/7/11/13/17/19 wheel
106	2.122	1.102	1.075	0.811	1.137	1.075	0.2903	1.22	1.075	0.2162	1.261	1.075	0.1524	1.416	1.075	0.114	1.416	1.075
107	2.2863	1.077	1.059	0.8932	1.101	1.059	0.3341	1.151	1.059	0.2537	1.174	1.059	0.1899	1.246	1.059	0.1421	1.246	1.059
108	2.4276	1.062	1.048	0.9638	1.079	1.048	0.3718	1.113	1.048	0.286	1.127	1.048	0.2222	1.17	1.048	0.1662	1.17	1.048
109	2.5514	1.051	1.04	1.0257	1.064	1.04	0.4048	1.089	1.04	0.3143	1.099	1.04	0.2505	1.127	1.04	0.1874	1.127	1.04
1010	2.6615	1.043	1.035	1.0808	1.054	1.035	0.4342	1.073	1.035	0.3395	1.08	1.035	0.2757	1.101	1.035	0.2063	1.101	1.035
1011	2.7608	1.037	1.03	1.1304	1.046	1.03	0.4607	1.061	1.03	0.3622	1.067	1.03	0.2984	1.082	1.03	0.2232	1.082	1.03
1012	2.8511	1.033	1.027	1.1755	1.04	1.027	0.4847	1.052	1.027	0.3828	1.057	1.027	0.319	1.069	1.027	0.2387	1.069	1.027
1013	2.9339	1.029	1.024	1.217	1.035	1.024	0.5068	1.046	1.024	0.4018	1.049	1.024	0.3379	1.059	1.024	0.2528	1.059	1.024
1014	3.0104	1.026	1.022	1.2552	1.031	1.022	0.5272	1.04	1.022	0.4193	1.044	1.022	0.3554	1.052	1.022	0.2659	1.052	1.022
1015	3.0815	1.024	1.02	1.2907	1.028	1.02	0.5462	1.036	1.02	0.4355	1.039	1.02	0.3717	1.046	1.02	0.2781	1.046	1.02
1016	3.1478	1.022	1.018	1.3239	1.026	1.018	0.5639	1.032	1.018	0.4507	1.035	1.018	0.3868	1.041	1.018	0.2894	1.041	1.018

The above shows that the log log n estimate is not very accurate even for maximum practical ranges of about 10¹⁶. One can see why it does not match by looking at the computational analysis above and seeing that within these practical sieving range limits, there are very significant constant offset terms such that the very slowly growing log log n term does not get large enough so as to make these terms insignificant until the sieving range approaches infinity – well beyond any practical sieving range. Within these practical ranges, these significant constant offsets mean that the performance of the Sieve of Eratosthenes is much better than one would expect just using the asymptotic time complexity estimates by a significant amount, but that also means that the slope of the performance with increasing range is steeper than predicted as the benefit of the constant offsets becomes slightly less significant.

One should also note that in using the calculated operation ratios to the sieve range, it must be less than about 0.2587 in order to be faster than the often compared sieve of Atkin if the operations take approximately the same time each in CPU clock cycles, which is a reasonable assumption for the one huge bit array algorithm. Using that assumption, the sieve of Atkin is only faster than the maximally wheel factorized sieve of Eratosthenes for ranges of over 10¹³ at which point the huge sieve buffer array would need about a quarter of a terabyte (about 250 gigabytes) of RAM memory even if bit packing were used. An analysis of the page segmented versions will show that the assumption that the time per operation stays the same between the two algorithms does not hold for page segmentation and that the sieve of Atkin operations get slower much faster than the sieve of Eratosthenes with increasing range. Thus for practical purposes, the maximally wheel factorized Sieve of Eratosthenes is faster than the Sieve of Atkin although the Sieve of Atkin is faster for lesser amounts of wheel factorization.

Using big O notation is also not the correct way to compare practical performance of even variations of the Sieve of Eratosthenes as it ignores constant factors and offsets that may be very significant for practical ranges: The sieve of Eratosthenes variation known as the Pritchard wheel sieve has an O(n) performance, but its basic implementation requires either a "one large array" algorithm which limits its usable range to the amount of available memory else it needs to be page segmented to reduce memory use. When implemented with page segmentation in order to save memory, the basic algorithm still requires about O(n/log n) bits of memory (much more than the requirement of the basic page segmented sieve of Eratosthenes using O(√n/log n) bits of memory). Pritchard's work reduced the memory requirement to the limit as described above the table, but the cost is a fairly large constant factor of about three in execution time to about three quarters the sieve range due to the complex computations required to do so. As can be seen from the above table for the basic sieve of Eratosthenes, even though the resulting wheel sieve has O(n) performance and an acceptable memory requirement, it will never be faster than a reasonably Wheel Factorized basic sieve of Eratosthenes for any practical sieving range by a factor of about two. Other than that it is quite complex to implement, it is rarely practically implemented because it still uses more memory than the basic Sieve of Eratosthenes implementations described here as well as being slower for practical ranges. It is thus more of an intellectual curiosity than something practical.

Euler's Sieve

Euler's proof of the zeta product formula contains a version of the sieve of Eratosthenes in which each composite number is eliminated exactly once. The same sieve was rediscovered and observed to take linear time by Gries & Misra (1978). It, too, starts with a list of numbers from 2 to n in order. On each step the first element is identified as the next prime and the results of multiplying this prime with each element of the list are marked in the list for subsequent deletion. The initial element and the marked elements are then removed from the working sequence, and the process is repeated:

 [2] (3) 5  7  9  11  13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79  ...
 [3]    (5) 7     11  13    17 19    23 25    29 31    35 37    41 43    47 49    53 55    59 61    65 67    71 73    77 79  ...
 [4]       (7)    11  13    17 19    23       29 31       37    41 43    47 49    53       59 61       67    71 73    77 79  ...
 [5]             (11) 13    17 19    23       29 31       37    41 43    47       53       59 61       67    71 73       79  ...
 [...]

Here the example is shown starting from odds, after the first step of the algorithm. Thus, on the kth step all the remaining multiples of the kth prime are removed from the list, which will thereafter contain only numbers coprime with the first k primes (cf. wheel factorization), so that the list will start with the next prime, and all the numbers in it below the square of its first element will be prime too.

Thus, when generating a bounded sequence of primes, when the next identified prime exceeds the square root of the upper limit, all the remaining numbers in the list are prime. In the example given above that is achieved on identifying 11 as next prime, giving a list of all primes less than or equal to 80.

Note that numbers that will be discarded by a step are still used while marking the multiples in that step, e.g., for the multiples of 3 it is 3 × 3 = 9, 3 × 5 = 15, 3 × 7 = 21, 3 × 9 = 27, ..., 3 × 15 = 45, ..., so care must be taken dealing with this.