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

# p-adic Numbers and Dissections of Squares into Triangles

My thesis advisor Robert Coleman passed away two years ago today (see this remembrance on my blog).  One of the things I learned from Robert is that p-adic numbers have many unexpected applications (see, for example, this blog post).  Today I want to share one of my favorite surprising applications of p-adic numbers, to a simple problem in Euclidean geometry. Continue reading

# John Nash and the theory of games

John Forbes Nash and his wife Alicia were 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

# Post-Cherylmania wrap-up

My last post was about “Cheryl’s birthday puzzle”, which recently became an internet sensation.  I mentioned several additional puzzles in that post and promised solutions; here they are.

Let me begin, though, with a “cryptography” variant of the Cheryl puzzle which was sent to me by my friend and puzzle guru Pete Winkler:

Cheryl’s birthday possibilities are now May 14 or 15, June 15 or 16, July 16 or 17 or August 14 or 17. Albert gets the month and Bernard the day as before, and they both want to find out the birthday.  But Eve, who’s listening in, mustn’t find out.  How can A and B, who’ve never met before (and aren’t cryptographers), accomplish this mission?

Think about it, it’s a fun little puzzle!  [Pete writes in addition: “You can also do this with a cycle of 5 months (10 dates total) but then you need a coin to flip.”]

My Meta-Cheryl Challenge (as revised on April 20) was to come up with a list of dates for which the following puzzle will have a unique solution:

# Cherylmania

Many of you have undoubtedly heard by now the math puzzle about Cheryl’s birthday which has been sweeping across the internet.  I appeared on CNN on Wednesday to explain the solution — here is a link to the problem and my explanation.  Since that appearance, I’ve received dozens of emails about the problem and/or my explanation of it.   I thought I’d share a few of my thoughts following this flurry of activity. Continue reading

# A motivated and simple proof that pi is irrational

Today is 3/14/15 — Super Pi Day — so was I telling my 7-year-old son all about the number $\pi$ this afternoon.  When I told him that $\pi$ keeps on going forever and ever he asked “How do you know that?”  Although I don’t know a proof that I could explain to a 7-year-old, I wanted to record the following proof which uses only basic calculus.  It is essentially Niven’s famous proof, as generalized by Alan Parks, but I have tried to write it in a way which is more motivated than the usual treatments.  As a bonus, the proof also shows that e is irrational.

# Spooky inference and the axiom of choice

A large crowd had gathered in Harvard Square, and I was curious what all the cheering and gasping was about.  Working my way through the crowd, I saw a street performer who (according to the handwritten red letters on his cardboard sign) went by the name “Zorn the Magnificent”.  He displayed a large orange, borrowed an extremely sharp knife from his assistant, and proceeded to chop the orange into five exotic-looking pieces while standing on one hand.  Working with almost unfathomably deft precision, he rearranged the pieces into two oranges, each the same size as the original one.  The oranges were given out for inspection and the crowd cheered wildly.  I clapped as well — even though I was familiar with the old Banach-Tarski paradox — since it was nevertheless an impressive display of skill and I had never seen it done one-handed before.  I heard a man with a long white beard whisper to the woman next to him “He hides it well, but I know that he’s secretly using the Axiom of Choice.” Continue reading

# Real Numbers and Infinite Games, Part II

In my last post, I wrote about two infinite games whose analysis leads to interesting questions about subsets of the real numbers.  In this post, I will talk about two more infinite games, one related to the Baire Category Theorem and one to Diophantine approximation.  I’ll then talk about the role which such Diophantine approximation questions play in the theory of dynamical systems.

The Choquet game and the Baire Category Theorem

The Cantor game from Part I of this post can be used to prove that every perfect subset of ${\mathbf R}$ is uncountable.  There is a similar game which can be used to prove the Baire Category Theorem.  Let $X$ be a metric space.   In Choquet’s game, Alice moves first by choosing a non-empty open set $U_1$ in $X$.  Then Bob moves by choosing a non-empty open set $V_1 \subseteq U_1$.  Alice then chooses a non-empty open set $U_2 \subseteq V_1$, and so on, yielding two decreasing sequences $U_n$ and $V_n$ of non-empty open sets with $U_n \supseteq V_n \supseteq U_{n+1}$ for all $n$.  Note that $\bigcap U_n = \bigcap V_n$; we denote this set by $U$.  Alice wins if $U$ is empty, and Bob wins if $U$ is non-empty. Continue reading

