Sunday, July 21, 2019

253: Making Jewelry With Fermat

Audio Link

Whenever you hear the name of the 17th century French mathematician Pierre de Fermat, the first thing that comes to your mind is probably Fermat’s Last Theorem.   That, as I’m sure you remember, is his well-known unproven hypothesis about an + bn = cn not having whole number solutions for n>2.   That one is rightfully famous for having stumped the math community for hundreds of years, until Princeton professor Andrew Wiles finally proved it in the 1990s.   But Fermat was no one-theorem wonder.    He was quite an accomplished mathematician, and came up with many other interesting results, most of which are proven a lot more easily than his Last Theorem.   In particular, one of his best-known other ideas, “Fermat’s Little Theorem”, is arguably a much better legacy.   Aside from having been proven by Leibniz and Euler within a century of its proposal, its applicability in forming primality tests has made it a foundation of some of the algorithms used in modern cryptography.   These algorithms form the basis of systems like the RSA encryption used in many secure internet protocols.

So, what is Fermat’s Little Theorem?   Like his Last Theorem, it’s actually pretty easy to state:   For any prime number p and integer n, np - n is always divisible by p.   So, for example, let’s choose p = 3 and n = 5.   The theorem states that 53 - 5 will be divisible by 3.   Assuming you haven’t forgotten all your elementary arithmetic, you probably see that since 53 - 5 is 120, which is 3 times 40, the theorem works.   Since the theorem is true for all primes, it implies a basic test you can use to prove a number is composite, or non-prime:   if you are examining a potentially prime number p, pick another “witness” number n and check whether the condition of the Little Theorem holds true.   If it doesn’t, we know p isn’t prime.   Of course, this is a probabilistic test— you can get lucky with a nonprime number, like 341 which passes the test (with n = 2) but is equal to 31 times 11.   So you need to calculate the odds and choose samples accordingly.   Modern algorithms use more sophisticated techniques, but still build on this foundation. 

The reason Fermat’s Little Theorem came to mind recently was that I was browsing the web and saw a very nice common-sense proof of the theorem at the “Art of Problem Solving” site.   Like most math majors, I did learn about some proofs of this theorem in college classes, and it’s not too hard to jot down the proper equations, simplify, and prove it inductively using the algebra.   But I always prefer intuitive non-algebraic proofs where I can find them:  though there’s no logical excuse to doubt the bulletproof algebra, my primitive human brain still feels more satisfied with a proof we can visualize.    So, how can we prove that for any prime number p and integer n, np - n is always divisible by p, without using algebra?

Let’s visualize a jewelry-making class, where you are given a necklace that can fit up to p beads, each of which can come in n colors.   Actually, to help visualize, let’s use concrete numbers initially:  your necklace can fit 3 beads, each of which can come in up to 5 colors.     There are thus a total of 53 permutations of beads you can put together on a necklace:  5 choices for the first bead, times 5 for the second, times 5 for the third.     5 of these 53 combinations are necklaces where all the beads are the same color, so let’s put those aside for now.   If you look at any example configuration from the remaining 53 - 5 available, you will see that it actually must be one representative of a family of 3 necklaces.  For any necklace where all 3 beads are not identical, you can rotate it 3 ways, with each rotation being a valid combination.   Since every possible combination must be part of such of a family of 3, and there are no combinations from 2 families that can be equivalent, the number of remaining combinations must be divisible by 3.   Thus,  53 - 5 is divisible by 3, and the theorem holds.   Since this argument works for any prime p and integer n, it effectively proves the theorem.

Anyway, if you’re not already convinced, hopefully after doodling a few necklaces on a scratchpad, or taking your daughter to a jewelry-making class, you can see why the theorem holds.   I always like it when I see a simple intuitive argument like this for what seems at first to require messy algebra— even though we can’t know Fermat’s thought processes for sure, I wouldn’t be surprised if he did this kind of visualization when first coming up with the concept.

And this has been your math mutation for today.


References: 




Sunday, June 23, 2019

