Category Archives: Proof Gallery

There are Infinitely Many Primes (Erdős)

Posted on by

Problem: Prove there are infinitely many primes

Solution: Denote by $ \pi(n)$ the number of primes less than or equal to $ n$. We will give a lower bound on $ \pi(n)$ which increases without bound as $ n \to \infty$.

Note that every number $ n$ can be factored as the product of a square free number $ r$ (a number which no square divides) and a square $ s^2$. In particular, to find $ s^2$ recognize that 1 is a square dividing $ n$, and there are finitely many squares dividing $ n$. So there must be a largest one, and then $ r = n/s^2$. We will give a bound on the number of such products $ rs^2$ which are less than or equal to $ n$.

If we want to count the number of square-free numbers less than $ n$, we can observe that each square free number is a product of distinct primes, and so (as in our false proof that there are finitely many primes) each square-free number corresponds to a subset of primes. At worst, we can allow these primes to be as large as $ n$ (for example, if $ n$ itself is prime), so there are no more than $ 2^{\pi(n)}$ such subsets.

Similarly, there are at most $ \sqrt{n}$ square numbers less than $ n$, since if $ x > \sqrt{n}$ then $ x^2 > n$.

At worst the two numbers $ r, s^2$ will be unrelated, so the total number of factorizations $ rs^2$ is at most the product $ 2^{\pi(n)}\sqrt{n}$. In other words,

$ 2^{\pi(n)}\sqrt{n} \geq n$

The rest is algebra: divide by $ \sqrt{n}$ and take logarithms to see that $ \pi(n) \geq \frac{1}{2} \log(n)$. Since $ \log(n)$ is unbounded as $ n$ grows, so must $ \pi(n)$. Hence, there are infinitely many primes.

Discussion: This is a classic analytical argument originally discovered by Paul Erdős. One of the classical ways to investigate the properties of prime numbers is to try to estimate $ \pi(n)$. In fact, much of the work of the famous number theorists of the past involved giving good approximations of $ \pi(n)$ in terms of logarithms. This usually involved finding good upper bounds and lower bounds and limits. Erdős’s proof is entirely in this spirit, although there are much closer and more accurate lower and upper bounds. In this proof we include a lot of values which are not actually valid factorizations (many larger choices of $ r, s^2$ will have their product larger than $ n$). But for the purposes of proving there are infinitely many primes, this bound is about as elegant as one can find.

Double Angle Trigonometric Formulas

Posted on by

Problem: Derive the double angle identities

$ \sin(2\theta) = 2\sin(\theta)\cos(\theta)\\ \cos(2\theta) = \cos^2(\theta) – \sin^2(\theta)$

Solution: Recall from linear algebra how one rotates a point in the plane. The matrix of rotation (derived by seeing where $ (1,0)$ and $ (0,1)$ go under a rotation by $ \theta$, and writing those coordinates in the columns) is

$ A = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{pmatrix}$

Next, note that to rotate a point twice by $ \theta$, we simply multiply the point (as a vector) by $ A$ twice. That is, multiply by $ A^2$:

$ AAv = A^2v$

Computing $ A^2$ gives the following matrix:

$ A^2 = \begin{pmatrix} \cos^2(\theta) – \sin^2(\theta) & -2\sin(\theta)\cos(\theta) \\ 2\sin(\theta)\cos(\theta) & \cos^2(\theta) – \sin^2(\theta) \end{pmatrix}$

But rotating twice by $ \theta$ is the same as rotating once by $ 2\theta$, so we have the equality:

$ \begin{pmatrix} \cos(2\theta) & -\sin(2\theta) \\ \sin(2\theta) & \cos(2\theta) \end{pmatrix} = \begin{pmatrix} \cos^2(\theta) – \sin^2(\theta) & -2\sin(\theta)\cos(\theta) \\ 2\sin(\theta)\cos(\theta) & \cos^2(\theta) – \sin^2(\theta) \end{pmatrix}$

The matrices are equal, so they must be equal entrywise, giving the identities we desire. $ \square$

Discussion: There are (painful, messy) ways to derive these identities by drawing triangles on the unit circle and cultishly chanting “soh-cah-toa.” The key idea in this proof that one might study geometric transformations, and it is a truly mature viewpoint of mathematics. Specifically, over the last two hundred years the field of mathematics has changed focus from the study of mathematical “things” to the study of transformations of mathematical things. This proof is an elementary example of the power such perspective can provide. If you want to be really high-brow, start asking about transformations of transformations of things, and transformations of those transformations, and recurse until you’re doing something original.

False Proof – 2 = 4, As the Limit of an Infinite Power Tower

Posted on by

Problem: Prove that $ 2 = 4$.

Solution: Consider the value of the following infinitely iterated exponent:

$ \displaystyle \sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\cdot^{\cdot^{\cdot}}}}}$

Let $ a_n = \sqrt{2} \uparrow \uparrow n$, that is, the above power tower where we stop at the $ n$-th term. Then $ a_n$ is clearly an increasing sequence, and moreover $ a_n \leq 4$ by a trivial induction argument: $ \sqrt{2} \leq 4$ and if $ a_n \leq 4$ then $ a_{n+1} = (\sqrt{2})^{a_n} \leq (\sqrt{2})^{4} = 4$.

So by basic results in analysis, the sequence of $ a_n$ converges to a limit. Let’s call this limit $ x$, and try to solve for it.

It is not hard to see that $ x$ is defined by the equation:

$ \displaystyle (\sqrt{2})^x = x,$

simply because the infinite power tower starting at the second level is the same as the infinite power tower starting at the first level. However, we notice that $ x=2$ and $ x=4$ both satisfy this relationship. Hence,

$ \displaystyle 2 = \sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\cdot^{\cdot^{\cdot}}}}} = 4$

And hence $ 2=4$, as desired. $ \square$

Explanation: The issue here is relatively subtle, but one trained in real analysis should have no trouble spotting the problem.

The first alarm is that we are claiming that the limit of a sequence is not unique, which is always false. Inspecting this argument more closely, we corner the flaw to our claim that $ x$ is defined by the equation $ (\sqrt{2})^x = x$. It does, in fact, satisfy this equation, but there is a world of difference between satisfying an equation and being defined by satisfying an equation. One might say that this only makes sense when there is a unique solution to the equation. But as we just saw, there are multiple valid solutions here: 2 and 4 (I don’t immediately see any others; it’s clear no other powers of two will work).

Analogously, one might erroneously say that $ i$ is defined by satisfying the equation $ x^2 = -1$, but this does not imply $ i = -i$, since the equation has two differing complex roots. This is a slightly murky analogy, as complex conjugation gives an automorphism of $ \mathbb{C}$. One would reasonably argue that $ i$ and $ -i$ “play the same role” in this field, while 2 and 4 play wildly different roles as real numbers. But nevertheless, they are not equal simply by virtue of satisfying the same equation.

Moreover, while we said the sequence was bounded from above by 4, an identical argument shows it’s bounded from above by 2. And so one can immediately conclude that the limit of the sequence cannot be 4.

In fact, this infinite tower power $ x^{x^{\cdot^{\cdot^{\cdot}}}}$ is continuous as a function, whose domain is the interval $ [e^{-e}, \sqrt[e]{e}]$ and whose range is $ [e^{-1},e]$. For more information about interesting number-theoretic properties of infinite power towers, see this paper.

Classic Nintendo Games are NP-Hard

Posted on by

The heroes and heroines of classic Nintendo games.

Problem: Prove that generalized versions of Mario Brothers, Metroid, Donkey Kong, Pokemon, and Legend of Zelda are NP-hard.

Solution: http://arxiv.org/pdf/1203.1895v1.pdf

Discussion: Three researchers (including Erik Demaine, a computer science professor at MIT famous for his work with the mathematics of origami) recently finished a paper giving the complexity of a number of classic Nintendo games (the ones I loved to play). All are proven NP-hard, some are shown to be NP-complete, and some are PSPACE-complete. Recall, a problem is NP-hard if an NP-complete problem reduces to it, and a problem is NP-complete if it’s NP-hard and also in NP. As we have just posted a primer on NP-completeness and reduction proofs, this paper is a fun next step for anyone looking for a more detailed reduction proof. A pre-print is available for free on arXiv, and it’s relatively short and easy to read. I’ll summarize his result here, and leave most of the details to the reader. Each game is “generalized” to the task of determining whether one can get from a “start” location to a “finish” location. So the decision problem becomes: given a finite level of a game, can the player move from the starting location to the finishing location? All of the reduction proofs are from 3-Sat, and they all rely on a common framework which can be applied to any platform game. Pictorially, the framework looks like this:

The framework for reducing 3-Sat to platform games.

The player starts in the “start” gadget, which allows one to set up initial state requirements. For instance, in Super Mario Brothers, the start provides you with a mushroom, and you cannot get to the finish without being able to break blocks by jumping under them, which requires the mushroom power-up. Each “variable” gadget requires the player to make a variable assignment in such a way that the player can never return to that gadget to make a different decision. Then each “clause” gadget can be “unlocked” in some way, and each clause gadget can only be visited by the player once the player has chosen a satisfying variable assignment for that clause. Once the player has visited all variable gadgets, he goes to the “check in” area, and can travel back through all of the clauses to the finish if and only if he unlocked every clause. The crossover of the paths in the picture above requires another gadget to ensure that the player cannot switch paths (the details of this are in the paper).

For example, here is the variable gadget described in the paper for The Legend of Zelda, a Link to the Past:

The variable gadget for A Link to the Past.

Note that here we require Link has the hookshot, which can grapple onto chests, but has limited reach. The configuration of the chests requires him to choose a path down one of the two columns at the bottom, and from there he may never return.

Here’s another example. In the classic Super Mario Brothers game, a possible clause gadget is as follows.

The clause gadget for the original Super Mario Brothers.

Note that if the player can only enter through one of the three columns at the top, then the only thing he can do is kick a red koopa shell down so that it breaks the blocks, unlocking the way for Mario to pass underneath at the end. Note that Mario cannot win if he falls from the top ledge (since must always remain large, he can’t fit through a one-tile-high entryway). Further details include the hole at the bottom, in which any stray koopa shell will necessarily fall, but which Mario can easily jump over. We recommend reading the entire paper, because it goes into all of the necessary details of the construction of the gadgets for all of the games.

Future Work

We note that there are some parts of the paper that only got partial results, mostly due to the variation in the game play between the different titles. For instance, the original Super Mario Brothers is known to be NP-complete, but the added ability to pick up koopa shells in later Super Mario Brothers games potentially makes the decision problem more complex, and so it is unknown whether, say, Super Mario World is in NP. We will summarize exactly what is known in the table below. If readers have additions for newer games (for instance, it’s plausible that Super Mario Galaxy could be adapted to fit the same construction as the original Super Mario Bros.), please leave a comment with justification and we can update the table appropriately. I admit my own unfamiliarity with some of the more recent games.

Super Mario Brothers:

Game Title NP-hard in NP PSPACE-complete
Super Mario Bros. ✓ ✓
Lost Levels ✓ ✓
Super Mario Bros. 2
Super Mario Bros. 3 ✓
Super Mario Land
Super Mario World ✓
Land 2: 6 Golden Coins
Super Mario Land 3
Yoshi’s Island
Super Mario 64
Sunshine
New Super Mario Bros.
Galaxy
New Super Mario Bros. Wii
Galaxy 2
Super Mario 3D Land

Legend of Zelda:

Game Title NP-hard in NP PSPACE-complete
The Legend of Zelda ✓
The Adventure of Link
A Link to the Past ✓
Link’s Awakening ✓
Ocarina of Time ✓ ✓
Majora’s Mask ✓ ✓
Oracle of Seasons ✓ ✓
Oracle of Ages
The Wind Waker ✓
Four Swords Adventures
The Minish Cap ✓ ✓
Twilight Princess ✓
Phantom Hourglass
Spirit Tracks
Skyward Sword ✓

Donkey Kong:

Game Title NP-hard in NP PSPACE-complete
Donkey Kong
Donkey Kong Country ✓ ✓
Donkey Kong Land ✓ ✓
Country 2: Diddy’s Kong Quest ✓ ✓
Land 2 ✓ ✓
Country 3: Dixie Kong’s Double trouble! ✓ ✓
Land 3 ✓ ✓
Donkey Kong 64
Donkey Kong Country Returns

Metroid:

Game Title NP-hard in NP PSPACE-complete
Metroid ✓ ✓
Metroid II: Return of Samus
Super Metroid ✓ ✓
Fusion
Prime ✓ ✓
Prime 2: Echoes
Prime Hunters ✓ ✓
Prime 3: Corruption ✓ ✓
Other M ✓ ✓

Pokemon:

Game Title NP-hard in NP PSPACE-complete
All Games ✓
Only trainers ✓ ✓