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 .
In order to explain what’s really going on here, we’ll go down what at first would appear to be an unrelated path. A function is monotone (or order-preserving) if implies . A Galois connection on is a pair of monotone functions (called the left adjoint) and (called the right adjoint) such that if and only if for all natural numbers and . It is a simple exercise to verify that is a Galois connection if and only if and determine one another by the formulas and .
Galois connections on are ubiquitous in mathematics. For example, the pair is a Galois connection, where and is the prime for , and where denotes the number of primes less than or equal to .
Here is a curious observation about this particular pair of functions: the sets and are complements of one another! Have we discovered a profound new property of prime numbers? No, this is just a concrete instance of a general fact about Galois connections:
Theorem (Lambek–Moser): There is a natural bijection between Galois connections on and complementary infinite sets and of natural numbers with . The bijection is given by the formulas and .
Before giving the proof, we present a few illustrative examples:
Example 1: Let be the set of perfect squares and its complement. Then and one shows easily that the right adjoint to is . Thus .
Example 2: Let be a positive irrational number, and let . Then the right adjoint to is , and thus and are complementary sets of positive integers. (We have discarded and replaced by in order to make the formulas look nicer.) This is equivalent to Beatty’s theorem that if are positive irrational numbers, then and are complementary sets of positive integers if and only if .
Example 3: and are complementary sets of positive integers.
Proof of the Lambek-Moser theorem: Suppose first that is a Galois connection on . Fix , and let . Consider natural numbers with . Since if and only if , we have iff iff . Thus
If for some then (setting ) we get a contradiction to . Thus . Define a function by if and if . This is well-defined and injective by . Thus is surjective for all which means that . Thus and are complements of one another.
Conversely, suppose and are complementary infinite sets of natural numbers with For a set , we denote by the sequence of elements of in ascending order. Set and . We need to prove that iff , which is equivalent (setting ) to , i.e., iff If both and belong to then and are distinct natural numbers in the -element set , a contradiction. On the other hand, if neither nor belongs to then has at most elements in and has an most elements in , and thus has at most elements in , contradicting the fact that . Thus exactly one of and belongs to , which establishes . Q.E.D.
- The original paper of Lambek and Moser is “Inverse and Complementary Sequences of Natural Numbers”, American Math Monthly 61 (1954). The reformulation in terms of Galois connections was published later on by Lambek in “Some Galois Connections in Elementary Number Theory”, Journal of Number Theory 47 (1994). My proof is an adaptation of the argument in the latter paper; I was also influenced by the exposition in this paper. Dijkstra gives a “visual” proof of the Lambek-Moser theorem here; see also Ross Honsberger’s book “Mathematical Gems III”.
- Given two partially ordered sets and , a Galois connection between them consists of a pair of order-preserving functions and such that iff for all and . There are many interesting examples of Galois connections. For example, if is any function between sets then the image and inverse image operations form a Galois connection between the power sets of and . There is a Galois connection between subgroups of a group and subsets of the underlying set given by and . The operations and from algebraic geometry form an (antitone, i.e., order-reversing) Galois connection between subsets of the polynomial ring and subsets of the vector space for any field . And of course, the Galois correspondence can be viewed as an (antitone) Galois connection.
- Every partially ordered set can be viewed as a category in a natural way by introducing a (unique) morphism from to whenever ; from this point of view a Galois connection is the same thing as a pair of adjoint functors between the corresponding categories.
- Beatty sequences have some interesting connections to game theory. For example, Wythoff’s Nim is a two-player game in which the players alternate removing matches from two piles which start with and matches, respectively. A legal move consists of removing either k of matches from the first pile, k matches from the second pile, or k matches each from both piles (for some positive integer k). The player who takes the last match wins. One can show that the first player has a winning strategy iff for some , where is the golden mean.
- In the course of their investigations of complementary sets of natural numbers, Lambek and Moser discovered the following remarkable result (“On some two way classifications of integers”, Canad. Math. Bull. 2 (1959)): There is a unique way to partition into complementary sets and such that every positive integer is expressible as a sum of distinct numbers from in the same number of ways as it is expressible as a sum of distinct numbers from . Concretely, if we assume (without loss of generality) that , then (resp. ) consists of all natural numbers with an even (resp. odd) number of 1’s in their binary expansion.
- The Scott Kim image included above appears in Chapter III of Douglas Hofstadter’s book “Gödel, Escher, Bach: An Eternal Golden Braid”, where it is used as a metaphor for Hofstadter’s Figure-Figure sequences, an interesting recursively-defined pair of complementary sets of positive integers.