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} \}.

Figure by Scott Kim
Continue reading