A fountainhead of intrigue

Recently, a Chinese-American mathematician named Yitang Zhang claimed to have resolved the Landau-Siegel zeroes conjecture, which is related to the Riemann hypothesis. (Specifically, disproving the conjecture brings us a small stop closer to proving the Riemann hypothesis.) His paper hasn’t been validated verified by independent mathematicians yet, but it was newsworthy nonetheless because Zhang has previously claimed to have cracked the problem only to retract it after others found some mistakes in his proof.

It also matters because any step, big or small, towards the Riemann hypothesis is important progress. Georg Bernhard Riemann formulated the hypothesis in 1859, and it is yet to be proved. In 2000, the Clay Mathematics Institute included it in its list of Millennium Problems: solving one will fetch the solver a prize of $1 million. Yet as important as the work of number theorists has been, to inch closer to a solution, the hypothesis itself is a thing of infinite beauty with intriguing parallels to ideas in far-flung fields of study.


Please jump over the next two paragraphs if you’re familiar with the Riemann zeta function and its nontrivial zeroes.

The hypothesis is a statement about the set of possible solutions to the Riemann zeta function. This function, Riemann found, could estimate the number of prime numbers between two points on the real number line. Its zeroes – the inputs for which the function has a value of zero – lie on the complex plane, i.e. they are complex numbers of the form a + bi, where a and b are real numbers. ‘a’ is called the real part and ‘b’ is called the imaginary part. i is of course the imaginary number: i = (-1)1/2 There are two kinds of zeroes, trivial and nontrivial. In trivial zeroes, the value of a is a negative integer (-2, -4, -6, -8, …). The Riemann hypothesis states that the value of a for which ‘a + bi’ is a nontrivial zero of the function is always 1/2.

This is a powerful statement if you think about it. Mathematicians (and for that matter everyone curious) have been keen to understand the pattern in which prime numbers are distributed on the number line. Finding a function that defines this pattern would unlock several mysteries in the annals of number theory, as well as in quantum physics and anywhere else where prime numbers make an appearance. If the Riemann hypothesis is proved, it will mean that a function that can specify the number of prime numbers between any two numbers has a real part that is either 1/2 or a negative integer. This will be predictability where there once was only chaos. More specifically, when the values of the trivial and nontrivial zeroes of the zeta function are plotted on a graph, the values of the real part will prevent the dots from fluctuating all over the place and constrain them within a particular range. And something about the picture that emerges could speak to mathematicians about where the secret pattern to prime-number distribution could be hiding.


Scientists have already found mysterious similarities between the distribution of nontrivial zeroes of the zeta function and quantum physics. I found a particularly evocative example in an article from 2003, entitled The Spectrum of Riemannium, written by Brian Hayes. He compared several one-dimensional distributions collected from mathematics as well as reality. Each distribution was distinguished by the distance between two datapoints. The most straightforward was the periodic distribution: a line drawn every 2 units, say (see image below). For the random distribution, a randomiser would spit out a number and a line would be drawn after those many units. For a jiggled distribution, lines are placed in a periodic pattern and each line is then moved (or “jiggled”) by a small, random amount. The distribution of zeroes of the zeta function arises when a line is drawn at every point on the number line where there is a zero.

Then there are “erbium” and “eigenvalues”. The former distribution shows the possible energy levels of the nucleus of the erbium-166 atom. This is determined by the energies and the electromagnetic properties of the nucleus’s constituent particles (68 protons and 98 neutrons). In the latter half of the 20th century, physicists found that the energy levels of a heavy nucleus were statistically similar to the eigenvalues of a type of matrix called a random Hermitian matrix. Every matrix is associated with a polynomial function. The exact solutions to the polynomial are called the matrix’s eigenvalues. If the matrix has P2 elements, it will have P eigenvalues. In a Hermitian matrix, the values of the elements are mirrored across a diagonal running from the top left to the bottom right. In a random Hermitian matrix, the value of each element is chosen at random. In Hayes’s image, the distribution shows 100 eigenvalues of a random Hermitian matrix with 3002 elements.

With these distributions in front of him, Hayes writes: “In analyzing patterns of this kind, there is seldom much hope of predicting the positions of individual elements in a series. The aim is statistical understanding – a description of a typical pattern rather than a specific one.” One of his measures of choice of statistical similarity is the pair-correlation function. If you specify a distance d, the pair-correlation function will tell you how many pairs of lines in the distribution are separated by d. Not every distribution will have the same function, of course: its form differs varies according to the properties of the distribution it is working on.

As Hayes narrates, in 1972, Hugh Montgomery and Freeman Dyson found that the pair-correlation functions of the zeroes of the Riemann zeta function and the eigenvalues of random Hermitian matrices were an exact match. Given that the distribution of the eigenvalues of the same matrices are statistically similar to the energy levels of heavy nuclei, like that of erbium-166, Hayes writes: “Is it all just a fluke, this apparent link between matrix eigenvalues, nuclear physics and zeta zeros? It could be, although a universe with such chance coincidences in its fabric might be considered even stranger than one with mysterious causal connections.” There are other connections between the Riemann zeta function and quantum physics (such as the representation of the function as a trace equation with applications in the study of quantum chaos) – but just this should suffice, I think, to illustrate how captivating the Riemann hypothesis is.

It is also tempting to imagine that in this day and age of superspecialised mathematics and advanced computing techniques and hardware, any problem that remains unsolved for long enough obviously accrues a kind of legendary status but also implies the existence of roots that run deep into disparate fields of scientific and mathematical inquiry – or its ‘unsolved’ status wouldn’t survive attacks from so many possible angles nor from the wisdom founded on the knowledge of so many concepts and meta-concepts.

I found Hayes’s 2003 article when I was rereading the work of physicist S. Pancharatnam (1934-1969) and wanted to learn more about Michael Berry, who is well-known for his description of the Berry phase. Pancharatnam had originally derived a parameter of polarised light called the geometric phase. To quote from a post I wrote in 2018 about Pancharatnam’s work: “All waves can be described by their phase and amplitude. When the values of both parameters are changed at the same time and in slow-motion, one can observe the wave evolving through different states. In some cases, when the phase and amplitude are cycled through a series of values and brought back to their original, the wave looks different from what it did at the start. The effective shift in phase is called the geometric phase.” In 1986, Berry – who was then unaware of Pancharatnam’s work – provided a generalised description of geometric phases, today called the Berry phase.

The first citation in Hayes’s article is to a 1999 article coauthored by Berry and Jonathan Keating, entitled The Riemann Zeros and Eigenvalue Asymptotics. This was a technical article and beyond my ability to parse, but knowing that Berry had studied the Riemann zeta function, I searched the web for other, more accessible descriptions of his insights – and an equally fascinating article published in 1998. It was entitled A Prime Case of Chaos, written by Barry Cipra as part of his acclaimed ‘What’s Happening in the Mathematical Sciences?’ series. Cipra’s article begins with an image resembling the one above from Hayes’s article. (If you’re interested in its origins, this is the attribution: “‘Chaotic motion and random matrix theories’ by O. Bohigas and M. J. Giannoni in Mathematical and Computational Methods in Nuclear Physics, J. M. Gomez et al., eds., Lecture Notes in Physics, volume 209 (1984), pp. 1–99.”.) In this article, Berry is quoted more extensively – as a “quantum chaologist”.

I hope Cipra won’t mind my reproducing the contents of one particular ‘box’ in full below:

Prime numbers are music to Michael Berry’s ears.

Berry, a theoretical physicist at the University of Bristol, is one of the leading theorists in the study of quantum chaos. And that’s brought him to a keen appreciation of the Riemann zeta function.

Prime numbers are a lot like musical chords, Berry explains. A chord is a combination of notes played simultaneously. Each note is a particular frequency of sound created by a process of resonance in a physical system, say a saxophone. Put together, notes can make a wide variety of music – everything from Chopin to Spice Girls. In number theory, zeroes of the zeta function are the notes, prime numbers are the chords, and theo- rems are the symphonies.

Of course chords need not be concordant; a lot of vibrations are nothing more than noise. The Riemann Hypothesis, however, imposes a pleasing harmony on the number-theoretic, zeta-zero notes. “Loosely speaking, the Riemann Hypothesis states that the primes have music in them,” Berry says.

But Berry is looking for more than a musical analogy; he hopes to find the actual instrument behind the zeta function – a mathematical drum whose natural frequencies line up with the zeroes of the zeta function. The answer, he thinks, lies in quantum mechanics. “There are vibrations in classical physics, too,” he notes, “but quantum mechanics is a richer, more varied source of vibrating systems than any classical oscillators that we know of.”

What if someone finds a counterexample to the Riemann Hypothesis? “It would destroy this idea of mine,” Berry readily admits – one reason he’s a firm believer in Riemann’s remark. A counterexample would effectively end physicists’ interest in the zeta function. But one question would linger, he says: “How could it be that the Riemann zeta function so convincingly mimics a quantum system without being one?”

One of these counterexamples is the Landau-Siegel zeroes conjecture. It states that there could be nontrivial zeroes of the zeta function whose real part is not 1/2. In his new paper, Yitang Zhang has claimed that he has constrained the possibility of this conjecture being true by a significant amount. Even if he hasn’t altogether eliminated the possibility, and if his proof is verified to be valid, Berry can rest easy – or at least as easy as his tantalising question will allow.

(Addendum: Riemann is one of my favourite mathematicians. I wrote a tribute of sorts to his work in 2015.)

Featured image: Georg Bernhard Riemann in 1863. Image: Public domain (edited with Photomosh).

Elementary P v. NP

“What’re you currently binge-watching?” is a great conversation-starter, I think. One well-suited for this age and carrying enough insights into the person you’re trying to strike up a conversation with.

I’m currently binge-watching Elementary, an adaptation of Sherlock Holmes whose mysteries may not be as well-roundedly gripping as they are in Sherlock but whose narrative spares me the melodrama of Benedict Cumberbatch and whose reality is neither as ambitious nor paranoid. I also like the idea of a male-female pair in the lead that doesn’t have sex from the get-go.

But in its simplicity, Elementary sometimes get ahead of itself. The most common symptom of this is that, in a few episodes, there is some information that is revealed in the second-half, to which the viewer has had no previous access and so to whom the resolution veritably arises from the blue. As a once-avid quizzer, this is a buzzkill because it offers no opportunity for the viewer to attempt to solve the puzzle before Holmes does (which isn’t impossible). It also makes a lesser ‘deductionist’ of Holmes because, in the viewer’s eyes, it robs him of the ability to piece together a solution to a puzzle using pieces the viewer knows exist.

But in some other episodes, another kind of problem arises. In them, Elementary ventures into fantasy. Often it has the good sense to explain some conundrums away with the suffix “… if we had a really well-equipped lab and billions of dollars”. At other times, it assumes the viewers ignorant. And at even other times, it clubs the two.

An example of the last variety is season 2, episode 2: ‘Solve for X’. In this episode, two mathematicians are killed while they’re both working on a solution to the P versus NP problem. The problem, first formally presented by a computer scientist named Stephen Cook in 1971, asks whether P equals NP. P stands for the set of all problems that can be solved in a reasonable amount of time (relative to their complexity). NP stands for the set of all problems that cannot be solved in a reasonable amount of time but that can be verified in a reasonable amount of time.

(John Pavlus had the perfect metaphor for NP back in 2010: “Imagine a jigsaw puzzle: finding the right arrangement of pieces is difficult, but you can tell when the puzzle is finished correctly just by looking at it”.)

Though a solution to the problem has evaded the most skilled mathematicians for many decades, most of them intuitively believe that P ≠ NP. Solving the problem fetches a $1 million cash prize from the Clay Mathematics Institute (CMI), New York – setting up the motive in ‘Solve for X’. However, the episode is also careful to note the fact that most of modern cryptography is problem-solving and that a solution to the P v. NP problem would be worth hundreds of millions to digital security companies.

This is a line that was bandied about just last month when a group of physicists announced that they were a step closer to resolving the Riemann hypothesis, another mathematical problem that carries a $1 million reward from the CMI. Resolving the hypothesis has some beautiful implications for the incidence of prime numbers on the number line and for prime factorisation, both integral components of the RSA encryption algorithm. However, it says little about how a problem itself could be solved – a notion that is also applicable to the pop culture surrounding the P v. NP problem.

In ‘Solve for X’, a third mathematician solves the problem and then uses it to hack emails and into CCTV footage.

Proving that P equals NP does not mean programmers immediately have insights into where the solutions for a given problem may lay. They only know that, technically, the problem has a solution in polynomial time. For example, consider the RSA algorithm itself. It is effective because it relies on prime factorisation, the process of finding two large prime numbers whose product is being used as a key to cracking the security the algorithm affords. A single-core 2.2-GHz CPU is supposed to take “almost 2,000 years” to factorise a number with 768 bits. Numbers with 2,048 bits or higher are thought to be unfactorisable in a single human lifetime. At the same time, given two prime numbers, their product can be quickly computed and a proposed solution rapidly verified.

But proving P equals NP doesn’t make any of this easier. Knowing that there is a solution out there is not the same as knowing what it could be, particularly in situations where scientists are concerned with practical applications.

R.J. Lipton, an expert on the problem, probably has the most meaningful take on this: that succeeding in solving the problem is about making a psychological impact. If P ≠ NP, then your conception of the world isn’t shaken much: some problems that you thought were hard are going to remain hard. But if P = NP, then it means there are a whole bunch of problems that you thought were hard but are actually easy, and that you – and thousands of mathematicians over the years – have missed out on simpler answers. However, it wouldn’t have anything to say about where this ease arises from.

… unless there is either something encoded in the solution of the P v. NP problem itself or it’s the case that a unified solution emerges to crack all NP problems. I felt that ‘Solve for X’ takes such encoding for granted, that it significantly overestimates the confidence boost accorded by knowing that a problem is solvable or that it significantly underestimates the gap between P = NP and being able to hack into everything. In other words, if P equalled NP, I would still be aghast if someone hacked into Google’s servers.

Any which way, it goes a step too far, evident when you see Tanya Barrett and her programmer friend go from solving the problem to hacking into CCTV footage within a day. It makes a fool of a viewer by saying that this is what the P v. NP problem immediately helps accomplish – and it also makes savants of Barrett and the programmer in order to be able to make such rapid progress but whose savantism doesn’t manifest in any other way.

SPOILERS END

I also think Elementary may have missed a great opportunity to explore a wider, wilder world in which P = NP.

As with my criticism of Spectral, my taking on of Elementary happened because it was an interesting intersection of science and popular culture and that doesn’t happen often. And while Elementary may not have perfectly depicted the consequences of solving a famous mathematical problem – just the way Spectral took some liberties with depicting an esoteric physical phenomenon – I’m glad that it ventured in that direction at all.

Finally, if you’re interested in reading more about the P v. NP problem, I highly recommend Scott Aaronson’s and Lipton’s blogs. Both can get quite technical but they also have some posts that discuss the problem very well, by which I mean not just simple language but also with insights that might allow you to glimpse the underlying principles. Here are two posts – here and here – to get started with.

Featured image credit: Pexels/pixabay.