| Page 23

Look Around You: Spherical Videos and Möbius Transformations

Posted on February 1, 2016 by evelynjlamb

A spherical photo, cut and pasted onto your rectangular screen. Image: Henry Segerman.

A spherical photo hit with the complex exponential function. Image: Henry Segerman.

I’ve lost count of the number of times I’ve watched the short video “Möbius transformations revealed” by Douglas Arnold and Jonathan Rogness.

It is a beautiful tribute to beautiful functions. As a complex analysis and hyperbolic geometry fangirl, I am contractually required to get a little misty-eyed when I think about Möbius transformations.

I thought “Möbius transformations revealed” was the pinnacle of Möbius transformation-related video until Henry Segerman posted this one last month.

(It took me a while to realize that if you’re on a computer and your browser supports it, you can push the arrows in the compass at the top left of the frame to look around the sphere. For phones it’s a little different. My iPhone shows the full frame, but I think on Android devices, you can see different parts of the video by moving your phone around. Your mileage may vary.)

Möbius transformations turn out to be the answer to some tricky problems that come up in spherical video, namely, how to zoom or rotate the way you would with rectangular videos. Like Frank Farris’ book Creating Symmetry, the mathematics inspires the creation of beautiful and interesting images. Segerman wrote a guest post about using Möbius transformations in spherical video editing on the eleVR blog. EleVR is the virtual reality research group of Emily Eifler, Vi Hart, Andrea Hawksley, and Elijah Butterfield, the team behind Hypernom, a game where you try to eat the cells of four-dimensional Platonic solids and other VR endeavors. Their blog documents the fascinating challenges, both mathematical and logistical, of creating and interacting with spherical videos. I love the Sphere-a-day post in which Eifler talks about how different spherical videos feel to her as a creator:

Many of the daily spherical videos so far feel more like ‘Come hang out with me while I do this thing I would be doing anyway,’ the largest number falling into the ‘I am making art and the camera is running’ category which reveals a lot about how I spend my life, something I never let happen when I was making flat video. In flat video I kept video Emily and RL Emily very separate, but not so in spherical. Its feels like documentation without translation into textual or verbal language and the non-framed non-presentational all seeing eye of the camera makes me feel more relaxed, more open, and frankly just more adventurous and laissez faire about what I can shoot with it. Nothing gets cropped out, nothing gets left behind.

Spherical videos already offer viewers the opportunity to interact with videos in new ways, but using Möbius transformations on them gives creators new ways to tell stories. With the help of the eleVR-ers, Segerman illustrates this beautifully in a spherical Droste video where you feel like you’re taking an endless scroll through a time loop.

To watch more spherical videos, check out Eifler’s YouTube channel BlinkPopShift, Segerman’s channel, and the eleVR channel.

A spherical picture hit with a Schottky function. Image: Henry Segerman.

A spherical picture hit with a Schottky group. Image: Henry Segerman.

Spherical video is still young, and people are still discovering new ways to make art with it. I can’t wait to see what comes next. Now get out of here and go watch something!

Posted in Math Communication, Mathematics and the Arts | Tagged Andrea Hawksley, droste effect, eleVR, Emily Eifler, henry segerman, Moebius transformations, spherical video, Vi Hart, virtual reality | Comments Off

There’s a New Prime! And It Looks Like…Wait…What?

Posted on January 25, 2016 by annahaensch

A new prime has been discovered. It’s really long. Over 22 million digits. And the number has just been sitting on a computer in the middle of Missouri unnoticed since September. But that’s not the crazy thing about it. The crazy thing is that it’s equal to 2^74,207,281-1. Why should something like that be a prime, and how on earth did we find it?

If you printed out the new prime it would take over 15 reams of paper. Photo courtesy of Pawpaw67 via Flickr.

If you printed out the new prime it would take over 15 reams of paper. Written out end to end, the number would be over 22 kilometers long. Photo courtesy of Pawpaw67 via Flickr.

