Archive for December 2010

More Nerdy Jokes

* * *

A note posted on the door of the tech-support department:

“Theory — you know everything, but nothing works. Practice — everything works, but nobody knows why. In our department we merge theory with practice: nothing works and nobody knows why.

* * *

A plus is two minuses at each others’ throats.

Share:Facebooktwitterredditpinterestlinkedinmail

PIE

I was teaching my students PIE, the Principle of Inclusion and Exclusion. This was the last lesson of 2010 and it seemed natural to have a party and bring some pie. It appears that the school has a new rule. If I want to bring any food to class, I need to submit a request that includes all food ingredients. The administrators send it to the parents asking them to sign a permission slip and then, if I receive all the slips back in time, I can bring pie to school. We had to study PIE without pie.

Our most important task as parents and teachers is to teach kids to make their own decisions. They are in high school; they know by now about their own allergies and diets; they should be able to avoid foods that might do them harm. I understand why schools create such rules, but we are treating the students like small children. We can’t protect them forever; they need to learn to protect themselves.

Next semester, we will study the mathematics of fair division. I will have to teach them how to cut a cake without a cake.

Share:Facebooktwitterredditpinterestlinkedinmail

Adjustments to Medical Bills

I once wrote a story about a mistake that my medical insurance CIGNA made. They had a typo in the year of the end date of my insurance coverage in their system. As a result of this error, they mistakenly thought they had paid my doctors after my insurance had expired and tried to get their money back. While I was trying to correct all this mess, an interesting thing happened.

To help me explain, check out the following portion of my bill. (If it looks a bit funny, it’s because I cut out some details including the doctor’s name).

My Medical Bill

On the bill you can see that I had a mammography for which I was charged $493.00, but CIGNA paid only $295.80. The remaining $197.20 was removed from the bill as an adjustment, as frequently happens because of certain agreements between doctors and insurance companies. A year later when CIGNA made their mistake, they requested that the payment be returned. You can see on the bill that once the payment was reversed, my doctors reversed the adjustment too.

When CIGNA fixed the typo, they repaid the doctors, but the adjustment stayed on the bill, which the doctors then wanted me to pay. And that was only one of many such bills. It took me a year of phone calls to get the adjustments taken off, but this is not what I am writing about today.

If not for this mistake, I would have never seen these bills and the revealing information on the different amounts doctors charge to different parties, and how much they really expect to receive. As you can see my doctors wanted 67% more for my mammogram than they later agreed to.

The difference in numbers for my blood test was even more impressive. I was charged $173.00, and the insurance company paid $30.28 — almost six times less.

If I ever need a doctor and I don’t have insurance, I will take these bills with me to support my request for a discount. I do not mind if you use this article for the same purpose.

Share:Facebooktwitterredditpinterestlinkedinmail

Math, Love and Immortality

Ed FrenkelI met Ed (Edik) Frenkel 20 years ago at Harvard when he was a brilliant math student of my now ex-husband, and a handsome young man. Now, at 42, he is a math professor at Berkeley and he is even hotter. He made a bizarre move for a mathematician: he produced and starred in an erotic short movie, Rites of Love and Math. If he wants to be known as the sexiest male mathematician alive, he just might get the title.

The movie created a controversy when Mathematical Sciences Research Institute (MSRI) withdrew its sponsorship for the first screening after a lot of objections based on the trailer. My interest was piqued by a painting that dominated the visual of the trailer’s erotica scene. The black and white amateur painting is of the integral sign with Russian letters stylized as math symbols that spell the word “Truth”. In addition, the name of the woman in the movie, Mariko, means “truth” in Japanese. Though it felt pretentious, I was hoping that the movie would be symbolic. When I heard that the actors do not talk in the movie, my expectations of symbolism grew. I love movies that are open to interpretation. So I bought the movie, watched it and wrote the following review. Before getting to the review itself I would like to thank Ed Frenkel for sending me the photos and giving me permission to use them in my frank assessment of his work.

Here is the plot:

A Mathematician, hoping to serve humanity, discovers a formula of Love. Bad guys find an evil way to use the formula to destroy humanity and are hunting for the Mathematician, who is hiding in his lover Mariko’s home. The Mathematician fears for his own life. Although it would make sense to destroy all the papers with the formula, the Mathematician loves his formula even more than his lover and himself. He wants to preserve the formula and tattoos it on her body with her consent.

