Meetup summary

2024-12-06 - Generatingfunctionologypracticum - Classical Edition

  • Wikipedia’s entry on formal power series, particularly the section on operations on formal power series.
  • Don Knuth’s treatment of power series in TAOCP (Volume 2, section 4.7). I believe this is only available starting in the third edition.
  • The supplemental post on formal power series composition. This is a surprisingly difficult operation, so I recommend prereading and thinking about it.
  • Stephen Melczer’s introduction of formal power series and their convergence in Invitation to Enumeration. This goes into some more formality that we’ll typically deal with so I would only recommend this if you’re really interested in the internal machinery of formal power series and generating functions.
  • If you want to appreciate the title of this meetup, check out Herbert Wilf’s book on generating functions.
  • My Python power series coefficient extraction recipes. It’s probably best to skim over the implementation details so we can “reimplement” this live, but it’s important to understand the target API. In particular, we want to represent a formal power series as an infinte stream of its coefficients. This is a good segue into the lazy stream method, which we’ll be investigating next time (hopefully). In practice, you would almost certainly want to use truncated series representations to save on memory and compute (in addition to exploiting other techniques that give much better than O(n3)O(n^3) runtime).
  • Knots!

Agenda:

The last few sessions have run over and not allowed nearly enough time to get through the original plan. We’ll try paring it down to a narrow subject this time.

  • Knot show and tell. This is not your mother’s mathematical embedding of the S1S^1 into 33-space, but rather something you can tie with a physical rope segment. “Bring” your favorite knot and be prepared to show us how to tie it and expound on its virtues and vices. I use the word “knot” generously. Feel free to choose a knot proper, a loop knot, a hitch, a bend, or any other knot-like structure that interests you. Google for something interesting if you don’t already have one. Optionally, bring some rope or cord for demonstration (though I’ll have some available for this purpose as well).
  • Discuss how to numerically pick out GF coefficients with simple programming techniques. Sadly, it turns out that working directly with GFs on real, complex problems quickly becomes infeasible on paper (modulo asymptotics), so we need a way to actually compute answers to the problems we care about. My hope is to get through the following:
    • The “obvious” operations (scalar multiplication, series addition, etc.)
    • Multiplication of a series by another series
    • Division (by a series)
    • Series composition
  • Discuss how the above, along with some additional tooling/abstractions, give you the ability to directly translate the admissible combinatorial constructions into values you can work with on a computer an extract coefficients from.
  • Work through a simple Python program that I’ve written to extract power series coefficients using “classical” (imperative generator) techniques. Verify that some canonical examples work (finite series, geometric series, well-known Taylor expansions, basic compositions of these).
  • If time allows: Go through some basic generating function problems with simple constructions.

Notes:

We went through all of the classical power series operations, including composition, and analyzed their runtimes and space requirements. We did not end up going through the actual Python implementation or work any practice problems and will do that next time instead.

Here are the knots people shared:

  • Trinity knot
  • Eskimo bowline
  • Reef knot and its close cousins (granny and thief’s knot)
  • Zeppelin bend and its “primary” eye knot1.

We also discussed the important notion of knot chirality and talked about how to identify the chirality of a simple overhand. However, we had a hard time identifying the chirality of the double overhand. I played with this a bit and found a nice way to identify it. Obviously, if you start with right-handed overhand, if you untuck the tail and make a second turn for the double overhand (moving in the same direction), you should still end up with a right-handed knot, but this time a double overhand. The way to recognize it is to use the right-hand rule to inspect the helix formed by the final tail2 coming out of the knot; ignore the crossing turns on the outside. I’ll include a graphic here if I can figure out how to show it clearly.

Footnotes

  1. We didn’t discuss this at the meetup, but the “primary” eye knot (my terminology) is the variant where the working end sticks out of one of the “sides” of the original bend. The standing end acts as one of the original ropes being joined, the outgoing leg is the other “rope”, and the incoming leg feeds in through the other “side” of the knot. By contrast, the “secondary” eye knot has the standing end coming in through one of the the “sides” of the knot (i.e., it would have formed a tail in the original bend).

    The different chiral options of the knot itself do not change the structure in an interesting way. ↩

  2. Note that you can just as well inspect the standing end on the other side, since this knot is symmetric. It will have the same chirality as the tail end. ↩

tags: