Snowden: Internet encryption useless against eyes in NSA, GCHQ

Both HTTPS, SSL, and VoIP only good against little fish

Edward Snowden has provided The New York Times and The Guardian and others with some eye-catching revelations:

N.S.A. Able to Foil Basic Safeguards of Privacy on Web (NYT)

---

NSA and GCHQ unlock privacy and security on the internet (Guardian)

The two U.S. and U.K. intelligence agencies "are investing in groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic" according to Director of National Intelligence who was quoted in the latest Snowden document about the $52 billion black budget. See also skeptical, technically sophisticated remarks by Wired. HTTPS, SSL, and VoIP are no longer safe; the correctly implemented strong encryption seems fine.



Of course, I got a bit excited: Have the agents finally built operational quantum computers? Have they made some progress that proves that \(P=NP\), after all?




Well, not really. Already the subtitle of the article in The Guardian makes it clear that the weapons that the agencies use aren't some groundbreaking advances in quantum computation or classical algorithms. Instead, they abuse the weaknesses of the human factor. Some big progress occurred in 2010, we're told.




So it seems that $250 million is spent every year to "encourage" the tech companies to insert weaknesses (backdoors and trapdoors) into their products. I suppose that to decrypt a message using state-of-the-art encryption programs, you either need to input a very long nonsensical sequence of characters that changes every day or you have to type "My name is Bond, James Bond". ;-) This sounds like a joke but it may be very close to the truth, too. NSA influences international agreements about encryption standards. Lots of supercomputers are running to break the codes by brute force but this hard work would be useless if the agencies didn't have secret agreements with folks in the tech companies.

Analysts aren't allowed to ask or speculate about the sources of the data or methods used to make the data readable. Having watched many superagent movies and having seen that I couldn't complete, I won't ask or speculate, either. NSA claims that without this control, the U.S. couldn't allow the access to the cyberspace to remain unrestricted. This claim surely sounds tough but it may have a point, too. A GCHQ team works with the "big four": Google, Facebook, Hotmail, Yahoo.

Well, as long as I feel that those agencies don't use their behind-the-scenes powerful tactics to harm free individuals for something that should always remain legal, I find the reports above just a little bit chilling. On the other hand, every capability or influence may be abused and what we're hearing seem to be extraordinary powers, indeed. It still sounds a bit more plausible when these powers belong to institutions whose composition may be refreshed according to the desires of the American (and British) voters.



Does this serious Gentleman have his own capabilities, too?

The British GCHQ seems to be among the "top two". That couldn't stop Dmitry Peskov, a Putin spokesman, from overlooking Northern Ireland and calling the United Kingdom "just a small island no one listens to" that plays no major role in the world politics and whose Chelsea and other upmarket London districts is being bought by Russian oligarchs. Cameron et al. claim that they believe that the U.K. continues to be a superpower. It's up to you to decide whose perspective is more ludicrous. ;-)

Read More

16 out of half a billion: elite Calabi-Yau manifolds with a fundamental group

Heterotic phenomenology seems to converge to an excitingly sparse shortlist of candidates

Heterotic compactifications represent a convincing – if not the most convincing – class of superstring vacua that seem to pass the "first great exam" for producing a theory of everything. A week ago, I discussed \(\ZZ_8\) orbifolds but now we return to smooth Calabi-Yau manifolds, the nice creatures you know from the popular books and from the girl who has a 3D printer.



The reason is a new hep-th paper by He, Lee, Lukas, and Sun (of China, Korea, and Oxford):

Heterotic Model Building: 16 Special Manifolds

---

...Mathematica supplements... (will be posted later)

These 16 manifolds are really special; they seem to have something that the remaining more than half a billion of manifolds in a list don't possess.




What is it? I will answer but let me begin with a more general discussion.

Calabi-Yau three-folds are used in the heterotic string model building and they're 6-real-dimensional shapes whose holonomy group is \(SU(3)\), a nice midway subgroup of the generic potato manifolds' \(O(6)\) holonomy. (Holonomy is the group of all rotations of the tangent space at any point that you may induce by the parallel transport around any closed curve through the manifold.) They come in families – topological classes. The most important topological invariant of such a manifold is the Euler characteristic \(\chi\).




For Calabi-Yaus, the Euler character (let me shorten the term in this way) may be written in terms of more detailed quantities, the Hodge numbers, as\[

\chi = 2(h^{1,1}-h^{2,1})

\] where, roughly speaking, the two terms refer to the number of topologically distinct and independent, non-contractible 2- and 3-dimensional submanifolds, respectively. In two different ways, they generalize the "number of handles" on a 2-dimensional Riemann surface. Let me assume that you know some complex cohomology calculus or you're satisfied with the sloppy explanation of mine.

These Hodge numbers \(h^{1,1},h^{2,1}\) also dictate the number of moduli – continuous parameters that can be used to deform a given Calabi-Yau manifold without changing its topology. Each Calabi-Yau seems to have a "mirror partner" (the relation is "mirror symmetry") that acts as (among other changes) as\[

(h^{1,1},h^{2,1})\leftrightarrow (h^{2,1},h^{1,1})\quad \Rightarrow\quad \chi\leftrightarrow -\chi

\] on the Hodge numbers and (as a consequence) on the Euler character. In total, \(30,108\) distinct Hodge number pairs \((h^{1,1},h^{2,1})\) are known to be realized. The number of known Calabi-Yau topologies is therefore at least equal to this number of order "tens of thousands". The plot is nice and reproduced many times on this blog and on Figure 1 in the paper.



The largest Hodge numbers appear in the "extreme" Calabi-Yaus with \((h^{1,1},h^{2,1})=(491,11)\) and its mirror with \((11,491)\). Those produce \(\chi=\pm 960\) which is the current record holder and the probability is high (but not 100 percent) that no greater Euler character is mathematically possible for the Calabi-Yau threefolds (the basic "pattern" of the picture would seem to be violated if there were larger Euler characters). In this sense, heterotic string theory predicts that there are at most \(480\) generations of quarks and leptons. The prediction seems to be confirmed experimentally. ;-)

There are of course much more detailed predictions you can make if you consider specific models.

But let me first say that there are three main methods to construct Calabi-Yau manifolds:

• CICYs, complete intersection Calabi-Yaus,
• elliptically fibered Calabi-Yaus,
• Calabi-Yau three-folds obtained from ambient four-folds coming with a reflexive polytope.

One needs to know some fancy higher-dimensional geometry and I am not a genuine expert myself but I could still give a short lecture that will have to be dramatically reduced here.

The first group, the complete intersections, are defined by sets of algebraic (polynomial) equations for homogeneous coordinates of products of projective spaces. Candelas, Dale, Lutken, and Schimmrigk began to probe this class in 1988.

The elliptically fibered ones were intensely studied e.g. by Friedman, Morgan, and Witten in 1997.

The paper we discuss now is all about the third group, the Calabi-Yau three-folds extracted from Calabi-Yau four-folds. In 2000, Kreuzer and Skarke listed \(473,800,776\) ambient toric four-folds with a reflective polytope. The list was "published" two years later. You know, it's not easy to print almost half a billion of entries in a journal. Just kidding, the full list was of course not printed. ;-)

This class obtained from four-folds seems to be most inclusive and it's this class which is enough to produce the examples with \(30,108\) pairs of the two Hodge numbers. While one can construct at least one Calabi-Yau three-fold from each four-fold, it's my understanding that the number of topologies of Calabi-Yau three-folds is vastly smaller than half a billion because there are very many repetitions once you "reduce" the four-folds to three-folds.

The new Asian/Oxford paper wants to focus on heterotic phenomenology. For such models to be viable, we need manifolds with a nontrivial (different than the one-element group \(\ZZ_1\): a clever notation, by the way, right?) fundamental group \(\Gamma\). This group counts non-contractible curves along the manifold that are needed for the symmetry breaking by Wilson lines, something that is apparently necessary to break the GUT group down to the Standard Model group in similar models (the GUT Higgs fields are totally circumvented, they probably have to be circumvented, and the Wilson-line-based stringy breaking seems more viable than GUT-scale Higgses, anyway).

In other words, we need four-folds that come in pairs. The pair includes an "upstair" manifold \(\tilde X\) that has an isometry \(\Gamma\) and the "downstair" manifold i.e. quotient \(X=\tilde X/\Gamma\).

To make the story short, they only found 16 four-folds whose order (number of elements) \(|\Gamma|\gt 1\) i.e. for which the fundamental group is non-trivial.

This is quite a reduction, from half a billion to sixteen. The basic topological data about these manifolds are listed in Table 1 on page 9 of the paper. The Euler characters of \(\tilde X\) and \(X\) belong to the intervals \(96-288\) and \(40-144\), respectively. The fundamental group \(\pi_1(X)=\Gamma\) is \(\ZZ_2\) in 13 cases, \(\ZZ_3\) in 2 cases, and \(\ZZ_5\) for 1 manifold.

There has to be quite a competition to get this small shortlist. One could argue that except for the \(16\) entries, the half a billion candidates don't allow life in the sense of the usual anthropic discussions. A non-trivial fundamental group seems to be more important for life than oxygen.

Now, for some esoteric Picard geometric reasons, they eliminate two candidates (with \(\Gamma=\ZZ_2\)) and they try to put line bundles on the remaining \(14\) manifolds and pick the manifold/bundle combinations that lead to three chiral families embedded in consistent supersymmetric models. This produces \(29,000\) models, still a pretty exclusive club. Most of them (\(28,870\)) have the \(SO(10)\) gauge group, my favorite one, when interpreted as grand unified theories broken by a Wilson line; there are \(122\) \(SU(5)\)-based models, too. If you believed that the right vacuum is a "generic" element of the list, it would be likely that the group is \(SO(10)\) which means that there exist right-handed neutrinos, among other things.

It's sort of impressive what progress has occurred in this heavily mathematical portion of string phenomenology in recent years. The advances were made possible by a combination of progress in algebraic geometry and in computer-aided algebra – and with the realization of the importance of holomorphic vector bundles that satisfy the Hermitian Yang-Mills equations as an efficient way to deal with the difficult problem of the gauge fields that have to have a profile on the compactification manifold.

Read More

Lev Pontryagin: 105th anniversary

Lev Semenovič Pontryagin was born in Moscow, Russian Empire, on September 3th, 1908, i.e. 105 years ago, and died in May 80 years later, about 25+ years ago.

Interestingly and sadly enough, a primus stove explosion made him legally blind at the age of 14. That didn't prevent him from becoming a top mathematician.

On the other hand, it didn't stop him from being a jerk of a sort, either. In 1936, he warned the Soviet officials that the mathematics community was full of counter-revolutionaries in the so-called Luzin affair. People were losing jobs. He was not only an aggressive commie, he was a sort of fascist, too. During mathematical conferences, he would scream that a pro-Israel Jewish scientist named Nathan Jacobson was a mediocre mathematician and racist because he was a Zionist. Another, even better Jewish mathematician, Grigory Margulis, won the Fields medal but couldn't get the permission to leave the USSR after Pontryagin painted him as a dirty Jew, too.

Much like other anti-Semites, he would claim that he wasn't one – he was just an anti-Zionist, everyone was told. Good try but my suspicion isn't quite gone (although I made a different conclusion 5 years ago).




Later in his career, he would work on optimization; Pontryagin's minimum principle is behind the bang-bang control. But string theorists primarily know him because of his earlier work on algebraic and differential topology.




Needless to say, the most famous concept named after him is a characteristic class now known as the Pontryagin class. (Although the Pontryagin duality for the Fourier transform on locally compact groups is also deep.) If you search through Google Scholar for papers mentioning both "string theory" and "Pontryagin class", you get 276 hits dominated by papers written by Witten, Vafa, Harvey, Moore, Sethi, Mukhi, and a few pals.

The Pontryagin class is a complexified even Chern class within a cohomology whose degree is a multiple of four. Needless to say, I don't really understand these matters well. The people for whom it's their cup of tea must think about many things in terms of vector bundles. It's probably great for them and it allows them to see and calculate many interesting things but despite a course by GM, I just couldn't learn to use those things. I need to translate bundles to some fields with some properties or physical conditions, otherwise I don't really understand them. In some sense, I feel that mathematics and not physics must be the "mother tongue" for those folks even though many of them are stellar theoretical physicists, too.

A longer CV was written 5 years ago.

Read More

Fermion masses from the Δ(27) group

Ivo de Medeiros Varzielas of Basel, Switzerland and Daniel Pidt of Dortmund, Germany released an interesting paper about the family symmetries

Geometrical CP violation with a complete fermion sector

They continue in the authors' three-weeks-old research of quark masses and Varzielas' 2012 research and other developments and argue that the \(\Delta(27)\) family symmetry seems fully appropriate to obtain not only quark masses but also lepton masses and the CP violation.




These models have (not just one but) several Higgs doublets – e.g. three Higgs doublets or a multiple of three – and a discrete symmetry is required to be respected by the scalar potential. This condition implies a relationship between the vacuum expectation values and leads to realistic patterns for quark and lepton masses. In some cases with three or more generations, the CP violation is made inevitable, too.




It's interesting because the same multi-Higgs paradigm using the \(\Delta(27)\) symmetry was exploited in Standard-Model-like braneworld models in type IIB string theory written down by Berenstein, Jejjala, and Leigh in their 2000 and 2001 papers. They had considered type IIB string theory on the \(\RR^4\times \CC^3/\Delta(27)\) orbifold.

At that time, their braneworlds looked particularly intriguing because they reduced to the almost pure supersymmetric Standard Model and inevitably predicted SUSY breaking approximately at the \(3\TeV\) scale and the stringy spectrum (!!!) at the \(10\TeV\) scale. David Berenstein believes that the model has been ruled out years ago but I forgot the exact reasons.

Nevertheless, the maths of such models seems irresistibly attractive. For decades, I tended to think that it's no coincidence that the number of extra dimensions in string theory compactifications is six, a multiple of the number of generations of fermions (three). There seem to be various constructions that promote this observation to much more than just numerology.



Symmetries are important in physics. Steven Weinberg just recorded a monologue on that very theme yesterday. Well, I have seen this "dancing Weinberg" video some time ago ;-) but if it were new, it would be a funnier coincidence. Hat tip: Phil Gibbs

Moreover, the \(\Delta(27)\) group is extremely simple and natural for the \(T^6\) compactifications: yes, it may act not just on \(\CC^3\) but also on the simply compactified sibling of it, the six-torus. How does it act? It's simple. Consider the group \(\Delta(3n^2)\) – where \(3n^2\) is the number of elements – generated by the following three transformations of three complex variables \(z_1,z_2,z_3\):\[

\eq{
e_1:\quad & (z_1,z_2,z_3)\to (\omega_n z_1,\omega_n^{-1} z_2,z_3),\\
e_2:\quad & (z_1,z_2,z_3)\to (z_1,\omega_n z_2,\omega_n^{-1} z_3),\\
e_3:\quad & (z_1,z_2,z_3)\to (z_3,z_1,z_2).
}

\] Here, \(\omega_n\) is an/the \(n\)-th root of unity. The first two generators only change the phases of the three complex variables while the third generator cyclically permutes them. Note that for \(n=3\), the group has \(27\) elements and preserves a honeycomb-cubed-like hexagonal lattice that makes it compatible with a toroidal compactification. (I can't resist thinking that there are other copies of the fixed points in the six-torus and the matter living there may look like dark matter to us although it may follow the same laws of particle physics as the matter we know. This possibility could even imply that the ratio of the dark and visible matter density in the Universe is a simple integer such as five.)



These finite groups may be easily seen to be subgroups of \(SU(3)\); see e.g. this paper on discrete subgroups of \(SU(3)\). Recall that the finite subgroups of \(SU(2)\) are classified by the ADE classification.

These groups \(\Delta(3n^2)\) may also be fully specified by the following short exact sequence:\[

0\to \ZZ_n\times \ZZ_n \to \Delta(3n^2)\to \ZZ_3\to 0.

\] The adjective "short" means that the sequence only has five elements if we also count the trivial one-element groups \(0\) at both sides. The term "exact sequence" means that in the sequence, each arrow describes a homomorphism of groups and the image (the set of possible results) of one homomorphism coincides with the kernel (the subset of the group that is mapped to the identity) of the following homomorphism.

This concept beloved by mathematicians may sound convoluted but they use it often and in this case, it's trivial to see how it works. The \(\ZZ_n\times \ZZ_n\) group is generated by the mutually commuting generators \(e_1,e_2\) above – but not \(e_3\). The first map starting in the trivial group \(0\) has image composed of the identity element of \(\ZZ_n\times\ZZ_n\) – because that's where the identity (i.e. only) element of the trivial group is mapped.

This image, the identity element of \(\ZZ_n\times\ZZ_n\), must coincide with the kernel of the following map. And indeed, the following map is simple because \(\ZZ_n\times \ZZ_n\) is mapped to a larger group by a (technically) "simple" map. The image of that map is composed of all the elements of \(\Delta(3n^2)\) that don't need the generator \(e_3\) to be written down. And indeed, this image coincides with the kernel of the following map that classifies the elements of \(\Delta(3n^2)\) by the exponent we need above \(e_3\) which is either \(0\) or \(1\) or \(2\), thus producing a \(\ZZ_3\) group. The image of that map in \(\ZZ_3\) is "everything" because the whole \(\ZZ_3\) may appear as a result and indeed, it's the kernel of the last map going to \(0\) because each element of \(\ZZ_3\) has to be mapped to the identity element of the trivial group (because this group has no other element).

There are many short exact sequences and if you just replace the 3 non-trivial groups above by something else, the story is pretty much "isomorphic" (in the colloquial sense) to the story above.

But that was just a segment of the text dedicated to some group theory. The dynamics of D-branes in the braneworlds on the orbifolds by the non-Abelian groups \(\Delta(3n^2)\) are described by the Douglas-Moore quiver theories – gauge theories with numerous simple factors (nodes in the quiver/moose diagram) and lots of added "bifundamental" matter (depicted as arrows in between those nodes). Berenstein et al. are among those who have played with this exciting technical tools in string theory for quite some time.

The anthropic fanatics may argue that there exists an overwhelming majority of \(10^{500}\) stringy compactifications that don't respect such a structure but I don't care about these majority arguments. The probability that the right compactification of string/M-theory uses the \(\Delta(27)\) group in a rather fundamental way and explains the three generations and the mass matrices of the leptons and quarks in these generations in this way seems very high to me – perhaps 10 percent if not higher – because this construction is mathematically natural and seems to explain certain things.

It can't be excluded that experimental hints of this scenario could arrive in a few years. A possible discovery of "several or many new Higgs bosons" could be a straightforward method for Nature to strengthen this sort of reasoning among the intelligent humans.

Stay tuned.

Read More

Edward Witten and the \(i\varepsilon\) prescription

What it would look like if Wolfgang Amadeus Mozart decided to discuss A440, concert pitch (440 Hz), on 24 pages?

Today, you may see the answer to a very similar question. Edward Witten finally attempted to solve a homework problem given not only to him by his (former) doctoral adviser in 1989 and wrote

The Feynman \(i\varepsilon\) in String Theory.

Almost all particle physicists learn about the \(i\varepsilon\) prescription in their introductory courses. The Feynman propagators have to have the form\[

\frac{-i}{p^2+m^2-i\varepsilon}

\] in the mostly positive \(({-}{+}{+}\cdots{+}{+})\) signature that Witten prefers. The extra infinitesimal term tells us in what direction we should circumvent the singularity when we integrate over the momenta in the loops and that's why it matters. In the position basis, the addition of the infinitesimal imaginary term answers the question whether the propagators are retarded or advanced or something in between. Yes, C) is correct: they are Feynman propagators, stupid.

Note that the extra term adds an imaginary term to something that you could naively try to define by the real principal value because\[

\frac{1}{z-i\varepsilon} = {\rm v.p.} \frac{1}{z}+i\pi\delta(z).

\] I would always say that you may imagine that this \(i\varepsilon\) is an infinitesimal limit of something like \(i\Gamma/2\) coming from a finite width (decay rate) – even if the lifetime is infinite, it has to be there for the stable intermediate particle to behave just like the unstable ones. There can't be any discontinuity if you just send the lifetime to infinity and because the form of the propagator seems obvious for the unstable particles (whose wave functions exponentially decay with time), a "trace" of the exponential decrease with time has to be inserted to the stable particles' propagators, too. This is a moment in which the arrow of time enters the fundamental formulae, by the way.




There exists a more systematic way to derive the \(i\varepsilon\) term in quantum field theories, of course. When inserted as a multiple of the Hamiltonian integrated over an infinitely long period of time, it effectively gives us the suppression \(\exp(-\varepsilon M H)\) which only picks a multiple of the ground state – and that's right because we're evaluating correlators or scattering amplitudes upon the vacuum.

From this need to reduce the path integral to the vicinity of the ground state we learn that all the masses \(m\) should be supplemented with an infinitesimal negative imaginary part so that in the rest frame where \(E=m\), \(\exp(Et/i\hbar)\) contains the factor that exponentially (but slowly) decreases with time, too. Therefore, you may imagine that \(i\varepsilon\) really came along with the mass, not with the squared momentum, and that's another way to look at the prescription.




I won't discuss these issues here. But what happens when we switch to string theory? People know how to calculate loop diagrams and it has almost seemed like we don't even need such a thing.

Well, we implicitly used it in all the calculations but we do need it, anyway. Witten argues that in string field theory, the prescription is straightforward. \(1/L_0\) appears in its propagators and has to be replaced by \(1/(L_0-i\varepsilon)\). However, it's harder to see what the prescription looks like in the normal, non-string-field-theory-based covariant calculations.

Witten's answer is that while the generic world sheets have the Euclidean signature in the conventional Euclideanized calculations, when an intermediate string goes on-shell, one has to change the signature to the Lorentzian one. Where do we change it? What are the variables – counterparts of momenta – that are treated in this way? You will have to read the paper to learn all the answers, assuming that they're right.

At any rate, the complexification of the world sheets is important for a proper definition of string theory (and similarly field theory, especially in the presence of gravity). Here, the complexification commands us to deviate from the expected signature just infinitesimally but finite excursions may be important for other physical applications.

Note that for many years, your humble correspondent has had disputes with various people including Jacques Distler who have various irrational reasons to dislike the analytic continuation and the Wick rotation and changing signatures etc. They believe that those operations make physics shaky and so on. It's reassuring to know that Witten agrees with me – these continuations and a careful incorporation of things calculable in other signatures are not only not ruining the precise consistency of physics but they're actually needed for physics to be precise.

Read More

Bernhard Riemann: an anniversary

Georg Friedrich Bernhard Riemann was born in a village in the Kingdom of Hanover on September 17th, 1826 and died in Selasca (Verbania), Northern Italy, on July 20th, 1866, i.e. 147 years ago. As you can see, he was 2 months short of 40 years when he died.

His father was a poor Lutheran pastor and a Napoleonic war veteran. His mother died when he was a kid. He was the second (oldest) among six children. Bernhard was shy, timid, afraid of speaking in public, and suffered from psychological problems and breakdowns. His math skills were obvious early on. However, he started to study a lyceum and investigated the Bible intensely, with a rough plan to become a pastor to earn some money for his family.




In 1846, his father gathered enough money to send Bernhard to University of Göttingen – to study... theology. But this has always been quite a place for mathematics. It didn't take much time for Riemann to study under Carl Friedrich Gauss himself, especially the method of least squares and similar things. After an approval from his father, Bernhard moved to University of Berlin where people like Jacobi, Dirichlet, Steiner, and Eisenstein were just teaching. After two years, in 1849, he returned to Göttingen.




In 1854, he was giving his first lectures – at the age of 28 – and the topic was nothing else than... the Riemannian geometry. These were times when without much ado, results of this magnitude could have been presented as an ordinary lecture for students. Some "extraordinary professor Riemann" efforts failed but at least, he started to get a proper salary and after Dirichlet's death, he would become the head of the mathematics department.

He married Elise Koch and they had a daughter. Riemann wanted to avoid wars so during the Austro-Prussian war that was taking place in Göttingen, he began to flee to Italy. Tuberculosis killed him there in July 1866, 34 days before that so-called Seven Weeks' War ended by Peace of Prague – Prussia gained some territory and my empire of Austria lost its previous right to define the intra-German relations and unification (the latter effectively started from scratch). His health has always been unreliable.

Riemann was a pure mathematician and among pure mathematicians, he was one of the most influential ones when it comes to the impact on physics. He not only invented the non-Euclidean (or generalized Euclidean) Riemannian geometry that became the basis of Einstein's general theory of relativity (substitute a long essay on the liberation out of the Euclidean straitjacket here). He was also the first man to propose that the physical reality could have extra dimensions (65 years before Kaluza initiated the research of Kaluza-Klein theory), something that only became obvious with the rise of string theory a few decades ago (about 120 years after Riemann's lecture). Many of the things we are using today were presented by Riemann in 1854 in their final form. Many others are more modern and would undoubtedly make Riemann happy.

His contributions to mathematics – the kind of mathematics that is mostly important for physicists (and the type of mathematics that you often encounter on this blog) – were numerous. Riemann surfaces, their topology, Riemann integrals using Riemann sums, Riemann–Liouville differintegral, Riemann zeta function, Riemann hypothesis, monodromies and the hypergeometric functions, and so on, and so on. It's really remarkable how many deep discoveries this former would-be theologian has done in less than 40 years that a mingy God gave him to spend on Earth.

Read More

Cumrun Vafa: Strings and the magic of extra dimensions

One month ago, Cumrun Vafa's son determined that he needed to go to Bangalore, South Central India, and because Cumrun is a good father, he went with him.



So why wouldn't he give a public talk (one hour and one second) about strings and the magic of extra dimensions at the local campus of the Tata Institute of Fundamental Research?




In the first sentence, Vafa denies that he was there by pure coincidence. He always wanted to visit India etc. ;-)

The sound quality isn't great... Moreover, you constantly hear the transmission from cell phones. Bangalore is a major global center of outsourcing and telephone services for various corporations so the audience may be just working while listening to Cumrun. :-)

He starts with Newton, a galaxy, and the flat space. Then (6:55) he shows the same smoking Einstein animation that I am using in my public talks as well. :-)




Around 7:00, the space already gets curved and waving. Straight lines in spaces of positive and negative curvature look like attraction or repulsion. LOL, at 12:24, there's another exact picture from my public talks, the structure of the atom. I suspect that Cumrun may have used the file of mine. ;-) Yes, I use this exact picture of Feynman at 12:50 and the animated Feynman diagram at 13:05, too. :-)

Disasters from the QFT+GR union; strings arrive around 15:00. He recalls the bizarre birth of string theory – a cute formula; there seem to be strings in it. 16:50, quark goes to string, another animated GIF from my public talks. The same about the animated string Feynman diagram at 17:35. Just to be sure, I gave Cumrun the permission to use anything used in my presentations, especially because I didn't create most of these pictures. Yup, 17:55, another one. Here he's also saying very similar things that I am saying at similar places of my talks and this agreement comes from two independently thinking brains.

At 30:30, Cumrun declares the string dualities to be the deepest discovery made by physicists in a century. Quite a big statement but surely a justifiable one. He says many excited things about the magic that a dual description emerges in each regime and we don't know how. It was a surprise and we don't quite know why it happens. Well, I sort of feel that I know why it has to happen. The issue is that in any asymptotic limit, there has to be a simplification and a hierarchy between energies from various objects/contributions and if a new low-energy continuum forms, it may always be organized into states of an object with a certain number of dimensions.

Lots of brane physics etc. Around 46:20, a stringy calculation of the CKM matrix is boasted. Smooth topology changing processes. We should be proud about the extra dimensions, not ashamed of them.

Read More

Quintuplets in physics

Cool anniversary: In late January, we celebrated the 30th anniversary of the announcement of the discovery of the W-boson. Today, we celebrate the 30th anniversary of the Z-boson. They were comparably important discoveries to the recent discovery of the God particle.

---

Sport: Viktoria Pilsen defeated Hradec, a much weaker team, 3-to-0 in the last round so we won the top soccer league for the 2nd time (after 2011). Because the Pilsner ice-hockey team has won the top league as well, Pilsen became the 2nd town in Czechia after Prague that collected both titles in the same year (correction: wrong, 3rd town, Ostrava did it in 1981).

Ms Alexandra Kiňová (23) is expecting the first Czechia's naturally born quintuplets (a package of 5 babies) on Sunday morning (tomorrow; update: they're out fine) which would mean that we match the achievement of the most fertile U.S. state – Utah – from the last week.

The Daily Mail tells us that the pregnancy has been easy so far. Doctors were still talking about "twins" in January and "quadruplets" in April. The probability that a birth produces \(n\)-tuplets goes like \(1/90^{n-1}\) or so but the decrease slows down relatively to this formula for really high representations.

In physics, quintuplets are rare, too. By quintuplets, we mean five-dimensional irreducible representations of groups.




Correct me if I am wrong but I think that among the simple Lie groups, only \(SU(2)=SO(3)\), \(USp(4)=SO(5)\), and \(SU(5)\) have irreducible five-dimensional representations. Let's look at them because looking at all quintuplets in group theory and physics is a rather unusual direction of approach to a subset of wisdom contained across the structure of maths and physics.




First, \(SU(2)\). That's a three-dimensional group of \(2\times 2\) complex matrices \(M\) obeying \(MM^\dagger={\bf 1}\) and \(\det M=1\). The basic isomorphisms behind spinors imply that this group is the same as the group \(SO(3)\) of rotations of the three-dimensional space except that the matrices \(+M\) and \(-M\) have to be identified.

The irreducible representations of \(SU(2)\) are labeled by the spin \(j\) which must be either non-negative integer or positive half-integer (only the former may also be interpreted as proper representations of \(SO(3)\); the latter change their sign after a 360-degree rotation). Because the \(z\)-projection goes from \(m=-j\) to \(m=+j\) with the spacing equal to one, the representation is \((2j+1)\)-dimensional.

The \(j=0\) representation is the trivial singlet that doesn't transform at all; the \(j=1/2\) is the two-dimensional pseudoreal spinor; the \(j=1\) representation is equivalent to the usual 3-dimensional vector; the \(j=3/2\) representation is a gravitino-like four-dimensional "spinvector". And finally, the \(j=2\) representation is the traceless symmetric tensor. What do I mean by that?

Imagine that you consider the tensor product \(V\otimes W\) of two copies of the three-dimensional vector space \(V=W=\RR^3\). The tensor product is composed of objects \(T_{ij}\) where \(i,j\) are vector indices: it's composed of tensors. Clearly, such a tensor has \(3\times 3 = 9\) independent components. They can be split into several pieces:\[

{\bf 3}\otimes {\bf 3} = {\bf 5} \oplus {\bf 1}\oplus {\bf 3}

\] The identity \(3\times 3 = 5+1+3\) is the consistency check that verifies that the representations above have the right dimensions but the boldface identity above says more than just the arithmetic claim about the integers: the two sides are representations of whole groups and the identity says that they're transforming in equivalent ways under all elements of the group. Why is this decomposition right? Well, the tensor \(T_{ij}\) may be divided to the symmetric tensor part which is 6-dimensional and the antisymmetric tensor which is 3-dimensional (it is equal to \(\epsilon_{ijk}v_k\) i.e. equivalent to some vector \(v_k\)).

However, the 6-dimensional symmetric tensor isn't an irreducible representation of \(SO(3)\). The trace \[

\sum_{i=1}^3 T_{ii}

\] is independent of the coordinate system i.e. invariant under rotations and may be separated from the 6-dimensional representation. The trace may be set to zero by removing it i.e. considering\[

T^\text{traceless part}_{ij} = T_{ij} - \frac 13 \delta_{ij} T_{kk}

\] and such a traceless tensor has 5 independent components; it is a quintuplet. The quadrupole moment tensor is one of the most famous applications of this 5-dimensional object. You could think it's just an accident that this number 5 is equal to the number of integers between \(m=-2\) and \(m=+2\); you could claim that the agreement is pure numerology, an agreement between the dimensions of two representations. But it is more than numerology: the representations are completely equivalent. The translation from the components \(T_{ij}\) of the (complexified) traceless tensor and the five complex amplitudes \(c_m\) for \(-2\leq m\leq 2\) is nothing else than a linear change of the basis. It has to be so because for every \(j\), the representation of \(SU(2)\) is unique.

Now, let's talk about \(SO(5)\). Clearly, this group of rotations of the 5-dimensional space has a 5-dimensional vector representation consisting of \(v_i\). But what some readers aren't aware of is that the group \(SO(5)\) may also be identified with the isomorphic \(\ZZ_2\) quotient of a spinor-based group, namely \(USp(4)\). What is this group? It's a unitary (U) symplectic (Sp) group of complex \(4\times 4\) matrices \(M\) that obey\[

MM^\dagger = M^\dagger M = 1, \quad M A M^T = A.

\] Both conditions have to be satisfied. The first condition is the well-known unitarity condition, effectively meaning that \(s_i^* s_i\) is kept invariant (it's the squared Pythagorean length of the vector computed with the absolute values). The other condition is equivalent to keeping the antisymmetric cross-like product of two vector-like objects \(s_i A_{ij} t_j\) invariant where \(A_{ij}\) are elements of the (non-singular) antisymmetric matrix \(A\) above. Note that in this invariant, there is no complex conjugation.

Simple linear redefinitions of the 4 complex components \(s_i\) may always translate your convention for \(A\) mine which is \[

A = \text{block-diag} \zav{ \pmatrix{0&+1\\-1&0}, \pmatrix{0&+1\\-1&0} }

\] You just arrange the right number of the "simplest nonzero antisymmetric matrices" along the (block) diagonal. The two conditions (unitary and symplectic) may be then seen to imply that \(M\) is composed of \(2\times 2\) blocks of this form\[

\pmatrix{ \alpha&+\beta\\ -\beta^*&\alpha^*},\quad \alpha,\beta\in\CC

\] and the addition+matrix-multiplication rules for such matrices are the same rules as the addition+multiplication rules for the quaternions \(\HHH\). So the group \(USp(2N)\) may also be called \(U(N,\HHH)\), the unitary group over quaternions. In particular, \(USp(4)=U(2,\HHH)\). Such a quaternionization is possible with all pseudoreal representations.

So the 4-dimensional complex (actually pseudoreal!) fundamental representation of \(USp(4)\) is complex-4-dimensional (but it is equivalent to its complex conjugate because it's pseudoreal!) and it may be viewed as a spinor of \(SO(5)\). It is no coincidence that \(4\) in \(USp(4)\) is a power of two. How do you get the five-dimensional \(j=1\) vector out of these four-dimensional spinors?

Note that for \(SO(3)\sim SU(2)\), we had\[

{\bf 2}\otimes{\bf 2} = {\bf 3}\oplus {\bf 1}.

\] The tensor product of two spinors produced a vector (triplet; also the symmetric part of the tensor with two spinor indices) and a singlet (the antisymmetric part of the tensor with two 2-valued indices). Similarly, here we have\[

{\bf 4}\otimes{\bf 4} = {\bf 5}\oplus {\bf 1}\oplus {\bf 10}.

\] The decomposition of \(4\times 4 = 16\) to \(6+10\) is the usual decomposition of a "tensor with two spinor indices" to the antisymmetric part and the symmetric part, respectively. The symmetric part may be identified as the antisymmetric tensor with two vector indices, note that \(5\times 4 / 2\times 1 = 10\). And the antisymmetric part is actually irreducible here. It's because the invariant for the symplectic groups is antisymmetric, \(a_{ij}\), rather than the symmetric \(\delta_{ij}\) we had for the orthogonal groups, so it's the antisymmetric part that decomposes into two irreducible pieces.

By tensor multiplying \({\bf 4}\) with copies of itself, we may obtain all representations of \(USp(4)\) and \(SO(5)\) by picking pieces of the decomposed tensor products. That's what we mean by saying that the representation \({\bf 4}\) is "fundamental". Whenever an even number of these \({\bf 4}\) factors appears in the tensor product, we obtain honest representations of \(SO(5)\) that are invariant under 360-degree rotations and all these representations may also be given a natural description in terms of tensors with vector indices.

Finally, the special unitary group \(SU(5)\) has an obvious 5-dimensional complex representation. It is a genuinely complex one, i.e. a representation inequivalent to its complex conjugate:\[

{\bf 5}\neq \overline{\bf 5}

\] This representation (and its complex conjugate, of course) is important in the simplest grand unified models in particle physics. One may say that \(SU(5)\) is an obvious extension of the QCD colorful group \(SU(3)\). We keep the first three colors (red, green, blue, so to say) and add two more colors that are interpreted as two lepton species from the same generation. The full collection of fifteen 2-component left-handed spinors per generation (they describe quarks and leptons; a Dirac spinor is composed of two 2-component spinors; the right-handed neutrino is not included among the fifteen) is interpreted as \[

{\bf 5}\oplus\overline{\bf 10},

\] the direct sum of the fundamental quintuplet of \(SU(5)\) we have already mentioned and the antisymmetric "tensor" with \(5\times 4 / 2\times 1\) components. Note that the counting of the components is the same as it was for the representation of \(SO(5)\) above. However, the 10-dimensional representation of \(SU(5)\) is a complex one, inequivalent to its complex conjugate (I won't explain why the bar appears in the decomposition above, it's a technicality). The list of 15 spinors may be extended to 16, \(10+5+1\), if we add one right-handed neutrino and this \({\bf 16}\) is then the spinor representation of \(SO(10)\), a somewhat larger group that is capable of being the grand unified group (it is no accident that 16 is a power of two: that's what spinors always do).

The number 5 may be thought of as the first "irregular" integer of a sort but it is still small and special enough and is therefore linked to many special things in maths and physics. In maths, five is special because the square root of five appears in the golden ratio; and a pentagram may be constructed by a pair of compasses and a ruler (these two facts are actually related). Quadrupole moments, moments of inertia, five-dimensional rotations, and grand unifications are among the physical topics in which 5-dimensional representations are used as "elementary building blocks".

I hope that Ms Kiňová's birth will be as smooth as her pregnancy.

Read More

Heuristic ideas about bounded prime gaps

Why Yitang Zhang's proof is probably far less fundamental than the claim

Yitang Zhang worked at Subway before he would land a mathematics job. And when he did, he wasn't publishing almost anything for years before he would offer a proof of something rather important weeks ago. That turned the name of the popular math instructor in New Hampshire into one of the most well-known names of number theorists in the world.



Some increasingly popular links are:

Bounded gaps between primes (Zhang's technical paper)

---

Philosophy behind the proof (Math Overflow)

---

First proof that... (Nature)

---

Prime number breakthrough by unknown professor (Telegraph)

If \(p_1,p_2,p_3,\dots =2,3,5,\dots\) denotes the \(n\)-th prime, the statement proven by Zhang may be phrased in a very simple way:\[

\liminf_{n\to\infty} (p_{n+1}-p_n) \lt 70,000,000.

\] The operator above is called the limit inferior which is just\[

\liminf_{n\to\infty}x_n := \lim_{n\to\infty}\Big(\inf_{m\geq n}x_m\Big)

\] If you think about this limit of the infimum for a while, you will understand that the limit inferior in the claim proved by Zhang is just the smallest gap between the adjacent primes that is realized infinitely many times (for infinitely many pairs). In other words, there exists at least one number – a potential gap between adjacent primes – that is realized infinitely many times.




Because of some technical properties that probably depended on many personal choices that Zhang has made while attacking the problem, the upper bound in the inequality turns out to be a high number, namely 70 million. It is such a high number that for all practical purposes, the proposition proven by Zhang is de facto equivalent to\[

\liminf_{n\to\infty} (p_{n+1}-p_n) \lt \infty

\] i.e. to the claim that there exists a finite number that is realized as the gap between adjacent primes in infinitely many pairs.




On the other hand, as I will argue, the actually correct (but rigorously unproven) claim stronger than Zhang's theorem says\[

\liminf_{n\to\infty} (p_{n+1}-p_n) = 2

\] which means that even twin primes – pairs of primes that differ by two – are realized infinitely many times: there are infinitely many pairs of twin primes. This claim is the famous twin prime conjecture. In some sense, the assertion proven by Zhang is 35 million times weaker than the twin prime conjecture. Note that the first twin primes are\[

(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), \\
(71, 73), (101, 103), (107, 109), (137, 139), \dots

\] and there doesn't seem to be the tiniest reason to think that the list should terminate at some point. The largest currently known twin prime pair is \(2,003,663,613\cdot 2^{195,000}\pm 1\), two similar numbers that have 58,711 digits (each).

I don't plan to study the proof in detail because it looks very complicated and "non-unique" to me. The proven statement is slightly interesting but the proof is probably less interesting – there's just a small chance that I am wrong – and there's less "profound message" to learn from it. It's like if you are interested in the Moon and someone asks you to study O-rings in the Apollo spacecraft.

Moreover, I am not too interested in the claim that has been proved. But there is one more key reason: I feel certain that the proposition is true. The reason behind this certainty is the validity of a much stronger claim – a not quite rigorously defined one – that implies the twin prime conjecture, Zhang's proof, and many and many other much weaker corollaries. The claim is that

except for patterns that may be easily proved, the prime integers are distributed randomly and independently with \(1/ \ln n\) being the probability that a random number close to \(n\) is a prime.

This general – somewhat vague but still very important – claim has many consequences, including the Riemann Hypothesis. In fact, the character of the proposition above is more or less a special case of Gell-Mann's totalitarian principle in physics:

Everything that isn't forbidden is mandatory.

By this quote that generalizes the experience of the people suffering under totalitarian regimes such as communism and Nazism (there's no freedom: they tell you what to do and what not to do) to all of physics, Gell-Mann meant that the coefficient of every interaction in a Lagrangian or the probability of any resulting complicated process is nonzero unless one may use a symmetry or another rock-solid principle to prove that the coefficient is zero (because it violates the symmetry or another sacred principle).

In this analogy, "patterns that are easy to prove" are analogous to the "symmetries or other principles forbidding certain things". May I explain what I mean in the case of primes?

A pattern that is easy to prove is, for example, that if \(n\) is a prime, then \(n+1\) and \(n-1\) are not primes, assuming that \(n\gt 3\). It's because except for \(n=2\), only odd numbers may be prime. Similarly, among six consecutive integers greater than \(12\), just to be sure, at most two numbers may be primes. It's because only three numbers among the six are odd; and one of them is a multiple of three. One could continue with many examples of this kind.

Similarly, using the Gell-Mann totalitarian principle, one may demonstrate that the twin prime conjecture and its generalizations hold. There doesn't seem to be any reason why the difference between primes shouldn't be equal to two (or some other allowed even numbers) – there are many examples in which it is two, in fact – so there must exist infinitely many examples for the probability that \(n\) and \(n+2\) are both primes to be nonzero. Of course, it's hard to prove that "there is no reason why twin primes should stop at some point", either, but at least, one may prove that there exist no "reasons of the well-known types".

A TRF-based heuristic proof of the prime number theorem

Now, the density of primes around \(n\) asymptotically goes like \(1/ \ln n\). This is the right estimate for \(n\to\infty\), including the right numerical prefactor (the relative error goes to zero in the limit). This statement is known as the prime number theorem and it is a severely weakened sibling of the Riemann Hypothesis which may be equivalently stated as the (easy-to-prove) assertion that the roots of \(\zeta(s)\) only exist for \(s\in\RR\) or in the critical strip \(0\leq {\rm Re}(s)\leq 1\).

I can offer you a supersimple, Lumoesque argument why the density of primes goes like \(1/\ln(n)\). Call the functional dependence of the density \(\rho(n)\); it's really the probability that the number around \(n\) is prime. A number \(n\) is prime if it is not divisible by any prime smaller than or equal to \(\sqrt{n}\). These are statistically independent conditions. So\[

\rho(n) = P_{n\in{\rm primes}} = \prod_{p\leq \sqrt{n}}^{p\in{\rm primes}} (1-1/p)=\dots

\] because the probability that a random large \(n\) isn't a multiple of \(p\) equals \(1-1/p\). But the product may be written as the exponential of the sum of logarithms\[

\dots = \exp\sum_{p\leq \sqrt{n}}^{p\in{\rm primes}} \ln (1-1/p) = \dots

\] and the sum over primes \(p\) may be approximated by the sum over all integers \(i\) weighted by the probability \(\rho(i)\) that \(i\) is prime:\[

\rho(n) = \dots = \exp \sum_{i\leq\sqrt{n}} \rho(i) \ln (1-1/i).

\] Now, the sum over \(i\) may be approximated by an integral when \(\rho(i)\) is smoothened. Take the logarithm of the identity above (with the sum replaced by the integral)\[

\ln\rho(n) = \dots = \int_1^{\sqrt{n}} \dd i\, \rho(i) \ln (1-1/i)

\] and differentiate it with respect to \(n\) to get\[

\frac{\rho'(n)}{\rho(n)} = \frac{1}{2\sqrt{n}} \rho(\sqrt{n}) \ln(1-1/ \sqrt{n})\sim -\frac{\rho(\sqrt{n})}{2n}

\] where \(1/2\sqrt{n}\) came from \(\dd(\sqrt{n})/\dd n\) and where \(\ln(1-x)\sim -x\) because \(x\to 0^+\). One may easily verify that \(\rho(n)\sim 1 / \ln(n)\) satisfies the identity above; both sides are equal to \(-1/ n\ln(n)\) in that case. Among uniformly, nicely decreasing functions \(\rho(n)\), this solution may be seen to be unique. Even the coefficient in front of the logarithm or, equivalently, the base of the logarithm (\(e\)) may be seen to be determined by the (nonlinear) condition above.

You may check how Terence Tao imagines a heuristic proof of the prime number theorem. I leave you to decide who among the two of us is the cumbersome overworked craftsman and who is the seer. ;-)

At any rate, the heuristic proofs above aren't rigorous but one may rigorously prove the prime number theorem. One may also prove other things. As you can see by comparing various proofs sketched by various people – or the same people at various moments – there are many strategies that may be used to attack similar problems. When we're rigorously proving something like that in mathematics, we often work with lots of inequalities – not only the final one that e.g. Zhang has proved; but also with many inequalities in the intermediate steps. And the inequalities are usually ad hoc. We want to find an object that is "good enough to achieve a certain next step" but how good this good enough object has to be isn't quite determined. What the next step has to be isn't quite determined, either. There's simply a lot of freedom when one designs a proof.

It's very likely that some other mathematicians will improve Zhang's proof so that they will reduce the constant 70 million to something smaller. Such proofs may be perhaps obtained as "modest mutations" of Zhang's machinery. However, it's unlikely that someone will reduce the constant 70 million to a constant smaller than 6 while keeping the bulk of Zhang's proof intact because certain tools become inapplicable for such small gaps (see the Math Overflow summary of the proof).

The proof of the actual twin prime conjecture will probably have to be completely different than Zhang's proof. It's nice that he has achieved a rigorous proof of a theorem that is a weaker version of the twin prime conjecture but I doubt that one can learn a lot by studying the details of his proof. There had to be so much freedom when he designed it. So it's like a NASA rocket engineer's decision to study every detail of a Soyuz aircraft. I don't think that this is the most important activity needed to conquer the outer space. Much like the Soyuz spaceships, Zhang's proof probably have many idiosyncrasies reflect the Russians' and the Chinese-American man's suboptimal approach to problems.

In mathematics and theoretical physics, when something is just being proved, we often encounter two different situations: in one subclass, the methods needed to prove something give us such new insights that these insights – methods, auxiliary structures that were used to complete the proof, and so on – are actually more valuable than the statement that has been proven. But I tend to think that Zhang's proof belongs to the opposite class of situations – in which the proof is less important than the assertion because it's composed of many idiosyncratic steps and tricks that are probably inapplicable elsewhere and that may be replaced by completely different "building blocks" to prove even the desired proposition.

Of course that I can't be quite sure about this pessimistic appraisal of the proof's methodology if I haven't actually mastered the proof. But because of general reasons and experience, I believe it's the case, anyway. Moreover, I tend to believe that the theorem proved by Zhang – and even the twin prime conjecture that may be proved in the future – is extremely weak relatively to some rigorous formulations of Gell-Mann's totalitarian principle applied here which says something like "the distribution of primes is random except for [simple divisibility-based] patterns that may be easily demonstrated". I tend to believe that such a principle will ultimately be formulated in a rigorous way and proved by a rather simple yet ingenious method, too.

You should understand that if I believe that this elegant goal is a legitimate, finite, \({\mathcal O}(1)\) task for some future mathematicians, it's also reasonable for me to believe that the assertion by Zhang and its seemingly cumbersome proof is a nearly infinitesimal fraction of what mathematicians will achieve sometime in the future. Zhang's proof represents a kind of the cutting edge that the mathematicians are able to prove about similar propositions today. But do I really care about the cutting edge? This cutting edge, much like most cutting edges in mathematics, is made terribly modest by the mathematicians' uncompromising insistence on complete rigor. If one is actually interested in the truth and is satisfied with arguments suggesting that something is true at the 5-sigma or 10-sigma confidence level, in some counting, the cutting edge is elsewhere – it's much further.

So of course that the hunt for strictly rigorous proofs that has defined mathematics after its divorce with physics is a legitimate goal – a constraint worshiped by a large group of professionals, the mathematicians in the modern sense. However, the strict rules of this hunt inevitably imply that in many cases, these professionals place themselves miles beneath the actual cutting edge of knowledge as I understand it.

And that's the memo.

Read More

Augustin-Louis Cauchy: an anniversary

By the number of mathematical papers he wrote, Augustin-Louis Cauchy was second just to Leonhard Euler. As many college freshmen may testify, more theorems and concepts in mathematics were named after Cauchy than anyone else. And a conservative theoretical physicist shouldn't omit a CV of Cauchy because Cauchy was... well... very conservative!

He died on May 23rd, 1857, i.e. exactly 156 years ago. But before he managed to do that, he had to do many other things. For example, he had to be born – in August 1789, just a month after Bastille was stormed by a crowd on the street, a mess we often call the beginning of the French Revolution.




Louis François Cauchy, i.e. Cauchy's father, had really nothing to do with this mess. He was a high official in the Parisian police before the revolution took over (during the "New Regime"). During the Reign of Communist Terror in 1794, when Cauchy was five, the family had to move to Arcueil. Things got safer when Robespierre – a guy who worked to transform bourgeoisie to a gang of leftwingers – was finally executed in 1794 and the family could return. When Napoleon took over 5 years later, Cauchy's father returned to police.

He was working directly under another high-tier policeman called Pierre-Simon Laplace who is today known, ehm, as a top mathematician. Joseph Louis Lagrange was well-known to the Cauchy family, too.




In fact, Lagrange advised Cauchy's father to enroll his son into the Central School of Pantheon. And no, Lagrange didn't want Cauchy to learn some proper mathematics. Due to uncle Lagrange's advices, Cauchy was supposed to learn classical languages and humanities. And he has won many prices in Latin and humanities, indeed. But despite the attempts by Lagrange to direct young Cauchy to this sissies' stuff, he chose an engineering career. In 1802, he scored among top 1% of the applicants to École Polytechnique and was accepted. He had some problems with the military-style rules in the school but he finished the school when he was 18, with the highest honors, and continued with civil engineering at the School for Bridges and Roads.

When he was 21, he already started to work as an engineer as well as a manager at something that Napoleon intended to become a naval base, Cherbourg. He had enough time to work on mathematical papers, anyway. His first two manuscripts on polyhedra were accepted; the third one on conic sections was rejected.

When he was 23, he realized he was overworked and the engineering job sucked, so he returned to Paris. He formally remained an engineer but was working for the ministry of interior and was on an unpaid sick leave etc. More importantly, he would work on higher-order algebraic equations, symmetric groups, symmetric functions, and the other Galois-like stuff (Évariste Galois himself was just an infant at that moment!).

In 1815, Napoleon was defeated in Waterloo – just to be sure, the place is very far from the Perimeter Institute – and Bourbon king Louis XVIII led the restoration attempts. So at the Academy of Sciences, mathematician Gaspard Monge and thermodynamics pioneer Lazare Carnot had to be fired for political reasons while Cauchy could have been hired for the same reasons. ;-)

Cauchy accepted but because a big part of the academic establishment was already composed of politically correct, left-wing activists, the reaction of his peers to his acceptance was harsh. He earned many enemies. In 1815, Cauchy could finally quit the engineering job and take the professor chair at École Polytechnique after Louis Poinsot who left for health reasons. Before that, Cauchy had already proven Fermat's polygonal number theorems. Many liberal activists could have been fired from the Bonapartist school while conservative Cauchy – whom Wikipedia calls "reactionary" – could be promoted.

He was living with his parents when he was 28 but his dad found a wife for him – a babe from a family that published most of Cauchy's writings. They had two daughters. Incidentally, Cauchy had brothers who became lawyers and one of them partly a mathematician, too.

As a mathematical factory, Cauchy flourished in the mid-to-late 1820s because he was lucky to live in a conservative political atmosphere. In 1824, Louis XVIII died and was superseded by an even more right-wing king, Charles X, which made Cauchy even more happy and more productive. He was also teaching at several schools simultaneously.

Things changed discontinuously in 1830. Charles X had to flee and the leadership was hijacked by a non-Bourbon king Louis-Philippe. Riots involving ignorant students took place near Cauchy's home. It had to be really annoying. Cauchy's lust to publish papers went nearly to zero – it's similar to my year around 2005 except that I had to be satisfied with a "relative conservative" in the form of Larry Summers who was finally removed in 2006. ;-)

Cauchy went to exile. In Switzerland, they still wanted him to endorse the new regime. He refused so he lost all positions he had in France. He went to Turin, Italy in 1831 and became a foreign member of the Royal Swedish Academy of Sciences.



Prague in 1830

In 1833, Cauchy moved to Prague in my homeland, the Austrian Empire ;-), to become a tutor of Henri of Artois, a spoiled brat from an aristocratic family. Back in Paris, Cauchy was already a bad lecturer and his teaching style resembled that of Sheldon Cooper. These difficulties escalated with young Henri who had no respect for Cauchy, mathematics, or anything of the sort, so even though Cauchy took the job very seriously, it was a disaster. The two main results of this tutoring was that an irrelevant Henri became a life-long math hater; and Cauchy hadn't done any research for 5 years. In 1838, he returned to Paris with his family that had been accompanying him in Prague since 1834.

