A First Look at Google’s N-Gram Corpus In this post we will focus on the problem of finding the appropriate word boundaries in strings like “homebuiltairplanes”, as is common in web URLs like www.homebuiltairplanes.com. This is an interesting problem because humans do it so easily, but there is no o...

This primer is a third look at Python, and is admittedly selective in which features we investigate (for instance, we don’t use classes, as in our second primer on random psychedelic images). We do assume some familiarity with the syntax and basic concepts of the language. For a first primer on Pyth...

Rectangles, Trapezoids, and Simpson’s I just wrapped up a semester of calculus TA duties, and I thought it would be fun to revisit the problem of integration from a numerical standpoint. In other words, the goal of this article is to figure out how fast we can approximate the definite integral of a ...

And a Pinch of Python Next semester I am a lab TA for an introductory programming course, and it’s taught in Python. My Python experience has a number of gaps in it, so we’ll have the opportunity for a few more Python primers, and small exercises to go along with it. This time, we’ll be investigatin...

We’re quite eager to get to applications of algebraic topology to things like machine learning (in particular, persistent homology). Even though there’s a massive amount of theory behind it (and we do plan to cover some of the theory), a lot of the actual computations boil down to working with matri...

We are about to begin a series where we analyze large corpora of English words. In particular, we will use a probabilistic analysis of Google’s ngrams to solve various tasks such as spelling correction, word segmentation, on-line typing prediction, and decoding substitution ciphers. This will hopefu...

A Study In Data Just before midnight on Thanksgiving, there was a murder by gunshot about four blocks from my home. Luckily I was in bed by then, but all of the commotion over the incident got me thinking: is murder disproportionately more common on Thanksgiving? What about Christmas, Valentine’s Da...

This is a natural follow-up to our first gallery entry on the impossibility of tiling certain chessboards with dominoes. Problem: Suppose we remove two squares from a chessboard which have opposite color. Is it possible to tile the remaining squares with 2-by-1 dominoes? Solution: Notice that if we ...

Note, while the problem below arose in ring theory (specifically, Euclidean domains), the proof itself is elementary, and so the title should not scare away any viewers. In fact, we boil the problem down to something which requires no knowledge of abstract algebra at all. Problem: Show that the ring...

Recalling our series on Conway’s Game of Life, here is an implementation of Life within Life. Unfortunately, it does not “prove” what I hoped it might, so unless a reader has a suggestion on what this demonstration proves, it doesn’t belong in the proof gallery. But it sure is impressive.

Problem: Show 1 = 2 (with calculus) “Solution”: Consider the following: $ 1^2 = 1$ $ 2^2 = 2 + 2$ $ 3^2 = 3 + 3 + 3$ $ \vdots$ $ x^2 = x + x + \dots + x$ ($ x$ times) And since this is true for all values of $ x$, we may take the derivative of both sides, and the equality remains true. In other word...

Preamble: This proof is not particularly elegant or insightful. However, it belongs in this gallery for two reasons. First, it is an example of the goal of most mathematics: to classify things. In the same way that all natural numbers can be built up from primes, every group can be built up from sim...

or, How I Learned to Love Functional Programming We recognize that not every reader has an appreciation for functional programming. Yet here on this blog, we’ve done most of our work in languages teeming with functional paradigms. It’s time for us to take a stand and shout from the digital mountaint...

Problem: Determine an arithmetic expression for $ \binom{n}{2}$. Solution: The following picture describes a bijection between the set of yellow dots and the set of pairs of purple dots: In particular, selecting any yellow dots and travelling downward along diagonals gives a unique pair of blue dots...

Warning: this proof requires a bit of familiarity with the terminology of propositional logic and graph theory. Problem: Let $ G$ be an infinite graph. Show that $ G$ is $ n$-colorable if and only if every finite subgraph $ G_0 \subset G$ is $ n$-colorable. Solution: One of the many equivalent versi...

I want to thank all my readers for visiting Math ∩ Programming as often as you do, and doubly thank those who are kind enough to leave a comment. Unfortunately over the next few weeks I may not have time to do work as much on this blog as I have in the past two months. After driving 3,000 miles acro...

Problem: Show that $ \sqrt{2}$ is an irrational number (can’t be expressed as a fraction of integers). Solution: Suppose to the contrary that $ \sqrt{2} = a/b$ for integers $ a,b$, and that this representation is fully reduced, so that $ \textup{gcd}(a,b) = 1$. Consider the isosceles right triangle ...

This post assumes some basic familiarity with Euclidean geometry and linear algebra. Though we do not assume so much knowledge as is contained in our primer on inner product spaces, we will be working with the real Euclidean inner product. For the purpose of this post, it suffices to know about the ...

We will orient our dash of Python around the first and simplest problem from ProjectEuler.net. Installing Python To get Python on your computer, go to python’s website and follow the instructions for downloading and installing the interpreter. Most Window’s users can simply click here to download an...

So far on this blog we’ve assumed familiarity with the programming languages used (at the time of this writing, this is Mathematica and Java). This is unfair for the mathematicians who have little to no programming experience, and we admit that some readers tend to skim those technical sections with...

This primer exists for the background necessary to read our post on RSA encryption, but it also serves as a general primer to number theory. Oh, Numbers, Numbers, Numbers We start with some easy definitions. Definition: The set of integers, denoted $ \mathbb{Z}$, is the set $ \left \{ \dots -2, -1, ...

This post assumes working knowledge of elementary number theory. Luckily for the non-mathematicians, we cover all required knowledge and notation in our number theory primer. So Three Thousand Years of Number Theory Wasn’t Pointless It’s often tough to come up with concrete applications of pure math...

Problem: Show that every natural number can be unambiguously described in fewer than twenty words. “Solution”: Suppose to the contrary that not every natural number can be so described. Let $ S$ be the set of all natural numbers which are describable in fewer than twenty words. Consider $ R = \mathb...

This post assumes familiarity with the terminology and notation of linear algebra, particularly inner product spaces. Fortunately, we have both a beginner’s primer on linear algebra and a follow-up primer on inner products. The Quest We are on a quest to write a program which recognizes images of fa...

Vector spaces alone are not enough to do a lot of the interesting things we’d like them to do. Since a vector space is a generalization of Euclidean space, it is natural for us to investigate more specific types of vector spaces which are more akin to Euclidean space. In particular, we want to inclu...

We present a video on Möbius transformations and the geometry of the sphere. Anyone who has taken or will take complex analysis (that means you engineers!) should watch this. It shows not only the beautiful correspondence between the two, but it reveals the intuition behind a lot of complex analysis...

“Tonight’s the Night” A large volume of research goes into the psychological and behavioral analysis of criminals. In particular, serial criminals hold a special place in the imagination and nightmares of the general public (at least, American public). Those criminals with the opportunity to become ...

It seems that false proofs are quickly becoming some of the most popular posts on Math ∩ Programming. I have been preparing exciting posts on applications of graph coloring, deck stacking, and serial killers. Unfortunately, each requires resources which exist solely on my home desktop, which is curr...

Problem: Show that all horses are of the same color. “Solution”: We will show, by induction, that for any set of $ n$ horses, every horse in that set has the same color. Suppose $ n=1$, this is obviously true. Now suppose for all sets of $ n$ horses, every horse in the set has the same color. Consid...

How many colors are required to color the provinces of Costa Rica? A common visual aid for maps is to color the regions of the map differently, so that no two regions which share a border also share a color. For example, to the right is a map of the provinces of Costa Rica (where the author is prese...