Here is another Matryoshka problem - well not really, since I can’t prove that the second problem is “strictly harder” than the first in any meaningful way, but it does have the property that the most intuitive trick needed to solve the first one fails on the second one:

Timothy Gowers posted a fairly classical “paradox” in probability involving two boxes:

original post

My analysis:

Note that the guy who gives you the box must pick (a, 2a) with equal probability for every a - i.e., he needs to be able to pick a real number uniformly. Unfortunately, this is impossible.

This is actually a common sleight of hand that many probability “paradoxes” use at some level. You can increase your “defense against probability paradoxes” by adding this to the list of things to check against every time you find a strange probability situation, in the same way that recognizing Russell’s Paradox counters many logic “paradoxes.”

—

Now the inner doll. Prof. Gowers attributes this one to Noga Alon:

original post

These two problems are similar in spirit. However, the trick that works for the first one no longer works here: we have a very well-defined distribution! So we have to dig a little deeper. Here is my take:

In the paradox, we considered the random variable of the values of the two envelopes (call them and , and proceeded to divide the probability space into a series of sums x_i (where ), seeing that for all i. Then we did an implicit sum of all of these equations to conclude that .

The problem is in the sum - we cannot do this summation when the expectation of X and Y are infinite (we can easily check, by the way, that and are both infinite), so we cannot conclude that one is larger than the other. Here is a clearer example: consider the list of inequalities , , … each one of these statements is true, but it makes no sense to then argue that , because the sums diverge and cannot be defined. If you track the list of inequalities in the problem, you will notice the exact analogous chicanery going on, just with different numbers.

The cool lesson form this M-2 pair is that I am reminded again to appreciate why math books always mention “boundary cases” like infinity and deal with them very carefully. Usually we see them as just stupid limitations for corner cases, but this is a case where not thinking about the clauses on these border cases can mislead (to be honest, I never remember these boundary cases, like the algebra theorems that hold for every ring except the zero ring).

By the way, I bet there is some way to turn each one of these into a “paradox” in their respective fields. Probability is just riper for these conundrums since the problems offer more intuitive statements.

-Y

Source: Gowers’ Weblog

Today, for unrelated reasons, elementary enumerative combinatorics came up twice at work, once from my boss and once from Alex Levin.

Problem:

Find the generating function for .

Proof:

Recognize that the coefficient for is the number of ways to sum (n+1) nonnegative numbers to get i (using the standard “stars and bars” argument. Thus, the generating function must be the power of the generating function which has coefficient 1 for each nonnegative integer, so our final function is .

Especially when the generating function is not provided, coming up with this proof might be difficult. To keep with the theme of these posts, it is more instructive to give a “dirty” proof where I struggle and find the answer in a more motivated fashion, in case I had to solve this problem with a gun to my head.

Proof 2 and analysis:

From a good angle and impeccable timing, disarm the gun with ninja tactics. If that is not an option, the biggest metaprinciple in combinatorics problems is to do small cases (this seems more true for combinatorics than for the rest of math, where small cases are frequently either too sparse and become unmanageable very quickly and/or too trivial to give enough information). Note that the n=0 case happily gives . No, this is probably not enough to guess the answer unless you know it already, so we save it as a base case.

The second tech is “how do I abuse the coefficients to make them talk?” The attack here is to look at how the objects are defined and find a way to relate the object to slightly augmented versions of itself and/or other things you already know. Hopefully, that would make more sense after I do the following.

So what are binomical coeffcients? At their most basic level, they are defined by base cases and . Hey - this caters to writing something as the sum of slightly “perturbed” versions of the same object, so we are on the right track. We now want to write out the coefficient of and try to line it up with a slightly different generating function so we end up using the above identity. It shouldn’t take long to see that if we shift the function by and subtract from itself, we (almost) get the function for (n-1): , which reduces to . Given our base case, we are clearly done.

I think this is called the “inverse binomial coefficient generating function.” Don’t quote me on it.

-Y
–
Source: Alex Levin

P.S. “Frequently, we prove the same theorem twice - once to show ourselves, once to show others.” - H. Nagy

P.S.S. I definitely came up with the second proof first.

This series of posts

This summer I’m attending a series of lectures on -homotopy theory being given at Columbia by Bhargav Bhatt; the seminar is being organized by Johan de Jong. I’m especially attracted to this stuff since I’m not sure which area of geometry/topology I want to go into, and this material combines algebraic topology with algebraic geometry. The idea in a nutshell is to use homotopy theoretic methods in algebraic geometry; more on this below.

However, my knowledge of the basic ingredients in the theory–e.g. schemes, sites, and model categories–isn’t too thorough.  In fact, one of my motivations for going to these talks is to improve my understanding of these ingredients by seeing them in action.

As for this series of posts, my motive is a bit more self-serving.  I’ll work out some concrete examples, flesh out explanations of things which confuse me, and so forth.  More importantly, I’m going to ask you readers for help.  (You’ve all been too quiet so far!)  At first most of what I write will be about ingredients used in the theory rather than anything about -homotopy itself, so there should be plenty of people who can help.

A quick note on motivating the concepts and constructions: the material I’ll be covering is mostly unfamiliar territory for me. So rather than parrot the motivations given to me (and likely screwing it up), I plan to discuss the math with minimal ado. With any luck, I’ll be able to look back later and talk about how we could have motivated things. So bear with me!

A note on the obvious: most or all of this series will follow the presentation of Bhatt,
but the errors are mine.

What is -homotopy theory?

For the rest of this post, I’ll give the gist of the idea behind the theory.  Schemes are interesting and homotopy theory is powerful, so let’s try and apply the latter to the former.  In “ordinary” homotopy theory (by this I’ll always mean the homotopy theory of topological spaces), homotopies are parametrized by the closed unit interval [0,1]. In -homotopy theory, as you may have guessed from the name, homotopies are parametrized by the affine line (taken over some fixed base scheme which for now we’re suppressing).

In modern terms, of course, if we want to “make a homotopy theory” then we have to find a category which contains a lot of information about schemes and then give it a model category structure.

However, algebraic geometry is littered with several different topologies. The most elementary one is the Zariski topology. In the classical case of affine varieties over an algebraically closed field , the Zariski closed sets are the vanishing sets of ideals of polynomials with coefficients in . As you can see, Zariski open sets are huge! While this is probably a disadvantage, the Zariski topology has one great advantage: it has very nice finiteness properties. For instance, a standard exercise in scheme theory is that any affine scheme is quasi-compact.

Past Zariski, one needs to refine what is meant by a topology.  This leads the the notion of a Grothendieck topology on a category (the case of an “ordinary” topology takes place on the category of open inclusions into a given topological space). The classic example here is the étale topololgy, which was used in solving the Weil conjectures among other things; this is a much finer topology than the Zariski one, but at the cost of Zariski’s nice finiteness properties. For -homotopy theory, a middle ground is used: the Nisnevich topology, which I’ll discuss in a few posts’ time.

An important point about sites (a site is a category equipped with a Grothendieck topology) is that they support the notion of a sheaf. Our model category, then, will be cooked up from a suitable category of sheaves on the Nisnevich site. Much more on this, much later.

There are several important points about the resulting homotopy theory. Since I don’t understand them and probably won’t at least until we get to them in the lectures, I’ll not mention any yet. I will, however, end with a family of questions:

Questions: Rational equivalence, which is used in defining the Chow ring of a smooth scheme, is parametrized by the projective line, . Now the Chow ring is a cohomology theory rather than something homotopical; still, I wonder what the relationship is here. What would happen to the Chow ring if we tried to define rational equivalence with ? Or if we tried to invent a -homotopy theory?

Here’s a rough plan of what’s coming up:

Next two times: simplicial sets, Serre and Kan fibrations, model categories, a model category structure on the category of simplicial sets, and more!

After that: the Nisnevich topology, construction of the -homotopy category and its model category structure, and some related theorems and constructions.

Hello internet! My name is Sam (Lewallen,) and I’m the third member of this intrepid triumvirate. I am interested in everything, though my specialized knowledge is limited basically to topology and geometry, knot theory in particular. I’ve worked on Khovanov homology, and the Volume Conjecture. I’m also hugely interested in neuroscience, i.e., figuring out how the brain works (ooooh consciousness!), and I would love if fancy math ends up playing a role.

I have lots of posts planned. Here are a few:

1. Alex and I want to do a series on zeta functions, the different types that there are and how they show up everywhere.
2. I, like everyone, am fascinated by the moments when natural numbers pop up in different places, out of the blue. For example, the fact that there are 5 convex regular polyhedra (why 5?!). I want to write a series of posts showing that ALL such “arbitrary” natural numbers can be derived from this 5! Less ambitiously, I want do describe as many situations as possible where this can be done. Any ideas? Here are two: The McKay correspondence says # of polyhedra => number of families of simple Lie algebras; I also think # of polyhedra => # of divsion algebras over . Which then says something about the number of generalized cohomologies you can have, according to some talk by Peter Teichner…
3. I have lots of obscure knot theory ideas I want to write about. I want to do overviews of the Alexander and Jones polynomials (and all their various definitions), and discuss some neat ways that they’re related, one, for example, involving random walks on diagrams and zeta functions (#1! #1!)

Do any of these interest anybody? Any other suggestions?

As for my personal info, I’m going to be a G1 at Princeton next year. Anyone gonna be in the area?

Goodbye, dear internet, for now.

One gratuity we mathematician wannabes love to throw around (especially around college age) is “degrees of freedom.” The jury is out on whether the physicist wannabes are more judicious when they do it, but most of us have developed at least a passable idea of when we seem to have enough “wiggle room,” at least erring on the side of assuming we have too much (when a problem looks difficult, say with an air of superiority: “mm. We cannot give up now, because we definitely have enough degrees of freedom.” which will earn you looks of awe when someone else actually solves the problem, giving you time to BS a reason on why you had enough degrees of freedom in the first place). The asymmetry is that we are actually usually very good at telling when we have very few degrees of freedom, which is why this problem scared the hell out of me, because at first glance it seems impossible (try, for example, f = 1 + x^2 + x^3 + x^4):

Take a polynomial f in Q[x]. Prove that we can multiply it by another polynomial in Q[x] such that the product contains only terms of the form ax^p, a in Q and p prime.

Proof and Analysis:

Consider Q[x] modded out by (f). This is a vector space of dimension deg(f) (read: finite). Hence, there is some nontrivial linear combination of monomials with prime degree that sum to 0 (mod f), which is equivalent to our claim.

Alternatively (this is how I got it at first): consider the k-dimensional vector space V of polynomials generated by f, xf, … x^{k-1} f. This is a k-dimensional vector space inside the vector space X generated by 1, x, … x^{deg(f) + k - 1}. Note the co-rank of V inside X is independent of k! Now consider the vector space P generated by x^p, p prime. P’, the intersection of P and X, has increasing rank as k goes to infinity, so eventually P’ has rank exceeding the corank of V, meaning P’ and V has some nontrivial intersection. Note this proof is basically the same as the first proof, but has slightly different intuition.

Andrew Dudzik claims that he usually sees this problem with “prime” replaced with “powers of 2,” which is ingenious since it fools you into thinking you have to use powers of 2 somehow (whereas if your mathematical intuition is fairly strong you’d have a feel that the “primes” were just a red herring in this problem). I suggest that when you give this problem to your friends you use the even more devious version that I came up with: force the degrees of the monomials to be divisible by [deg(f) - 1].

-Y
–
Source: Berkeley Problems in Mathematics (de Souza, Silva) / Andrew Dudzik

I regretted not learning the basics well while I was in school. Blaming Math 55’s evolution is a cowardly excuse to not blame myself: it surely wasn’t purely the professor’s fault when the students - including myself - were very good as a unit at pretending to understand the material. This is of course why I always tell junior students to learn the basics well and not to skip too many classes, an extension of a popular phenomenon that I will coin as the “those who can’t do and those who f***ed up in their past, teach” principle. While (unlike seemingly everyone else) I did take my share of undergraduate courses, I am still sad that I never had a solid treatment of basic group theory. I knew the theorems and understood the definitions - something easy to do by osmosis - but I never got my hands dirty with problems with real, concrete groups, especially finite ones. The analogy is one between a reader and a writer - I can understand any paper that uses these concepts (and look up more obscure items as I need them), but I have very limited craft in dealing with these objects, to the degree that I am more comfortable in manipulating some of the more “difficult” objects like matrices, fields, algebraic varieties (not schemes. Those things still WTF me ;P) and CW-complexes. This is a gaping hole in my swiss cheese of mathematical knowledge.

This is not a criticism of my peers (most of whom will surely become better mathematicians than I will). Their frequent objection to my view on basics is the following: with the obvious exception of representation theory, we can honestly do a lot of “higher” algebra at a concrete level without really getting dirty with groups, because we are usually using deeper facts about more sophisticated structures. For example, when was the last time you actually used Sylow’s theorem? My objection with my flimsiness with groups is more of a meta-learning concern - I think every branch of mathematics (or general skillset in life, for that matter) can teach a way of thinking and a way of solving problems, both invaluable even if I never use the knowledge in that branch. While I will probably never use Sylow’s Theorems in future research, having used them to solve certain problems will have trained me to think about certain types of general problem-solving situations, and I never think that is a waste of time.

The point of that verbose preface was… to keep myself honest, I’ve been collecting some (easy) algebra problems and working on them. They’re not “deep,” they’re fun and easy, and they teach many little facts that I never knew (and probably will never use). I might post more if I find them, but for now, something cute:

Every finite group of order >=3 has a nontrivial automorphism.

Proof (yeah yeah, I know all of you think this is trivial. I am a beginner remember):

Suppose the group G is not abelian. Then there is some nontrivial element a. Conjugation by a is a group automorphism, and is nontrivial on any element b which doesn’t commute with a, so we are done. In the case that G is abelian, we know G is isomorphic to a direct product of cyclic groups, which we can think of as Z_k under addition. If any one of these, say Z_t, has order >= 3, mapping the generator 1 in that group to an integer in Z_t relatively prime with t and imposing the identity on all the other cyclic groups is a nontrivial automorphism. The only time when this doesn’t work is if all of our cyclic groups has order 2… but the moment we have two of these, we can just define an automorphism to send the generator 1 in one of the groups to the generator 1 in the other (and vice-versa), again applying the identity to everything else.

Feel free to give me more exercises like this!

-Y
–
Source: Berkeley Problems in Mathematics (de Souza, Silva).

I don’t enjoy studying for exams very much. Rather than despair, however, I channeled my energy into a creative outlet:

300 meets the Bianchi identities: the first “No Weil!” Comics production, here.

Can you spot all four versions of the Bianchi identity I used?!?

Is there a basis of the space of linear transformations from to itself made of only invertible elements?

Proof:

Well yes. It is kind of strange though. Let’s think in matrix-land first and think of these as matrices since they are easier to conceptualize. Just take your basic Kronecker basis (the matrices containing 1 in exactly one position and 0 elsewhere) and add I, the identity matrix, to each.

To see that they span, take any matrix A. Consider the linear combination of the Kronecker basis you would use to get A. That linear combination with the new basis elements will sum to A plus some multiple of I. Since you can add the n diagonal matrices and then scale ot make I, you can subtract copies of I to get your desired matrix.

To see that they are linearly independent, you can either do it directly or just dimension count. I have n^2 vectors which span a dimension n^2 space, so I am done.

It is kind of weird that this is true (is this true for ?), but it is nice to have invertible matrices. I’m going to try to find problems where I can use this fact, since it is a pretty strong property to have “for free.”

-Y
–
Source: Linear Algebra Problem Book (Halmos). God I love Halmos.

I keep telling myself that I’m a geometer/topologist, but I keep acting otherwise. I’ve been attending lectures by Imre Leader at Cambridge on Hypergraph Games. I attended the first lecture on a whim, having never thought about games or graphs or combinatorics in my life (other than my odd fascination with topological tic tac toe). Five minutes into the lecture, I realized that topological tic tac toe is a hypergraph game! Moreover, I found the lecture thoroughly entertaining, and I’ve been following the course attentively since. So in this post, which is sort of an appendix to my previous posts (1, 2) on topological tic-tac-toe (henceforth called T4 for short), I will discuss the wider context of hypergraph games. Much of the general presentation here follows Leader’s lectures.

Although I’ll briefly indicate how T4 fits into this larger picture, let me give the short answer up front: game-theoretically, it’s a fairly boring and straightforward example. But as a visualization exercise or as a gimmick, I still think it’s groovy.

Throughout this post, all sets will be taken to be finite; this isn’t essential everywhere, but it simplifies certain things. The data of a hypergraph game are a set called the board and a collection of subsets of which are called the winning lines of the game. Two players (P1 and P2) take turns marking elements of ; each element can only be marked once. The game ends when one player has marked all the elements of a winning line; if the board is exhausted with neither player winning, then the game is a draw. A particular state of the game is called a position; precisely, it is a choice of two disjoint subsets of —those marked by P1 and those marked by P2—such that P1 has marked either one or zero more elements than P2 has. Note that this necessarily encodes whose turn is next.

We are most interested in what happens when P1 and P2 both play with perfect strategy. A winning strategy (for P1) is a function from the set of positions on the board to the set of possible moves such that in any play of in which P1 plays according to , P1 will win. A drawing strategy (for P1) is the same, except the guaranteed result is that the game is a draw or P1 wins.

Proposition 1: For any hypergraph game , exactly one of the following holds:

1. P1 has a winning strategy
2. P2 has a winning strategy
3. both P1 and P2 have a drawing drawing strategy

Proof: The proof is by “backtracking.” We say a position is a P1 winning position if whenever the game is played from this point (with perfect strategy), P1 wins; define similarly the notions of a P2 winning position and a drawing position. (We allow such positions to be such that the game is already finished.) Let . Then every position in which all elements are marked is one of these three possibilities: winning for P1 or P2, or drawing.

Inductively, suppose all positions with at least elements marked is either winning for P1 or P2, or drawing. Let be a position with elements marked; without loss of generality, suppose P1 is next to move. There are finitely many possible resulting positions after P1 moves. If any of these are P1-winning, then is P1-winning. If all are P2-winning, then is P2-winning. If none are P1-winning and not all are P2-winning then by the inductive hypothesis at least one must be drawing. Hence P1 will play for a draw and is drawing. Hence, by induction, the initial position in which no elements of are marked is either P1-winning, P2-winning, or drawing; the Proposition follows, as the status of the initial position is the status of the game itself. Q.E.D.

Hence we can refer to a given game as either a P1 win, a P2 win, or a draw. In fact, we can improve on this. You may wish to try and prove this yourself before reading the given proof.

Proposition 2: No hypergraph game is a P2 win. In particular, if a hypergraph game can never end in a draw, then it is a P1 win.

Proof: We use the technique of “strategy stealing.” Let be a winning strategy for P2; we will find a winning strategy for P1, yielding a contradiction. Note that for either player an extra move can never hurt (think this through!). P1 begins by playing anywhere, say . Then it is as if P1 were the second player with an extra element marked. So playing according to is a win for P1; if at any point says P1 should play at , then P1 plays anywhere unmarked, say , and on his next turn resumes play according to . In the future, if calls on P1 to play at , then P1 plays anywhere unmarked and then resumes , and so forth. Hence P1 has a winning strategy. Contradiction! Q.E.D.

Note that the strategy-stealing proof of Proposition 2 is completely non-constructive! One theme in the theory of hypergraph games is the search for explicit winning strategies to particular games. This is very hard! Many (most?) of the known winning strategies for small games are by case analysis. If you constructed winning strategies to the various flavors of T4 similarly to the way that I did, then you were essentially doing clever case analysis, in which you used observation and/or symmetry to cut down the number of cases considered. This quickly becomes unwieldy for larger boards.

While there seems to be a dearth of general techniques for constructing winning strategies, there is one which helps for constructing drawing strategies—the technique of a pairing strategy. Let be a hypergraph game. Suppose one can choose exactly two elements from each winning line such that all elements are distinct; we call this a splitting of the board. Then P2 has an easy drawing strategy: whenever P1 plays by marking one member of a given pair, P2 responds by marking the other member. Since by Proposition 2 a P2-winning game is impossible, it follows that any hypergraph game which admits such a splitting is a draw. Exercises 1-3 below give some practice with splitting strategies.

We conclude with what may be a surprising fact to some.

Warning: Based on our intuition and what we have seen in the various flavors of T4, one might conjecture the following: if a hypergraph game is a P1 win and is a collection of subsets of which contains as a subset, then the hypergraph game is a P1 win as well. This is false, and the phenomenon is known as non-monotonicity. Exercises 4 and 5 below are a do-it-yourself example.

Exercises:

1. Use case analysis to show that the games of 3×3 tic-tac-toe and 4×4 tic-tac-toe are draws.

2. Construct pairing strategies for 5×5 and for 6×6 tic-tac-toe, showing both are draws.

3. Given a pairing strategy for x tic-tac-toe, construct one for x tic-tac-toe. Conclude that for , the game of x tic-tac-toe is a draw. Why wouldn’t this work for x tic-tac-toe?

4. Let be the set of vertices of a binary tree of depth ; that is, and the bottom row has leaves. Let consist of the subsets of which are direct paths to leaves along the tree; there is one of these for each leaf. (By direct, we mean each step descends one level.) Show that the hypergraph game is a P1 win in moves.

5. Let be the game of the previous exercise on a binary tree of depth . Add one winning line to the set such that the resulting game is a draw, proving that non-monotonicity can occur.

Inspired by Tim Gowers’s illuminating informal discussions of mathematical topics, and in particular this one on vector spaces, I am starting my own “Shoulda Series.” That is, a series of notes on things about which I might have said: “Someone should have told me this a long time ago!” In particular, I don’t want to use this series to “give away” the sorts of things you should really figure out for yourself.

Question: Why do we avoid choosing bases for vector spaces whenever possible? In particular, why is an isomorphism defined independent of bases “better” than one which uses bases?

One of thousands of possible answers: Since I’m a geometer at heart, I think the following is a great reason. In short, the moral is: basis-free isomorphisms generalize to vector bundles and basis-dependent ones usually do not. This is because “choosing a basis” of a vector space is the point-wise analogue of the “choosing a local trivialization” of a vector bundle. To do anything globally, one generally needs to use several different trivializations; a bona fide isomorphism of vector bundles requires a family of vector space isomorphisms compatible with the transition functions between the various trivializations. (For those who know what this means, the precise check is that the Cech 1-cocycles corresponding to the bundles in question differ by a Cech 1-coboundary, where the coefficient sheaf is the constant sheaf associated to .)

For a wealth of examples, consider the following. Any two finite-dimensional vector spaces (over the same field) are isomorphic, but not naturally so. But there are usually several different isomorphism classes of (real or complex) vector bundles of a given dimensionon on a given space.

A more specific example will also bring out a slight improvement of our moral above. Let be a real vector space and be a real vector bundle. Recall that the isomorphism between and its dual is not natural. Hence is not always isomorphic to its dual . (Here, is the trivial vector bundle .) But if is given an inner product , the isomorphism becomes natural: the map is simply . So if a vector bundle admits an inner product (in the sense of vector bundles), then we should expect an isomorphism . Indeed this is the case, and in fact this is a common phenomenon: using a partition of unity, you can check that every real vector bundle on a paracompact base space admits an inner product.

However, the situation is different with complex vector bundles. Let be a complex vector bundle. While every complex vector bundle paracompact base space admits a Hermitian inner product, this product induces an isomorphism between the dual bundle and the complex conjugate bundle ; neither of these need be isomorphic to itself.

For example, consider the tangent bundle to the Riemann sphere and its dual, . Considered as real 2-plane bundles, these are isomorphic since is paracompact. But they are non-isomorphic as complex line bundles. For readers familiar with characteristic classes, there is an easy way to see this algebraically. The Chern classes of a complex vector bundle take values in the integral cohomology of the base space. They obey the relation , so if for any odd , then is not isomorphic to . The Stiefel-Whitney classes of a real vector bundle obey the same law. But since they take values in cohomology, and the relation is an equality!

Aside: Unoriented phenomena (e.g. Stiefel-Whitney classes) tend to use relations, while oriented phenomena tend to use relations. Complex vector spaces have a canonical orientation on their underlying real vector bundles, so complex phenomena (e.g. Chern classes) fall under oriented phenomena. Examples are mod 2 versus oriented intersections (see Guillemin & Pollack, Differential Topology) and the oriented versus unoriented versions of Poincaré duality (see Hatcher, Algebraic Topology, freely available online). While I’m on the subject of references, two great references for vector bundles and characteristic classes are Milnor & Stasheff’s Characteristic Classes and Hatcher’s Vector Bundles and K-Theory (the latter is unfinished and freely available online).

We conclude with our improved moral statement.

Improved moral: A natural isomorphism of vector spaces generalizes to vector bundles. An isomorphism of vector spaces making use of a structure which “globalizes” well (e.g. inner products, when the base space is paracompact) will also generalize to vector bundles. Other isomorphisms often will not.