A quick note on log odds

Probabilties are usually numbers that range from 0 to 1. However, the standard way of representing probabilities is not always optimal. However, there is another mapping of probability that goes from negative infinity to infinity. This system called "log odds" has a number of advantages. In the standard log odds approach, one maps the probability of an event x to the quantity log(x/(1-x)). Brian Lee and Jacob Sanders wrote a good summary (pdf) of this system which discusses its advantage and disadvantages. As they observe, use of log odds allows one to immediately see how something like the change in probability from 51% to 52% isn't that big whereas the change from 98% to 99% is a much larger change in the sense that the chance of the event not happening has now halved. Log odds helps makes this sort of intuition immediatelty obvious from the numbers. Brian and Jacob discuss the advantages and disadvantages of log odds in detail, and show how it is particularly useful for doing Bayesian updates. I strongly recommend reading their piece.

A brief note on non-transitive dice

I've talked before about non-transitive dice. We say that given a pair of dice X and Y, X beats Y if more than half the time when the pair is rolled X has a larger number face up than Y. It turns out one can construct dice A, B and C such that A beats B, B beats C, but C in fact beats A. This is a neat and weird property.

During a recent discussion I used non-transitive dice as an example of a counter-intuitive aspect of mathematics, I was pointed to an even weirder variant. Consider the following set of dice: A has sides (5,5,5,2,2,2), B has sides (4,4,4,4,4,1) and C has sides (6,3,3,3,3,3).

Here A beats B, B beats C and C beats A. But here's the really cool part: Let's say I roll two copies of A, two copies of B or two copies of C. Now things actually reverse! That is, a pair of Bs beats a pair of As and a pair of As beats a pair of Cs and a pair of Cs beats a pair of Bs.

This is a much more sensitive property than just non-transitive dice. Most sets of non-transitive dice will not have this property. We can also describe this sensitivity in a more rigorous fashion. Suppose we have a strictly increasing function f(x). That is, a function such that f(x) is greater than f(y) whenever x is greater than y. Now suppose we take a set of non-transitive dice and relable each value x with f(x). Then they will still be non-transitive. But, given a set of non-transitive, reversable dice, reversibility is not necessarily preserved by the f mapping. This reflects the much more sensitive nature of the reversible dice.

Here's a question I have so far been unable to answer: Is it possible to make a set of die which do an additional reversal? That is, is there a set of dices such rolling three copies the dice results in another reversal direction?

What is P ?= NP and why should you care?

After my last blog post, readers remarked that they had no idea what
"P ?= NP" was and that I had completely failed to explain what I was talking about. They are correct. This entry is to remedy that problem.

First an analogy: Suppose you have a jigsaw puzzle. Assembling the puzzle correctly is difficult. But, if someone has the puzzle completed, one can generally tell at a glance that the puzzle is correct. (This isn't strictly true if you are dealing with someone like me who as a little kid would sometimes shove the pieces to fit in where they didn't belong. If one does this to sections that depict sky and clouds, it can be quite hard to tell that it is wrong.) But it seems that it is very difficult to tell how to assemble a puzzle. Moreover, it isn't even clear if one has all the pieces of the puzzle until one is nearly done with the puzzle. It can be a very frustrating experience to be nearly done with a puzzle and then realize that pieces are missing. What if there were a way to tell just from looking at the jumbled pieces in the box if one had the all pieces? Whether P is equal to NP is essentially asking if this is possible. The general consensus among computer scientists is that P is not equal to NP which means that puzzle-solvers are out of luck.

Let's break this down further. P is the set of types of puzzles that can be essentially solved quickly. So for example, "Is a given integer even or odd?" is a problem that lies in P. Given an integer, one can just look at the leading digit and see if it is even or odd. (I'm assuming that our integers are written in base 10). Similarly, the problem "given integers a and b, does a divide b?" is in P,;all one needs to do is divide a into b and see if there is a remainder. But not everything is necessarily in P. For example, the question, "is a given integer composite?" is not obviously in P, since checking requires successive search for divisors.

But, there is a larger class of problems, NP, which are problems which, if they have an answer of "yes," one can quickly convince someone else of the answer if one has the right information. In this context, "is an integer composite?" is in NP, since if I know a non-trivial divisor of the integer, and I want to convince you that it is composite. I can just tell you that number and you can check yourself. To make this more concrete, if I gave you the number 1517 and asked you if it were prime or composite, you would have to do a lot of unpleasant arithmetic. But, if told you 1517 is 37 times 41, you'd be able to check this easily.

Now, it actually turns out that whether a number is prime composite can actually be checked quickly using something called the AKS algorithm . This result was a very big deal, proven by Manindra Agrawal and two other mathematicians in 2002 . I remember when this happened. When the result was announced, I was a high school student who was then at PROMYS, a summer math program at Boston University, and people were distributing and looking over copies of the preprint. The algorithm they used was straightforward, but proving that algorithm really did what was claimed required deeper mathematical results from the area known as sieve theory.

Let's try to make these notions of P and NP more mathematically rigorous. To do that, we need a rigorous notion of what it means to calculate quickly. We want the length of time it takes to run our algorithims to solve our problems to not grow very fast. When mathematicians want something that doesn't grow too quickly, they often look at polynomials (that is, functions like n^2, or n^3, or n^4 +10n +2, as opposed to say exponentials that look like 2^n or 3^n). So, we will define an algorithm to be quick if the amount of time it takes to run is bounded by a polynomial of the length of whatever we inputted. So ,for example, in our earlier case of looking at whether an integer is prime or composite, the length of the input would be the number of digits in the integer. Thus, Agrawal constructed an algorithm that ran would when given an integer always tell you if the integer was prime or composite. Agrawal showed that there is a constant K such that his algorithm terminates in at most at most Kn^12 steps, where n is the number of digits of of the number to be test.

Whether P = NP is one of the great unsolved problems of modern mathematics. P ?= NP is one the seven Clay Millenium Problems, each of which has a million dollar prize. Moreover, there are many practical applications. There are many practical problems which appear in some form to be in NP, but have no known quick algorithm to solve them. These include problems in protein folding, circuit design, and others areas.

Readers have likely also benefited more directly from practical issues related to this problem without even realizing it. I've discussed on this blog before the Diffie-Hellman algorithm. This is one example of many cryptographic systems that are used by modern computer networks, most often without users even realizing that they are being used. These all rest on certain problems being easy to solve if one has extra information, but very difficult otherwise. Thus, if P = NP, then all these algorithms will become insecure. This would be bad. Unfortunately, the converse does not follow: There is a common misconception that if P is not equal to NP, then modern encryption is actually safe. This doesn't follow. It turns out that claims that encryption works implies that P is not equal to NP, but the reverse doesn't follow. It is conceivable (although unlikely) that P and NP are distinct and encryption still collapses. But, figuring out whether P = NP would be a major step in understanding whether or not encryption is really safe.
Those worried about the encryption for their bank accounts can rest easy. Most experts in the field seem to think that P and NP are distinct. This means your encryption is secure. On the other hand, this also means that a lot of practical problems are genuinely tough. One can't have it both ways. Either one gets lots of helpful fast algorithms or one gets good encryption. Right now, it looks like one gets good encryption.

So, how close are we to actually answering if P = NP? This looks pretty far off right now. There are a few methods that look somewhat promising, but a lot of the best current results are results that essentially show that certain techniques cannot answer the question. So right now resolving the question looks pretty far off.

Gasarch P = NP Poll

A decade ago, Bill Gasarch conducted an informal poll asking computer scientists and mathematicians various questions related to whether or not P was equal to NP. He asked when people thought the problem would be resolved, which was it would be resolved, and what techniques they thought would be used. One thing that is striking about Gasarch's data is that a surprisingly large fraction of serious computer scientists seem to think that P = NP. Moreover, while Gasarch notes that some of those individuals explicitly said they were saying it for the sake of being contrary, a large fraction also were simply unwilling to guess which way it would be resolved.

Now, Gasarch is again conducting such a poll. I am noting this here, because he is accepting emails from not just computer scientists but individuals in general, although he wants people to note their academic background. Also, please note that he wants replies by email. Apparently some people have already failed to note this and have added them as comments to his announcement post.

My own opinion (which I will submit via email shortly), is that P != NP, and I'm about 95% confident in this regard. I assign low probability to the weirder possible results involving undecidability in ZFC. I have no idea when the problem will be resolved, and I have no idea what techniques will be used to resolve it, although the techniques used by both Mulmuley and Ryan Williams look interesting. Obviously, I'm not a computer scientist, so my opinions on these matters should be taken with a large dose of salt.

Gasarch's poll also has an open-ended question allowing one to pontificate on related issues. Unfortunately, I really don't have any strong opinion on any related issues other than something like "derandomization is nice, yay?" The obvious related question of whether P = BPP seems tough. A lot of people are convinced that this is the case, and there's been a lot of success in the last few years with derandomizing algorithms, but my impression is that there's very little in the way of general techniques of how to do this systematically.

I'm also curious what readers of this blog thing, so feel free to leave your speculations in the comments.

Planar Divisibility Graphs and The Bible

I've talked about graph theory here before in the context of Ramsey theory.

However, there are many other interesting graph theory problems.

A graph is said to be planar if one can draw it on a plane with none of the edges intersecting. So for example, K3, the graph formed by three vertices all of which connect to each other is planar, but the similar graph K5 formed by five vertices all of which connect is not planar.
We can also change our notion of graph by allowing our edges to have directions, and represent them with arrows rather than straight lines. Thus for example, if one wanted to use a graph to represent who knows the name of whom with a bunch of people, using a directed graph would be quite natural.

Over the last few days I have been thinking about divisibility graphs of sets. These graphs arise when one takes some set of positive integers and assigns each to a vertex then draws the corresponding arrows when one integer divides another. (So for example, if our set was was {1,2,4} then 1 would have arrows going to 2 and 4 and 2 would have an arrow going to 4). For convenience, I am ignoring the arrows that vertices would have going to themselves.
Now, assume one has a set of positive integers A and we know that corresponding divisibility graph is planar. What can we say about how large the set is. That is, if we let A(x) be the number of elements in A which are at most x, how fast does A(x) grow? It is not difficult to see that one can get A(x) to grow at least about as fast as x/log x. One does this by taking A to be the set of prime numbers. The resulting graph is certainly planar since it has no edges at all. Then the prime number theorem does the rest. With a small amount of tweaking, one can get this to grow at about 2x/log x since one can include all the numbers of the form 2p and still get a planar graph. I suspect that the actual best possible growth is on the order of x/log x but I'm not sure. One possible approach to making a large planar divisibility graph is to use the greedy algorithm. That is, throw 1 into the set and then go by induction on each integer, throwing in the next integer if it still allows a planar graph. If one call this set G, then the first number not in G is 18. It seems at first that G grows quickly, and G includes every prime number. But most large integers are in fact not in G, a result of the fact that most large integers have a lot of prime factors. For example, every multiple of 6 other than 6 and 12 is not in G.

Now, you may be thinking, "Josh, this is an interesting math problem, but the title mentioned the Bible. What does that have to do with anything?" The truth is that the connection is tenuous. The problem about planar divisibility graphs occurred to me when I was tutoring a professor's young kid in graph theory, and we discussed divisibility graphs. The professor's family is Orthodox, and so another graph we talked was to take different Biblical figures and make a graph representing who had met whom. The major graph had three large components, one corresponding to the patriarchal time period (with Abraham, Issac and Jacob as the most connected points), one to the time around the Exodus (with Moses at the center), and one at the early monarchy, with David, Samuel and Solomon as the main points. However, an issue came up. My young student wanted to add Eli, the high priest during most of the of Samuel to the graph. This raised an issue which neither he nor I knew the answer: Did Eli ever encounter David? The text does not mention such an event, but the chronology seems tentatively to allow such a meeting. I'm also unaware of any midrashim claiming that they met. I'm mentioning this here therefore for two reasons: One can any more knowledgeable readers point me to anything in the text itself which deals with this, or can any of my more midrashically inclined readers point me to any midrashim that address whether they met?

Abusing Statistics

A friend writing under a pseudonym has a new blog about the use and abuse of statistics in the media. He's a good writer. Since he came to statistics (and the mathy end of everything) somewhat late compared to most math and science bloggers, I expect that his take will be quite interesting. He will likely also do a good job explaining some of the relevant ideas to less mathematical people. The latest entry is on how not to conduct surveys. The entry is worth reading.

Multiplicative functions and almost division

A function f(n) with range in the integers is said to be multiplicative if f(ab)=f(a)f(b) whenever a and b are relatively prime. A function is said to be completely multiplicative if this applies for all a and b whether or not a and b are relatively prime. Some of my prior posts have discussed multiplicative functions (e.g. this post on Mersenne primes and perfect numbers). An important thing to note is that a multiplicative function is determined by its values at prime powers, while a completely multiplicative function is determined by its values at primes.

Let f and g be two functions from the positive integers to the integers. Let K(f,g)(x) be the number of n less than x such that f(n) does not divide g(n). We say that f almost always divides g if f(n) divides g(n) for almost all n if K(f,g)(x) = o(x) (or to put it another way, the set of exceptions has density zero). Obviously, almost divisibility is weaker than divisibility. Almost divisibility shares many of the properties of divisibility; it is a transitive relation. One important difference between divisibility and almost divisibility is that among positive functions, divisibility is an anti-symmetric relation (that is, if fg, and gf then f=g). This is not true for almost divisibility, but is true for almost divisibility if we restrict our attention to multiplicative functions.

