The Riemann Hypothesis is probably the deepest one
In 2000, the Clay Mathematics Institute offered 7 times $1,000,000 for the proofs of the Millennium Prize Problems. Is it possible to compare which of them are deeper than others?
Needless to say, such a comparison depends on personal preferences, emotions, and there is probably no rigorous way to "prove" that one problem is deeper than others. However, that doesn't mean that one can't have an opinion; and it doesn't prevent some opinions from being more well-informed than others.
So let me offer a sketch of the seven problems and some evaluation of their depth.
The Poincaré Conjecture
I began with this one because it has been proven by Grigori Perelman. The statement of the theorem is simple:
You may ask why the problem talks about three-dimensional spheres only. Roughly speaking, it's because less-than-three-dimensional manifolds are too simple to be classified (and to prove the claims about the classification). Among the two-dimensinoal surfaces, you have Riemann surfaces with \(h\) handles – and perhaps \(b\) circular boundaries and \(c\) crosscaps, too.
And higher-dimensional manifolds become sort of simpler, too. At least those that "smell like a sphere" are easy to be put under control. Needless to say, the diversity of complicated manifolds such as the Calabi-Yau manifolds becomes more extreme for higher dimensions. But when you talk about "truly special, highly constrained" manifolds, there is a sense in which \(d=3\) maximizes the "depth of the mathematical insights" needed to understand the set of manifolds.
Perelman solved it and in some sense, the technology behind the proof is sort of "easy" and the proof allows us to say that there was "nothing totally new" hiding behind the conjecture. The proof is easy to formulate in terms of concepts that are natural in quantum field theory and especially string theory, namely the so-called Ricci flows (this idea was first proposed as a path to the proof by Richard Hamilton).
One may study strings propagating on a 3-dimensional manifold and use this "non-linear sigma-model" as an effective theory. One may try to change the characteristic world sheet length and look what it does with the whole theory. This is about the flows of the renormalization group. Effectively, such a transition to lower world sheet energies or longer distances has the effect of "rounding the target three-manifold". So if it is a potato close enough to the sphere, it will increasingly resemble the sphere with the standard metric.
Pretty much constructively, you may actually end up with the sphere. The flow of the renormalization group, the Ricci flow, may betray you because in some cases it may produce a singularity instead of making your theory ever smoother. But these possible evolutions may be controlled by some extra "surgeries" and a careful supervision of the "fundamental group" of the manifold at each stage. At the end, Perelman showed that a rather natural strategy – a method to make the spherical character of the original manifold manifest – really works and may be made totally rigorous.
There are of course many other special questions about the geometry in \(d=3\) Рin some sense, many problems of knot theory could be included here. The Poincar̩ conjecture is rooted in the "totally continuous" questions of geometry and it should therefore not be surprising that the proof sounds like a proof in mathematical physics. Such "purely continuous proofs" with very limited links to any auxiliary discrete structures etc. are very important Рespecially in physics Рbut one could argue that at the end, they're sort of straightforward once the right "physical intuition" is used.
It was great when Perelman completed the proof. But if we ignore the historical coincidence that the proof is a relatively recent event, I think that many "comparably difficult" problems and proofs in the purely continuous geometry are much more important and deeper – classification of Lie groups, classification of possible holonomies of manifolds, and so on.
Birch and Swinnerton-Dyer conjecture
This conjecture proposes a way to count the diversity of the arithmetic data defining an elliptic curve (a two-torus written as a quadratic-cubic equation in complex variables; named in this way because of links to the "elliptic integrals") by the Hasse-Weil \(L\)-function.
I don't want to go into details here but it's a counting problem that is very similar to Fermat's Last Theorem ultimately proved by Andrew Wiles. That's also why Wiles was the natural person to ask for a description of the problem. Recall that Wiles proved Fermat's Last Theorem by trying to count certain things.
It could be difficult to compare FLT and the Birch and Swinnerton-Dyer conjecture when it comes to their depth – I am no real number theorist, after all. However, let me mention that most of us loved FLT more than this particular Millennium Prize Problem. But we should acknowledge that much of this preference boils down to a relatively shallow criterion – Fermat's Last Theorem may be explained to a schoolkid. The elliptic curves are about a bit more advanced maths.
I am not sure whether this difference should be counted as evidence that FLT is "more deep". It's surely more popular because it's more accessible. But when one starts to master the actual maths that is needed for the full proof of FLT, it turns out that it's the same kind of maths that is (probably) needed to decide about the fate of this Birch-and-someone conjecture. The problems may be comparably deep and there could exist similar "truly comparable" other problems in number theory, too. FLT only differed by its being extremely accessible. I mean the proposition, not its proof which is very advanced and complicated.
FLT and this Millennium Prize Problem are examples of number theory and its connections with "geometry over discontinuous fields". One generalizes some natural concepts we know from the continuous geometry and they turn out to be relevant for problems that sound like problems about integers, especially primes and factorizations etc. (number theory). This is always a deep link. However, I will argue that the Riemann Hypothesis is probably deeper than these FLT-like problems because in the RH case, the flow of wisdom goes in both directions, more symmetrically. When we solve FLT or this Birch-and-someone problem, we learn something about integers and solutions of equations with integers etc. using methods that we also routinely use in the continuous context but we don't seem to learn much about the continuous maths.
The Hodge conjecture
The Hodge conjecture talks about the de Rham cohomology – cohomology is about the independent antisymmetric tensor fields (forms) that are closed by not exact (and, nearly equivalently, homology is the space of topologically inequivalent and non-trivial, non-contractible submanifolds of a manifold) – and it says that if you talk about manifolds that may be described via complex algebraic equations, there's also a similar way to describe all the cohomology classes as combinations of the classes of submanifolds that may also be specified by complex algebraic equations.
In some sense, this problem says that if a manifold seems to be equivalent to complex algebraic equations, then complex algebraic equations are also enough to describe all the cohomology classes. There's nothing "new" that would force you to go outside the complex algebraic "box" if you started inside the box in the first place.
It's interesting that this problem hasn't been proven but it's hard to predict the apparent depth that this problem will have after a hypothetical proof is found. Such a proof may turn out to be constructive and somewhat straightforward Рin some sense, analogous to Perelman's proof of the Poincar̩ Conjecture. It may differ e.g. from Wiles' proof of Fermat's Last Theorem by remaining "simple" for all dimensions. In order to prove FLT, Wiles had to use qualitatively more advanced mathematical techniques than the techniques you need for the proof of FLT specialized to a particular exponent such as \(n=4\). We don't know but I find it somewhat plausible that the future proof of the Hodge conjecture will be more uniform Рa more straightforward generalization of a natural proof you could construct for a particular dimension \(d\).
But of course, the proof may be much deeper than that. One must always remember that we should better talk about "a proof" because there can exist many proofs, even many qualitatively different proofs. Some of them may be much shorter than others; some of them may be much deeper than others. Only the first proof of the Millennium Prize Problems earns a million of dollars but it's always possible that another, inequivalent proof that is still in the pipeline is actually deeper and more important (but unrewarded).
The Yang–Mills existence and mass gap problem
This problem is most closely linked to quantum field theory, the main "technology" in which I was sort of professionally trained, but that doesn't mean that I consider this problem to be too deep. In fact, I don't.
The real reason is that using physical arguments, sometimes very deep ones (including wisdom hiding in the AdS/CFT), we have acquired answers to much deeper and more detailed questions than just the existence of the mass gap. To get the prize, you need to present an argument that is pretty much rigorous – and define a QFT sort of rigorously along the way. And once you complete this "paperwork", you also have to use your framework to prove a rather basic claim that pure QCD doesn't contain any "arbitrarily light massive particles"; the lightest massive particle has a strictly positive mass (comparable to the QCD scale) and nothing (i.e. gap) in between this mass and zero.
I don't think that this is a natural way towards profound insights. Quantum field theories and string theory are sort of pulsating, living animals that may be studied with the help of many techniques and perspectives that admit very precise rules and that work but that don't fit the mathematicians' fully elaborated "straightjackets" that have already been formulated in the very rigorous mathematical way. In some sense, this problem wants you to kill the pulsating animal and decompose it into some boring components that admit a totally rigorous mathematical definition.
When you do it, you will only recover some physical insights that are known to be true to the physicists – in fact, physicists may answer much more detailed and quantitative questions of this kind. I would say that the importance of the problem is in rigorous mathematicians' desire to declare that quantum field theory is "fully incorporated" to the rigorous maths, within a basic mathematical framework that has been completely found and should no longer evolve in the future. I am not sure whether I would subscribe to this thesis. QFT and string theory are already "the cutting-edge physics" tools and as physicists are discovering their new properties, they're also learning about new ways to mathematically formalize them. To write down "a definition" of a quantum field theory and to prove some basic properties of the corresponding mathematical structure is a settled subject but "all interesting knowledge about quantum field theories" is surely not a completed subject.
Navier–Stokes existence and smoothness
This problem is close to physics, in fact it is the only obvious "classical physics" problem in the list. The Navier-Stokes equations describe fluid mechanics which displays complicated phenomena, especially turbulence that looks "cool" on the pictures. That's a reason why this topic is popular. To win the prize, you must:
Turbulence leads to interesting conceptual phenomena such as a self-similarity of the relevant pictures. It's been believed for quite some time that all the relevant statistical distributions are pretty much self-similar. There is now clear evidence that this ain't the case. The self-similarity is broken at some point.
There is another issue – the real-world fluids with a cutoff at the atomic length scale may differ, when it comes to some short-distance behavior, from the fluids idealized by the Navier-Stokes equations. The problem is a mathematical one about the equations so the winner of the prize may also miss many actual real-world subtleties associated with the existence of atoms, and so on.
There are numerous interesting problems and patterns related to fluid mechanics in general and turbulence in particular that may be discussed or proved. I am just not sure whether the rigorous mathematical formulation above is a natural way to direct the researchers towards the most profound parts of these problems of mathematics of classical physics. The problem was probably incorporated in order to state that "there are still interesting math problems related to classical physics" – a thesis I would almost certainly subscribe to – but I am not sure whether the representative problem was formulated usefully.
P versus NP problem
This computer-science problem was the original reason that made me write this blog entry. Scott Aaronson didn't like that I interpreted the "P = NP problem" as a comparably messy problem to the question whether chess is a draw (whether two ideally clever chess players attempting to reach the best results inevitably end up with a draw).
Just to be sure, I do think – like most experts – that chess is a draw and that P isn't the same thing as NP.
In this computational complexity business, you have an integer \(N\) that measures the "size" of the objects in the problem you want to solve and the main question is whether the number of computer operations scaling like a power of \(N\) for large \(N\) is enough to solve such a problem in a class. The polynomially fast solutions are considered "fast"; the "slow" ones need exponentially or factorially (etc.) long timescales to be solved.
As the diagram above shows, there is a large set of NP problems. They're "quickly checkable". NP stands for "non-deterministically polynomial". They're problems such that if you're told a solution, you may verify it is a solution in a polynomial time. Verification is generally believed to be easier than the search for solutions, so that's why people generally believe that "P is not NP".
In the NP class, you have the P subclass – problems that can be (polynomially) quickly solved, not just verified. And then there is the NP-complete subset. Well, the NP-complete subset is the intersection of NP with the set of "NP hard problems" which are those that are as difficult as the hardest problems in NP. In practice, NP-complete is a limited class of problems that have been proved equally complicated as other NP-complete problems by various ways to convert one problem in the class to another (plus all the other problems that may be shown equivalent in the future). So I can just give you a representative: quickly compute the permanent of a matrix (the determinant-like sum over permutations but with no minus signs).
If P were the same as NP, which is believed to be false, then NP-complete problems, because they're still elements of the NP problems, would be solvable in a polynomial time as well, so NP-complete would be the same set as P and NP, too. In the more likely case that P isn't NP, NP-complete and P problems are two completely disjoint subsets of NP ("opposite" in their complexity).
P vs NP problem is sort of interesting because it's rather easy to be formulated but if you look closely, it's really a messy problem and there isn't a good reason why there should exist an accessible enough resolution. We're asking whether problems are polynomially quickly solvable. This very adjective is sort of contrived. From a practical viewpoint, there is usually a big difference between polynomial and longer-than-polynomial time requirements but it doesn't seem to me that this distinction is too fundamental from a deeper theoretical viewpoint. In other words, I believe that this "polynomial technicality" is already enough to classify the P vs NP problem as a "mostly practical messy problem", not a mathematically natural fundamental problem.
At the same moment, I think that some hype promoting the P vs NP problem resembles TV commercials way too much. In Wikipedia, Scott Aaronson is quoted as saying:
I may describe the same problem in the following, nearly equivalent way: the P vs NP problem is asking about the existence of an algorithm for each problem in NP and whether such an algorithm is polynomially fast. So in some sense, it's not a question about some important mathematical structures themselves but about higher-order "texts" (algorithms) that discuss the mathematical structures and their not-too-fundamental properties such as the polynomial speed.
The brute-force way to decide would be to look at all candidate algorithms and check whether they work and whether they are polynomially fast. Clearly, this can't be done in a finite time because the potential algorithms, although polynomially fast, may still be given by an arbitrarily long program.
"Finding all nicest and fastest algorithms that may solve a difficult problem" looks like an extremely creative, Mozart-like problem and it's plausible that this creative achievement is needed to decide about the P vs NP problem. In this sense, I think that not only the proof of P = NP but also the disproof probably require something extraordinarily difficult and Mozart-like. If P isn't NP, as most experts expect, it still seems natural to assume that to find the proof of "P isn't NP" is an NP-complete problem of a sort. Such a proof may be extremely long or unnatural or whatever. To decide about P = NP, it seems like you need to place yourself about "all the Mozarts" whose superioty you want to prove if you want to prove that P isn't NP. And that's a contradiction, at least a morally or practically. You shouldn't prove that all of us are inferior insects relatively to Mozart by becoming the superior supervisor and guru of Mozart and every other genius. ;-)
So I don't expect any proof of P = NP and I don't expect any proof that P isn't NP, either. One of the proofs, probably the latter, probably exists but it's probably extremely complicated and doesn't illuminate much.
The Riemann hypothesis
The Riemann Hypothesis seems to be the deepest problem to me although it may ultimately turn out to be just about one physics-related problem/insight among many.
It may be phrased as a problem on analytic functions of a complex variable: the Riemann \(\zeta\)-function has no roots away from the real axis and the \(1/2+is\) vertical line. But it may also be phrased as an equivalent problem about number theory, namely the distribution of primes. For example, an equivalent way to phrase the Riemann Hypothesis is to say\[
|\pi(x) - \operatorname{Li}(x)| \lt \frac{1}{8\pi} \sqrt{x} \, \log(x), \qquad \text{for all } x \ge 2657.
\] The number of primes smaller than \(x\) may be approximated by the integral of \(1/\ln(t)\) – this inverse logarithm function quantifies the probability that a number comparable to \(t\) is a prime – integrated up to \(x\) and the error is very small, given by the right hand side of the inequality above. (Similar but weaker statements with a larger allowed error on the right hand side may be proved, e.g. by the prime number theorem; they're equivalent to the proved non-existence of the zeroes of the \(\zeta\)-function outside the real axis and outside the width-one critical strip symmetrically located around the critical axis.)
Because of its relationships to integers and primes, the Riemann zeta function is an extremely natural function of a complex variable. In some sense, it's the most natural "non-elementary" function of a complex variable that has something to do with integers in general and primes in particular. The function may be defined in many ways, it clearly has infinitely many non-trivial zeros on the \(1/2+is\) vertical axis, and it sounds crazy we're not able to prove that it has no extra zeroes (which would be paired symmetrically with respect to this vertical axis) in the bulk of the complex plane (well, they would be in the width-one strip around the vertical axis).
The values of \(s\) for which \(\zeta(1/2+is)=0\) are very interesting, non-trivial real numbers. The Hilbert–Pólya conjecture is a general approach to the proofs of the Riemann Hypothesis that many, including myself, find extremely promising and natural. It says that the set of such real values \(s\) is the spectrum of a Hermitian operator. This operator may be defined in a way that makes the Hermiticity manifest; and that makes it manifest that the eigenvalues are linked to these zeroes i.e. special values of \(s\); that would prove that \(s\) is real and there are no other non-trivial roots (away from the axis).
In some sense, the non-integer values of \(s\), the zeroes of the Riemann \(\zeta\)-function, are "inverse" to the set of primes on the real axis. I won't tell you the exact sense but if the allowed momenta were primes, the allowed windings would be the roots \(s\) of the \(\zeta\)-function. This vague statement also implies that the zeroes of the \(\zeta\)-function become more dense, as \(2\pi\ln s\), if you go further away from the real axis; note that the probability that an integer is a prime was decreasing as \(1/ \ln n\).
I have tried many times to go one step further (or several steps). In one approach of mine, I decided that for each such zero \(s\), there is actually a whole unitary representation of \(SL(2,\RR)\). There should exist a natural physical system with the \(SL(2,\RR)\) symmetry whose states include unitary representations of this group. One has to find the physical system, prove that the second Casimirs are given by \(x(x-1)\) where \(x=1/2+is\), and the Riemann Hypothesis follows from some known results about five classes of the unitary representations of \(SL(2,\RR)\). I find it utterly natural to use the whole \(SL(2,\RR)\) and not just a generic single Hermitian operator, especially because of the role that \(x(x-1)\) plays in the \(\zeta\)-function and the role that the \(1/2+is\) vertical line plays in the theory of representations of that group.
Also, for some time, I believed that the non-existence of the physical string states above Martin Schnabl's tachyon-condensation solution to the open string field theory proved the non-existence of other non-trivial zeroes – because the form of Schnabl's solution may be written in terms of the \(\zeta\)-function, too. I have never been able to complete the proof, not even at the physicist's level of rigor, and I am not sure that a proof of this sort exists today.
At any rate, I tend to think that because the \(\zeta\)-function is so unique in the complex calculus, its very visible and manifestly correct property – the location of zeroes on two straight lines only – is something important that we should understand. The Riemann Hypothesis seems much more unique, special, and fundamental to me than any other problem discussed above.
And that's the memo.
In 2000, the Clay Mathematics Institute offered 7 times $1,000,000 for the proofs of the Millennium Prize Problems. Is it possible to compare which of them are deeper than others?
Needless to say, such a comparison depends on personal preferences, emotions, and there is probably no rigorous way to "prove" that one problem is deeper than others. However, that doesn't mean that one can't have an opinion; and it doesn't prevent some opinions from being more well-informed than others.
So let me offer a sketch of the seven problems and some evaluation of their depth.
The Poincaré Conjecture
I began with this one because it has been proven by Grigori Perelman. The statement of the theorem is simple:
Every simply connected, closed 3-manifold is homeomorphic to the 3-sphere.For three-dimensional manifolds, Perelman had to prove that everything that smells like a sphere is a sphere. The "smelling" means that the manifold is "closed" i.e. free of boundaries etc.; and it is "simply connected" which means that you can't "laso it". Every topological circle within the manifold may be gradually and continuously shrunk to a point.
You may ask why the problem talks about three-dimensional spheres only. Roughly speaking, it's because less-than-three-dimensional manifolds are too simple to be classified (and to prove the claims about the classification). Among the two-dimensinoal surfaces, you have Riemann surfaces with \(h\) handles – and perhaps \(b\) circular boundaries and \(c\) crosscaps, too.
And higher-dimensional manifolds become sort of simpler, too. At least those that "smell like a sphere" are easy to be put under control. Needless to say, the diversity of complicated manifolds such as the Calabi-Yau manifolds becomes more extreme for higher dimensions. But when you talk about "truly special, highly constrained" manifolds, there is a sense in which \(d=3\) maximizes the "depth of the mathematical insights" needed to understand the set of manifolds.
Perelman solved it and in some sense, the technology behind the proof is sort of "easy" and the proof allows us to say that there was "nothing totally new" hiding behind the conjecture. The proof is easy to formulate in terms of concepts that are natural in quantum field theory and especially string theory, namely the so-called Ricci flows (this idea was first proposed as a path to the proof by Richard Hamilton).
One may study strings propagating on a 3-dimensional manifold and use this "non-linear sigma-model" as an effective theory. One may try to change the characteristic world sheet length and look what it does with the whole theory. This is about the flows of the renormalization group. Effectively, such a transition to lower world sheet energies or longer distances has the effect of "rounding the target three-manifold". So if it is a potato close enough to the sphere, it will increasingly resemble the sphere with the standard metric.
Pretty much constructively, you may actually end up with the sphere. The flow of the renormalization group, the Ricci flow, may betray you because in some cases it may produce a singularity instead of making your theory ever smoother. But these possible evolutions may be controlled by some extra "surgeries" and a careful supervision of the "fundamental group" of the manifold at each stage. At the end, Perelman showed that a rather natural strategy – a method to make the spherical character of the original manifold manifest – really works and may be made totally rigorous.
There are of course many other special questions about the geometry in \(d=3\) Рin some sense, many problems of knot theory could be included here. The Poincar̩ conjecture is rooted in the "totally continuous" questions of geometry and it should therefore not be surprising that the proof sounds like a proof in mathematical physics. Such "purely continuous proofs" with very limited links to any auxiliary discrete structures etc. are very important Рespecially in physics Рbut one could argue that at the end, they're sort of straightforward once the right "physical intuition" is used.
It was great when Perelman completed the proof. But if we ignore the historical coincidence that the proof is a relatively recent event, I think that many "comparably difficult" problems and proofs in the purely continuous geometry are much more important and deeper – classification of Lie groups, classification of possible holonomies of manifolds, and so on.
Birch and Swinnerton-Dyer conjecture
This conjecture proposes a way to count the diversity of the arithmetic data defining an elliptic curve (a two-torus written as a quadratic-cubic equation in complex variables; named in this way because of links to the "elliptic integrals") by the Hasse-Weil \(L\)-function.
I don't want to go into details here but it's a counting problem that is very similar to Fermat's Last Theorem ultimately proved by Andrew Wiles. That's also why Wiles was the natural person to ask for a description of the problem. Recall that Wiles proved Fermat's Last Theorem by trying to count certain things.
It could be difficult to compare FLT and the Birch and Swinnerton-Dyer conjecture when it comes to their depth – I am no real number theorist, after all. However, let me mention that most of us loved FLT more than this particular Millennium Prize Problem. But we should acknowledge that much of this preference boils down to a relatively shallow criterion – Fermat's Last Theorem may be explained to a schoolkid. The elliptic curves are about a bit more advanced maths.
I am not sure whether this difference should be counted as evidence that FLT is "more deep". It's surely more popular because it's more accessible. But when one starts to master the actual maths that is needed for the full proof of FLT, it turns out that it's the same kind of maths that is (probably) needed to decide about the fate of this Birch-and-someone conjecture. The problems may be comparably deep and there could exist similar "truly comparable" other problems in number theory, too. FLT only differed by its being extremely accessible. I mean the proposition, not its proof which is very advanced and complicated.
FLT and this Millennium Prize Problem are examples of number theory and its connections with "geometry over discontinuous fields". One generalizes some natural concepts we know from the continuous geometry and they turn out to be relevant for problems that sound like problems about integers, especially primes and factorizations etc. (number theory). This is always a deep link. However, I will argue that the Riemann Hypothesis is probably deeper than these FLT-like problems because in the RH case, the flow of wisdom goes in both directions, more symmetrically. When we solve FLT or this Birch-and-someone problem, we learn something about integers and solutions of equations with integers etc. using methods that we also routinely use in the continuous context but we don't seem to learn much about the continuous maths.
The Hodge conjecture
The Hodge conjecture talks about the de Rham cohomology – cohomology is about the independent antisymmetric tensor fields (forms) that are closed by not exact (and, nearly equivalently, homology is the space of topologically inequivalent and non-trivial, non-contractible submanifolds of a manifold) – and it says that if you talk about manifolds that may be described via complex algebraic equations, there's also a similar way to describe all the cohomology classes as combinations of the classes of submanifolds that may also be specified by complex algebraic equations.
In some sense, this problem says that if a manifold seems to be equivalent to complex algebraic equations, then complex algebraic equations are also enough to describe all the cohomology classes. There's nothing "new" that would force you to go outside the complex algebraic "box" if you started inside the box in the first place.
It's interesting that this problem hasn't been proven but it's hard to predict the apparent depth that this problem will have after a hypothetical proof is found. Such a proof may turn out to be constructive and somewhat straightforward Рin some sense, analogous to Perelman's proof of the Poincar̩ Conjecture. It may differ e.g. from Wiles' proof of Fermat's Last Theorem by remaining "simple" for all dimensions. In order to prove FLT, Wiles had to use qualitatively more advanced mathematical techniques than the techniques you need for the proof of FLT specialized to a particular exponent such as \(n=4\). We don't know but I find it somewhat plausible that the future proof of the Hodge conjecture will be more uniform Рa more straightforward generalization of a natural proof you could construct for a particular dimension \(d\).
But of course, the proof may be much deeper than that. One must always remember that we should better talk about "a proof" because there can exist many proofs, even many qualitatively different proofs. Some of them may be much shorter than others; some of them may be much deeper than others. Only the first proof of the Millennium Prize Problems earns a million of dollars but it's always possible that another, inequivalent proof that is still in the pipeline is actually deeper and more important (but unrewarded).
The Yang–Mills existence and mass gap problem
This problem is most closely linked to quantum field theory, the main "technology" in which I was sort of professionally trained, but that doesn't mean that I consider this problem to be too deep. In fact, I don't.
The real reason is that using physical arguments, sometimes very deep ones (including wisdom hiding in the AdS/CFT), we have acquired answers to much deeper and more detailed questions than just the existence of the mass gap. To get the prize, you need to present an argument that is pretty much rigorous – and define a QFT sort of rigorously along the way. And once you complete this "paperwork", you also have to use your framework to prove a rather basic claim that pure QCD doesn't contain any "arbitrarily light massive particles"; the lightest massive particle has a strictly positive mass (comparable to the QCD scale) and nothing (i.e. gap) in between this mass and zero.
I don't think that this is a natural way towards profound insights. Quantum field theories and string theory are sort of pulsating, living animals that may be studied with the help of many techniques and perspectives that admit very precise rules and that work but that don't fit the mathematicians' fully elaborated "straightjackets" that have already been formulated in the very rigorous mathematical way. In some sense, this problem wants you to kill the pulsating animal and decompose it into some boring components that admit a totally rigorous mathematical definition.
When you do it, you will only recover some physical insights that are known to be true to the physicists – in fact, physicists may answer much more detailed and quantitative questions of this kind. I would say that the importance of the problem is in rigorous mathematicians' desire to declare that quantum field theory is "fully incorporated" to the rigorous maths, within a basic mathematical framework that has been completely found and should no longer evolve in the future. I am not sure whether I would subscribe to this thesis. QFT and string theory are already "the cutting-edge physics" tools and as physicists are discovering their new properties, they're also learning about new ways to mathematically formalize them. To write down "a definition" of a quantum field theory and to prove some basic properties of the corresponding mathematical structure is a settled subject but "all interesting knowledge about quantum field theories" is surely not a completed subject.
Navier–Stokes existence and smoothness
This problem is close to physics, in fact it is the only obvious "classical physics" problem in the list. The Navier-Stokes equations describe fluid mechanics which displays complicated phenomena, especially turbulence that looks "cool" on the pictures. That's a reason why this topic is popular. To win the prize, you must:
Prove or give a counter-example of the following statement:You potentially don't have to learn the answer to any interesting "physical" question. The reason why the smooth, globally defined solution to the Navier-Stokes problem exists – or doesn't exist – may be highly technical details you have to be picky about. It is not guaranteed at all that a winner of this prize must achieve some genuine progress in the "puzzling physics properties" of turbulent fluids etc.
In three space dimensions and time, given an initial velocity field, there exists a vector velocity and a scalar pressure field, which are both smooth and globally defined, that solve the Navier–Stokes equations.
Turbulence leads to interesting conceptual phenomena such as a self-similarity of the relevant pictures. It's been believed for quite some time that all the relevant statistical distributions are pretty much self-similar. There is now clear evidence that this ain't the case. The self-similarity is broken at some point.
There is another issue – the real-world fluids with a cutoff at the atomic length scale may differ, when it comes to some short-distance behavior, from the fluids idealized by the Navier-Stokes equations. The problem is a mathematical one about the equations so the winner of the prize may also miss many actual real-world subtleties associated with the existence of atoms, and so on.
There are numerous interesting problems and patterns related to fluid mechanics in general and turbulence in particular that may be discussed or proved. I am just not sure whether the rigorous mathematical formulation above is a natural way to direct the researchers towards the most profound parts of these problems of mathematics of classical physics. The problem was probably incorporated in order to state that "there are still interesting math problems related to classical physics" – a thesis I would almost certainly subscribe to – but I am not sure whether the representative problem was formulated usefully.
P versus NP problem
This computer-science problem was the original reason that made me write this blog entry. Scott Aaronson didn't like that I interpreted the "P = NP problem" as a comparably messy problem to the question whether chess is a draw (whether two ideally clever chess players attempting to reach the best results inevitably end up with a draw).
Just to be sure, I do think – like most experts – that chess is a draw and that P isn't the same thing as NP.
In this computational complexity business, you have an integer \(N\) that measures the "size" of the objects in the problem you want to solve and the main question is whether the number of computer operations scaling like a power of \(N\) for large \(N\) is enough to solve such a problem in a class. The polynomially fast solutions are considered "fast"; the "slow" ones need exponentially or factorially (etc.) long timescales to be solved.
As the diagram above shows, there is a large set of NP problems. They're "quickly checkable". NP stands for "non-deterministically polynomial". They're problems such that if you're told a solution, you may verify it is a solution in a polynomial time. Verification is generally believed to be easier than the search for solutions, so that's why people generally believe that "P is not NP".
In the NP class, you have the P subclass – problems that can be (polynomially) quickly solved, not just verified. And then there is the NP-complete subset. Well, the NP-complete subset is the intersection of NP with the set of "NP hard problems" which are those that are as difficult as the hardest problems in NP. In practice, NP-complete is a limited class of problems that have been proved equally complicated as other NP-complete problems by various ways to convert one problem in the class to another (plus all the other problems that may be shown equivalent in the future). So I can just give you a representative: quickly compute the permanent of a matrix (the determinant-like sum over permutations but with no minus signs).
If P were the same as NP, which is believed to be false, then NP-complete problems, because they're still elements of the NP problems, would be solvable in a polynomial time as well, so NP-complete would be the same set as P and NP, too. In the more likely case that P isn't NP, NP-complete and P problems are two completely disjoint subsets of NP ("opposite" in their complexity).
P vs NP problem is sort of interesting because it's rather easy to be formulated but if you look closely, it's really a messy problem and there isn't a good reason why there should exist an accessible enough resolution. We're asking whether problems are polynomially quickly solvable. This very adjective is sort of contrived. From a practical viewpoint, there is usually a big difference between polynomial and longer-than-polynomial time requirements but it doesn't seem to me that this distinction is too fundamental from a deeper theoretical viewpoint. In other words, I believe that this "polynomial technicality" is already enough to classify the P vs NP problem as a "mostly practical messy problem", not a mathematically natural fundamental problem.
At the same moment, I think that some hype promoting the P vs NP problem resembles TV commercials way too much. In Wikipedia, Scott Aaronson is quoted as saying:
"If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in 'creative leaps,' no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss..."That sounds great. We surely want to know whether everyone may be a Mozart; whether Mozart's work may be automatized. Well, it probably can't. But even if P were equal to NP, it could still be difficult to construct the "straightforward algorithm" that solves an arbitrary problem in NP. P = NP would say that a fast solving algorithm exists for each problem in NP; it doesn't say that we actually know a method how to find such an algorithm for any NP problem. For the known mutually equivalent NP-problems, you could perhaps do it but it could still be hard to find the equivalence of other NP-complete problems with the known ones (recall again that if N equals NP, then all problems in NP are NP-complete, too). The translations to the "already solved" NP problems could become "increasingly difficult" for problems that deviate from the initially solved subclass. Things could be very hard in practice even if P were equal to NP.
I may describe the same problem in the following, nearly equivalent way: the P vs NP problem is asking about the existence of an algorithm for each problem in NP and whether such an algorithm is polynomially fast. So in some sense, it's not a question about some important mathematical structures themselves but about higher-order "texts" (algorithms) that discuss the mathematical structures and their not-too-fundamental properties such as the polynomial speed.
The brute-force way to decide would be to look at all candidate algorithms and check whether they work and whether they are polynomially fast. Clearly, this can't be done in a finite time because the potential algorithms, although polynomially fast, may still be given by an arbitrarily long program.
"Finding all nicest and fastest algorithms that may solve a difficult problem" looks like an extremely creative, Mozart-like problem and it's plausible that this creative achievement is needed to decide about the P vs NP problem. In this sense, I think that not only the proof of P = NP but also the disproof probably require something extraordinarily difficult and Mozart-like. If P isn't NP, as most experts expect, it still seems natural to assume that to find the proof of "P isn't NP" is an NP-complete problem of a sort. Such a proof may be extremely long or unnatural or whatever. To decide about P = NP, it seems like you need to place yourself about "all the Mozarts" whose superioty you want to prove if you want to prove that P isn't NP. And that's a contradiction, at least a morally or practically. You shouldn't prove that all of us are inferior insects relatively to Mozart by becoming the superior supervisor and guru of Mozart and every other genius. ;-)
So I don't expect any proof of P = NP and I don't expect any proof that P isn't NP, either. One of the proofs, probably the latter, probably exists but it's probably extremely complicated and doesn't illuminate much.
The Riemann hypothesis
The Riemann Hypothesis seems to be the deepest problem to me although it may ultimately turn out to be just about one physics-related problem/insight among many.
It may be phrased as a problem on analytic functions of a complex variable: the Riemann \(\zeta\)-function has no roots away from the real axis and the \(1/2+is\) vertical line. But it may also be phrased as an equivalent problem about number theory, namely the distribution of primes. For example, an equivalent way to phrase the Riemann Hypothesis is to say\[
|\pi(x) - \operatorname{Li}(x)| \lt \frac{1}{8\pi} \sqrt{x} \, \log(x), \qquad \text{for all } x \ge 2657.
\] The number of primes smaller than \(x\) may be approximated by the integral of \(1/\ln(t)\) – this inverse logarithm function quantifies the probability that a number comparable to \(t\) is a prime – integrated up to \(x\) and the error is very small, given by the right hand side of the inequality above. (Similar but weaker statements with a larger allowed error on the right hand side may be proved, e.g. by the prime number theorem; they're equivalent to the proved non-existence of the zeroes of the \(\zeta\)-function outside the real axis and outside the width-one critical strip symmetrically located around the critical axis.)
Because of its relationships to integers and primes, the Riemann zeta function is an extremely natural function of a complex variable. In some sense, it's the most natural "non-elementary" function of a complex variable that has something to do with integers in general and primes in particular. The function may be defined in many ways, it clearly has infinitely many non-trivial zeros on the \(1/2+is\) vertical axis, and it sounds crazy we're not able to prove that it has no extra zeroes (which would be paired symmetrically with respect to this vertical axis) in the bulk of the complex plane (well, they would be in the width-one strip around the vertical axis).
The values of \(s\) for which \(\zeta(1/2+is)=0\) are very interesting, non-trivial real numbers. The Hilbert–Pólya conjecture is a general approach to the proofs of the Riemann Hypothesis that many, including myself, find extremely promising and natural. It says that the set of such real values \(s\) is the spectrum of a Hermitian operator. This operator may be defined in a way that makes the Hermiticity manifest; and that makes it manifest that the eigenvalues are linked to these zeroes i.e. special values of \(s\); that would prove that \(s\) is real and there are no other non-trivial roots (away from the axis).
In some sense, the non-integer values of \(s\), the zeroes of the Riemann \(\zeta\)-function, are "inverse" to the set of primes on the real axis. I won't tell you the exact sense but if the allowed momenta were primes, the allowed windings would be the roots \(s\) of the \(\zeta\)-function. This vague statement also implies that the zeroes of the \(\zeta\)-function become more dense, as \(2\pi\ln s\), if you go further away from the real axis; note that the probability that an integer is a prime was decreasing as \(1/ \ln n\).
I have tried many times to go one step further (or several steps). In one approach of mine, I decided that for each such zero \(s\), there is actually a whole unitary representation of \(SL(2,\RR)\). There should exist a natural physical system with the \(SL(2,\RR)\) symmetry whose states include unitary representations of this group. One has to find the physical system, prove that the second Casimirs are given by \(x(x-1)\) where \(x=1/2+is\), and the Riemann Hypothesis follows from some known results about five classes of the unitary representations of \(SL(2,\RR)\). I find it utterly natural to use the whole \(SL(2,\RR)\) and not just a generic single Hermitian operator, especially because of the role that \(x(x-1)\) plays in the \(\zeta\)-function and the role that the \(1/2+is\) vertical line plays in the theory of representations of that group.
Also, for some time, I believed that the non-existence of the physical string states above Martin Schnabl's tachyon-condensation solution to the open string field theory proved the non-existence of other non-trivial zeroes – because the form of Schnabl's solution may be written in terms of the \(\zeta\)-function, too. I have never been able to complete the proof, not even at the physicist's level of rigor, and I am not sure that a proof of this sort exists today.
At any rate, I tend to think that because the \(\zeta\)-function is so unique in the complex calculus, its very visible and manifestly correct property – the location of zeroes on two straight lines only – is something important that we should understand. The Riemann Hypothesis seems much more unique, special, and fundamental to me than any other problem discussed above.
And that's the memo.
Comparing the depth of the millennium problems
![Comparing the depth of the millennium problems]()
Reviewed by DAL
on
May 06, 2013
Rating:
No comments: