# Complementary sets of natural numbers and Galois connections

In this post, I’d like to discuss a beautiful result about complementary sets of natural numbers due to Lambek and Moser. I first learned about their theorem as a high school student (from Ross Honsberger’s delightful book “Ingenuity in Mathematics”), but it’s only more recently that I learned about the “Galois” connection.

To motivate the discussion, consider the following question. Let $F = \{ 0,1,4,9,16,25,\ldots \}$ be the sequence of squares, and let $G = \{ 2,3,5,6,7,8,10,\ldots \}$ be its complement in ${\mathbb N} = \{ 0,1,2,3,\ldots \}$. What is the $n^{\rm th}$ term of the sequence $G$? In other words, can we give a formula for the $n^{\rm th}$ non-square? One might imagine that no simple formula exists, but in fact Lambek and Moser showed that the $n^{\rm th}$ non-square is equal to $n + \{ \sqrt{n} \}$, where $\{ x \}$ denotes the closest integer to $x$. Similarly, if $T = \{ 0,1,3,6,10,\ldots \}$ denotes the set of triangular numbers, the $n^{\rm th}$ element of the complement of $T$ is equal to $n + \{ \sqrt{2n} \}$.

Theorem: Let $M$ be a matroid on $n$ elements, and let $I_k(M)$ denote the number of independent sets of size $k$ in $M$. Then the sequence $I_k(M)$ is ultra-log-concave.
A special case of this result (which seems to be no easier to prove than the general case) is the following: Let $E$ be a set of $n$ vectors in some finite-dimensional vector space, and let $I_k$ denote the number of $k$-element linearly independent subsets of $E$. Then the sequence $I_k$ is ULC.