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 […]
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) […]
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 […]
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 […]
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.
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 […]
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 […]