Turns out, primes of that form have been a hot topic for some time. Let’s go back to the beginning of the story. Since humans figured out how to factor numbers, humans have been looking for primes — remember, those are the numbers greater than 1 which are only divisible by 1 and themselves. In the 14th and 15th century people were very interested in finding a simple rule that you could apply to numbers to guarantee that you would get a prime, some sort of prime generating function.

In the 16th century, monk slash mathematician Marin Mersenne started to consider numbers of the form 2ⁿ-1. He noticed that often, when you put a number in place of n you get a prime back. If you try out a few values of n, it seems to work: 2²-1=3, 2³-1=7, and 2⁵-1=31. Today, if a number of that form turns out to be a prime, we call it a Mersenne Prime. So, is it true that if we plug any number n into that rule, we get a prime back?

Nope. He (and probably anybody who’s taken a course in elementary number theory!) can see that if n is composite — so if n=ab for some integers a and b — then of course both 2^a-1 and 2^b-1 divide 2ⁿ-1, so there’s no way it’s prime.

But it’s not enough just to insist that n is prime, since it doesn’t take too much heavy lifting to see that 2¹¹-1=23×89.

Mersenne knew it wasn’t so simple, but he put together a list of n values that he thought would give back primes. Since he was living in the 16th century, and only had a quill pen and some parchment to do his calculations, quite a few turned out to be wrong. Quite notably, as was the subject of the best This American Life Prologue of all time, Frank Nelson Cole found an error in one of Mersenne’s calculations.

Nevertheless, due to significant advances in computing power and the Lucas-Lehmer test for primeness, searching through Mersenne’s numbers has proven to be a reasonably successful way to look for primes.

So successful, in fact, that we just found a new Mersenne prime this week! Needless to say, my Twitter feed has been blowing up. This discovery has gotten a great deal of media attention, some that’s tons of fun and some that’s…well…it’s what you might expect from math press. But my co-blogger Evelyn gave a beautiful recap of the search for the prime on Slate.com.

This is exciting news, not in that it changes the face of mathematics or unlocks some great mystery, but that it’s just so cool and satisfying this to come up with concrete examples of theoretical concepts. It’s ties such a beautiful thread through history to know that we are chipping away at the same simple ideas that have occupied minds for so many centuries.

Posted in Number Theory, Uncategorized | Tagged GIMPS, Mersenne Prime, number theory | 1 Comment

Today’s Post Is Brought To You By The Letter P

Posted on January 10, 2016 by annahaensch

There is this joke that people like to make. It’s something about how real mathematicians don’t use numbers. It’s a little bit funny, and a lot true. As a number theorist, I, more so than anybody, should be using numbers, but the truth is that I rarely do. In my research, almost everything I do is symbolic. You know, like “let p be a prime,” or “Π is an element of the permutation group on p many elements”. For better or worse, we love to use symbols to simplify the way we communicate math.

But are we really simplifying things, or just making them a whole lot more confusing?

There’s a patent on π. That is, π with a period after it, like I just did. π period.

In the newest episode of the mathematics podcast Relatively Prime, host Samuel Hansen has a conversation with Joseph Mazur, author of the history of symbols in mathematics, Enlightening Symbols. Hansen and Mazur discuss the relatively recent — well, bearing in mind that in terms of mathematics the 16th century was just yesterday — creep of symbols into the mathematical lexicon, and what that means for understanding mathematical ideas. If the father of algebra, Hansen points out, “had picked up your algebra textbook, he would have no idea what he was looking at.”

According to Mazur, “a symbol is something that is graphic, but is also something that doesn’t look like the thing it represents.” Such a distinction is important to make, lest we start thinking that words or even numbers themselves are symbols. The letter π (that’s the lowercase one, not to be confused with the upper case Π in the first paragraph), Mazur says, doesn’t count as a symbol because the greek π denotes that irrational number 3.14159… which is just the perimeter of a circle divided by its diameter, and perimeter starts with p, the greek equivalent of p is π…you get the idea.

