Problems that are hard for intermediate values of some parameter

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.)

Brownies and space-filling curves

The Baker's Edge brownie pans, which are pans constructed in such a way that everybody gets an edge piece and nobody gets a piece from the middle, remind me of space-filling curves.

The isoperimetric inequality suggests that the only way to do the reverse -- to have pans where nearly everybody gets the middle and nearly nobody gets the edge -- is to have really big pans.

The Iranian election

The Devil Is in the Digits, an op-ed by Bernd Beber and Alexandra Scacco in Saturday's Washington Post.

This piece claims that the distribution of insignificant digits in vote totals in the recent Iranian election look funny, and that there's a good chance this is because the numbers were made up.

I haven't looked at the numbers myself, but this seems like an avenue worth pursuing.

Money with mathematicians on it

Banknotes featuring scientists and mathematicians. Including the two in-print US bills that we're all least likely to see: the $100 (Franklin) and the $2 (Jefferson). For the non-US readers: the $100 is the largest bill in general circulation. For some reason the $2 bill has fallen out of favor, and although it's legal it's very rare, to the point that some people don't know about them and urban legends circulate about the $2 being suspected as counterfeit)

There seem to be more "scientists" than "mathematicians" on the list, but this may just reflect the fact that there are more scientists than mathematicians in general. In fact, "scientist" is a broad enough category that I don't think too many people would describe themselves as "scientists" when asked "what do you do?", rather responding with something like "physicist" or "biologist"; but I think a lot of mathematicians would answer "I'm a mathematician" to this question. (This seems to correspond roughly with the way departments are organized in most universities; there's usually a "department of mathematics" but very rarely a "department of science".)

(via a comment at Gil Kalai's blog)

Edit, 6:20 pm: the linguists seem to be compiling their own list of linguists-on-money, over at Language Log.

The Math Factory?

On Sunday, June 14, in New York City, there was a Math Midway as part of the World Science Festival's street fair. The web page refers to it as a "traveling exhibit" so maybe it's coming to somewhere near you?

This is the first exhibit mounted by the Math Factory, which will be a full-scale museum of mathematics, incorporating the collection of the now closed Goudreau Museum, which was housed in a couple classrooms at a former school. This is the brainchild of Glen Whitney, who got a PhD in math, worked for a hedge fund for some time, and now is devoting himself to this museum, according to this article from the New York Daily News. Here is a list of exhibits they're planning and an interview about the museum that Whitney did in April in the oddly named online magazine gelf.

I found out about the midway from Quomodocumque and the Daily News article from My Biased Coin.

Incidentally, I'm not sure I like the name "Math Factory" for this museum. Factories are generally not pleasant places, and in addition they won't actually be manufacturing mathematics there.

When do you learn that the rationals are countable, and the reals aren't?

I'm currently teaching a course "Ideas in Mathematics" in our summer session. This is a course generally taken by students not in technical fields; quickly speaking, my syllabus is some basic number theory, different notions of infinity, some bits of geometry (polyhedra, letting them know that there is such a thing as non-Euclidean geometry, etc.), fractals and chaos, and a smattering of probability. This is a course that's not a prerequisite for anything and the students aren't going into fields where they'll need math, so I, like a lot of other people teaching this class, take the approach of showing them that "math is beautiful" rather than that "math is useful".

So today I'm showing my students that the rationals are countable, first by the standard proof and then by the superior Calkin-Wilf proof. I find the Calkin-Wilf proof aesthetically superior because the "standard" proof, in my opinion, is "really" a proof that the set of pairs of natural numbers is countable; we then just cross off the pairs which aren't in lowest terms as a sort of afterthought. As a result, it's difficult to answer questions like "what's the 1000th rational number in the `standard' enumeration?". Then I will show them that the reals are uncountable, using Cantor's diagonalization argument.

While preparing today's class, I realized that I don't know when I learned that the rationals are countable and the reals are uncountable. Is this even part of the "standard" curriculum for math majors? These feel like facts that I have always known; presumably I picked them up from some popular mathematics book at an early age. Do any of you remember when you learned this?

Odd periods in continued fractions

Here's a question. Why is the period of the quotients in the continued fraction of N^1/2 "usually" even? For example, if N runs over the ninety non-squares less than 100, then only 20 times does the continued fraction expansion of N^1/2 have an odd period. Of the 992 non-squares less than 1024, 157 have an odd period. Of the 9900 squares less than 10⁴, 1322 have an odd period. This is a sign that something is going on under the hood -- naively you'd expect half the periods to be odd.

Arnold has observed this, but only empirically; I first observed it from this problem from Project Euler.

The period of the continued fraction of N^1/2 is odd if and only if x² - Ny² = -1 has solutions in integers. All such integers, it turns out, have no prime factors congruent to 3 mod 4, which is pretty rare for large numbers. (The number of positive integers less than N with no prime factors congruent to 3 mod 4 is about N(log N)^-1/2.) For integers having no prime factors congruent to 3 mod 4, though, a paper of Etienne Fouvry and Jurgen Kluners shows that asymptotically at least 52% of such numbers have odd period, and at most two-thirds do.