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 be the sequence of squares, and let be its complement in . What is the term of the sequence ? In other words, can we give a formula for the non-square? One might imagine that no simple formula exists, but in fact Lambek and Moser showed that the non-square is equal to , where denotes the closest integer to . Similarly, if denotes the set of triangular numbers, the element of the complement of is equal to .

Continue reading