Are there interesting examples of non-trivial almost divisibility where one doesn't have divisibility? Yes. Let σ(n) be the sum of the positive divisors of n, and let τ(n) be the number of positive divisors of n. Erdos showed that τ almost divides σ and showed through similar logic that τ almost divides the Euler φ function.

Why am I thinking about these functions? I noticed that some multiplicative functions divide a positive completely multiplicative function. Thus, for example φ divides the completely multiplicative f such that for any prime p, f(p)=p(p-1). However, other cases don't have such examples. It isn't too hard to show that there's no such completely multiplicative function for τ or σ. But, the situation changes drastically in the case of almost divisibility. We in fact have that for any function f from the natural number to the natural numbers, there is a completely multiplicative function g such that f almost divides g. We shall call such a g, a "completely multiplicative almost multiple" (or CMAM) Moreover, we can construct such a function explicitly.

Proposition: Let f(n) be a function from N to N, and let g(n) be the completely multiplicative function defined by g(p) = is the least common multiple of f(1),f(2),f(3)...f(2^p). Then g is a completely multiplicative almost multiple of f.

In order to prove this result, we need another notion, that of normal order. Often, to describe the behavior of a poorly behaved function, number theorists like to show that it asymptotic to a well behaved function in the sense that the limit of their ratios is 1. Thus, for example, the prime number theorem says that the poorly behaved function π(n) that counts the number of primes that are at most n is asymptotic to n/log n. But for many functions we care about this sort of statement is much too strong. Let ω(n) be the number of distinct prime divisors of n, and let Ω(n) be the total number of prime factors. Then these functions hit 1 infinitely often and so clearly are not asymptotic to any nice functions. However, ω and Ω possess a normal order, in the sense that for any ε > 0, we have that excepting a set of density 0, (1-ε) log log n < ω(n) < (1+ε) log log n and the same holds for Ω(n). (More refined estimates exist but we don't need them for these remarks.) An important heuristic that stems from this result is that most numbers look very close to square free in the sense that they have a lot of prime factors and very few of the prime factors occur more than once.

Now, to prove our result, we observe that excepting a set of density zero, we have Ω(n) < 2 log log n . So ignoring a set of density zero, the largest prime factor of n, call it p, is at least n^(1/(2 log log n)), and so f(n) appears as a term in g(p).

Obviously, for any f, the constructed CMAM grows very fast. However, this doesn't need to be the case, and it might be that in specific contexts one can substantially reduce this growth rate. So, this leaves me with three questions, one broad and two specific:

1) How much can we improve on reducing the growth rate of the CMAM for a function f? There are obvious steps to take in the construction but they still make it grow very quickly.

2) Let g(n) be a CMAM for σ. Does it follow that g(n) is not O(n^k) for any k? I strongly suspect this is true but don't see how to prove it.

3) One can through more careful work show that there is a CMAM for τ that is 0(x). What is the best possible growth rate for such a function?

While I've seen individual papers that have discussed specific functions being almost divisible by each other, I'm not aware any substantial work on their general structure. I don't know if this is due to my ignorance of the literature, the fault of almost divisibility being too weak a property to be interesting, or some other cause.

On rotations of spheres

Consider a sphere living in some number of dimensions. The sphere we are used to is the 2-sphere, denoted by S². Mathematicians call it this because even though it lives in 3-dimensions, it is itself a 2-dimensional object (in the sense that small sections of it look like the 2-dimensional plane). One can similarly talk about the n-sphere, which lives in n+1 dimensions. Thus for example, the 1-sphere, S¹, can be thought of all all points on a plane that are of distance one from the origin.

When one has a geometric object one of the most obvious things to do is to ask what rigid movements of the object will take it to itself. Thus, for example, for a sphere, a rotation about some axis through the sphere's center rigidly moves the sphere to itself.

Rotations seem simple, but they can be surprisingly tricky. For the 1-sphere if one does a rotation and then another rotation one is left with a rotation. This is an important and helpful property. It says essentially that rotations form what mathematicians call a subgroup of the group of all rigid motions. It turns out that this is still true for the 2-sphere, S² even when one uses different axises for the two rotation Now, you might find surprising the fact that for S³, the sphere of three dimensions living in four dimensions, this breaks down. The composition of rotations is not necessarily a rotation. In some sense the not obvious fact is not why this breaks down for three dimensions, but why it still holds true in two dimensions.

The above is well known to mathematicians or to many people who have played around a bit with geometric objects. But, I recently learned a related fact that I found startling. Call a rotation "periodic" if we eventually get every point back to where we started. So for example, if one repeat a 90 degree rotation (π/2 for those using radians) four times we will have every point back where we started. Now, it turns out that for rotations of S² even though the composition of rotations is a rotation, the composition of periodic rotations is not necessarily periodic. Once one knows that this is true it is easy construct examples. Consider two rotations around perpendicular axises each of 30 degrees (π/6 in radians). It isn't difficult to show that their composition although still a rotation is not periodic. This is a good example of how even basic geometry can surprise us even when we think we understand it.

Review of Jason Rosenhouse's "The Monty Hall Problem"

I've had the recent pleasure of reading Jason Rosenhouse's "The Monty Hall Problem." Rosenhouse's book is a comprehensive investigation into the eponymous Monty Hall problem, variations of the problem, and the larger implications of the problem.

The original Monty Hall problem named after a game played on an old television game show "Let's Make a Deal" with host Monty Hall. Rosenhouse describes the problem as:

You are shown three identical doors. Behind one of them is a car. The other two conceal goats. You are asked to choose, but not open one of the doors. After doing so, Monty, who knows where the car is, opens one of the two remaining doors. He always opens a door he knows to be incorrect, and randomly chooses which door to open when he has a more than one option (which happens on those occasions where your initial choice conceals the car). After opening an incorrect door, Monty gives you the option of either switching to the other unopened door or sticking with your original choice. You then receive whatever is behind the door you choose. What should you do?

