Raising A Mathematician

A training program to induce research-mentality in mathematics high school students

Category: Articles

Patterns in Primes found

hqdefaultMathematicians are stunned by the discovery that prime numbers are pickier than previously thought. The find suggests number theorists need to be a little more careful when exploring the vast infinity of primes.

Primes, the numbers divisible only by themselves and 1, are the building blocks from which the rest of the number line is constructed, as all other numbers are created by multiplying primes together. That makes deciphering their mysteries key to understanding the fundamentals of arithmetic.

Although whether a number is prime or not is pre-determined, mathematicians don’t have a way to predict which numbers are prime, and so tend to treat them as if they occur randomly. Now Kannan Soundararajan and Robert Lemke Oliver of Stanford University in California have discovered that isn’t quite right.

“It was very weird,” says Soundararajan. “It’s like some painting you are very familiar with, and then suddenly you realise there is a figure in the painting you’ve never seen before.”

Surprising order

So just what has got mathematicians spooked? Apart from 2 and 5, all prime numbers end in 1, 3, 7 or 9 – they have to, else they would be divisible by 2 or 5 – and each of the four endings is equally likely. But while searching through the primes, the pair noticed that primes ending in 1 were less likely to be followed by another prime ending in 1. That shouldn’t happen if the primes were truly random –  consecutive primes shouldn’t care about their neighbour’s digits.

“In ignorance, we thought things would be roughly equal,” says Andrew Granville of the University of Montreal, Canada. “One certainly believed that in a question like this we had a very strong understanding of what was going on.”

The pair found that in the first hundred million primes, a prime ending in 1 is followed by another ending in 1 just 18.5 per cent of the time. If the primes were distributed randomly, you’d expect to see two 1s next to each other 25 per cent of the time. Primes ending in 3 and 7 take up the slack, each following a 1 in 30 per cent of primes, while a 9 follows a 1 in around 22 per cent of occurrences.

Similar patterns showed up for the other combinations of endings, all deviating from the expected random values. The pair also found them in other bases, where numbers are counted in units other than 10s. That means the patterns aren’t a result of our base-10 numbering system, but something inherent to the primes themselves. The patterns become more in line with randomness as you count higher – the pair have checked up to a few trillion – but still persists.

“I was very surprised,” says James Maynard of the University of Oxford, UK, who on hearing of the work immediately performed his own calculations to check the pattern was there. “I somehow needed to see it for myself to really believe it.”

Stretching to infinity

Thankfully, Soundararajan and Lemke Oliver think they have an explanation. Much of the modern research into primes is underpinned G H Hardy and John Littlewood, two mathematicians who worked together at the University of Cambridge in the early 20th century. They came up with a way to estimate how often pairs, triples and larger grouping of primes will appear, known as the k-tuple conjecture.

Just as Einstein’s theory of relativity is an advance on Newton’s theory of gravity, the Hardy-Littlewood conjecture is essentially a more complicated version of the assumption that primes are random – and this latest find demonstrates how the two assumptions differ. “Mathematicians go around assuming primes are random, and 99 per cent of the time this is correct, but you need to remember the 1 per cent of the time it isn’t,” says Maynard.

The pair used Hardy and Littlewood’s work to show that the groupings given by the conjecture are responsible for introducing this last-digit pattern, as they place restrictions on where the last digit of each prime can fall. What’s more, as the primes stretch to infinity, they do eventually shake off the pattern and give the random distribution mathematicians are used to expecting.

“Our initial thought was if there was an explanation to be found, we have to find it using the k-tuple conjecture,” says Soundararajan. “We felt that we would be able to understand it, but it was a real puzzle to figure out.”

The k-tuple conjecture is yet to be proven, but mathematicians strongly suspect it is correct because it is so useful in predicting the behaviour of the primes. “It is the most accurate conjecture we have, it passes every single test with flying colours,” says Maynard. “If anything I view this result as even more confirmation of the k-tuple conjecture.”

Although the new result won’t have any immediate applications to long-standing problems about primes like thetwin-prime conjecture or the Riemann hypothesis, it has given the field a bit of a shake-up. “It gives us more of an understanding, every little bit helps,” says Granville. “If what you take for granted is wrong, that makes you rethink some other things you know.”

Journal reference: arxiv.org/abs/1603.03720

Source: https://www.newscientist.com/article/2080613-mathematicians-shocked-to-find-pattern-in-random-prime-numbers/


The Musical, Magical Number Theorist

The Musical, Magical Number Theorist.


The Musical, Magical Number Theorist

The search for artistic truth and beauty has led Manjul Bhargava to some of the most profound recent discoveries in number theory.

Comments (16)