He couldn't return to teaching – formally because he refused to endorse the new regime – but he badly wanted to be formally recognized by the science establishment in Paris again. He decided to get "there" though the Bureau to Determine the Longitude. He didn't need the oath so he was elected but the king was refusing to approve him for 4 years in which Cauchy was getting no money and had no academic rights (e.g. submitting papers). After that, Cauchy was eliminated altogether and replaced by Poinsot. Note that the opposite replacement was discussed above.

Throughout the 19th century, France was converging towards the separation of state and church, entities that Cauchy always wanted to unify. He became an enthusiastic Jesuit and officer in various Catholic and Jesus Society institutes. His colleagues would have full mouths of non-discrimination and so on but when this top mathematician of the French history applied for an ordinary chair in mathematics, he got just 3 out of 45 votes. Leftwingers have been a biased scum for at least 150 years.

The pan-European revolution of 1848 was mostly good news for Cauchy. The oath was removed from the law and he could regain the professorship again. He died on this day in 1857, sort of respected again. His name is one of the 72 names inscribed into the Eiffel Tower.

Research

In his early career, he made lots of advances about the Appolonius problem of circles touching three other circles; Euler's formulae for polyhedra; he introduced the notion of convergence, and other things. He was quickly becoming a pioneer of mathematical analysis – that's the part of maths dealing with functions, sums, integrals, derivatives, and... (this is why it's more advanced than just calculus – which is otherwise almost the same thing) with all kinds of limits.

He also made contributions to physics – wave mechanics (Fresnel's wave theory) and elasticity (Cauchy stress tensor). Add various things about membranes, vibrations, and so on. I have already mentioned the Fermat polygonal number theorem.

When it comes to mathematical analysis, he really laid the foundations of the holomorphic functions of complex variables, e.g.\[

\oint_C f(z)\dd z = 0

\] if there are no singularities inside the closed contour \(C\). Seeds of this theorem already existed in 1814; the complete form was given in 1825. He figured out how to compute residues either from limits determining the Taylor expansion; or from the contour integrals. Pierre-Alphonse Laurent was the first man after Cauchy who contributed to this essential mathematical knowledge (Laurent series in 1843).

Cauchy tended to praise the mathematical rigor. Already in 1821, he was working with the infinitesimals – formally infinitely small numbers – but he was the first visible guy to have introduced the \(\varepsilon\)-\(\delta\) gymnastics (games with limits) as the rigorous incarnation of the infinitesimal numbers.

It's an excessive task to enumerate everything that Cauchy has done in mathematics. I find it sort of funny to copy-and-paste a list of insights named after Cauchy:

• Binet–Cauchy identity
• Cauchy's argument principle
• Cauchy–Binet formula
• Cauchy boundary condition
• Cauchy condensation test
• Cauchy's convergence test
• Cauchy (crater)
• Cauchy determinant
• Cauchy distribution
• Cauchy's equation
• Cauchy–Euler equation
• Cauchy functional equation
• Cauchy formula for repeated integration
• Cauchy–Frobenius lemma
• Cauchy–Hadamard theorem
• Cauchy horizon
• Cauchy's integral formula
• Cauchy's integral theorem
• Cauchy interlacing theorem
• Cauchy–Kovalevskaya theorem
• Cauchy matrix
• Cauchy momentum equation
• Cauchy–Peano theorem
• Cauchy principal value
• Cauchy problem
• Cauchy product
• Cauchy's radical test
• Cauchy–Riemann equations
• Cauchy–Schwarz inequality
• Cauchy sequence
• Cauchy surface
• Cauchy's mean value theorem
• Cauchy stress tensor
• Cauchy's theorem (geometry)
• Cauchy's theorem (group theory)
• Euler-Cauchy stress principle
• Maclaurin–Cauchy test

Let me remind you: this guy was voted as unworthy the chair of an ordinary scholar in mathematics by 42 out of 45 self-described "pro-Enlightment" researchers in mathematics. Certain left-wing portions of the Academia have been rotten for centuries.

And that's the memo.

Read More

A proof of the Riemann Hypothesis using the convergence of an integral

Thursday morning update: After many hours, I decided that there is a critical error in the otherwise cleverly constructed proof. On page 138 (discussing Lemma 3), second part, he says "whence the function converges absolutely" essentially for any \(z\) with a real positive part. But it seems he hasn't really established that (except for circular reasoning) because if RH is false, and it may be false, the numerator \(|\psi(e^t)-e^t|\) goes like \(e^{at}\) for some positive \(a\) and the region of convergence is shifted by \(a\). So the "absolute" part of the convergence isn't correctly proven, it seems to me. Maybe it's enough to prove the "ordinary" convergence but I suspect that there could be a similar error in the \(g_1\) part of Lemma 3, too. Apologies if I am making a mistake.

Some people talk about the proof of "almost twin" prime integers separated by at most 70 million or something like that. I am not terribly excited by this result even if it is true. It's always more interesting to talk about somewhat promising proofs to the Riemann Hypothesis, not only because of the $1 million that will be given to the first person who solves the old puzzle.

Many people have thought that they had a proof but the candidate proofs have always failed so far. So you must understand it is extremely likely that we have another example of a failure here. But I am going to tell you, anyway. It would be great if some readers spend a sufficient time and energy by reading the paper. Please don't be repelled by the idiosyncratic Chinese English. Even I can recognize that it's not how a native speaker would formulate the ideas. ;-)

吴豪聪

That's his real name. Today, Hao-cong [first name] Wu [surname] of China sent me his new paper with a somewhat strange title (linguistically)

Showing How to Imply Proving The Riemann Hypothesis (PDF full)

published in the European Journal of Mathematical Sciences. How does the proof work?




It's likely that I won't quite reproduce everything that is needed for the proof in this blog entry even though I may try. Teaching things is the best way to learn them. ;-)

