Reverse Mathematics of Complexity Lower Bounds

Reverse mathematics is simply exchanging axiom A contained in axiom system S with theorem T of axiom system S—creating new axiom system S-A+T—and then proving that A is a theorem of the axiom system S-A+T. Since T can be derived by assuming A and S-A, and since A can be derived by assuming T and S-A, then A and T are equivalent. Adding A to the axiom system S-A is the same as adding T to the axiom system S-A.

The pigeonhole principle (see below) appears to be an obviously true principle, but in mathematics, we must be clear and precise about everything, so we use the principle (or a variation of it) as an unproven axiom. I don't want to use pigeonholes (usually small openings in a cabinet for storing letters) or pigeons (rats with wings) in my version of the principle, so I will use cookie jars and cookies instead. I want to call it the cookie jar principle, but other mathematicians wouldn't know what I was talking about if I called it that.

Pigeonhole Principle: If we put M cookies into N cookie jars, and if M is larger than N, then at least one of the cookie jars will contain more than one cookie.

The remarkable paper accessible by the above link uses reverse mathematics to prove the surprising result that a version of the pigeonhole principle is equivalent to "several natural lower bound statements about communication complexity, error correcting codes, and Turing machines…" I've been having a delicious time wrapping my head around this weird result. For instance, the pigeonhole principle is equivalent to the statement there is a lower bound to the amount of time that it takes certain types of Turing machines to determine whether or not a string of zeros and ones is a palindrome. Bizarre, cool, and useful!

This amazing bit of reverse mathematics is telling us that some things which appear to be difficult to analyze are really the same as putting cookies into cookie jars. I wonder if Turing liked chocolate chip.

This post is a page of the Tidbits website.

• Tidbits home page

Subscribe to the web feed to receive notifications when new posts appear. Use a feed reader to subscribe to the web feed. The web feed is a text file containing code written in the Atom syndication format.

• Tidbits web feed

Thunderbird can be used as a web feed reader.

• How to subscribe to web feeds with Thunderbird

Elfeed is a web feed reader for Emacs. Elfeed is available on MELPA as the package elfeed. Elfeed can be configured with an Org Mode file using the elfeed-org extension.

Author: Flower Snark
Email: flowersnark@gmail.com

Made with GNU Emacs and Org Mode.

Copyright © 2026 Flower Snark
This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license (CC BY-SA 4.0).
CC BY-SA 4.0 summary
CC BY-SA 4.0 legal code

Page created on 2026-09-10T12:33:23-04:00.