For Manjul Bhargava, the counting numbers don’t simply line themselves up in a demure row. Instead, they take up positions in space — on the corners of a Rubik’s Cube, or the two-dimensional layout of the Sanskrit alphabet, or a pile of oranges brought home from the supermarket. And they move through time, in the rhythms of a Sanskrit poem or a tabla drumming sequence.

Bhargava’s mathematical tastes, formed in his earliest days, are infused with music and poetry. He approaches all three realms with the same goal, he says: “to express truths about ourselves and the world around us.”

The soft-spoken, boyish mathematician could easily be mistaken for an undergraduate student. He projects a quiet friendliness that makes it easy to forget that the 40-year-old is widely considered one of the towering mathematical figures of his age. “He’s very unpretentious,” said Benedict Gross, a mathematician at Harvard University who has known Bhargava since the latter’s undergraduate days. “He doesn’t make a big deal of himself.”

Yet the search for artistic truth and beauty has led Bhargava, a mathematics professor at Princeton University, to some of the most profound recent discoveries in number theory, the branch of mathematics that studies the relationships between whole numbers. In the past few years, he has made great strides toward understanding the range of possible solutions to equations known as elliptic curves, which have bedeviled number theorists for more than a century.

“His work is better than world-class,” said Ken Ono, a number theorist at Emory University in Atlanta. “It’s epoch-making.”

Today, Bhargava was named one of this year’s four recipients of the Fields Medal, widely viewed as the highest honor in mathematics.

Bhargava “lives in a wonderful, ethereal world of music and art,” Gross said. “He floats above the normal concerns of daily life. All of us are in awe of the beauty of his work.”

Bhargava “has his own perspective that is remarkably simple compared to others,” saidAndrew Granville, a number theorist at the University of Montreal. “Somehow, he extracts ideas that are completely new or are retwisted in a way that changes everything. But it all feels very natural and unforced — it’s as if he found the right way to think.”


Playing the tabla.

From early childhood, Bhargava displayed a remarkable mathematical intuition. “Teach me more math!” he would badger his mother, Mira Bhargava, a mathematics professor at Hofstra University in Hempstead, N.Y. When he was 3 years old and a typical, rambunctious toddler, his mother found that the best way to keep him from bouncing off the walls was to ask him to add or multiply large numbers.

“It was the only way I could make him stay still,” she recalled. “Instead of using paper and pencil, he would kind of flip his fingers back and forth and then give me the right answer. I always wondered how he did it, but he wouldn’t tell me. Perhaps it was too intuitive to explain.”

Bhargava saw mathematics everywhere he looked. At age 8, he became curious about the oranges he would stack into pyramids before they went into the family juicer. Could there be a general formula for the number of oranges in such a pyramid? After wrestling with this question for several months, he figured it out: If a side of a triangular pyramid has length n, the number of oranges in the pyramid isn(n+1)(n+2)/6. “That was an exciting moment for me,” he said. “I loved the predictive power of mathematics.”

Bhargava quickly became bored with school and started asking his mother if he could go to work with her instead. “She was always very cool about it,” he recalled. Bhargava explored the university library and went for walks in the arboretum. And, of course, he attended his mother’s college-level math classes. In her probability class, the 8-year-old would correct his mother if she made a mistake. “The students really enjoyed that,” Mira Bhargava said.

Every few years, Bhargava’s mother took him to visit his grandparents in Jaipur, India. His grandfather, Purushottam Lal Bhargava, was the head of the Sanskrit department of the University of Rajasthan, and Manjul Bhargava grew up reading ancient mathematics and Sanskrit poetry texts.

To his delight, he discovered that the rhythms of Sanskrit poetry are highly mathematical. Bhargava is fond of explaining to his students that the ancient Sanskrit poets figured out the number of different rhythms with a given number of beats that can be constructed using combinations of long and short syllables: It’s the corresponding number in what Western mathematicians call the Fibonacci sequence. Even the Sanskrit alphabet has an inherent mathematical structure, Bhargava discovered: Its first 25 consonants form a 5 by 5 array in which one dimension specifies the bodily organ where the sound originates and the other dimension specifies a quality of modulation. “The mathematical aspect excited me,” he said.

Fibonacci Rhythms


Sanskrit poems feature a mix of short and long syllables that last for one or two beats, respectively. As a child, Bhargava was fascinated by the question of how many different rhythms it is possible to construct with a given number of beats. A four-beat phrase, for example, could be short-long-short or short-short-short-short (or one of three other possibilities).

The answer, Bhargava discovered, was given in “Chandahsastra,” a treatise on poetic rhythms written by Pingala more than two millennia ago. There’s a simple formula: The number of different rhythms with, say, nine beats is the sum of the number of rhythms with seven beats and the number of rhythms with eight beats. That’s because each nine-beat rhythm can be constructed by adding either a long syllable to a seven-beat rhythm or a short syllable to an eight-beat rhythm.

This rule generates the sequence 1, 2, 3, 5, 8, 13, 21, 34, 55, and so on —in which each number is the sum of the preceding two. These are known as the Hemachandra numbers — after 11th-century scholar Acharya Hemachandra, who wrote about poetic rhythms — or the Fibonacci numbers, to Western mathematicians. Bhargava enjoys showing his students that these numbers arise not only in poetic rhythms but also in natural settings, such as in the number of spirals on a pine cone or petals on a daisy.

At Bhargava’s request, his mother started teaching him to play tabla, a percussion instrument of two hand drums, when he was 3 (he also plays the sitar, guitar and violin). “I liked the intricacy of the rhythms,” he said, which are closely related to the rhythms in Sanskrit poetry. Bhargava eventually became an accomplished player, even studying tabla with the legendary Zakir Hussain in California. He has performed in concert halls around the country and even at Central Park in New York City.

“He’s a terrific musician who has reached a very high technical level,” said Daniel Trueman, a music professor at Princeton who collaborated with Bhargava on a performance over the Internet with musicians in Montreal. Just as important, he said, is Bhargava’s warmth and openness. Even though Trueman’s background is not primarily in Indian music, “I never felt that I was offending his high level of knowledge of North Indian classical music,” Trueman said.

Bhargava often turns to the tabla when he is stuck on a mathematics problem, and vice versa. “When I go back, my mind has cleared,” he said.

He experiences playing the tabla and doing mathematics research similarly, he said. Indian classical music — like number theory research — is largely improvisational. “There’s some problem-solving, but you’re also trying to say something artistic,” he said. “It’s similar to math — you have to put together a sequence of ideas that enlightens you.”

Mathematics, music and poetry together feel like a very complete experience, Bhargava said. “All kinds of creative thoughts come together when I think about all three.”


Between attending his mother’s classes and traveling to India, Bhargava missed a lot of school over the years. But on the days he didn’t go to school, he would often meet his schoolmates in the afternoon to play tennis and basketball. Despite his extraordinary intelligence, “he was just a normal kid, associating with all the kids,” Mira Bhargava recalled. “They were completely at ease with him.”

That’s a refrain repeated by Bhargava’s colleagues, students and fellow musicians, who describe him using words like “sweet,” “charming,” “unassuming,” “humble” and “approachable.” Bhargava wears his mathematical superstardom lightly, said Hidayat Husain Khan, a professional sitarist based in Princeton and India who has performed with him. “He has the ability to connect with a huge spectrum of people, regardless of their background.”

The only time that Bhargava’s extended school absences threatened to harm him was when his high school health teacher tried to block him from graduating — even though he was the valedictorian and had been accepted to Harvard. (He did graduate.)

It was at Harvard that Bhargava decided, once and for all, to pursue a career in mathematics. With such eclectic interests, he had flirted with many possible careers — musician, economist, linguist, even mountain climber. Eventually, however, he realized that it was usually the mathematical aspects of these subjects that got him most excited.

“Somehow, I always came back to math,” he said.

Bhargava felt the strongest tug between mathematics and music but decided in the end that it would be easier to be a mathematician who did music on the side than a musician who did mathematics on the side. “In academia, you can pursue your passions,” he said.


Now, Bhargava has an office on the 12th floor of Princeton’s Fine Hall littered with math toys — Rubik’s Cubes, Zometools, pine cones and puzzles. When he is thinking about mathematics, however, Bhargava prefers to escape his office and wander in the woods. “Most of the time when I’m doing math, it’s going on in my head,” he said. “It’s inspirational being in nature.”

This approach can have its drawbacks: More than once, Bhargava has postponed writing down an idea for years only to forget the specifics. At times, however, delays between thinking and writing are inevitable. “Sometimes, when I have a new idea, there hasn’t been language developed to express it yet,” he said. “Sometimes, it’s just a picture in my mind of how things should flow.”

Although Bhargava uses his office primarily for meetings, the mathematical toys decorating its surfaces are more than just a colorful backdrop. When he was a graduate student at Princeton, they helped him solve a 200-year-old problem in number theory.

If two numbers that are each the sum of two perfect squares are multiplied together, the resulting number will also be the sum of two perfect squares (Try it!). As a child, Bhargava read in one of his grandfather’s Sanskrit manuscripts about a generalization of this fact, developed in the year 628 by the great Indian mathematician Brahmagupta: If two numbers that are each the sum of a perfect square and a given whole number times a perfect square are multiplied together, the product will again be the sum of a perfect square and that whole number times another perfect square. “When I saw this math in my grandfather’s manuscript, I got very excited,” Bhargava said.