Wu elaborates upon some ideas initiated by Serge Lang, a famous mathematician. But that's the last comment about the sociological context. Now, let us look at the ideas which don't seem to require any esoteric new branches of mathematics.

The proof reduces the Riemann Hypothesis to a claim about the absolute convergence of an integral that is related to the Riemann \(\zeta\)-function in a simple way. Let's roll.




The function that Wu finds more convenient is called \(\psi(x)\), pronounce "psi of ex". It is related to the Riemann \(\zeta\)-function by the following identities\[

\eq{
\phi(s) &= -\frac{\zeta'(s)}{\zeta(s)} = \sum_{n=1}^\infty \frac{\Lambda(n)}{n^s} =\sum_p \frac{\log p}{p^s-1}=\\
&= s \int_1^\infty \frac{\psi(x)}{x^{s+1}}\dd x = \frac{s}{s-1}+s\int_1^\infty \frac{\psi(x)-x}{x^{s+1}}\dd x
}

\] where the sum over \(p\) goes over the primes \(2,3,5,\dots\). The first step you should be able to verify if you want to validate Wu's proof is that the identities above are satisfied if \(\psi(x)\) is defined as the manifestly convergent sum\[

\psi(x) = \sum_{p^m\leq x} \log p = \sum_{n\leq x} \Lambda(n)

\] where \(\Lambda(n)=\log p\) if \(\exists m\geq 1: \,n=p^m\) for a prime \(p\) and otherwise it is set to zero. Note that this \(\psi(x)\) is defined in such a way that for a large \(x\), it's expected to be very close to \(x\) because the "probability to be prime" \(1/\log x\) is cancelled by the factor \(\log p\) from the definition of \(\psi(x)\) – it's close enough already when we allow \(m=1\) only.

The second step is to realize that the presence of a zero or zeroes of \(\zeta(s)\) also implies (or would imply) a pole of \(\phi(s)\), the [minus] "logarithmic derivative of the \(\zeta\)-function", at the same location of the complex plane. To prove the Riemann hypothesis, it is sufficient to prove that \(\phi(s)\) has no poles for \[

\frac 12 \lt {\rm Re}(s) \lt 1

\] (in the "right half-strip", as I will call it) because the hypothetical "RH-violating" zeroes (and singularities) come in pairs symmetrically distributed relatively to the critical axis \(s=1/2+it\) for \(t\in\RR\). Note that \(\phi(s)\) has a pole (or would have a pole) even for a higher-order zero of \(\zeta(s)\).

The third step, and it's the only hard one, is to actually prove that one of the integrals involving \(\psi(x)\) used to calculate \(\psi(s)\) above\[

\int_1^\infty \frac{\psi(x)-x}{x^{s+1}}\dd x

\] is analytic in the right half-strip so it has no poles over there. Consequently, the \(\zeta\)-function has no zeroes in the right half-strip and, by the left-right symmetry, no zeroes in the left half-strip, either.

Wu reduces the claimed analyticity of the integral above to the absolute convergence (convergence even if the integrand is replaced by its absolute value) and uniform convergence (the speed of convergence may be taken to be \(\varepsilon\)-independent), \(\forall\varepsilon\gt 0\), of the integral\[

\int_1^\infty \frac{\psi(x)-x}{x^{3/2+\varepsilon}}\dd x.

\] It shouldn't be hard to see that the absolute and uniform convergence of the integral above (here) is enough for the analyticity of the previous integral, and therefore for the absence of the non-trivial zeroes. Note that the exponents \(s+1\) for \(s\) in the right half-strip and \(3/2+\varepsilon\) for a positive \(\varepsilon\) are the same objects.

So aside from the claims that should be straightforward, the beef of the proof should be the demonstration of the absolute and uniform convergence of the integral in the last displayed equation.