# Real Numbers and Infinite Games, Part I

Georg Cantor

In this post I’d like to illustrate how one can use infinite games to prove theorems about the real numbers.  I’ll begin with a game-theoretic proof that the set of real numbers is uncountable, following the exposition in this paper of mine.  This will lead us somewhat unexpectedly into the realm of descriptive set theory, where we will discuss how games are used in cutting-edge explorations of the Axiom of Choice, the Continuum Hypothesis, and the foundations of second-order arithmetic.   In a sequel post I will discuss how infinite games can be used to study Diophantine approximation, with applications to complex dynamics.

Countable versus uncountable infinities

When my daughter was 5 years old, she asked me if there is just one infinity.  I proudly kissed her on the forehead and told her what an excellent question that was.  I told her no, infinity comes in many different flavors.  I pretty much left it at that, but since she’s 10 now, here are some more details for her.  (The reader familiar with the basics of set theory can move on to the next section.) Continue reading

# The Pentagon Problem

In this post I’ll talk about another favorite recreational math puzzle, the (in)famous “Pentagon Problem”.  First, though, I wanted to provide a solution to the Ghost Bugs problem from my last blog post.  The puzzle is the following:

You are given four lines in a plane in general position (no two parallel, no three intersecting in a common point). On each line a ghost bug crawls at some constant velocity (possibly different for each bug). Being ghosts, if two bugs happen to cross paths they just continue crawling through each other uninterrupted.  Suppose that five of the possible six meetings actually happen. Prove that the sixth does as well.

Here is the promised solution.  The idea (like in Einstein’s theory of general relativity) is to add an extra dimension corresponding to time.  We thus lift the problem out of the page and replace the four lines by the graph of the bugs’ positions as a function of time.  Since each bug travels at a constant speed, each of the four resulting graphs $g_i$ is a straight line.  By construction, two lines $g_i$ and $g_j$ intersect if and only if the corresponding bugs cross paths.

Suppose that every pair of bugs cross paths except possibly for bugs 3 and 4.  Then the lines $g_1, g_2, g_3$ each intersect one another (in distinct points) and therefore they lie in a common plane.  Since line $g_4$ intersects lines $g_1$ and $g_2$ in distinct points, it must lie in the same plane.  The line $g_4$ cannot be parallel to $g_3$, since their projections to the page (corresponding to forgetting the time dimension) intersect.  Thus $g_3$ and $g_4$ must intersect, which means that bugs 3 and 4 do indeed cross paths.

Cool, huh?  As I mentioned in my last post, I can still vividly remember how I felt in the AHA! moment when I discovered this solution more than 15 years ago.

# Beauty and explanation in mathematics

I just moved into a new house and haven’t had time to blog much lately.  But I did want to advertise my friend Manya Raman-Sundström’s upcoming Workshop on Beauty and Explanation in Mathematics at Umeå University in Sweden: http://mathbeauty.wordpress.com/wbem/

The list of invited speakers includes Hendrik Lenstra, one of my graduate school teachers.  (If you haven’t see it before, you should check out Lenstra’s lovely short article Profinite Fibonacci Numbers.) Continue reading

# Quadratic reciprocity and Zolotarev’s Lemma

I want to explain a beautiful proof of the Law of Quadratic Reciprocity from c. 1874 due to Egor Ivanovich Zolotarev (1847-1878). Some time ago I reformulated Zolotarev’s argument (as presented here) in terms of dealing cards and I posted a little note about it on my web page. After reading my write-up (which was unfortunately opaque in a couple of spots), Jerry Shurman was inspired to rework the argument and he came up with this elegant formulation which I think may be a “proof from the book”.  The following exposition is my own take on Jerry’s argument.  The proof requires some basic facts about permutations, all of which are proved in this handout.

Let $m$ and $n$ be odd relatively prime positive integers.  You have a stack of $mn$ playing cards numbered 0 through $mn-1$ and you want to deal them onto the table in an $m \times n$ rectangular array.  Consider the following three ways of doing this:

Row deal ($\rho$) : Deal the cards into rows, going left to right and top to bottom.