There are many other such relationships, in which numbers that can be expressed in a particular form can be multiplied together to produce a number with another particular form (sometimes the same form and sometimes a different one). As a graduate student, Bhargava discovered that in 1801, the German mathematical giant Carl Friedrich Gauss came up with a complete description of these kinds of relationships if the numbers can be expressed in what are known as binary quadratic forms: expressions with two variables and only quadratic terms, such as x2 + y2 (the sum of two squares),x2 + 7y2, or 3x2 + 4xy + 9y2. Multiply two such expressions together, and Gauss’ “composition law” tells you which quadratic form you will end up with. The only trouble is that Gauss’ law is a mathematical behemoth, which took him about 20 pages to describe.

Bhargava wondered whether there was a simple way to describe what was going on and whether there were analogous laws for expressions involving higher exponents. He has always been drawn, he said, to questions like this one — “problems that are easy to state, and when you hear them, you think they’re somehow so fundamental that we have to know the answer.”

The answer came to him late one night as he was pondering the problem in his room, which was strewn with Rubik’s Cubes and related puzzles, including the Rubik’s mini-cube, which has only four squares on each face. Bhargava — who used to be able to solve the Rubik’s Cube in about a minute — realized that if he were to place numbers on each corner of the mini-cube and then cut the cube in half, the eight corner numbers could be combined in a natural way to produce a binary quadratic form.

There are three ways to cut a cube in half — making a front-back, left-right or top-bottom division — so the cube generated three quadratic forms. These three forms, Bhargava discovered, add up to zero — not with respect to normal addition, but with respect to Gauss’ method for composing quadratic forms. Bhargava’s cube-slicing method gave a new and elegant reformulation of Gauss’ 20-page law.

Additionally, Bhargava realized that if he arranged numbers on a Rubik’s Domino — a 2x3x3 puzzle — he could produce a composition law for cubic forms, ones whose exponents are three. Over the next few years, Bhargava discovered 12 morecomposition laws, which formed the core of his Ph.D. thesis. These laws are not just idle curiosities: They connect to a fundamental object in modern number theory called an ideal class group, which measures how many ways a number can be factored into primes in more complicated number systems than the whole numbers.

“His Ph.D. thesis was phenomenal,” Gross said. “It was the first major contribution to Gauss’ theory of composition of binary forms for 200 years.”


Bhargava’s doctoral research earned him a five-year Clay Postdoctoral Fellowship, awarded by the Clay Mathematics Institute in Providence, R.I., to new Ph.D.s who show leadership potential in mathematics research. He used the fellowship to spend one additional year at Princeton and the neighboring Institute for Advanced Study and then moved to Harvard. Only two years into his fellowship, however, job offers started pouring in, and a bidding war soon erupted over the young mathematician. “It was a crazy time,” Bhargava said. At 28, he accepted a position at Princeton, becoming the second-youngest full professor in the university’s history.

Back at Princeton, Bhargava felt like a graduate student again and had to be reminded by his former professors that he should call them by their first names now. “That was a little weird,” he said. Bhargava ordered some frictionless chairs for his office, and he and his graduate student friends would race down the halls of Fine Hall in the evenings. “One time, another professor happened to be there in the evening, and he came out of his office,” Bhargava said. “That was rather embarrassing.”

“He has proven some of the most exciting theorems in the past 20 years of number theory. The questions he attacks sound like things he shouldn’t have the right to answer.”

Bhargava is glad to be at an institution where he has the opportunity to teach. As an undergraduate teaching assistant at Harvard, he won the Derek C. Bok Awardfor excellence in teaching three years running. He especially enjoys reaching out to students in the arts or humanities, some of whom may think of themselves as mathphobic. “Because I came to math through the arts, it has been a passion of mine to bring in people who think of themselves as more on the art side than the science side,” he said. Over the years, Bhargava has taught classes on the mathematics of music, poetry and magic. “I think anyone is reachable if the material is presented in the right way,” he said.

Carolyn Chen, a Princeton undergraduate who took Bhargava’s freshman seminar on mathematics and magic, called the course “super chill.” Bhargava started each class by performing a magic trick — something he loves to do — and then the students dissected its mathematical principles. Bhargava’s colleagues had warned him to steer clear of proofs, he said, “but by the end of the course, everyone was coming up with proofs without realizing that’s what they were doing.”

The course inspired Chen and several classmates to take more proof-based mathematics classes. “I took number theory after that freshman seminar,” she said. “I would never have thought of taking it if I hadn’t taken his class, but I really enjoyed it.”

At Princeton, Bhargava started developing an arsenal of techniques for understanding the “geometry of numbers,” a field somewhat akin to his childhood orange counting that studies how many points on a lattice lie inside a given shape. If the shape is fairly round and compact, like a pyramid of oranges, the number of lattice points inside the shape corresponds approximately to the shape’s volume. But if the shape has long tentacles, it may capture many more — or many fewer — lattice points than a round shape of the same volume. Bhargava developed a way to understand the number of lattice points that appear in such tentacles.

“He has applied this method to one problem after another in number theory and just knocked them off,” Gross said. “It’s a beautiful thing to watch.”

While Bhargava’s early work on composition laws was a solo flight, much of his subsequent research has been in collaboration with others, something he describes as “a joyous experience.” Working with Bhargava can be intense: At times, said Xiaoheng Wang, a postdoctoral researcher at Princeton, he and Bhargava have begun discussing a math problem, and the next thing he knows, seven hours have passed. Characteristically, Bhargava is quick to deflect the honor of winning the Fields Medal onto his collaborators. “It’s as much theirs as mine,” he said.

In recent years, Bhargava has collaborated with several mathematicians to study elliptic curves, a type of equation whose highest exponent is three. Elliptic curves are one of the central objects in number theory: They were crucial to the proof of Fermat’s Last Theorem, for example, and also have applications in cryptography.

A fundamental problem is to understand when such an equation has solutions that are whole numbers or ratios of whole numbers (rational numbers). Mathematicians have long known that most elliptic curves have either one rational solution or infinitely many, but they couldn’t figure out, even after decades of trying, how many elliptic curves fall into each category. Now, Bhargava has started to clear up this mystery. With Arul Shankar, his former doctoral student who is now a postdoc at Harvard, Bhargava has shown that more than 20 percent of elliptic curves have exactly one rational solution. And with Christopher Skinner, a colleague at Princeton, and Wei Zhang of Columbia University, Bhargava has shown that at least 20 percent of elliptic curves have an infinite set of rational solutions with a particular structure called “rank 1.”

Bhargava, Skinner and Zhang have also made progress toward proving the famousBirch and Swinnerton-Dyer conjecture, a related problem about elliptic curves for which the Clay Mathematics Institute has offered a million-dollar prize. Bhargava, Skinner, and Zhang have shown that the conjecture is true for more than 66 percent of elliptic curves.

Bhargava’s work on elliptic curves “has opened a whole world,” Gross said. “Now everybody is excited about it and jumping in to work on it with him.”

“He has proven some of the most exciting theorems in the past 20 years of number theory,” Ono said. “The questions he attacks sound like things he shouldn’t have the right to answer.”

Bhargava has developed a unique mathematical style, Gross said. “You could look at a paper and say, ‘Manjul’s the only one who could have done that.’ It’s the mark of a really great mathematician that he doesn’t have to sign his work.”

Thomas Lin contributed reporting from Princeton, N.J.

August 14, 2014

A Grand Vision for the Impossible | Subhash Khot

A Grand Vision for the Impossible

Subhash Khot’s bold conjecture is helping mathematicians explore the precise limits of computation.

One summer afternoon in 2001, while visiting relatives in India, Subhash Khot drifted into his default mode — quietly contemplating the limits of computation. For hours, no one could tell whether the third-year Princeton University graduate student was working or merely sinking deeper into the living-room couch. That night, he woke up, scribbled something down and returned to bed. Over breakfast the next morning, he told his mother that he had come up with an interesting idea. She didn’t know what it was, but her reserved older son seemed unusually happy.

Khot’s insight — now called the Unique Games Conjecture — helped him make progress on a problem he was working on at the time, but even Khot and his colleagues did not realize its potential. “It just sounded like an idea that would be nice if it was true,” recalled Khot, now a 36-year-old computer science professor at New York University’s Courant Institute of Mathematical Sciences.

When Khot returned to Princeton, he mentioned the idea to Sanjeev Arora, his doctoral adviser, who advised him to hold off on publishing it. “I wasn’t sure it was going to be a good paper,” Arora said. “I thought it was maybe a little premature, that it was just a month since he had the idea.”

Khot wrote the paper anyway. “I was just a graduate student,” Khot said of the decision. “I wasn’t expecting anyone to take me seriously to begin with.”

In a sense, Khot’s insight completed an idea set in motion by another mentor, Johan Håstad of the Royal Institute of Technology in Stockholm. But even Håstad ignored Khot’s conjecture at first. “I thought it might get proven or disproven in a year,” he said. “It took us awhile to realize it had all these consequences.”

