Category Archives: The expert’s corner

You ask, we answer your questions related to the fascinating science at IQIM.

Largest prime number found?

Posted on by
38

Over the past few months, I have been inundated with tweets about the largest prime number ever found. That number, according to Nature News, is 2^{57,885,161}-1. This is certainly a very large prime number and one would think that we would need a supercomputer to find a prime number larger than this one. In fact, Nature mentions that there are infinitely many prime numbers, but the powerful prime number theorem doesn’t tell us how to find them!
nature_news_highlightWell, I am here to tell you of the discovery of the new largest prime number ever found, which I will call P_{euclid}. Here it is:

P_{euclid} = 2\cdot 3\cdot 5\cdot 7\cdot 11 \cdot \cdots \cdot (2^{57,885,161}-1) +1.

This number, the product of all prime numbers known so far plus one, is so large that I can’t even write it down on this blog post. But it is certainly (proof left as an exercise…!) a prime number (see Problem 4 in The allure of elegance) and definitely larger than the one getting all the hype. Finally, I will be getting published in Nature!

In the meantime, if you are looking for a real challenge, calculate how many digits my prime number has in base 10. Whoever gets it right (within an order of magnitude), will be my co-author in the shortest Nature paper ever written.

Update 2: I read somewhere that in order to get attention to your blog posts, you should sprinkle them with grammatical errors and let the commenters do the rest for you. I wish I was mastermind-y enough to engineer this post in this fashion. Instead, I get the feeling that someone will run a primality test on P_{euclid} just to prove me wrong. Well, what are you waiting for? In the meantime, another challenge: What is the smallest number (ballpark it using Prime Number Theorem) of primes we need to multiply together before adding one, in order to have a number with a larger prime factor than 2^{57,885,161}-1?

Update: The number P_{euclid} given above may not be prime itself, as pointed out quickly by Steve Flammia, Georg and Graeme Smith. But, it does contain within it the new largest prime number ever known, which may be the number itself. Now, if only we had a quantum computer to factor numbers quickly…Wait, wasn’t there a polynomial time primality test?

Note: The number mentioned is the largest known Mersenne prime. That Mersenne primes are crazy hard to find is an awesome problem in number theory.

Post-Quantum Cryptography

Posted on by
4

As an undergraduate, I took Introduction to Algorithms from Ron Rivest. One of the topics he taught was the RSA public-key cryptosystem which he had created with Adi Shamir and Leonard Adleman. At the time, RSA was only about a decade old, yet already one of the banner creations of computer science. Today many of us rely on it routinely for the security of banking transactions. The internet would not be the same without it and its successors (such as elliptic curve cryptography, ECC). However, as you may have heard, quantum computation spells change for cryptography. Today I’ll tell a little of this story and talk about prospects for the future.

Ron Rivest

Ron Rivest

What is public-key cryptography (PKC)? The basic notion is due to Ralph Merkle in 1974 and (in a stronger form) to Whitfield Diffie and Martin Hellman in 1976. Their remarkable proposal was that two parties, “Alice” and “Bob”, could cooperate in cryptographic protocols, even if they had never met before. All prior cryptography, from the ancients up through and after the cryptographic adventures of WWII, had relied on the cooperating parties sharing in advance some “secret key” that gave them an edge over any eavesdropper “Eve”.
Continue reading →

De divina proportione

Posted on by
25

As a mathematician, I often wonder if life would have been easier were I born 2,400 years ago. Back then, all you had to do to become eternally famous was to show that 3^2+4^2=5^2 ( I am looking at you Πυθαγόρα!) OK, maybe I am not giving the Ancients enough credit. I mean, they didn’t have an iPhone back then, so they probably had to do 3^2+4^2 by hand. All kidding aside, they did generalize the previous equality to other large numbers like 12^2+5^2=13^2 (I am feeling a little sassy today, I guess.) Still, back then, mathematics did not start as an abstract subject about relations between numbers. It grew from a naive attempt to control elements of design that were essential to living, like building airplanes and plasma TVs. The Greeks didn’t succeed then and, if I am not mistaken, they still haven’t succeeded in making either airplanes, or plasma TVs. But, back then at least, my ancestors made some beautiful buildings. Like the Parthenon.

