Earlier today I gave a talk in the graduate student seminar titled “Counting is Hard. Complex Analysis is Easy.” based in part on my recent blog post about analytic combinatorics and based in part on Varilly’s notes on Dirichlet’s Theorem, showing how to count the number of trees of a certain shape and the number of “primes of a certain shape” by doing complex analysis. While prepping for this talk, I realized there’s a very pretty geometric way to see what’s going on when counting rooted ordered ternary trees! I don’t usually write blog posts about my local seminar talks anymore, but I think this is more than worthy of an exception! For instance, I think this could serve as a great visiual example of branches and mild singularities in complex analysis. So, let’s remember the problem! We want to count the number of rooted ordered ternary trees with $n$ nodes. Call this number $t_n$. We note that every such tree is either a root node a root with one child a root with two children a root with three children where each child is recursively a rooted ordered ternary tree. If we define $T(z) = \sum_n t_n z^n$ to be the (ordinary) generating function for the $t_n$ we see from this recurrence relation that it must satisfy the functional equation That is, if $P(z,w) = -w + z + zw + zw^2 + zw^3$ then $P(z,T(z)) = 0$. If we draw (the real locus of) $P$ it looks like and the implicit function theorem says that we can find functions $f(z)$ so that $P(z,f(z)) = 0$ through any starting point $P(z_0,f_0)$ on the curve for as long as $\frac{\partial P}{\partial w} \neq 0$. In particular, we know that our $T(0) = t_0 = 0$ since there are no trees with zero vertices, so that our $T(z)$ takes $z$ to the unique part of this curve passing through the origin, for as long as this is defined. Here we’ll plot our curve $P$ in blue, and the implicit function $T(z)$ in orange. Note we have to stop at $z \approx 0.27695$ since here $\frac{\partial P}{\partial w} = 0$ so that the slope is infinite and we can’t continue. Said another way, we bend backwards and if we tried to continue we would fail the vertical line test. But since we have to stop here, we see that $0.27695$ is the radius of convergence for $T$, and is the dominant singularity! Next, can we find a good approximation for $T$ near this singularity? In the main post we used puiseux series for this, but it’s instructive to do it by hand! Note that $\frac{\partial P}{\partial z} \neq 0$ at $(0.27695, 0.65730)$ so there’s nothing stopping us from approximating $z$ as a function of $w$ at this point (then inverting it). Indeed, we can solve for $z = \frac{w}{1+w+w^2+w^3}$ and then just taylor expand this at our point of interest: Of course, we chose this point because $\frac{\mathrm{d}z}{\mathrm{d}w} = \frac{- \frac{\partial P}{\partial w}}{\frac{\partial P}{\partial z}}$ is $0$ here. So we know this $2.97 \times 10^{-8}$ is a rounding error and our leading order expansion is Here’s a graph zoomed into near the singularity. The actual graph of $P$ is shown in blue, and our approximating parabola is shown in orange: But of course if $z - 0.27695 \approx -.34680 (w - 0.6573)^2$ then we can solve for and if we want this to agree with our $w = T(z)$ branch through the origin we obviously have to choose the negative square root (since we want the lower half of this sideways parabola1). Here we draw our $T(z)$ in blue, and we draw the approximation $0.6573 - 0.8936 \sqrt{1 - \frac{z}{0.27695}}$ in orange so you can see how well they line up! But now from here we can run exactly the same argument as in the previous post! We compute $t_n = \frac{1}{2\pi i} \oint \frac{T}{z^{n+1}} \ \mathrm{d}z$, along a keyhole contour around the singular point $z=0.27695$ with a branch cut along the real axis. The brunt of this integral comes from the cutout near the singular point, where $T$ is well approximated by $0.6573 - 0.8936 \sqrt{1 - \frac{z}{0.27695}}$ so that Again, for more details about exactly what this keyhole contour is and how you estimate this integral along it, see the main post. Let’s go ahead and call it here! My actual talk was slightly longer than this, since I also sketched a proof of Dirichlet’s Theorem following Varilly’s notes on the subject, but there’s no sense in me writing that up since those notes are already so good! Plus it’s getting late and I want to go to bed, haha. As always, here’s a copy of my title and abstract. Unfortunately I don’t have any slides or recordings today, but I’m giving another talk at WiSCons in Madison next week and I should have slides for that. I’m also hoping to finish a sister blog post for that talk where I do more example computations in more detail than I could possibly do in a 20 minute talk. Lots of writing to do this week! Take care all, stay safe, and I can’t wait to talk soon ^_^ Counting is Hard. Complex Analysis is Easy. Don’t you miss being a kid, when your mom would ask you to count how many of your alphabet fridge magnets were both red and vowels? When you saw the answer was “2”, you felt such accomplishment…. But counting has only gotten harder since then, and now if you want to count how many objects satisfy some properties (say, being both red and vowels) it can be borderline impossible! In this talk we’ll show how you can solve counting problems by doing complex analysis instead. First we’ll count the number of trees of a certain shape, then (given time) we’ll count how many prime numbers are of a (different) certain shape. In the main post we used puiseux series for this, and we had to essentially guess which branch was correct. Now we see how the geometry of the situation tells us that we have to choose the negative branch of the square root! After all, this is the one that locally agrees with the rest of the graph of $T$! ↩