There is much about the film that I like, including the slow pace and the visuals, with their minimalistic background and palette of black, white and red. The camera work is superb.

I welcomed the idea of a Love formula, because mathematics is ready to broaden the scope of its models, including venturing into love. Of course, some mathematical models of relationships already exist.

Truth

It’s great that the mathematician is portrayed against the stereotype: he’s neither introverted nor asexual. Unfortunately, the movie plays into other stereotypes of male mathematicians — being creepy and demanding sacrifices from their wives in the name of mathematics. As I mentioned, I was looking forward to the movie, hoping that it would encourage the imagination of viewers in their interpretations. To my disappointment, every scene in the movie is preceded by text that describes the plot, removing any flexibility of interpretation. Besides that, the emotions portrayed didn’t quite match the written plot, in no small part because Ed Frenkel is not a good actor.

The idea of preserving a formula by tattooing it on someone is beyond strange. He could have used a safe-deposit box. Or put the formula in an envelope and given it to the lover to keep, or just encrypted it, etc. With narcissistic lack of consciousness, the Mathematician seems unaware of the implications of his action of imprinting this dangerous secret on Mariko. She can never go swimming, or go to the gym, or be intimate with anyone else. Moreover, if the bad guys discover that Mariko is the Mathematician’s lover, her life will be in grave danger. Not to mention that tattooing is painful.

Something that could have been interesting and watchable in a historic movie, in this contemporary movie seems pointlessly cruel, dehumanizing and senseless.

I know for sure that Ed Frenkel is not stupid, so what are his reasons for constructing the plot in this way? Before investigating his reasons, I have a mathematical complaint about the movie. Every mathematician and teacher knows that when asserting a formula you need to indicate its interpretation: what its symbols refer to in the real world. For example, suppose I tell you my own great Formula of Love: Cn = (2n)!/(n+1)!n!. You may recognize Cn as the Catalan numbers, but what does this have to do with Love? To give the formula meaning I need to tell you that Cn is the number of ways you can seat n loving couples at a round table with 2n chairs, so that each couple can join hands (assuming the arms are long enough to reach across the table) without any two pairs of arms crossing. Assigning an interpretation makes the Catalan numbers part of the world’s growing body of romantic research.

Writing a formula without mentioning what the variables mean fails to preserve it for the future. Ed Frenkel knows that. Wait a minute. The formula in the movie is actually not the Formula of Love, but a real formula from Ed’s paper on instantons. It’s right there, formula 5.7 on page 74. Every variable is explained in the paper. Ah-ha! So his movie isn’t actually about art, but rather about Ed’s formula. Indeed, there is no real Formula of Love. In such situations in other movies, they have simply shown fragments of a formula. However, in Rites of Love and Math, Frenkel’s formula — which has nothing to do with Love — is shot in full view, zooming in slowly.

The Formula

The movie is a commercial. Ed is using our fascination with sex to popularize his formula, and using his formula and his scientific standing to advertise his body.

I was so disappointed that the default interpretation of the movie was imposed on me by those pre-scene texts, that I decided to watch the movie for a second time, trying to ignore the text, hoping to find some new meaning.

If you decide to see the movie, you’ll probably come up with your own interpretation of the plot. I actually came up with several. I had a funny one and an allegorical one, but the most interesting task for me was to try create an interpretation matching the emotions portrayed:

Mariko knows that something is wrong in her sex life with the Mathematician. But she still loves him and writes him a love letter. The Mathematician comes to Mariko’s place. He is distant and cold. They cuddle. He explains to her that sex doesn’t bring him pleasure anymore and that moreover, he can’t even perform. He tells her that the only thing that brings him joy is mathematics and suggests that his sexual dysfunction and lack of pleasure will be fixed if they tattoo his favorite formula on her body. She agrees, but first they decide to give sex a last try. They try real hard. But he can’t relax and he doesn’t enjoy it, so she agrees to the tattoo. He does get excited during the tattooing process itself, but once he finishes his whole formula, he is no longer turned on. Mariko’s suffering has been in vain.

Share:Facebooktwitterredditpinterestlinkedinmail

Lida Goncharova — The First Gold IMO Girl

LidaJanet Mertz wrote several papers about the gender gap in mathematics. One of her research ideas was to find girls who went to the International Math Olympiad (IMO) and compare their fate to that of their teammates with a similar score. She asked me to find Soviet and Russian IMO girls. All my life I had heard about Lida Goncharova, the first girl on a Soviet team, and the first girl in the world who took a gold medal, but I had never dared to reach out to her. A little push by Janet Mertz was enough for me to find Lida’s phone number in Moscow and call her.

My conversation with Lida Goncharova

Lida

Lida got interested in mathematics when she was five years old. Luckily, many of her relatives were mathematicians and she started bugging them for math puzzles.

Her involvement with math was interrupted by the death of her parents — her mother when she was seven, and her father when she was nine. She ended up living with her sister, but felt very lonely.

After several years of personal turmoil, she renewed her pursuit of mathematics. Lida started discussing math with her mother’s first husband. She joined a math circle which was run at Moscow State University. When she was 13 she went to a summer camp and found a mentor there to study trigonometry. Eventually she ended up at School Number 425, one of the first schools in Moscow that opened for children gifted in math.

At the end of high school she went to the IMO as part of the Soviet team and won a gold medal there. After that she enrolled in the most prestigious Soviet institute for the study of math — Moscow State University (MSU).

Half of her high school classmates went to MSU, including her high school sweetheart Alexander Geronimus. Lida married Alexander when she was a sophomore and they had their first son in her fourth year of undergraduate school.

Meanwhile, she wasn’t doing as well in her studies as she had hoped. Lida was very fast to pick up math ideas during conversations, but she had difficulty reading books. As ideas were becoming more complicated and involved, this became a problem. She started feeling that she was falling behind her friends. When her friends gathered together to discuss mathematics she couldn’t understand everything. She wanted to ask questions, but was too shy. Plus, she didn’t want to impose on them. She made a decision to be silent. As a result she started ignoring the conversations of others and became discouraged as she fell behind.

She had her second child at the beginning of graduate school, where she studied under the supervision of Dmitry Fuchs. Lida was already losing her self-esteem and so she chose a self-contained problem that didn’t require a lot of outside knowledge. The solution involved some combinatorial methods, but Lida didn’t quite understand the big picture and the problem’s goal.

I contacted Dmitry Fuchs and asked him about Lida’s thesis. He told me that Lida’s main result is extremely important and widely cited. It is called Goncharova’s theorem.

Meanwhile, her husband finished his PhD in math and secured a great job in an academic institution. They had started as peers, but her work was interrupted by having their children. Lida finished her PhD a couple of years after her husband and got a very boring job as an algorithm designer. She even wrote some papers at the job, but she was not much interested. She continued her attempts to do mathematics and continued asking everyone for problems, but it didn’t go anywhere. Her friends were not very interested in her calculations and after the birth of her third child she began to lose hope in her research.

When Lida and her husband entered graduate school they became religious. Ten years later, Alexander decided to pursue the Russian Orthodox religion as a career and got a parish in 600 km from Moscow. They didn’t want to move their children away from Moscow, with its educational and cultural opportunities. So they started living in two places with long commutes. This didn’t help her math either.

Eight years after the third son, the fourth son was born. Although Lida sporadically continued her calculations, she still didn’t talk about them to anyone.

When the older children went to high school, Lida enjoyed solving their math problems tremendously. In 1990 perestroika started and Lida lost her job. She got an offer to create a private school and teach there. By this time she had had two more children, a son and a daughter. Lida continued working for the private school until her six children grew out of it. Lida enjoyed teaching and inventing methods to teach mathematics. The school ended in 2004. But she continues working with kids sharing with them her joy of mathematics.

Lida believes that she has had an extremely lucky life in many ways. The only exception was her unsuccessful math career. She can’t live without math, and will continue working with kids, solving fun problems and doing her private research.

When I first called her and said I wanted to talk about her and math, she told me: —There is nothing to talk about. I stopped doing math after my PhD. Almost.— That —almost— kept me asking questions.

Lida’s teammates

Lida

Janet Mertz was considering a serious research project comparing the fates of IMO medal girls with the fates of their teammates, to see whether gender plays a role later. However, due to the language and cultural differences and the fact that most of the girls changed their last name, it was difficult to locate them. So Mertz put this research project on hold.

She had asked me to find and contact the Russian women and I was so fascinated with Lida’s story that I decided to write it up in this article. And because the research is on hold, I decided to include the fates of Lida’s teammates.

Lida Goncharova got her gold medal in the 1962 IMO with 42 points and was ranked third. The teammate with the closest score was Joseph Bernstein with another gold medal and 46 points. I don’t even have to check Wikipedia to tell you about Joseph, as I was once married to him. He used to be a professor at Harvard University and is now a professor at Tel-Aviv University. He is a member of the Israel Academy of Sciences and Humanities and the United States National Academy of Sciences. He achieved a lot and is greatly respected by his peers.

Joseph Bernstein might not be the best person to compare Lida to as he had a perfect score. Some might argue that a perfect score indicates that he might have done better if the problems had been more difficult.

The two Soviet teammates whose scores were the closest to that of Lida, but below her, were Alexey Potepun with 37 points and Grigory Margulis with 36 points.

Alexei Potepun got a PhD in mathematics and is now a professor at Saint-Petersburg University. He has published eleven papers.

Next to Alexey Potepun is Grigory Margulis, who is a professor at Yale and was awarded the Fields Medal and the Wolf Prize. He is a member of the U.S. National Academy of Sciences.

You might notice that the two people who moved to the US are much more famous than those who stayed in Russia. You might say that moving to the US is a better predictor of success than gender. Sure, living in a free country helps, but Margulis got his Fields medal while he was in the USSR. And Bernstein invented his famous D-Modules while in Russia also.

My conversation with Lida was personally inspiring. I loved the tone of her voice when she talked about mathematics. There were many elements that prevented her from having the mathematical career she might have had: the untimely death of her parents, her shyness, raising six children, many years of long commutes. When we look at the achievements of her closest teammates, we can’t help but wonder what kind of mathematics we lost.

This conversation was very encouraging for me. I felt there were similarities between Lida and myself in more ways than I expected. What we share most of all is a love for mathematics. I could hear that in her voice.

Share:Facebooktwitterredditpinterestlinkedinmail

Problem Design for Multiple Choice Questions

I gave my students a problem from the 2002 AMC 10-A:

Tina randomly selects two distinct numbers from the set {1, 2, 3, 4, 5}, and Sergio randomly selects a number from the set {1, 2, …, 10}. The probability that Sergio’s number is larger than the sum of the two numbers chosen by Tina is: (A) 2/5, (B) 9/20, (C) 1/2, (D) 11/20, (E) 24/25.

Here is a solution that some of my students suggested:

On average Tina gets 6. The probability that Sergio gets more than 6 is 2/5.

This is a flawed solution with the right answer. Time and again I meet a problem at a competition where incorrect reasoning produces the right answer and is much faster, putting students who understand the problem at a disadvantage. This is a design flaw. The designers of multiple-choice problems should anticipate mistaken solutions such as the one above. A good designer would create a problem such that a mistaken solution leads to a wrong answer — one which has been included in the list of choices. Thus, a wrong solution would be punished rather than rewarded.

Readers: here are three challenges. First, to ponder what is the right solution. Second, to change parameters slightly so that the solution above doesn’t work. And lastly, the most interesting challenge is to explain why the solution above yielded the correct result.

Share:Facebooktwitterredditpinterestlinkedinmail

Blindfolded Charades

This is a version of the standard charades game that my son, Sergei Bernstein, invented.

Unlike in regular charades, the person who acts out the phrase doesn’t know what the phrase is and has to guess it. The viewers on the other hand, know the phrase but they are not allowed to talk.

So the actor is blindfolded and the viewers are not just watching; they are actively moving the actor and his/her body parts around to communicate the phrase. For example, if the actor is on the right track, since the viewers can’t say, “Yes, good!”, they might communicate it by nodding the actor’s head.

Sounds like fun, especially for people who enjoy touching and being touched.

Share:Facebooktwitterredditpinterestlinkedinmail

Sparsity and Computation

Once again I am one of the organizers of the Women and Math Program at the Institute for Advanced Study in Princeton, May 16-27, 2011. It will be devoted to an exciting modern subject: Sparsity and Computation.