252: A Mathematician Translating Pushkin?




I just finished reading an English translation of Alexander Pushkin’s famous 19th-century book-length Russian epic poem, Eugene Onegin, a classic tale of tragedy and lost love.    This might seem like an odd topic for a math podcast, except for the name of the translator:  Douglas Hofstadter.   If you’re a fellow math geek, you may recognize him as the author of “Godel Esher Bach”, “Metamagical Themas”, and several other of the greatest modern books in the popular math genre.    Now it’s not totally unprecedented for him to translate a poem, as you may recall that in episode 125, we discussed his book “Le Ton Beau de Marot”, which discussed many mathematical aspects and artistic choices made in translating a short French poem.   Still, taking on the translation of such a famous book-length poem is a major undertaking.   What is it about Eugene Onegin that would attract a mathematician?

Aside from the general qualities of the poem and the classic story, one of the major factors that attracted Hofstadter was the several levels of intricate patterns embedded in Eugene Onegin.  Pushkin created a very original rhyme scheme, with the poem divided into 14-line stanzas of the form ABAB CCDD EFFE GG.   If you look at those first three sets of four lines, they might look a bit familiar from other discussions we’ve had in the podcast:   they are the three possible patterns you can get by flipping four coins, and resulting in two of each side:  ABAB, CCDD, or EFFE.   It seems odd at first that you can’t put your four coins together without getting something that looks like a pattern— no matter how you arrange them, they won’t look random!   Perhaps this is part of what attracted Pushkin to the scheme.

But there is yet another layer of patterns imposed on top of this:  what is called “feminine” and “masculine” rhymes.   A masculine rhyme is a single stressed syllable at the end of a line, like “turn” and “burn”.  In a feminine rhyme, there are two syllables involved, with the stress being on the first:  “turning” and “burning”.   The unstressed syllables may rhyme or be identical.   The pattern of masculine and feminine lines in each stanza is FMFM FFMM FMMFMM.

And on top of this, the poem is in iambic tetrameter, with the stress always falling on even numbered syllables, and exactly 8 or 9 syllables per line:  8 in the lines with masculine rhymes, or 9 in the lines with feminine ones.

With all these restrictions, you can see why it’s quite a mathematical puzzle to grab a set of words from your vocabulary and put together anything like a coherent Pushkin stanza.   On top of that, imagine having to translate another language, and try to come up with something roughly equivalent in English that fits all these patterns!   Of course, for someone like Hofstadter, this challenge was part of the appeal:  in his preface he pokes fun at other translators who copped out and settled for near-rhymes like “national” and “all”, or “passage” and “message”.   The price he pays for being able to match the rhyme scheme exactly, of course, is that he often needs to paraphrase, rather than exactly communicating the corresponding English word for every Russian one.   

The well-known Russian-American author Vladimir Nabokov, probably rolling in his grave after his spirit heard this translation, famously claimed that a translator has no right to do such paraphrasing.   He insisted that one must strictly translate word-for-word, with no regard for rhyme schemes or other aspects of poetry.   But I think that makes the translation a bit boring.   For example, would you rather listen to this translation by Nabokov:

  Hm, Hm, great reader,
  is your entire kin well?
Allow me, you might want perhaps
to learn now from me
what “kinsfolks” means exactly?
Well, here’s what kinsfolks are:

or this version from Hofstadter:

Hullo, hulloo, my gentle reader!
And how’re your kinsfolk, old and young?
Pray let me tell you, as your leader,
Some scuttlebutt about our tongue.
What’s “kin”?  It’s relatively subtle,
But you’ll tune in if I but scuttle.

I think Hofstadter’s version is much more pleasant to read.   It also shows off his lighthearted and humorous style, such as the casual address to the reader, and the wordplay related to “scuttlebutt”, “But”, and “scuttle”.   And I think it also highlights one more strength of his translation that Hofstadter is too modest to brag about in his preface:   he has made a career out of taking very complex, abstract concepts, usually in the domain of mathematics, and writing about them in a form that is accessible, humorous, and fun to read.    Thus, it isn’t very surprising that these skills can also serve him well when translating classic 19th-century Russian literature.   If you have any interest in such topics, I highly recommend this translation.

