29 July 2009

Fields of onions

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

27 July 2009

Plats diviseurs, or how the French cut cakes




24 July 2009

A meta-proof

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

21 July 2009

A number-theoretic coincidence

An interesting little tidbit from Tanya Khovanova: consider the Pythagorean triple 32 + 42 = 52, in which all three numbers are consecutive, and another similar coincidental-seeming equation 102 + 112 + 122 = 132 + 142. 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 32 + 42 = 52 and 33 + 43 + 53 = 63. Of course once you see these it's tempting to check if 34 + 44 + 54 + 64 = 74. (It doesn't.) In fact, for n ≥ 4,

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

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

(3/(n+3))n + (4/(n+3))n + ... + ((n+2)/(n+3))n < 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))n (1 + ((n+1)/(n+2))n + (n/(n+2))n + ... + (3/(n+2))n)

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

(1 + ((n+1)/(n+2))n + (n/(n+2))n + ... + (3/(n+2))n) > (1 + r + r2 + r3 + ...)

where r = ((n+1)/(n+2))n. 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.

16 July 2009

"Roommates" is a euphemism?




15 July 2009

Batting under .200



11 July 2009

A puzzle

229, 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 229. (Thanks to Kate for this one; a solution is there, so don't look until you've thought about it.)

05 July 2009

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