In case you are wondering about the meaning of the picture on the program’s poster (which I reproduce below), let us explain.

WaM 2011 Poster Picture

The left image is the original picture of Fuld Hall, the main building on the IAS campus. The middle image is a corrupted version, in which you barely see anything. The right image is a striking example of how much of the image can be reconstructed from the corrupted image using clever algorithms.

Female undergraduates, graduates and postdocs are welcome to apply to the program. You will learn exactly how the corrupted image was recovered and much more. The application deadline is February 20, 2011.

Eugene Brevdo generated the pictures for our poster and agreed to write a piece for my blog explaining how it works. I am glad that he draws parallels to food, as the IAS cafeteria is one of the best around.

by Eugene Brevdo

The three images you are looking at are composed of pixels. Each pixel is represented by three integers corresponding to red, green, and blue. The values of each integer range between 0 and 255.

The image of Fuld hall has been corrupted: some pixels have been replaced with all 0s, and are therefore black; this means the pixel was not “observed”. In this corrupted version, 85% of the pixel values were not observed. Other pixels have been modified to various degrees by stationary Gaussian noise (i.e. independent random noise). For the 15% observed pixel values, the PSNR is 6.5 db. As you can see, this is a badly corrupted image!

The really interesting image is the one on the right. It is a “denoised” and “inpainted” version of the center image. That means the pixels that were missing were filled in and the observed pixel integer values were re-estimated. The algorithm that performed this task, with the longwinded name “Nonparametric Bayesian Dictionary Learning,” had no prior knowledge about what “images should look like”. In that sense, it’s similar to popular wavelet-based denoising techniques: it does not need a prior database of images to correct a new one. It “learns” what parts of the image should look like from the original image, and fills them in.

Here’s a rough sketch of how it works. The idea is to use a new technique in probability theory — the idea that a a patch, e.g. a contiguous subset of pixels, of an image is composed of a sparse set of basic texture atoms (from the “Dictionary”). Unfortunately for us, the number of atoms and the atoms themselves are unknowns and need to be estimated (the “Nonparametric Learning” part). In a way, the main idea here is very similar to Wavelet-based estimation, because while Wavelets form a fixed dictionary, a patch from most natural images is composed of only a few Wavelet atoms; and Wavelet denoising is based on this idea.

We make two assumptions that allow us to simplify and solve this problem, which is unwieldy-sounding and vague when the texture atoms have to be estimated. First, there may be many atoms, but a single patch is a combination of only a sparse subset of them. Second, because each atom appears in part in many patches, even if we observe some noisily, once we know which atoms appear in which patches, we can invert and average together all of the patches associated with an atom to estimate it.

To explain and programmatically implement the full algorithm that solves this problem, probability theorists like to explain things in terms of going to a buffet. Here’s a very rough idea. There’s a buffet with a (possibly infinite) number of dishes. Each dish represents a texture atom. An image patch will come up to the buffet and, starting from the first dish, begins to flip a biased coin. If the coin lands on heads, the patch takes a random amount of food from the dish in front of it (the atom-patch weight), and then walks to the next dish. If the coin lands on tails, the patch skips that dish and instead just walks to the next. There it flips its coin with a different bias and repeats the process. The coins are biased so the patch only eats a few dishes (there are so many!). When all is said and done, however, the patch has eaten a random amount from a few dishes. Rephrased: the image patch is made from a weighted linear combination of basic atoms.

At the end of the day, all the patches eat their own home-cooked dessert that didn’t come from the buffet (noise), and some pass out from eating too much (missing pixels).

If we know how much of each dish (texture atom) each of the patches ate and the biases of the coins, we can estimate the dishes themselves — because we can see the noisy patches. Vice versa, if we know what the dishes (textures) are, and what the patches look like, we can estimate the biases of the coins and how much of a dish each patch ate.

At first we take completely random guesses about what the dishes look like and what the coins are, as well as how much each patch ate. But soon we start alternating guesses between what the dishes are, the coin biases, and the amounts that each patch ate. And each time we only update our estimate of one of these unknowns, on the assumption that our previous estimates for the others is the truth. This is called Gibbs sampling. By iterating our estimates, we can build up a pretty good estimate of all of the unknowns: the texture atoms, coin biases, and the atom-patch weights.