I’m not sure that I totally agree with Mazur’s definition of what constitutes a symbol. By his logic Π as an element of the permutation group, isn’t a symbol since permutation starts with p, nor is the Σ for summation, and therefore ∫ for integral. So I’m going to say that in math, a symbol is any non-number or non-word representing a mathematical idea.

The good thing is that you can convey a great deal of information very quickly, and to the initiated audience, very little preamble is necessary. For example, my head nearly exploded when I took my first course in graduate number theory, taught by my advisor, who used the following three versions of the letter p all to denote distinct objects.

At first I was horrified. But after a few hours it started to make sense. You begin by letting p be a prime, and then the other two versions of p are just describing the way that same p looks in a different stage of life. Without getting too jargony on you, it’s just like having baby, mama, and grandma p, all from the same lineage.

This of course brings with it a collateral problem of writing these letters on the board, which is tantamount to writing high-speed calligraphy with a dull crayon. I’ve found that you just sort of find your personal style after awhile, but for those just starting, Old Pappus’ Book of Mathematical Calligraphy is the ultimate style guide for writing math symbols.

So, are we really simplifying things, or are we just building a big gigantic paywall around mathematics to make everything we do look as scary as possible? I’m not sure, because when I write math I’m certainly happy for the symbols, but when I stare at a page of math I know that my eyes always scan for written prose first. What do you think? Let me know @extremefriday.

Posted in Math Communication | Tagged Relatively Prime, Samuel Hansen, symbols | 5 Comments

The Best and Worst of Math in 2015

Posted on December 30, 2015 by annahaensch

The year is coming to an end, that means it’s time for me to put on me best sequined dancing pants, pop open a bottle of champagne and reflect on some of the highs and lows of the last 12 months, particularly, some of the best and worst things that have happened for math in 2015.

The Best of 2015

This year put to rest a couple of huge conjectures, two of which I’ve blogged about right here, the Erdos discrepancy problem and the graph isomorphism problem, as well as several other interesting breakthroughs, like the discovery of a new pentagonal tiling.

Another great thing to happen in 2015 was Piper Harron’s PhD thesis, which caused a huge splash, not because of the groundbreaking mathematics, but because it was an indicting commentary on the culture of mathematics and mathematicians. Harron’s thesis is a take-down of sorts, of the pervasive opacity and exclusivity of mathematics, her thesis, she writes for math babe, is “this thing that was initially going to be a grenade launched at my ex-prison, for better or for worse, and instead turned into some kind of positive seed bomb where flowers have sprouted beside the foundations I thought I wanted to crumble.”

On a more nebulous note, I feel like 2015 was the year that mathematics became a cool thing to do. I’m not sure whether it’s the sudden uptick of cool math portrayed in films and TV like The Imitation Game and the amazingly unmitigated awesomeness that is The Bletchley Circle, or if it’s the rise of the hot shot billionaire math majors like Sergey Brin and James H. Simons, but somewhere out there is a PR campaign being waged for math, and it’s looking good.

The Worst of 2015

In June 2015 the Notices of the AMS (sorry AMS) had this cringe inducing cover with the caption “the polyface of polymath” that featured 13 very heterogeneous faces. And I guess it’s not the fault of the AMS — or the fault of the Polymath project — that there isn’t more diversity in the contributor pool, but nevertheless when I first saw that cover I felt like, “Really, math? That’s all you’ve got for me?”

Here’s something that’s been in the worst column for me since 2012: we still haven’t verified Mochizuki’s proof of the abc conjecture. Although Mochizuki announced his proof of the famous number theory conjecture in 2012, using something he called inter-universal Teichmuller theory, here we are, 3 years later, and it’s still not clear whether his proof is correct. And this is despite a tremendous effort on the parts of dozens of top mathematicians to understand the dense and seemingly opaque arguments. But just last month there was a workshop at Oxford where the top minds gathered to (hopefully) get a deeper understanding into the fundamental mechanics of Mochizuki’s proof. Brian Conrad blogged about his experience at the workshop and points out “It was not the purpose of the workshop to evaluate the correctness of the proof. The aim as I (and many other participants) understood it was to help participants from across many parts of arithmetic geometry to become more familiar with some key ideas involved in the overall work so as to (among other things) reduce the sense of discouragement many have experienced when trying to dig into the material.” So, maybe in 2016 we can move this one into the best column?

Finally, we have the perennial problem of Americans lagging on numeracy and mathematical literacy, as compared to other developed nations. I feel like each year sees a new batch of data to remind us of this sad state. Unfortunately, turning around this desperate barge is going to take some doing.

Now that’s all I’ve got. Do you disagree with me on any of these? Do you have some of your own mathematical highs and lows to share? Let me know on Twitter, @extremefriday.

Posted in Uncategorized | Comments Off

Diagonalization and Other Mathematical Wonders

Posted on December 21, 2015 by evelynjlamb

It’s only a slight exaggeration to say I’m a mathematician because of Cantor’s diagonalization arguments (both the proof that the rationals are countable and the proof that the reals aren’t). I was already enjoying my intro to proofs class when we got to it, but it was the first theorem in the class (or in math generally) that truly astonished me.

In a highly scientific survey of all the mathematicians who live in my house, diagonalization made a strong showing as mind-blowing math. Image: Jochen Burghardt, via Wikimedia Commons.

In a highly scientific survey of all the mathematicians who live in my house about mind-blowing mathematics, diagonalization made a strong showing. Image: Jochen Burghardt, via Wikimedia Commons.

Mike Lawler recently wrote a post about math that made him go whoa! that links to a recent Reddit thread on the same subject. Lawler’s list includes the residue theorem and Galois theory along with Polya’s theory of counting, a topic I was unfamiliar with. Unsurprisingly, I am not alone in being astonished by the diagonalization argument, but people love a lot of other mathematics as well.

If you’re feeling a little blah after a long semester and months of dwindling daylight (Southern Hemisphere-dwellers, just imagine you’re reading this in six months), a trip through that Reddit thread might cheer you up. It’s got some of the greatest hits of undergraduate math and a good dose of heavier research math to boot. (Incidentally, maybe I need to bite the bullet and read the proof of the Riemann-Roch theorem in Hartshorne, which comes highly recommended by at least one Redditor.)

Reading through other people’s top mathematical moments naturally led me to reflect on my favorite bits of mathematics. I was a late mathematical bloomer. Not a lot of math really blew my mind in college because my attitude at the time tended towards the utilitarian. Diagonalization notwithstanding, I didn’t often appreciate the beauty of what I was learning or even know that I should be surprised by it. As time passes, I gain more and more respect for many ideas in math, even ones I’ve been familiar with for years.

For me, teaching complex analysis this semester was refreshing. Revisiting the basic material and really feeling like I understood how all the pieces fit together was gratifying. I have never appreciated the Cauchy integral formula more. Another recent time I really felt like I had a new appreciation for a theorem came last semester, when I was teaching undergraduate geometry and topology. The Gauss-Bonnet theorem seemed to tumble from the classification of surfaces in a way that felt so much more natural to me than it had when I first learned it.

Finally, I can’t reminisce about mind-blowing math without pointing to my favorite piece of mathematics communication of the year, and SMBC comic about Kempner series. (Kevin Knudson’s Forbes post on the topic is fun, too, although it doesn’t use the word “balls” as many times.)

Image: Zach Weinersmith, SMBC Comics.

When was the last time math made you say “What the balls?!”

Posted in Math Communication | Tagged diagonalization, Kevin Knudson, Mike Lawler, nostalgia, smbc comics | 4 Comments

Stuff Math Professors Say

Posted on December 14, 2015 by annahaensch

It’s December, the semester is winding down, we all need a break from deep thinking about hard math. So this week I have some extra special brain candy I’ve been saving up for you, in the form of a Tumblr, Math Professor Quotes.

You can browse by subject, or just take your time and scroll through them all, but either way, prepare to give up at least 15 minutes of your life. It’s fun. I always find the number theory quotes extra hilarious, but having just taught discrete math this semester, these were giving me the giggles extra hard.

I myself have always been a fan of the $2 words injection and surjection, not because I’m a fancy pants who drinks from a frosted mug — I prefer my beer in a can, thanks — but just because (for unclear reasons) I hate the word onto. I mean, how can onto even be a word? It doesn’t have the heft that I need such an important piece of terminology to bear.

I do always feel silly talking about pigeons and holes. Do pigeons even live in holes? And even if they did, are they tame enough to be placed into the holes by a handler? Anyways, some of these quotes hit really close to home, and I start to wonder, have I said that before? If not, I should really start saying it.

Posted in Uncategorized | Tagged Math Professor Quotes, Tumblr | 4 Comments

Blogging Counterexamples

Posted on December 8, 2015 by evelynjlamb

I can’t believe someone has been blogging about counterexamples since July of last year and I just found out! Luckily, the Aperiodical Advent Calendar alerted me to it yesterday, and now Math Counterexamples is the newest addition to my blog feed.

The Smith-Volterra, or “fat” Cantor set, a great counterexample in topology. Image: Inductiveload, via Wikimedia Commons.

Counterexamples have been on my mind a lot lately. This spring, inspired by a post I wrote about the π-Base, an online analogue of Counterexamples in Topology, I started writing about some of my favorite spaces at my Scientific American blog Roots of Unity. Many of these spaces are counterexamples: connected but not path connected, nowhere dense but having positive measure, contractible but in no obvious way. While my posts tend to be focused on geometry and topology, Jean-Pierre Merx, who writes Math Counterexamples, is an equal-opportunity counterexample-ist. His posts cover topics in algebra and analysis as well as topology.

Like Tai-Danae Bradley’s blog Math3ma, which I wrote about a couple months ago, I imagine Math Counterexamples would be a great resource for undergraduate or graduate students in math. (Their professors should probably pay attention, too: these are great resources to share with your students, but you may also want to make sure the questions you give aren’t immediately google-able!)

I’m especially partial to the analysis counterexamples right now because they’re useful but I often have trouble cooking them up on my own. A recent post that caught my eye is about a function from R² to R with a local minimum at (0,0) on all lines through the origin but which doesn’t have a local minimum there when considered as a function of two variables. Weird, huh? If you go poking around the archives, I’m sure you’ll find some fun factoids too.

Posted in Math Education | Tagged algebra, analysis, counterexamples, Jean-Pierre Merx, topology | 3 Comments

And For The Mathematician Who Has Everything

Posted on November 30, 2015 by annahaensch

I don’t mean to sound ungrateful, but as a mathematician, I’ve been on the receiving end of one too many well-intentioned protractor cases and Π-themed pie plates. And I’ll concede, if you are anything like me, it is likely a challenge for your loved ones to shop for your bizarrely math-obsessed tastes. But to help you, my matheux readers, here are some of the items I’ll be posting to my Christmas list this year.

Rubinstein making everyone at ICERM jealous in his Ramanujan swag.

Rubinstein spotted at ICERM sporting his Ramanujan swag.

Nothing bespeaks your love for mathematics quite like a T-shirt bearing the likeness of Srinivasa Ramanujan or the Princeps mathematicorum himself, Carl Friedrich Gauss. Now this is possible thanks to Michael Rubinstein, a professor at the University of Waterloo, and his fine collection of mathematical swag. using historical paintings and photos, Rubinstein sketched these famous mathematicians in intense black and white, and from his sketches he has curated a collection of T-shirts and tote bags to satisfy even the most snoooty of number theorists on your list. And I have personally experienced the effect of these shirts, I recently ran into Rubinstein at ICERM when I locked eyes with Ramanujan’s icy stare from across the room. You can get art posters, T-shirts, and tote bags at his online store here — I’m particular to the Ramanujan tote myself.

The Fibonacci clock, for the person who loves circuit boards as much as style.