(Presumably you are attempting to maximize your chance of winning one's chance of getting a car). Most people conclude that there's no benefit from switching. The general logic against switching is that after the elimination of a door there are two doors remaining, so each should now have a 1/2 chance of containing the door.

This logic is incorrect. One door has a 2/3rds chance of getting the car if one's general strategy is switching. Many people find this claim extremely counterintuitive. To see quickly the correctness of this claim, note that if one chooses a strategy of to always switching, then one will switch to the correct car-containing door exactly when your original door was not the car door. This will occur 2/3rd of the time.

Many people have great difficulty accepting the correct solution to the Monty Hall problem. This includes not just laypeople, but also professional mathematicians, including most famously Paul Erdos who initially did not accept the answer. The problem, and variants thereof, not only raise interesting questions of probability but also give insight into how humans think about probability.

Rosenhouse's book is very well done. He looks not just at the math, but also the history of the problem, and philosophical and psychological implications of the problem. For example, he discusses studies which show that cross-culturally the vast majority of people when given the problem will not switch. I was unaware until I read this book how much cross-disciplinary work there had been surrounding the Monty Hall problem. Not all of this work has been that impressive, and Rosenhouse correctly points out where much of the philosophical argumentation over the problem simply breaks downs. Along the way, Rosenhouse explains such important concepts as Bayes' Theorem (where he uses the simple discrete case), the different approaches to what probabilities mean (classical, frequentist, and Bayesian) and their philosophical implications. The book could easily be used for supplementary reading for an undergraduate course in probability or reading for an interested highschool student.

By far the most interesting parts of the book were the chapters focusing on the psychological aspects of the problem. Systematic investigation of the common failure of people to correctly analyze the Monty Hall problem has lead to much insight about how humans reason about probability. This analysis strongly suggests that humans use a variety of heuristics which generally work well for many circumstances humans run into but break down in extreme cases. In a short blog post I can’t do justice to the clever, sophisticated experimental set-ups used to test the nature and extent of these heuristics, so I'll simply recommend that people read the book.

For my own part, I'd like to use this as an opportunity to propose two continuous versions of the Monty Hall problem that to my knowledge have not been previously discussed. Consider a circle of circumference 1. A point is randomly picked as the target point on circle (and not revealed to you). You then pick a random interval of length 1/3rd on the circle. Monty knows where the target point is. If you picked an interval that contains the target point, Monty picks a random 1/3rd interval that doesn't overlap your interval and reveals that interval as not containing the target point. If your interval does not contain the target point, Monty instead picks uniformly a 1/3rd interval that doesn't include the target point and doesn't overlap with your interval. At the end of this process, you have with probability one, three possible intervals that might contain the target point, your original interval, or the intervals on either side of Monty's revealed interval. You are given the option to switch to one of these new intervals. Should you switch and if so to which interval?

I'm pretty sure that the answer in this modified form is also to switch, in this case switching to the larger of the two new intervals.

However, the situation becomes a bit trickier if we modify it a bit. Consider the following situation that is identical to the above, but instead of Monty cutting out an interval of length 1/3rd, he picks k intervals of each length 1/(3k) (thus the initial case above is k=1). Monty picks where to place these intervals by each picking one of the valid intervals uniformly and then going on to the other, then revealing the locations of all his intervals at the end. The remaining choices for an interval for you to pick are your original interval or any of the smaller intervals created in between Monty's choices. You get an option to stay or to switch to one of these intervals. It seems clear that even for k=2, sometiimes you should switch and sometimes you should not switch, depending on the locations of Monty's intervals. However, it isn't clear to me when to stay and when to switch. Thoughts are welcome.

On Almost Commuting Matrices

When mathematicians encounter a binary operation, one of the first things they ask is "when does the operation commute?" That is, given an operation * when does one have A*B=B*A? Some operations always commute. Addition and multiplication in the real numbers are examples of this. Sometimes they commute under certain restricted circumstances. For example, subtraction rarely commutes (1-2 is not the same as 2-1).

In high school, children are often taught about matrices and matrix multiplication. Matrix multiplication seems to be given in part simply to have an example of an operation which has complicated behavior regarding when it commutes. Of course, we can only meaningfully talk about this when the matrices in question are assumed to be square matrices since otherwise the multiplication won't even be defined. However, matrices have other operations which we can do on them other than just matrix addition and multiplication. In particular, we can also multiply a matrix by a scalar.

This raises the following question: When do matrices almost commute? By almost commute, we mean commute up to multiplication by a non-zero scalar. A general result seems difficult. But there is at least one pretty result which can be proven without too much trouble by looking at the eigenvalues and eigenvectors of a pair of matrices:

If cAB=BA for some constant c, and A is invertible, then c is a dth root of unity for some d such that d divides the number of distinct non-zero eigenvalues of B. It isn't that hard to generalize this result slightly with A not invertible. However, one then needs the slightly technical condition that A sends no non-zero eigenvector of B to zero. Note also that this result is most nicely stated in the slightly more restricted symmetric case when both A and B are invertible.

One pretty corollary of this result is that if A and B are invertible p x p matrices over the real numbers where p is an odd prime, with all distinct eigenvalues, then A and B are almost commuting if and only if they actually commute.

Conservapedia, P=NP, and the Fields Medal

Conservapedia, the right-wing, Christian alternative to Wikipedia has once again broken new ground. In previous entries we've discussed Conservapedia's founder Andrew Schlafly self-Godwining and Conservapedia's interesting take on Popperian falsifiability. Others have discussed Conservapedia's objections to special and general relativity. Now, Conservapedia is at it again.

Apparently, Conservapedia has taken a recent interest in mathematics. First, they added to their mainpage a take on the recent reports that Deolalikar had proven that P ≠ NP . Conservapedia announced:

University professors pile on against a non-professor's claim to have solved one of the millennium problems. MIT Assistant Professor Scott Aaronson declares, "Vinay Deolalikar still hasn’t retracted his P≠NP claim, but a clear consensus has emerged that the proof, as it stands, is fatally flawed." He absurdly adds, with a cite to Richard Dawkins, "the only miracle in life is that there are no miracles, neither in mathematics nor in anything else."

But the best of the public, aided by the internet, will inevitably solve more problems than liberal colleges will - just as Grigori Perelman solved another millennium problem. The future belongs to the conservative public.

(internal links and fonts suppressed)

Apparently, Aaronson's decision to quote Richard Dawkins meant that math must be evil. I'll leave it as an exercise to the reader to note some of the other more glaring errors. However, this was not the end of Conservapedia's attack on establishment math for being just too liberal. Shortly after this declaration, an addition about the Fields Medal went up. The Fields Medal, awarded every four years, is for mathematics roughly equivalent to a Noble Prize(there is no Nobel in math). Conservapedia announced a "Conservapedia exclusive":

[T]his Thursday liberals will likely give the coveted Fields Medal -- math's highest honor -- to an underachieving woman and to a communist-trained mathematician from Vietnam. Is the lamestream media holding back stories about this to create a bigger splash on Thursday?

(internal links and fonts suppressed)

It is not clear what "underachieving woman" Conservapedia is thinking of, but apparently the "communist-trained mathematician" is a reference to Ngo Bao Chau, who made headlines last year for proving the Fundamental Lemma of the Langlands program. Apparently Conservapedia believes that the general media cares so much about mathematics that a failure to speculate on who will win the Fields Medal is a sign of a media conspiracy. Why a "communist-trained" mathematician would be a big deal is not clear given thatabout half of the Fields Medal winners have been either from the USSR or trained in the USSR.

Also, apparently Conservapedia is unhappy that after Terence Tao got the Fields Medal four years ago he then endorsed Barack Obama for President, Finally, we come to the detail that forced me to write this blog entry. To deal with this apparent liberal bias and affirmative action in the Fields Medal, Conservapedia is starting its own award for mathematicians, the "ConservaMath Medal." According to the website this Medal is "the merit-based alternative to the Fields Medal, with winners announced at the same time so that real achievement is recognized." I'll let that speak for itself.

Integer Complexity: An Upper Bound Update

It looks like I may have a final upper bound on the integer complexity problem. Recall we defined f(n) to be the minimum number of 1s needed to represent n as a product or sum of 1s. Thus, f(6)=5 because we can write 6=(1+1)(1+1+1). Harry Altman and I have been working on improving the lower and upper bounds on this function. Prior posts about this problem can be found under the label integer complexity. Harry has a large number of posts on the subject also, but they aren't all tagged so I'll just direct readers to the most recent one.

I'm writing this post to announce that we have a tight upper bound for f(n). Prior to our work, it was known that if n ≥ 2, we have 3log2 n ≥ f(n) ≥ 3log3 n. It is clear that the lower bound is hit infinitely often (whenever n is a power of 3). We (and by we I mean mostly Harry) have worked on understanding what n have close to the lowest possible value, and using this to understand other conjectures about f, such as the conjecture that if n=2^a*3^b then the most efficient representation for n is the obvious one. However, I've been also working on improving the upper bound, and whenever I've thought that I've been done improving the upper bound, I've then realized another way to tweak my proof to reduce the upper bound slightly. However, at this point, I'm confident that cannot happen anymore using the techniques in question, barring substantially new insight. Thus, I'm now announcing the new upper bound. We have for n ≥ 2, f(n) ≤ αlog2 n where α = 70/(log_2 102236160)= 2.630853... Note that this constant is just small enough for us to also state the weaker but prettier result that f(n) ≤ (19/5) log n. Unfortunately, the proof in question is very ugly, involving a large amount of case checking as well as nasty calculation of inequalities. I'm in the process of writing up the last bit. If readers are interested I can email people a draft of the proof when it is fully written.

Math Anxiety, Math Education and Gender Expectations

A recent study has shown that young girls in the United States who are taught by teachers with math anxiety are more likely themselves to develop anxiety of about math. The study is by psychologist Sian Beilock et al. at the University of Chicago. Her research looked at second graders’ anxiety levels in mathematics. She found that, with her sample, there was no correlation between gender and attitude towards math at the beginning of the school year. However, by the end of the school year, girls were much more likely to develop math anxiety. Moreover, girls were much more likely to develop such anxiety if their female teachers had math anxiety. Rather than summarize all of the more interesting details in the study, what follows first is a large quote from the study followed by my comments:

If it is simply the case that highly math-anxious teachers are worse math teachers, one would expect to see a relation between teacher anxiety and the math achievement of both boys and girls. Instead, teachers with high math anxiety seem to be specifically affecting girls’ math achievement—and doing so by influencing girls’ gender-related beliefs about who is good at math.

This study explores the relation between female teachers’ math anxieties and their students’ math achievement. Thus, it is an open question as to whether there would be a relation between teacher math anxiety and student math achievement if we had focused on male instead of female teachers. In one sense, the lack of male elementary school teachers in the United States makes this a hard question to answer. Yet, it is an important question, given research suggesting that girls are more socially sensitive than boys in early elementary school (16). Thus, it is possible that even with male teachers, a relation between teacher anxiety and female student achievement might occur. Nevertheless, the literature on math anxiety, gender modeling, and the impact of negative stereotypes on achievement lead us to speculate that any relation between male teacher anxiety and girls’ math achievement would be obtained through a different route than the one proposed here. Moreover, in the current work, the relation between female teachers’ math anxieties and girls’ math achievement was mediated (or accounted for) by girls’ beliefs that boys are better at math. Hence, it seems unlikely that a male teacher’s math anxiety would affect girls’ math achievement by pushing girls to confirm that boys are good at math.

In addition, children do not blindly imitate adults of the same gender. Instead, they model behaviors they believe to be gendertypical and appropriate (9). Thus, it may be that first- and secondgrade girls are more likely to be influenced by their teachers’ anxieties than their male classmates, because most early elementary school teachers are female and the high levels of math anxiety in this teacher population confirm a societal stereotype about girls’ math ability (2). This match between teacher math anxiety and societal norms would not hold for male teachers exhibiting math anxiety. However, if such a correspondence is important in influencing student achievement, we would expect that for school subjects for which girls are stereotyped to excel (e.g., language arts), male teachers’ anxieties would have an impact on male more than female students’ achievement.

It is important to note that the effects reported in the current work, although significant, are small. There are likely many influences on girls’ math achievement and gender ability beliefs overand above their current teachers’ anxieties. For instance, previous teachers, parents, peers, and siblings who either do or do notmodel traditional academic gender roles may play an important part in shaping girls’ gender ability beliefs and their math achievement more generally. Exploring these relationships—in addition to the influence of both male and female teachers—will help to elucidate the full range of social influences on student achievement.

In conclusion, we show that female teachers’ math anxiety has consequences for the math achievement of girls in early elementary school grades. Given that this relation is mediated by girls’ gender ability beliefs, we speculate that female teachers model commonly held gender stereotypes to their female students through their math anxieties. These findings open a window into gender differences in math achievement and attitudes that emerge over the course of schooling.

Interestingly, math anxiety can be reduced through math training and education (17 –19). This suggests that the minimal mathematics requirements for obtaining an elementary education degree at most US universities need to be rethought. If the next generation of teachers—especially elementary school teachers—is going to teach their students effectively, more care needs to be taken to develop both strong math skills and positive math attitudes in these educators.

How should we respond to this study? As with all initial scientific studies, the data is by its nature tentative, but in this case it looks very robust.Consequently I will for the remainder of this post assume that the phenomenon as described in Beilock et al. is accurate.

We currently focus most of our resources aimed at getting young women to be confident in math at the middle school and high school level. Moreover, prominent celebrities who have tried to deal with this problem have focused almost exclusively on this older age cohort. Danica McKellar for example has focused on encouraging mathematical confidence and learning in middle school girls. This new study suggests that much of the damage done to girls’ mathematical confidence occurs at a very young age. Thus, we may need to rethink where resources are being allocated. Unfortunately, this study does not as of yet include any long-term follow-up. So how much of this early math anxiety is correctable later is not clear. Aside from this sort of vague generality about resource allocation, here are four concrete proposals that need discussion.

First, let’s get the most controversial possibility out of the way: We may want to consider more direct encouragement of males to engage in elementary school teaching. Put less politely, we should consider affirmative action and other incentives to encourage males to go into elementary school teaching, at least for math. While this study showed that young girls picked up on the math anxiety of their female teachers, it is clear that young males did not gain math anxiety from female teachers. Moreover, math anxiety is simply less common among males. Thus, male students will be unlikely to pick up math anxiety, and female students will not pick it up from male teachers until they are older. This proposal has a number of problems. Foremost among them is that it assumes that male teachers will not act in an overly sexist fashion, either explicitly or implicitly denigrating female mathematical ability. Unfortunately, it is clear from anecdotal evidence that many teachers of both genders do explicitly disparage young girls’ mathematical ability. See for example this thread at SkepChick . Moreover, the exact impact of male teachers is far from clear: The study looked only at female teachers. Without more data about how students of both genders interact with male teachers both with and without math anxiety, this proposal must by nature be extremely tentative. The argument can be made that this will send a bad message to young children, i.e., that only males can teach or do math. However, that’s erroneous. Currently, around 90% of elementary school teachers are female. If we replace the females with math anxiety with males without math anxiety or even males with mild math anxiety, the fraction of teachers who are male will still be well below half. So this step also helps correct for a pre-existing gender disparity in elementary sc hool teaching.

Second, and almost as controversial as the first proposal, we can encourage teachers, especially females, to not go into elementary school teaching if they have math anxiety or simply aren’t very good at math. Unfortunately, we already suffer serious problems in the United States getting qualified people to teach elementary school. So directly altering who we encourage to become teachers is non-optimal. Similarly, increasing the required level of math background for elementary school teachers is not a good response. Moreover, as Beilock discusses, proper education can remove or reduce math anxiety. This leads directly to the third possible response.

Third, we must take more steps to directly reduce math anxiety in teachers and people planning on becoming teachers. This should likely focus on female teachers or teacher-candidates who have shown to have serious math anxiety issues. We can introduce them to additional areas of math, where the math is easy to understand and fun. Very elementary number theory and graph theory may be relevant areas. More broadly, we can also have them play mathematical games that get them more comfortable with the idea that math can be fun. Zendo for example would be an excellent potential confidence builder.

Fourth, we can take direct steps to expose young females to mathematically confident females. One method of doing so is to have the math sections of elementary education taught by separate teachers who are more mathematically confident. Even in schools with high percentages of teachers with math anxiety, some teachers will still likely be mathematically confident. Having those teachers handle the math teaching for other teachers (or possibly specializing to only teach math) is an option. Also, we can encourage young girls by having them directly interact with female mathematicians. Part of the problem is that mathematically confident females generally go into industry, sciences or upper tiers of academia, not elementary school teaching. So, mathematicians and scientists should visit local elementary schools. If schools can regularly sponsor visits by firefighters, police officers and members of other vocations and professions, there’s no reason that mathematicians and scientists can’t do the same thing. It doesn’t take much to show up and say “Hey! Look! I’m a lady who does math. And I enjoy it!”

Fortunately, resources which are spent encouraging the general public and children of all ages to be more mathematically confident can potentially work in general to help the situation with female students. Thus, work like Steven Strogatz’s new regular column in the New York Times to help make math more accessible to the general audience can be helpful.
No matter what happens we need to look at this data dispassionately at the same time as we try to gather more information about the transmittable nature of math anxiety. As a society we are short-changing many bright young females. Because those students then do not go into math-intensive areas of study,the society suffers. These problems need to be addressed. We are not doing enough now to address them.

A Quick Note on a Silly, Pseudo-recursive Class of Functions

Let f(n) be a function from the natural numbers from the natural numbers. Suppose further that f(1)=1, and assume that f(n) is equal to the number of positive integers k that are less than equal to n and satisfy f(k) | k. Then it is not hard to show that in fact f(n)=n. Now suppose we instead look at the exact same thing, but insist that f(n) count the number of k that are at most n and satisfy f(k)|P(k) where P is some fixed polynomial with integer coefficients.

For some choices of P, we do not have any function f which would satisfy the desired recursion. For example, if P(x)=x+1 we don't have any function f satisfying the recursion. To see this, note that we have either f(2)=1 or f(2)=2. If f(2)=1, then f(1)|1, and f(2)|2, so in fact f(2)=2. Consider the other case where f(2)=2. If so, since 2 does not divide 3, we must have f(2)=1. Contradiction and nd of p.

Here's my question which I have not been able to make substantial progress on: Are there any valid choices of P and f that satisfy the recursion and don't have f(n)=n for all n?

Minyanim and Mathematics: A protocol for anonymous counting.

In Judaism, many communal prayers require a minimum of ten people. This quorum is called a "minyan" which is often also used to mean a service in general. (In Orthodox Judaism, only Jewish adult males count for a minyam while in Conservative Judaism all Jewish adults count). However, certain liturgical elements on fast days (such as a Torah reading at the afternoon prayer) require not just ten present, but ten who are actually fasting.

However, people may not wish to advertise that they are not fasting even if they are willing to assist with the minyan. Moreover, even a very observant individual might have a reason not to fast and would not want people to know about it (such as a medical condition). This leads to the following problem: How do we determine how many people are fasting without requiring people to disclose whether or not they are fasting?

In a recent minyan I attended, this question was handled by the gabbai (the person in charge of running the minyan) asking everyone to close their eyes and hold up one hand if they were fasting. This is obviously unsatisfactory since the gabbai finds out who is fasting. One could suggest slips of paper or the like. but they could be easily connected to particular individuals. To make this problem interesting, it is helpful to assume that everyone knows the identity of the sender of any communication they receive. Is there a solution under which individuals' statuses remain private while the minyan is assured of 10 fasters?

Curiously the answer is yes albeit the solution is a bit cumbersome. Here's how: The gabbai picks a random integer (the distribution doesn't matter although in practice one might want a reasonable distribution that approximates a bell curve or an exponential distribution or something similar). The gabbai takes this integer and adds 1 to it if he is fasting. The gabbai whispers this number to another person. That person adds 1 to the total if he is fasting and similarly passes it on to another person. The last person gives his number to the gabbai. The gabbai now subtracts the random integer that they initially added. The total the gabbai has is the number of people fasting.

