# Circle Inversion and the Pappus Chain

There is a pledge of the big and of the small in the infinite.

-Dejan Stojanović

In the next two posts, we are going to look at two interesting geometric ideas of the 19th century involving circles. Next time, we will consider Poincaré’s disk model for hyperbolic geometry. Today, though, we immerse ourselves in the universe of inversive geometry.

Consider a circle in the infinite 2-dimensional plane:

This circle divides the plane into two regions: the bounded region inside the circle and the unbounded region outside the circle (let’s say that the points on the circle belong to both regions). A natural thing to want to do, now, especially in the context of this blog, would be to try to exchange these two regions, to map the infinite space outside the circle into the bounded space of the circle, and vice versa, in a “natural” way.

I could be bounded in a nutshell, and count myself a king of infinite space.

-William Shakespeare, Hamlet

Upon first reflection, one might be tempted to say that we want to “reflect” points across the circle. And this is sort of right, but reflection already carries a meaning in geometry. Truly reflecting points across the circle would preserve their distance from the circle, so the inside of the circle could only be mapped onto a finite ring whose outer radius is twice that of the circle two. Moreover, it would not be clear how to reflect points from outside this ring into the circle.

Instead, we want to consider a process known as “inversion.” Briefly speaking, we want to arrange so that points arbitrarily close to the center of the circle get sent to points arbitrarily far away from the center of the circle, and vice versa. For simplicity, let us suppose that the circle is centered at the origin of the plane and has a radius of 1. The most natural way to achieve our aim is to send a point $P$ to a point $P'$ that lies in the same direction from the origin as $P$ and whose distance from the origin is the reciprocal of the distance from $P$ to the origin. Here’s an example:

One can check that, algebraically, this inversion sends a point $P$ with coordinates $(x,y)$ to a point $P'$ with coordinates $(\frac{x}{x^2+y^2}, \frac{y}{x^2+y^2})$. Points inside the circle are sent to points outside the circle, points outside the circle are sent to points inside the circle, and points on the circle are sent to themselves. Moreover, as one might expect from the name, the inversion map is its own inverse: applying it twice, we end up where we started. Perfect!

Wait a second, though. We’re being a little too hasty. What about the origin? Where is it sent? Our procedure doesn’t seem to tell us, and if we try to use our algebraic expression, we end up dividing by zero. Since the origin is inside the circle, it should certainly be sent to a point outside the circle, but all of those points are already taken. Also, since points arbitrarily close to the origin get mapped to points arbitrarily far from the origin, we want to send the origin to a point as far away from itself as possible. At first glance, we might seem to be in a quandary here, but longtime readers of this blog will see an obvious solution: the origin gets mapped to a point at infinity! (And the point at infinity, in turn, gets mapped to the origin.)

(Technical note: Since we’ve added a point at infinity, the inversion map should be seen not as a map on the plane $\mathbb{R}^2$, but on its one-point compactification (or Alexandroff compactification), $\hat{\mathbb{R}}^2$. In fact, the inversion map is a topological homeomorphism of $\hat{\mathbb{R}}^2$ with itself.)

Let’s examine what the inversion map does to simple geometric objects. We have already seen what happens to points. It should also be obvious that straight lines through the origin get mapped to themselves. For example, in the image above, the line connecting $P$ and $P'$ gets mapped to itself. (Here we are specifying, of course, that every line contains the point at infinity.)

A bit of thought and calculation will convince you that lines not passing through the origin get sent to circles that do pass through the origin.

Since the inversion map is its own inverse, circles passing through the origin get mapped to lines that don’t pass through the origin. Circles that don’t pass through the origin, on the other hand, get mapped to other circles that don’t pass through the origin.

There’s an important special case of this phenomenon: a circle that is met perpendicularly by the circle through which we are inverting gets mapped to itself.

We thus have a sort of duality between lines and circles that has been revealed through the process of circle inversion. Lines, when seen in the right light, are simply circles with an infinite radius. We’re going to move on to some applications of circle inversion in just a sec, but, first, a pretty picture of an inverted checkerboard.

The introduction of the method of circle inversion is widely attributed to the Swiss mathematician Jakob Steiner, who wrote a treatise on the matter in 1824. When combined with the more familiar rigid transformations of rotation, translation, and reflection, the decidedly non-rigid transformation of inversion gives rise to inversive geometry, which became a major topic of study in nineteenth geometry. It was perhaps most notably applied by William Thomson (later to become 1st Baron Kelvin, immortalized in the name of a certain temperature scale), at the age of 21, to solve problems in electrostatics. Circle inversion also allows for extremely elegant proofs of classical geometric facts. We end today’s post with an example.

Consider three half-circles, all tangent to one another and centered on the same horizontal line, with two placed inside the third, as follows:

This figure (or, more precisely, the grey region enclosed by the semicircles) is known as an arbelos, and its first known appearance dates back to The Book of Lemmas by Archimedes. A remarkable fact about the arbelos is that, starting with the smallest of the semicircles in the figure, one can nestle into it an infinite sequence of increasingly small circles, each tangent to the two larger semicircles and the circle appearing before it, thus creating the striking Pappus chain, named for Pappus of Alexandria, who investigated the figure in the 3rd century AD:

Let us label the circles in the Pappus chain (starting with the smallest semicircle in the arbelos) $\mathcal{C}_0, \mathcal{C}_1, \mathcal{C}_2$, etc. (So, in the picture above, $P_1$ is the center of $\mathcal{C}_1$, $P_2$ is the center of $\mathcal{C}_2$, and so on.) Clearly, the size of $\mathcal{C}_n$ decreases as $n$ increases, but it is natural to ask how quickly it decreases. It is also natural to ask how the position of the point $P_n$ changes as $n$ increases. In particular, what is the height of $P_n$ above the base of the figure? It turns out that the answers to these two questions are closely related, a fact discovered by Pappus through a long and elaborate derivation in Euclidean geometry, and which we will derive quickly and elegantly through circle inversion.

Let $d_n$ denote the diameter of the circle $\mathcal{C}_n$, and let $h_n$ denote the height of the point $P_n$ above the base of the Pappus chain (i.e., the line segment $AB$). We will prove the remarkable formula:

For all $n \in \mathbb{N}$$h_n = n \cdot d_n$.

For concreteness, let us demonstrate the formula for $\mathcal{C}_3$. The same argument will work for each of the circles in the Pappus chain. As promised, we are going to use circle inversion. Our first task is to find a suitable circle across which to invert our figure. And that circle, it turns out, will be the circle centered at $A$ and perpendicular to $\mathcal{C}_3$:

Now, what happens when we invert our figure? First, consider the two larger semicircles in the arbelos, with diameters $AC$ and $AB$. The circles of which these form the upper half pass through the center of our circle of inversion and thus, as discussed above, are mapped to straight lines by our inversion. Moreover, since the centers of these circles lie directly to the right of $A$, a moment’s thought should convince you that they are mapped to vertical lines.

Now, what happens to the circles in the Pappus chain? Well, none of them pass through $A$, so they will all get mapped to circles. $\mathcal{C}_3$ is perpendicular to the circle of inversion, so it gets mapped to itself. But, in the original diagram, $\mathcal{C}_3$ is tangent to the larger semicircles in the arbelos. Since circle inversion preserves tangency, in the inverted diagram, $\mathcal{C}_3$ is tangent to the two vertical lines that these semicircles are mapped to. And, of course, the same is true of all of the other circles in the Pappus chain. Finally, note that, since the center of $\mathcal{C}_0$ lies on the base of the figure, which passes through the center of our inversion circle, it also gets mapped to a point on the base of the figure. Putting this all together, we end up with the following striking figure:

The circle with diameter $AB$ gets mapped to the vertical line through $B'$, and the circle with diameter $AC$ gets mapped to the vertical line through $C'$. Our Pappus chain, meanwhile, is transformed by inversion into an infinite tower of circles, all of the same size, bounded by these vertical lines. Moreover, the circle $\mathcal{C}_3$ and the point $P_3$ are left in place by the inversion. It is now straightforward to use this tower to calculate the height $h_3$ of $P_3$ in terms of the diameter $d_3$ of $\mathcal{C}_3$. To get from $P_3$ down to the base, we must first pass through half of $\mathcal{C}_3$, which has a height of $\frac{d_3}{2}$. We then must pass through the image of $\mathcal{C}_2$ under the inversion, which has a height of $d_3$. Then the image of $\mathcal{C}_1$, which also has a height of $d_3$. And, finally, the image of the smallest semicircle of the arbelos, which has a height of $\frac{d_3}{2}$. All together, we get:

$h_3 = \frac{d_3}{2} + d_3 + d_3 + \frac{d_3}{2} = 3d_3$.

Pretty nice!

For further reading on circle inversion, see Harold P. Boas’ excellent article, “Reflections on the Arbelos.”

Cover image: René Magritte, The false mirror

Trying to make sense of it doesn’t make sense.

A spa town in the Czech Republic, Marienbad was a favored vacation spot of European royalty and celebrities during the 19th and early 20th centuries. Some mathematicians came, too: Karl Weierstrass, Gösta Mittag-Leffler, and Sofia Kovalevskaya were all drawn by the combination of the restful atmosphere and sparkling social life that could be found at the spa.

Though its golden era ended in the early 20th century, Marienbad remained popular between the world wars. Among the visitors during that time was a young Kurt Gödel. According to some accounts, Gödel’s interest in the sciences was kindled by a teenage visit to Marienbad, during which he and his brother studied Goethe’s philosophical theory of color and found it lacking in comparison to Newton’s more strictly scientific account.

After the war we were in Marienbad quite often with my brother, and I remember that we once read Chamberlain’s biography of Goethe together. At several points, he took a special interest in Goethe’s theory of color, which also served as a source of his interest in the natural sciences. In any case, he preferred Newton’s analysis of the color spectrum to Goethe’s.

-Rudolf Gödel

Goethe himself was a frequent visitor to Marienbad. During an 1823 trip, the 73-year-old Goethe became infatuated with the 18-year-old Baroness Ulrike von Levetzow. The pain caused by her rejection of his marriage proposal led him to write the famous Marienbad Elegy (updated in 1999 by the great W.G. Sebald).

…who dance, stroll up and down, and swim in the pool, as if this were a summer resort like Los Teques or Marienbad.

-Adolfo Bioy Casares, The Invention of Morel

In 1961, Last Year at Marienbad was released. Directed by Alain Resnais and written by Alain Robbe-Grillet, the film is as beautiful as it is inexplicable. On its face, the film is set at a resort hotel; an unnamed man (‘X’) becomes infatuated with an unnamed woman (‘A’) and attempts to convince her that they had an affair the previous year. The film unfolds in combinatorial play, with narration and scenes repeated in ever-evolving and bewildering variation.

A popular theory is that Last Year at Marienbad is actually an adaptation of Adolfo Bioy Casares’ The Invention of Morel, a novel of which our friend Jorge Luis Borges wrote, “To classify it as perfect is neither an imprecision nor a hyperbole.” I will not say much about this, so as not to spoil the book (you should go read it right now), but will only mention that Morel was, in a way, an homage to Louise Brooks, a Hollywood actress with whom Casares was somewhat obsessed and whose performance in Pandora’s Box provided a model for Delphine Seyrig’s performance as ‘A’ in Marienbad. The idea that there is a direct line from Casares and Brooks to the main characters in Morel to ‘X’ and ‘A’ in Marienbad, and that the obscurities of both novel and film are at heart simply odes to the power of cinema is an appealing one.

This theory about the connection between Marienbad and Morel was never acknowledged by the filmmakers (some say that the source text for the film is not Casares’ novel, but rather Wittgenstein’s Philosophical Investigations). Perhaps its fullest explication is given by this article in Senses of Cinema, in which the only sources given by the author are the dust jacket of a different Casares work and an Encyclopedia Britannica article which has since been removed from the online archives. Regardless of the theory’s truth, though, when one views the film through the lens of Morel, it comes tantalizingly close to making sense; the characters of the film lose their agency, consigned to repeating their roles ad infinitum.

At first sight, it seemed impossible to lose your way. At first sight…

The third main character in Marienbad is ‘M’, a man who may or may not be the husband of ‘A’. Throughout the film, we see ‘M’ playing a version of the mathematical game of Nim with ‘X’.

This version of Nim became known by the name “Marienbad” and was a brief craze in certain circles. It even got written about in Time:

Last week the Marienbad game was popping up at cocktail parties (with colored toothpicks), on commuter trains (with paper matches), in offices (paper clips) and in bars (with swizzle sticks). Only two can play, but any number can kibitz — and everyone, it seems, has a system for duplicating “X’s” talent for winning.

-“Games: Two on a Match,” Time, Mar. 23, 1962

The game is a theoretical win for the second player, although, as it is unlikely that a player will stumble upon the winning strategy by accident, ‘X’ is able to win even as the first player. We will return to general winning strategies for Nim and other games in later posts.

-The one who starts, wins.

-You must take an even number.

-You must take the smallest odd number.

-It’s a logarithmic series.

-You must switch rows as you go.

-And divide by three.

-Seven times seven is forty-nine.

-kibitzers in Last Year at Marienbad

I leave you now with Nick Cave’s exquisite “Girl in Amber.” Another secret adaptation of The Invention of Morel? Possible…