The image on the right is our best final guess, after iterating this game, as to what the patches look like after eating their dishes, but before eating dessert and/or passing out.

Share:Facebooktwitterredditpinterestlinkedinmail

Blindfolded Men Getting Together

I’ve heard many fun problems in which blindfolded parachutists are dropped somewhere and they need to meet up once they’re on the ground. They can’t shout or purposefully leave traces behind. They will recognize each other as soon as they bump into each other. Their goal is to get to the same assembly point. They can design their strategy in advance.

Here is the first problem in a series that gets increasingly difficult:

Two parachutists are dropped at different locations on a straight line at the same time. Both have an excellent sense of direction and a good geographical memory, so both know where they are at any moment with respect to their starting point on the line. What’s their strategy?

The strategy is that the first person stands still and the second one goes forward and back repeatedly, increasing the distance of each leg until they collide.

In the next variation, both are required to execute the same program, that is, if one stands still, then both stand still. To compensate for this increased difficulty, they are allowed to leave their parachutes anywhere. And both of them will recognize the other’s parachute if they bump into it.

In the third variation, the set-up is similar to the previous problem, but they are not allowed to change the direction of their movement. To their advantage, they know which way East is.

I recently heard a 2-D version from my son Sergei in which the parachutists are ghosts. That means that when they bump into each other they go through each other without even recognizing the fact that they met:

Several blindfolded men are sleeping at different locations on a plane. Each wakes up, not necessarily at the same time. At the moment of waking up, each of them receives the locations of all the others in relation to himself at that moment. They are not allowed to interact, nor will they receive any further information as time passes. They need to get together in one place. How can they do that, if they are allowed to decide on their strategy in advance?

They do not know where North is. So they can’t go to the person at the most Northern point. Also they do not know how locations correspond to people, so they can’t all go to where, say, Peter is. Let us consider the case of two men. Suppose they decide to go to the middle of the segment of two locations they receive when they awake. But they get different locations because they wake up at different times. Suppose the first person wakes up and goes to the middle. The fact that he walks while the other is sleeping, means that he changes the middle. So when the second person wakes up, his calculated middle is different from the one calculated by the first person. Consequently, they will never manage to meet. Hence, the solution should be different.

Actually Sergei gave me a more difficult problem:

Not only do they need to meet, but they need to stay together for a predefined finite time period.

Here is as bonus problem.

If there are three parachutists, it is possible to end up in a meeting place and stay there indefinitely. For four people it is often possible too.

Share:Facebooktwitterredditpinterestlinkedinmail

Darth Vader and Social Networks

Darth Maul killed Qui-Gon Jinn. Obi-Wan Kenobi killed Darth Maul. Palpatine killed Mace Windu. Darth Vader killed Obi-Wan Kenobi and Palpatine. I am mentally drawing the kill graph of Star Wars, where people are vertices and kills are edges. The graph is not very interesting. In movies where no one gets resurrected, the kill graph is a forest.

I’m interested in studying social networks in the movies and how they differ from social networks in real life. As we saw, the kill graph is not very exciting mathematically.

Now let’s try the acquaintance graph, where edges mark two people who know each other. Unfortunately, in the movies there are often many nameless people and we learn very little about their acquaintances. On the other hand, all the “nameful” people usually know each other, thus their acquaintance graph is a complete graph. The richest acquaintance graphs would be for epic movies like Star Wars, in which the events span two generations and many planets. As a result, there are characters who never meet each other. For example, Leia, Luke and Han from the original trilogy never meet people who died in the prequel, such as Anakin’s mother and Count Dooku.

But I think that the most intriguing type of filmic social network is the fight graph, where edges represent characters who fight each other. Usually such graphs are bipartite, reflecting the division between bad guys and good guys. When an epic film is more complex and has traitors, the fight graph is no longer bipartite. Consider Darth Vader who fought and killed a lot of good guys including Obi-Wan Kenobi as well as many bad guys including Count Dooku and the Emperor.

I would like to immortalize Darth Vader in mathematics. He did restore the balance to the Force. If there is a graph which is not bipartite and can become bipartite by removing one highly connected node, I would like to name such a node Darth Vader.

Share:Facebooktwitterredditpinterestlinkedinmail