“There are many talented people who can solve problems — few people can change the way we look at things.”

Over the next several years, what seemed a modest observation — that a particular assumption could simplify certain approximation algorithm problems — grew into one of the most influential new ideas in theoretical computer science. Today, for his “prescient” assumption and his subsequent leadership in “the effort to understand its complexity and its pivotal role in the study of efficient approximation of optimization problems,” Khot was awarded the 2014 Rolf Nevanlinna Prize, widely considered one of the top honors in his field.

In announcing the prize on its website, the International Mathematical Union also credited Khot’s work for generating “new exciting interactions between computational complexity, analysis and geometry.”

Khot, who tends to keep his thoughts close and acknowledgment of his achievements even closer, was as surprised as his colleagues by the success of the Unique Games Conjecture. “I definitely didn’t expect that this small proposal would go so far,” he said.

Although Arora, like others studying the limits of approximation algorithms, was initially unconvinced by Khot’s “pie in the sky” idea, he now credits his former graduate student for sensing that his proposal could clear “a fundamental stumbling block.”

“His intuition was right,” Arora said. “He’s now probably the number one expert in that field.”

Subhash Khot

Assaf Naor, an Israeli mathematician who has worked closely with Khot for almost a decade, nominated his colleague and friend for a $200,000 Microsoft fellowship in 2005, the National Science Foundation’s prestigious Alan T. Waterman Award in 2010, and this year’s Nevanlinna Prize. “I see in his work more than just a collection of really good papers: I see an agenda, an original point of view,” Naor said. “There are many talented people who can solve problems — few people can change the way we look at things.”

Three Cookies

The way Khot looks at things might strike some as pessimistic. Given his research into the theoretical limitations of computers, perhaps it is natural that he tends to see what cannot be done or what might go wrong. When packing for vacations, for example, Khot tries to anticipate any ailments that could strike his 2-year-old son, Neev, by bringing all the medicine he thinks his family could need.

“He has a good sense of what’s going to go wrong — he’s very analytical,” said his wife, Gayatri Ratnaparkhi, a 32-year-old analyst at the Federal Reserve Bank of New York. “And the end result is that not much goes wrong in our lives.”

But Khot’s analytical approach can also be maddening, Ratnaparkhi said. “He tries to optimize things in every possible way,” she said. When walking from point A to point B, for example, Khot always wants to find the shortest path. Ratnaparkhi has to persuade him to take the scenic route. And shopping becomes “a major enterprise,” as Khot feels “obliged to go to five stores and take a look at prices,” he said. He tries to avoid the outings whenever possible.

Then there were the cookies. One time, inside a local bakery, Khot was surprised to find that three 33-cent cookies were being sold for a dollar. While it didn’t prevent him from buying the cookies, he said, “even if it’s one cent, it seems off.”

Truly, his wife said, “he’s in the perfect job for his skill set.”

Khot acknowledged that his area of research suits his way of thinking. “In many of the problems that the world faces, in some sense there’s an overemphasis on being optimistic,” he said. “It’s good to know one’s own limitations.”

Khot’s views are also informed by his voracious appetite for other subjects, including economics, history and current events. He studies labor statistics, his wife said, and reads seven or eight newspapers a day. “He knows stuff I had no idea he knew,” Ratnaparkhi said. “At the museum, looking at Renaissance art, he can tell me what the context is.”

While few would mistake Khot’s subtle, rimless glasses for the proverbial rose-tinted variety, those who know him best describe him as kind, gentle and giving. “He is a superb adviser and mentor with great graduate students,” said Naor, who suggested to NYU’s provost in 2007 that the university hire Khot. As Courant Institute colleagues and neighbors in the faculty housing complex, the two have grown closer. “He and his family are my family,” Naor said.

Calling Khot a “first-class mathematician,” Naor highlighted the importance of the big, abstract questions he studies: “The boundaries between tractable and intractable are inherently interesting to us as humans.”

In the three decades preceding Khot’s graduate school research, computer scientists had shown that hundreds of important computational challenges belong to a category called “NP-hard” problems, which most computer scientists believe cannot be solved exactly by any algorithm that runs in a reasonable amount of time. One example is the famous “traveling salesman” problem, which asks for the shortest round-trip route that visits each city in a collection of cities once. By the time Khot arrived at Princeton in 1999, many computer scientists had shifted their focus to exploring efficient algorithms that find good approximate solutions to these difficult problems.

And computer scientists were successful at doing so — for many problems. But in 1992, a team of computer scientists — including Khot’s adviser-to-be, Arora — astonished their colleagues by proving a result called the PCP theorem, which enabled researchers to show that for a wide variety of computational problems, even finding good approximate solutions is NP-hard, meaning that it’s a task that, most computer scientists believe, is impossible to carry out efficiently.

This revelation dashed researchers’ hopes of identifying arbitrarily good approximation algorithms for every problem, but it opened up a new line of inquiry: trying to generate “exact hardness” results, statements of the form, “Here’s an approximation algorithm for problem X and a proof that finding any better approximation is NP-hard.” Shortly before Khot started graduate school, Håstad established exact hardness results for a few approximation problems. It was unclear, however, how to extend his results to other computation problems.

Subhash Khot and his wife.

At Princeton, after breezing through the department’s prerequisites in three months — course work that usually takes good students a year and average students two, Arora said — Khot started playing around with Håstad’s techniques, trying to establish exact hardness results for several problems. Then came his epiphany while vacationing in India: One of his problems got much simpler if he made a certain assumption about how difficult a certain approximation problem is. Back at Princeton, Khot realized that several of his other problems also became easier if he made the same assumption. He eventually named this assumption the Unique Games Conjecture.

Proving the Impossible

Khot grew up in Ichalkaranji — considered a small town in India with a population of just under 300,000 — where he was well-known for winning math competitions; his name and picture frequently appeared in the local Marathi-language newspapers Sakal (“Morning”) and Pudhari (“Leader”). At 16, he achieved the highest score countrywide in the Indian Institute of Technology Joint Entrance Exam, a test so notoriously difficult that most eligible students don’t bother to take it. At 17, Khot went off to study computer science at the school in Mumbai without ever having touched a computer.

Khot was an autodidact from an early age. He loved reading Russian science books that had been translated into Marathi. His favorite one included chapters describing rare elements like palladium and gallium. But he seemed destined to follow his parents into the medical profession. His father and mother — an ear, nose and throat specialist and a general practitioner, respectively — ran a clinic on the first two floors of the family’s residence that bustled with patients from the local textile industry, many of whom suffered from respiratory ailments.

Then one day, Khot told his mother that he didn’t want to be a doctor. “I was very interested in chemistry and some physics and eventually mathematics,” he said. “I kind of realized that math was at the base of all these things; so why not study mathematics?”

This change was for the best, Ratnaparkhi joked. “He would have been a terrible doctor,” she said. “He doesn’t like to talk to people.”

During Khot’s high school years, the person who most influenced him was his math teacher and headmaster, V.  G.  Gogate. “He’s like a father or a grandfather,” Khot said. “Whenever I go home, he’s the first person I would call and the first person I would visit.”

After learning in March that he had won the Nevanlinna Prize, Khot said, the most difficult part of keeping it a secret was not being able to tell Gogate. When he finds out about the prize, Khot said, “he will be the happiest person, even more so than me or even my mom.”

Gogate, now 78 and retired, didn’t really teach math to Khot, who for years had been learning on his own by reading advanced texts. “There are no good education facilities in our small town,” said Khot’s mother, Jayashree Khot. “So he had to do it himself.”

Gogate invited Khot and other top students to study at his home and encouraged his charges to be self-sufficient and to help others. Khot not only taught himself everything, Gogate said, but he also assisted all of his friends in science, math, Sanskrit, Marathi and English. “He was finding answers to the questions by thinking himself, and he was guiding all his classmates,” Gogate said.

But it wasn’t easy. Until he began attending IIT, Khot had to figure out the answers to difficult problems by himself. Some problems took him six months to a year to solve. In the end, though, “I think that was very helpful that I learned everything the hard way,” he said. Now, Khot believes that his independence and ability to focus are his greatest strengths as a mathematician. “I’m perfectly happy to spend very long periods on a single problem,” he said.

About a month into his undergraduate program at IIT, tragedy struck: His father died of a heart attack. “After my father’s death, my outlook changed,” he said. Test scores and competition standings no longer seemed all-important. He worked hard but worried less about external outcomes.

In Mumbai, Khot completed the required programming homework but gravitated toward the mathematical aspects of computer science, where, he said, “you don’t really need the computer as a machine.” When he graduated and went to Princeton, he knew he wanted to focus on theoretical computer science.

Khot’s paper describing the Unique Games Conjecture appeared in 2002. The first hint of the conjecture’s power came a year later when Khot and Oded Regev, now of New York University, showed that if the conjecture is true, then it is possible to establish the exact approximation hardness of a problem about networks called Minimum Vertex Cover. Then, in 2004, Khot and three collaborators used the conjecture to produce anunexpected finding. They showed that if the conjecture is true, then the best known approximation algorithm for another network problem called Max Cut — an algorithm that many computer scientists had assumed was just a placeholder until they could find a better one — was truly the best possible.