The Acropolis in Athens, GreeceThe temple of Athina (the Goddess of Wisdom, which gave her name to the city we now call Athens after a fierce contest with Poseidon – imagine flying into Poseidonia every time you visited Greece had she lost) was designed to be seen from far away and inspire awe in those who wished to conquer the city-state of Athens. But, those who were granted access to the space behind the doric columns, came face to face with the second divine woman to ever make Zeus stand in attention, whenever she met her dad on legendary Mt. Olympus: Αθηνά. And so, Φειδίας (Phidias), that most famous of ancient Greek sculptors, decided to immortalize Athina’s power with a magnificent statue, a tribute to the effortless grace with which she personified the wisdom of an ancient culture in harmony with the earth’s most precious gift – feta cheese.

Here she is, playing an invisible electric cello next to Yo-Yo Ma (also invisible).

Here she is, playing an invisible electric cello next to Yo-Yo Ma (also invisible). And yes, she liked to work out.

OK, I may be biased on this one. For Greeks, virgin olive oil and φέτα cheese go like peanut butter and jelly (I didn’t even know the last two went so well together, until I left Greece for the country of America!) Oh yeah, you are probably wondering what feta cheese and olive oil have to do with the Goddess of Wisdom. Well, how do you think she won over the Athenians, against Zeus’ almighty brother, Poseidon? The olive branch, of course. The sea is good and all (actually, the sea is pretty freakin’ amazing in Greece), but you can’t eat it with feta – you can preserve feta in brine (salt water), which is why Poseidon had a fighting chance in the first place – but, yeah, not good enough. Which brings us to the greatest rival, nay – nemesis, of the first letter with an identity crisis, \pi: The letter \phi. You are most likely familiar with the letter-number \pi = 3.1415925123\ldots (you may have even seen the modern classic, American Pie, a tour-de-force, honest look at the life of Pi. No pun intended.) But, what about the number 1.618033\ldots? Well, I could tell you all about this number, \phi, named after the sculptor dude above, but I ‘d rather you figure out its history on your own through this simple math problem:

The divine proportion: Does there exist a function f: \mathbb{N} \rightarrow \mathbb{N}, such that f(1)=2, f(f(n)) = f(n)+n and f(n) < f(n+1) for all n \in \mathbb{N}?

Καλή τύχη, μικροί μου Φιμπονάτσι!

Unsolvable

Posted on by
26
mar-de-plata1

Why go swimming, if you can do math instead inside a room with no windows?

Back in 1997, during my visit to beautiful Mar del Plata in Argentina, I was asked to solve a math problem that I soon realized was close to being unsolvable. The setting was the Banquet for the 38th International Math Olympiad. I was 17 and there was delicious, free food in front of me, so it was pretty impossible to get my attention. Still, the coach of the Romanian team decided to drop by the Greek table to challenge us with the following problem:

Infinite Power: If x^{x^{x^{x^{\dots }}}} = 2, find x.

I was pretty hungry and a bit annoyed at the interruption (it is rude to eat and do math at the same time!), so I looked at the problem for a moment and then challenged him back with this one:

Infiniter Power: If x^{x^{x^{x^{\dots }}}} = 4, find x.

After a few moments, he looked at me with a puzzled look. He knew I had solved his problem within a few seconds, he was annoyed that I had somehow done it in my head and he was even more annoyed that I had challenged him back with a problem that confounded him.

Your mission, if you choose to accept it, is to figure out why the coach of the Romanian IMO team left our table alone for the rest of the competition.

Good luck!

PS: The rest of the Romanian team (the kids) were really cool. In fact, a few years later, I would hang out with a bunch of them at MIT’s Department of Mathematics, or as my older brother put it, The Asylum.

A poll on the foundations of quantum theory

Posted on by
57
Erwin Schrödinger. Discussions of quantum foundations often seem to involve this fellow's much abused cat.

Erwin Schrödinger. Discussions of quantum foundations often seem to involve his much abused cat.

The group of physicists seriously engaged in studies of the “foundations” or “interpretation” of quantum theory is a small sliver of the broader physics community (perhaps a few hundred scientists among tens of thousands). Yet in my experience most scientists doing research in other areas of physics enjoy discussing foundational questions over coffee or beer.

The central question concerns quantum measurement. As often expressed, the axioms of quantum mechanics (see Sec. 2.1 of my notes here) distinguish two different ways for a quantum state to change. When the system is not being measured its state vector rotates continuously, as described by the Schrödinger equation. But when the system is measured its state “collapses” discontinuously. The Measurement Problem (or at least one version of it) is the challenge to explain why the mathematical description of measurement is different from the description of other physical processes.

My own views on such questions are rather unsophisticated and perhaps a bit muddled:

1) I know no good reason to disbelieve that all physical processes, including measurements, can be described by the Schrödinger equation.

