Now blogging on Bluesky

November 22nd, 2024

I haven’t been actively blogging for several years at this point, but have instead been posting on other social media. These days I’m on Bluesky (@njohnston.ca), so here’s my Bluesky feed—come talk to me there:

Tags:

Minimal injective superstrings: A simpler generalization of superpermutations

May 6th, 2024

It seems that I write about superpermutations way too frequently, and today I’m going to continue the trend. Recall that a superpermutation is a string on n symbols that contains all n! permutations of those n symbols as contiguous substrings. For example, when n = 3, the 3! = 6 permutations of the symbols “1”, “2”, and “3” are 123, 132, 213, 231, 312, and 321, and a superpermutation is

123121321

since it contains all 6 of those permutations as substrings. That superpermutation is “minimal”: no shorter superpermutation on 3 symbols exists. We know how long minimal superpermutations are when n ≤ 5, but when n ≥ 6 determining this minimal length is still an open problem.

Somewhat surprisingly, there is a natural generalization of this problem that is actually easier to solve… in all cases except for the original case (superpermutations) that we care about. Here’s how it works: instead of requiring that the superstring contain all permutations as substrings, fix an additional parameter k that specifies the length of the substrings that it must contain. We say that a (length-k) string is injective if all of the characters in it are distinct, and we say that an injective superstring is a string that contains all injective strings (for a fixed pair of parameters n and k) as contiguous substrings. What is the minimal length of an injective superstring?

The requirement that the characters in an injective string be distinct forces the inequality k ≤ n. In the extreme case when k = n, an injective string is simply a permutation, so an injective superstring is simply a superpermutation, in which case the problem of finding a minimal one is hard. However, all other cases are easy: whenever k < n, it is known that minimal injective superstrings have length exactly equal to n!/(n-k)! + (k-1). For example, if n = 3 and k = 2 then the injective strings (strings of length 2 on the symbols “1”, “2”, and “3” in which all characters are distinct) are 12, 13, 21, 23, 31, and 32, and a minimal injective superstring (of length n!/(n-k)! + (k-1) = 6/1 + 2 = 8) is 1231321.

My latest video demonstrates how to construct minimal injective superstrings, and explains why they are so much easier to construct than minimal superpermutations:

Herschel tracks in Conway’s Game of Life – Part 1 – Making oscillators and glider guns of any period 61 or larger

April 19th, 2024

Back in September 1995, David Buckingham showed how to construct oscillators and glider guns of any period at least 61 in Conway’s Game of Life. His method was based on a tool called a “Herschel conduit“; a configuration of still lifes that can be used to move a Herschel from one location to another. By stitching together several of these Herschel conduits, we can create a complete track for the Herschel to move around, thus creating an oscillator (or a gun, if we let the glider that the Herschel naturally creates escape).

Herschel tracks are still used constantly in Conway’s Game of Life, and I’m starting a series of video tutorials that show how they work. Part 1 is now up:

The pattern animations throughout the video were all made with Manim. Once I get a few more videos under my belt, and my code cleaned up a bit more, I’ll share my code for making pretty Life animations.

Solving the “Lights Out” Puzzle via Linear Algebra

March 26th, 2024

Lights Out is a puzzle that sits in a very interesting place mathematically: while many puzzles can be solved with the help of math, Lights Out is solved exactly and completely by math (linear algebra in particular). Linear algebra doesn’t just make it easier to solve: it finds an exact solution, and does it so cleanly that it seems like Lights Out was made for mathematical reasons (even though it wasn’t, unlike some other puzzles).

So if you’re ever stuck in a video game that has this puzzle (which seems to be just about all of them), just give the following video a quick watch and then whip out your favourite linear algebra software to solve a too-large-to-want-to-solve-by-hand linear system:

The Manim Python script for creating the animations in this video is attached below since, given how absurdly long it took to put together, it would be a shame if no one else made use of it for anything. So please, make use of it – make more videos about Lights Out!

First true period 15 and 16 glider guns found in Conway’s Game of Life

March 18th, 2024

I’ve been meaning to make a series of videos on Conway’s Game of Life for a few years now, and I finally decided that rather than rehashing topics that are already covered in the textbook, I’ll make videos explaining particularly notable new discoveries as they’re made. Unfortunately, the news that Life is omniperiodic is somewhat well-worn at this point, so I started this week with a video about the newly-discovered true period 15 and 16 glider guns (which are both the first guns of their respective periods ever found, and which were found less than 5 hours apart!):

The video does delve into some “rehashed” stuff, like what a B-heptomino is, and how guns work in general, but that’s unavoidable if I want the video to be understandable to more than 100 or so people in the world. Hopefully a few news videos like this might actually convince enough people that Life is interesting enough so as to bump that “100” number up in the near future!

What is the Maximum Possible Area of 3 Circles in a Triangle?

March 13th, 2024

After a 3-year hiatus, I’m back making math videos, not least of all thanks to my new fancy-schmancy basement studio:

This time I’m trying this crazy technique called “editing”, rather than just recording myself and dumping raw video footage online (which, believe it or not, is what I did for my previous videos – those were all recorded “live”). My first new video is now up, which investigates the problem of how to place 3 non-overlapping circles in a triangle so as to cover as much area as possible (a problem that is often incorrectly thought to have the Malfatti circles as its solution):

I used Manim for the triangle and circle animations and Capcut to edit everything together. I’m going to aim for one video per week or so, and hopefully will be able to put together a decent Applied Calculus playlist this summer.

Tags: ,