God Plays Dice

Uniquely identifying people by birth date, gender, and zip code

2009-12-18T11:36:00.001-05:00

Netflix Spilled Your Brokeback Mountain Secret, Lawsuit Claims. A woman is suing Netflix because she was in the closet, and her movie-rental data was part of the Netflix prize dataset. She claims this means that people could figure out her secret.

Now Netflix is starting a second contest, and rumor has it that the data will include the zip code, birthdate, and gender of each individual. According to this paper (abstract only, unfortunately, so I can't comment on methods) by Latanya Sweeney, this is enough to uniquely identify 87% of the US population. A paper by Phillippe Golle gives the figure as 63%, based on actual Census Bureau data. (The Census gives the number of people with each birth year and gender in each zip code.)

Is it surprising that people can be identified this easily?

From the Golle paper, there are 33,233 "Zip Code Tabulation Areas" in the United States.

US life expectancy is 77.7 years. Since this is a back-of-the-envelope calculation, let's assume that everybody drops dead after 77.7 years (28,379 days), and therefore that the age of a random individual is uniformly distributed over the last 28,000 days. (It pains me to say this, because my grandmother is 85 and still living.)

There are, to a first approximation, two genders.

Therefore there are 28,379 * 33,233 * 2, or about 1.9 billion, possible combinations of birthdate, zip code, and gender. There are about 300 million Americans. If we assume all of these are equally likely (which they're not; some ages are more likely than others, and some zip codes have more people than others), and that they're independent (which they're not, as anybody who's lived in a college town can tell you; Golle notes the college-town effect, and also a military-base effect), then on average the number of people having a given (birthdate, zip code, gender) triplet is about 0.16.

So we'll model the population of the US as 1.9 billion Poisson random variables, each of mean 0.16, and each corresponding to a birthdate-zip code-gender triplet. How many of these do we expect to have value 1 (meaning that that triplet picks out exactly one person)? The probability that a Poisson(0.16) random variable takes the value 1 is exp(-0.16)*(0.16). Thus we find that there are (1.9 billion)*(0.16)*exp(-0.16) people uniquely identified by this triplet, out of (2.5 billion)*(0.16) people.

According to this crude model, the probability that a random individual is uniquely identified by these three pieces of information, then, is exp(-0.16), or about 85%. Why is everybody so surprised?

Distribution of Putnam scores

2009-12-08T12:04:00.004-05:00

The distributions of Putnam exam scores are interesting. See, for example, the 2001 distribution. It takes a bit of number-crunching to get an actual distribution of scores from the data; they report the "rank" of the people getting each score. The rank corresponding to a given score is, I assume, A+(B+1)/2 where A is the number of people scoring higher than that score and B is the number of people scoring that particular score. For example, in 2001 -- which happens to be one of the years in which I took the Putnam -- the table begins

Score	101	100	86	80	79	77	73	72	71	70	69	68
Rank	1	2	3	4.5	6	7.5	9	11	14	16.5	19	23.5
Number	1	1	1	2	1	2	1	3	3	2	3	6

where the first two rows are provided by the organizers, and the third row can be worked out by working left to right. For example, once we know 17 people got 70 or better, the fact that the score 69 corresponds to rank 19 means that the people scoring 69 must have been the 18th, 19th, and 20th-best; so there were three of them. (Incidentally, most increasing sequences of half-integers, when interpreted as sequences of ranks, don't appear to correspond to legitimate score distributions; the number of people getting certain scores ends up negative if you're note careful.)

Anyway, if you crunch the numbers on a typical Putnam score distribution you observe two things:
- the scores follow, roughly, a power law; the number of people scoring 10n decays like some power of n, for integer n.
- once you remove this decay (which I haven't actually done; I've just eyeballed it), there are "spikes" at multiples of 10. For example, the number of people scoring 18, 19, 20, 21, 22, 23 in 2001 were 8, 23, 99, 60, 39, 11. Twenty-four people scored 50; seven scored each of 49 and 51.

I can't explain the first one (and it may just be an artifact of the way I'm doing the plotting; lots of things look close to linear when plotted on a logarithmic scale). But the second one is actually easy to explain; Putnam problems are worth ten points each, and most scores are 0 or 10 with a smattering of 1, 2, 8, or 9. Scores between 3 and 7 on a problem are exceedingly rare. So to get a score of, say, 55, one has to get five problems right and have made a bit of progress on three to five more, which is less likely than straight-out solving five or six problems (for 50 or 60, respectively).

Incidentally, I haven't looked at the problems from the 2009 Putnam, because I have work to do.

Math Overflow

2009-10-23T00:16:00.000-04:00

Because I'd have to forfeit my math blogger card otherwise: you should know about Math Overflow This is a site where people can ask mathematics questions -- the level is basically that of questions which would be of interest to professional mathematicians. I'm rather enjoying it; it's procrastination and education at the same time!

It is also useful for asking questions and being told that I already answered them on this blog.

Evidence that mathematicians have a big Internet presence

2009-10-08T14:25:00.004-04:00

If you google genealogy, the first hit is The mathematics genealogy project. In some sense, according to "the Internet", mathematical genealogy is more important than real genealogy! (I have a feeling that the biological parents of mathematicians would be offended by this, so I won't tell my parents.)

If you google AMS, the first hit is the American Mathematical Society. (Societies of meteorologists, musicologists, Montessori schools, etc. show up further down the list.) I have a musicologist friend that I joke with this about, claiming that the mathematical society is the real AMS.

I suspect this is because mathematicians found the Internet early, and seem to be more likely to have personal web pages than even most other academics.

Edit, 4:18 pm: In a comment by Boris, I'm reminded that Google personalizes search results, so what I've said is not true.

Is zero even?

2009-09-30T20:25:00.000-04:00

Did you know that there are actually things to say about whether zero is even or odd (from Wikipedia)? Obviously it is, but the math-ed folks have seriously looked at this.

I found this via a comment by John Thacker at The Volokh Conspiracy. There's a poll there; right now 2% of people have said 0 is odd, 51% even, 43% both, 4% neither. I can kind of understand what's going on with people saying "neither" (perhaps they're getting this from some elementary-school notions), but how is 0 odd?

My answer: yes, zero is even, because it's twice an integer.

(Or because the identity permutation on n letters is an element of the alternating group A_n -- I've been thinking about permutations a lot lately. But if you understand that, you probably are like me, think zero is even, and didn't even think there was anything to discuss.)

Incidentally, sometime recently -- I forget the context -- I saw something that referred to the Gaussian integer a+bi as "uneven" if and only if a and b had different parity.

Economic impact of mathematics?

2009-09-27T22:02:00.000-04:00

Tim Gowers wrote in The Importance of Mathematics:

If you were to work out what mathematical research has cost the world in the last 100 years, and then work out what the world has gained, in crude economic terms, then you would discover that the world has received an extraordinary return on a very small investment.

I don't doubt this. But has anyone actually tried to do this? (And would the numbers even be meaningful?)

Eponyms in mathematics

2009-09-23T20:27:00.002-04:00

Let S be the standard Smith class of normalized univalent Matcuzinski functions on the unit disc, and let B be the subclass of normalized Walquist functions. We establish a simple criterion for the non-Walquistness of a Matcuzinski function. With this technique it is easy to exhibit, using standard Hughes-Williams methods, a class of non-Walquist polynomials. This answers the Kopfschmerzhaus-type problem, posed by R. J. W. (Wally) Jones, concerning the smallest degree of a non-Walquist polynomial.

This fake abstract of a paper is from Merv Henwood and Ivan Rival, Eponymy in Mathematical Nomenclature: What's in a Name, and What Should Be? (PDF), from the Mathematical Intelligencer in 1980. It sounds to me like slight caricature -- but only slight. Henwood and Rival point out that such names are lazy. Names have at least two important functions -- to describe and to label -- and eponyms only label.

Perhaps such abstracts would be more common in areas which are small enough that all the major players talk to each other. I imagine that Smith, Matcuzinski, Walquist, etc. know each other.

Also of interest is David Rusin's list of eponyms occurring in the MSC classification. These names in general seem a bit less obscure than the names one would find in the abstract of a random paper, which isn't surprising as they're names of concepts big enough to get areas named after them.

(And can someone confirm or refute the story that Banach, in the paper in which he introduced Banach spaces, called them "spaces of type B" in an effort to get them named after himself? I've heard this one a few times but always unsourced.)

Steen on mathematics and biology

2009-09-22T12:47:00.001-04:00

Here's a fascinating article on what math is good for in biology: The "Gift" Of Mathematics in the Era of Biology, by Lynn Arthur Steen. Steen gives lots of examples about what math is good for in biology. Somewhat surprisingly to me, he doesn't really mention one of the first things that came to mind, namely the use of combinatorial techniques to study the genome, which is nothing but a word on a four-letter alphabet. It's possible that he subsumes this in "statistics", though; to take a simple example, one might want to know how many times a certain sequence of bases would appear in a "random" genome in order to determine whether the fact that such a pattern appears often is signal or noise. Still, he makes the point that while the traditional mathematics curriculum (with lots of calculus and differential equations) takes its scientific inspiration from physics, biology is ascending.

A shorter version of this article is available at The Chronicle of Higher Education.

(How did I find this? Steen was one of the authors of Counterexamples in Topology, which I mentioned yesterday, so I went over to his web site.)

Perfection "squared" on standardized tests

2009-09-21T17:52:00.004-04:00

I came across an article about a student who got a perfect score on both the ACT and the SAT. (These are the two standardized tests used for university admissions in the US; generally schools on the coasts use the SAT and schools in the interior of the country use the ACT, although this is a vast generalization. The geographical separation seems to be a function of where the tests originated, in Iowa and New Jersey respectively.

This article (which I'm not linking to because I found it by googling a student, and the student is probably already not happy that this is all over the Internet) points out that less than 1 percent of students get a perfect score on each of these tests. (As you'll see below, this is quite an understatement.) I think we're supposed to come to the conclusion that less than 1 in 10000 students would get a perfect score on both.

But of course scores on these tests are positively correlated! So the probability of getting a perfect score on both tests is much higher than the product of the probability of getting a perfect score on each. (I don't think knowing that would help you on the SAT. But it's been a while. In my day they were out of 1600.)

This article indicates that 294 of the high school seniors graduating in 2008 got a perfect score on the SAT, and 514 out of 1.4 million got a perfect score on the ACT. Wikipedia puts the number of SAT takers at 1.5 million per year; let's knock this down to 1 million since some people take the test more than once and we're talking about the total number of students. So the probability that a random student who takes both tests gets a perfect score on both is something like (294/1000000) (514/1400000), which is about one in 1.3 million. The number of students taking both tests is less than this (many people only take one of the two), so assuming independence there should be less than one student per year who gets a perfect score on both tests.

But a quick glance at the Google results will convince you that there are a few students per year who pull this off.

Counterexamples in X

2009-09-21T12:41:00.004-04:00

Counterexamples in Probability And Statistics (Joseph P. Romano and A. F. Siegel) and Counterexamples in Probability and Real Analysis (Gary L. Wise and Eric B. Hall) both seem to be books in the tradition of Counterexamples in Analysis (Bernard Gelbaum and John Olmsted) and Counterexamples in Topology (Lynn Arthur Steen and J. Arthur Seebach. These are books that collect the examples just "outside" the boundaries of the various standard theorems, the point being to explain why one needs the seemingly strange collections of hypotheses that seem to begin every analytic theorem. (Hence the tags "education" and "teaching"; I've often seen these counterexample books described as "anti-textbooks", and as being complementary to standard textbooks which often spend most of their time telling you what's true.)

It seems that these books are concentrated on the analytic end of mathematics; I couldn't find, for example, books of counterexamples in algebra, combinatorics, or number theory. There is, however, Theorems and Counterexamples in Mathematics. My sense is that the nonexistence of these books is connected to the fact that those fields don't seem quite as rife with theorems where all the work is hidden in the definitions.

The hidden mathematics of bathrooms

2009-09-02T09:49:00.002-04:00

From the xkcd blog: urinal protocol vulnerability.

The basic premise here is the following: there's a long row of urinals (n of them), and a line of men who want to use them. The first man picks a urinal at the end. Each man after that picks one of the urinals which is the furthest from any of the occupied urinals. Nobody ever leaves. How many men have to show up before one of them will be forced into using a urinal adjacent to one that's already occupied? Call this number f(n).

You might think that f(n)/n approaches some limit, but it doesn't; it oscillates between 1/3 and 1/2 based on the fractional part of log₂ n. If n = 2^k + 1 then this "greedy" algorithm for filling the urinals works and every other urinal gets filled: f(2^k + 1) = 2^k-1 + 1. If n = 3 x 2^k-1 + 1 then the worst possible thing happens and only every third urinal gets filled, and f(3 x 2^k-1 + 1) = 2^k-1 + 1. (Yes, that's the same number, and the function's constant in between.) f(5) = f(6) = f(7) = 3, f(9) = ... = f(13) = 5, and so on.) Oscillations like this -- periodic in the logarithm of the problem size -- happen a lot in problems involving binary trees counted by the number of nodes. Still, it was a bit surprising to see this, because I'd never thought about the problem in the case of "unphysically" large n.

Exercise for the reader: invent a mathematically equivalent version of this problem that doesn't involve urinals.

Two baseball games the same?

2009-08-22T16:54:00.001-04:00

The Yankees and Red Sox have played each other two thousand and something times, as the good folks on Fox told us, so I started to wonder: which baseball teams have played each other the most times? If I had to guess it's Giants-Dodgers; Wikipedia agrees with me but gives no source. Apparently Cardinals-Cubs, Cardinals-Pirates, and Cubs-Pirates are all a close second. These are the ones you'd expect if you take into account when teams changed divisions, etc.

Anyway, trying to find this out I found a blog post entitled Have Two Baseball Games Ever Played Out Identically?. The answer is no, but "identically" is defined a bit too strictly; (say) a groundout to second and a groundout to shortstop are counted as different. And the metric that the author uses for similarity of two games A and B is, I think, the number of times where the nth plate appearance in games A and B had the same outcome. Intuitively I think you'd want to line up innings with each other. Two "most similar" games should at least have similar-looking line scores. I think what one wants is some notion of "edit distance" between games, and defining that is hardly trivial.

I've sort of poked at this before: in 2007 I asked what's the most common line score in connection with a promotion that MLB did for that year's all-star game.

There's a nice combinatorial/probabilistic question hiding here; I've seen results on, say, the probability that two randomly chosen permutations of [n] have the same cycle type, or the probability that two binary trees with n labelled nodes have the same shape. Baseball games are combinatorial structures, and I'm not just saying that to justify the fact that I'm probably going to spend six hours today watching baseball. (The Yankees and Red Sox are on TV now, the Phillies and Mets later.)

A number-theoretic tangent for your Saturday afternoon

2009-08-15T15:42:00.002-04:00

You may know that 1001 has a simple prime factorization, namely 1001 = (7)(11)(13).

And of course 1000 has a simple prime factorization, namely 1000 = (2³)(5³).

The natural question to ask at this point, to me, is "how often does this happen?" Of course one has to define "this". One question is "how often are there two consecutive numbers that have all their prime factors less than or equal to 13?" There seem to be finitely many, and after I compiled a list I googled a few numbers from it and discovered that David Rusin had also done so. In case you're wondering why I conjecture there are finitely many: the number of integers less than n with all prime factors at most 13 is proportional to (log n)⁶. (The exponent 6 comes from the fact that there are six primes which are 13 or less.) So the "probability" (in the usual heuristic number-theoretic sense) that a given number n is "13-smooth" is the derivative of this, and thus of the order of (log n)⁵/n. The "probability" that two consecutive numbers are "13-smooth" is on the order of the square of this "probability", i. e. (log n)¹⁰n^-2, and the integral of that from, say, 2 to infinity converges. Nothing is special about 13 here; there should be finitely many pairs of consecutive "p-smooth numbers" where p is any prime.

(Rusin's list, by the way, was something he compiled to illustrate how one might calculate logarithms; since 1000 ~ 1001, we can take common logs and get 3 ~ log(7) + log(11) + log(13). Given enough relations like this one can solve for the logarithms themselves.)

Alternatively, we can define the "roughness" of n as (log p)/(log n) where p is the largest prime factor of n. I call it "roughness", not "smoothness", because if it's smaller than the corresponding number is smoother, i. e. has comparatively small prime factors. This naturally compensates for the size of the number; if I recall correctly the proportion of numbers less than n with roughness less than r approaches some limit (a function of r) as n goes to infinity. (I only dabble in analytic number theory so I can't provide a source off the top of my head.)

It seems reasonable then that there should be a similar limit for pairs of consecutive numbers. Then empirically it seems that the probability that n and n+1 both have roughness at most (log 13)/(log 1001) is about 1 in 250. The pairs of numbers that are "at least as round" as (1000, 1001) in this sense are

(80, 81), (224, 225), (1000, 1001), (1715, 1716), (2079, 2080), (2400, 2401), ...

and it seems like about one in 230 pairs of consecutive numbers have this property (4291 in the first million). As is often the case, the interesting thing is that the limiting probability appears to exist and be neither zero nor one.

Postscript: I know some readers will be offended by my use of "probability" in this number-theoretic sense, because the prime factorization of a number is hardly a random object! But I'm a probabilist; this is how I think.

Mathematicians in today's New York Times crossword

2009-08-13T09:04:00.000-04:00

A clue from today's New York Times crossword puzzle: "Mathematician Post or Artin". (Four letters. If you don't know the answer, click on the links.)

The crossword blogs (here, here, here) think this was an unfair clue; this one says that "Neither [...] will be familiar to most solvers, or even to all mathematicians."

I got this with no problem. But it took me a moment, because the son of the Artin the clue was about was one of my professors as an undergrad. A few commenters here and there say they needed some of the crossing letters to decide which Artin the clue referred to.

Student "entitlement" to grades

2009-08-04T14:03:00.001-04:00

An interesting statistic from this article from the Madison (Wisconsin) Times: in fall 2008, the average grade in social work courses was 3.70 on a 4.0 scale, and the average grade in mathematics courses was 2.79. (The article doesn't indicate why these two departments were chosen, but I suspect they're at the extremes of the distribution.) This is a fact offered in an article about how students feel more "entitled" to high grades than in the past.

I don't want to comment on how students may or may not feel entitled to high grades. Most of the information I've seen indicates that this sort of entitlement is more common now than in the past; I haven't been teaching long enough to feel like I can comment intelligently on historical trends. (And I wouldn't want to include data from when I was taking classes, because my friends and I may or may not have been a good sample.)

From 3σ → left.

When 2+2 = 5

2009-08-01T13:17:00.003-04:00

From "you suck at craigslist:" 2+2 = 5. People selling things on craigslist who want $x for one of some item and more than $2x for two.

I'm pretty sure I once saw somebody selling T-shirts on the boardwalk in Atlantic City for "$3, 3 for $10." Or it might have been "$4, 2 for $10" or "$2, 4 for $10". In any case, it didn't make sense.

I'm sure there are cases where this sort of pricing structure actually makes sense, but I can't think of anybody. (I also wouldn't be surprised to learn that economists have a name for it.) Anyone want to try?

Fields of onions

2009-07-29T10:32:00.000-04:00

The Onion, commenting on Sarah Palin's resignation as governor of Alaska, writes that "Nothing can distract her laser focus from the ultimate prize: the Fields Medal.”

But Palin is 45, and the age limit for the Fields is 40. Perhaps she should aim for the Abel Prize instead?

(Note to the humor-impaired: this is not meant to disparage the Abel Prize.)

Plats diviseurs, or how the French cut cakes

2009-07-27T16:29:00.000-04:00

Apparently in France they have an interesting solution to cake-cutting problems -- a plate with markings on the rim for the proper place to cut into 3, 5, 6, 7, or 9 slices, called the plat diviseur. See also here. You can buy them here; the site is in French. Some especially ornate examples are due to Paul Urfer, who appears to be the original inventor.

I found out about these from The Number Warrior, Jason Dyer. Unfortunately I have no use for one of these, because I live alone, in a small apartment where I couldn't reasonably have enough people over to need a whole cake, and so I do not buy a whole cake at once.

I suspect I have some French readers. Have you seen these before?

A meta-proof

2009-07-24T10:52:00.002-04:00

A meta-proof of P=/!=NP, from the Geomblog in 2004. (That's "equals or does not equal".)

Note that you don't need to know anything about the P vs. NP problem to find it funny.

(via Michael Trick.)

A number-theoretic coincidence

2009-07-21T10:00:00.001-04:00

An interesting little tidbit from Tanya Khovanova: consider the Pythagorean triple 3² + 4² = 5², in which all three numbers are consecutive, and another similar coincidental-seeming equation 10² + 11² + 12² = 13² + 14². These are the first two elements of a sequence of similar equations, with k+1 squares on the left-hand side and k squares on the right-hand side, which she presents there.

Still perhaps coincidental is the fact that 3² + 4² = 5² and 3³ + 4³ + 5³ = 6³. Of course once you see these it's tempting to check if 3⁴ + 4⁴ + 5⁴ + 6⁴ = 7⁴. (It doesn't.) In fact, for n ≥ 4,

3ⁿ + 4ⁿ + ... + (n+2)ⁿ < (n+3)ⁿ

and here's a proof. I'll prove it for n ≥ 5. It suffices to show that

(3/(n+3))ⁿ + (4/(n+3))ⁿ + ... + ((n+2)/(n+3))ⁿ < 1.

Call the left-hand side f(n). But the last term on the right-hand side is decreasing in n, and for n ≥ 5, is at most 16807/32768 (its value at 5). Now, we can write the left-hand side of the above inequality as

((n+2)/(n+3))ⁿ (1 + ((n+1)/(n+2))ⁿ + (n/(n+2))ⁿ + ... + (3/(n+2))ⁿ)

and each term in the second factor is at most ((n+1)/(n+2))ⁿ times the previous one. So we have

(1 + ((n+1)/(n+2))ⁿ + (n/(n+2))ⁿ + ... + (3/(n+2))ⁿ) > (1 + r + r² + r³ + ...)

where r = ((n+1)/(n+2))ⁿ. Of course the right-hand side of the previous inequality is 1/(1-r). r is positive and decreasing in n, so 1/(1-r) is as well. Since n ≥ 5, 1/(1-r) is bounded above by its value at 5, which is 16807/9031. Thus for n ≥ 5,

f(n) < (16807/32768)(16807/9031)

and the right-hand side is easily checked to be less than 1.

For n = 4 this proof doesn't work, because I threw away a bit too much in bounding the sum of a finite series by the sum of an infinite one, but it's easy to check.

In fact, f(n) approaches 1/(e-1) as n goes to infinity.

Edit (8:41 pm):: See also The Everything Seminar.

News from Course XVIII-P

2009-07-20T22:38:00.001-04:00

Glimpi's conjecture, the Holy Grail of numeric set lassitude mathematics, has been proven.

"Roommates" is a euphemism?

2009-07-16T18:58:00.003-04:00

I'm at the Cornell Probability Summer School. (This announcement is too late for anybody who wants to find me here, as it's almost over! But I have been tracked down by at least one fan.)

In a lecture here this morning, Ander Holroyd spoke about the stable marriage problem and variations of it involving point processes (see this paper of Holroyd, Pemantle, Peres, and Schramm, which I've mentioned before, for details). The goal of the problem is to pair up n men and n women in such a way that no two people who aren't married to each other prefer each other to their current partners; this is called a "stable matching" and one always exists.

The original paper on the stable marriage problem is that of Gale and Shapley, in 1962. This paper also talks about the "stable roommates" problem, which is the analogous problem where everybody is of the same gender. Rather surprisingly, I never realized that "roommates" might be a euphemism here, which is something that Holroyd pointed out this morning to quite a bit of laughter.

Batting under .200

2009-07-15T22:51:00.001-04:00

Stat of the day (from baseball-reference.com) has a list of players who went an entire season, had enough at bats to qualify for the batting title (I forget the statistics for this, but this basically means they have to play regularly), and are batting under .200.

Most of them are from a long time ago. Why? Because .200 is well below average and always has been (which is why the list was worth compiling) and the variance in batting averages has gone down as the standard of play has improved. Stephen Jay Gould wrote about this in Full House: The Spread of Excellence from Plato to Darwin; the argument is roughly that as baseball scouting and training has gotten better, there are not as many bad pitchers in the major leagues as there were in the past, so players can't inflate their batting average that way. (I'm in Ithaca and my copy of the book is in Philadelphia, so I can't check if I'm stating this correctly.)

A puzzle

2009-07-11T19:38:00.003-04:00

2²⁹, expressed in base 10, is a nine-digit number. All nine of its digits are different. Find the digit that is missing without explicitly calculating 2²⁹. (Thanks to Kate for this one; a solution is there, so don't look until you've thought about it.)

Problems that are hard for intermediate values of some parameter

2009-07-05T16:37:00.000-04:00

In Clifford Henry Taubes' review of Monopoles and three-manifolds, by Peter Kronheimer and Tomasz Mrowka (citation information; article), near the end of the first paragraph the authors mention the problem of classifying compact manifolds with the homotopy type of the n-sphere. In any dimension there is exactly one. The history of this problem is roughly as follows:

n ≥ 5: Smale, 1960 (and Stallings at around the same time)

n = 4: Freedman, 1980

n = 3: Perelman, early 2000s (this is the Poincare conjecture)

n = 2: "follows from the Riemann mapping theorem"

n = 1: "a nice exercise for an undergraduate"

So in low dimensions the problem is easy, or at least doesn't require "modern" apparatus; in high dimensions it's harder (Smale and Freedman both got Fields Medals); in "middle" dimensions (like 3) it's the hardest, or at least took the longest. It's my understanding that it's pretty typical in geometry/topology for the three- or four-dimensional cases of a problem to be the most difficult?

Can you think of other problems (from any area of mathematics) that have a similar property -- that they're hardest for some medium-sized value of whatever a natural parameter for the problem is? (Yes, it's a vague question.)