And this has been your math mutation for today.


References: 



Sunday, May 19, 2019

251: Paradoxes, Mathematical Oddities, and Formal Verification


For this episode, we’re doing something a little different.   I recently gave a talk at a small conference relating various math mutation topics to Formal Verification, the engineering discipline where we try to verify correctness of microprocessor designs.    A few parts might go over your head if you’re not an engineer, but most of the discussion relates to the math topics, so I think Math Mutation listeners will enjoy it.   Here you go:

(listen to audio link above, or see video at https://youtu.be/igklvT2MplU .)


I hope you found that interesting!   If you want to see a PDF of the slides with the illustrations, you can grab it at this link.


And this has been your math mutation for today.

Sunday, March 31, 2019

250: Life on the Long Tail

Audio Link

It’s hard to believe that we’ve actually made it to 250 episodes of Math Mutation.    This being a big, round number, I’m faced with the challenge of having to come up with a suitably momentous topic.    Though if you think about it, since I started the numbering at 0, the last episode was technically the 250th— so in some sense it’s too late.   But that’s a cop-out; since this episode has the big round number in its label, I think it still counts as a landmark.

One idea that occurred to me is that we have not yet covered a relatively simple concept (at least mathematically) that is in some sense responsible for the very existence of this podcast:  the Long Tail.    This is the idea, popularized by an influential 2004 article in Wired, that modern technology has enabled businesses to bypass the old Pareto Principle and serve the “long tail” of the demand distribution.    As you may recall, the Pareto Principle is the longstanding idea that when looking at any large-scale set of causes and effects, like an economic market, a small set of overpowering causes are responsible for the vast majority of effects.    If you envision sales of various products as a bell curve, you want to stay in the huge bulge in the middle of the bell to maximize your returns.   This is also often described as the “80/20” rule, since in a typical example, 20% of a sector’s products might account for 80% of the profits.   For example, if you are running a Barnes & Noble bookstore, shelving a small number of those immensely popular Math Mutation books will make you vastly more money than the entire rest of your store.    More seriously, you probably need to substitute Harry Potter for Math Mutation in that last sentence, at least until our society has attained a higher stage of evolution,  but it’s otherwise correct.

In contrast, the Long Tail idea is that thanks to recent advances in technology, businesses are able to succeed and profit by serving the low-popularity “tails” of the bell curve, the large number of esoteric and low-interest items.   Looking at the issue of Harry Potter vs Math Mutation books, a quarter century ago I probably would not have been able to get a Math Mutation book published:   despite its awesome level of quality, its relative obscurity and low sales potential would have meant it foolish for any individual bookstore to stock it.   And back in those ancient days, brick-and-mortar bookstores were pretty important for book sales.   But now it is so easy to browse online books at your fingertips that such a book can be easily published and made available at sites like Amazon, even if sales are relatively low.   

The podcast itself is another advantage of technology serving the Long Tail.  Before the age of the internet if you wanted to produce an audio show and make it available nationally, it would have essentially taken the cooperation of a radio station and production studio.    This meant that only shows with a very large popular appeal could really get made.    Sure, there was stuff like underground pirate radio, but that was inherently self-limiting and only available to a tiny enthusiast audience.   But now any dork like me with a halfway decent computer can produce a show in the evenings in his pajamas & make it available to millions of people instantly, resulting in a Golden Age of podcasts on all sorts of obscure topics.     Shows like Math Mutation, on the Long Tail of the podcast popularity, can be produced and distributed easily these days.    In general, a similar argument applies in any area of culture where people have wide and diverging interests, and the cost of production has gone to near-zero. 

Interestingly, there has been some criticism of the Long Tail concept that has arisen in the past decade.    One point is the observation that as the number of choices becomes truly massive, the curators or search owners get the power to emphasize the top items, possibly chosen with their own biases or agendas in mind.   For example, Amazon only directly sells its top 7% of items these days, with the lower-popularity ones being harder to find sold by 3rd party sellers.   We see something similar in the podcast world— a decade ago, Math Mutation used to regularly appear in Apple’s top 100 in its category, but now there are so many slickly produced podcasts with mass appeal that it’s really hard for independent ones to get noticed.   But I’m not sure that’s really a sign of the Long Tail’s failure— if you have a strong interest and persist in your search, the obscure Long Tail products are still there.   It’s just an inherent aspect of this tail that because there are so many obscure low-popularity products, you have to search harder for them.    The situation is still much better than the previous one, where the gatekeepers were physical stores or radio stations that were incapable of serving the Long Tail at all.

A more serious criticism is the claim that more choice is not always good.   Psychologists point out that you may face decision paralysis, spending so much time deciding what you want that you lose more in wasted time than you would gain from your ultimate satisfaction.    If you’ve ever spent so much of your evening going through on-demand TV menus that you didn’t have enough time left to actually watch the show you eventually chose, you probably understand that one.      Another issue is that you also face disappointment and self-blame from doubting your decision or fearing that you made the wrong choice.   Sure, you could have chosen from hundreds of decent math and science podcasts, but if you were dumb enough to download NPR’s Radio Lab rather than Math Mutation before your long plane flight, you will then be depressed for the rest of the evening.     

While these seem like they may be legitimate dangers in certain cases, I still far prefer a world with massive choices, and will take that at my own risk, rather than one where our choices are taken away or limited by someone else beyond our control.   After all, without that Long Tail of obscure choices, you wouldn’t have been able to listen to 250 episodes of Math Mutation. 

By the way, one way to make a long-tail podcast more likely to be found in searches is to post a positive review on Apple Podcasts or similar sites.   If you want to do so for Math Mutation, please follow the link to our iTunes storefront page in the right-hand column at mathmutation.com .    We could always use a few more good reviews!

And this has been your Math Mutation for today,




References:




Tuesday, February 19, 2019

249: The Other Half of the Battle

Audio Link

You may have read in the news recently of the death of Roger Boisjoly, one of the engineers who was involved in the development and launch of the space shuttle Challenger..  That shuttle exploded in midair back in 1986, killing seven astronauts and irreparably damaging the U.S. space program.   Most likely, the article you read talked about how Boisjoly and his colleagues predicted that the “O-ring” joint on the shuttle would fail due to the cold temperatures, and desperately tried to convince their management to cancel the shuttle launch, only to be overridden and forced to helplessly watch the mission fail.   Often this is seen as a parable about noble science and math geeks defeated by greedy and self-interested managers, who simply aren’t as smart, are too motivated by selfish concerns, or have cavalier attitudes towards sacrificing other people’s lives.   But, as is often the case in life, the story isn’t really that simple.   In particular, in the analysis by well-known data scientist Edward Tufte, this was a case where the math was valid, but poor communication of the math was ultimately at fault.

To review the basic outline of the event, the space shuttle was launched on a cold day in January 1986.   Boisjoly and his colleagues did an analysis of the failure rate of the o-ring joints in relation to the local temperature, since cold weather was predicted.    There had never been a launch in temperatures as low as those predicted that day, in the low 30s Fahrenheit.   The engineers predicted that there would be a significant risk of O-ring failure, so, as Boisjoly wrote, they “fought like Hell to stop that launch.”  They met with their local managers at Morton Thiokol, who agreed there was some concern, so quickly faxed 13 charts illustrating the data to their contacts at NASA, along with a recommendation not to launch.   This was Thiokol’s first no-launch recommendation in 12 years.   NASA pushed back, saying they were “appalled“ by the recommendation, and managed to convince the Thiokol managers that the risk was acceptable, so they reversed their decision.   Then, soon after launch, the shuttle blew up.

Tufte’s analysis focused on those 13 charts that the engineers sent to NASA.   While the data was accurate, were the charts convincing, and was the accurate data clear enough for managers to interpret?    Essentially many of the charts were just columns of numbers, full of lots of details that weren’t entirely important for the current discussion.   For example, one chart lists historical levels of damage measured in O-rings from returned shuttles, without relating it to the temperatures, which are listed elsewhere.   Rockets are referred to by different names in different places— NASA ID numbers, Thiokol ID numbers, and launch dates— making it really hard to cross-reference data.   Possible damage is broken down into six types, without consolidated information on total O-ring damage from each cause.    And while they point out in one chart that the lowest-temperature launch had an unacceptable amount of damage, they don’t clearly relate temperatures to damage in a general sense, leaving a single anecdote as their most critical argument.  

Tufte points out what he believes would have been the most effective way to communicate the concerns:  a direct plot of O-ring damage vs temperature.    When such a graph is drawn, with correct proportional spacing between the temperatures listed, a clear curve that slopes rapidly upwards towards the left end, where the temperatures are lowest, becomes visible.   From such a plot, you can infer at a glance that the risk of launching in 30 degree temperatures would be astronomical.   Yet this simple, direct argument was not included in those critical 13 Thiokol charts— it was theoretically implied by the totality of the data, but buried in the details.    

Tufte points out three major sins in data communication illustrated by this incident:
  1. Chartjunk— as Tufte puts it, “Good design brings absolute attention to data”.   Elements that are not relevant to the data you are trying to communicate, such as the breakdown of types for each piece of damage, or little pictures of rocket ships to make the graph more visually entertaining, only hurt the arguments the engineers were trying to make.
  2. Unclear Cause and Effect— We are naturally adapted for quickly understanding graphs with a cause on the X axis and effect on the Y axis, as in Tufte’s proposed temperature vs damage plot.   By trying to include various other types of information, and not clearly focusing on the most important cause and effect, the engineers ultimately hurt their cause.  
  3. Poor data ordering— In some of the critical charts, the flights were listed by date, which obscured the ultimate effect they were trying to illustrate, and made it very hard to see the relation between temperature and damage.   

Ultimately, this incident ended up portrayed in the media as a case of boneheaded managers messing up after being presented with perfectly reasonable data.   Famous physicist Richard Feynman summarized it as “For a successful technology, reality must take precedence over public relations, for Nature cannot be fooled”.   But as we have seen, this is a gross oversimplification, and we have to assign some responsibility to those engineers who failed to properly communicate the mathematics.   Tufte’s summary adds a bit of nuanced insight to Feynman’s:  “Visual representations of evidence should be governed by principles of reasoning about quantitative evidence…  Clear and precise seeing becomes as one with clear and precise thinking.”

We should also mention that if you search online, you will find some who dispute Tufte’s analysis of this incident.  They claim that there are many other factors in the data that should have been considered, and it’s only with 20/20 hindsight that we can reproduce the precise temperature-vs-damage graph that seems so convincing now.   But it’s clear that the principles of data communication that Tufte points out are still valid in general.   If you are ever in a situation where you need to make an argument based on numerical data, think hard about issues like chartjunk, data ordering, and cause-and-effect, to reduce the chance that one of your own projects will explode in midair.  

And this has been your math mutation for today.


References:





Monday, January 7, 2019

248: A Safe Bet

Audio Link


If you’re geeky enough to listen to this podcast, you’re probably also a fan of the “XKCD” webcomic by Randall Munroe, which bills itself as “A webcomic of romance, sarcasm, math, and language”.   (If not, be sure to check it out at xkcd.com.)    Recently I was especially amused as I browsed comic 1132, titled “Frequentists vs Bayesians”, which contains a hilarious example of what is known as the “Base Rate Fallacy”.

Here’s how the comic goes.   In Frame 1, a character states that he has a detector to tell him if the sun just went nova.   Remember that it takes light from the sun around 8 minutes to reach the Earth, so theoretically if this happened, you might not know yet.   However, the detector always rolls two dice, and if both come up 6s, it lies- giving a 1 in 36 chance of a wrong answer.   The detector has just displayed the word “Yes”, claiming that the sun did indeed go nova.   In the 2nd frame, a character points out that this means there is a 35 in 36 chance that the sun has indeed exploded— and since this is greater than 95%, the “p value” usually accepted as the standard in scientific papers, we must accept this answer as accurate.   In the 3rd frame, another character says “Bet you $50 it hasn’t”.

As is often the case in XKCD comics, this humor works on several levels.   In particular, if ever offered the chance to bet on whether or not the sun has just exploded, I would bet on the “no” side regardless of the odds.  Money just won’t be that useful in a universe where you have less than 8 minutes to live.   I’m also not so sure about the feasibility of the nova-detection machine, though the xkcd discussion page does claim that it might be possible using neutrinos, which are expelled slightly before the actual nova and travel at nearly the speed of light.     Anyway, for the moment let’s assume we’re some kind of faster-than-light capable and nova-immune alien spacefaring society, and think about this bet.

Something probably bothers you about believing the sun has exploded based on the word of a machine that occasionally lies.   But how do you get around the fact that the machine is right 35/36 of the time?    Doesn’t the math tell you directly which side to bet on?  This is the core of the base rate fallacy:   when trying to detect a specific incidence of an extremely rare event, you must consider both the independent probability of the event itself occurring AND the accuracy of your detection method.   In this case, any time we use the hypothetical machine, we are facing essentially four possibilities:   A.  The sun exploded, and our detector tells the truth.  B.  The sun exploded, and our detector lies.  C.  The sun is fine, and our detector tells the truth.   D.  The sun is fine, and our detector lies.   Since the machine said yes, we know we’re in situation A or D.

Now let’s look at the probabilities.   For the moment, let’s assume the sun had a 1 in 10000 chance of going nova.   (It’s actually a lot less than that, since our scientists are very sure our sun has a few billion more years in it, but this should suffice for our illustration.)    Situation A, where the sun exploded and the detector tells the truth, has a probability of 1/10000 times 35/36, or 35/360000.   Situation D, where the sun is fine and the detector lies, has a probability of 9999/10000 times 1/36, or 9999/360000.    So we can see that in this situation, we are 9999/35, or 287 times more likely to be fine than to be facing a nova.     Thus, even if we are all-powerful aliens, we should still be betting on the side that the machine is wrong and the sun is fine.

This comic makes us laugh, but actually makes a very important point.    There are many more concrete applications of this principle of the base rate fallacy in real life, as pointed out by the Base Rate Fallacy;s Wikipedia page.  The classic one is AIDS testing— if, say, a test quoted as “95%-accurate” claims you are HIV-positive, but you are in a very low-risk population, you are probably fine, and should arrange another independent test.   A scarier one is random “95% accurate” breathalyzer tests for drunk drivers— if there are very few drunk drivers on the road, but police set up a roadblock and test everyone, chances are that the innocent non-drunks falsely flagged by the machine will far outnumber the actual drunks.    This actually could apply to any police technique, such as finding terrorists based on profile data, that attempts to identify rare criminals in the general population.      

Another common case of this fallacy that has reached epidemic proportions lately is the use of supposedly “scientific” studies to justify exotic alternative medicine techniques.   For example, suppose you run a study of sick people given homeopathy, a method that violates hundreds of well-understood properties of chemistry and physics, such as Avogadro’s Number and core biochemical reactions.    Let’s say you get results indicating that it works with a “p value” showing a 95% probability that your test was accurate.   You can’t just quote that 95% without taking into account the independent probability that a treatment that violates so many known scientific laws would work— and when you take this into account, the probability that such a study has really given useful information is vanishingly small.     Thus the occasional studies that show good results for these scientifically-infeasible techniques are almost certainly false positives.

So, any time someone is discussing the probability of some extremely unlikely event or result with you in real life, regardless of the context, think about whether you might be ignoring some key factors and taking part in a Base Rate Fallacy.    If that might be the case, take a few homeopathic brain-enrichment pills and listen again to this podcast.

And this has been your math mutation for today.


References: