More from Chris Grossack's Blog
Another day, another blog post that starts with “I was on mse the other day…”. This time, someone asked an interesting question amounting to “how many unordered rooted ternary trees with $n$ nodes are there, up to isomorphism?”. I’m a sucker for these kinds of combinatorial problems, and after finding a generating function solution I wanted to push myself to get an asymptotic approximation using Flajolet–Sedgewick style analytic combinatorics! I’ve never actually done this before, so I learned a lot, and I want to share some of the things I learned – especially how to do this stuff in sage! Now, you might be thinking – didn’t you write a very similar blog post three years ago? Yes. Yes I did. Did I also completely forget what was in that post? Yes. Yes I did, haha. For some reason I was getting it mixed up with this other post from even more years ago, which isn’t nearly as relevant. Thankfully it didn’t matter much, since I’m fairly sure what I wanted to do wouldn’t work in the framework of that post anyways, and now I have a better idea of what this machinery is actually doing which is really exciting (since I’ve been wanting to understand this stuff for years). Let’s start with a warmup problem! How might we count the number of rooted ordered ternary trees with $n$ nodes? These are the kinds of “ternary trees” that you might remember from a first class on algorithms and data structures. Such a tree is either a leaf or an internal node with 1,2, or 3 children. Crucially these children come with an order, because the datatype keeps track of which child is on the left/right (in the case of 2 children) or on the left/middle/right (in the case of 3 children). After all, from a CS perspective, we need to remember this in order to traverse the tree! This means that the following two trees are distinct for our purposes, even though they’re isomorphic as graphs: In a functional programming language, you might describe this datatype by T z = Leaf z | Unary z (T z) | Binary z (T z) (T z) | Ternary z (T z) (T z) (T z) and this translates immediately to give a functional equation for the generating function of $t_n$, which counts the number of rooted ordered ternary trees with $n$ nodes: We can rearrange this as so that we can compute the power series expansion of $T$ by lagrange inversion: = QQbar[[]] # power series ring T = (z/(1 + z + z^2 + z^3)).reverse() show(T.O(10)) Incredibly, this agrees with A036765, which is the “number of ordered rooted trees with n non-root nodes and all outdegrees <= three”, as we hoped! You might reasonably ask if there’s a closed form for these numbers, and this is too much to ask for (indeed, it’s already too much to ask for a closed form for fibonacci numbers, and this is more complicated). But like the fibonacci numbers, we can come up with an excellent approximation: where $C = \frac{(0.8936\ldots)}{2 \sqrt{\pi}}$ is a constant. Indeed, this gives fantastic results! Let’s plot the ratio of this approximation to the true value so we can see just how good this approximation gets as $n$ gets large. Note that it respects the promised big-oh error bound too! = PowerSeriesRing(QQbar, default_prec=N) T = (z/(1 + z + z^2 + z^3)).reverse() return T.coefficients()[n-1:] def approx(n,N): # very very magic C = 0.8936373911078061 / (2 * sqrt(pi)) w = 3.610718613276040 return [(C * w^k * (1/k^1.5)).n() for k in range(n,N+1)] show(html("Plot the error ratios in the range [n,N]")) @interact def _(n=input_box(100, width=20, label="$n$"), N=input_box(120, width=20, label="$N$"), auto_update=False): actuals = actual(n,N) approxs = approx(n,N) ratios = [(actuals[i]/approxs[i]) for i in range(N+1-n)] show(html("ratio at n={}: {}".format(n, ratios[0]))) show(html("ratio at N={}: {}".format(N, ratios[-1]))) text_options = {'horizontal_alignment': 'right', 'vertical_alignment': 'bottom', 'fontsize': 'large'} G = Graphics() G += scatter_plot([(n+i,r) for (i,r) in enumerate(ratios)]) G += plot(1, (x,n,N)) G += plot(1-1/x, (x,n,N)) G += text('$y = 1$', (N, 1), **text_options) G += text('$y = 1-1/x$', (N, 1-1/N), **text_options) G.show() This is extremely cool, but where the hell did this approximation come from? The answer is called Singularity Analysis, and can be found in Chapter 2 Section 3 of Melczer’s excellent An Invitation to Analytic Combinatorics, or Chapters VI and VII of Flajolet and Sedgewick’s tome. See especially Theorem VII.3 on pg 468. Like seemingly every theorem in complex analysis, this is basically an application of the Residue Theorem. I won’t say too much about why it works, but I’ll at least gesture at a proof. You can read the above references if you want something more precise. First, we recall where $C$ is any contour containing the origin inside a region where $T$ is holomorphic. Then we draw the most important picture in complex analysis: Here the obvious marked point is our singularity $\omega$, and we’ve chosen a branch cut for $T$ (shown in blue1) so that $T$ is holomorphic in the region where the pink curve lives. We’ll estimate the value of this integral by estimating the contribution from the big circle, the little circle, and the two horizontal pieces2. It turns out that the two horizontal pieces basically contribute $O(1)$ amount to our integral, so we ignore them. Since the big circle is compact, $T$ will attain a maximal value on it, say $M$. Then the integral along the big circle (of radius $\omega + \epsilon$, say) is bounded by $2 \pi (\omega + \epsilon) \frac{M}{(\omega + \epsilon)^{n+1}} = O((\omega+\epsilon)^{-n})$ To estimate the integral around the little circle, it would be really helpful to have a series expansion at $\omega$ since we’re staying really close to it… Unfortunately, $\omega$ is a singular point so we don’t have a taylor series, but fortunately there’s another tool for exactly this job: a Puiseux Series! I won’t say much about what these are, especially since Richard Borcherds already put out such a great video on the topic. What matters is is that Sage can compute them for us3, so we can actually get our hands on the approximation! We compute the integral around the little circle to be roughly: In step $(1)$ we approximate $T$ by the first term of its puiseux series, in step $(2)$ we apply the generalized binomial theorem, so that in step $(3)$ we can apply the residue theorem to realize this integral as the coefficient of $z^{-1}$ in our laurent expansion. This gives us something which grows like $\widetilde{O}(\omega^{-n})$, dominating the contribution $O((\omega + \epsilon)^{-n})$ from the big circle, so that asymptotically this is the only term that matters. If we were more careful to keep track of the big-oh error for the puiseux series for $T$ we could easily sharpen this bound4 to see This looks a bit weird with the $(-1)^n$, but remember that $\binom{\alpha}{n}$ also alternates sign. Indeed, asymptotics for $\binom{\alpha}{n}$ are well known so that we can rewrite this as Which finally shows us where our magic numbers came from! Sage happily tells us that the dominant singularity for $T$ is at $\omega = (0.2769\ldots)$ and that a puiseux expansion for $T$ at $\omega$ is so that for us $\alpha = 1/2$, and $C_{1/2} = -(0.8936\ldots)$. Finally, since $\Gamma(-1/2) = -2 \sqrt{\pi}$ and $(0.2769\ldots)^{-1} = (3.6107\ldots)$ we see as promised! Indeed, here’s how you could actually get sage to do all this for you! = QQbar[] S. = R[] # our defining polynomial. # we want to solve for T as a function of z P = z*T^3 + z*T^2 + (z-1)*T + z # following Example 2.12 in Melczer, # we compute the dominant singularity w. w = min([r for (r,_) in P.discriminant().roots() if r != 0], key=lambda r: r.abs()) # to work with abelfunctions we need P # to be a polynomial in two variables R. = QQbar[] P = R(P) # compute the puiseux expansion for T at w. # I know from trial and error that the correct # branch to pick is entry [1] in the list. You # just need to check which one gives you # positive real coefficients for T at 0. s = abelfunctions.puiseux(P,w)[1] c = -sqrt(-s.x0/s.xcoefficient) As a fun exercise, you might modify this code (using s.add_term()) to compute a longer puiseux series and get asymptotics valid up to a multiplicative error of $O \left ( \frac{1}{n^2} \right )$ for the number of rooted ternary trees. Try modifying the previous code block to see that our current approximation is not accurate to $O \left ( \frac{1}{n^2} \right )$, and then check that your approximation is! Ok, now that we understand the warmup, let’s get to the actual problem! How many unordered rooted ternary trees are there, up to isomorphism? Now we’re counting up to graph isomorphism, so that our two trees are now considered isomorphic. It’s actually much less obvious how one might pin down a generating function for something like this, but the answer, serendipitously, comes from Pólya-Redfield counting! If this is new to you, you might be interested in my recent blog post where I talk a bit about one of its corollaries. Today, though, we’ll be using it in a much more sophisticated way. Say you have a structure $X$ acted on by a group $G$ and a collection $C$ of “colors”. How can we count the number of ways to give each $x \in X$ a color from $C$, up to the action of $G$? We start by building the cycle index polynomial of the action $G \curvearrowright X$, which we call $P_G(x_1, \ldots, x_n)$. Then we can plug all sorts of things into the variables $x_i$ in order to solve various counting problems. For example, if $C$ is literally just a finite set of colors, we can plug in $x_1 = x_2 = \ldots = x_n = |C|$ to recover the expression from my recent blog post. But we can also do much more! Say that $C$ is a possibly infinite family of allowable “colors”, each of a fixed “weight”. (For us, our “colors” will be trees, and the “weight” will be the number of nodes). Then we can arrange them into a generating function $F(t) = \sum c_i t^i$, where $c_i$ counts the number of colors of weight $i$5. Then an easy argument (given in full on the wikipedia page) shows that $P_G(F(t), F(t^2), \ldots, F(t^n))$ is a generating function counting the number of ways to color $X$ by colors from $C$, counted up to the $G$ action, and sorted by their total weight6. Check out the wikipedia page for a bunch of great examples! For us, we realize an unordered rooted ternary tree is either empty, or a root with 3 recursive children7. In the recursive case we also want to count up to the obvious $\mathfrak{S}_3$ action permuting the children, so by the previous discussion we learn that where \(P_{\mathfrak{S}_3}(x_1, x_2, x_3) = \frac{1}{6}(x_1^3 + 3x_1 x_2 + 2 x_3)\) is the cycle index polynomial for the symmetric group on three letters. Plugging this in we see Now, how might we get asymptotics for $t_n$ using this functional equation? First let’s think about how our solution to the warmup worked. We wrote $F(z,T)=0$ for a polynomial $F$, used the implicit function theorem to get a taylor series for $T$ at the origin, then got a puiseux series near the dominant singularity $\omega$ which let us accurately estimate the taylor coefficients $t_n$8. We’re going to play the same game here, except we’ll assume that $F$ is merely holomorphic rather than a polynomial. Because we’re no longer working with a polynomial, this really seems to require an infinite amount of data, so I’m not sure how one might get an exact solution for the relevant constants… But following Section VII.5 in Flajolet and Sedgewick we can get as precise a numerical solution as we like! We’ll assume that the functions $T(z^2)$ and $T(z^3)$ are already known analytic functions, so that we can write $F(z,w) = -w + 1 + \frac{z}{6} \left ( w^3 + 3 T(z^2) w + 2 T(z^3) \right )$. This is an analytic function satisfying $F(z,T) = 0$. Now for a touch of magic. Say we can find a pair $(r,s)$ with both $F(r,s)=0$ and $\left . \frac{\partial F}{\partial w} \right |_{(r,s)} = 0$… Then $F$ is singular in the $w$ direction at $(r,s)$ so this is a branch point for $T$. Since both $F$ and $F_w = \frac{\partial F}{\partial w}$ vanish at $(r,s)$ the taylor series for $F$ at $(r,s)$ starts Since we know $F(z,T)$ vanishes, we estimate up to smaller order terms so that a puiseux series for $T$ at $(r,s)$ begins If we write $\gamma = \sqrt{\frac{2r F_z(r,s)}{F_{ww}(r,s)}}$ and are slightly more careful with our error terms, the same technique from the warmup shows See Flajolet and Sedgewick Theorem VII.3 on page 468 for a more careful proof of this theorem. Now how do we use this? We can approximate $T$ by its taylor series at the origin, then numerically solve for the unique9 positive real solution to the system $F(r,s) = F_w(r,s) = 0$ using this approximation: = B[[]] # cycle index polynnomials S. = QQ[] P3 = (x1^3 + 3*x1*x2 + 2*x3)/6 # to start, the taylor coefficients of T are variables T = sum([t[i] * z^i for i in range(n)]) + O(z^n) lhs = T rhs = 1 + z*P3.subs(x1=T(z), x2=T(z^2), x3=T(z^3)) # formally expand out the rhs and set the coefficients # equal to each other. This gives a recurrence relation # for t[n] in terms of the t[i] for i If we run this code locally with $N=20$, we get the approximation so that we expect and indeed this seems to work really well! Our taylor expansion for $T$ agrees with A000598, as we expected, and comparing our approximation to our taylor expansion gives: = B[[]] S. = QQ[] P3 = (x1^3 + 3*x1*x2 + 2*x3)/6 T = sum([t[i] * z^i for i in range(N)]) + O(z^N) lhs = T rhs = 1 + z*P3.subs(x1=T(z), x2=T(z^2), x3=T(z^3)) I = B.ideal([lhs.coefficients()[i] - rhs.coefficients()[i] for i in range(N)]) return [I.reduce(t[i]) for i in range(n,N)] show(html("Plot the error ratios in the range [n,N]")) show(html("This is likely to time out if you make N too large online,")) show(html("so you might want to play around with it locally instead!")) @interact def _(n=input_box(10, width=20, label="$n$"), N=input_box(30, width=20, label="$N$"), auto_update=False): actuals = actualList(n,N) approxs = approxList(n,N) ratios = [actuals[i]/approxs[i] for i in range(N-n)] show(html("ratio at n={}: {}".format(n, ratios[0].n()))) show(html("ratio at N={}: {}".format(N, ratios[-1].n()))) text_options = {'horizontal_alignment': 'right', 'vertical_alignment': 'bottom', 'fontsize': 'large'} G = Graphics() G += scatter_plot([(n+i,r) for (i,r) in enumerate(ratios)]) G += plot(1, (x,n,N)) G += plot(1-1/x, (x,n,N)) G += text('$y = 1$', (N, 1), **text_options) G += text('$y = 1-1/x$', (N, 1-1/N), **text_options) G.show() I’m pretty proud of this approximation, so I think this is a good place to stop ^_^. As a fun exercise, can you write a program that outputs the number of cyclic rooted ternary trees on $n$ vertices? For these we consider two trees the same if they’re related by cyclicly permuting their children. Compare your solution to A000625 For bonus points, can you check that the number of such trees is, asymptotically, Wow! It’s been super nice to be writing up so many posts lately! Like I said in one of my other recent posts, I’ve had a lot of time to think about more bite sized problems and mse stuff while waiting for my DOI generating code to run, so I’ve had more things that felt quick to write up on my mind. My research is actually going quite well too! I have a few interesting directions to explore, and at least one project that might be wrapping up soon. Of course when that happens I’ll be sure to talk about it here, and I’m still planning out a series on fukaya categories, hall algebras, skein algebras, and more! That’s a pretty long one, though, so it’s easy for me to deprioritize, haha. It’s already heating up in Riverside, consistently in the 80s (Fahrenheit), so I can really feel the summer coming. I’m enjoying the sunny days, though, and it’s been nice to spend time working outside and under trees. Thanks for hanging out, all! Take care of each other, and I can’t wait to chat soon ^_^. Just like $w = \sqrt{z}$, a solution to $w^2 = z$ has branches, so too does $T$, a solution to $T = z + zT + zT^2 + zT^3$. ↩ Really these are circles with a little arc cut out, say by integrating from $\epsilon$ to $2 \pi - \epsilon$… But we’ll end up taking $\epsilon \to 0$ and we’re all friends here, so let’s not worry about it. ↩ Though at time of writing you need the abelfunctions package to do it. There is a builtin implementation of puiseux series, but it won’t actually compute a series expansion for you. ↩ Of course, it’s easy to see how to extend this technique to get better asypmtotics. The first approach is to just keep more terms of the puiseux series of $T$ at $\omega$. Then apply the generalized binomial formula multiple times for each term you kept. You can also do better by keeping track of more of the singularities. Build a contour with multiple keyholes in order to get sharper lower order asymptotics: Of course, you can also combine these approaches to keep track of both more singularities and more puiseux coefficients at each singularity. ↩ In fact we can push things even farther and work with multivariate generating functions, but we won’t need that here. ↩ This is why we plug $F(t^k)$ into $x_k$. Because $x_k$ is responsible for $k$-cycles, so we choose a single color for each $k$ cycle, but we have to count it $k$-many times towards our total weight. See the proof on the wikipedia page for more information! ↩ This actually isn’t the version of the recurrence I used in my mse answer. There I used the convention that a rooted tree had to be nonempty, since… you know… it has a root. But allowing possibly empty trees makes the recurrence much simpler, which in turn allows for much easier to analyze asymptotics. Hilariously this exact example is on the wikipedia page for the Pólya-Redfield theorem, which could have saved me a lot of time writing up that answer. I was a bit worried at first about doing these asymptotics by myself, since this was my first serious attempt at using analytic combinatorics, but serendipitously this exact example was also worked out in Flajolet and Sedgewick VII.5, though slightly more tersely than I would have liked, haha. ↩ Officially we have to check that the choice of puiseux series matches up with our choice of taylor series (since there’s multiple branches to our function). But this is easy to arrange for us by choosing the branch of the puisuex series that leads to all our coefficients being positive reals. If you want to do this purely analytically you need to solve a “connection problem”. See figure VII.9 in Flajolet and Sedgewick, as well as the surrounding text. ↩ Under mild technical conditions this pair $(r,s)$ is unique. See Flajolet and Sedgewick Theorem VII.3. ↩
Every few weeks recently I’ve been putting a new fun problem on one of the whiteboards in the first year office. These are often inspired by something I saw on MSE, and I’m usually choosing problems that force you to understand something fundamental really well. Then I usually have a “challenge” bonus problem that uses the same ideas, but requires you to do some independent research to finish the puzzle! I’ve just decided what the next problem is going to be, and I’m going to post about it here because I think it’s too cute to not share more widely! This is also going to serve as a nice excuse to talk about some important reasons to care about yoneda and representability that I don’t think we often tell beginners! Before we start, though, some quick life updates: I’m still waiting to hear back positively from postdocs, but there’s still plenty of departments where I’d be very happy. I’m trying to not stress out until the end of april. What’s more stressful is my actual dissertation – because we had to move everything up a year, I didn’t have as much time as I expected to solve my main problem, and while I solved some very simple thing that’s needed along the way… It’s really not a very good thesis, haha. So I’m trying really hard to finish the whole problem in the time I have, and we’ll see how I manage. My mental health has been pretty hit or miss with the *gestures at the state of the world*, but I’m doing what I can where I can to help, and that’s been good for what would otherwise be an overwhelming sense of helplessness. I know everyone is feeling some amount of this, especially in the queer and trans community, and I encourage everyone to find something actionable to do on a local level – it helps the community, and it really does help keep the feelings manageable. BUT, enough about all that! I haven’t been writing much because I’ve been so focused on research, and I’ve really missed posting here. The quicker I am the more likely I’ll find time to do it again, so let’s get to the fun part! I’m going to assume that most people reading my blog have at least heard of the Yoneda Lemma. But it’s possible that some people reading this are confused as to why you might care about it. Like, what does it buy you? How does it help prove theorems? One answer is that it’s foundational for thinking about the functor of points approach to lots of subjects, which tells you how to study things like stacks, etc. Said in a different way, it’s an extremely useful perspective for studying certain moduli problems – you can see my old blog post about this here if you’re interested. But that’s all quite high powered. Is there a more concrete reason to care about yoneda? The answer here is inspired by one of Terry Tao’s old blog posts – the yoneda lemma tells you how to understand polymorphic transformations between two constructions (which are a priori complicated) by just studying regular old functions between representing objects! For one version of this, say you want to understand cohomology operations. That is, say you want to understand when there’s a map on cohomology $H^p(X,G_1) \to H^q(X,G_2)$ which is “polymorphic in $X$” or “uniform in $X$” in the sense that the same map works no matter which $X$ you choose1. Just as in analysis where uniformity allows you to prove lots of ~bonus results~, requiring uniformity here gives us access to many additional theorems – such as the yoneda lemma. Here this “uniformity” is usually called naturality of the transformation, and the precise relationship to polymorphism will be well understood by anyone who learned category theory via functional programming2, and is well explained in some of Bartosz Milewski’s old blog posts here and here. Now we know that $H^p(-,G)$ is represented by a space called $K(G,p)$, so asking for one of these “cohomology operations” is asking for a natural transformation Which, by representability, is a natural transformation but now we finally get to use yoneda! These natural transformations are exactly the same thing as ordinary continuous functions (up to homotopy) This means if we can understand all continuous functions between these fixed spaces, that’s enough to understand all cohomology operations $H^p(X,G_1) \to H^q(X,G_2)$ for every space $X$ simultaneously! The ability to work with the representing objects directly is a huge reduction in complexity, and one of the main reasons people work with objects like “stacks” and “spectra” is because they want more things to be representable so that they can play exactly this game3. That’s well and good…. But surely that can’t be the “down to earth” example, right? Cohomology operations are interesting, and might eventually feel down to earth, but objectively most people would laugh at that idea. This, finally, brings us to the problem I’ll be writing on the first year’s whiteboard later today: Let $R$ be a (commutative, unital) ring. Classify all “polymorphic” functions $R^n \to R$. That is, all (set) functions $R^n \to R$ that can be defined uniformly for all rings $R$ simultaneously. (Hint: yoneda) If $G$ is a finite group, define a “$G$-torsion collection” in $R$ to be a group homomorphism $G \to R^\times$ from $G$ to the units of $R$. For example, a “$C_n$-torsion collection” is an element $x \in R$ so that $x^n = 1$, and a “$\mathfrak{S}_3$-torsion collection” is determined by elements $x,y \in R$ with $x^2 = 1$, $y^3 = 1$, and $xyx = y^2$ (because $\langle x, y \mid x^2=1, \ y^3=1, \ xyx=y^2 \rangle$ is a presentation for $\mathfrak{S}_3$) (Challenge) Classify all “polymorphic” (set) functions \(\Big \{\mathfrak{S}_3\text{-torsion collections in $R$} \Big \} \to \Big \{C_2\text{-torsion collections in $R$} \Big \}\) I’m about to spoil both of these problems, so if you want to think about them (and I really encourage you to think about them! At least the first problem!) now is your last chance to be unbiased by my explanation… Ok, so. Inspired by the rest of this post you’ll want to think about how to represent the constructions above. For the first problem, where we want set functions $R^n \to R$, that means we want to represent4 the functor sending a ring $R$ to the underlying set of $R^n$ the functor sending a ring $R$ to its underlying set The second one isn’t so hard to do – a moment’s thought shows that ring homs $\mathbb{Z}[x_1] \to R$ are in bijection with elements of $R$ (we just have to choose where to send $x_1$). Once you’ve figured this out it’s not such a big jump to see that ring homs $\mathbb{Z}[x_1, \ldots, x_n] \to R$ are in bijection with elements of $R^n$ (we just have to choose where to send each of the $x_i$ separately). So classifying “polymorphic” transformations $R^n \to R$ is classifying natural transformations which, by yoneda, is asking to classifying good old fashioned ring homs and, as before, we just need to decide where $y$ goes! So this is in bijection with the underlying set of $\mathbb{Z}[x_1, \ldots, x_n]$. That is, with integer-coefficient polynomials in $n$ variables. It’s not hard to see that any such polynomial gives you such a natural map! Indeed, for a concrete example take $p = x_1^2 + 2 x_1 x_2 - 3$. Then we get a function $R^2 \to R$ sending $(r_1, r_2) \mapsto r_1^2 + 2 r_1 r_2 - 3$, where an integer like $-3$ is interpreted in $R$ as $0_R - 1_R - 1_R - 1_R$. If one thought about this problem without knowing category theory, I think it would be pretty easy to conjecture that integer polynomials are the only polymorphic maps $R^n \to R$… But I’m not sure how you would prove it without basically rediscovering this special case of yoneda! Now… what about the challenge problem? We want to classify “polymorphic” maps Again we have a natural5 conjecture, since if we have a group homomorphism $\mathfrak{S}_3 \to R^\times$ we get some obvious group homomorphisms $C_2 \to R^\times$ too (namely the images of $(1 \ 2)$, $(2 \ 3)$ and $(1 \ 3)$, the 2-torsion elements in $\mathfrak{S}_3$)… Could this be all of them? Well, a “$G$-torsion collection” in $R$ is a group homomoprhism $G \to R^\times$, and these are in bijection with ring maps $\mathbb{Z}G \to R$! So the same idea as before shows that classifying natural transformations is the same as classifying natural transformations which, by yoneda, means classifying ring maps and thus means classifying $C_2$-torsion collections in $\mathbb{Z}\mathfrak{S}_3$. So we want to understand the group of units in $\mathbb{Z}\mathfrak{S}_3$, and in particular we want to classify the $2$-torsion elements in this group! Now is where the independent research comes in. You might naively guess that the group of units in $\mathbb{Z}G$ is just $G$ again… But you would be wrong! Of course if $g \in G$ then both $+g$ and $-g$ are units in $\mathbb{Z}G$, but even this isn’t enough! Understanding the units in group rings turns out to be a subtle and interesting problem, and I think it’s extra cute that this little puzzle helps people learn about this surprisingly rich subject6. We want to understand the group of units in $\mathbb{Z}\mathfrak{S}_3$, and searching for things related to this will quickly turn up the paper The Group of Units of the Integral Group Ring $\mathbb{Z}S_3$ by Hughes and Pearson, which certainly seems related! This paper is only 6 pages long, and is a very polite read7. Part (2) of their Theorem 1 is exactly what we’re looking for: (2) … there are $2$ conjugacy classes of elements of order $2$, with generic elements $(12)$ and $t=(12) + 3(13) - 3(23) - 3(123) + 3(132)$ respectively. What does this mean for us? Their Part (1) to this same theorem gives an isomorphism of \((\mathbb{Z}\mathfrak{S}_3)^\times\) with a certain $2 \times 2$ matrix group, so it’s easy to compute conjugation. So knowing this and knowing both conjugacy representatives we have a classification of all order 2 elements in $\mathbb{Z}\mathfrak{S}_3$, and by extension (crucially using yoneda and representability!) a classification of all natural transformations Indeed from this we’ve learned that our naive conjecture was wrong! This element $t$ is not one of the 2-torsion elements we were expecting, and it gives us a new and unexpected natural transformation! If $f : \mathfrak{S}_3 \to R^\times$ is a $\mathfrak{S}_3$-torsion collection in $R$, then of course we have $C_2$-torsion elements $f(1 \ 2)$, $f(2\ 3)$ and $f(1 \ 3)$. But it turns out we also have a secret, special $C_2$-torsion element Or, said another way, if $x,y \in R^\times$ with $x^2 = 1$, $y^3 = 1$, and $xyx = y^2$ determine a $\mathfrak{S}_3$-torsion collection in $R$, then is a (probably surprising!) $C_2$-torsion element in $R$. Of course, as with the last problem, I’m not sure how you would even begin to approach this classification problem without rediscovering the relevant version of the yoneda lemma! Thanks again for hanging out, everyone! I’m working on a lot of really fun stuff and I can’t wait to have time to talk about it. I think I want a quick outro today – I’ve had the sniffles all weekend, probably because I didn’t dress well before hanging out in the cold with one of my best friends who visited me last week! We made creme brulee for the first time (since I recently bought a blowtorch), and it was surprisingly easy and turned out delicious! I already make a lot of lava cakes when I want a decadent and fancy dessert, but I’ll have to add creme brulee into the rotation! Talk soon, everyone! Stay warm 💖 This “polymorphism” (which, of course, corresponds to naturality) is because we want an operation that’s really coming from the cohomology rather than being an “accidental” operation that comes from structure on $X$. ↩ Like I did… about a decade ago… I realized when writing this post that I remember waiting for many of these Bartosz Milewski posts to be published! But these posts have been done since 2017. Wild. ↩ I was so close to making “spectra” in this sentence link to spectra instead, which I think would be hilarious, but I decided against it. ↩ Some pedants might prefer I say corepresent. This footnote is purely to indicate that I do know better, I just don’t care, haha. ↩ Pun very much intended ↩ I forget exactly when I learned that the units in $\mathbb{Z}G$ might be bigger than just $\pm G$… But I remember being extremely surprised at the time! I’ll mention, though, that this maybe shouldn’t be that surprising. Indeed the group ring and group of units constructions are adjoint, so the unit of the adjunction gives a (natural) map and there’s no reason to suspect this unit is an isomorphism! Most units aren’t, haha. ↩ Though you have to get over the “function application on the right” notation, which goes totally unmentioned and confused me for a second when I read it. Functions on the right is absolutely objectively the better notation, and unfortunately it’s just confusing enough when you aren’t used to it to make it so that it’s unlikely to ever really catch on. ↩
Oftentimes in your “intro to proofs” class or your first “discrete math” class or something similar, you’ll be shown problems of the form “prove that for $n^6 + n^3 + 2n^2 + 2n$ is a multiple of $6$ for every $n$”… But where do these problems come from? And have you ever stopped to think how magical this is? If I gave you some random polynomial in $n$ and asked you if it always output multiples of $6$, the answer would almost always be “no”! So if you really needed to come up with an example of this phenomenon, how would you do it? In this blog post, we give one approach! I want to give some sort of attribution for this, since I remember reading about this exact topic… like a long time ago. Maybe 6 or 7 years ago? I’m sure that I saved the relevant article1 in my zotero, but I can’t find it for the life of me! Regardless, I want to emphasize that the whole idea for this topic (using Pólya-Redfield counting to build these divisibility problems) is not mine. I’ve wanted to write a post on Pólya-Redfield counting for years now, since it was a pet topic of mine as an undergrad, but I think I was always planning too big a scope. This is a very bite-sized problem, and I won’t go into the theory very deeply, so I think it should make for a blog post I can finish in a day2. Let’s get to it! Ok, first, how might we come up with problems like this? We want a polynomial $P(n)$ and an integer $k$ so that $P(n)$ is always a multiple of $k$. That is, so that $P(n) / k$ is always an integer! But what are sources of integers? If we put our combinatorial hats on, we learn that we had better be counting something! That’s the quickest way to ensure that we get an integer answer at the end of the day. So we want a polynomial so that as we vary $n$, the value $P(n) / k$ counts… something. At this point, you might be inspired by The Lemma Which is Not Burnside’s, which says that when a group $G$ acts on a set $X$, the number of orbits is where \(X^g = \{ x \mid gx = x \}\) is the set of fixed points of $g$. This is great, since in some sense it’s “where division comes from”. I don’t want to get into categorification here, but when we say we’re thinking of numbers as the cardinality of some set (to guarantee they’re integers) we’re really categorifying our problem. There’s been lots of work showing how various operations on numbers lift to categorified operations on the category of finite sets, and the only way I know of to categorify division is to take the orbits of some group action3. Hopefully this also serves to show that categorification doesn’t need to be scary! It can be incredibly simple, just thinking about finite sets and what we can do to them… Though maybe people who read my blog are already convinced of that, haha. Regardless, this orbit-counting formula is close to what we want! It gives us access to division. So if we could only find a family of sets $X_n$, all of which admit a $G$-action, then maybe we could have $P(n) = \sum_g |X_n^g|$ and thus $P(n)$ will always be divisible by $|G|$, since $P(n)/|G|$ counts the orbits $|X_n \big / G|$! This is exactly what Pólya-Redfield counting buys us! I really want to write a blog post with lots of pretty pictures that explains this in detail, but maybe just for today I’ll allow myself to be a bit less thorough. If you want to see this motivated with pretty pictures, I’ll point you to some slides by my undergrad advisor Klaus Sutner4. These are from the 2023 version of the class where I first met him back in… 2017? It’s better to not think about that, haha. Moving on, say we have a set $X$ with a $G$-action. Then we think about all the ways to “color” $X$ with $n$-many colors. Precisely these are functions from \(X \to [n]\), and they pick up a natural $g$ action by sending the function $f : X \to [n]$ to the function $(gf)(x) = f(g^{-1}x)$5. These function spaces6 \((X \to [n])\) will be our sets $X_n$, and all that’s left is to see how to compute $|X_n \big / G|$, ideally in a way that’s uniform in $n$. Now (a corollary of) the main Pólya-Redfield theorem says: where $c(g)$ is the “cycle count” of $g$. We can view the action of $G$ on $X$ as a homomorphism $\alpha$ from $G$ to the symmetric group $\mathfrak{S}_X$. Then $\alpha(g) \in \mathfrak{S}_X$ is a permutation, so decomposes into a product of cycles. The number $c(g)$ is perhaps the dumbest invariant you can think of: just count the number of cycles! This is exactly what we want, since it tells us that the polynomial $P(n) = \sum_g n^{c(g)}$ is always divisible by $|G|$, since the quotient is exactly counting the orbits of the action of $G$ on \((X \to [n])\)! Again, unfortunately I’ll leave the derivation of this formula (and the many many other useful things the Pólya-Redfield theory buys you) for another day, but at least we can do some quick examples! First, say we want to count the number of bracelets you can make with $6$ beads, provided you have $n$ many types of beads available. Obviously if you were looking at bracelets in the real world that you can move around, the following two bracelets are actually the same: so we want to count the number of ways to color this picture with $n$ colors (this is a choice of bead in each position), but only up to the obvious $\mathbb{Z} / 6$ action on the space of colorings7! Now choose an isomorphism between the colorable places of our configuration and the standard set of size $6$, for instance, this is likely to be a common choice: After making this identification our action is a map $\mathbb{Z}/6 \to \mathfrak{S}_6$, and thus we can compute cycle decompositions as follows: Element $g \in \mathbb{Z}/6$ Image in $\mathfrak{S}_6$ Number of Cycles, $c(g)$ $0$ $(1)(2)(3)(4)(5)(6)$ $6$ $1$ $(1 \ 2 \ 3 \ 4 \ 5 \ 6)$ $1$ $2$ $(1 \ 3 \ 5)(2 \ 4 \ 6)$ $2$ $3$ $(1 \ 4)(2 \ 5)(3 \ 6)$ $3$ $4$ $(1 \ 5 \ 3)(2 \ 6 \ 4)$ $2$ $5$ $(1 \ 6 \ 5 \ 4 \ 3 \ 2)$ $1$ Using this, we see that the number of bracelets with $n$ beads, up to our $\mathbb{Z}/6$ action is Since this is counting the number of orbits, it must be an integer, and so for every $n$, the polynomial $P(n) = n^6 + n^3 + 2n^2 + 2n$ has to be divisible by $6$, as promised! Let’s see a harder one, which (in the interest of speed) I stole from Klaus’s lectures: How many ways can you fill a tic-tac-toe board with $X$s and $O$s, up to rotation and reflection? We have configurations like the following (I’ve already chosen a bijection between our colorable places and the standard set with $9$ elements): Now we want to color each slot $X$ or $O$, and quotient out the action of the dihedral group in order to view the following colorings as “the same” (of course, these aren’t the whole orbit! There’s many other rotations and reflections which are also equivalent): Notice we’re also not worried about which colorings come from actual games of tic-tac-toe! How does Pólya-Redfield tell us to proceed? Well, the dihedral group $D_{2 \cdot 4}$ has $8$ elements, built out of rotations and reflections. Say that $r$ is the clockwise rotation shown above, and $s$ is the horizontal flip shown above. Then using the numbering system from before, we compute so that, in cycle notation: Since $r$ and $s$ generate the whole dihedral group, we’re done with the hard work! Now a computer algebra system like sage can compute the rest of the table from these by multiplying them together: As a cute exercise for those new to group theory, try computing these 8 permutations yourself! Can you figure out which one comes from which element of the dihedral group? Can you see how they relate to the usual presentation $G = \langle r, s \mid r^4, s^2, srs=r^{-1} \rangle$? From here it’s easy to read off the polynomial! If we have $n$-many available colors to put in each slot of the tic-tac-toe board, then the number of possible boards, counted up to rotation and reflection is given by Since we’re trying to color the board with only two colors, $X$ and $O$, we see the number of ways is Now we’ve really made two predictions here. First, that $P(n) = n^9 + 4n^6 + n^5 + 2n^3$ will be a multiple of $8$ for whichever $n$ you plug in. Second, that this quotient really is counting the tic-tac-toe boards! Let’s take a quick second and ask sage how true those look. First, we can just plug in a few thousand $n$s and see if we ever hit anything other than a multiple of $8$: Second, we know there’s only $2^9 = 512$ many ways to 2-color a tic-tac-toe board without counting rotations and reflections. So it’s not too time consuming to just list all of them and remove any we’ve seen before! So there we go! This actually ended up taking two days to write, since yesterday I got distracted from my distraction when I was talking to a friend about connections and how curvature is related to force in physics. I realized I don’t actually understand that as well as I thought I did, so I had to spend some time rereading a bunch of physics stuff, which was super fun, even if it took a while, haha. If you’re ever on a deserted island and you find yourself needing polynomials whose outputs are always divisible by some fixed number, this is an endless source! You might ask if every such polynomial arises from Pólya-Redfield counting in this way, and that’s obviously false (since, for instance, we’ll never get any constant terms)… But it’s not obviously false that every such polynomial arises from Pólya-Redfield counting after a change of variables! So with no intuition at all for whether it’s true or false, let me pose that as a conjecture: Conjecture: If $p$ is a polynomial so that $p(n)$ is a multiple of $k$ for every $n$, then there is a set $X$ and a group $G$ of order $k$ and a polynomial $f$ sending integers to integers so that Maybe $f$ can even be taken to be of the form $an+b$, why not. I haven’t thought about it either way, haha. For anyone interested in thinking about this conjecture, it’ll be nice to know that every polynomial sending integers to integers is an integer linear combination of binomial coefficients (see here). Amusingly, this was also shown by Pólya! You can push this further (as mentioned in the same wikipedia article) to note that $k \mid p(n)$ for all $n$ if and only if in the above representation $p = \sum c_i \binom{x}{i}$, all the $c_i$s are multiples of $k$. So we have an extremely concrete classification of these polynomials, which one might use to (dis)prove the conjecture8! As a cute aside, we’ve actually talked about this basis for polynomials in terms of binomial coefficients before! Seeing them turn up here was like seeing an old friend. Thanks again for hanging out, all! This was super fun, and it was a nice diversion from the blog post about my thesis work. It’s loooong, but really interesting, and I think people will enjoy it. This stuff relating fukaya categories, topological field theories, and representation theory is some of the coolest math I’ve ever seen, and I couldn’t have asked for a more fun thesis topic. Of course, I also need to get the topological topos posts cleaned up and submitted to journals, and I have a fun project that I want to finish up which will be interesting to categorical logicians and algebraic geometers! (At least, algebraic geometers of a certain kind, haha). There’s always more to do, but that’s part of the fun of it! After two months applying to postdocs and barely doing any math at all, I’m thrilled to be back at it ^_^. Alright, stay safe, all! We’ll talk soon 💖 or maybe it was a blog post or an mse question or something… Or maybe a footnote in a published paper? Part of why I can’t find it is because I don’t remember anything about where I read it! And back when I was an undergrad I was much worse about leaving myself searchable notes so I can quickly find interesting things again. ↩ If you’re curious why I decided to make this blog post now, I just started learning about cluster algebras today, and in the first lecture of Pavel Galashin’s series on the subject he mentions a recurrence relation which magically always gives integers, despite division happening. This reminded me of these polynomials which always give outputs divisible by some number (which is an easier version of the same phenomenon), and I went looking for the original article to share on mastodon. I couldn’t find it, so… I guess I’m writing one! John Baez and Jim Dolan and I also talked about species and structure types in our last meeting, and so I think I was also somewhat primed to think about generating functions and Pólya-Redfield counting based on that conversation. ↩ You need groupoids and “groupoid cardinality” to have access to division in general, since this lets you get rational numbers (and even certain real numbers!) as cardinalities. See, for instance, John and Jim’s famous paper From Finite Sets to Feynman Diagrams or this MO post for more. ↩ I saved a copy of these slides local to this blog to make sure they’re always available, but if you want them right from the horse’s mouth you can find them here, and a course schedule with all the available lecture slides here. ↩ As long as I’m missing my undergrad years, I’ll pass on an insight from one of my favorite undergrad professors Clinton Conley about this seemingly weird $g^{-1}$: Remember when you were learning how to graph functions and if you want to move the graph of $f(x)$ to the right by $c$, you look at the function $f(x-c)$? This trips up a lot of students first learning things, since it seems backwards to subtract $c$ to move to the right, especially since moving up and down has the much more sane behavior that $f(x)+c$ moves you up by $c$ units! This is the same phenomenon, where the action on the input is contravariant (and we act on $x$ by the inverse of $c$) while the action on the output is covariant (and we act on $f(x)$ by $c$)! There’s also something to be said here about left vs right actions, but I won’t say it, haha. Hopefully this Clinton-ism helps this make more sense, since I remember it really helped me when I was younger! ↩ I guess my type theory background is showing in this notation, haha. ↩ I think when most people talk about these bracelet problems, they quotient by the dihedral group instead of the cyclic group. This is because you can flip a bracelet over in 3D, so you have access to reflections too. I’m ignoring that for the sake of the example, though, and just counting things up to rotation. ↩ This is also a much more efficient source of polynomials for undergrad divisibility problems, but it wouldn’t have been anywhere near as fun! ↩
I’ve been trying to learn all about topological (quantum) field theories, the cobordism hypothesis, and how to use $(\infty,n)$-categories. This is all in service of some stuff I’m doing with skein algebras (which are part of a “$3+1$ TQFT” often named after Crane–Yetter, but I believe the state of the art is due to Costantino–Geer–Haïoun–Patureau-Mirand), but it’s incredibly interesting in its own right and it’s been super fun to get a chance to learn more physics and learn way more about topology and higher categories. Along the way, I was watching a lecture by Jacob Lurie where he mentions something that should probably be obvious (but wasn’t to me): For a (smooth) manifold $F$, $\mathsf{B}\text{Diff}(F)$ classifies bundles with fibre $F$ That is, given a manifold $M$ we have a natural bijection I asked about this in the category theory zulip, and got some great responses that still took me a while to digest. Actually, it wasn’t until I started reviewing a bunch of material on principal bundles1 that everything clicked into place for me. Over the course of this post, I’ll hopefully make this bijection obvious, and I’ll explain some facts about bundles along the way. This should serve as a nice quick blog post to write during my winter break since I’ve been extremely stressed for the last two months trying to get all my postdoc applications done2. Thankfully it’s all finally behind me, and I’m back in New York with people I love, so I’m resting up and doing math again (which have both been fantastic for my mental health). Let’s get to it! First, let’s remember what a bundle even is. Say we have a base space $M$ and a map $\pi : E \to M$. Then for each point $m \in M$ we have the fibre $E_m = \pi^{-1}(m)$, and so we can view $\pi$ as a family of spaces $(E_m)$ indexed by points of $M$. We think of $E_m$ as being “vertical” over $m \in M$, and we think of the topology on $E$ as telling us how these fibres are glued to each other “horizontally”3: We say that $\pi : E \to M$ is a fibre bundle if it’s “locally trivial” in the sense that (locally) the fibres are all $F$, and these copies of $F$ are all glued to each other in the most obvious possible way. Because we mathematicians feel the need to make newcomers feel inadequate, we call this most obvious way the “trivial” bundle: $\pi : M \times F \to M$. For a bundle to be locally trivial we don’t ask for it to literally be $M \times F$, that’s asking too much. Instead we ask that for every point $m \in M$ there should be a neighborhood $U_m$ so that $\pi^{-1}(U_m) \cong F \times U_m$4. We say that such a bundle is a Fibre Bundle with Fibre $F$, and here’s a completely natural question: Can we classify all fibre bundles with fibre $F$ over a base space $M$? Let’s think about how we might do this from a conceptual point of view, and that will lead us to the answer in the title of this post. Then we’ll reinterpret that conceptual understanding in much more concrete language, and hopefully explain why people care so much about principal bundles at the same time! If we put our type theory hats on5, then we want to think about a fibre bundle as being a map from our base space $M$ into a “space of all $F$s”. Then we think of this map as assigning an $F$ to every point of $M$, and this is exactly6 the data of a fibre bundle! But what should a “space of all $F$s” look like7? Well, as a first try let’s just take a huge manifold $\mathcal{U}$ and look at all copies of $F$ sitting inside it! For instance, we might take $\mathbb{R}^\infty$, and then an “$F$ sitting inside it” is an embedding $\iota : F \hookrightarrow \mathbb{R}^\infty$… almost! A choice of embedding has the ~bonus data~ of a parameterization, which an abstract “copy of $F$” wouldn’t have. We’re only interested in what’s morally the image of a particular embedding, so we should quotient out by reparameterization. Concretely, if $\varphi : F \overset{\sim}{\rightarrow} F$ is a diffeomorphism, then $\iota$ and $\iota \circ \varphi$ represent the same “copy” of $F$ in $\mathbb{R}^\infty$, so we find ourselves interested in the space Now it feels like we made a choice here, taking $\mathcal{U} = \mathbb{R}^\infty$, but we can worm our way out of this choice with homotopy theory! Indeed it’s believable that \(\{ \iota : F \hookrightarrow \mathbb{R}^\infty \}\) should be contractible, since if $F$ is finite dimensional then any two embeddings lie in a small subspace of $\mathbb{R}^\infty$, so there’s plenty of room to homotope them into each other. Then for any two such homotopies there’s still room to fill in the resulting circle, and so on. Since the space of embeddings is contractible, up to homotopy we’re working with8 and if we make “$\mathcal{U}$ is sufficiently large” mean “the space of embeddings of $F$ in $\mathcal{U}$ is contractible”, then we’ll get $\star \big / \text{Diff}(F)$ independent of this choice. Of course, $\star \big / \text{Diff}(F)$ is frequently called the Classifying Space $\mathsf{B} \text{Diff}(F)$, and so we’re halfway to our goal! We normally think of $\mathsf{B}G$ for a group $G$ as an object classifying “principal $G$-bundles”, so that a map $M \to \mathsf{B}G$ is the same thing as a bundle over $M$ whose fibres are all isomorphic to $G$… So, naively, it sounds like a map $M \to \mathsf{B}\text{Diff}(F)$ should be the data of a bundle over $M$ whose fibres are $\text{Diff}(F)$! But we wanted a bundle over $M$ whose fibres are $F$! What gives? The answer comes from the Associated Bundle Construction, which is the reason to care about principal bundles at all! In a remarkably strong sense, we can understand every “$G$-bundle” as long as we’re able to understand the principal $G$-bundles! Let’s see how, then use it to solve our problem in a (more) down-to-earth way. Concretely, we might understand a fibre bundle by picking a good open cover \(\{ U_\alpha \}\). Then we pick local trivializations $\varphi_\alpha : \pi^{-1}(U_\alpha) \overset{\sim}{\to} U_\alpha \times F$. If we want to answer a (local) question about the bundle, we can use one of these $\varphi_\alpha$s to transfer the question to a question about $U_\alpha \times F$, which is often easier to work with. But crucially we need to know that we’ll get the same answer no matter which of these “charts” $U_\alpha$ we work with. For instance, say our fibres are all $\mathbb{R}$. Then a natural question might be “is this element of the fibre $0$?”. If we always glue $0$ to $0$ then we get a consistent answer, but if at some point we glue $0$ in $U_\alpha$ to $1$ in $U_\beta$ then the answer will depend on which chart we use to do the computation! It turns out that more fundamental than the particular choice of trivialization are the “transition maps” $\varphi_\beta \circ \varphi_\alpha^{-1} : (U_\alpha \cap U_\beta) \times F \overset{\sim}{\to} (U_\alpha \cap U_\beta) \times F$ which tell us how to translate computations between our $\alpha$ and $\beta$ charts. These have to be the identity on the $U_\alpha \cap U_\beta$ part, so the interesting data is a map $\varphi_{\beta \alpha} : F \overset{\sim}{\to} F$ which tells us how to glue the $\alpha$ and $\beta$ charts along their intersection. Now if we want to answer questions corresponding to “bonus structure” on our fibre, we need to make sure we only ever glue in a way that preserves the answers to these questions. That is, instead of $\varphi_{\beta \alpha}$ being any old diffeomorphism of $F$, we want it to be in the subgroup of diffeomorphisms respecting this structure9. If we call this subgroup $G$, then we call our bundle a $G$-bundle. For example, if our fibres are all $\mathbb{R}^n$ and we want to ask vector-spacey questions, then we should only glue them using diffeomorphisms that respect the vector space structure. That is, we should only glue along $\mathsf{GL}(n) \subseteq \text{Diff}(\mathbb{R}^n)$, and so we’re working with a $\mathsf{GL}(n)$-bundle. If we moreover want to ask questions about the usual inner product on $\mathbb{R}^n$, then we have to glue in a way that preserves the inner product so our transition functions will be valued in $\mathsf{O}(n)$10. So it turns out the crucial data for a $G$-bundle are the transition maps $\varphi_{\beta \alpha} : U_\alpha \cap U_\beta \to G$. These have to satisfy the Cocycle Condition11 that $\varphi_{\gamma \beta} \varphi_{\beta \alpha} = \varphi_{\gamma \alpha}$, which crucially never mentions the fibre $F$! So we learn that $G$-bundles can be classified without referencing the fibre $F$ at all! Indeed, say we have the data of a $G$-cocycle $\varphi_{\beta \alpha}$. Then for any space $F$ with a $G$-action we can build a bundle with fibres $F$ by using these as our transition functions. Since we can choose any $F$ we want (at least for the purposes of classification) it’s reasonable to ask if there’s a “best” choice of fibre that makes things easier. To answer this one might ask if there’s a “best” choice of set that $G$ acts on, and from there we might be led to say that the best choice is $G$ acting on itself by multiplication! In this case our fibres are all $G$, and it’s easy to see this preserves “relative information” about $G$ since $h^{-1}k = (gh)^{-1}(gk)$ and the value of $h^{-1}k$ is preserved by the multiplication action. However this action does not preserve “absolute information” about $G$, such as the identity, since $ge = g \neq e$. The structure that’s preserved is called a torsor, and so we see that any $G$-valued cocycle on $M$ naturally gives us a bundle of $G$-torsors on $M$! This is called a Principal $G$-Bundle, and from the earlier discussion if we can classify the principal $G$-bundles, we can classify all $G$-bundles easily! It turns out that in many many ways if we want to understand $G$-bundles it’s enough to understand the principal ones. For instance connections on a $G$-bundle arise in a natural way from connections on a principal $G$-bundle, and principal $G$-bundles give us a way to work with bundles in a coordinate-invariant way. I won’t say any more about this, in the interest of keeping this post quick, but I’ll point you to the excellent blog posts by Nicolas James Marks Ford12 on $G$-bundles and connections, as well as the relevant sections of Baez and Muniain’s excellent book Gauge Fields, Knots, and Gravity. Concretely, how can we implement this bijection? Well, given a $G$-bundle $\pi : E \to M$ we can fix a good open cover \(\{ U_\alpha \}\) of $M$, and we can read off the transition maps $\varphi_{\beta \alpha} : U_\alpha \cap U_\beta \to G$, and then we can build a new $G$-bundle $\widetilde{E} \to M$ whose fibres are all $G$ (called the Associated Bundle to $E$) by gluing copies of $G$ together with these same transition maps $\varphi_{\beta \alpha}$. This is a principal $G$-bundle. In the other direction, say we have a principal $G$-bundle $\pi : P \to M$. Then if $G$ acts on any space $F$ we can build a new $G$-bundle which is fibrewise given by $E_m = (P_m \times F) \big / \sim$ where we quotient by the relation $(hg,f) \sim (h, gf)$. This is, in some sense, coming from the “universality” of $G$ as a $G$-set that made $G$ the “best” choice of set with a $G$-action13! It’s a cute exercise to check that these operations are inverse to each other! Now. Where did we start, and where did we end? Well we can read on wikipedia that $\mathsf{B}G$ classifies principal $G$-bundles. But we know that once we fix an action of $G$ on $F$, the principal $G$-bundles are in bijection with $G$-bundles with fibre $F$! So using the obvious action of $\text{Diff}(F)$ on $F$, and remembering that all bundles with fibre $F$ have transition functions landing in $\text{Diff}(F)$, we get a natural bijection Which is exactly what we were looking for! In hindsight, I’m not sure whether the story involving a “space of all $F$s” or the story about associated bundles is “more concrete”… I know the second story is easier to make precise, but I think both versions are good to see. I’m super happy to have finished this post in two days. I started writing it last night when I got to my friends’ house in New York, and I finished it this morning while they were addressing and signing a bunch of christmas cards. It’s good to be thinking and writing about math again after my two months of postdoc application hell, and I’m feeling SO comfortable and relaxed it’s just great to be around people I love. I’m going to hopefully find time to finish writing a series on skein algebras, hall algebras, and fukaya categories (which is the topic of my thesis) in the next month or two. That will be great, because I have a TON of fascinating stuff to share ^_^. As always, thanks for hanging out. Now more than ever stay safe, stay warm, and take care of each other. Nobody else is going to. Also… wow I’m tall. I’m trying to learn some gauge theory for other reasons ↩ For political reasons at UCR, it seems like none of the rising 6th years will get TA positions next year. Which means that me and a LOT of people in my cohort are having to graduate a year earlier than we planned, because like…. we need money to live, lol. We found this out in mid october, crucially after the NSF grant deadline, and only a month and a half before most postdoc applications were due. I made it happen, but it’s been a really unpleasant two months. ↩ I want this to be a quick low effort post, so I’m going to shamelessly steal all my graphics from Baez and Muniain’s book Gauge Fields, Knots, and Gravity. ↩ In this situation we say our condition is “local on the base” or “local on the target” since we have a neighborhood $U_m$ for every $m \in M$ the “base space”, which is the target of the map $\pi : E \to M$. This is to be contrasted with a condition that’s “local on the domain” or “local on the total space” or “local on the source”, where we have a neighborhood $U_e$ for every $e \in E$ the “domain” or “total space” or “source” of the map $\pi : E \to M$. ↩ You could just as well put your moduli space hat on, if you’re more comfortable with that. One of the ↩ It’s reasonable to ask why this definition only gives us locally trivial bundles. The reason is that a homotopy class of a map from a contractible space to the “space of all $F$s” is the same thing as a map from a point to this space. Composing with the contraction homotopy we find that the bundle we classify is trivial. So if you take a point if $M$ and restrict your map to a contractible neighborhood of $m$, you’ll find that the bundle is trivial on that neighborhood. ↩ I got this argument from Kevin Carlson in the CT Zulip, from the same thread I linked earlier. ↩ Here, of course, we have to work $\infty$-categorically and interpret this quotient as a homotopy quotient in order for it to be interesting! ↩ This is what “structure groups” are all about. I had half a mind to write up a longer thing explaining how structure groups work and why they correspond to structure on the fibre surviving to global structure on the bundle (especially because it was something that took me a while to understand)… But I also want this post to be done quickly, and I found myself wanting to draw a bunch of pictures and write a bunch of stuff about that, so… I didn’t 😌. I’m sure we’ll talk more about it someday. ↩ If at this point you’re thinking that if we don’t want to preserve ~any~ bonus structure we should take our structure group to be the whole of $\text{Diff}(F)$, then congratulations! You are making an observation that would have saved me… a lot of time and confusion a few months ago, haha. ↩ I won’t get into this here, and since I want this to be quick I don’t want to find a good reference, but this use of the word “cocycle” isn’t an accident, and indeed we’re computing the Čech cohomology of the base space with coefficients in $G$. The cocycle condition tells us we’re considering cocycles, and the coboundaries tell us when we’re describing the same bundle with different intitial choices of trivialization. ↩ It’s kind of hilarious how similar his blog looks to mine. We’re using very similar color schemes. ↩ Note also that the action of left multiplication of $G$ on itself commutes with (“preserves”) the action of right multiplication of $G$ on itself (this is associativity). So a principal $G$-bundle has a global right action of $G$, and a trivial bundle with fibre $F$ has a global left action of $G$, since the identity diffeomorphism preserves the left action of $G$ on $F$. So we have two bundles, one with a global right $G$-action and one with a global left $G$-action. So we can take thier tensor product to be left with a new bundle, not necessarily admitting a global $G$-action. ↩
More in science
The FDA should do something similar for humans
Regulations are a classic example of a proverbial double-edged sword. They are essential to create and maintain a free and fair market, to prevent exploitation, and to promote safety and the public interest. Just look at 19th century America for countless examples of what happens without proper regulations (child labor, cities ablaze, patent medicines, and […] The post Transgene-Free Gene Editing in Plants first appeared on NeuroLogica Blog.
Rose Yu has a plan for how to make AI better, faster and smarter — and it’s already yielding results. The post Improving Deep Learning With a Little Help From Physics first appeared on Quanta Magazine