# A Complexity-Theoretic Account of The Strong Law of Small Numbers

The Strong Law of Small Numbers (see also Wikipedia) says that “There aren’t enough small numbers to meet the many demands made of them.” It means that when you look at small numbers, it’s easy to see compelling patterns that turn out to be false when you look at larger numbers. Using complexity theory, we […]

# Two Constants: Khinchin and Chaitin

Take a real number, .  Write out its continued fraction: It’s an intriguing fact that if you look at the sequence of geometric means this approaches a single constant, called Khinchin’s constant, which is approximately , for almost every .  This means that if you were to pick (for convenience, say it’s between 0 and 1) […]

# A Good Definition of Randomness

Most mathy people have a pretty good mental model of what a random process is (for example, generating a sequence of 20 independent bits). I think most mathy people also have the intuition that there’s a sense in which an individual string like 10101001110000100101 is more “random” than 0000000000000000000 even though both strings are equally […]

# Why is the derivative of a generating function meaningful?

A generating function is a formal power series where the sequence of coefficients is the object of interest. Usually the point of using them is that operations on the power series (like addition, multiplication, and differentiation) correspond to meaningful operations on your sequence of coefficients. I’ve known about the gist of generating functions for a […]

# Complexity to Simplicity and Back Again

Generalizing a problem can make the solution simpler or more complicated, and it’s often hard to predict which beforehand. Here’s a mini-example of a puzzle and four generalizations which alternately make it simpler or more complicated.

# Generating Functions as Cardinality of Set Maps

There is a class of all cardinalities , and it has elements , and operations , , and so forth defined on it. Furthermore, there is a map which takes sets to cardinalities such that (and so on). Ordinary generating functions can be thought of entirely analogously with set maps replacing sets: There is a […]

# Mathematica and Quantifier Elimination

In 1931, Alfred Tarski proved that the real ordered field allows quantifier elimination: i.e., every first-order formula is equivalent to one with no quantifiers.  This is implemented in Mathematica’s “Resolve” function. The Resolve function is called like Resolve[formula,domain] where domain gives the domain for the quantifiers in formula.  Since we’ll always be working over in […]