# The Simurgh (Universal Structures I)

To see a World in a Grain of Sand
And a Heaven in a Wild Flower
Hold Infinity in the palm of your hand
And Eternity in an hour

-William Blake, “Auguries of Innocence”

In Persian mythology, the Simurgh is a bird that lives in the mountains of Alborz. Sometimes she has the head or body of a dog, sometimes of a human. She has witnessed the destruction of the world three times. The wind of her beating wings is responsible for scattering seeds from the Tree of Life, creating all plants in the world.

The Simurgh is, in some tellings, the archetype of all birds. Her name resembles the Persian phrase si murg, meaning “thirty birds.”

In The Conference of the Birds, Farid ud-Din Attar’s 12th-century masterpiece, the birds of the world undertake a journey to find the Simurgh. And they succeed.

Their life came from that close, insistent sun
And in its vivid rays they shone as one.
There in the Simorgh’s radiant face they saw
Themselves, the Simorgh of the world – with awe
They gazed, and dared at last to comprehend
They were the Simorgh and the journey’s end.
They see the Simorgh – at themselves they stare,
And see a second Simorgh standing there;
They look at both and see the two are one,
That this is that, that this, the goal is won.

-Farid ud-Din Attar, The Conference of the Birds

The Simurgh is a bird that contains all birds. She is a universal bird.

Unsurprisingly, the Simurgh shows up a number of times in the works of Jorge Luis Borges, in both his short stories and his essays. One reference appears in the masterful story, “The Aleph,” a particularly rich and dense work which you should certainly read for yourself.

“The Aleph” is partly about how we create our own worlds, how we approximate the unknowable universe within our lives and our art. The narrator of the story, also named Borges, grieving the loss of his beloved Beatriz, pays repeated visits to the home of her father and her cousin, the poet Carlos Argentino Daneri. On one of these visits, Carlos Argentino takes Borges to his basement to show him the source of his poetry, the titular Aleph, a single point that contains the universe.

On the back part of the step, toward the right, I saw a small iridescent sphere of almost unbearable brilliance. At first I thought it was revolving; then I realised that this movement was an illusion created by the dizzying world it bounded. The Aleph’s diameter was probably little more than an inch, but all space was there, actual and undiminished. Each thing (a mirror’s face, let us say) was infinite things, since I distinctly saw it from every angle of the universe. I saw the teeming sea; I saw daybreak and nightfall; I saw the multitudes of America; I saw a silvery cobweb in the center of a black pyramid; I saw a splintered labyrinth (it was London); I saw, close up, unending eyes watching themselves in me as in a mirror; I saw all the mirrors on earth and none of them reflected me; I saw in a backyard of Soler Street the same tiles that thirty years before I’d seen in the entrance of a house in Fray Bentos; I saw bunches of grapes, snow, tobacco, lodes of metal, steam; I saw convex equatorial deserts and each one of their grains of sand; I saw a woman in Inverness whom I shall never forget; I saw her tangled hair, her tall figure, I saw the cancer in her breast; I saw a ring of baked mud in a sidewalk, where before there had been a tree; I saw a summer house in Adrogué and a copy of the first English translation of Pliny — Philemon Holland’s — and all at the same time saw each letter on each page (as a boy, I used to marvel that the letters in a closed book did not get scrambled and lost overnight); I saw a sunset in Querétaro that seemed to reflect the colour of a rose in Bengal; I saw my empty bedroom; I saw in a closet in Alkmaar a terrestrial globe between two mirrors that multiplied it endlessly; I saw horses with flowing manes on a shore of the Caspian Sea at dawn; I saw the delicate bone structure of a hand; I saw the survivors of a battle sending out picture postcards; I saw in a showcase in Mirzapur a pack of Spanish playing cards; I saw the slanting shadows of ferns on a greenhouse floor; I saw tigers, pistons, bison, tides, and armies; I saw all the ants on the planet; I saw a Persian astrolabe; I saw in the drawer of a writing table (and the handwriting made me tremble) unbelievable, obscene, detailed letters, which Beatriz had written to Carlos Argentino; I saw a monument I worshipped in the Chacarita cemetery; I saw the rotted dust and bones that had once deliciously been Beatriz Viterbo; I saw the circulation of my own dark blood; I saw the coupling of love and the modification of death; I saw the Aleph from every point and angle, and in the Aleph I saw the earth and in the earth the Aleph and in the Aleph the earth; I saw my own face and my own bowels; I saw your face; and I felt dizzy and wept, for my eyes had seen that secret and conjectured object whose name is common to all men but which no man has looked upon — the unimaginable universe.

-Jorge Luis Borges, “The Aleph”

Aleph ($\aleph$) is of course the letter chosen by Georg Cantor to represent transfinite cardinals and the first letter of the Hebrew alphabet. It plays a special role in Kabbalah as the first letter in “Ein Sof,” roughly translated as “infinity,” and in “Elohim,” one of the names of the Hebrew god. We will surely return to these matters.

This is the first installment in a mini-series on what we will call “universal structures,” objects that contain all other objects of their type. We will continue to look at examples from literature and religion, and will delve into the existence of universal structures in mathematics, a topic which continues to drive cutting-edge research to this day. Next week, we will look at a particular universal structure in mathematics, the wonderfully named “random graph.” I hope you will join us.

# An Infinitude of Proofs, Part 1

In our previous post, we gave three elementary number-theoretic proofs of the infinitude of the prime numbers. Today, in an unforgivably delayed second installment, we provide two proofs using machinery from more distant fields of mathematics: analysis and topology.

A small word of warning: today’s proofs, though not difficult, require a bit more mathematical sophistication than those of the previous post. The first proof will involve some manipulation of infinite sums, and the second proof uses rudiments of topology, which we introduced here.

Without further ado, let us begin. Our first proof today dates to the 18th century and is due to the prolific Leonhard Euler, of whom Pierre-Simon Laplace, an exceptional mathematician in his own right, once said, “Read Euler, read Euler, he is the master of us all.”

Proof Four (Euler): Suppose there are only finitely many prime numbers, $\{p_1, p_2, \ldots, p_n\}$. For each prime number $p$, consider the infinite series $\sum_{i = 0}^\infty \frac{1}{p^i} = 1 + \frac{1}{p} + \frac{1}{p^2} + \ldots$. As you probably learned in a precalculus class, the value of this infinite sum is precisely $\frac{1}{1-\frac{1}{p}}$.

