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

John Nash and the theory of games

John Forbes Nash and his wife Alicia nashwere tragically killed in a car crash on May 23, having just returned from a ceremony in Norway where John Nash received the prestigious Abel Prize in Mathematics (which, along with the Fields Medal, is the closest thing mathematics has to a Nobel Prize). Nash’s long struggle with mental illness, as well as his miraculous recovery, are depicted vividly in Sylvia Nasar’s book “A Beautiful Mind” and the Oscar-winning film which it inspired. In this post, I want to give a brief account of Nash’s work in game theory, for which he won the 1994 Nobel Prize in Economics. Before doing that, I should mention, however, that while this is undoubtedly Nash’s most influential work, he did many other things which from a purely mathematical point of view are much more technically difficult. Nash’s Abel Prize, for example (which he shared with Louis Nirenberg), was for his work in non-linear partial differential equations and its applications to geometric analysis, which most mathematicians consider to be Nash’s deepest contribution to mathematics. You can read about that work here. Continue reading