11 Jun 2021

Jad Hamdan and I have uploaded our paper “The lattice
of arithmetic progressions” to the arXiv. In it we study the partially
ordered set $L_n$ of all subsets of \([n] = \{1,2,\ldots,n\}\) that are arithmetic progressions, including
the empty set and trivial progressions of length $1$ and $2$. This poset is a lattice, but for $n\geq 4$, it
is not graded. We derive formulas and recurrences regarding
the numbers $p_{nk}$ of arithmetic progressions in $[n]$ of length $k$ as well as the number $b_{nk}$ of
chains in $L_n$ of length $k+2$ that contain both $\emptyset$ and $[n]$.
Let $\mu_n$ denote the Möbius function of the lattice; we give three short,
independent proofs of the fact that for $n\geq 2$, $\mu_n(L_n) = \mu(n-1)$, where $\mu$ is the classical
(number-theoretic) Möbius function. We finish off by computing the homology groups of the order complex
$\Delta_n$ of $L_n$.

**Update.** (*7 Sep 2021*) We have added a second version of the paper. Our good friend Jonah Saks has joined
the cause, helping us to strengthen the topological results in the second half of the paper. In particular,
we are now able to show that $\Delta_n$ has the homotopy type of a sphere or a point.

07 Mar 2021

I haven’t done a proper math blog post for awhile, and I’ve been meaning to learn more about the polynomial
method, so I thought I’d sit down and get to grips with the “combinatorial Nullstellensatz” (see Alon (1999)).
This was prompted when I realised that there were a couple of exercises in of Knuth’s books (namely Volume 2
and Volume 4, Fascicle 5) that concern
the Nullstellensatz. (I’m working off a preliminary draft of *Mathematical Preliminaries Redux* (MPR),
which was posted to Knuth’s website before the book came out; it is no longer there because the book is now out!
I do not know if the exercises (and numbering) in my draft correspond to the exercises in the actual book.)
I must confess to having seen the proof of the Nullstellensatz before
in Tao and Vu’s *Additive Combinatorics* which I read (read: skimmed) about three months ago, but I have forgotten
it and so this post will see me trying to reconstruct it, with some hints from Knuth.

01 Feb 2021

I’m taking a seminar class this semester on the Na-Dene languages as part of my linguistics minor, and this week
it is my turn to give a presentation on a paper in the field. I am covering a 1999 paper by Jeff Leer called
“Tonogenesis in Athabaskan”, and I thought it’d be good preparation to collect my thoughts in a blog post while
reading the paper. This is a bit of a departure from the mathematical content I usually deliver, but should
be in the original spirit of the blog. Most of my early posts involve me grappling and experimenting with
new ideas, and I’m sure there will be a lot of that in this post, since
most of the linguistic concepts found in this paper are completely new to me. Of course, you might get more
out of this post if you have read/are reading the paper as well, but I intend to make this a self-contained summary
of the paper for a somewhat more general audience.

26 Dec 2020

Rosie Zhao and I have just uploaded our paper “Arithmetic subsequences
in a random ordering of an additive set” to the arXiv.
In its simplest form, the problem we consider is
the following. Given an ordering of the numbers $1$ through $n$,
what is the length of the longest arithmetic subsequence that is embedded in this
permutation? For example, in the ordering $(2,7,1,6,3,4,5)$, the longest arithmetic subsequence is $(2,3,4,5)$,
which has length $4$. If we store the permutation in an array, the problem of finding the length of
the longest arithmetic subsequence is a popular programming interview question that can be solved efficiently
using dynamic programming (it is a
medium-difficulty problem on LeetCode). But
if we take the ordering to be random, with each of the $n!$ possibilities occurring with equal probability,
then the length $L_n$ of the longest arithmetic subsequence becomes a random variable. Our paper studies
the asymptotic behaviour of $L_n$ as $n$ gets large.

01 Aug 2020

Using Plain TeX in the 21st century isn’t as big a pain as it might seem. The main difference
between using TeX and LaTeX is that when you need a new feature in LaTeX, there is almost certainly a
package out there that does it, while with TeX, you have to be prepared to write your own solution.
I’ve written my own macros
for most of the things I
need to do on a daily basis, and the TeXbook
contains approaches to most problems, but
something that I never figured out how to do was format reference lists automatically. Recently, Prof. Luc
Devroye showed me how he formats his references: entirely using UNIX scripts! I expanded his script
to handle automatic numbering of references, and I thought I’d write a little post explaining how it works.