Now recall that every natural number greater than 1 can be written in a unique way as a product of prime numbers. Since $\{p_1, \ldots, p_n\}$ are all of the primes, this means that, for each natural number $m \geq 1$, we can express $\frac{1}{m}$ as $\frac{1}{p_1^{s_1}} \cdot \frac{1}{p_2^{s_2}} \cdot \ldots \cdot \frac{1}{p_n^{s_n}}$ for some natural numbers $s_1, s_2, \ldots, s_n$. Moreover, it is clear that this gives a one-to-one correspondence between natural numbers $m \geq 1$ and the corresponding $n$-tuples of natural numbers, $\langle s_1, s_2, \ldots, s_n \rangle$. Putting this all together, we obtain the following remarkable formula:

$\sum_{m=1}^\infty \frac{1}{m} = \prod_{k=1}^n \frac{1}{1-\frac{1}{p_k}}$.

The sum on the left hand of this equation is the famous harmonic series, and it is well-known and easily verified that this sum diverges to infinity. On the other hand, the product on the right hand is a finite product of finite numbers and is therefore finite! This gives a contradiction and concludes the proof.

Our next proof was published in 1955 by a young Hillel Furstenburg, who is still active at the Einstein Institute of Mathematics here in Jerusalem.

Proof Five (Furstenberg): For all integers $a$ and $b$, let $U_{a,b}$ be the set $\{a + bk \mid k \in \mathbb{Z} \}$, i.e., $U_{a,b}$ contains $a$ and all integers that differ from $a$ by a multiple of $b$.

Claim: For all pairs of integers $(a_0, b_0)$ and $(a_1, b_1)$, either $U_{a_0,b_0} \cap U_{a_1, b_1} = \emptyset$ or there are $a_2, b_2$ such that $U_{a_0,b_0} \cap U_{a_1, b_1} = U_{a_2, b_2}$.

Proof of Claim: If $U_{a_0, b_0} \cap U_{a_1, b_1} \neq \emptyset$, then let $a_2$ be any element of the intersection, and let $b_2$ be the least common multiple of $b_0$ and $b_1$. It is easily verified that $U_{a_0,b_0} \cap U_{a_1, b_1} = U_{a_2, b_2}$, thus finishing the proof of the claim.

It now follows that we can define a topology on $\mathbb{Z}$ by declaring that a set $U \subseteq \mathbb{Z}$ is open if and only if $U = \emptyset$ or $U$ is a union of sets of the form $U_{a,b}$. In particular, for each prime number $p$, the set $U_{0,p}$, which is the set of all multiples of $p$, is open. However, $U_{0,p}$ is also closed, since it is the complement of the set $\bigcup_{0 < a < p} U_{a,p}$, which is an open set.

Now suppose that there are only finitely many prime numbers, $\{p_1, \ldots, p_n\}$. Since each set $U_{0,p_k}$ is closed and a finite union of closed sets is closed, we have that $\bigcup_{k = 1}^n U_{0,p_k}$ is a closed set. Notice that every integer that is not $1$ or $-1$ is a multiple of some prime number, so $\bigcup_{k = 1}^n U_{0,p_k}$ is precisely the set of all integers except $1$ and $-1$. Since it is closed, its complement, which is $\{-1,1\}$, is open. But every non-empty open set is a union of sets of the form $U_{a,b}$, each of which is clearly infinite, so there can be no finite non-empty open sets. This is a contradiction and concludes the proof.

Cover Image: Passio Musicae by Eila Hiltunen, a monument to Jean Sibelius in Helsinki, Finland. Photograph by the author.

# An Infinitude of Proofs, Part 0

Today, we take a break from our recent philosophical musings to return to some good old-fashioned mathematics (indeed, the mathematics today could be seen as all being “old-fashioned,” as the theorem we will be considering dates back to the ancient Greeks).

I’m sure my readers have all been introduced to the prime numbers, but, to refresh any memories, let me remind you that a prime number is a natural number, at least 2, that has no divisors other than 1 and itself. The first few prime numbers are, therefore: 2, 3, 5, 7, 11, 13…

The prime numbers can be thought of as the building blocks of number theory, as the backbone of the natural numbers. They have occupied a central place in mathematics and offered endless fascination for millennia. They are a source of great mystery even today.

In this post, we look at a classic theorem, commonly attributed to Euclid. Euclid’s proof is one of the gems of mathematics, a proof that is taught to every mathematician at the beginning of their true mathematical career. The theorem, as we will state it, is simply this:

Euclid’s Theorem: There are infinitely many prime numbers.

Euclid himself did not state the theorem in exactly this form, perhaps because of the ancient Greeks’ general antipathy towards the existence of infinite sets. He instead put forward the equivalent statement, “For every finite set of prime numbers, there is a prime number not in that set.”

Euclid’s Theorem has collected a vast and varied array of delightful proofs throughout the years, and, in a proposed infinite series of blog posts, I plan to cover all of them. Today, we will look at three proofs, from three very different centuries, all using only elementary number-theoretic techniques. First, of course, is Euclid’s proof itself.

Proof One (Euclid): Suppose that $P = \{p_0, p_1, \ldots, p_n\}$ is a finite set of prime numbers. We will show that there is a prime number that is not in $P$. To do this, let $q = p_0p_2\ldots p_n$, and let $r = q+1$. For all $i \leq n$, $p_i$ divides $q$ with no remainder (as $q = p_i(p_0\ldots p_{i-1}p_{i+1}\ldots p_n)$), so, as $r = q+1$ and $p_i \geq 2$, $p_i$ does not divide $r$. Since $r > 1$ and every integer greater than 1 has prime divisors, there is at least one prime, $p^*$, that divides $r$. But we just saw that no element of $P$ divides $r$, so $p^*$ is a prime that is not in $P$.

The next proof we will consider is due to the eighteenth-century German mathematician Christian Goldbach, largely known today for the statement of the still unproven Goldbach’s Conjecture. This proof (like Goldbach’s Conjecture itself) appears in a letter from Goldbach to Leonhard Euler (whose analytic proof of Euclid’s Theorem we will visit in a future post).

Proof Two (Goldbach): For each natural number $n$, let $F_n = 2^{2^n} + 1$, so $F_0 = 3, F_1 = 5, F_2 = 17$, etc. ($F_n$ is known as the $n^{\mathrm{th}}$ Fermat number.)

Claim 1: For every natural number $n$, $F_{n+1} = F_0F_1\ldots F_n + 2$.

Proof of Claim 1: Suppose that the Claim is false, and let $n$ be the smallest natural number such that $F_{n+1} \neq F_0F_1 \ldots F_n + 2$. Since the Claim can easily be verified by inspection for $n=0$, we may assume $n > 0$. But now we have the following sequence of calculations where, because we are assuming that $n$ is the smallest counterexample to the Claim, we can use the fact that $F_n = F_0F_1\ldots F_{n-1} + 2$.