The Fibonacci Clock was launched as a Kickstarter campaign by Philippe Chrétien. The clock is powered by a small Arduino computer, and displays the time by lighting up different colored panels in Fibonacci’s famous golden rectangle. The clock itself is very stylish and beautiful, but it’s also a fun brain exercise because you’re required to do some quick arithmetic to read the time. The squares indicate the numbers 1,1,2,3,5 in the Fibonacci sequence, and the display color — red, green, or blue — indicates whether the number represents minutes, hours, or both. The clock can now be purchased here for $135 fully assembled, or as a pile of parts for $85. Obviously, go for the second option.

A geometric art print is sure to lend just the right gravitas to the home or study.

Finally, for that barren office wall that needs some pizazz, the beautiful mathematical prints at Geometry Daily are a feast for the eyes. The prints are by graphic artist Tilman Zitzmann, and I’ll admit, have shown up here on the Blog on Math Blogs before. Prints can be purchased at the artist’s Society6 online store and start as low as $20. The only difficulty that I see with these prints — and indeed the reason that I don’t currently own one — is that it’s so hard to pick a favorite. And that makes these a perfect gift item, because then you can burden someone else with choosing it for you.

If you have other great mathematical gift ideas, let me know on Twitter @extremefriday. And for the math educators on your list, I have to end with a hat-tip to my little brother for getting me the most, not mathematical, but certainly professorial, gift ever: A chrome telescoping pocket pointer. Bust this baby out midway through the semester, and it makes L’Hopital’s Rule go down real easy.

Posted in Mathematics and the Arts, Recreational Mathematics, Uncategorized | Tagged Fibonacci Clock, geometry daily, Math Art, Michael Rubinstein, Tilman Zitzmann | Comments Off

How Math Can Help You Avoid Talking about Politics at the Holidays

Posted on November 23, 2015 by evelynjlamb

Another fun family activity is to make hand turkeys and fill them with the theorems you're most thankful for. Image: Evelyn Lamb

A fun family Thanksgiving activity is to make hand turkeys and fill them with the theorems you’re most thankful for. Image: Evelyn Lamb.

Happy Thanksgiving! I’m sure your wonderful family is the exception, but sometimes holiday dinner conversations can veer into unpleasant territory. If you don’t have Adele to bail you out, math blogs are here to help. (When your only tool is a math blog, every problem looks like…well, whatever a math blog can solve.) If you need a conversation topic for a group of turkey-bloated people with a diverse range of opinions about politics, religion, and morality, here are some suggestions from the math blogosphere.

What your part of America eats for Thanksgiving, courtesy of FiveThirtyEight. There’s nothing more satisfying than talking about food as you devour it. Green beans or squash? Canned cranberry sauce or whole berry? Are Thanksgiving cherry pie eaters totally depraved or just slightly misguided?

With a few diagrams scratched into the mashed potatoes, anyone can appreciate this elegant proof of the Pythagorean theorem attributed to Albert Einstein.

Tanya Khovanova’s math blog is rife with fun puzzles, but my favorite at the moment is this one: How many letters are there in the correct answer to this question?

Likewise, Math Munch has lots of fun topics and activities to look into. Hypernom seems especially appropriate for this particular holiday.

How many pentagonal tilings can you make with turkey bones and orphaned green beans after dinner?

Mathematicians have proved that English is trivial. In that article, Alex Bellos gives “aisle” and “isle” as an example. They are homophones, so we can do a little algebra to show aisle=isle, which means a=1. In fact, we can find homophones to reduce every letter of the alphabet to 1. Can you prove it around the dinner table? As a bonus, try to prove it for other languages represented around your table.

The Erdős discrepancy conjecture, one of the many (fairly) easy to state but hard to prove conjectures about sequences of integers, was recently proven. Everyone likes numbers, so you can definitely get people talking about these conjectures and maybe even make some progress at the Collatz conjecture.

Graph isomorphism! Those feisty computer scientists are at it again, whittling down the known complexity of NP-intermediate problems. You can get the whole family involved in this one: draw some graphs with leftover cranberries and green beans and see if they’re isomorphic. Were you able to do it in polynomial time?

What is the funniest number? Do you agree with Catch-[insert funny number] author Joseph Heller and his agent?

If you did an average of a 15:00 mile over the course of the race, is there a mile you traveled in exactly 15:00? Get thee to a turkey trot for some real-world experiments!

What’s up with Shinichi Mochizuki’s proof of the abc conjecture? And what does the saga say about the sociology of mathematics? For that one, you might need to brush up on what exactly the abc conjecture is. Luckily, Numberphile has you covered.

Can you wrap your mind around the function x^x?

If you want to stir the pot but prefer to avoid politics, Is 5×3 five threes or three fives, and does it matter?

If all else fails, you can always gather the family around the computer screen, watch Vi Hart’s mathematical Thanksgiving celebration, and lament the fact that you made a green bean casserole rather than a green bean matherole.

However you celebrate or don’t, I hope you have a peaceful holiday.

Posted in Events | Tagged holiday math, holidays, linkfest, math, mathematics | Comments Off

Meanwhile Over In Computer Science

Posted on November 16, 2015 by annahaensch

An algorithm has just been proposed for solving the graph isomorphism problem in quasipolynomial time, dealing a serious blow to hard problems all over the world. But let me first explain what all of those words mean.

Graphs, you’ll recall, are simply collections of nodes linked together by edges. If you look at the image below, you see three different graphs. Each has four nodes linked together with four edges. But wait, are they actually different? If you take the graph to the far left and twist the top and bottom, you get the graph in the middle. So we say these two graphs are the same, or in mathematical jargon: isomorphic. Any time you can twist and deform to get from one picture to another (without detaching any of the edges or nodes), you are dealing with isomorphic graphs. So what about the graph on the far right, can you twist and pull that one to make it look like the first two?

Sure, you can. This is the essence of the graph isomorphism problem: how do we decide when two graphs are isomorphic? And this example above is pretty easy, but as you increase the number of nodes, this quickly becomes a really hard problem. In the parlance of algorithms, it is even thought to be NP hard. Or rather, it was thought to be NP hard until University of Chicago’s Laszlo Babai totally pwned it last week. It was announced that Babai has discovered a quasipolynomial time algorithm for deciding isomorphism of graphs, which is a massive discovery in the face of classicaly super-duper hard problems in complexity theory.

When we measure the speed of this sort of algorithm, we measure it relative to the number of nodes n. A really fast algorithm would only increase in complexity at the rate of a polynomial in n. A really slow algorithm would increase exponentially relative to n. Babai’s algorithm seems to sit somewhere between the two. It’s faster than anything that’s ever been done before, bit it’s not quite polynomial fast either, so fittingly, it is called quasi-polynomial.

Babai is unveiling his results in a series of three talks at the University of Chicago, the first two of which have already been graciously livetweeted by Gabriel Gaster — a sincere tip of the hat to Gaster for this exciting blow-by-blow.

Screenshot from Gabe Gaster’s Livetweet of Babai’s first Graph Isomorphism Talk.

Computer scientist and blogger at Shtetl-Optimized, Scott Aaronson, gives a nice breakdown of the striking features of this new result that make it such a dramatic step forward from its predecessors, including its relationship to string isomorphisms, finite simple groups, and Luks’ algorithm from 1982. For all the gory details on the mathematical content of Babai’s talk, Jeremy Kun posted a recap of the November 12th lecture, which he intends to update as further details emerge. In the meantime, there are some thoughtful discussions going on over in the comments section at In Theory, computer scientist Luca Trevisan’s blog.

As for the preprint, rumor has it that Babai said it will be available “soon, soon.” It’s all very exciting, but we have to remember to keep our proverbial hats on until everything is checked out. But it occurs to me that it suddenly became a lot more difficult to walk around glibly saying how hard it is to factor large numbers, and how secure our cryptosystems are because of that. Because who knows, graph isomorphism today…maybe factoring tomorrow?

Posted in Events, Mathematics and Computing | Tagged complexity theory, Gabriel Gaster, graph theory, Jeremy Kun, Laszlo Babai, Luca Trevisan, P vs NP, Scott Aaronson | 2 Comments