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

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 $f : {\mathbb N} \to {\mathbb N}$ is monotone (or order-preserving) if $x \leq y$ implies $f(x) \leq f(y)$ . A Galois connection on ${\mathbb N}$ is a pair $(f,g)$ of monotone functions $f : {\mathbb N} \to {\mathbb N}$ (called the left adjoint) and $g : {\mathbb N} \to {\mathbb N}$ (called the right adjoint) such that $f (m) \leq n$ if and only if $m \leq g(n)$ for all natural numbers $m$ and $n$ . It is a simple exercise to verify that $(f,g)$ is a Galois connection if and only if $f$ and $g$ determine one another by the formulas $f(m) = \min \{ n \in {\mathbb N} \; : \; m \leq g(n) \}$ and $g(n) = \max \{ m \in {\mathbb N} \; : \; f(m) \leq n \}$ .

Galois connections on ${\mathbb N}$ are ubiquitous in mathematics. For example, the pair $(p(n),\pi(n))$ is a Galois connection, where $p(0)=0$ and $p(n)$ is the $n^{\rm th}$ prime for $n\geq 1$ , and where $\pi(n)$ denotes the number of primes less than or equal to $n$ .

Here is a curious observation about this particular pair of functions: the sets $\{ p(m)+m \; : \; m \in {\mathbb N} \} = \{ 0+0,2+1,3+2,5+3,7+4\ldots \} = \{ 0,3,5,8,11 \}$ and $\{ \pi(n)+n+1 \; : \; n \in {\mathbb N} \} = \{ 0+1, 0+2, 1+3, 2+4, 2+5 \ldots \} = \{ 1,2,4,6,7\ldots \}$ 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 $(f,g)$ on ${\mathbb N}$ and complementary infinite sets $F$ and $G$ of natural numbers with $0 \in F$ . The bijection is given by the formulas $F = \{ f(m) + m \; : \; m \in {\mathbb N} \}$ and $G = \{ g(n) + n + 1 \; : \; n \in {\mathbb N} \}$ .

Before giving the proof, we present a few illustrative examples:

Example 1: Let $F$ be the set of perfect squares and $G$ its complement. Then $f(m) = m^2 - m$ and one shows easily that the right adjoint to $f$ is $g(n) = \max \{ m \in {\mathbb N} \; : \; f(m) \leq n \} = \{ \sqrt{n+1} \}$ . Thus $G = \{ n+1 + \{ \sqrt{n+1} \} \; : \; n \geq 0 \} = \{ n + \{ \sqrt{n} \} \; : \; n \geq 1 \}$ .

Example 2: Let $\rho$ be a positive irrational number, and let $f(m) = \lfloor \rho m \rfloor$ . Then the right adjoint to $f$ is $g(n) = \lfloor \rho^{-1} n \rfloor$ , and thus $F(m) = \{ \lfloor (1 + \rho)m \rfloor \; : \; m \geq 1 \}$ and $G(n) = \{ \lfloor (1 + \rho^{-1})n \rfloor \; : \; n \geq 1 \}$ are complementary sets of positive integers. (We have discarded $m=0$ and replaced $n+1$ by $n$ in order to make the formulas look nicer.) This is equivalent to Beatty’s theorem that if $\alpha,\beta$ are positive irrational numbers, then $A = \{ \lfloor \alpha m \rfloor \; : \; m \geq 1 \}$ and $B = \{ \lfloor \beta n \rfloor \; : \; n \geq 1 \}$ are complementary sets of positive integers if and only if $\frac{1}{\alpha} + \frac{1}{\beta} = 1$ .

Example 3: $E = \{ \lfloor e^m \rfloor + m \; : \; m \geq 1 \}$ and $L = \{ \lfloor \ln(n) \rfloor + n \; : \; n \geq 1 \}$ are complementary sets of positive integers.

Proof of the Lambek-Moser theorem: Suppose first that $(f,g)$ is a Galois connection on ${\mathbb N}$ . Fix $N \in {\mathbb N}$ , and let $[N] = \{ 0,1,\ldots, N \}$ . Consider natural numbers $m,n$ with $m+n=N$ . Since $f (m) \leq n$ if and only if $m \leq g(n)$ , we have $f (m)+m \leq N$ iff $g(n)+n \geq N$ iff $g(n)+n+1 > N$ . Thus

$(\star) \; F_m := f(m) + m \in [N]$ iff $G_n := g(n)+n+1\not\in [N].$