$\begin{array}{rcl}F_{n+1} & = & 2^{2^{n+1}}+1 \\ & = & 2^{2^n}\cdot 2^{2^n} + 1 \\ & = & (F_n-1)(F_n-1)+1 \\ & = & (F_n)(F_n) - 2F_n + 2 \\ & = & (F_n)(F_0F_1\ldots F_{n-1} + 2) -2F_n + 2 \\ & = & F_0F_1\ldots F_n + 2F_n - 2F_n + 2 \\ & = & F_0F_1\ldots F_n + 2 \end{array}$

But this calculation shows that $n$ is not a counterexample to our Claim, contradicting our assumption and finishing the proof of the Claim.

We now need a very simple number-theoretic Claim.

Claim 2: If $a$ and $b$ are natural numbers, $p$ is a prime, and $p$ divides both $a$ and $a+b$, then $p$ divides $b$.

Proof of Claim 2: Suppose $a = mp$ and  $a+b = np$, where $m$ and $n$ are natural numbers. Then $b = a+b-a = np - mp = (n-m)p$, so $p$ divides $b$.

Claim 3: If $m < n$ are natural numbers, then there is no prime number $p$ such that $p$ divides both $F_m$ and $F_n$.

Proof of Claim 3: Suppose that the Claim is false and that there are natural numbers $m < n$ and a prime number $p$ such that $p$ divides both $F_m$ and $F_n$. Note that $F_m$ is one of the factors in the product $F_0F_1\ldots F_{n-1}$, so $p$ divides $F_0F_1\ldots F_{n-1}$. Since $F_n = F_0F_1\ldots F_{n-1} + 2$, we also conclude that $p$ divides $F_0F_1\ldots F_{n+1} + 2$, so, by Claim 2, we know that $p$ divides $2$. As $2$ is prime, this means that $p = 2$. But $F_m$ and $F_n$ are both odd, so this is impossible.

We are now ready to finish the proof. For each natural number $n$, choose a prime number $p_n$ that divides $F_n$. By Claim 3, for all natural numbers $m < n$, we have $p_m \neq p_n$, so $\{p_n \mid n \in \mathbb{N}\}$ is an infinite set of prime numbers.

Remark: The Fermat numbers were introduced, unsurprisingly, by the seventeenth-century French mathematician Pierre de Fermat (of Fermat’s Last Theorem fame). Fermat conjectured that every Fermat number is in fact prime (this would obviously imply Claim 3 from the previous proof). The first four Fermat numbers (3, 5, 17, 257) are easily verified to be prime, and the next Fermat number, 65537, can be seen to be prime with a bit more work. However, Euler proved in 1732 that $F_5$ is not prime. Indeed, $F_5 = 2^{32}+1 = 4294967297 = 641 \times 6700417$. Many mysteries remain regarding the Fermat numbers. For example, even the following two very basic questions remain unsolved to this day:

• Are there infinitely many prime Fermat numbers?
• Are there infinitely many non-prime Fermat numbers?

The Fermat numbers grow so quickly that, even with computers, it can be hard to analyze even “relatively small” Fermat numbers. For example, it is unknown whether $F_{20}$ or $F_{24}$ are prime. On the other hand, the truly gigantic number $F_{3329780}$ is known to be non-prime: one of its prime factors is $193 \times 2^{3329780} + 1$.

Finally, a proof that combines ideas from Euclid’s and Goldbach’s proofs was given recently by Filip Saidak.

Proof Three: (Saidak) Note first that, for every natural number $n$, we have that $n$ and $n+1$ do not have any shared prime divisors. Now define an infinite sequence of natural numbers, $\langle n_0, n_1, \ldots \rangle$ as follows. Let $n_0$ be any natural number that is at least 2. Let $n_1 = n_0(n_0+1)$. Since $n_0$ and $n_0 + 1$ do not share any prime divisors, and since both $n_0$ and $n_0+1$ have at least one prime divisor, it follows that $n_1$ must have at least 2 distinct prime divisors.

Now let $n_2 = n_1(n_1+1)$. Again, $n_1$ and $(n_1 + 1)$ do not have any shared prime divisors. We have shown that $n_1$ has at least 2 distinct prime divisors, and we know that $n_1 + 1$ has at least one prime divisor, so $n_2$ must have at least 3 distinct prime divisors. Continuing in this way, defining $n_{k+1} = n_k(n_k+1)$ for every natural number $k$, one proves that, for each natural number $k$, the number $n_k$ has at least $k+1$ distinct prime divisors. In particular, there are infinitely many prime numbers.

Stay tuned for a future post, in which we will provide proofs of Euclid’s Theorem from further flung areas of mathematics, including real analysis and topology.

# Dante, Einstein, and the Shape of the World

Last week, we began a series of posts dedicated to thinking about immortality. If we want to even pretend to think precisely about immortality, we will have to consider some fundamental questions. What does it mean to be immortal? What does it mean to live forever? Are these the same thing? And since immortality is inextricably tied up in one’s relationship with time, we must think about the nature of time itself. Is there a difference between external time and personal time? What is the shape of time? Is time linear? Circular? Finite? Infinite?

Of course, we exist not just across time but across space as well, so the same questions become relevant when asked about space. What is the shape of space? Is it finite? Infinite? It is not hard to see how this question would have a significant bearing on our thinking about immortality. In a finite universe (or, more precisely, a universe in which only finitely many different configurations of matter are possible), an immortal being would encounter the same situations over and over again, would think the same thoughts over and over again, would have the same conversations over and over again. Would such a life be desirable? (It is not clear that this repetition would be avoidable even in an infinite universe, but more on that later.)

Today, we are going to take a little historical detour to look at the shape of the universe, a trip that will take us from Ptolemy to Dante to Einstein, a trip that will uncover a remarkable confluence of poetry and physics.

One of the dominant cosmological views from ancient Greece and the Middle Ages was that of the Ptolemaic, or Aristotelian, universe. In this image of the world, Earth is the fixed, immobile center of the universe, surrounded by concentric, rotating spheres. The first seven of these spheres contain the seven “planets”: the Moon, Mercury, Venus, the Sun, Mars, Jupiter, and Saturn. Surrounding these spheres is a sphere containing the fixed stars. This is the outermost sphere visible from Earth, but there is still another sphere outside it: the Primum Mobile, or “Prime Mover,” which gives motion to all of the spheres inside it. (In some accounts the Primum Mobile is itself divided into three concentric spheres: the Crystalline Heaven, the First Moveable, and the Empyrean. In some other accounts, the Empyrean (higher heaven, which, in the Christianity of the Middle Ages, became the realm of God and the angels) exists outside of the Primum Mobile.)

This account is naturally vulnerable to an obvious question, a question which, though not exactly in the context of Ptolemaic cosmology, occupied me as a child lying awake at night and was famously asked by Archytas of Tarentum, a Greek philosopher from the fifth century BC: If the universe has an edge (the edge of the outermost sphere, in the Ptolemaic account), then what lies beyond that edge? One could of course assert that the Empyrean exists as an infinite space outside of the Primum Mobile, but this would run into two objections in the intellectual climate of both ancient Greece and Europe of the Middle Ages: it would compromise the aesthetically pleasing geometric image of the universe as a finite sequence of nested spheres, and it would go against a strong antipathy towards the infinite. Archytas’ question went largely unaddressed for almost two millennia, until Dante Alighieri, in the Divine Comedy, proposed a novel and prescient solution.

Before we dig into Dante, a quick mathematical lesson on generalized spheres. For a natural number $n$, an $n$-sphere is an $n$-dimensional manifold (i.e. a space which, at every point, locally looks like $n$-dimensional real Euclidean space) that is most easily represented, embedded in $n+1$-dimensional space, as the set of all points at some fixed positive distance (the “radius” of the sphere) from a given “center point.”

Perhaps some examples will clarify this definition. Let us consider, for various values of $n$, the $n$-sphere defined as the set of points in $(n+1)$-dimensional Euclidean space at distance 1 from the origin (i.e. the point (0,0,…,0)).

If $n=0$, this is the set of real numbers whose distance from 0 is equal to 1, which is simply two points: 1 and -1.

If $n=1$, this is just the set of points $(x,y)$ in the plane at a distance of 1 from $(0,0)$. This is the circle, centered at the origin, with radius 1.

If $n=2$, this is the set of points $(x,y,z)$ in 3-dimensional space at a distance 1 from the point $(0,0,0)$. This is the surface of a ball of radius 1, and is precisely the space typically conjured by the word “sphere.”

0-, 1-, and 2-spheres are all familiar objects; beyond this, we lose some ability to visualize $n$-spheres due to the difficulty of considering more than three spatial dimensions, but there are useful ways to think about higher-dimensional spheres by analogy with the more tangible lower-dimensional ones. Let us try to use these ideas to get some understanding of the 3-sphere.

First, note that, for a natural number $n$, the non-trivial “cross-sections” of an $n+1$-sphere are themselves $n$-spheres! For example, if a 1-sphere (i.e. circle) is intersected with a 1-dimensional Euclidean space (a line) in a non-trivial way, the result is a $0$-sphere (i.e. a pair of points). If a 2-sphere is intersected with a 2-dimensional Euclidean space (a plane) in a non-trivial way, the result is a 1-sphere (this is illustrated above in our picture of a 2-sphere). The same relationship holds for higher dimensional spheres: if a 3-sphere is intersected with a 3-dimensional Euclidean space in a non-trivial way, the result is a 2-sphere.

Suppose that you are a 2-dimensional person living in a 2-sphere universe. Let’s suppose, in fact, that you are living in the 2-sphere pictured above, with the 1-sphere “latitude lines” helpfully marked out for you. Let’s suppose that you begin at the “north pole” (i.e. the point at the top, in the center of the highest circle) and start moving in a fixed direction. At fixed intervals, you will encounter the 1-sphere latitude lines. For a while, these 1-spheres will be increasing in radius. This will make intuitive sense to you. You are moving “further out” in space; each successive circle “contains” the last and thus should be larger in radius. After you pass the “equator,” though, something curious starts happening. Even though you haven’t changed direction and still seem to be moving “further out,” the radii of the circles you encounter start shrinking. Eventually, you reach the “south pole.” You continue on your trip. The circles wax and wane in a now familiar way, and, finally, you return to where you started.

A similar story could be told about a 3-dimensional being exploring a 3-sphere. In fact, I think we could imagine this somewhat easily. Suppose that we in fact live in a 3-sphere. For illustration, let us place a “pole” of this 3-sphere at the center of the Earth. Now suppose that we, in some sort of tunnel-boring spaceship, begin at the center of the Earth and start moving in a fixed direction. For a while, we will encounter 2-sphere cross-sections of increasing radius. Of course, in the real world these are not explicitly marked (although, for a while, they can be nicely represented by the spherical layers of the Earth’s core and mantle, then the Earth’s surface, then the sphere marking the edge of the Earth’s atmosphere) but suppose that, in our imaginary world, someone has helpfully marked them. For a while, these successive 2-spheres have larger and larger radii, as is natural. Eventually, of course, they will start to shrink, contracting to a point before expanding and contracting as we return to our starting point at the Earth’s core.

Dante’s Divine Comedy, completed in 1320, is one of the great works of literature. In the first volume, Inferno, Dante is guided by Virgil through Hell, which exists inside the Earth, directly below Jerusalem (from where I happen to be writing this post). In the second volume, Purgatorio, Virgil leads Dante up Mount Purgatory, which is situated antipodally to Jerusalem and formed of the earth displaced by the creation of Hell. In the third volume, Paradiso, Dante swaps out Virgil for Beatrice and ascends from the peak of Mount Purgatory towards the heavens.

Dante’s conception of the universe is largely Ptolemaic, and most of Paradiso is spent traveling outward through the larger and larger spheres encircling the Earth. In Canto 28, Dante reaches the Primum Mobile and turns his attention outward to what lies beyond it. We are finally in a position to receive an answer to Archytas’ question, and the answer that Dante comes up with is surprising and elegant.

The structure of the Empyrean, which lies outside the Primum Mobile, is in large part a mirror image of the structure of the Ptolemaic universe, a revelation that is foreshadowed in the opening stanzas of the canto:

When she who makes my mind imparadised
Had told me of the truth that goes against
The present life of miserable mortals —

As someone who can notice in a mirror
A candle’s flame when it is lit behind him
Before he has a sight or thought of it,

And turns around to see if what the mirror
Tells him is true, and sees that it agrees
With it as notes are sung to music’s measure —

Even so I acted, as I well remember,
While gazing into the bright eyes of beauty
With which Love wove the cord to capture me.

When Dante looks into the Empyrean, he sees a sequence of concentric spheres, centered around an impossibly bright and dense point of light, expanding to meet him at the edge of the Primum Mobile:

I saw a Point that radiated light
So sharply that the eyelids which it flares on
Must close because of its intensity.

Whatever star looks smallest from the earth
Would look more like a moon if placed beside it,
As star is set next to another star.

Perhaps as close a halo seems to circle
The starlight radiance that paints it there
Around the thickest mists surrounding it,

As close a ring of fire spun about
The Point so fast that it would have outstripped
The motion orbiting the world most swiftly.

And this sphere was encircled by another,
That by a third, and the third by a fourth,
The fourth by a fifth, the fifth then by a sixth.

The seventh followed, by now spread so wide
That the whole arc of Juno’s messenger
Would be too narrow to encompass it.

So too the eighth and ninth, and each of them
Revolved more slowly in proportion to
The number of turns distant from the center.

This seemingly obscure final detail, that the spheres of the Empyrean spin increasingly slowly as they increase in size, and in distance from the point of light, turns out to be important. Dante is initially confused because, in the part of the Ptolemaic universe from the Earth out to the Primum Mobile, the spheres spin faster the larger they are; the fact that this is different in the Empyrean seems to break the nice symmetry he observes. Beatrice has a ready explanation, though: the overarching rule governing the speed at which the heavenly spheres rotate is not based on their size, but rather on their distance from God.

This is a telling explanation and seems to confirm that the picture Dante is painting of the universe is precisely that of a 3-sphere, with Satan, at the center of the Earth, at one pole and God, in the point of light, at the other. If Dante continues his outward journey from the edge of the Primum Mobile, he will pass through the spheres of the Empyrean in order of decreasing size, arriving finally at God. Note that this matches precisely the description given above of what it would be like to travel in a 3-sphere. Dante even helpfully provides a fourth dimension into which his 3-sphere universe is embedded: not a spatial dimension, but a dimension corresponding to speed of rotation!

(For completeness, let me mention that the spheres of the Empyrean are, in order of decreasing size and hence increasing proximity to God: Angels, Archangels, Principalities, Powers, Virtues, Dominions, Thrones, Cherubim, and Seraphim.)

Dante’s ingenious description of a finite universe helped the Church to argue against the existence of the infinite in the physical world. Throughout the Renaissance, Scientific Revolution, and Enlightenment, this position was gradually eroded in favor an increasingly accepted picture of infinite, flat space. A new surprise awaited, though, in the twentieth century.

In 1917, Einstein revolutionized cosmology with the introduction of general relativity, which provided an explanation of gravity as arising from geometric properties of space and time. Central to the theory are what are now known as the Einstein Field Equations, a system of equations that describes how gravity interacts with the curvature of space and time caused by the presence of mass and energy. In the 1920s, an exact solution to the field equations, under the assumptions that the universe is homogeneous and isotropic (roughly, has laws that are independent of absolute position and orientation, respectively), was isolated. This solution is known as the Friedmann-Lemaître-Robertson-Walker metric, after the four scientists who (independently) derived and analyzed the solution, and is given by the equation,

$ds^2 = -dt^2 + R^2(t)\left(\frac{dr^2}{1-kr^2} + r^2(d\theta^2 + \sin^2\theta d\phi^2)\right)$,

where $k$ is a constant corresponding to the “curvature” of the universe. If $k = 0$, then the FLRW metric describes an infinite, “flat” Euclidean universe. If $k < 0$, then the metric describes an infinite, hyperbolic universe. If $k>0$, though, the metric describes a finite universe: a 3-sphere.

PS: Andrew Boorde, from whose book the above illustration of the Ptolemaic universe is taken, is a fascinating character. A young member of the Carthusian order, he was absolved from his vows in 1529, at the age of 39, as he was unable to adhere to the “rugorosite” of religion. He turned to medicine, and, in 1536, was sent by Thomas Cromwell on an expedition to determine foreign sentiment towards King Henry VIII. His travels took him throughout Europe and, eventually, to Jerusalem, and led to the writing of the Fyrst Boke of the Introduction of Knowledge, perhaps the earliest European guidebook. Also attributed to him (likely without merit) is Scoggin’s Jests, Full of Witty Mirth and Pleasant Shifts, Done by him in France and Other Places, Being a Preservative against Melancholy, a book which, along with Boord himself, plays a key role in Nicola Barker’s excellent novel, Darkmans.

Mark A. Peterson, “Dante and the 3-sphere,” American Journal of Physics, 1979.

Carlo Rovelli, “Some Considerations on Infinity in Physics,” and Anthony Aguirre, “Cosmological Intimations of Infinity,” both in Infinity: New Research Frontiers, edited by Michael Heller and W. Hugh Woodin.

Cover Image: Botticelli’s drawing of the Fixed Stars.

# Measuring V.2: Density and Arithmetic Progressions

In our last post, we introduced the notions of density, upper density, and lower density as means of measuring subsets of natural numbers. We ended with two exercises. We recall them now; solutions are at the end of this post.

Exercise 1: Find subsets $A,B \subseteq \mathbb{N}$ such that:

• $A \cap B = \emptyset$;
• $A \cup B = \mathbb{N}$;
• $\overline{d}(A) = \overline{d}(B) = 1$;
• $\underline{d}(A) = \underline{d}(B) = 0$.

Exercise 2: Show that, if $n \in \mathbb{N}$ and $A_0, \ldots, A_n$ are subsets of $\mathbb{N}$ such that $A_0 \cup A_1 \cup \ldots \cup A_n = \mathbb{N}$, then there is $k \leq n$ such that $\overline{d}(A_k) > 0$.

Before getting to the solutions, though, let’s take an interesting detour through a simple topic that has been the focus of a large amount of groundbreaking mathematics over the last century: arithmetic progressions in natural numbers. The journey will stop at three beautiful theorems and one beautiful conjecture and will involve some of the mathematical giants of the twentieth and twenty-first centuries.

Definition: An arithmetic progression of natural numbers is an increasing sequence of natural numbers such that the difference between successive terms of the sequence is constant. The length of an arithmetic progression is the number of terms in the sequence.

For example, the sequence $\langle 4,7,10,13 \rangle$ is an arithmetic progression of length 4, as the difference between each pair of successive terms is 3. The sequence of even numbers, $\langle 0,2,4,6,\ldots \rangle$, and the sequence of odd numbers, $\langle 1,3,5,7, \ldots \rangle$ are both arithmetic progressions of infinite length.

In an earlier post, we introduced the mathematical field of Ramsey Theory. Roughly speaking, Ramsey Theory studies the phenomenon of order necessarily arising in sufficiently large structures. Ramsey Theory takes its name from Frank Ramsey, who published a seminal paper in 1930. Arguably the first important theorem in Ramsey Theory, though, came three years earlier and is due to the Dutch mathematician Bartel Leendert van der Waerden.

Theorem (van der Waerden, 1927): Suppose that the natural numbers are partitioned into finitely many sets, $A_0, A_1, \ldots, A_n$ (so we have $\bigcup_{i \leq n} A_i = \mathbb{N}$). Then there is an $i \leq n$ such that $A_i$ contains arithmetic progressions of every finite length.

This is naturally seen as a statement in Ramsey Theory: Arithmetic progressions are very orderly things, and Van der Waerden’s Theorem states that, no matter how deviously you divide the natural numbers into finitely many pieces, you cannot avoid the appearance of arbitrarily long arithmetic progressions in one of the pieces. It is also worth noting that Van der Waerden’s Theorem cannot be strengthened to ensure the existence of infinite arithmetic progressions: it is relatively easy to partition the natural numbers into even just two sets such that neither set contains an arithmetic progression of infinite length (try it!).

You might notice a similarity between the statement of Van der Waerden’s Theorem and our Exercise 2: both say that, if the natural numbers are divided into finitely many pieces, at least one of the pieces must be “large” in a certain sense. In Van der Waerden’s Theorem, “large” means containing arbitrarily long arithmetic progressions, while in Exercise 2, it means having positive upper density.

Is there a connection between these two notions of largeness? It turns out that there is! In 1936, Erdős and Turán conjectured that, if $A \subseteq \mathbb{N}$ and $A$ has positive density, then $A$ contains arbitrarily long arithmetic progressions. Almost forty years later, the conjecture was confirmed (and, in fact, strengthened, as it was proven for upper density rather than density) in a celebrated proof by Hungarian mathematician Endre Szemerédi.

Theorem (Szemerédi, 1975): Suppose that $A \subseteq \mathbb{N}$ and $\overline{d}(A) > 0$. Then $A$ contains arithmetic progressions of every finite length.

Note that Szemerédi’s Theorem is a true generalization and strengthening of Van der Waerden’s theorem: when combined with Exercise 2, Szemerédi’s Theorem directly implies Van der Waerden’s Theorem. However, Szemerédi’s Theorem does not give any information about sets of natural numbers with zero upper density. There is one particularly interesting such set, which we encountered in our last post: the set of prime numbers, $P = \{2,3,5,7,11, \ldots \}$.

According to experts, it is likely that it was conjectured as early as 1770, by Lagrange and Waring, that the set of primes contains arbitrarily long arithmetic progressions, and the question experienced renewed interest in the wake of the proof of Szemerédi’s Theorem. An answer finally came in 2004, in a paper by Ben Green and Terence Tao.

Theorem (Green-Tao, 2004): The set of prime numbers contains arithmetic progressions of every finite length.

The story has not ended yet, as many very natural questions about arithmetic progressions remain unsolved. Perhaps the most famous is the following conjecture of Erdős, strengthening his conjecture with Turán that was eventually confirmed by Szemerédi.

Conjecture (Erdős): Suppose $A \subseteq \mathbb{N}$ (with $0 \not\in A$) and $\sum_{n \in A} \frac{1}{n} = \infty$. Then $A$ arithmetic progressions of every finite length.

This conjecture, unlike Szemerédi’s Theorem, would cover the case in which $A$ is the set of all primes, so this conjecture would generalize both Szemerédi’s Theorem and the Green-Tao Theorem. The problem currently carries a cash prize of \$5000 (and, of course, the promise of mathematical fame).

Solution to Exercise 1: Recursively define a sequence $\langle a_n \mid n \in \mathbb{N} \rangle$ by letting $a_0 = 1$, and, given $a_0, \ldots, a_n$, letting $a_{n+1} = (n+1)(a_0 + a_1 + \ldots + a_n)$. The first few terms of the sequence are thus $1,1,4,18,96, \ldots$. Now divide $\mathbb{N}$ into pairwise disjoint blocks $\langle A_n \mid n \in \mathbb{N} \rangle$, arranged one after the other, in which, for all $n \in \mathbb{N}$, $|A_n| = a_n$. The first few blocks are thus as follows:

• $A_0 = \{0\}$;
• $A_1 = \{1\}$;
• $A_2 = \{2,3,4,5\}$;
• $A_3 = \{6,7,\ldots,23\}$;
• $A_4 = \{24,25,\ldots,119\}$.

Now let $A$ be the union of all of the even-numbered blocks, i.e. $A = \bigcup_{n \in \mathbb{N}}A_{2n}$, and let $B$ be the union of all of the odd-numbered blocks.

We clearly have $A \cap B = \emptyset$ and $A \cup B = \mathbb{N}$. We next show $\overline{d}(A) = 1$. Recall that $\overline{d}(A) = \limsup_{n \rightarrow \infty} \frac{|A \cap n|}{n}$. Given $n \in \mathbb{N}$, let $m_n$ be the largest element of $A_{2n}$. Think about the quantity $\frac{|A \cap (m_n+1)|}{m_n+1}$. Since $A_{2n} \subseteq A$, we clearly have $|A \cap (m_n+1)| \geq |A_{2n}| = a_{2n}$. We also have $m_n+1 = |A_0| + |A_1| + \ldots + |A_{2n}| = a_0 + a_1 + \ldots + a_{2n}$. But this yields:

$\frac{|A \cap (m_n+1)|}{m_n+1} \geq \frac{a_{2n}}{a_0 + \ldots + a_{2n}} = \frac{(2n)(a_0 + \ldots + a_{2n-1})}{a_0 + \ldots + a_{2n-1} + (2n)(a_0 + \ldots + a_{2n-1})} = \frac{2n}{2n+1}$.

As $n$ gets arbitrarily large, $\frac{2n}{2n+1}$ gets arbitrarily close to $1$, so we in fact get $\overline{d}(A) = 1$. The proofs of $\overline{d}(B) = 1$ and $\underline{d}(A) = \underline{d}(B) = 0$ are essentially the same and are thus left to the reader.

Solution to Exercise 2: We will in fact show something stronger: there is $k \leq n$ such that $\overline{d}(A_k) \geq \frac{1}{n+1}$. Suppose for sake of a contradiction that this is not the case. Then, by the definition of upper density, for each $k \leq n$ we can find $m_k \in \mathbb{N}$ such that, for all natural numbers $m \geq m_k$, $\frac{|A_k \cap m|}{m} < \frac{1}{n+1}$. Now we can choose a natural number $m^*$ large enough so that, for all $k \leq n$, $m_k \leq m^*$.

For each $k \leq n$, by our choice of $m_k$, we know that $\frac{|A_k \cap m^*|}{m^*} < \frac{1}{n+1}$. Also, by the fact that $A_0 \cup \ldots \cup A_n = \mathbb{N}$, we have that $|A_0 \cap m^*| + \ldots + |A_n \cap m^*| \geq m^*$. But this yields:

$1 = \frac{m^*}{m^*} \leq \frac{|A_0 \cap m^*| + \ldots + |A_n \cap m^*|}{m^*} = \frac{|A_0 \cap m^*|}{m^*} + \ldots + \frac{|A_n \cap m^*|}{m^*} <$

$<\frac{1}{n+1} + \ldots + \frac{1}{n+1} = (n+1)\frac{1}{n+1} = 1$.

We have thus shown $1 < 1$. This is, of course, a contradiction, which finishes the exercise.

Cover Image: Vir Heroicus Sublimis by Barnett Newman