Category Archives: fun problems

Some Mathoverflow challenges

Mathoverflow has become a roaring success! The site is getting about 20-25 questions a day, and about 95% of them get answered. But one of the problems with being so successful is that a question rarely remains on the front page for more than a day. Here are some which I believe are interesting, challenging and solvable.

Why do flag manifolds, in the P(V_{\rho}) embedding, look like products of \mathbb{P}^1‘s.
\mathcal{F}\ell_n and (\mathbb{P}^1)^{\binom{n}{2}} have the same multi-graded Hilbert functions. Is there any reason for this?

Smooth proper schemes over \mathbb{Z} with points everywhere locally,
Non-simply-connected smooth proper scheme over \mathbb{Z}?.
The condition of being smooth and proper over \mathbb{Z} appears to be very restrictive. Can you construct examples with these properties?

Pencils with many completely decomposable fibers
Does there exist a pencil of hypersurfaces in \mathbb{P}^4, which is not a cone over a pencil in \mathbb{P}^3, but has three fibers which are unions of hyperplanes?

Are submersions of differentiable manifolds flat morphisms?
This is basically a commutative algebra question: Is C^{\infty}(\mathbb{R}^{n+1}) flat over C^{\infty}(\mathbb{R}^{n})? Several people made progress, but no one finished it off.

Five Front Battle
Two generals, with armies of equal sizes, must apportion their troops between five fronts. On each front, the army with more troops will win; the nation which wins three fronts will win the war. What is the optimal strategy?

Spanning polynomials with powers

So, here a cute little algebraic question that I came across thinking about a finite groups question Noah asked me (he or I might blog about that later):
Choose your favorite set of m linear polynomials in n variables (if you don’t like coordinates, your favorite m element subset of your favorite n dimensional subspace). When do the the jth powers of these polynomials span all polynomials of degree j?

Of course, for j=1, this is easy. It isn’t immediately clear what happens even for j=2; I think the answer is something like you must contain a subset of \binom j 2 polynomials such that no k dimensional subspace contains more than \binom k2 of them. Any thoughts? (Also, special bonus bonus points to whoever figures out what representation theory question this is supposed to solve).

Is massively collaborative mathematics scalable?

I’ve been watching, though not particularly intently, Tim Gowers’s attempt massively collaborative mathematics. I’m not sure if I’ve looked hard enough to judge, but it certainly looks as though it were quite successful. This of course, answers Tim’s original question “is massively collaborative mathematics possible?” positively, but I still have to wonder if it’s sustainable in the long term. Of course, it never seems smart to bet against the possibilities of the Internet combining disperate contributions into valuable knowledge. Certainly, I would say people have tended to underestimate the possibilities of real advances coming from the technology of wikis and blogs. At the same time, it seems hard to imagine that people will really have the energy and time, not to mention mental organization, to follow several such projects at all closely. One of Tim’s take away lessons from the project seemed to be that it shrank in number of participants faster than he expected. And this was in a collaboration prominently featuring two Fields medalists and promoted on what is probably the world’s most prestigious math blog! It seems more likely that as the number of such projects expands the average number of participants will shrink until most are functionally equivalent of the collaborations we are used to today, just with more efficient coauthor location. By which I mean, the important advance will not be the number of people involved, but rather the identity of them.

Not that the value of efficient coauthor location should be minimized! The broader array of people we can stay in contact with due to the Internet is a huge boon to mathematics. It’s just that I suspect any concern over how we will deal with the allocating credit in a 20 person collaboration is a bit premature, at least outside of exceptional cases.

On the other hand, I’m kind of excited about the possibility of proving myself wrong, but haven’t been able to come up with any good projects. Does anyone wanna do that massively collaboratively?

Satisfying Solution

In my previous post, I posed the problem:

Problem Let f(x,y) and g(x,y) be polynomials in two variables such that \lim_{t \to \infty} f(t,t^{-1}) and \lim_{t \to \infty} g(t,t^{-1}) exist. Show that the determinant

(\partial f/\partial x) (\partial g/\partial y) - ( \partial f/\partial y) (\partial g/\partial x ) is not a nonzero constant.

