tag:theconversation.com,2011:/uk/topics/millennium-prize-1938/articlesMillennium Prize – The Conversation2011-12-22T00:55:41Ztag:theconversation.com,2011:article/47732011-12-22T00:55:41Z2011-12-22T00:55:41ZCalls for a posthumous pardon … but who was Alan Turing?<figure><img src="https://images.theconversation.com/files/6616/original/hq5fybbh-1324357407.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=496&fit=clip" /><figcaption><span class="caption">Momentum is gathering behind calls to pardon the father of computer science.</span> <span class="attribution"><span class="source">BinaryApe</span></span></figcaption></figure><p>You may have read the British Government is <a href="http://epetitions.direct.gov.uk/petitions/23526">being petitioned</a> to grant a posthumous pardon to one of the world’s greatest mathematicians and most successful codebreakers, Alan Turing. You may also have read that Turing was was convicted of gross indecency in 1952 and died tragically two years later. </p>
<p>But who, exactly, was he? </p>
<p>Born in London in 1912, Turing helped lay the foundations of the “information age” we live in. </p>
<p>He did his first degree at King’s College, Cambridge, and then became a Fellow there. His first big contribution was his development of a mathematical model of computation in 1936. This became known as the <a href="http://mathworld.wolfram.com/TuringMachine.html">Turing Machine</a>. </p>
<p>It was not the first time a computer had been envisaged: that distinction belonged to <a href="http://www.gap-system.org/%7Ehistory/Biographies/Babbage.html">Charles Babbage</a>, a 19th century mathematician who designed a computer based on mechanical technology and built parts of it (some of which may be seen at the <a href="http://www.sciencemuseum.org.uk/">Science Museum</a> in London or <a href="http://www.powerhousemuseum.com/">Powerhouse Museum</a> in Sydney, for example).</p>
<p>But Babbage’s design was necessarily complicated, as he aimed for a working device using specific technology. Turing’s design was independent of any particular technology, and was not intended to be built. </p>
<figure class="align-right ">
<img alt="" src="https://images.theconversation.com/files/6613/original/6pd735r5-1324357079.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=237&fit=clip" srcset="https://images.theconversation.com/files/6613/original/6pd735r5-1324357079.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=600&h=866&fit=crop&dpr=1 600w, https://images.theconversation.com/files/6613/original/6pd735r5-1324357079.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=600&h=866&fit=crop&dpr=2 1200w, https://images.theconversation.com/files/6613/original/6pd735r5-1324357079.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=600&h=866&fit=crop&dpr=3 1800w, https://images.theconversation.com/files/6613/original/6pd735r5-1324357079.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&h=1089&fit=crop&dpr=1 754w, https://images.theconversation.com/files/6613/original/6pd735r5-1324357079.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=754&h=1089&fit=crop&dpr=2 1508w, https://images.theconversation.com/files/6613/original/6pd735r5-1324357079.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=754&h=1089&fit=crop&dpr=3 2262w" sizes="(min-width: 1466px) 754px, (max-width: 599px) 100vw, (min-width: 600px) 600px, 237px">
<figcaption>
<span class="caption">The now iconic shot of Alan Turing.</span>
</figcaption>
</figure>
<p>It was very simple, and would be very inefficient and impractical as a device for doing real computations. But its simplicity meant it could be used to do mathematical reasoning about computation.</p>
<p>Turing used his abstract machines to investigate what kinds of things could be computed. He found some tasks which, although perfectly well defined and mathematically precise, are <em>uncomputable</em>. The first of these is known as the <a href="http://plus.maths.org/content/os/issue5/turing/index">halting problem</a>, which asks, for any given computation, whether it will ever stop. Turing showed that this was uncomputable: there is no systematic method that always gives the right answer.</p>
<p>So, if you have ever wanted a program that can run on your laptop and test all your other software to determine which of them might cause your laptop to “hang” or get stuck in a never-ending loop, the bad news is such a comprehensive testing program cannot be written.</p>
<p>Uncomputability is not confined to questions about the behaviour of computer programs. Since Turing’s work, many problems in mainstream mathematics have been found to be uncomputable. For example, the Russian mathematician and computer scientist, <a href="http://en.wikipedia.org/wiki/Yuri_Matiyasevich">Yuri Matiyasevich</a>, showed in 1970 that determining if a polynomial equation with several variables has a solution consisting only of whole numbers is also an uncomputable problem.</p>
<p>Turing machines have been used to define measures of the efficiency of computations. They underpin formal statements of the <a href="https://theconversation.com/millennium-prize-p-vs-np-4246">P vs NP problem</a>, one of the <a href="https://theconversation.com/topics/millennium-prize">Millennium Prize problems</a>.</p>
<p>Another important feature of Turing’s model is its capacity to treat programs as data. This means the programs that tell computers what to do can themselves, after being represented in symbolic form, be given as input to other programs. Turing Machines that can take any program as input, and run that program on some input data, are called <a href="http://introcs.cs.princeton.edu/java/75universality/">Universal Turing Machines</a>. </p>
<p>These are really conceptual precursors of today’s computers, which are <a href="http://www.computer50.org/mark1/stored.html">stored-program computers</a>, in that they can treat programs as data in this sense. The oldest surviving intact computer in the world, in this most complete sense of the term, is <a href="http://museumvictoria.com.au/melbournemuseum/whatson/current-exhibitions/csirac/">CSIRAC</a> at Melbourne Museum.</p>
<figure class="align-center zoomable">
<a href="https://images.theconversation.com/files/6678/original/fzth4868-1324429890.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=1000&fit=clip"><img alt="" src="https://images.theconversation.com/files/6678/original/fzth4868-1324429890.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&fit=clip" srcset="https://images.theconversation.com/files/6678/original/fzth4868-1324429890.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=600&h=253&fit=crop&dpr=1 600w, https://images.theconversation.com/files/6678/original/fzth4868-1324429890.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=600&h=253&fit=crop&dpr=2 1200w, https://images.theconversation.com/files/6678/original/fzth4868-1324429890.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=600&h=253&fit=crop&dpr=3 1800w, https://images.theconversation.com/files/6678/original/fzth4868-1324429890.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&h=318&fit=crop&dpr=1 754w, https://images.theconversation.com/files/6678/original/fzth4868-1324429890.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=754&h=318&fit=crop&dpr=2 1508w, https://images.theconversation.com/files/6678/original/fzth4868-1324429890.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=754&h=318&fit=crop&dpr=3 2262w" sizes="(min-width: 1466px) 754px, (max-width: 599px) 100vw, (min-width: 600px) 600px, 237px"></a>
<figcaption>
<span class="caption">CSIRAC was Australia’s first digital computer, and the fourth “stored program” computer in the world.</span>
<span class="attribution"><span class="source">Melbourne Museum</span></span>
</figcaption>
</figure>
<p>It seems a mathematical model of computation was an idea whose time had come. In 1936, the year of Turing’s result, another model of computation was published by <a href="http://www.gap-system.org/%7Ehistory/Biographies/Church.html">Alonzo Church</a> of Princeton University. Although Turing and Church took quite different routes, they ended up at the same place, in that the two models give exactly the same notion of computability. </p>
<p>In other words, the classification of tasks into computable and uncomputable is independent of which of these two models is used. </p>
<p>Other models of computation have been proposed, but mostly they seem to lead to the same view of what is and is not computable. The <a href="http://mathworld.wolfram.com/Church-TuringThesis.html">Church-Turing Thesis</a> states that this class of computable functions does indeed capture exactly those things which can be computed in principle (say by a human with unlimited time, paper and ink, who works methodically and makes no mistakes). </p>
<p>It implies Turing Machines give a faithful mathematical model of computation. This is not a formal mathematical result, but rather a working assumption which is now widely accepted.</p>
<p>Turing went to Princeton and completed his PhD under Church, returning to Britain in 1938.</p>
<p>Early in the Second World War, Turing joined the British codebreaking operation at <a href="http://www.bletchleypark.org/">Bletchley Park</a>, north-west of London. He became one of its most valuable assets. He was known by the nickname “Prof” and was described by colleague <a href="http://www.telegraph.co.uk/news/obituaries/military-obituaries/special-forces-obituaries/5132599/Professor-Jack-Good.html">Jack Good</a> as “a deep rather than a fast thinker”.</p>
<figure class="align-right ">
<img alt="" src="https://images.theconversation.com/files/6606/original/zhfkdjby-1324356711.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=237&fit=clip" srcset="https://images.theconversation.com/files/6606/original/zhfkdjby-1324356711.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=600&h=800&fit=crop&dpr=1 600w, https://images.theconversation.com/files/6606/original/zhfkdjby-1324356711.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=600&h=800&fit=crop&dpr=2 1200w, https://images.theconversation.com/files/6606/original/zhfkdjby-1324356711.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=600&h=800&fit=crop&dpr=3 1800w, https://images.theconversation.com/files/6606/original/zhfkdjby-1324356711.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&h=1005&fit=crop&dpr=1 754w, https://images.theconversation.com/files/6606/original/zhfkdjby-1324356711.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=754&h=1005&fit=crop&dpr=2 1508w, https://images.theconversation.com/files/6606/original/zhfkdjby-1324356711.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=754&h=1005&fit=crop&dpr=3 2262w" sizes="(min-width: 1466px) 754px, (max-width: 599px) 100vw, (min-width: 600px) 600px, 237px">
<figcaption>
<span class="caption">One of the famous Enigma machines decrypted at Bletchley Park.</span>
<span class="attribution"><span class="source">Keir David</span></span>
</figcaption>
</figure>
<p>At the time, Germany was using an encryption device known as <a href="http://www.bletchleypark.org/content/machines.rhtm">Enigma</a> for much of its communications. This was widely regarded as completely secure. The British had already obtained an Enigma machine, from the Poles, and building on their work, Turing and colleague Gordon Welchman worked out how the Enigma-encrypted messages collected by the British could be decrypted. </p>
<p>Turing designed a machine called the <a href="http://www.ellsbury.com/enigmabombe.htm">Bombe</a>, named after a Polish ice cream, which worked by testing large numbers of combinations of Enigma machine configurations, in order to help decrypt secret messages. These messages yielded information of incalculable value to the British. Winston Churchill described the Bletchley Park codebreakers as “geese that laid the golden eggs but never cackled”.</p>
<p>In 1945, after the war, Turing joined the <a href="http://www.npl.co.uk/">National Physical Laboratory</a> (NPL), where he wrote a report on how to construct an electronic computer, this time a general-purpose one unlike the machines dedicated to cryptanalysis which he helped to design at Bletchley Park. </p>
<p>This report led to the construction of an early computer (<a href="http://www.alanturing.net/turing_archive/archive/infopages/london1st.html">Pilot ACE</a>) at NPL in 1950. By then, Turing had already moved on to Manchester University, where he worked on the first general-purpose stored-program computer in the world, the <a href="http://www.computer50.org/mark1/new.baby.html">Manchester “Baby”</a>.</p>
<figure class="align-left ">
<img alt="" src="https://images.theconversation.com/files/6609/original/k5z3rywz-1324356830.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=237&fit=clip" srcset="https://images.theconversation.com/files/6609/original/k5z3rywz-1324356830.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=600&h=450&fit=crop&dpr=1 600w, https://images.theconversation.com/files/6609/original/k5z3rywz-1324356830.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=600&h=450&fit=crop&dpr=2 1200w, https://images.theconversation.com/files/6609/original/k5z3rywz-1324356830.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=600&h=450&fit=crop&dpr=3 1800w, https://images.theconversation.com/files/6609/original/k5z3rywz-1324356830.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&h=566&fit=crop&dpr=1 754w, https://images.theconversation.com/files/6609/original/k5z3rywz-1324356830.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=754&h=566&fit=crop&dpr=2 1508w, https://images.theconversation.com/files/6609/original/k5z3rywz-1324356830.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=754&h=566&fit=crop&dpr=3 2262w" sizes="(min-width: 1466px) 754px, (max-width: 599px) 100vw, (min-width: 600px) 600px, 237px">
<figcaption>
<span class="caption">The remade Bombe machine at Bletchley Park, England, features miles of circuitry.</span>
<span class="attribution"><span class="source">Keir David</span></span>
</figcaption>
</figure>
<p>In their early days, computers were often called “electronic brains”. Turing began to consider whether a computer could be programmed to simulate human intelligence, which remains a major research challenge today and helped to initiate the field of artificial intelligence.</p>
<p>A fundamental issue in such research is: how do you know if you have succeeded? What test can you apply to a program to determine if it has intelligence? Turing proposed that a program be deemed intelligent if, in its interaction with a human, the human is unable to detect whether he or she is communicating with another human or a computer program. (The test requires a controlled setting, for example where all communication with the human tester is by typed text.)</p>
<p>His paper on this topic – <a href="http://www.turingarchive.org/browse.php/B/9">Computing Machinery and Intelligence</a> – was published in 1950. The artificial intelligence community holds regular competitions to see how good researchers’ programs are at the Turing test.</p>
<figure><div style="text-align:center;">
<figure>
<iframe width="440" height="260" src="https://www.youtube.com/embed/jq0ELhpKevY?wmode=transparent&start=24" frameborder="0" allowfullscreen=""></iframe>
</figure>
</div></figure>
<p>The honours Turing received during his lifetime included an OBE in 1945 and becoming a Fellow of the Royal Society in 1951.</p>
<p>His wartime contributions remained secret throughout his life and for many years afterwards.</p>
<p>In 1952 he was arrested for homosexuality, which was illegal in Britain at the time. Turing was found guilty and required to undergo “treatment” with drugs. This conviction also meant he lost his security clearance. </p>
<p>In 1954 he ingested some cyanide, probably via an apple, and died. An inquest classified his death as suicide, and this is generally accepted today. But some at the time, including his mother, contended his death was an accidental consequence of poor handling of chemicals during some experiments he was conducting at home in his spare time.</p>
<figure class="align-right ">
<img alt="" src="https://images.theconversation.com/files/6617/original/mk2k9b6g-1324357525.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=237&fit=clip" srcset="https://images.theconversation.com/files/6617/original/mk2k9b6g-1324357525.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=600&h=800&fit=crop&dpr=1 600w, https://images.theconversation.com/files/6617/original/mk2k9b6g-1324357525.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=600&h=800&fit=crop&dpr=2 1200w, https://images.theconversation.com/files/6617/original/mk2k9b6g-1324357525.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=600&h=800&fit=crop&dpr=3 1800w, https://images.theconversation.com/files/6617/original/mk2k9b6g-1324357525.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&h=1005&fit=crop&dpr=1 754w, https://images.theconversation.com/files/6617/original/mk2k9b6g-1324357525.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=754&h=1005&fit=crop&dpr=2 1508w, https://images.theconversation.com/files/6617/original/mk2k9b6g-1324357525.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=754&h=1005&fit=crop&dpr=3 2262w" sizes="(min-width: 1466px) 754px, (max-width: 599px) 100vw, (min-width: 600px) 600px, 237px">
<figcaption>
<span class="caption"></span>
<span class="attribution"><span class="source">Dino Gravalo.</span></span>
</figcaption>
</figure>
<p>The irony of Turing losing his security clearance – after the advantage his work had given Britain in the war, in extraordinary secrecy – is clear. </p>
<p>The magnitude of what was done to him has become increasingly plain over time, helped by greater availability of information about the work at Bletchley Park and changing social attitudes to homosexuality.</p>
<p>Next year, 2012, will be the centenary of Turing’s birth – with <a href="http://www.turingcentenary.eu">events planned globally</a> to celebrate the man and his contribution. As this year approached, a movement developed to recognise Turing’s contribution and atone for what was done to him. In 2009, British Prime Minister, Gordon Brown, responding to a petition, <a href="http://www.telegraph.co.uk/news/politics/gordon-brown/6170112/Gordon-Brown-Im-proud-to-say-sorry-to-a-real-war-hero.html">issued a formal apology</a> on behalf of the British government for the way Turing was treated. </p>
<p><strong>_The E-petition for a pardon for Alan Turing can be found by <a href="http://epetitions.direct.gov.uk/petitions/23526">clicking here</a>.<br>
_</strong></p><img src="https://counter.theconversation.com/content/4773/count.gif" alt="The Conversation" width="1" height="1" />
<p class="fine-print"><em><span>Graham Farr receives funding from the Australian Research Council.</span></em></p>You may have read the British Government is being petitioned to grant a posthumous pardon to one of the world’s greatest mathematicians and most successful codebreakers, Alan Turing. You may also have…Graham Farr, Associate Professor, Clayton School of IT, Monash UniversityLicensed as Creative Commons – attribution, no derivatives.tag:theconversation.com,2011:article/38482011-12-08T19:38:57Z2011-12-08T19:38:57ZMillennium Prize: the Yang-Mills Existence and Mass Gap problem<figure><img src="https://images.theconversation.com/files/6193/original/zv8k4cn9-1323218279.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=496&fit=clip" /><figcaption><span class="caption">There's a contradiction between classical and quantum theories.</span> <span class="attribution"><span class="source">TonZ</span></span></figcaption></figure><p><strong>MILLENNIUM PRIZE SERIES:</strong> <strong><em>The Millennium Prize Problems are seven mathematics problems laid out by the Clay Mathematics Institute in 2000. They’re not easy</em>—_ a correct solution to any one results in a US$1,000,000 prize being awarded by the institute_.</strong> </p>
<p><strong><em>Russian mathematician Grigori Perelman was awarded the Prize on March 18 last year for solving one of the problems, the Poincaré conjecture—as yet the only problem that’s been solved. Famously, he turned down the $1,000,000 Millennium Prize.</em></strong></p>
<p><strong><em>In the last instalment of our series, Peter Bouwknegt, Alan Carey and Michael Murray – experts from <a href="http://theconversation.com/institutions/the-australian-mathematical-sciences-institute">Australian Mathematical Sciences Institute</a> (AMSI) member institutions – explain the Yang-Mills Existence and Mass Gap problem.</em></strong></p>
<p><strong><em>Enjoy.</em></strong></p>
<p>One of the outstanding discoveries made in the early part of the last century was that of the quantum behaviour of the physical world. At very short distances, such as the size of an atom and smaller, the world behaves very differently to the “classical” world we are used to. </p>
<p>Typical of the quantum world is so-called <a href="http://hyperphysics.phy-astr.gsu.edu/hbase/mod1.html">wave-particle duality</a>: particles such as electrons behave sometimes as if they are point particles with a definite position, and sometimes as if they are spread out like waves. </p>
<p>This strange behaviour is not just of theoretical interest, since it is underpins <a href="http://theconversation.com/explainer-quantum-physics-570">much of our modern technology</a>. It is fundamental to the behaviour of semiconductors in all our electronic devices, the behaviour of nano-materials, and the current rise of quantum computing.</p>
<p><a href="http://www.thebigview.com/spacetime/quantumtheory.html">Quantum theory</a> is fundamental. It must govern not just the very small but also the classical realm. That means physicists and mathematicians have had to develop methods not just for understanding new quantum phenomena, but also for replacing classical theories by their quantum analogues. </p>
<p>This is the process of [quantization.](http://en.wikipedia.org/wiki/Quantization_(physics) When we have a finite number of degrees of freedom, such as for a finite collection of particles, although the quantum behaviour is often counter-intuitive, we have a well-developed mathematical machinery to handle this quantization called quantum mechanics. </p>
<p>This is well understood physically and mathematically. But when we move to study the electric and magnetic fields where we have an infinite number of degrees of freedom, the situation is much more complicated. With the development of so-called <a href="http://plato.stanford.edu/entries/quantum-field-theory/">quantum field theory</a>, a quantum theory for fields, physics has made progress that mathematically we do not completely understand.</p>
<h2>What’s the problem?</h2>
<p>Many field theories fall into a class called <a href="http://mathworld.wolfram.com/GaugeTheory.html">gauge field theories</a>, where a particular collection of symmetries, called the gauge group, acts on the fields and particles. In the case that these symmetries all commute, so-called <a href="http://www.claymath.org/millennium/Yang-Mills_Theory/yangmills.pdf">abelian gauge theories</a>, we have a reasonable understanding of the quantization. </p>
<p>This includes the case of the electromagnetic field, <a href="http://hyperphysics.phy-astr.gsu.edu/hbase/forces/qed.html">quantum electrodynamics</a>, for which the theory makes impressively accurate predictions.</p>
<p>The first example of a <a href="http://mathworld.wolfram.com/Non-Abelian.html">non-abelian</a> theory that arose historically is the theory of the <a href="http://www2.slac.stanford.edu/vvc/theory/electroweak.html">electro-weak interaction</a>, which requires a mechanism to make the predicted particles massive as we observe them in nature. This involves the so-called <a href="http://theconversation.com/explainer-the-higgs-boson-particle-280">Higgs boson</a>, which is currently being searched for with the <a href="http://theconversation.com/is-the-large-hadron-collider-a-time-machine-447">Large Hadron Collider</a> (LHC) at CERN. </p>
<p>The notable feature of this theory for our present discussion is that the Higgs mechanism is classical and carries over to the quantum theory under the quantization process.</p>
<p>The case of interest in the Millennium Problem “Yang-Mills theory and Mass-Gap” is Yang-Mills gauge theory, a non-abelian theory which we expect to describe quarks and the strong force that binds the nucleus and powers the sun. Here we encounter a contradiction between the classical and quantum theories. </p>
<p>The classical theory predicts massless particles and long-range forces. The quantum theory has to match the real world with short-range forces and massive particles. Physicists expect various mathematical properties such as the “mass gap” and “<a href="http://cerncourier.com/cws/article/cern/27905">asymptotic freedom</a>” to explain the non-existence of massless particles in observations of the strong interactions. </p>
<p>As these properties are not visible in the classical theory and arise only in the quantum theory, understanding them means we need a rigorous approach to “quantum Yang-Mills theory”. Currently we do not have the mathematics to do this, although various approximations and simplifications can be done which suggest the quantum theory has the required properties.</p>
<p>The Millennium Problem seeks to establish by rigorous mathematics the existence of the “mass gap” – that is, the non-existence of massless particles in Yang-Mills theory. The solution of the problem would involve an approach to quantum field theory in four dimensions that is sophisticated enough to explain at least this feature of quantum non-abelian Yang-Mills gauge theory.</p>
<h2>Doing the maths</h2>
<p>Clearly this is of interest to physicists, but why is it of importance to mathematicians? It has become apparent in the last few decades that the tools that physicists have developed for doing quantum field theory, in particular <a href="http://www.scholarpedia.org/article/Path_integral">path integrals</a>, make precise predictions about geometry and topology, particularly in low dimensions. </p>
<p>But we don’t know mathematically what a path integral is, except in very simple cases. It is as if we are in a pre-Newtonian world – certain calculations can be done with certain tricks but Newton hasn’t developed calculus for us yet. </p>
<p>Analogously, there are calculations in geometry and topology that can be done non-rigorously using methods developed by physicists in quantum field theory which give the right answers. This suggests that there is a set of powerful techniques waiting to be discovered. </p>
<p>A solution to this Millennium Problem would shed light on what these new techniques are.</p>
<p><strong>This is the seventh and final part of the Millennium Prize Series. To read the other instalments, follow the links below.</strong></p>
<ul>
<li><strong><a href="http://theconversation.com/millenium-prize-the-navier-stokes-existence-and-uniqueness-problem-4244">Part One: Millennium Prize: the Navier–Stokes existence and uniqueness problem</a></strong></li>
<li><strong><a href="http://theconversation.com/millennium-prize-the-hodge-conjecture-4243">Part Two: Millennium Prize: the Hodge Conjecture</a></strong></li>
<li><strong><a href="http://theconversation.com/millennium-prize-p-vs-np-4246">Part Three: Millennium Prize: P vs NP</a></strong></li>
<li><strong><a href="http://theconversation.com/millennium-prize-the-poincar-conjecture-4245">Part Four: Millenium Prize: the Poincaré Conjecture</a></strong></li>
<li><strong><a href="http://theconversation.com/millennium-prize-the-birch-and-swinnerton-dyer-conjecture-4242">Part Five: Millenium Prize: the Birch and Swinnerton-Dyer Conjecture</a></strong></li>
<li><strong><a href="http://theconversation.com/millennium-prize-the-riemann-hypothesis-3847">Part Six: Millennium Prize: the Riemann Hypothesis</a></strong></li>
</ul><img src="https://counter.theconversation.com/content/3848/count.gif" alt="The Conversation" width="1" height="1" />
<p class="fine-print"><em><span>Michael Murray receives funding from The Australian Research Council. He is affiliated with the University of Adelaide.</span></em></p><p class="fine-print"><em><span>Alan Carey receives funding from the Australian Research Council</span></em></p><p class="fine-print"><em><span>Peter Bouwknegt receives funding from the Australian Research Council. He is affiliated with the Australian National University.</span></em></p>MILLENNIUM PRIZE SERIES: The Millennium Prize Problems are seven mathematics problems laid out by the Clay Mathematics Institute in 2000. They’re not easy—_ a correct solution to any one results in a US$1,000,000…Michael Murray, Professor of Pure Mathematics, University of AdelaideAlan Carey, Director of Mathematical Sciences Institute, Australian National UniversityPeter Bouwknegt, Professor of Theoretical Physics and Mathematics, Australian National UniversityLicensed as Creative Commons – attribution, no derivatives.tag:theconversation.com,2011:article/38472011-12-06T19:40:26Z2011-12-06T19:40:26ZMillennium Prize: the Riemann Hypothesis<figure><img src="https://images.theconversation.com/files/6143/original/d6c315ad344e2eef-1323061463.jpg?ixlib=rb-1.1.0&rect=2%2C2%2C1017%2C816&q=45&auto=format&w=496&fit=clip" /><figcaption><span class="caption">What will be the next number in this sequence?</span> <span class="attribution"><span class="source">crisinplymouth</span></span></figcaption></figure><p><strong>MILLENNIUM PRIZE SERIES:</strong> <strong><em>The Millennium Prize Problems are seven mathematics problems laid out by the Clay Mathematics Institute in 2000. They’re not easy</em>—<em>a correct solution to any one results in a US$1,000,000 prize being awarded by the institute</em>.</strong> </p>
<p><strong><em>Russian mathematician Grigori Perelman was awarded the Prize on March 18 last year for solving one of the problems, the Poincaré conjecture—as yet the only problem that’s been solved. Famously, he turned down the $1,000,000 Millennium Prize.</em></strong></p>
<p><strong><em>Over the coming weeks, each of these problems will be illuminated by experts from the <a href="http://theconversation.com/institutions/the-australian-mathematical-sciences-institute">Australian Mathematical Sciences Institute</a> (AMSI) member institutions.</em></strong></p>
<p><strong><em>Here, Ole Warnaar and Wadim Zudilin explain the Riemann Hypothesis, and explore the confounding beauty of prime numbers. Enjoy.</em></strong></p>
<p>“At school I was never really good at maths” is an all too common reaction when mathematicians name their profession.</p>
<p>In view of most people’s perceived lack of mathematical talent,
it may come as somewhat of a surprise that a recent study carried out at John Hopkins University has shown that six-month-old babies already have a clear sense of numbers. They can count, or at least approximate, the number of happy faces shown on a computer screen.</p>
<p>By the time they start school, at around the age of five, most children are true masters of counting, and many will proudly announce when for the first time they have counted up to 100 or 1000.
Children also intuitively understand the regular nature of counting; by adding sufficiently many ones to a starting value of one they know they will eventually reach their own age, that of their parents, grandparents, 2011, and so on.</p>
<figure class="align-right ">
<img alt="" src="https://images.theconversation.com/files/6145/original/86f199500c110c10-1323061866.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=237&fit=clip" srcset="https://images.theconversation.com/files/6145/original/86f199500c110c10-1323061866.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=600&h=401&fit=crop&dpr=1 600w, https://images.theconversation.com/files/6145/original/86f199500c110c10-1323061866.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=600&h=401&fit=crop&dpr=2 1200w, https://images.theconversation.com/files/6145/original/86f199500c110c10-1323061866.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=600&h=401&fit=crop&dpr=3 1800w, https://images.theconversation.com/files/6145/original/86f199500c110c10-1323061866.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&h=504&fit=crop&dpr=1 754w, https://images.theconversation.com/files/6145/original/86f199500c110c10-1323061866.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=754&h=504&fit=crop&dpr=2 1508w, https://images.theconversation.com/files/6145/original/86f199500c110c10-1323061866.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=754&h=504&fit=crop&dpr=3 2262w" sizes="(min-width: 1466px) 754px, (max-width: 599px) 100vw, (min-width: 600px) 600px, 237px">
<figcaption>
<span class="caption">Counting is child’s play.</span>
<span class="attribution"><span class="source">Photography By Shaeree</span></span>
</figcaption>
</figure>
<p>From counting to more general addition of whole numbers is only a small step—again within children’s almost-immediate grasp. After all, counting is the art of adding one, and once that is mastered it takes relatively little effort to work out that 3 + 4 = 7.
Indeed, the first few times children attempt addition they usually receive help from their fingers or toes, effectively reducing the problem to that of counting:</p>
<p>
3 + 4 = (1 + 1 + 1) + (1 + 1 + 1 + 1) = 7.
</p>
<p>For most children, the sense of joy and achievement quickly ends
when multiplication enters the picture.
In theory it too can be understood through counting: 3 x 6 is three lots of six apples, which can be counted on fingers and toes to give 18 apples.</p>
<p>In practice, however, we master it through long hours
spent rote-learning multiplication tables—perhaps not among our favourite primary school memories.</p>
<p>But at this point, we ask the reader to consider the
possibility—in fact, the certainty—that multiplication is far from boring and uninspiring,
but that it is intrinsically linked with some of mathematics’
deepest, most enduring and beautiful mysteries.
And while a great many people may claim to be “not very good at maths” they are, in fact, equipped to understand some very difficult mathematical questions.</p>
<h2>Primes</h2>
<p>Let’s move towards these questions by going back to addition and
those dreaded multiplication tables. Just like the earlier example of 7, we know that every whole number can be constructed by adding
together sufficiently many ones.
Multiplication, on the other hand, is not so well-behaved.</p>
<p>The number 12, for example, can be broken up into smaller pieces, or <em>factors</em>, while the number 11 cannot.
More precisely, 12 can be written as the product of two
whole numbers in multiple ways:
1 x 12, 2 x 6 and 3 x 4, but 11 can
only ever be written as the product 1 x 11.
Numbers such as 12 are called <em>composite</em>, while those that
refuse to be factored are known as <em>prime numbers</em> or simply <em>primes</em>.
For reasons that will soon become clear, 1 is not considered
a prime, so that the first five prime numbers are 2, 3, 5, 7 and 11.</p>
<p>Just as the number 1 is the atomic unit of whole-number addition,
prime numbers are the atoms of multiplication.
According to the <a href="http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic"><em>Fundamental Theorem of Arithmetic</em></a>,
any whole number greater than 1 can be
written as a product of primes in exactly one way.
For example:
4 = 2 x 2, 12 = 2 x 2 x 3,
2011 = 2011 and</p>
<p>
13079109366950 = 2 x 5 x 5 x 11 x 11 x 11 x 37 x 223 x 23819,
</p>
<p>where we always write the factors from smallest to largest.
If, rather foolishly, we were to add 1 to the list of prime numbers,
this would cause the downfall of the Fundamental Theorem of Arithmetic:</p>
<p>
4 = 2 x 2 = 1 x 2 x 2 = 1 x 1 x 2 x 2 = …
</p>
<p>In the above examples we have already seen several prime numbers,
and a natural question is to ask for the total number of primes.
From what we have learnt about addition with its single atom of 1,
it is not unreasonable to expect there are only finitely many prime
numbers, so that, just maybe, the 2649th prime number, 23819,
could be the largest.
<a href="http://www.gap-system.org/%7Ehistory/Biographies/Euclid.html">Euclid of Alexandria</a>,
who lived around 300BC and who also gave us
<a href="http://en.wikipedia.org/wiki/Euclidean_geometry"><em>Euclidean Geometry</em></a>,
in fact showed that there are infinitely many primes.</p>
<p>Euclid’s reasoning can be captured in just a single sentence:
if the list of primes were finite, then
by multiplying them together and adding 1 we would get a new number
which is not divisible by any prime on our list—a contradiction.</p>
<p>A few years after Euclid, his compatriot
<a href="http://www.gap-system.org/%7Ehistory/Biographies/Eratosthenes.html">Eratosthenes of Cyrene</a>
found a clever way, now known as the <a href="http://www.cut-the-knot.org/Curriculum/Arithmetic/Eratosthenes.shtml"><em>Sieve of Eratosthenes</em></a>,
to obtain all primes less than a given number. </p>
<p>For instance, to find all primes less than 100, Eratosthenes would
write down a list of all numbers from 2 to 99, cross out all multiples
of 2 (but not 2 itself), then all multiples
of 3 (but not 3 itself), then all multiples of 5, and so on. After
only four steps(!) this would reveal to him the 25 primes</p>
<p>
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97.
</p>
<p>While this might seem very quick, much more sophisticated methods,
combined with very powerful computers,
are needed to find really large prime numbers. The
<a href="http://www.sciencenews.org/view/generic/id/36625/title/Math_Trek__Largest_known_prime_number_found">current world record</a>,
established 2008, is the truly monstrous
2<sup>43112609</sup> – 1, a prime number of approximately 13 million digits.</p>
<p>The quest to tame the primes did not end with the ancient Greeks, and many great mathematicians,
such as <a href="http://www.gap-system.org/%7Ehistory/Biographies/Fermat.html">Pierre de Fermat</a>,
<a href="http://www.gap-system.org/%7Ehistory/Biographies/Euler.html">Leonhard Euler</a> and
<a href="http://www.gap-system.org/%7Ehistory/Biographies/Gauss.html">Carl Friedrich Gauss</a>
studied prime numbers extensively.
Despite their best efforts, and those of many mathematicians up to the
present day, there are many more questions than answers concerning the primes.</p>
<p>One famous example of an unsolved problem is
<a href="http://en.wikipedia.org/wiki/Goldbach%27s_conjecture"><em>Goldbach’s Conjecture</em></a>.
In 1742, <a href="http://www.gap-system.org/%7Ehistory/Biographies/Goldbach.html">Christian Goldbach</a>
remarked in a letter to Euler that it
appeared that every even number greater than 2 could be written as the
sum of two primes.</p>
<p>For example, 2012 = 991 + 1021.
While computers have confirmed the conjecture holds well beyond the first quintillion (10<sup>18</sup>) numbers,
there is little hope of a proof of Goldbach’s Conjecture in the foreseeable future.</p>
<p>Another intractable problem is that of breaking very large numbers into their prime factors.
If a number is known to be the product of
two primes, each about 200 digits long, current supercomputers
would take more than the lifetime of the universe to actually find
these two prime factors.
This time round our inability to do better is in fact a blessing:
most secure encryption methods rely
heavily on our failure to carry out prime factorisation quickly.
The moment someone discovers a fast algorithm to factor large numbers, the world’s financial system will collapse, making the GFC look like child’s play. </p>
<p>To the dismay of many security agencies, mathematicians have also failed to show that fast algorithms are impossible—the possibility of an imminent collapse of world order cannot be entirely ruled out!</p>
<h2>Margins of error</h2>
<p>For mathematicians, the main prime number challenge is to understand their distribution.
Quoting <a href="http://en.wikipedia.org/wiki/Don_Zagier#Common_quotations">Don Zagier</a>, nobody can predict where the next prime will sprout; they grow like weeds among the whole numbers, seemingly obeying no other law than that of chance. At the same time the prime numbers exhibit stunning regularity:
there are laws governing their behaviour, obeyed with almost military precision.</p>
<p>The <a href="http://en.wikipedia.org/wiki/Prime_number_theorem"><em>Prime Number Theorem</em></a>
describes the average distribution of the primes; it was first conjectured by both Gauss and
<a href="http://www.gap-system.org/%7Ehistory/Biographies/Legendre.html">Adrien-Marie Legendre</a>,
and then rigorously established independently
by <a href="http://www.gap-system.org/%7Ehistory/Biographies/Hadamard.html">Jacques Hadamard</a>
and <a href="http://www.gap-system.org/%7Ehistory/Biographies/Vallee_Poussin.html">Charles Jean de la Vallée Poussin</a>,
a hundred years later in 1896.</p>
<p>The Prime Number Theorem states that the number of primes less than an arbitrarily chosen number <i>n</i> is approximately <i>n</i> divided by ln(<i>n</i>), where ln(<i>n</i>) is the
natural logarithm of <i>n</i>. The relative
error in this approximation becomes arbitrarily small as
<i>n</i> becomes larger and larger.</p>
<p>For example, there are 25 primes less than 100,
and 100/ln(100) = 21.7…, which is around 13% short.
When <i>n</i> is a million we are up to 78498 primes
and since 10<sup>6</sup>/ln(10<sup>6</sup>) = 72382.4…,
we are only only 8% short.</p>
<h2>The Riemann Hypothesis</h2>
<figure class="align-right ">
<img alt="" src="https://images.theconversation.com/files/6144/original/19f644ca63314f8f-1323061470.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=237&fit=clip" srcset="https://images.theconversation.com/files/6144/original/19f644ca63314f8f-1323061470.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=600&h=760&fit=crop&dpr=1 600w, https://images.theconversation.com/files/6144/original/19f644ca63314f8f-1323061470.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=600&h=760&fit=crop&dpr=2 1200w, https://images.theconversation.com/files/6144/original/19f644ca63314f8f-1323061470.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=600&h=760&fit=crop&dpr=3 1800w, https://images.theconversation.com/files/6144/original/19f644ca63314f8f-1323061470.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&h=956&fit=crop&dpr=1 754w, https://images.theconversation.com/files/6144/original/19f644ca63314f8f-1323061470.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=754&h=956&fit=crop&dpr=2 1508w, https://images.theconversation.com/files/6144/original/19f644ca63314f8f-1323061470.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=754&h=956&fit=crop&dpr=3 2262w" sizes="(min-width: 1466px) 754px, (max-width: 599px) 100vw, (min-width: 600px) 600px, 237px">
<figcaption>
<span class="caption"></span>
</figcaption>
</figure>
<p>The Prime Number Theorem does an incredible job describing the
distribution of primes, but mathematicians would love to have a
better understanding of the relative errors.
This leads us to arguably the most famous open problem in mathematics:
the <em>Riemann Hypothesis</em>.</p>
<p>Posed by <a href="http://www.gap-system.org/%7Ehistory/Biographies/Riemann.html">Bernhard Riemann</a>
in 1859 in his paper
“Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse”
(On the number of primes less than a given magnitude),
the Riemann Hypothesis tells us how to tighten the Prime Number Theorem,
giving us a control of the errors, like the 13% or 8% computed above.</p>
<p>The Riemann Hypothesis does not just “do better” than the Prime Number
Theorem—it is generally believed to be “as good as it gets”.
That is, we, or far-superior extraterrestrial civilisations,
will never be able to predict the distribution of the primes any better
than the Riemann Hypothesis does.
One can compare it to, say, the ultimate 100 metres
world record—a record that, once set, is impossible to ever break.</p>
<p>Finding a proof of the Riemann Hypothesis,
and thus becoming record holder for all eternity,
is the holy grail of pure mathematics.
While the motivation for the Riemann Hypothesis is to understand the
behaviour of the primes, the atoms of multiplication, its actual formulation
requires higher-level mathematics and is beyond the scope of this article.</p>
<p>In 1900, <a href="http://www.gap-system.org/%7Ehistory/Biographies/Hilbert.html">David Hilbert</a>,
the most influential mathematician of his time, posed a now famous
<a href="http://en.wikipedia.org/wiki/Hilbert's_problems#Table_of_problems">list of 23 problems</a>
that he hoped would shape the future of mathematics in the 20th century.
Very few of Hilbert’s problems other than the Riemann Hypothesis remain open.</p>
<p>Inspired by Hilbert, in 2000 the Clay Mathematics
Institute announced a list of seven of the
most important open problems in mathematics.
For the successful solver of any one of these there
awaits not only lasting fame,
but also one million US dollars in prize money.
Needless to say, the Riemann Hypothesis is one of the
“Millennium Prize Problems”.</p>
<p>Hilbert himself remarked:
“If I were awoken after having slept for a thousand years, my first
question would be: has the Riemann Hypothesis been proven?”
Judging by the current rate of progress, Hilbert may well have to
sleep a little while longer.</p>
<p><strong>This is the sixth part of the Millennium Prize Series. To read the other instalments, follow the links below.</strong></p>
<ul>
<li><strong><a href="http://theconversation.com/millenium-prize-the-navier-stokes-existence-and-uniqueness-problem-4244">Part One: Millennium Prize: the Navier–Stokes existence and uniqueness problem</a></strong></li>
<li><strong><a href="http://theconversation.com/millennium-prize-the-hodge-conjecture-4243">Part Two: Millennium Prize: the Hodge Conjecture</a></strong></li>
<li><strong><a href="http://theconversation.com/millennium-prize-p-vs-np-4246">Part Three: Millennium Prize: P vs NP</a></strong></li>
<li><strong><a href="http://theconversation.com/millennium-prize-the-poincar-conjecture-4245">Part Four: Millenium Prize: the Poincaré Conjecture</a></strong></li>
<li><strong><a href="http://theconversation.com/millennium-prize-the-birch-and-swinnerton-dyer-conjecture-4242">Part Five: Millenium Prize: the Birch and Swinnerton-Dyer Conjecture</a></strong></li>
</ul><img src="https://counter.theconversation.com/content/3847/count.gif" alt="The Conversation" width="1" height="1" />
<p class="fine-print"><em><span>Ole Warnaar receives funding from the Australian Research Council.</span></em></p><p class="fine-print"><em><span>Wadim Zudilin receives funding from the Australian Research Council.</span></em></p>MILLENNIUM PRIZE SERIES: The Millennium Prize Problems are seven mathematics problems laid out by the Clay Mathematics Institute in 2000. They’re not easy—a correct solution to any one results in a US$1,000,000…Ole Warnaar, Chair and Professor in Pure Mathematics, The University of QueenslandWadim Zudilin, Associate Professor, School of Mathematical and Physical Sciences, University of NewcastleLicensed as Creative Commons – attribution, no derivatives.tag:theconversation.com,2011:article/42422011-11-30T19:44:33Z2011-11-30T19:44:33ZMillennium Prize: the Birch and Swinnerton-Dyer Conjecture<figure><img src="https://images.theconversation.com/files/6039/original/3449993951-152f987ab5-b-jpg-1322632072.jpg?ixlib=rb-1.1.0&rect=55%2C13%2C898%2C651&q=45&auto=format&w=496&fit=clip" /><figcaption><span class="caption">If this doesn't bake your hippy noodle, nothing will.</span> <span class="attribution"><span class="source">stuartpilbrow</span></span></figcaption></figure><p><strong>MILLENNIUM PRIZE SERIES:</strong> <strong><em>The Millennium Prize Problems are seven mathematics problems laid out by the Clay Mathematics Institute in 2000. They’re not easy</em> – <em>a correct solution to any one results in a US$1,000,000 prize being awarded by the institute</em>.</strong> </p>
<p><strong><em>Russian mathematician Grigori Perelman was awarded the Prize on March 18 last year for solving one of the problems, the Poincaré conjecture – as yet the only problem that’s been solved. Famously, he turned down the $1,000,000 Millennium Prize.</em></strong></p>
<p><strong><em>Over the coming weeks, each of these problems will be illuminated by experts from the <a href="http://theconversation.com/institutions/the-australian-mathematical-sciences-institute">Australian Mathematical Sciences Institute</a> (AMSI) member institutions.</em></strong></p>
<p><strong><em>Here, Daniel Delbourgo explains the Birch and Swinnerton-Dyer Conjecture. Enjoy.</em></strong>
<br></p>
<p><a href="http://mathworld.wolfram.com/EllipticCurve.html">Elliptic curves</a> have a long and distinguished history that can be traced back to antiquity. They are prevalent in many branches of modern mathematics, foremost of which is <a href="http://mathworld.wolfram.com/NumberTheory.html">number theory</a>.</p>
<p>In simplest terms, one can describe these curves by using a <a href="http://en.wikipedia.org/wiki/Cubic_function">cubic equation</a> of the form</p>
<figure class="align-center ">
<img alt="" src="https://images.theconversation.com/files/5979/original/screen-shot-2011-11-29-at-12-27-25-pm-png-1322530070.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&fit=clip" srcset="https://images.theconversation.com/files/5979/original/screen-shot-2011-11-29-at-12-27-25-pm-png-1322530070.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=600&h=119&fit=crop&dpr=1 600w, https://images.theconversation.com/files/5979/original/screen-shot-2011-11-29-at-12-27-25-pm-png-1322530070.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=600&h=119&fit=crop&dpr=2 1200w, https://images.theconversation.com/files/5979/original/screen-shot-2011-11-29-at-12-27-25-pm-png-1322530070.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=600&h=119&fit=crop&dpr=3 1800w, https://images.theconversation.com/files/5979/original/screen-shot-2011-11-29-at-12-27-25-pm-png-1322530070.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&h=149&fit=crop&dpr=1 754w, https://images.theconversation.com/files/5979/original/screen-shot-2011-11-29-at-12-27-25-pm-png-1322530070.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=754&h=149&fit=crop&dpr=2 1508w, https://images.theconversation.com/files/5979/original/screen-shot-2011-11-29-at-12-27-25-pm-png-1322530070.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=754&h=149&fit=crop&dpr=3 2262w" sizes="(min-width: 1466px) 754px, (max-width: 599px) 100vw, (min-width: 600px) 600px, 237px">
<figcaption>
<span class="caption"></span>
</figcaption>
</figure>
<p>where A and B are fixed rational numbers (to ensure the curve E is nice and smooth everywhere, one also needs to assume that its discriminant 4A<sup>3</sup> + 27B<sup>2</sup> is non-zero).</p>
<p>To illustrate, let’s consider an example: choosing A=-1 and B=0, we obtain the following picture:</p>
<figure class="align-center ">
<img alt="" src="https://images.theconversation.com/files/5967/original/screen-shot-2011-11-29-at-12-13-10-pm-png-1322529282.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&fit=clip" srcset="https://images.theconversation.com/files/5967/original/screen-shot-2011-11-29-at-12-13-10-pm-png-1322529282.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=600&h=535&fit=crop&dpr=1 600w, https://images.theconversation.com/files/5967/original/screen-shot-2011-11-29-at-12-13-10-pm-png-1322529282.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=600&h=535&fit=crop&dpr=2 1200w, https://images.theconversation.com/files/5967/original/screen-shot-2011-11-29-at-12-13-10-pm-png-1322529282.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=600&h=535&fit=crop&dpr=3 1800w, https://images.theconversation.com/files/5967/original/screen-shot-2011-11-29-at-12-13-10-pm-png-1322529282.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&h=672&fit=crop&dpr=1 754w, https://images.theconversation.com/files/5967/original/screen-shot-2011-11-29-at-12-13-10-pm-png-1322529282.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=754&h=672&fit=crop&dpr=2 1508w, https://images.theconversation.com/files/5967/original/screen-shot-2011-11-29-at-12-13-10-pm-png-1322529282.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=754&h=672&fit=crop&dpr=3 2262w" sizes="(min-width: 1466px) 754px, (max-width: 599px) 100vw, (min-width: 600px) 600px, 237px">
<figcaption>
<span class="caption"></span>
</figcaption>
</figure>
<p>At this point it becomes clear that, despite their name, elliptic curves have nothing whatsoever to do with ellipses! The reason for this historical confusion is that these curves have a strong connection to <a href="http://mathworld.wolfram.com/EllipticIntegral.html">elliptic integrals</a>, which arise when describing the motion of planetary bodies in space.</p>
<p>The ancient Greek mathematician <a href="http://www.gap-system.org/%7Ehistory/Biographies/Diophantus.html">Diophantus</a> is considered by many to be the father of algebra. His major mathematical work was written up in the tome <a href="http://www.mathsisgoodforyou.com/artefacts/diphantusarithmetica.htm">Arithmetica</a> which was essentially a school textbook for geniuses. Within it, he outlined many tools for studying solutions to <a href="http://people.hofstra.edu/stefan_Waner/realworld/tut_alg_review/framesA_5B.html">polynomial equations</a> with several variables, termed <a href="http://mathworld.wolfram.com/DiophantineEquation.html">Diophantine Equations</a> in his honour.</p>
<p>One of the main problems Diophantus considered was to find all solutions to a particular polynomial equation that lie in the field of <a href="http://www.mathsisfun.com/rational-numbers.html">rational numbers Q</a>. For equations of “degree two” (circles, ellipses, <a href="http://mathworld.wolfram.com/Parabola.html">parabolas</a>, <a href="http://mathworld.wolfram.com/Hyperbola.html">hyperbolas</a>)
we now have a complete answer to this problem. This answer is thanks to the late German mathematician <a href="http://www.gap-system.org/%7Ehistory/Biographies/Hasse.html">Helmut Hasse</a>, and allows one to find all such points, should they exist at all.</p>
<p>Returning to our elliptic curve E, the analogous problem is to find all the rational solutions (x,y) which satisfy the equation defining E. If we call this set of points E(Q), then we are asking if there exists an algorithm that allows us to obtain all points (x,y) belonging to E(Q).</p>
<p>At this juncture we need to introduce a <a href="http://en.wikipedia.org/wiki/Elliptic_curve#The_group_law">group law</a> on E, which gives an eccentric way of fusing together two points (p₁ and p₂) on the curve, to obtain a brand new point (p₄). This mimics the addition law for numbers we learn from childhood (i.e. the sum or difference of any two numbers is still a number). There’s an illustration of this rule below:</p>
<figure class="align-center ">
<img alt="" src="https://images.theconversation.com/files/5974/original/screen-shot-2011-11-29-at-12-17-51-pm-png-1322529491.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&fit=clip" srcset="https://images.theconversation.com/files/5974/original/screen-shot-2011-11-29-at-12-17-51-pm-png-1322529491.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=600&h=435&fit=crop&dpr=1 600w, https://images.theconversation.com/files/5974/original/screen-shot-2011-11-29-at-12-17-51-pm-png-1322529491.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=600&h=435&fit=crop&dpr=2 1200w, https://images.theconversation.com/files/5974/original/screen-shot-2011-11-29-at-12-17-51-pm-png-1322529491.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=600&h=435&fit=crop&dpr=3 1800w, https://images.theconversation.com/files/5974/original/screen-shot-2011-11-29-at-12-17-51-pm-png-1322529491.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&h=546&fit=crop&dpr=1 754w, https://images.theconversation.com/files/5974/original/screen-shot-2011-11-29-at-12-17-51-pm-png-1322529491.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=754&h=546&fit=crop&dpr=2 1508w, https://images.theconversation.com/files/5974/original/screen-shot-2011-11-29-at-12-17-51-pm-png-1322529491.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=754&h=546&fit=crop&dpr=3 2262w" sizes="(min-width: 1466px) 754px, (max-width: 599px) 100vw, (min-width: 600px) 600px, 237px">
<figcaption>
<span class="caption"></span>
</figcaption>
</figure><figure class="align-center ">
<img alt="" src="https://images.theconversation.com/files/5968/original/screen-shot-2011-11-29-at-12-13-49-pm-png-1322529343.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&fit=clip" srcset="https://images.theconversation.com/files/5968/original/screen-shot-2011-11-29-at-12-13-49-pm-png-1322529343.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=600&h=433&fit=crop&dpr=1 600w, https://images.theconversation.com/files/5968/original/screen-shot-2011-11-29-at-12-13-49-pm-png-1322529343.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=600&h=433&fit=crop&dpr=2 1200w, https://images.theconversation.com/files/5968/original/screen-shot-2011-11-29-at-12-13-49-pm-png-1322529343.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=600&h=433&fit=crop&dpr=3 1800w, https://images.theconversation.com/files/5968/original/screen-shot-2011-11-29-at-12-13-49-pm-png-1322529343.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&h=544&fit=crop&dpr=1 754w, https://images.theconversation.com/files/5968/original/screen-shot-2011-11-29-at-12-13-49-pm-png-1322529343.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=754&h=544&fit=crop&dpr=2 1508w, https://images.theconversation.com/files/5968/original/screen-shot-2011-11-29-at-12-13-49-pm-png-1322529343.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=754&h=544&fit=crop&dpr=3 2262w" sizes="(min-width: 1466px) 754px, (max-width: 599px) 100vw, (min-width: 600px) 600px, 237px">
<figcaption>
<span class="caption"></span>
</figcaption>
</figure>
<p>Under this geometric model, the point p₄ is defined to be the sum of p₁ and p₂ (it’s easy to see that the addition law does not depend on the order of the points p₁, p₂). Moreover the set of rational points is preserved by this notion of addition; in other words, the sum of two rational points is again a rational point.</p>
<p><a href="http://www.gap-system.org/%7Ehistory/Biographies/Mordell.html">Louis Mordell</a>, who was <a href="http://en.wikipedia.org/wiki/Sadleirian_Professor_of_Pure_Mathematics">Sadleirian Professor</a> of Pure Mathematics at Cambridge University from 1945 to 1953, was the first to determine the structure of this group of rational points. In 1922 he proved </p>
<figure class="align-center ">
<img alt="" src="https://images.theconversation.com/files/5975/original/screen-shot-2011-11-29-at-12-20-18-pm-png-1322529630.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&fit=clip" srcset="https://images.theconversation.com/files/5975/original/screen-shot-2011-11-29-at-12-20-18-pm-png-1322529630.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=600&h=123&fit=crop&dpr=1 600w, https://images.theconversation.com/files/5975/original/screen-shot-2011-11-29-at-12-20-18-pm-png-1322529630.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=600&h=123&fit=crop&dpr=2 1200w, https://images.theconversation.com/files/5975/original/screen-shot-2011-11-29-at-12-20-18-pm-png-1322529630.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=600&h=123&fit=crop&dpr=3 1800w, https://images.theconversation.com/files/5975/original/screen-shot-2011-11-29-at-12-20-18-pm-png-1322529630.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&h=154&fit=crop&dpr=1 754w, https://images.theconversation.com/files/5975/original/screen-shot-2011-11-29-at-12-20-18-pm-png-1322529630.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=754&h=154&fit=crop&dpr=2 1508w, https://images.theconversation.com/files/5975/original/screen-shot-2011-11-29-at-12-20-18-pm-png-1322529630.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=754&h=154&fit=crop&dpr=3 2262w" sizes="(min-width: 1466px) 754px, (max-width: 599px) 100vw, (min-width: 600px) 600px, 237px">
<figcaption>
<span class="caption"></span>
</figcaption>
</figure>
<p>where the number of copies of the <a href="http://www.mathsisfun.com/definitions/integer.html">integers</a> Z above is called the “rank r(E) of the elliptic curve E”. The finite group Τ<sub>E</sub>(Q) on the end is uninteresting, as it never has more than 16 elements.</p>
<figure class="align-right ">
<img alt="" src="https://images.theconversation.com/files/5978/original/louis-mordell-jpeg-1322529840.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=237&fit=clip" srcset="https://images.theconversation.com/files/5978/original/louis-mordell-jpeg-1322529840.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=600&h=842&fit=crop&dpr=1 600w, https://images.theconversation.com/files/5978/original/louis-mordell-jpeg-1322529840.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=600&h=842&fit=crop&dpr=2 1200w, https://images.theconversation.com/files/5978/original/louis-mordell-jpeg-1322529840.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=600&h=842&fit=crop&dpr=3 1800w, https://images.theconversation.com/files/5978/original/louis-mordell-jpeg-1322529840.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&h=1058&fit=crop&dpr=1 754w, https://images.theconversation.com/files/5978/original/louis-mordell-jpeg-1322529840.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=754&h=1058&fit=crop&dpr=2 1508w, https://images.theconversation.com/files/5978/original/louis-mordell-jpeg-1322529840.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=754&h=1058&fit=crop&dpr=3 2262w" sizes="(min-width: 1466px) 754px, (max-width: 599px) 100vw, (min-width: 600px) 600px, 237px">
<figcaption>
<span class="caption">Professor Louis Mordell.</span>
<span class="attribution"><span class="source">Konrad Jacobs, Erlangen</span></span>
</figcaption>
</figure><img src="https://counter.theconversation.com/content/4242/count.gif" alt="The Conversation" width="1" height="1" />
<p class="fine-print"><em><span>Daniel Delbourgo receives funding from the Australian Research Council.</span></em></p>MILLENNIUM PRIZE SERIES: The Millennium Prize Problems are seven mathematics problems laid out by the Clay Mathematics Institute in 2000. They’re not easy – a correct solution to any one results in a US$1,000,000…Daniel Delbourgo, Senior lecturer, Mathematical Sciences, Monash UniversityLicensed as Creative Commons – attribution, no derivatives.tag:theconversation.com,2011:article/42452011-11-29T03:40:05Z2011-11-29T03:40:05ZMillennium Prize: the Poincaré Conjecture<figure><img src="https://images.theconversation.com/files/5943/original/2987898631-5c3a56f6b1-o-jpg-1322454405.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=496&fit=clip" /><figcaption><span class="caption">The problem's been solved … but the sweet treats were declined.</span> <span class="attribution"><span class="source">Back to the Cutting Board</span></span></figcaption></figure><p><strong>MILLENNIUM PRIZE SERIES:</strong> <strong><em>The Millennium Prize Problems are seven mathematics problems laid out by the Clay Mathematics Institute in 2000. They’re not easy</em> – <em>a correct solution to any one results in a US$1,000,000 prize being awarded by the institute</em>.</strong> </p>
<p><strong><em>Russian mathematician Grigori “Grisha” Perelman was awarded the Prize on March 18 last year for solving one of the problems, the Poincaré conjecture – as yet the only one that’s been solved. Famously, he turned down the $1,000,000 Millennium Prize.</em></strong></p>
<p><strong><em>Over the coming weeks, each of these problems will be illuminated by experts from the <a href="http://theconversation.com/institutions/the-australian-mathematical-sciences-institute">Australian Mathematical Sciences Institute</a> (AMSI) member institutions.</em></strong></p>
<p><strong><em>Here, Hyam Rubinstein discusses the now-resolved Poincaré Conjecture. Enjoy.</em></strong>
<br></p>
<p>In 1904, French mathematician <a href="http://www.gap-system.org/%7Ehistory/Biographies/Poincare.html">Henri Poincaré</a> asked a key question about three-dimensional spaces (“<a href="http://www.euclideanspace.com/maths/geometry/surfaces/manifold/index.htm">manifolds</a>”).</p>
<p>Imagine a piece of rope, so that firstly a knot is tied in the rope and then the ends are glued together. This is what mathematicians call a <a href="http://mathworld.wolfram.com/Knot.html">knot</a>. A <a href="http://mathworld.wolfram.com/Link.html">link</a> is a collection of knots that are tangled together. </p>
<p>It has been observed that DNA, which is coiled up within cells, occurs in closed knotted form. </p>
<p>Complex molecules such as <a href="http://pslc.ws/macrog/kidsmac/wiap.htm">polymers</a> are tangled in knotted forms. There are deep connections between <a href="http://mathworld.wolfram.com/KnotTheory.html">knot theory</a> and ideas in mathematical physics. The outsides of a knot or link in space give important examples of three-dimensional spaces. </p>
<figure class="align-right ">
<img alt="" src="https://images.theconversation.com/files/5961/original/torus-cycles-png-1322526447.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=237&fit=clip" srcset="https://images.theconversation.com/files/5961/original/torus-cycles-png-1322526447.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=600&h=442&fit=crop&dpr=1 600w, https://images.theconversation.com/files/5961/original/torus-cycles-png-1322526447.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=600&h=442&fit=crop&dpr=2 1200w, https://images.theconversation.com/files/5961/original/torus-cycles-png-1322526447.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=600&h=442&fit=crop&dpr=3 1800w, https://images.theconversation.com/files/5961/original/torus-cycles-png-1322526447.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&h=555&fit=crop&dpr=1 754w, https://images.theconversation.com/files/5961/original/torus-cycles-png-1322526447.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=754&h=555&fit=crop&dpr=2 1508w, https://images.theconversation.com/files/5961/original/torus-cycles-png-1322526447.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=754&h=555&fit=crop&dpr=3 2262w" sizes="(min-width: 1466px) 754px, (max-width: 599px) 100vw, (min-width: 600px) 600px, 237px">
<figcaption>
<span class="caption">Torus.</span>
<span class="attribution"><span class="source">Fropuff</span></span>
</figcaption>
</figure>
<p>Back to Poincaré and his conjecture. He asked if the <a href="http://www.universe-galaxies-stars.com/3-sphere.html">3-sphere</a> (which can be formed by either adding a point at infinity to ordinary three-dimensional <a href="http://mathworld.wolfram.com/EuclideanSpace.html">Euclidean space</a> or by gluing two solid three-dimensional balls together along their boundary <a href="http://topospaces.subwiki.org/wiki/2-sphere">2-spheres</a>) was the only three-dimensional space in which every loop can be continuously shrunk to a point. </p>
<p>Poincaré had introduced important ideas in the structure and classification of surfaces and their higher dimensional analogues (“manifolds”), arising from his work on <a href="http://mathworld.wolfram.com/DynamicalSystem.html">dynamical systems</a>. </p>
<h2>Donuts to go, please</h2>
<p>A good way to visualise Poincaré’s conjecture is to examine the boundary of a ball (a two-dimensional sphere) and the boundary of a donut (called a <a href="http://mathworld.wolfram.com/Torus.html">torus</a>). Any loop of string on a 2-sphere can be shrunk to a point while keeping it on the sphere, whereas if a loop goes around the hole in the donut, it cannot be shrunk without leaving the surface of the donut. </p>
<p>Many attempts were made on the Poincaré conjecture, until in 2003 a wonderful solution was announced by a young Russian mathematician, <a href="http://www.notablebiographies.com/supp/Supplement-Mi-So/Perelman-Grigory.html">Grigori “Grisha” Perelman.</a> </p>
<p>This is a brief account of the ideas used by Perelman, which built on work of two other outstanding mathematicians, <a href="http://www.gap-system.org/%7Ehistory/Biographies/Thurston.html">Bill Thurston</a> and <a href="http://www.claymath.org/research_award/Hamilton/hamilton_bio.php">Richard Hamilton</a>. </p>
<h2>3D spaces</h2>
<p>Thurston made enormous strides in our understanding of three-dimensional spaces in the late 1970s. In particular, he realised that essentially all the work that had been done since Poincaré fitted into a single theme. </p>
<p>He observed that known three-dimensional spaces could be divided into pieces in a natural way, so that each piece had a uniform geometry, similar to the flat plane and the round sphere. (To see this geometry on a torus, one must embed it into four-dimensional space!).</p>
<p>Thurston made a bold “<a href="http://www.ucl.ac.uk/%7Eucahhjr/Notes/Essay.pdf">geometrisation conjecture</a>” that this should be true for all three-dimensional spaces. He had many brilliant students who further developed his theories, not least by producing powerful computer programs that could test any given space to try to find its geometric structure. </p>
<figure><div style="text-align:center;">
<figure>
<iframe width="440" height="260" src="https://www.youtube.com/embed/AUoaTrQTM5o?wmode=transparent&start=0" frameborder="0" allowfullscreen=""></iframe>
</figure>
</div></figure>
<p>Thurston made spectacular progress on the geometrisation conjecture, which includes the Poincaré conjecture as a special case. The geometrisation conjecture predicts that any three-dimensional space in which every loop shrinks to a point should have a round metric – it would be a 3-sphere and Poincaré’s conjecture would follow. </p>
<p>In 1982, Richard Hamilton published a beautiful paper introducing a new technique in geometric analysis which he called <a href="http://mathworld.wolfram.com/RicciFlow.html">Ricci flow</a>. Hamilton had been looking for analogues of a flow of functions, so that the energy of the function decreases until it reaches a minimum. This type of flow is closely related to the way heat spreads in a material. </p>
<p>Hamilton reasoned that there should be a similar flow for the geometric shape of a space, rather than a function between spaces. He used the <a href="http://mathworld.wolfram.com/RicciCurvatureTensor.html">Ricci tensor</a>, a key feature of Einstein’s field equations for <a href="http://theconversation.com/explainer-einsteins-theory-of-general-relativity-3481">general relativity</a>, as the driving force for his flow.</p>
<p>He showed that, for three-dimensional spaces where the Ricci curvature is positive, the flow gradually changes the shape until the metric satisfies Thurston’s geometrisation conjecture.</p>
<p>Hamilton attracted many outstanding young mathematicians to work in this area. Ricci flow and other similar flows have become a huge area of research with applications in areas such as moving interfaces, fluid mechanics and computer graphics. </p>
<figure class="align-left ">
<img alt="" src="https://images.theconversation.com/files/5962/original/ricci-flow-png-1322526651.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=237&fit=clip" srcset="https://images.theconversation.com/files/5962/original/ricci-flow-png-1322526651.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=600&h=1104&fit=crop&dpr=1 600w, https://images.theconversation.com/files/5962/original/ricci-flow-png-1322526651.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=600&h=1104&fit=crop&dpr=2 1200w, https://images.theconversation.com/files/5962/original/ricci-flow-png-1322526651.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=600&h=1104&fit=crop&dpr=3 1800w, https://images.theconversation.com/files/5962/original/ricci-flow-png-1322526651.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=754&h=1388&fit=crop&dpr=1 754w, https://images.theconversation.com/files/5962/original/ricci-flow-png-1322526651.jpg?ixlib=rb-1.1.0&q=30&auto=format&w=754&h=1388&fit=crop&dpr=2 1508w, https://images.theconversation.com/files/5962/original/ricci-flow-png-1322526651.jpg?ixlib=rb-1.1.0&q=15&auto=format&w=754&h=1388&fit=crop&dpr=3 2262w" sizes="(min-width: 1466px) 754px, (max-width: 599px) 100vw, (min-width: 600px) 600px, 237px">
<figcaption>
<span class="caption">Ricci flow.</span>
<span class="attribution"><span class="source">CBN</span></span>
</figcaption>
</figure>
<p>He outlined a marvellous program to use Ricci flow to attack Thurston’s geometrisation conjecture. The idea was to keep evolving the shape of a space under Ricci flow. </p>
<p>Hamilton and his collaborators found the space might form a <a href="http://mathworld.wolfram.com/Singularity.html">singularity</a>, where a narrow neck became thinner and thinner until the space splits into two smaller spaces. </p>
<p>Hamilton worked hard to try to fully understand this phenomenon and to allow the pieces to keep evolving under Ricci flow until the geometric structure predicted by Thurston could be found. </p>
<h2>Perelman</h2>
<p>This is when Perelman burst on to the scene. He had produced some brilliant results at a very young age and was a researcher at the famous <a href="http://www.mi.ras.ru/index.php?l=1&main&m=1">Steklov Institute</a> in St Petersburg. Perelman got a Miller fellowship to visit UC Berkeley for three years in the early 1990s. </p>
<p>I met him there around 1992. He then “disappeared” from the mathematical scene for nearly ten years and re-emerged to announce that he had completed Hamilton’s Ricci flow program, in a series of papers he posted on the electronic repository called <a href="http://arxiv.org/archive/math">ArXiv</a>. </p>
<p>His papers created enormous excitement and within several months a number of groups had started to work through Perelman’s strategy. </p>
<p>Eventually everyone was convinced that Perelman had indeed succeeded and both the geometrisation and Poincaré conjecture had been solved. </p>
<p>Perelman was awarded both a <a href="http://www.mathunion.org/general/prizes/fields/details/">Fields medal </a>(the mathematical equivalent of a Nobel prize) and also offered a million dollars for solving one of the Millenium prizes from the Clay Institute. </p>
<p>He turned down both these awards, preferring to live a quiet life in St Petersburg. Mathematicians are still finding new ways to use the solution to the geometrisation conjecture, which is one of the outstanding mathematical results of this era.</p>
<p><strong>This is the fourth part of the Millennium Prize Series. To read the other instalments, follow the links below.</strong></p>
<ul>
<li><strong><a href="http://theconversation.com/millenium-prize-the-navier-stokes-existence-and-uniqueness-problem-4244">Part One: Millennium Prize: the Navier–Stokes existence and uniqueness problem</a></strong></li>
<li><strong><a href="http://theconversation.com/millennium-prize-the-hodge-conjecture-4243">Part Two: Millennium Prize: the Hodge Conjecture</a></strong></li>
<li><strong><a href="http://theconversation.com/millennium-prize-p-vs-np-4246">Part Three: Millennium Prize: P vs NP</a></strong></li>
</ul><img src="https://counter.theconversation.com/content/4245/count.gif" alt="The Conversation" width="1" height="1" />
<p class="fine-print"><em><span>Hyam Rubinstein receives funding from the Australian Research Council and has also received funding from several mining companies for research on the optimal design of access networks in underground mines.</span></em></p>MILLENNIUM PRIZE SERIES: The Millennium Prize Problems are seven mathematics problems laid out by the Clay Mathematics Institute in 2000. They’re not easy – a correct solution to any one results in a US$1,000,000…Hyam Rubinstein, Professor, Department of Mathematics and Statistics, The University of MelbourneLicensed as Creative Commons – attribution, no derivatives.tag:theconversation.com,2011:article/42462011-11-25T03:34:20Z2011-11-25T03:34:20ZMillennium Prize: P vs NP<figure><img src="https://images.theconversation.com/files/5817/original/2647699204_79b479cec4_o.jpg?ixlib=rb-1.1.0&rect=66%2C238%2C1323%2C1120&q=45&auto=format&w=496&fit=clip" /><figcaption><span class="caption">Deciding whether a statement is true is a computational head-scratcher.</span> <span class="attribution"><span class="source">rofi</span></span></figcaption></figure><p><strong>MILLENNIUM PRIZE SERIES:</strong> <strong><em>The Millennium Prize Problems are seven mathematics problems laid out by the Clay Mathematics Institute in 2000. They’re not easy</em> – <em>a correct solution to any one results in a US$1,000,000 prize being awarded by the institute</em>.</strong> </p>
<p><strong><em>Russian mathematician Grigori Perelman was awarded the Prize on March 18 last year for solving one of the problems, the Poincaré conjecture – as yet the only problem that’s been solved. Famously, he turned down the $1,000,000 Millennium Prize.</em></strong></p>
<p><strong><em>Over the coming weeks, each of these problems will be illuminated by experts from the <a href="http://theconversation.com/institutions/the-australian-mathematical-sciences-institute">Australian Mathematical Sciences Institute</a> (AMSI) member institutions.</em></strong></p>
<p><strong><em>Here, Marcel Jackson explains the P vs NP problem. Enjoy.</em></strong>
<br></p>
<p>In the 1930s, <a href="http://www.turing.org.uk/bio/part1.html">Alan Turing</a> showed there are basic tasks that are impossible to achieve by algorithmic means. In modern lingo, what he showed was that there can be no general computer program that answers yes or no to the question of whether another computer program will eventually stop when it is run. </p>
<p>The amazing unsolvability of this <a href="http://www.cgl.uwaterloo.ca/%7Ecsk/halt/">Halting Problem</a> contains a further perplexing subtlety. While we have no way of finding in advance if a program will halt, there is an obvious way, in principle, to demonstrate that it halts if it is a halting program: run it, wait, and witness it halting! </p>
<p>In other words, Turing showed that, at the broadest level, deciding whether a statement is true is computationally harder than demonstrating that it’s true when it is.</p>
<h2>A question of efficiency</h2>
<p>Turing’s work was a pivotal moment in the history of computing. Some 80 years later, computing devices have pervaded almost every facet of society. Turing’s original “what is computable?” question has been mostly replaced by the more pertinent, “what is efficiently computable?” </p>
<p>But while Turing’s Halting Problem can be proved impossible in a few magical lines, the boundary between “efficient” and “inefficient” seems far more elusive. P versus NP is the most famous of a huge swathe of unresolved questions to have emerged from this modern take on Turing’s question.</p>
<h2>So what is this NP thing? </h2>
<p>Roughly speaking, P (standing for “<a href="http://mathworld.wolfram.com/PolynomialTime.html">polynomial time</a>”), corresponds to the collection of computational problems that have an efficient solution. It’s only an abstract formulation of “efficient”, but it works fairly well in practice. </p>
<p>The class NP corresponds to the problems for which, when the answer is “yes”, there is an efficient demonstration that the answer is yes (the “N” stands for “nondeterministic”, but the description taken here is more intuitive). P versus NP simply asks if these two classes of computational problems are the same. </p>
<p>It’s just the “deciding versus demonstrating” issue in Turing’s original Halting Problem, but with the added condition of efficiency.</p>
<h2>A puzzler</h2>
<p>P certainly doesn’t look to be the same as NP. Puzzles are good examples of the general intuition here. Crossword puzzles are popular because it’s a challenge to find the solution, and humans like challenge. But no-one spends their lunchtime checking already completed crosswords: checking someone else’s solution offers nowhere near the same challenge. </p>
<p>Even clearer is Sudoku: again it is a genuine challenge to solve, but checking an existing solution for correctness is so routine it is devoid of entertainment value. </p>
<p>The P=NP possibility is like discovering that the “finding” part of these puzzles is only of the same difficulty to the “checking” part. That seems hard to believe, but the truth is we do not know for sure.</p>
<p>This same intuition pervades an enormous array of important computational tasks for which we don’t currently have efficient algorithms. One particularly tantalising feature is that, more often than not, these problems can be shown to be maximally hard among NP problems. </p>
<p>These so-called “<a href="http://mathworld.wolfram.com/NP-CompleteProblem.html">NP-complete</a>” problems are test cases for P versus NP: if any one of them has an efficient algorithmic solution then they all do (and efficient checking is no harder than efficient finding). </p>
<p>But if even just one single one can be shown to have no efficient solution, then P does not equal NP (and efficient finding really is, in general, harder than efficient checking). </p>
<p>Here are some classic examples of NP-complete problems.</p>
<ul>
<li><p><em>Partition (the dilemma of the alien pick-pockets)</em>. On an alien planet, two pick-pockets steal a wallet. To share the proceeds, they must evenly divide the money: can they do it? Standard Earth currencies evolved to have coin values designed to make this task easy, but in general this task is NP-complete. It’s in NP because, if there is an equal division of the coins, this can be easily demonstrated by simply showing the division. (Finding it is the hard part!)</p></li>
<li><p><em>Timetabling</em>. Finding if a <a href="http://theconversation.com/timetables-hard-to-read-even-harder-to-build-1308">clash-free timetable</a> exists is NP-complete. The problem is in NP because we can efficiently check a correct, clash-free timetable to be clash-free.</p></li>
<li><p><em>Travelling Salesman</em>. A travelling salesman must visit each of some number of cities. To save costs, the salesman wants to find the shortest route that passes through all of the cities. For some given target distance “n”, is there a route of length at most “n”?</p></li>
<li><p><em>Short proofs</em>. Is there a short proof for your favourite mathematical statement (a Millennium Prize problem perhaps)? With a suitable formulation of “short”, this is NP-complete. It is in NP because checking formal proofs can be done efficiently: the hard part is finding them (at least, we think that’s the hard part!).</p></li>
</ul>
<p>In every case, we know of no efficient exact algorithm, and the nonexistence of such an algorithm is equivalent to proving P not equal to NP.</p>
<p>So are we close to a solution? It seems the best we know is that we don’t know much! Arguably, the most substantial advances in the P versus NP saga are curiously negative: they mostly show we cannot possibly hope to resolve P as different to NP by familiar techniques. </p>
<p>We know Turing’s approach cannot work. In 2007, <a href="http://www.cs.uchicago.edu/people/razborov">Alexander Razborov</a> and <a href="http://www.cs.cmu.edu/%7Erudich/">Steven Rudich</a> were awarded the <a href="http://www.eatcs.org/index.php/goedel-prize">Gödel Prize</a> (often touted as the Nobel Prize of Computer Science) for their work showing that no “natural proof” can prove P unequal to NP.</p>
<p>Of course, we’ll keep looking!</p>
<p><strong>This is the third part of the Millennium Prize Series. To read the other instalments, follow the links below.</strong></p>
<ul>
<li><strong><a href="http://theconversation.com/millenium-prize-the-navier-stokes-existence-and-uniqueness-problem-4244">Part One: Millennium Prize: the Navier–Stokes existence and uniqueness problem</a></strong></li>
<li><strong><a href="http://theconversation.com/millennium-prize-the-hodge-conjecture-4243">Part Two: Millennium Prize: the Hodge Conjecture</a></strong></li>
</ul><img src="https://counter.theconversation.com/content/4246/count.gif" alt="The Conversation" width="1" height="1" />
<p class="fine-print"><em><span>Marcel Jackson does not work for, consult, own shares in or receive funding from any company or organisation that would benefit from this article, and has disclosed no relevant affiliations beyond their academic appointment.</span></em></p>MILLENNIUM PRIZE SERIES: The Millennium Prize Problems are seven mathematics problems laid out by the Clay Mathematics Institute in 2000. They’re not easy – a correct solution to any one results in a US$1,000,000…Marcel Jackson, Senior Lecturer in Mathematics & Statistics, La Trobe UniversityLicensed as Creative Commons – attribution, no derivatives.tag:theconversation.com,2011:article/42442011-11-16T19:39:40Z2011-11-16T19:39:40ZMillennium Prize: the Navier–Stokes existence and uniqueness problem<figure><img src="https://images.theconversation.com/files/5399/original/2657830471_a1baabc557_o.jpg?ixlib=rb-1.1.0&q=45&auto=format&w=496&fit=clip" /><figcaption><span class="caption">How fluids move has fascinated researchers since the birth of science.</span> <span class="attribution"><span class="source">tonyhall</span></span></figcaption></figure><p><strong>MILLENNIUM PRIZE SERIES:</strong> <strong><em>The Millennium Prize Problems are seven mathematics problems laid out by the Clay Mathematics Institute in 2000. They’re not easy</em> – <em>a correct solution to any one results in a US$1,000,000 prize being awarded by the institute</em>.</strong> </p>
<p><strong><em>Russian mathematician Grigori Perelman was awarded the Prize on March 18 last year for solving one of the problems, the Poincaré conjecture – as yet the only problem that’s been solved. Famously, he turned down the $1,000,000 Millennium Prize.</em></strong></p>
<p><strong><em>Over the coming weeks, each of these problems will be illuminated by experts from the <a href="http://theconversation.com/institutions/the-australian-mathematical-sciences-institute">Australian Mathematical Sciences Institute</a> (AMSI) member institutions.</em></strong></p>
<p><strong><em>Here Professor Jim Denier explains the Navier–Stokes existence and uniqueness problem. Enjoy.</em></strong>
<br></p>
<p>Among the seven problems in mathematics put forward by the <a href="http://www.claymath.org/">Clay Mathematics Institute</a> in 2000 is one that relates in a fundamental way to our understanding of the physical world we live in. </p>
<p>It’s the <a href="http://www.claymath.org/millennium/Navier-Stokes_Equations/">Navier-Stokes existence and uniqueness problem</a>, based on equations written down in the 19th century.</p>
<p>The solution of this prize problem would have a profound impact on our understanding of the behaviour of fluids which, of course, are ubiquitous in nature. Air and water are the most recognisable fluids; how they move and behave has fascinated scientists and mathematicians since the birth of science. </p>
<p>But what are the so-called Navier-Stokes equations? What do they describe? </p>
<h2>The equations</h2>
<p>In order to understand the Navier-Stokes equations and their derivation we need considerable mathematical training and also a sound understanding of basic physics. </p>
<p>Without that, we must draw upon some very simple basics and talk in terms of broad generalities – but that should be sufficient to give the reader a sense of how we arrive at these fundamental equations, and the importance of the questions. </p>
<p>From this point, I’ll refer to the Navier-Stokes equations as “the equations”. </p>
<p>The equations governing the motion of a fluid are most simply described as a statement of <a href="http://www.physicsclassroom.com/class/newtlaws/u2l3a.cfm">Newton’s Second Law of Motion</a> as it applies to the movement of a mass of fluid (whether that be air, water or a more exotic fluid). Newton’s second law states that: </p>
<p><em>Mass x Acceleration = Force acting on a body</em></p>
<p>For a fluid the “mass” is the mass of the fluid body; the “acceleration” is the acceleration of a particular fluid particle; the “forces acting on the body” are the total forces acting on our fluid. </p>
<p>Without going into full details, it’s possible to state here that Newton’s Second Law produces a system of differential equations relating rates of change of fluid velocity to the forces acting on the fluid. We require one other physical constraint to be applied on our fluid, which can be most simply stated as:</p>
<p>Mass is conserved! – i.e. fluid neither appears nor disappears from our system. </p>
<h2>The solution </h2>
<p>Having a sense of what the Navier-Stokes equations are allows us to discuss why the Millennium Prize solution is so important. The prize problem can be broken into two parts. The first focuses on the existence of solutions to the equations. The second focuses on whether these solutions are bounded (remain finite). </p>
<p>It’s not possible to give a precise mathematical description of these two components so I’ll try to place the two parts of the problem in a physical context. </p>
<p>1) For a mathematical model, however complicated, to represent the physical world we are trying to understand, the model must first have solutions. </p>
<p>At first glance, this seems a slightly strange statement – why study equations if we are not sure they have solutions? In practice we know many solutions that provide excellent agreement with many physically relevant and important fluid flows. </p>
<p>But these solutions are approximations to the solutions of the full Navier-Stokes equations (the approximation comes about because there is, usually, no simple mathematical formulae available – we must resort to solving the equations on a computer using numerical approximations). </p>
<p>Although we are very confident that our (approximate) solutions are correct, a formal mathematical proof of the existence of solutions is lacking. That provides the first part of the Millennium Prize challenge. </p>
<p>2) The second part asks whether the solutions of the Navier-Stokes equations can become singular (or grow without limit). </p>
<p>Again, a lot of mathematics is required to explain this. But we can examine why this is an important question. </p>
<p>There is an old saying that “nature abhors a vacuum”. This has a modern parallel in the assertion by physicist Stephen Hawking, while referring to black holes, that “nature abhors a naked singularity”. Singularity, in this case, refers to the point at which the gravitational forces – pulling objects towards a black hole – appear (according to our current theories) to become infinite. </p>
<p>In the context of the Navier-Stokes equations, and our belief that they describe the movement of fluids under a wide range of conditions, a singularity would indicate we might have missed some important, as yet unknown, physics. Why? Because mathematics doesn’t deal in infinites. </p>
<p>The history of <a href="http://en.wikipedia.org/wiki/Fluid_mechanics">fluid mechanics</a> is peppered with solutions of simplified versions of the Navier-Stokes equations that yield singular solutions. In such cases, the singular solutions have often hinted at some new physics previously not considered in the simplified models. </p>
<p>Identifying this new physics has allowed researchers to further refine their mathematical models and so improve the agreement between model and reality. </p>
<p>If, as many believe, the Navier-Stokes equations do posses singular solutions then perhaps the next Millennium Prize will go to the person that discovers just what new physics is required to remove the singularity. </p>
<p>Then nature can, as all fluid mechanists already do, come to delight in the equations handed down to us by <a href="http://www.gap-system.org/%7Ehistory/Biographies/Navier.html">Claude-Louis Navier</a> and <a href="http://www.giffordlectures.org/Author.asp?AuthorID=160">George Gabriel Stokes</a>.</p>
<p><strong>This is the first part of the Millennium Prize Series. To read the other instalments, follow the links below.</strong></p>
<ul>
<li><strong><a href="http://theconversation.com/millennium-prize-the-hodge-conjecture-4243">Part Two: Millennium Prize: the Hodge Conjecture</a></strong></li>
<li><strong><a href="http://theconversation.com/millennium-prize-p-vs-np-4246">Part Three: Millennium Prize: P vs NP</a></strong></li>
</ul><img src="https://counter.theconversation.com/content/4244/count.gif" alt="The Conversation" width="1" height="1" />
<p class="fine-print"><em><span>Jim Denier receives funding from the Australian Research Council.</span></em></p>MILLENNIUM PRIZE SERIES: The Millennium Prize Problems are seven mathematics problems laid out by the Clay Mathematics Institute in 2000. They’re not easy – a correct solution to any one results in a US$1,000,000…Jim Denier, Head of School of Mathematical Sciences, University of AdelaideLicensed as Creative Commons – attribution, no derivatives.