Note that Wu's approach is linked both to the "complex analytic" interpretation of the Riemann Hypothesis as well as the prime-integer-counting, "number-theoretical" interpretation. It's because sufficient experts know that the Riemann Hypothesis is equivalent to the statement\[

\forall \varepsilon\gt 0: \, \psi(x) = x+ O(x^{1/2+\varepsilon})

\] which says that if we accept that the probability for a "rough number \(x\)" to be a prime is \(1/\log(x)\), then the estimated number of primes up to \(n\) deviates from the actual one at most by a power law (that is producing the \(O(\dots)\) term above.

Proving the convergence

OK, so how does Wu want to prove the uniform and absolute convergence? He offers some introduction to the theory of functions of real and complex variables together with some lemmas that are not quite well-known and that may even be new. Finally, the proof boils down to the existence (for any \(s\) with a real positive part) of the Laplace transforms \(g_{1,2}(s)\) of a function called \(f_{1,2}(t)\) related to \(\psi(e^t)-e^t\) for the subscript \(1\) or its absolute value for the subscript \(2\).

If you quickly want to focus on claims related to the \(\zeta\)-function and ignore various theorems and lemmas about completely general functions and their convergence etc. (assuming that these things are harmless and perhaps known to you, explicitly or intuitively), you may find it helpful for me to say that only Theorem 5 (among 7 theorems) and Lemma 3 (among 3 lemmas) is what you want to read. If there is some circularity in Wu's argument (secretly assuming RH), it's probably somewhere in Theorem 5 or Lemma 3.

In particular, I believe that Theorem 5 contains the main trick that allows us to show the convergence in the right half-strip. This theorem claims the absence of poles (except for the \(s=1\) pole) of the function\[

\eq{
\Phi(s) &= \sum_p \frac{\log p}{p^s} = \phi(s)-\sum_p h_p(s),\\
|h_p(s)|&\leq B\frac{\log p}{|p^{2s}|}
}

\] On one hand, this capital \(\Phi(s)\) is shown to be rather close to the lowercase \(\phi(s)\), using an argument based on geometric series. On the other hand, the \(2s\)-th power of something appears in the difference between \(\Phi\) and \(\phi\) which makes \(\sum\log n/n^{2s}\) converge for \({\rm Re}(s)\geq 1/2+\delta\). So the coefficient \(2\) in \(2s\) here is the ultimate reason why the meromorphic character of \(\Phi(s)\) starts at \({\rm Re}(s)\gt 1/2\), how we get the one-half somewhere, and why the critical axis becomes a decisive boundary for the well-definedness of \(\phi(s)\), too.

I don't see any mistake so far but I haven't really devoured all the beef of the proof yet, either, so no complete confirmation from your humble correspondent yet. But it is apparently making more sense every minute!

See the previous TRF blog entries mentioning the Riemann Hypothesis.

Read More

Short questions often require long answers and proofs

Several debaters as well as complexity theorist Boaz Barak religiously worship their belief that it must be that \(P\neq NP\) and that the question whether the proposition holds is extremely deep because \(P=NP\) would revolutionize the whole world.

Most of their would-be arguments are examples irrational hype, fabricated justifications of the limited progress in a field, and group think. I will primarily focus on a single major wrong thesis they promote, namely the idea that a mechanical or polynomially fast or efficient algorithm to solve a problem specified by a short prescription must be short, too.

So let me begin.

\(P\) and \(NP\)

\(NP\) is the class of problems whose solution, if you're told one, may be verified to be correct by \(O(C\cdot N^\ell)\) operations or fewer (the number of operations is effectively the time!) for some \(C,\ell\) if \(N\), an integer specifying the number of objects in the problem or its size, is asymptotically large.




\(P\) is the class of problems whose solution may be found, and not just verified, after \(O(C\cdot N^\ell)\) operations. Verifying a solution can't ever be harder than finding one so we see that \(P\subseteq NP\) but we don't know whether \(P=NP\) or \(P\) is a proper subset.

There are lots of examples of \(NP\) problems that don't seem to be in \(P\) – but, with some surprise, they could be. The provably "most difficult problems in \(NP\)", the so-called \(NP\)-complete problems, are those whose fast solution could be translated to a fast solution to any \(NP\) problem. So \(NP\)-complete problems are on the opposite (hard) side of the \(NP\) set than the \(P\) problems if this "polarization" can be done at all.

Examples of \(NP\)-complete problems include the the clique problem i.e. the decision whether a combinatorial graph has a complete graph with one-half of the nodes that are completely connected with each other; the travelling salesman problem (find the shortest closed route that visits all nodes/cities in a graph), and so on.




I think that a physicist would find the computation of the permanent (the determinant-like sum of products over permutations in a matrix but without the minus sign) to be a more natural representative of the not-in-\(P\), difficult, class because it's more "explicit" – it's given by a compact formula. However, it's not in \(NP\) – there's no way to quickly verify the resulting value of the permanent, either: an example of the fact that \(NP\) is a constraining, narrow-minded class. On the other hand, it's known how a fast calculation of the permanent may be used to solve \(NP\)-problems; it's known that the permanent is \(NP\)-hard (which is a larger class than \(NP\)).

Computer scientists' most favorite difficult \(NP\)-complete problem is probably 3SAT or SAT – to decide whether a proposition constructed from logical operations AND, OR, and binary variables \(x_i\) (obeying a certain constrained format, if you add the digit "3" or another one at the beginning) is a tautology (a proposition equal to TRUE regardless of the values of variables \(x_i\)) but faster than going through all the \(2^N\) possible choices of the truth values of the variables. This very preference favoring 3SAT already shows some "unnatural bias" – they're focusing on things that are easier to write on the existing computers (including the preference for binary computers instead of e.g. ternary ones that we could be using equally well) which is not really a good, invariant criterion for the mathematical depth.

A reason why all these – effectively equivalent (equally hard, convertible to each other with minimal losses) – problems probably don't have an exponentially fast resolution (why they're not in \(P\)) is that at least for some of them, you would expect that if a solution exists, it would already have been found. So you use the same "mathematical induction" – if New York skyscrapers haven't been demolished by an airplane in 100,000 previous days, chances are that it won't happen tomorrow, either; instead, there may be a law that this will never happen and this conjecture has passed some somewhat nontrivial test. Such an argument is risky but it has at least some logic. Or at least, people would say it had before 9/11.

However, many complexity theorists prefer completely different arguments – or modifications of the valid yet inconclusive argument above – which aren't rational.

The key problem why \(P=NP\) wouldn't be far-reaching even if it were true is that the algorithm to quickly solve 3SAT could be "fast enough" so that it obeys the polynomial criterion but it could still be "slow enough" to make it completely impractical. The number of operations could go like\[

10^{100}\times N\quad {\rm or}\quad N^{100}

\] or some other function. The first Ansatz above is linear – very slowly growing with \(N\) – but it has a large coefficient. The second Ansatz has a modest coefficient, namely one, but the exponent is large. Already for \(N=2\) or \(N=10\), respectively, the two expressions above give you at least a googol and no computer will ever do this many operations.

One could conjecture that mathematics isn't this malicious and both the exponent and the prefactor are likely to be of order one for all problems; a physicist would call this argument "an argument from naturalness". However, the experience with many highly natural problems in mathematics suggests that this application of "naturalness" fails much more often than many people might expect.

Let me emphasize that even if \(P=NP\) and a fast algorithm to solve the 3SAT problem or even to compute the permanent only takes \(N^4\) operations, a natural polynomial scaling, there is no contradiction. The discovery of this fast algorithm would make a significant number of calculations of the "clique" or "traveling salesman" type vastly more efficient but the rest of the world would stay the same. You couldn't automatize the search for proofs or deep discoveries in maths or physics, music, and so on because these activities haven't been reduced to 3SAT and not even to the harder permanent without "big losses".

But in the rest of the text, I want to provide you with some evidence and context showing that \(P=NP\) is still very likely to produce impractically slow algorithms in practice.

Forums: short questions, long answers

If you were ever answering questions on forums such as Physics Stack Exchange, you must know that a very short question often requires an extremely long answer. Well, questions such as "explain string theory to me" may require hundreds or thousands of pages and people usually don't try. But even if the question is realistic, a long answer is simply needed.

But we may talk about a more rigorous incarnation of the same question: the length of proofs needed to prove a theorem. Half a year ago, John Baez wrote about insanely long proofs and about the way how some of them may dramatically shrink if we're allowed to assume the consistency of an axiomatic system etc.

However, I don't want to play these Gödelian games because in most cases, you end up talking about propositions you wouldn't be interested in to start with – propositions that are not always human-readable and that are only interesting because of the length of the required theorems. On the other hand, even if we talk about very practical, important math problems, we often end up with the need to write down very long proofs and very long books on the classification of things.

Before I will mention a few examples, it is important to mention that they're examples of proofs and classifications that we have already found. There may exist many interesting theorems with even longer proofs, perhaps much longer proofs, and we haven't found them yet – partly because it becomes harder and harder to search for longer and longer proofs. So it's totally plausible that extremely long proofs of interesting theorems are almost omnipresent in maths. In fact, it seems sensible to assume that the average length of the proof that the mathematicians and others are finding or mastering is an increasing function of time.

I am talking about proofs but the same comment may apply to speedy algorithms to solve certain problems. These algorithms may still be extremely complicated and the fact that we haven't found them yet doesn't really prove that they don't exist. This caution is promoted in the Wikipedia article on \(P\) vs \(NP\). While it offers us the would-be impressive slogan by Scott Aaronson,

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...