Dennis gave a nice, if brief solution, and Pace fleshed it out a bit in an e-mail to me. I now understand where the mysterious “trace operator” in the solution comes from, and that’s what I want to explain here.

First, Dennis’ solution. For any polynomial h(x,y) = \sum h_{pq} x^p y^q, define T(h) = \sum h_{pp}/(p+1). We now observe the mysterious identity

T( f_x g_y - g_x f_y) = \sum_{m = -\infty}^{\infty} m \left( \sum f_{(i+m)i} \right) \left( \sum g_{j(j+m)} \right).

Now, if f(t, t^{-1}) contains no positive powers of t, then $\sum f_{(i+m)i$ is zero for positive m. Similarly, the hypothesis on g forces the third factor to be zero for negative m. And, when m=0, the m in front kills the summand. So the conditions on f and g force T(f_x g_y - f_x g_y) to be zero. In particular, f_x g_y - f_x g_y is not a nonzero constant.

It’s very slick. The only question is, what is T? The explanation, as it turns out, gives us a nice chance to practice our differential forms.

Continue reading →

Two fun problems

One of the points of this blog is for us to share the little problems we’d be discussing at tea if we were all still in Berkeley.  Here are two that came up in the last couple weeks.

As we all know, you can never know too much linear algebra.  So here’s a fun little linear algebra exercise that Dave Penneys asked us over beers on friday:  “Which matrices have square roots?”

The second question I don’t know the answer to, but I haven’t looked too hard.  The other week Penneys and I were trying to compute an example in subfactors and stumbled on the following interesting question about infinite groups (somewhat reminiscent of this old post). When can you find a group G and a proper inclusion G->G such that the image is finite index?

There’s the obvious example Z.  But once you start adding adjectives it starts getting tricky.  We were looking for a finitely generated group all of whose nontrivial conjugacy classes are infinite.  If only I knew more geometric group theory…

Stable marriages

So, one of my odd mathematical fixations (totally unrelated to my research) is the stable marriage algorithm. Don’t ask me why, I just find it a remarkably appealing piece of math.

The stable marriage algorithm is, unfortunately, not a fool-proof way of keeping one’s marriage stable, but rather a way of taking two sets of parties (the obvious example being a group of men and a group of women, though the real life applications tend to involve much more boring things like matching medical students to residency programs), who would like to be paired up with each other. But rather than decide who marries who in the normal way, they want to give a mathematician a preference list, and have him sort out things in a sensible way.

Being a mathematician, this chap first has to come up with definition of a rigorous “sensible.” Certainly things won’t work very well if after the matching, there are any couples who would prefer to give the mathematician the middle finger and elope with each other to Vegas rather than stick with their assigned mates. A matching with no such couples is called “stable.” Now, this doesn’t uniquely specify the matching, and could leave many people still unhappy (if one gender all has similar preference lists, somebody still has to take the duds), but anybody they prefer to their spouse will not want to leave their own spouse for our unlucky lover. But at least no couple can complain the mathematician that he should have matched them instead. Continue reading →

A probability puzzle

I learned this puzzle from Henry Cohn. Henry tells me it is probably due to Peter Glynn and Phillip Heidelberger (JSTOR).

I’ve just come back from trick-or-treating, and in my bag are two types of candy — peppermints and toffee. I’d like to know what fraction of the bag is peppermints. Not wanting to dump out that whole big bag, I’ll just draw a few random samples and make an estimate. (The bag is big enough that it doesn’t matter whether or not I return candies to the bag after sampling.) The responsible way to do this would be to decide ahead of time how many samples I will draw — say ten pieces — and stick to that plan. Instead, though, I decide to just sample for five seconds and count however much candy I can grab in that time. This would be fine too, if it took me the same amount of time to draw a toffee or to draw a peppermint. But it doesn’t. I can draw a peppermint from the bag in one second, while the toffee sticks to my fingers and takes three seconds to unwrap. This makes my sampling process flawed. Suppose that the probability of drawing a peppermint is p, and the probability of drawing a toffee is q (with p+q=1). So, for example, I might draw a toffee, a peppermint and then another toffee (which I would finish unwrapping after time expired). The probability of this sequence of draws is q*p*q and, if I encountered that series of draws, I would esitmate that my bag was 1/3 peppermint. In the table below, I have listed all possible sequences of draws, the odds of obtaining that sample, and the estimate that sample produces

Draws: PPPPP PPPPT PPPT PPT PTP PTT TPP TPT TT
Odds: p^5 p^4 q p^3 q p^2 q p^2 q p q^2 p^2 q p q^2 q^2
Estimate: 1 4/5 3/4 2/3 2/3 1/3 2/3 1/3 0

So the expected value of our estimate is
p^5+2 p^2 q+(3/4) p^3 q+(4/5) p^4 q+(2/3) p q^2 = \\ \hphantom{p^5+} (2/3) p +(2/3) p^2-(7/12) p^3+(1/20) p^4+(1/5) p^5 .
Note that this is not equal to the true value, p. It is a slight underestimate because those sticky toffee get counted more than their fair share. In statistical jargon, this is not a consistent estimator. Here is a graph of our estimate as a function of the true value of p.

candygraph.gif

Incidently, this has a “practical” application. Suppose a pollster comes to your door and asks what candidate you plan on voting for. If you suspect that he will poll for eight hours and then stop, you should stall as long as possible, as that will lead to a higher reported total for your candidate.

Ok, that was nifty, but it wasn’t the puzzle. Here is the puzzle. Suppose that I adjust my sampling procedure in just the smallest way: if I am still unwrapping a piece of toffee when time runs out, I don’t count it to my sample. So that changes the bottom row of our table as follows:

Draws: PPPPP PPPPT PPPT PPT PTP PTT TPP TPT TT
Odds: p^5 p^4 q p^3 q p^2 q p^2 q p q^2 p^2 q p q^2 q^2
Old Estimate: 1 4/5 3/4 2/3 2/3 1/3 2/3 1/3 0
New Estimate: 1 1 1 2/3 2/3 1/2 2/3 1/2 0

The new expected value of our estimate is p^5+2 p^2 q+p^3 q+p^4 q+p q^2=p. That’s right, this slight change made our procedure accurate again! So the puzzle is, why? I have two proofs, but they both involve some messy computations. There must be an argument which makes this just jump out at us. (Of course, there is nothing important about the numbers 3 and 5, or about having two types of candy. This happens with any number of types of candy, any unwrapping times and any sampling time, as long as the sampling time is longer than the longest unwrapping time.)

By the way, I was going to suggest that pollsters should use this modified sampling to defeat the attack mentioned above. But the modified method is vulnerable to a slightly more sophisticated attack: you should now answer slowly near the beginning of the day but rapidly at the end of the day. The modified method only works when the time to draw a particular candy is independent of past history, including being independent of how much history has passed.

Update: Terence Tao gives a very nice solution in the comments.

Theme and variations: Schroeder-Bernstein

Recall that the Schroeder-Bernstein theorem states that given two sets X and Y and injections f: X->Y and g:Y->X there exists a bijection h: X->Y. Probably most of our readers have proved this result at some point using the nifty ladder argument. If you haven’t seen the proof it’s covered nicely over on wikipedia (I find the “other proof” easier to follow).

My freshman year of college several of my classmates (me, Jared Weinstein, Haiwen Chu, and Mike Hill are the ones I remember) played a game of proving or disproving Schroeder-Bernstein in other categories. For example, if you have two vector spaces with linear injections both ways are they automatically isomorphic? If you have two groups with group injections both ways are they automatically isomorphic? (I don’t want to spoil your fun so I’ll put the answers to these two easy questions in comments.)

This is still a game I like to play when I run accross a new category to test my understanding. Plus it’s fun. Here are some more categories you might try (with *’s by the most interesting ones):

  • Abelian groups
  • Rings
  • *Fields
  • Topological spaces
  • *Finite topological spaces
  • *Vector spaces without the axiom of choice
  • *Free modules over a noncommutative ring

Put proofs/counterexamples/other suggestions in comments!