2) But to describe measurement this way, we must include the observer as part of the evolving quantum system.

3) This formalism does not provide us observers with deterministic predictions for the outcomes of the measurements we perform. Therefore, we are forced to use probability theory to describe these outcomes.

4) Once we accept this role for probability (admittedly a big step), then the Born rule (the probability is proportional to the modulus squared of the wave function) follows from simple and elegant symmetry arguments. (These are described for example by Zurek – see also my class notes here. As a technical aside, what is special about the L2 norm is its rotational invariance, implying that the probability measure picks out no preferred basis in the Hilbert space.)

5) The “classical” world arises due to decoherence, that is, pervasive entanglement of an observed quantum system with its unobserved environment. Decoherence picks out a preferred basis in the Hilbert space, and this choice of basis is determined by properties of the Hamiltonian, in particular its spatial locality.
Continue reading →

Science books for kids matter (or used to)

Posted on by
46

The elementary school I attended hosted an annual book fair, and every year I went with my mother to browse. I would check out the sports books first, to see whether there were any books about baseball I had not already read (typically, no). There was also a small table of science books, and in 1962 when I was in the 4th grade, one of them caught my eye: a lavishly illustrated oversized “Deluxe Golden Book” entitled The World of Science.

My copy of The World of Science by Jane Werner Watson, purchased in 1962 when I was in the 4th grade.

My copy of The World of Science by Jane Werner Watson, purchased in 1962 when I was in the 4th grade.

As I started leafing through it, I noticed one of the cutest girls in my class regarding me with what I interpreted as interest. Right then I resolved to buy the book, or more accurately, to persuade my mother to buy it, as the price tag was pretty steep. Impressing girls is a great motivator.

The title page.

The title page.

Continue reading →

One, two, three, four, five…

Posted on by
9

As this year comes to a close, people around the world will be counting down the last few seconds of 2012. But, how come we never count up the first few seconds of the new year? What is it about the last few seconds of the year that makes them so special? Maybe it has to do with surviving a Mayan apocalypse, but that was just this year. I guess it always comes down to letting go of the good and of the difficult moments in our past. The champagne helps. Still, I would like to take a moment to pay tribute to the first few seconds of 2013 (the future) with a simple problem and a twist…

back-to-the-future

The question is simple enough:
What is the longest sequence of consecutive numbers, such that each element of the sequence is a power of a prime number?

You will arrive at the answer soon after asking yourself the question: How often is a number divisible by both 2 and 3? The answer is every 6 numbers (since the number in question has to be divisible by 2\cdot3). So, the best one can do is to count the numbers from one to five. That is, if you count 1 as the power of a prime number, then the first five numbers have the incredible property of being the only such sequence of numbers (right?). [Note: Recalling that 1 is not a prime number (see Redemption: Part I, for a hint), we will allow ourselves to use 0 as a valid power to which we may raise a prime number, thus getting 2^0 = 1, which completes the argument.]

Now, here comes the twist…

Challenge: Is there a sequence of 10 consecutive numbers such that none of them is a power of a prime number?

To get the ball rolling, here are the first such sequences with one, two and three elements, respectively: [6], [14,15], [20,21,22].

Super Challenge: Can you find a sequence of 2013 consecutive numbers, such that none of them is a power of a prime number?

Impossible Challenge: Can you solve the first challenge, giving the sequence containing the smallest numbers satisfying the conditions of the problem?

Good luck and enjoy the rest of 2012! Who knows, maybe some genius will solve the above challenges before 2013 rolls around…

Introduction to Quantum Information

Posted on by
13
First slide, viewed on my laptop.

First slide, viewed on my laptop.

I’m lazy. The only reason I ever do anything is that sometimes in a weak moment I agree to do something, and after that I don’t have the nerve to back out. And that’s how I happened to give the introductory lectures leading off the 12th Canadian Summer School on Quantum Information last June.

The video of the lectures recently became available on YouTube in two one-hour segments, which is my reason for posting about them now:

Here are the slides I used. The school is pitched at beginning graduate students who have a solid background in quantum mechanics but may not be very familiar with quantum information concepts.

Andrew Childs, who knows my character flaws well, invited me to lecture at the school nearly a year in advance. Undaunted by my silence, he kept resending the invitation at regular intervals to improve his chances of catching me on a weak day. Sure enough, feeling a twinge of guilt over blowing off David Poulin when he made the same request the year before, and with a haunting sense that I had refused to do something Andrew had asked me to do on an earlier occasion (though I can’t recall what), one day in September I said yes, feeling the inevitable stab of regret just seconds after pushing the Send button. I consoled myself with the thought that this could be a Valuable Service to the Community.

Actually, it was fun to think about what to include in my lectures. The job was easier because I knew that the other lecturers who would follow me, all of them excellent, would be able to dig more deeply into some of the topics I would introduce. I decided that my first responsibility should be to convey what makes the topic important and exciting, without getting too bogged down in technicalities which were likely to be addressed later in the school. That meant emphasizing the essence of what makes quantum information different from ordinary “classical” information, and expounding on the theme that classical systems cannot in general simulate quantum systems efficiently.

The conditions under which I delivered the lectures were not quite ideal. Preparing PowerPoint slides is incredibly time consuming, and I believe in the principle that such a task can fill however much time is allotted for it. Therefore, as a matter of policy, I try to delay starting on the slides until the last moment, which has sometimes gotten me into hot water. In this case it meant working on the slides during the flight from LA to Toronto, in the car from Toronto to Waterloo, and then for a few more hours in my hotel room until I went to bed about midnight, with my alarm set for 6 am so I could finish my preparations in the morning.

It seemed like a good plan. But around 2 am I was awakened by an incredibly loud pounding, which sounded like a heavy mallet hammering on the ceiling below me. As I discovered when I complained to the front desk, this was literally true — they were repairing the air-conditioning ducts in the restaurant underneath my room. I was told that the hotel could not do anything about the noise, because the restaurant is under different ownership. I went back to bed, but lost patience around 3:30 am and demanded a different room, on the other side of the hotel. I was settled in my (perfectly quiet) new room by 4 am, but I was too keyed up to sleep, and read a book on my iPad until it was 6 am and time to get up.

I worked in my room as late as I could, then grabbed a taxi, showing the driver a map with the location of the summer school marked on it. Soon after he dropped me off, I discovered I was on the wrong side of the University of Waterloo campus, about a 20 minute walk from where I was supposed to be. It was about 8:15, and the school was to begin at 8:30, so I started jogging, though not, as it turned out, in the right direction. After twice asking passersby for help, I got to the lecture hall just in time, my heart pounding and my shirt soaked with sweat. Not in the best of moods, I barked at Andrew that I needed coffee, which he dutifully fetched for me.

Though my head was pounding and my legs felt rubbery, adrenalin kicked in as I started lecturing. I felt like I was performing in a lower gear than usual, but I wasn’t sure whether the audience could tell.

And as often happens when I reluctantly agree to do something, when it was all over I was glad I had done it.

Is Alice burning? The black hole firewall controversy

Posted on by
83
Quantum correlations are monogamous. Bob can be highly entangled with Alice or with Carrie, but not both.

Quantum correlations are monogamous. Bob can be highly entangled with Alice or with Carrie, but not both.

Back in the early 1990s, I was very interested in the quantum physics of black holes and devoted much of my research effort to thinking about how black holes process quantum information. That effort may have prepared me to appreciate Peter Shor’s spectacular breakthrough — the discovery of a quantum algorithm for factoring intergers efficiently. I told the story here of how I secretly struggled to understand Shor’s algorithm while attending a workshop on black holes in 1994.

Since the mid-1990s, quantum information has been the main focus of my research. I hope that some of the work I’ve done can help to hasten the onset of a new era in which quantum computers are used routinely to perform super-classical tasks. But I have always had another motivation for working on quantum information science — a conviction that insights gained by thinking about quantum computation can illuminate deep issues in other areas of physics, especially quantum condensed matter and quantum gravity. In recent years quantum information concepts have begun penetrating into other fields, and I expect that trend to continue.
Continue reading →

Showtime for Sophomores

Posted on by
9

Exciting a square Chladni plate with a violin bow.

One of the many unique features of Caltech is our core curriculum. All of our undergraduates are required to take five terms of physics and five terms of math (all three terms freshman year and the fall and winter terms sophomore year) — though this will change for the class entering in the fall of 2013.

Each fall, about 170 sophomores take Physics 2a, a course on vibrations, waves, and quantum mechanics, while the remaining 60 or so sophomores take Physics 12a, a souped up course covering similar material at a level more appropriate for physics concentrators.

This term I am teaching Physics 2a. While 170 students is a lot more than in most courses I teach at Caltech, the workload is manageable, in part because I share the lecturing duties with another professor, and in part because we have a staff of capable and hard working Teaching Assistants who handle recitation sections and grade the homework and quizzes.

Continue reading →