“We understand immediately an infinite class of problems by relying only on the one problem [that Khot] postulated is hard, which is amazing.”

Suddenly, everyone was studying the implications of the Unique Games Conjecture. “You should see the number of mathematicians working on problems that emanated from this conjecture,” saidAvi Wigderson of the Institute for Advanced Study in Princeton, N.J. The years following the Max Cut result witnessed a flood of approximation hardness results — theorems of the form, “If the Unique Games Conjecture is true, then it’s NP-hard to approximate the solutions of problem X any closer than Y percent.”

“This conjecture suddenly became really interesting and important,” Wigderson said. It even seemed to help prove approximation hardness results about problems that on the surface seemed to have nothing to do with the problem at the heart of the Unique Games Conjecture, which involves assigning colors to the nodes of a network. “What was special about his problem?” Wigderson asked. “It wasn’t clear.”

In 2008, Prasad Raghavendra of the University of California, Berkeley, showed that if the UGC is true, then it’s possible to establish the approximation hardness of an entire category of common computational problems called “constraint satisfaction” problems. These involve trying to find the solution to a problem that satisfies as many of a set of constraints as possible — for example, the wedding seating chart that places feuding family members at different tables as much as possible.

“We understand immediately an infinite class of problems by relying only on the one problem [that Khot] postulated is hard, which is amazing,” Wigderson said. The conjecture “creates an understanding that one rarely expects — that’s why it’s so interesting and beautiful,” he said.

“It has changed the way we think about a lot of problems in computer science,” saidRyan O’Donnell, a theoretical computer scientist at Carnegie Mellon University in Pittsburgh.

For the problem of coloring the nodes of a network that has a collection of constraints about which color combinations are allowed (top left), it is sometimes possible to find a coloring that satisfies all the constraints (top right). But for some networks and constraints (bottom left), it is impossible to satisfy all the constraints simultaneously. The Unique Games Conjecture concerns the problem of finding a coloring that satisfies as many constraints as possible, such as the bottom right coloring, which satisfies all the constraints except the one for the thick edge.

True or False

Khot is most comfortable thinking quietly — whether he’s alone in his office, on a Washington Square Park bench surrounded by strollers, buskers and chess hustlers, in a cafe packed with NYU students or at home in India among family and friends.

“When we go to a movie he doesn’t like, he’s working on his own,” Ratnaparkhi said. “That happens quite a lot.”

If the Unique Games Conjecture is ever disproved, all the approximation hardness results that emanate from it will collapse. But certain other results will hold firm: For some mysterious reason, the proofs of the approximation hardness results and the attempts to prove the conjecture itself have led mathematicians to state — and then prove — an assortment of theorems about seemingly unrelated areas of mathematics, including the geometry of foams, the relationship between different ways of measuring distance, and even the stability of different election systems. “Out popped these very natural questions,” O’Donnell said. These results will hold up regardless of whether the Unique Games Conjecture turns out to be true or false.

It remains to be seen whether computer scientists will be able to prove or disprove Khot’s Unique Games Conjecture. A proof would be a boon to computer scientists, but a disproof might be even more exciting, Arora said. Researchers agree that disproving the conjecture would probably require innovative new algorithmic techniques that could unlock a host of different approximation problems. “If someone came up with an efficient algorithm [for the Unique Games problem], we would have a very valuable new insight into how to design algorithms,” Arora said.

Khot doesn’t expect someone to prove or disprove his conjecture any time soon. “At this point, we can probably hope to just keep constructing pieces of evidence in one direction or another,” he said. He is working on proving the conjecture but is also exploring whether he can come up with different avenues toward proving approximation hardness results. “That’s the real goal,” he said.

Before his son was born nearly three years ago, Khot used to think about problems related to the Unique Games Conjecture all the time. But with fatherhood, he said, “you suddenly realize there are much more important things in life than what you thought before.”

Heading from his office — where he had been discussing his work with long pauses and carefully chosen words — to the playground, where he was to pick up his son, Khot could barely hide his anticipation. As the little boy ran to meet him, Khot’s brow unfurrowed, and a broad smile swept over his face.

“Of all people, he’s happiest when he’s with Neev,” Ratnaparkhi said. “He talks all the time with Neev.”

Khot said that wanting to spend more time with his son has made him more efficient at work. Before, he would do his research in between reading the news and browsing the Internet. Now, “I have 9 to 5 free to work when he is at day care,” Khot said. “I’m much more organized.”

Math occasionally creeps in while he’s playing with his son, Khot said, but “if the guy is running around, what are you going to do?”

Source: http://www.simonsfoundation.org/quanta/20140812-a-grand-vision-for-the-impossible/