This will be a really quick one! Over the last two weeks I’ve been finishing up a big project to make DOIs for all the papers published in TAC, and my code takes a while to run. So while testing I would hit “go” and have like 10 minutes to kill… which means it’s time to start answering questions on mse again! I haven’t been very active recently because I’ve been spending a lot of time on research and music, but it’s been nice to get back into it. I’m especially proud of a few recent answers, so I think I might quickly turn them into blog posts like I did in the old days! In this post, we’ll try to understand the Capping Algorithm which turns a graph embedded in a surface into a particularly nice embedding where the graph cuts the surface into disks. I drew some pretty pictures to explain what’s going on, and I’m really pleased with how they turned out! So, to start, what’s this “capping algorithm” all about? Say you have a (finite) graph $G$ and you want to know what surfaces it embeds into. For instance planar graphs are those which embed in $\mathbb{R}^2$ (equivalently $S^2$), and owners of this novelty mug know that even the famously nonplanar $K_{3,3}$ embeds in a torus1: Obviously every graph embeds into some high genus surface – just add an extra handle for every edge of the graph, and the edges can’t possibly cross each other! Also once you can embed in some surface you can obviously embed in higher genus surfaces by just adding handles you don’t use. This leads to two obvious “extremal” questions: What is the smallest genus surface which $G$ embeds into? What is the largest genus surface which $G$ embeds into where all the handles are necessary? Note we can check if a handle is “necessary” or not by cutting our surface along the edges of our graph. If the handle doesn’t get cut apart then our graph $G$ must not have used it! This leads to the precise definition: Defn: A $2$-Cell Embedding of $G$ in a surface $S$ is an embedding so that all the conected components of $S \setminus G$ are 2-cells (read: homeomorphic to disks). Then the “largest genus surface where all the handles are necessary” amounts to looking for the largest genus surface where $G$ admits a 2-cell embedding! But in fact, we can restrict attention to 2-cell embeddings in the smallest genus case too, since if we randomly embed $G$ into a surface, there’s an algorithm which only ever decreases the genus and outputs a 2-cell embedding! So if $S$ is the minimal genus surface that $G$ embeds in, we can run this algorithm to get a 2-cell embedding of $G$ in $S$. And what is that algorithm? It’s called Capping, see for instance Minimal Embeddings and the Genus of a Graph by J.W.T. Youngs. The idea is to cut your surface along $G$, look for anything that isn’t a disk, and “cap it off” to make it a disk. Then you repeat until everything in a disk, and you stop. The other day somebody on mse asked about this algorithm, and I had a lot of fun drawing some pictures to show what’s going on2! This post basically exists because I was really proud of how these drawings turned out, and wanted to share them somewhere more permanent, haha. Anyways, on with the show! We’ll start with an embedding of a graph 𝐺 (shown in purple) in a genus 2 surface: we’ll cut it into pieces along $G$, and choose one of our non-disk pieces (call it $S$) to futz with: Now we choose3 a big submanifold $T \subseteq S$ which leaves behind cylinders when we remove it. Pay attention to the boundary components of $T$, called $J_1$ and $J_2$ below, since that’s where we’ll attach a disk to “cap off” where $T$ used to be We glue all our pieces back together, but remove the interior of $T$ and then, as promised “cap off” the boundary components $J_1$ and $J_2$ with disks. Note that the genus decreased when we did this! It used to be genus 2, and now we’re genus 1! Note also that $G$ still embeds into our new surface: Let’s squish it around to a homeomorphic picture, then do the same process a second time! But faster now that we know what’s going on: At this point, we can try to do it again, but we’ll find that removing $G$ cuts our surface into disks: This tells us the algorithm is done, since we’ve successfully produced a 2-cell embedding of $G$ ^_^. Wow that was a really quick one today! Start to finish in under an hour, but it makes sense since I’d already drawn the pictures and spent some time doing research for my answer the other day. Maybe I’ll go play flute for a bit. Thanks for hanging out, all! Stay safe, and see you soon ^_^ This photo of a solution was taken from games4life.co.uk ↩ You know it’s funny, even over the course of drawing just these pictures the other day I feel like I improved a lot… I have half a mind to redraw all these pictures even better, but that would defeat the point of a quick post, so I’ll stay strong! ↩ It’s possible there’s a unique “best” choice of $T$ and I’m just inexperienced with this algorithm. I hadn’t heard of it until I wrote this answer, so there’s a lot of details that I’m fuzzy on. If you happen to know a lot about this stuff, definitely let me know more! ↩

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! ↩