If $F_m = G_n$ for some $m,n \in {\mathbb N}$ then (setting $N = m+n$ ) we get a contradiction to $(\star)$ . Thus $F \cap G = \emptyset$ . Define a function $H_N : [N] \to [N]$ by $H_N(m) = F_m$ if $F_m \in [N]$ and $H_N(m) = G_m$ if $F_m \not\in [N]$ . This is well-defined and injective by $(\star)$ . Thus $H_N$ is surjective for all $N$ which means that $F \cup G = {\mathbb N}$ . Thus $F$ and $G$ are complements of one another.

Conversely, suppose $F$ and $G$ are complementary infinite sets of natural numbers with $0 \in F.$ For a set $A \subseteq {\mathbb N}$ , we denote by $A_0,A_1,A_2,\ldots$ the sequence of elements of $A$ in ascending order. Set $f(m)=F_m - m$ and $g(n) = G_n - n - 1$ . We need to prove that $f(m) \leq n$ iff $m \leq g(n)$ , which is equivalent (setting $N = m+n$ ) to $(\star)$ , i.e., $F_m \in [N]$ iff $G_n \not\in [N].$ If both $F_m$ and $G_n$ belong to $[N]$ then $F_0,F_1,\ldots,F_m$ and $G_0,G_1,\ldots,G_n$ are $N+2$ distinct natural numbers in the $(N+1)$ -element set $[N]$ , a contradiction. On the other hand, if neither $F_m$ nor $G_n$ belongs to $[N]$ then $F$ has at most $m$ elements in $[N]$ and $G$ has an most $n$ elements in $[N]$ , and thus $F \cup G$ has at most $m+n=N$ elements in $[N]$ , contradicting the fact that $F \cup G = {\mathbb N}$ . Thus exactly one of $F_m$ and $G_n$ belongs to $[N]$ , which establishes $(\star)$ . Q.E.D.

Concluding remarks:

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 $(A,\leq)$ and $(B,\leq)$ , a Galois connection between them consists of a pair of order-preserving functions $f : A \to B$ and $g : B \to A$ such that $f(a) \leq b$ iff $a \leq g(b)$ for all $a \in A$ and $b \in B$ . There are many interesting examples of Galois connections. For example, if $f : X \to Y$ is any function between sets then the image and inverse image operations form a Galois connection between the power sets of $X$ and $Y$ . There is a Galois connection between subgroups of a group $G$ and subsets of the underlying set $\underline{G}$ given by $H \mapsto \underline{H}$ and $S \mapsto \langle S \rangle$ . The operations $V$ and $I$ from algebraic geometry form an (antitone, i.e., order-reversing) Galois connection between subsets of the polynomial ring $K[X_1,\ldots,X_n]$ and subsets of the vector space $K^n$ for any field $K$ . 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 $x$ to $y$ whenever $x \leq y$ ; 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 $a$ and $b$ 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 $(a,b)=(\lfloor (1+\phi)n \rfloor, \lfloor (1+\phi^{-1})n \rfloor)$ for some $n \in {\mathbb N}$ , where $\phi = (-1 + \sqrt{5})/2$ 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 ${\mathbb N}$ into complementary sets $A$ and $B$ such that every positive integer is expressible as a sum of distinct numbers from $A$ in the same number of ways as it is expressible as a sum of distinct numbers from $B$ . Concretely, if we assume (without loss of generality) that $0 \in A$ , then $A$ (resp. $B$ ) consists of all natural numbers $n$ 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.

4 thoughts on “Complementary sets of natural numbers and Galois connections”

Trevor Hyde says:

September 12, 2019 at 11:00 pm

Hey Matt, nice post! In the proof of the theorem, when defining $H_n$ you condition on whether $m$ belongs to $[N]$, but I think it should be conditioned on whether $F_m$ belongs to $[N]$.

- Matt Baker says:
  
  September 13, 2019 at 1:10 am
  
  Yep, that was a serious typo. I’ve fixed it now — thanks, Trevor.
  
Isky Mathews says:

January 1, 2020 at 5:17 pm

Wonderful!

In your statement of the theorem, didn’t you mean to define $G=\{g(n)+n+1…\}$ rather than defining it as $F$ again?

- Matt Baker says:
  
  January 2, 2020 at 1:53 am
  
  Oops! Thanks for pointing that out… it has now been fixed.

Matt Baker's Math Blog

Thoughts on number theory, graphs, dynamical systems, tropical geometry, pedagogy, puzzles, and the p-adics

Complementary sets of natural numbers and Galois connections

4 thoughts on “Complementary sets of natural numbers and Galois connections”

Leave a Reply Cancel reply

Share this:

Like this:

Related

4 thoughts on “Complementary sets of natural numbers and Galois connections”

Leave a Reply Cancel reply