A few notes about this algorithm. First, it is important that, when the gabbai is picking a random integer, that every integer has some non-zero probability of being chosen. Consider, for example, what would happen if the gabbai was known to only pick positive integers. If the gabbai picks 1, the next person can tell if the gabbai is not fasting. Thus, the gabbai can never pick 1. But then, by the same logic, the gabbai won't be able to pick 2. Or 3. And so on. This problem is avoided if the gabbai can pick any integer whether or not it is positive.

There is also a degenerate case of if only the gabbia is fasting or only the gabbai is not fasting. In those cases, the exceptional individual can work out the status of everyone else.

The algorithm also assumes that people are not going out of their way to obtain information. If two people bracket a third and cooperate, they can figure out the middle person's status as a faster.

In fact, it turns out that it is possible to make a more sophisticated protocol that would prevent this and similar tricks. This would be a variation of an anonymous voting algorithm. However, these algorithms rely on clever cryptography with large prime numbers which is only believed to work rather than proven to work. Implementation also would require much more computation than can be done by hand.

Less intensive algorithms can be used to increase the number of people who must cooperate. It is, for example, an interesting exercise to construct a variation of the above such that finding out someone's status requires the cooperation of at least three people.

This algorithm in practice is cumbersome. Moreover, the goal it seeks to accomplish is minor since, if the fast day liturgy is used, those sections of the services actually need to be performed by people who are fasting. Thus, the gabbai will need to know the status of at least a few people. However, this algorithm has the slight advantage that, if there are not enough people to recite the fast day liturgy, then no one will know which people cause the deficiency.

Integer Complexity: Why Blogging is Fun

A while back I wrote a blog entry about a generalization of the four fours problem. That entry focused on the function f(n) defined as the minimum number of 1s needed to represent n using just addition and multiplication. So for example, f(6)=5 since 6 = (1+1)(1+1+1) and there's no way to represent 6 with four or fewer 1s. Surprisingly little is known about the general behavior of f.

After that blog entry, two commentators, Etienne and Harry, took up examining f in more detail. Harry and I together produced new work on the behavior of f that will likely turn into a paper.

I will attempt here to briefly summarize what was known and how we've improved it. (Reading my original blog entry and my previous follow-up will probably help matters).

It was known that f(n) satisfied the inequalities 3log3 n ≤ f(n) ≤ 3log2 n for n greater than 1. We've improved the upper bound somewhat, replacing 3log2 n with 2.64log2 n. We've also shown that f(n) - 3log3 n is unbounded (that is one can make it as large as one wants if one chooses suitable n). We did this by defining what we call the "defect" of d(n)= f(n) - 3log3 n. We defined Ak to be the set of numbers with defect at most k. Then, we were able to show that each set Ak was way too small to contain every natural number. More technically, we showed that if one defines Ak(x) to be the number of elements in Ak that are at most x, then Ak(x) = O( (log x)^c) with c a function of k.


Also, it was conjectured that if one had a number of the form n=2^a3^b that f(2^a3^b)=2a+3b (aside from the trivial case when a=b=0). Essentially this conjecture stated that the most efficient representation for n arose from the obvious one, that is writing n = (1+1)(1+1)...(1+1) * (1+1+1)(1+1+1)...(1+1+1). Harry, was able to prove that this conjecture held for all such n as long as a was at most 10. Since then, we've been able to improve that bound to a at most 19.

It turns out that for much of the behavior of f, including both of the two problems discussed above, the sets of Ak and some closely related sets are natural objects to consider. Thus, we tried to work on making c as small as we could in the equation Ak(x) = O( (log x)^c). The initial proof gave a very poor bound on c (being able to take c=1024^k). After a series of improvements, primarily by Harry, he was able to take c=4^k and then using a combination
of ideas from the two of us, we got a linear bound. In particular, one can take c=3k/(5- 3log_3 5). Note how this bound grows much slower than the previous bounds. However, we do know that A1(x) is in fact of order log(x)^2 so there's some realm for improvement in that this proof gives an upper bound for c of about 4.96 for A1(x). One thing to note: While these results were proved using induction arguments (as one would expect), one cannot induct on Ak with k a positive integer. One actually needs to induct on Aαk for fixed α less than 1. A good choice of what alpha to use then becomes very important.

Harry has on his blog a long post that summarizes what we have accomplished and discusses them in more detail. See his posts here and here and the other posts he links to.

The moral to this story is that you don't know what interesting things will happen when you blog, especially when you have readers that are as smart or smarter than you.

Benford’s Law: Human Intuition, Randomness and Fraud

Suppose we look at some set of fairly natural data, say the populations of various countries. Let’s look at the leading digits of their populations. For example, the United States has a population slightly over 300 million. So, for the United States, the leading digit would be 3. What fraction of countries would you expect to have a leading digit of 1? Most people would guess 1/9th since there are 9 possibilities (1,2,3,4,5,6,7,8,9) and no obvious reasons to prefer any digit over any other digit. However, you’d be wrong:The actual percentage is slightly over 25%. In fact, it turns out that we should expect about 30% of countries to have a leading digit of 1. This strangely large number of 1s shows up frequently in natural data and is known as Benford’s law. It turns out that for many natural data sets we expect about 30% to have a leading digit of 1, about 18% to have a leading digit of 2 and so on. Benford’s Law is an important statistical rule that has a variety of generalizations and has practical applications (such as in detecting fraudulent or manipulated data).

Where is this strange pattern coming from? I didn’t have a good understanding of this until it was explained to me by Steven Miller. Consider a finite list of numbers that is reasonably well-behaved. For each member of our list, we can write it in scientific notation. So, for example. if we had 236 on our list, we would write it as 2.36 * 10^2. Note that the lead digit is then determined by what the lead digit is in the part of the scientific notation that isn’t the exponent. (This part is sometimes called the mantissa when one wants to be fancy) Now, for each number on our list, instead of looking at the number x, we can look at log10 x. What does this do to the scientific notation? Well, scientific notation then corresponds to the log of the mantissa + an integer that is the power of the exponent. So, for example, log10 (2.36 * 10^2)= .3729...+ 2.

Let’s examine the non-integer part of log10 x (call this f(x)) What distribution do we expect for f(x)?, It is a fixed value between 0 and 1 with no clear cut offs or biases in any direction so the most obvious thing to do is to make it a uniform distribution. That means that there’s about a 5% chance that f(x) falls below .05, about a 20% chance that f(x) falls below .2, about a 50% chance that f(x) falls below .5 and so on.

So what does this tell us about the leading digit? If the mantissa is below 2, then we have lead digit 1. If the mantissa is between 2 and 3, then we have lead digit 2 and so on. The mantissa is below 2 if f(x) is less than log10 2 = .301. Accordingly, we should expect that the mantissa is below 2 about 30.1% of the time. Thus, a number should have a lead digit of 1 about 30.1% of the time. Similar logic works for how frequently we should expect the lead digit to be 2, or 3 or so on.

What is wrong with the intuition that every lead digit is just as common? When we calculate probabilities, we are used to using the simplest probability distribution we can imagine, something like picking a positive integer from 1 to 10^n for some fixed n. We are used to this approach primarily because it is easy to calculate. Consequently, most probability problems in high school and college assume that we have such a uniform distribution since that assumption makes the math much easier. But actual distributions in real life don’t often look like this. For example, we might have a Bell curve or some other distribution. For almost any distribution that arises in nature, Benford’s law will apply due to the logic we used earlier.

So what does this do for us? Perhaps most importantly, we can use this insight to detect fraud. When humans try to make up data, it often fails to fit Benford’s law. In general, humans are bad at constructing data that passes any minimal test for randomness. Failure to obey a generalized version of Benford’s law was one of the major pieces of evidence for election fraud in the last Iranian election. The recent questions regarding whether Strategic Visions Polling was falsifying poll data arose when Nate Silver noticed that its results diverged substantially from Benford’s law.

For more information on Benford’s Law and related patterns in data, as well as more mathematical discussions of that data, see Terry Tao’s blog post from which I shamelessly stole the hard data about populations of nations.

New Largest Prime Number Found

The largest known prime has now been bumped up. The recently discovered prime is 2^43112609 − 1 which in base 10 has around twelve million digits. As with all the largest primes discovered for most of the last hundred years, the prime is a Mersenne prime, that is it is one less than a power of 2. As with the last few Mersenne primes discovered, this was discovered by the Great Internet Mersenne Prime Search which uses distributed computing to search for Mersenne primes. I've blogged before about Mersenne primes. For more details on why we care about Mersenne primes and their history dating back to the ancient Greeks see this post and this post.

There are reasons to suspect that if 2^n-1 is prime that n-1 should be likely to have a lot of small prime factors. In this case, 43112609 -1= 2^5 * 7 * 11 * 17497. So while some of the prime divisors look very small, it has at least one prime very large prime divisor and so doesn't seem to fit this pattern well. This is in contrast to the last discovered Mersenne prime 2^42643801 - 1. In that case one has 42643800 = 2^3 * 3^3 * 5^2 * 53 * 149. It remains to be seen if this new example is simply an outlier or if we need to reevaluate what we expect the exponents of Mersenne primes to look like.

Lockhart’s Lament: A Cogent Criticism of Math Education

I’ve received multiple requests to blog about Paul Lockhart’s “A Mathematician’s Lament.” Lockhart is a math teacher who is fed up with elementary and high school math education. I haven’t blogged about Lockhart's piece primarily because I agree with most of what he has to say and also a lot of people have already talked about it. (See for example, Scott Aaronson’s insightful commentary.)

Lockhart’s thesis is that much of mathematics education is simply wrong. According to Lockhart, the vast majority of our math education before college is rote learning that does not convey what mathematics is about. Lockhart argues that much of what children do in high school would be the equivalent of painting by numbers if we translated it into art. Mathematics is far more about exploration and understanding than it is about rote memorization. Lockhart argues that, by failing to let children understand and explore, we are not even teaching them mathematics. Lockhart further argues against rote math education based on practicality i.e. that these are techniques children will need when they are older.

Lockhart makes many good points and I recommend that people read his piece. As someone who has worked for many summers with the PROMYS program which uses a method similar to that outlined by Lockhart, I have much sympathy for his viewpoint. However, there are three problems with his thesis.

First, Lockhart overemphasizes the willingness of students to do exploratory mathematics. Exploration is intrinsically difficult. Moreover, it is difficult to get people to do math exploration if they don’t want to. If one tries to get youngsters to explore and they can’t do it effectively , the result is that parents will do the “exploration” for them. I’m sure there are readers of this blog who remember their parents “helping” with art projects back in elementary school.
Second, Lockhart underemphasizes the actual importance of rote learning and drills in picking up basic mathematics. Students need to be able to add, subtract, divide and multiply. They need to be able to do these things quickly in real life. Moreover, they need to do them enough times that they develop an intuition for orders of magnitude and when answers look right or wrong. That requires drilling in arithmetic from a young age. Lockhart addresses this issue briefly, but his response is unsatisfactory.

Third, Lockhart’s choice of focus on specific aspects of the high school and elementary curriculum is poor. He is correct in his criticism of the large amounts of trig memorization that occur. But he is incorrect in his example of the quadratic formula. In order to have an intuitive understanding of parabolas and other curves of degree 2, you need to know the quadratic formula. Moreover, the formula comes up frequently enough in later math classes that not knowing it would be a serious barrier. Finally, there are some items that educated people just need to know. Understanding the quadratic formula is one of those things that educated people just need to know in the same way that you can’t be an educated citizen of the United States and not know who Abraham Lincoln was.

Despite these criticisms, Lockhart is essentially correct. There are many serious problems with how we teach math and Lockhart correctly identifies many of them. While the massive overhaul that he outlines may not be necessary, it would substantially help matters if children were exposed at a much earlier age to what mathematics actually is, a subtle and beautiful art.

Alan Turing, Apologies, and Cthulhu

The British Government has finally apologized for its treatment of Alan Turing. Turing was one of the greatest mathematicians of the twentieth century. He was responsible for founding computer science and he lead the effort to crack the Enigma encryption used by the Germans during World War II. This work saved many Allied lives and according to some historians proved crucial to the victory over the Axis forces. Without Turing's work, our world would look very different. However, Turing was gay. In 1952, Turing was convicted for engaging in homosexual acts. He was forced to undergo hormone therapy which lead to weight gain and other problems. Turing's security clearance was revoked. At the time, homosexuals were considered a security risk because of the potential of blackmail. The fact that the entire risk of blackmail was because they were considered a security risk apparently did not matter. Nor did it matter that since Turing was publicly gay, there was no possible risk of blackmail. Turing's ongoing consulting work with the government was terminated. Turing's life took a steady downhill side. In 1954, he committed suicide.

I am ambivalent about this apology. On the one hand, it is good to acknowledge how horribly Britain treated one of the saviors of civilization. On the other hand, apologies to the long dead always strike me as hollow. The living always face more than enough issues that are of far more practical importance than assuaging the feelings of the long-deceased.

Rather than discuss the pros and cons of such apologies, I am instead going to suggest three pieces of further reading.

First, Wikipedia has an excellent biography of Turing which explains his accomplishments and his mistreatment in far more detail than one can easily do in a short blog entry.

Second, Greg Egan, an excellent science fiction writer, has written a short story imagining a world in which Turing's life went slightly differently. In this case, "slightly differently" means had the assistance of a time-traveling robot. The story is more serious than one might think from that summary. The story looks at Turing's interactions with C.S. Lewis. I'm not sure the story is completely fair to Lewis overall, but it is very well-written and is an amusing what-if. Like most of Egan's writing, there's just enough plausibly correct mathematics to make it interesting.

Third, Charles Stross has written an amusing novel The Atrocity Archives in which Turing figures in the background. The essential premise is that Turing did not commit suicide but was assassinated by the British government to cover up far scarier discoveries he made (so presumably the Brits still owe Turing an apology in that universe). In that novel, mathematics is deeply connected to magic and thinking about certain theorems can accidentally lead to summonings of Cthulhu and other eldritch horrors. Turing was killed for discovering a series of powerful theorems including a proof that P=NP which if invoked improperly could destroy our universe. Unlike the Egan story, this is not a story I can claim has much in the way of serious merit. But it is very fun. By most accounts, Turing was a man with a sense of humor about things. I'd like to think that he'd smile to know that fifty years after he was dead, Great Britain would be apologizing to him at the same time that people were reading novels which linked him to Lovecraftian horrors.