(I've already explained that this fairy-tale suffers from many serious illnesses: one of them is that it completely overlooks the fact that the main ingenious thing about these famous men is that they can find – and not just follow – some de facto step-by-step procedures to achieve something) it also quotes two researchers as examples of those who believe that it's wrong to be biased and the experts in that field should comparably eagerly study the possibility that \(P=NP\) and try to search for proofs of that:

The main argument in favor of \(P \neq NP\) is the total lack of fundamental progress in the area of exhaustive search. This is, in my opinion, a very weak argument. The space of algorithms is very large and we are only at the beginning of its exploration. [...] The resolution of Fermat's Last Theorem also shows that very simple questions may be settled only by very deep theories.

—Moshe Y. Vardi, Rice University

---

Being attached to a speculation is not a good guide to research planning. One should always try both directions of every problem. Prejudice has caused famous mathematicians to fail to solve famous problems whose solution was opposite to their expectations, even though they had developed all the methods required.

—Anil Nerode, Cornell University

Very wise. Aaronson really represents the unlimited prejudices, retroactive rationalization and hyping of these prejudices, and even bullying those who are showing that the opposite possibility is also compatible with everything we know and who are working to add some progress in that direction. Aaronson's approach to \(P=NP\) is a similar skewed approach to science as the climate alarmism or Lysenkoism – after all, Aaronson has openly come out of the closet as a climate alarmist himself, too.

I need to emphasize that in physics, we also claim that various marvelous hypothetical engines – like the perpetual-motion machines – don't exist. But in physics, we actually have a much stronger case for such no-go theorems. We can really prove the energy conservation from the time-translational symmetry of Nature, via Noether's theorem. We may prove the second law of thermodynamics in the form of the H-theorem and its variations. These results only depend on assumptions that have been heavily tested in millions of experiments, assumptions that we really consider the most rock-solid foundations of all the natural science. Aaronson's (and not only his, of course) prejudices are rooted in no comparably solid foundations.

Fine, now the examples of the long proofs.

Fermat's Last Theorem

I have discussed some history of the proof last month. The statement of the theorem is extremely easy to formulate. Almost all the well-known mathematicians of the last centuries spent hundreds of hours per capita in attempts to prove the conjecture. At most, they succeeded for some individual exponents \(n\).

Suddenly, in the 1990s, Andrew Wiles succeeded. Many people had already switched to the lazy philosophy saying that "if it hasn't been found for several centuries, it can't be found". They were proved wrong. Wiles' proof was rather long and, even more importantly, it depended on highly advanced, hierarchically abstract concepts that "seemingly" have nothing to do with a simple statement about integers, their powers, and their sums.



In this random episode, Pat and Mat try to bring a painting through the door and hang it in the living room. They spent quite some time with it – more than 8 minutes on the video – and tried many methods which still doesn't prove that they have proven that no better solution exists.

In some formal language, Wiles' proof would still require at least thousands of characters. A brute force search for proofs would require at least something like \(O(256^{1,000})\) operations, if you understand me, but even if \(P=NP\) were true and allowed us to search for proofs polynomially quickly, the power could still be what it is in \(1,000^8\) which would make it impossible to find the proof in practice. The hypothetical proof of \(P=NP\) would still be very far from providing us with proofs of every theorem or a fast solution to any problem.

And of course, all the comments about Wolfgang Amadeus Mozart, Bobby Fischer, or Carl Gauss are completely silly and unrelated to the technical question above, except by verbal tricks. After all, these and other ingenious men had superior skills due to some kind of a brute force that others didn't receive from God. It may be great to believe that something divine, qualitatively different, intrinsically creative is behind these men's superiority but it ain't so. Almost everyone has gotten some memory, CPU, and creativity when he or she was born but some people just get much more of it and it – along with some training, hard work, and lucky circumstances – allows them to do things that others apparently can't do or at least don't do.

Four Color Theorem

The four-color theorem says a very simple thing: areas on a map may always be painted by four colors so that no two adjacent areas share the same color.



This is how you may paint the U.S. map with four colors.

Sometimes three colors are simply not enough. Divide a disk to three 120° wedges. They need to have 3 distinct colors. An extra area surrounding most of the disk touches all the three wedges so you need a fourth color.

And five colors is safely enough; it was proved in the 19th century and the proof is elementary.

However, four colors are enough, too. But there is almost no "wiggle room" left. Consequently, the existence of a four-colored painting of the map often looks like a good luck. Equivalently, the known proof is very complicated.

The first proof was constructed with the help of computers. They needed to verify thousands of possible "submaps". In 1996, the number of submaps that require a computer-enhanced verification was reduced to 633 but it's still large. It's been argued that no human can really check the proof by himself.

Boaz Barak tries to argue that 633 may perhaps be a bit larger than one but it will decrease to a number of order one. Well, it doesn't have to. It may be that 633 or 450 will be proved to be the minimum number of submaps that need to be verified in a similar proof. It's still an extremely large number.

Moreover, we're talking just about the four-color theorem, a kindergarten kid's playing with pastels. It seems pretty much obvious to me that more structured problems will require a much larger number of individual cases that have to be checked by the brute force. For example, there may exist an algorithm that searches for length-\(N\) proofs of a theorem in a polynomial time, \(C\times N^\ell\). Such an algorithm may still require an astronomical large memory for the algorithm itself and/or an astronomically large (either smaller or larger or the same) memory for the intermediate data. The fact that we don't know of such an algorithm today doesn't mean that it doesn't exist.

On the other hand, it's still plausible that the four-color theorem also has a different, elementary proof. Two years ago, I was sent something that looked rather promising by a chap and spent many days with that. At the end, there was nothing that looked like a proof. Today, I would probably be able to see that "it can't possibly be a seed of the proof" much more quickly – simply by seeing that too elementary a proof can't possibly know about the "wisdom" or "good luck" that are needed to four-color some difficult enough maps.

Classification of finite groups, largest sporadic groups

A group is a set with the associative multiplication\[

(fg)h = f(gh), \quad f,g,h\in G

\] and with a unit element and inverse element for everyone. A group may be a finite set. How many finite groups are there? Of course, infinitely many, e.g. the cyclic groups \(\ZZ_n\) already form an infinite subset. Moreover, you may always construct Cartesian product groups and other constructions. Can you list all the mathematically possible groups in terms of some well-understood building blocks such as \(\ZZ_n\), \(S_n\), \(D_n\), \(A_n\), and their direct or semidirect products and/or a few extra operations?

Just for two decades, we have known the answer to be Yes.

The achievement – the classification – is written as the union of hundreds of mathematical papers by a hundred of authors. Thousands and thousands of pages are needed to solve the simply formulated problem above. Aside from the easy-to-understand groups above – some of which are coming in understandable infinite families – the classification forces you to discover 26 truly unusual examples of groups, the sporadic simple groups. (Sometimes the Tits group, albeit a bit simpler, is counted as the 27th sporadic group.)

The largest sporadic group is the monster group. Its number of elements is about \(8\times 10^{53}\), almost a million trillion trillion trillion trillions. It's a very particular, fundamental, and important integer in maths that arises "out of nothing". The dimension 248 of the largest exceptional Lie group, \(E_8\), is analogous except that the number of elements of the monster group is vastly larger.

The laymen could also intuitively guess that objects described by very large integers such as this one are contrived, unimportant in practice, and so on. But if you read some articles about the monstrous moonshine, you will see that just the opposite is true. The largest sporadic group is, in some sense, the most elementary sporadic group. An algebra of vertex operators that respect this huge finite symmetry carries an explanation for the coefficients in the expansion of the \(j\)-function, a very natural function (basically unique if holomorphic) mapping the fundamental domain to a sphere. The AdS/CFT dual of the conformal field theory with the monster group symmetry is the "simplest" gravitational theory you may think of, the pure gravity in the 3-dimensional AdS space, at least at the minimal curvature radius.

The latter relationship suggests some kind of a duality. If the CFT has some group with many elements, its dual is simple and has a few fields. There is some complementarity between these two things and the product could be something like \(10^{54}\), if I describe the relationship in a "moral" way that isn't quite accurate.

When we approach some really natural structures in maths – especially the deep maths that has links to the foundations of quantum gravity etc. – we easily and naturally get prefactors that may be as large as \(8\times 10^{54}\) or other large numbers. Of course that if an algorithm gets slowed down by this factor, it doesn't matter that it's still "polynomial": it will be impractically slow and useless in practice.

And those things surely do happen in maths often. Even though our current knowledge is almost certainly biased towards knowing the shorter proofs and methods and be ignorant about the longer ones (because the latter are harder to be found), we already know that there are many important proofs and algorithms and classifications that are extremely long and hierarchically complex.

The string-theoretical landscape

String theory is the richest theory that the mankind knows and one may enter the realm through many entrances. The evidence strongly suggests that it's a completely unique structure with no deformations or siblings. However, it may have many solutions.

In the class of semi-realistic stabilized flux vacua, people have tried to estimate the number of solutions to string theory's equations. The "stabilized" adjective implies that there are no moduli left; no continuous parameters can be freely adjusted. With these extra conditions, the number of vacuum-like solutions has to be finite or countable and if one imposes some additional semi-realistic criteria, he ends up with a finite number. But the number is often quoted as \(10^{500}\) although this estimate is far from a rigorous enough calculation.

At any rate, it seems very likely that powers of a googol are a good estimate of the number of string-theoretical vacua obeying certain very natural (and sort of realistic) constraints that make them very promising as descriptions of the real Universe around us. Whether there exists a principle that picks one of them or some of them according to some non-anthropic criteria remains unknown.

But even if we ignore these vacuum-selection and anthropic questions, it seems true that string theory produces a high number of solutions. If you accept that string theory describes the laws of physics in the most general sense, you may ask whether the laws of physics allow some particular phenomena or creatures. Describe the creature in some way. To find out whether they appear anywhere, you may be ultimately forced to search through those \(10^{500}\) different universes.

The \(P\neq NP\) complexity theorists usually talk about a few dozens of their pet \(NP\)-complete algorithms, not about the problems for "mature scientists" such as the searches for some stringy vacua with some properties. So they think that the traveling salesman and equivalent problems are "almost everything" that is worth thinking about. Well, it surely ain't so. But in the "traveling salesman" type of problem, they know what \(N\) is.

What is \(N\) in the case of the problem "Find a stringy vacuum with some properties"? Needless to say, really fundamental physics problems usually don't come with instructions such as "use the label \(N\) for this and that". In some sense, we are dealing with a single string theory and the finite number of solutions is just an order-of-one extra complication. In some counting, we have \(N=1\). Nevertheless, it makes the search \(10^{500}\) or so times more time-consuming, at least if you have to rely on the brute force method (which isn't clear). It's an example of the huge prefactor that Boaz Barak believes not to occur in practice. It surely does occur – it occurs in the case of many fundamental math problems such as those above as well as in the case of the most natural and fundamental problems in physics, those asking about the basic properties of string theory.

More generally, I want to say that there are lots of "subfields in maths" that may be completely mastered – in the sense that you may turn a previously seemingly creative activity to a mechanical process – but the number of concepts and algorithms that you sometimes need to learn to make these things mechanical is often very large. Think about all the tricks and rules you need to know to integrate large classes of functions or anything else. Think about the huge amount of code hiding in Mathematica which allows you to solve so many things. Mathematica and Wolfram Alpha are examples of projects in which people actually made a significant progress in their efforts to "automatize" many things. While I find it unlikely that Wolfram or others will ever find a gadget that "automatizes everything" – e.g. the tasks "find the shortest proof of a valid proposition" or "find the fastest algorithm that solves something" etc., I don't really have a proof (and not even legitimate, strong enough evidence) and it's just wrong to promote big ideologies that try to "frame" everything so that it's compatible with the predetermined conclusions even though the truth may be different and the alternatives might be "framed" as well, if you tried a little bit.

I feel that people such as Boaz Barak are extremely narrow-minded in their focus on 3SAT and several other, comparably down-to-Earth, problems; extremely biased against the existence of more sophisticated algorithms and proofs than they know now (partly because they don't really want to learn something difficult and new and they don't want to be shown to have been unable to find out something remarkable that they should have found if they were ingenious enough); and they spend way too much time by rationalizations of the limited progress in the search for much better algorithms to solve various things.

Moreover, their experience with the really nice and important problems that have some "beef" is limited, otherwise they couldn't possibly claim that large prefactors and very long minimal proofs or algorithms can't appear in maths. They surely can and they often do. At least in this sense, "naturalness" (in the sense of the preference for order-of-one coefficients in answers to questions) fails in maths: the number of concepts and the amount of time you need to solve a short problem formulated as a length-\(N\) string is often much larger than \(N\) or a small multiple of its modest power. As Barbie correctly said, math class is tough. But it should still be taught at schools.

Mathematics is a complicated network of things that are easy, things that are hard, things that look hard but they're easy, things that look easy but they are hard, and the hardness has very many aspects. The idea that all problems deserving to be a part of maths may be divided to easy and hard ones in a binary way is a childishly naive concept. Very simple questions often require one to discover and (in the case of others) master very complicated bodies of knowledge to understand the answers. And very rigid and in this sense simple laws – like, in the most extreme case, the laws of string theory – are often able to produce an amazingly rich set of phenomena, implications, and relationships, i.e. pulsating and intelligent worlds with lots of fun. Complexity theorists who effectively assume that solutions and straightforward algorithms have to be as short and easy-to-learn as the questions themselves are effectively assuming that "what comes out had to come in". But this just isn't true in maths and science. It's the whole point of physics, for example, that we can explain diverse things with a limited canon of laws – but these in principle simple laws have many consequences and create many patterns that have to be understood if you want to master the implications of the laws.

The idea that "proofs and solving algorithms are about as short and as deep as the formulation of the problem" may be described as the "garbage in, garbage out (GIGO)" paradigm and this is what the research may easily look like if you insist on similar prejudices.

Read More