# The Geometric Viewpoint

geometric and topological excursions by and for undergraduates

• ## Tessellations of the Hyperbolic Plane and M.C. Escher

(this post is by Allyson Redhunt)

“For me it remains an open question whether [this work] pertains to the realm of mathematics or to that of art.” -M. C. Escher

Figure 1. M.C. Escher [7].

Escher’s beginnings
M. C. Escher (1898-1972) (Figure 1) is known for his mind-boggling artwork that challenges our sense of space. Although many of his works are artistic renditions of deep mathematical ideas, he had no formal training in mathematics. In fact, he was a poor student in high school–struggling to earn a diploma. In his post-secondary education, he was trained at the School of Architecture and Decorative Arts in Haarlem. This is where he developed his fascination with structure.
Although he began as an architecture student, he was soon switched to a decorative arts path. During his schooling, he did some traveling and was exposed to Moorish motifs. These works of design are created from mathematically careful patterns. From their influence, Escher’s art branched into tessellations of the plane. He was inspired by the idea of “approaches to infinity” and began by playing with flat surfaces and spheres.

Figure 3. Coxeter’s tessellation [2].

Escher’s ideas about structure, pattern, and infinity were suddenly enhanced when he came across the work of geometer H. S. M. Coxeter (1907-2003). Coxeter and Escher struck up a correspondence when Coxeter hoped to use Escher’s unique depictions of symmetry in a presentation for the Royal Society of Canada. Coxeter sent Escher a copy of the talk, which included an illustration depicting a tessellation of the hyperbolic plane (Figure 3) [2]. This image sparked a new area of Escher’s exploration of infinity [6]. To fully understand the beauty of his works, it is helpful to have a basic understanding of hyperbolic geometry.

A crash course in hyperbolic geometry
So what is hyperbolic space? Grade school mathematics is taught using Euclidean geometry. This assumes Euclid’s axioms, which he intended to be the basis of all geometry. However, one of them was a great source of debate between mathematicians. The “Parallel Postulate,” which states that if one straight line crosses two other straight lines to make both angles on one side less than 90˚, then the two lines meet. Proving that triangles have 180˚ angle sums is an application of this postulate [4].
However, the Parallel Postulate need not hold true in all cases, such as on the surface of a sphere. Proving that the postulate need not hold led to the discovery of an important “non-Euclidean” geometry called hyperbolic geometry. Although it at first seems unnatural to think about parallel lines performing in “new” ways, hyperbolic surfaces can be found in nature. Two common examples are sea slugs (Figure 4) and lettuce (Figure 5). The wavy structure is the tip-off that their surfaces exhibit hyperbolic geometry. This is because, while a Euclidean surface has curvature equal to zero everywhere, a hyperbolic surface has constant negative curvature (for comparison, a sphere has constant positive curvature).

Figure 4. Close up of a colorful nudibranch [8]. Figure 5. Leafy lettuce [9].

Hyperbolic geometry has many interesting properties that counter our ingrained Euclidean intuition. To understand them, we will explore an important model of hyperbolic space: the Poincaré disc model.
The Poincaré disc model
We can imagine hyperbolic space as an open disk in the complex plane $\C$. We think of the space in the disk getting infinitely more “dense” as we approach the boundary of the disc, so the distance of a straight line between two points get longer as we approach the boundary. Thus, the shortest path between two points may be curved to take advantage of the “less dense” area towards the center of the disc. It turns out that the shortest distance between two points lies along the arc of a circle that is perpendicular to the boundary. In Figure 6, the shortest distance, called a geodesic, between A and B is the arc length of the given circle. Thus, the idea of “lines” in Euclidean space is generalized when in hyperbolic space to include circles.
This disc model is precisely what Escher saw in Coxeter’s book, and is what he used to create his art.

Figure 6. A geodesic between points A and B (created with GeoGebra).

Polygons in hyperbolic space
Since lines in hyperbolic space differ from our intuition about lines in Euclidean space, we must adjust our understanding of polygons as well. A hyperbolic polygon is a region of the hyperbolic plane whose boundary is decomposed into finitely many generalized line segments (recall that this includes circle segments), called edges, meeting only at their endpoints, called vertices. At most two edges can meet at any one point [1].
Earlier we mentioned that Euclid’s axiom that fails in hyperbolic space is used to prove that triangles have an interior angle sum of 180˚. Since this axiom does not hold, we need a new framework for thinking about polygons in hyperbolic space. In particular, Euclidean rectangles–quadrilaterals having four 90˚ angles–do not exist in hyperbolic space.
The basis for the polygon framework in hyperbolic space is the Gauss-Bonnet formula, which tells us that the area of a convex geodesic n-gon is $(n-2)\pi$ minus the sum of the interior angles [10]. Let’s take a moment for this to sink in–the area of polygons in hyperbolic space is dependent completely on angles! This goes against our Euclidean intuition, which tells us that a triangle with longer side lengths has a larger area than a triangle with shorter side lengths, despite the fact that both have angle sums of 180˚.
Armed with this knowledge that hyperbolic space gets more “dense” along with these new ideas about polygons, we are ready to dig in to the math of Escher’s works: hyperbolic tessellations.

Tessellations of hyperbolic space
Anyone who has looked at a tiled bathroom floor is familiar with the idea of tessellations: If we repeat a pattern of polygons, we can create a pattern over a large space. Someone who has attempted to tile their own bathroom floor may have noticed that not all tile shapes fit together nicely in a pattern. Note that a bathroom floor is an example of a Euclidean space, a geometry in which it turns out to be relatively difficult to happen upon a true tessellation. In contrast, hyperbolic space is relatively easy to tessellate.
Formally, a tessellation is a polygonal tiling of a plane that covers the entire plane. The Tessellation Theorem states that any polygon tiling in a complete space with the angles around any vertex adding to $\frac{2\pi}{n}$ for some integer n > 0 will be a tessellation of the plane. This holds true for Euclidean, spherical, and hyperbolic geometries.

When thinking about the increased “density” as we approach the edge, it should not be surprising that polygons appear smaller as we approach the boundary. Despite this, the areas stay constant (recall that it depends only on the angles!).

Escher’s tessellations
Escher created five works inspired by hyperbolic plane tessellations: Circle Limits I-IV and Snakes. While Circle Limit II and Snakes are beautiful (I highly recommend looking them up), in them Escher took more artistic license in tessellating the hyperbolic plane than the others. Thus, we will investigate Circle Limits I, III, and IV, all of which are wood cuts. His goal with creating these was to depict infinity in a finite space.

Figure 7. Polygons on Circle Limit I [5].

Circle Limit I
This is Escher’s first attempt at his exploration of hyperbolic tessellations, and my least favorite. I find it so be harsh and too sharp to be aesthetically pleasing.

As you can see from Figure 7, we can find both hexagonal and quadrilateral tessellations [5].

Notice that the Euclidean side lengths and areas of the polygons diminish as we approach the edge. Just how much do they scale? The answer comes from the distance formula for hyperbolic geometry–analogous to $d=\sqrt{x^2+y^2}$ in Euclidean geometry. It turns out that lengths are inversely proportional to the distance to the boundary. That is to say, a segment half way between the center and the boundary has twice the Euclidean length of one that is one quarter of the way from the boundary to the center. Since Euclidean area is related to edge lengths, the areas share this same relationship.

Escher was displeased with the result of this piece because the fish aren’t all facing the same direction, the coloring doesn’t alternate well, and the fish do not look realistic [3]. His Circle Limit III will resolve these self-criticisms.

Figure 8. Circle Limit III with the central tile of the octagonal tessellation [7], (polygon made using GeoGebra).

Circle Limit III
Circle Limit III is my favorite of the tessellations. In this work, the fish are nicely organized, their coloring properly alternates, and the images look more like real animals. This is achieved by alternating between triangles and quadrilaterals (as you can see from the defined white spines).

Although this image is more aesthetically pleasing, it did not pass the mathematical scrutiny of our very own Coxeter. As we discussed earlier, geodesic polygons must be made of perpendicular circle segments, but the arcs in Circle Limit III meet the boundary at about 80˚. An alternative view on the polygons, though, gives a true tessellation with octagons [5]. The center polygon is indicated in Figure 8, and the rest of the tiles can be found in the same way, by connecting the nose vertices and the fin vertices. Notice that the edges of the polygon are not straight lines, and are instead segments of circles perpendicular to the boundary of the disc.

Figure 9. Circle Limit IV [7].

Circle Limit IV
Circle Limit IV (Figure 9) is the last piece in the series, and plays with negative space to alternate angels and devils. It is commonly referred to as “Heaven and Hell,” and creates a hexagonal tiling–can you find it? (Hint: look at toes and wing tips to find vertices). Check this link to see if you found it. Escher also made a similar Euclidean tiling: Notebook Pattern or Symmetry Work 45 (1941) [6].

Today, most geometers use computers to study and create tessellations and other geometrical phenomena. The fact the Escher created these using only a compass and ruler is nothing short of miraculous. (This  column explores the nuts and bolts of how he could have achieved that–an especially hard task considering he was working in wood cuts). And recall that Escher was working not only without the aide of technology, but also without the aide of a formal math education. Keeping that in mind, although the technicalities of non-Euclidean spaces can be daunting, the mathematical beauty that arises from hyperbolic geometry are within your grasp, too.

References

[1] Bonahon, Francis. Low-Dimensional Geometry: From Euclidean Surfaces to Hyperbolic Knots, American Mathematical Society, 2009.
[2] Casselman, Bill. How Did Escher Do It?, America Mathematical Society Feature Column.
[3] Dunham, Douglas. Transformation of Hyperbolic Escher Patterns, University of Minnesota-Duluth.
[4] Mackenzie, Dana. The Universe in Zero Words, Elwin Street Press, 2012.
[5] Math & the Art of MC Escher. Hyperbolic Geometry, EscherMath, 2016.
[6] Math Explorer Club. M. C. Escher and Hyperbolic Geometry, Cornell University, funded by the National Science Foundation.
[7] MC Escher, website.
[8] National Geographic. Nudibranchs Photo Gallery.
[9] Organic Facts. Health Benefits of Lettuce.
[10] Schwartz, Richard Evan. Mostly Surfaces, American Mathematical Society, 2011.

This entry was posted in Uncategorized. Bookmark the permalink.

• ## History of Hyperbolic Geometry

Sami was a student in the Fall 2016 course “Geometry of Surfaces” taught by Scott Taylor at Colby College. The essay has been lightly edited before being published here.

Introduction
This essay is an introduction to the history of hyperbolic geometry. Euclid, Gauss, Felix Klein and Henri Poincare all made major contribution to the field. We will discuss some of their influences in the following sections, starting with Euclid and his postulates that defined geometry. Then we will look at the effect of Gauss’s thoughts on Euclid’s parallel postulate through noneuclidean geometry. Later, Klein settled any doubt of noneuclidean consistency. Lastly, Poincare makes some notable contributions to solidifying hyperbolic geometry as an area of academic study.

Euclid’s Postulates
Euclidean geometry came from Euclid’s five postulates. It is the most intuitive geometry in that it is the way humans naturally think about the world. Nonetheless, there are a few other lesser-known, but equally important, geometries that also have many applications in the world and the universe. These “other” geometries come from Euclid’s fifth postulate: “If a straight line falling on two straight lines makes the interior angles on the same side less than two right angles the two straight lines if produced indefinitely meet on that side on which the angles [are] less than two right angles” [6]. See Figure 1(A) below for an illustration of this. An equivalent way to express this is that the angle sum of a triangle is two right angles.

This is also called the parallel postulate because it is equivalent to the following statement: “if one draws a straight line and a point not on that line, there is only one unique line that is parallel to given line through the point” [10]. See Figure 1(B) below.

Figure 1: Visualization of parallel postulate.

Unlike the other postulates, the fifth is not obvious (to satisfy your curiosity, the rest of Euclid’s postulates are attached at the end of this essay). For centuries, mathematicians and amateurs alike attempted to prove that the fifth postulate is a consequence of the first four postulates and other established theorems [6]. However, it turns out this postulate determines whether we are in euclidean or noneuclidean geometry [10].

The Birth of Hyperbolic Geometry
Over 2,000 years after Euclid, three mathematicians finally answered the question of the parallel postulate. Carl F. Gauss, Janos Bolyai, and N.I. Lobachevsky are considered the fathers of hyperbolic geometry. Gauss published little of his work on it because he, allegedly, feared disrespecting Euclid by disproving the parallel postulate. Yet, Gauss extended geometry to include what he coined “non-euclidean,” or the contradiction of the parallel postulate [5]. Bolyai and Lobachevsky published their works on noneuclidean geometry independently but around the same time; however, their findings were not popularized until after 1862, when Gauss’s private letter to Schumacher about his “meditations” on hyperbolic geometry was published. With the work of these three mathematicians, the controversy of the parallel postulate was put to rest. It was definitive that without the parallel postulate, the remaining four postulates created a geometry that is equally consistent [10].

What is hyperbolic geometry?
Now that a brief history of the sources of hyperbolic geometry has been provided, we will define hyperbolic geometry. It has constant negative Gaussian curvature, which resembles a hyperboloid (See Figure 2). Note, that spherical geometry has constant positive curvature [10].

Figure 2: A visualization of Gaussian curvature [8].

First, we will give a few different ways to visualize hyperbolic geometry, then we will explain how to measure distance in this space.

Visualization of Hyperbolic Geometry
A more natural way to think about hyperbolic geometry is through a crochet model as shown in Figure 3 below. This discovery by Daina Taimina in 1997 was a huge breakthrough for helping people understand hyperbolic geometry when she crocheted the hyperbolic plane. This was important because now people can touch and move the crocheted object to get a more intuitive understanding of what a straight line in hyperbolic space would look like.

Figure 3: A crochet from Daina Taimina [3]. You can clearly see that the parallel postulate does not hold here because there are three lines that go through a point and none of them intersect with the given line on the bottom.

As mentioned before, we can visualize hyperbolic geometry through crochet. However, there are some different models including the upper-half plane and the Poincare disk model. See Figure 4 below. The upper-half plane model has the real line as the axis, which we may approach but will never reach. The disk model has the same idea as we approach the edge of the circle. Lines that appear to hit these ideal boundaries at the same point have an angle of 0 between them.

Figure 4

Definition of Distance
Although it may be a bit surprising at first, the definition of metric, or measure of distance, is different for each type of geometry. In Euclidean geometry, the distance is given as

$d_{euc}= \sqrt{(x_1-x_0)^2+(y_1-y_0)^2}$

between two points $(x_0,y_0)$ and $(x_1,y_1)$. Note that in euclidean geometry, the shortest distance between two points is a line (as postulated by Euclid). However, in hyperbolic space, the shortest distance between two points is the arc from point $a$ to point $b$ that lie on the unique semicircle centered at a point on the boundary as shown in Figure 5; if we parameterize the arc as $t \mapsto (x(t),y(t)), \ \ a\leq t \leq b$,

$l_{hyp} = \int_{a}^{b} \frac{\sqrt{x'(t)^2+y'(t)^2}}{y(t)} dt$

See [2].

Figure 5: Hyperbolic geodesic pictured as a euclidean semi-circle centered at a point on x.

Now that we’ve gone over the founding of hyperbolic geometry and have some sense of what it is, we’ll talk about two more influential mathematicians in the field: Felix Klein and Henri Poincare.

Felix Klein
Klein’s contribution to geometry is not only the famous Klein Bottle, but also his proof of the extension of the Cayley Measure on projective geometry to non-euclidean geometry. According to John Stillwell’s translation of On so-called Noneuclidean Geometry, Klein started by showing that each non-euclidean geometry is a special case of projective geometry; he then ended by concluding that non-euclidean geometry can be derived from projective geometry. Furthermore, projective geometry is independent from the theory of parallels; if not, the consistency of projective geometry would be questioned.

Projective Geometry

Projective geometry has simple origins from Renaissance artists who portrayed the rim of a cup as an ellipse in their paintings to show perspective. Projective geometry can be thought of in this way:

The theory of perspective regards the artist’s canvas as a transparent screen through which he looks from a fixed vantage point at the scene he is painting. Light rays coming from each point of the scene are imagined to enter his eye, and the totality of these lines is called a projection. [11]

From there, the idea eventually entered the academic mathematical community where it was incorporated into the study of linear algebra and other areas of mathematics. Projective geometry is the study of invariants on projections – properties of figures which are not modified in the process of projection [11]. Projective geometry is more more general than both euclidean and hyperbolic geometries and this is what Klein uses to show that noneuclidean geometries are consistent.

Figure 6: From the world to the canvas through the artist’s eye. Image found here.

Euclidean and hyperbolic geometry follows from projective geometry

Klein gives a general method of constructing length and angles in projective geometry, which he believed to be the fundamental concept of geometry. To borrow psychology terms, Klein’s approach is a top-down way to look at non-euclidean geometry while the upper-half plane, disk model and other models would be referred to as bottom-up methods. The bottom-up methods are easier to visualize and to deal with applications of hyperbolic geometry. This is remarkable because this top-down approach provides a “more comprehensive” [10] proof than those that had in a case by case manner. Moreover, projective geometry is consistent outside of geometry [10].

Distance in general
The different geometries we get from projective geometry come from the the projection of the fundamental conic. This idea is illustrated below in Figure 7.

Figure 7: Conic Sections

First, Klein defines the general distance function as

$2ic \text{ arccos }\frac{\Omega_{xy}}{\sqrt{\Omega_{xx} \Omega_{yy}}}$
where the constant $c$ determines which space we are in (Hyperbolic, parabolic, elliptic) and

$\begin{array}{rcl}\Omega_{xx} &=& ax_1 ^2+bx_1x_2+cx_2 ^2\\ \Omega_{yy} &=& ay_1 ^2+by_1y_2+cy_2 ^2 \ \text{and} \\ \Omega_{xy} &=& ax_1y_1+b(x_1y_2+y_1x_2)+cx_2y_2 \end{array}$
with $(x_1,x_2) \text{ and } (y_1,y_2)$ as the coordinates of two points.

Klein shows that the fundamental conic section “corresponds completely with the idea of hyperbolic geometry.” Now, the fundamental conic is the projection onto the plane with the appropriate metric; it “determines a measure on all basic figures of the first kind in the plane”[10]. Here, the “first kind” is fuchsian groups [2], which are isometries of the hyperbolic plane. An isometry is a way of transforming a figure in a given space without changing its angles or lengths. Every isometry in hyperbolic space can be written as a linear fractional transformation in the following form:

$\phi(z) = \frac{az+b}{cz+d}$

where $z$ is the complex coordinate of a point. You can think of a complex coordinate in the same way that you think about $(x,y)$ on the euclidean plane where $z = x +\text{i}y$. The “basic figures” are the triangle, circle, and the square. So these isometries take triangles to triangles, circles to circles and squares to squares.

The fundamental conic that forms hyperbolic geometry is proper and real – but “we shall never reach the fundamental conic, let alone pass beyond it”[10]. Recall, our visualizations of hyperbolic space using the upper-half plane model from Figure 4(A), then the fundamental conic is the real line and the fuchsian groups are the isometries acting on $\mathbb{H}^2$.

By using projective geometry to construct noneuclidean geometries, Klein has created a proof that is indisputable.

Henri Poincare
A discussion of the history of hyperbolic geometry cannot leave out Henri Poincare after which the Poincare disk model is named (See Figure 4 (B)). Originally, he began his studies in differential equations, then stumbled upon hyperbolic geometry naturally in his work. He wrote in his book Science and Methods that:

The incidents of travel made me forget my mathematical work. When we arrived at Countances, we got into a break to go for a drive, and, just as I put my foot on the step, the idea came to me, though nothing in my former thoughts seemed to have prepared me for it, that the transformations I had used to define Fuchsian functions were identical with those of non-euclidean geometry. [9]

In fact, he was studying the differential equation $x''(t)+p(t)x(t)=0$ for a given function $p(t)$ that resembles linear fractional transformations with real coefficients. When perturbed to have slightly complex coefficients, this yielded a group $\Gamma$ of linear fractional maps with complex coefficients that act on the Riemann Sphere. This is also related to chaos! He called the ones with real coefficients fuchsian groups after Fuchs and the ones with complex coefficients kleinian groups, though neither Fuchs nor Klein had much to do with the groups they are named after. Allegedly, Klein was offended when Poincare declared the fuchsian group, claiming it had been he, not Fuchs, who had thought about it. So to appease Klein, Poincare named the next group after him. Nonetheless, these are groups of isometries on the hyperbolic plane, $\mathbb{H}^2$ [2].

There have been many other theorems (and still more though current research) in hyperbolic space but these have been instrumental in the creation of hyperbolic geometry. Despite its turbulent history surrounding the parallel postulate and its late debut in the mathematical world, hyperbolic geometry is gaining prominence and has many great applications to the real world.

Euclid’s Postulates [7]:

1. A straight line segment can be drawn joining any two points.
2. Any straight line segment can be extended indefinitely in a straight line.
3. Given any straight lines segment, a circle can be drawn having the segment as radius and one endpoint as center.
4. All Right Angles are congruent.
5. If two lines are drawn which intersect a third in such a way that the sum of the inner angles on one side is less than two Right Angles, then the two lines inevitably must intersect each other on that side if extended far enough.

References:

[1] Antonick, Gary. “The Non-Euclidean Geometry of Whales.” The New York Times. The New York Times, 08 Oct. 2012. Web. 04 Dec. 2016.
[2] Bonahon, Francis. Low-dimensional Geometry: From Euclidean Surfaces to Hyperbolic Knots. Providence, RI: American Mathematical Society, 2009. Print.
[3] Creates, Cris. “Crochet Mathematics: Hyperbolic Crochet.” Crochet Mathematics: Hyperbolic Crochet. N.p., 12 Jan. 2012. Web. 04 Dec. 2016.
[4] “Daina Taimina.” Daina Taimina | Crochet Coral Reef. N.p., n.d. Web. 04 Dec. 2016.
[5] Henderson, David W. Experiencing Geometry: In Euclidean, Spherical, and Hyperbolic Spaces. Contributer: Daina Taimina. 2nd ed. Upper Saddle River, NJ: Prentice Hall, 2001. Print.
[6] Lewis, Florence P. “History of the Parallel Postulate.” The American Mathematical Monthly, vol. 27, no. 1, 1920, pp. 16–23. www.jstor.org/stable/2973238.
[7] McMullen, Curtis T. “Euclid’s Postulates.” Euclid’s Postulates. Harvard University, 1997. Web. 07 Dec. 2016.
[8] Nicoguaro. Gaussian Curvature. Digital image. Wikicommons, 9 Jan. 2016. Web. 6 Dec. 2016.
[9] Poincaré, Henri. Science and Methods. Trans. Francis Maitland. London: T Nelson, 1914. Archive.org.
[10] Stillwell, John. “Introduction and Translation to Klein’s On the So-called Noneuclidean Geometry.” Sources of Hyperbolic Geometry. Vol. 10. Providence, RI: American Mathematical Society, 1996. 63-111. Print. History of Mathematics.
[11] Wylie, C. R. “Introduction to Projective Geometry.” Google Books. Courier Corporation, 2011. Web. 08 Dec. 2016.

This entry was posted in Hyperbolic Geometry and tagged , , . Bookmark the permalink.

• ## Delauney Triangulations and the Traveling Salesman

The Traveling Salesman and Delauney Triangulation

By Aaron Liu

To quote Death of a Salesman, “A salesman is got to dream, boy”, it is easy to understand the struggles that come with being a traveling salesman. I like to think that the main character was dreaming of a quick way to approximate a path from his starting location to every city and back. I know that that might not have been his exact dream, but if I were a salesman I would dream of a solution to this problem.

It is hard to imagine the struggles of the traveling salesman, but if you take a quick look at the picture below, you will understand why a salesman must dream. Must I remind you that the distance from Boston to California as shown on the map is approximately: 3,109.3 miles. That’s about 5003.9333 kilometers for all of my European readers.

Currently there is no effect method of solving this problem for all situations. There are no known algorithms that will work 100% of the time and a lot of people have come to accept that fact (not me). But, there are ways to approximate solutions to the traveling salesman problem and one way involves topology. More importantly, I’m going to use the brilliant work of Boris Delauney and his triangulation in order to detail the approximations.

Triangulation Basics

I bet you are wondering how to create a Delauney Triangulation. Lucky for you I’m about to explain just that. Let’s start off with a simple graph in order to understand the basics.

In order create a Delauney Triangulation we need to consider all of the circles around sets of 3 points. Generally, if we start on the outside we can work our way inward. These such circles are called circumcircles and the key aspect is the fact that no point on the graph is inside a circumcircle. This may sound very complex and hard to achieve and that may be true for huge graphs, but for our example the Delauney Triangulation is actually quite simple.

It is easy to picture if you isolate the circles. Notice how the circumcircles overlap, but no point is inside of a circumcircle. Above all of the circles created is the triangulation that we wanted. The triangles are created by the circumcircles. Every point is connected with an edge to points that it shares a common circle with. It is important to note that if there is ever a circle with four points on it, the Delauney Triangulation will not exist. Conceptually this is makes sense because if that were allowed, we might have to call it a Delauney Polygonation. Sorry for that terrible joke.

In any event, the circumcircles allow us to create the triangulation and also give the triangulation some key features. But, first here are some important concepts.

Important Concepts:

A simplex is a dimensional piece of the whole. A 0-simplex would be a point, a 1-simplex would be a line segment, a 2-simplex would be a triangle, a 3 simplex would be a tetrahedron and so on.

Also the convex hull is the points such that all other points can be contained within those points. In the graph below the points P0, P1, P3, P10, P12 are the convex hull.

Now that you are enlightened with those key definitions, here are some key features of the triangulation:

• The union of all the simplicies is the convex hull of the points
• The triangulation maximizes the minimum angle of the triangles

This second characteristic means that the smallest angle of a triangle in the triangulation tends to be high. The triangulation rarely has scalene triangles because that would mean that two of the points were close together and the other was far away. This rarely occurs because if that were the case then the circle would likely be much bigger and has a higher chance of containing a point on the interior.

Delauney triangulations are derived from Voronoi diagrams. A Voronoi diagram can be created by connected the centers of the circumcircles of a Delauney triangulation. If you want to know more about the diagrams, take a quick look at Vlad’s post.

If not, or you believe you have a strong grasp on the triangulation, continue reading about the traveling salesman.

Delauney Triangulation and the Traveling Salesman

After seeing the above triangulation, it is hard to obviously see how the triangulation can be used to find a shortest path. The importance of approximating the traveling salesman problem is the quickness and in this situation, the ability to find a working solution. In the case of a Delauney Triangulation we can use the fact that none of the points are inside any other triangle. This is important because that means the triangulation has edges between points that are the closest to each other. It also gives us enough edges that we can construct a fairly accurate approximation.

Delauney Triangulations simply approximate so there are a lot of different algorithms that can be used. Also, the algorithms tend to grow to many and many lines of code that are very difficult to understand. Thus, I will explain a few such algorithms.

Algorithm Basics

Constructing an algorithm to approximate the shortest path using Delauney Triangulations can be very difficult. However, a lot of the characteristics of the Delauney Triangulation are very relevant to creating a shortest path algorithm.

Consider the following Delauney Triangulation:

Looking at this triangulation it is easy to see how an approximation to the shortest cycle could exist. The edges minimize the distance between the points and allow us to connect all points of the graph. Also, it is important to note that the amount of edges needed to be checked is much less than if there had been an edge between each vertex.

In order to find an approximation you can systematically check and eliminate unnecessary edges of the graph. The methods of doing this will vary greatly and will have to be very specific. The level of accuracy of the approximation will depend on how the edges are checked and removed.

Algorithms

The easiest method of doing this would be a brute-force check of all of the possible paths and eliminate the edges that are not in it. This method can be time-consuming, but would still be comparatively fast and accurate.

Another method would be a variation of the brute-force, but would compare the edges used in the path to the length of the path. The algorithm would look for certain edges that are contained in longer paths and would eliminate them. The algorithm would continue to eliminate edges, which would decrease the amount of work needed to find an approximation.

There are so many different variations of an approximation algorithm because after all it is approximation. One last algorithm that might be useful is checking a random amount of random paths and simply returning the path that produced the smallest distance. This obviously is not as accurate as the other algorithms, but is nonetheless useful if a quick solution is needed.

These algorithms are similar to an algorithm implemented by Christine T. Phan. Her paper can be found here.

It is important to note that at the end of her paper she states her results. She said on average Delauney Triangulations contained about 99.28% of the edges in the true shortest path. Using her own algorithm, similar to the ones described above, she was able obtain a 76.1% accuracy with her approximations. Although that number is not incredibly high, the results show that there are algorithms that will accurately approximate solutions to the problem. Perhaps, you will one day develop such an algorithm.

Conclusion

It has been shown that although Delauney Triangulations do not necessarily contain the optimal path, the triangulations contain edges that are in the optimal path. Thus, the quick approximation is very valuable and non-time-consuming. Delauney Triangulations are constructed in a way that is ideal towards finding a shortest path. Below are some resources that you can read if you want to learn more about Delauney Triangulations and the Traveling Salesman Problem. I guess until you do some more research and look into solving the problem, a salesman will just continue to dream.

Aaron Liu was a student in Scott Taylor’s Fall 2014 Topology class.

References:

http://www.geom.uiuc.edu/~samuelp/del_project.html

http://en.wikipedia.org/wiki/Delaunay_triangulation

http://oas.uco.edu/00/Papers/phan.htm

http://www.nytimes.com/interactive/2012/03/01/theater/201203-death-of-a-salesman-interactive.html

http://kiharalab.org/3d-surfer/v1.0/convex_hull.gif

This entry was posted in Uncategorized. Bookmark the permalink.

• ## Topology & Infinite-Dimensional Linear Algebra

For the student wishing to see interplay between the three major branches of mathematics (analysis, algebra, topology), Hilbert Space is a great place to explore!  Hilbert Space is a tool that gives us the ability to do linear algebra in infinite dimensions.  The very fact that infinity is involved should tell us that we will need analysis, and where ever there’s analysis, there’s also topology.  Oftentimes, interplay between analysis, algebra, and topology is not glimpsed at the undergraduate level; such connections are designated as “grad school material”.  Hilbert Space will offer us a chance to see these connections at work. Rather than give a host of definitions that define Hilbert Space and then give an example, it will perhaps be useful to work in the reverse order.  Consider the set of all complex-valued sequences.  An element of this set might look like this: $(4+ i, 3 - i, 1 - 7i, 5, 0, 5-9i, 2i,\ldots)$.  We look at a special subset:  let $\ell_2$ be the subset consisting of sequences that are square summable; that is, the sequences $(x_n)$ satisfying

$\sum\limits_{i=1}^\infty {\vert x_{i} \vert}^2 < \infty$.

It shouldn’t be entirely clear why we are interested in sequences satisfying this seemingly arbitrary condition, but shortly we will see its importance.  Notice the similarity between the dot product and the infinite sum on the left – the sum looks a lot like the dot product of a vector in $\mathbb{C}^n$ with itself.  The set $\ell_2$ is an example of Hilbert Space; it is just the natural extension of $\mathbb{C}^n$.  We will work a lot with $\ell_2$, but first let’s make sure we really understand this space.  We set out on defining Hilbert Space – a fairly tall order as we shall see!

David Hilbert first introduced the concept of Hilbert Space

This may sound intimidating; it shouldn’t be. A Hilbert Space is just a very special type of vector space. Recall from linear algebra that a (real or complex) vector space $V$ is a set that is closed under addition and scalar multiplication (by real or complex numbers). We call a subset $B$ of $V$ a basis if $V = span(B)$ and if $B$ is linearly independent. In this case we define the dimension of $V$ by saying $dim(V) = \vert B \vert$. Notice that there is nothing about this definition which requires $B$ to be a finite set. Indeed, while finite dimensional vector spaces are the primary object of consideration in linear algebra, so-called infinite dimensional vector spaces are the central object in a subject called operator theory, and Hilbert Space is to operator theory what $\mathbb{R}^n$ and $\mathbb{C}^n$ are to linear algebra. We need a few preliminary definitions in order to define a Hilbert Space. We will work over $\mathbb{C}$ (it is no more difficult to do so than to work over $\mathbb{R}$). We first define an inner product on a vector space $V$.  An inner product is just a generalization of the dot product on $\mathbb{R}^n$ or $\mathbb{C}^n$.  Recall the importance of the dot product: it gives us a notion of length, angle, and orthogonality.  So an inner product on an arbitrary vector space is a way of giving the space some geometry. An inner product is denoted $\langle \cdot , \cdot \rangle$, and we replace the dots with vectors to indicate that we’re taking the inner product of those two vectors.  Of course, there is a more rigorous, axiomatic definition.  For thoroughness, we state this definition, but it can be safely ignored without loss of understanding later on.  An inner product on a vector space $V$ is a function from $V \times V$ to $\mathbb{C}$ that satisfies the following four rules:

1. $\langle a + b, c \rangle = \langle a , c \rangle + \langle b , c \rangle$ for every $a, b, c \in V$.
2. $\langle \lambda a , b \rangle = \lambda \langle a , b \rangle$ for every $a, b \in V$, $\lambda \in \mathbb{C}$.
3. $\langle a , b \rangle = \overline{\langle b , a \rangle}$ for every $a, b \in V$.
4. $\langle a , a \rangle$ is real and greater than $0$ if $a \neq 0$.

Note that if we were working over $\mathbb{R}$, property (3) would just say that the inner product is symmetric.  We call a vector space with an associated inner product an inner product space. Recall that the definition of the dot product on $\mathbb{C}^n$ is $x \cdot y = \sum\limits_{i=l}^n x_{i}\overline{y_{i}}$, where $x_{i}$ and $y_{i}$ are the components of $x$ and $y$, respectively. The dot product satisfies all the properties above, and so it is an inner product on $\mathbb{C}^n$.  Once one has verified that the dot product on $\mathbb{C}^n$ is an inner product, it is not too hard to convince oneself that the extension of the dot product to $\ell_2$ is an inner product as well.  We define an inner product on $\ell_2$ by

$\langle x , y \rangle = \sum\limits_{i=1}^\infty x_i \overline{y_i}$

An example of a norm, just the usual distance function on the plane

The square summable condition we imposed on $\ell_2$ suddenly makes sense.  If we tried to compute the above inner product on sequences that are not square summable, we might end up with a divergent series on the right side of the equation – and we don’t want that! We define the norm of an element $v$ in an inner product space $V$ to be $\Vert v \Vert = \langle v , v \rangle ^\frac{1}{2}$. We will denote the norm on $\ell_2$ by ${\Vert \cdot \Vert}_2$.  Notice that if one applies this definition to $\mathbb{R}^n$, the norm of a point is just its distance in the origin.  So we think of a norm as a function that assigns lengths to vectors in our vector space.  In general, a norm is any function $\Vert \cdot \Vert: V \to \mathbb{R}$ that satisfies the following three axioms:

1. $\Vert x \Vert \geq 0$ for all $x \in V$, with equality if and only if $x = 0$.
2. $\Vert \lambda x \Vert = \lambda \Vert x \Vert$ for all $x \in V$, $\lambda \in \mathbb{C}$.
3. $\Vert x + y \Vert \leq \Vert x \Vert + \Vert y \Vert$ for all $x,y \in V$.

One can verify that any inner product induces a norm. Although we defined the norm in terms of an inner product, we say that any function satisfying (1), (2), and (3) is a norm, whether or not it is given in terms of an inner product. So, any inner product defines a norm, but not every norm is given by an inner product. For example, it is impossible to define an inner product on $\mathbb{R}^2$ such that the induced norm is $\Vert (x,y) \Vert = max\{ \vert x \vert , \vert y \vert \}$.

Sequences of rational numbers can ”converge” to irrational numbers, so the rationals are not complete

We need one more definition before we can define a Hilbert Space. We need the concept of completeness. This is a fundamental property of the real numbers – completeness is what allows us to do real analysis. Essentially a space is complete if there are no “gaps” in it. For example, $\mathbb{Q}$ is not complete because the sequence $3, 3.1, 3.14, 3.141, 3.1415, \ldots$ should converge, but it doesn’t (in $\mathbb{Q}$). Such a gap does not exist in $\mathbb{R}$, so we say the reals are complete. We are now in a position to define a Hilbert Space: a Hilbert Space is a complete vector space equipped with an inner product. A similar structure is a Banach Space, which is a complete vector space equipped with a norm. So any Hilbert Space is a Banach Space, but the converse is not true. We can immediately get our hands on some Hilbert Spaces: $\mathbb{R}^n$ and $\mathbb{C}^n$ are both finite-dimensional Hilbert Spaces. These are not particularly interesting Hilbert Spaces because they are finite-dimensional. But we are also ready to consider an infinite-dimensional Hilbert Space.  As we stated before, $\ell_2$ is a Hilbert Space.  It is not difficult to show that $\ell_2$ is a vector space, and we’ve already defined an inner product on it.  Showing that $\ell_2$ is complete does take a bit of work, but it’s doable.  We can also readily see that $\ell_2$ has no finite basis.  Indeed, an example of a basis for $\ell_2$ is the collection of sequences $e_{i} = (0, 0,\ldots, 1, 0, 0,\ldots)$ where the $1$ appears in the $i^{th}$ entry.  Of course, there are many other examples of Hilbert Spaces, but a somewhat remarkable fact is that every Hilbert Space that has a countable (indexed by $\mathbb{N}$) basis is isomorphic to $\ell_2$! For this reason, mathematicians sometimes refer to “the” Hilbert Space, as if there is only one. The upshot is that we can work exclusively in $\ell_2$ without sacrificing the generality obtained by referring to a general Hilbert Space.

A rotation about the origin is a linear operator on the plane

Since $\ell_2$ is a vector space, the natural thing to do is think about linear transformations of the space.  We define a linear operator on $\ell_2$ in the same way a linear transformation is defined in linear algebra. A function $T: \ell_2 \to \ell_2$ is a linear operator if

1. $T(x+y) = T(x) + T(y)$ for every $x,y \in \ell_2$.
2. $T(\lambda x) = \lambda T(x)$ for every $x \in \ell_2$ and $\lambda \in \mathbb{C}$.

It should be noted that not everything one may have learned about linear transformations in linear algebra is true for linear operators on $\ell_2$. For example, consider the shift operators $S$ and $S^*$ on $\ell_2$ defined by $S(x_1,x_2,x_3,\ldots) = (0,x_1,x_2,\ldots)$ and $S^*(x_1,x_2,x_3,\ldots) = (x_2, x_3,x_4,\ldots)$. It is easily verified that these are both linear operators, and that $S$ is injective but not surjective, $S^*$ is surjective but not injective, and $S^*S = I$ but $SS^* \neq I$. In linear algebra, one learns that all of these conditions are equivalent, but in Hilbert Space this is not the case.  An important part of operator theory is determining what kinds of operators on $\ell_2$ behave like linear transformations on a finite-dimensional vector space.

We call a linear operator $T$ on $\ell_2$ bounded if there is a constant $M$ such that $T$ is bounded on the unit ball $\mathbb{B} = \{ x \in \ell_2 : {\Vert x \Vert}_2 \leq 1 \}$ by $M$. The norm ${\Vert T \Vert}_{op}$ of a linear operator is defined to be the smallest such $M$ that works in the preceding definition. Equivalently, ${\Vert T \Vert}_{op}$ is the largest value of ${\Vert T(x) \Vert}_2$, where $x$ ranges over the unit ball in $\ell_2$. An interesting fact about linear operators on $\ell_2$ is that they are continuous if and only if they are bounded (an exercise!). We define $B(\ell_2)$ to be the set of all bounded (continuous) linear operators on $\ell_2$.

$B(\ell_2)$ is an interesting space in and of itself: equipped with the norm defined in the preceding paragraph, $B(\ell_2)$ is a Banach Space (a complete normed vector space) with respect to pointwise addition and multiplication by complex scalars. We have seen a little bit of analysis and algebra, so it’s time to introduce some topology to the mix. Our goal is to define and understand some topologies on $B(\ell_2)$. This should be a bit surprising. After all, what does it mean for a subset of linear operators to be “open”? There are many topologies that can be put this set, but we will consider the three most common ones: the norm topology, the strong operator topology, and the weak operator topology. In describing a topology on a space, it is difficult to pin down exactly what the topology is; this is because in most interesting spaces, there are so many open sets that it’s impossible to list all of them. Instead we can define a topology by describing what properties our set has when equipped with this topology. For example, we might say that a topology on a set $A$ is “the smallest topology such that our space $A$ has property $X$“. We can also define a topology in terms of a base which, roughly speaking, is a collection of open sets that generates the rest of the open sets (by taking unions). Before we embark on defining different topologies on $B(\ell_2)$, let’s stop and think about why we may need different topologies on the same set, and whether it is of real importance. A question one may ask is, “What properties of $B(\ell_2)$ will change when the topology changes?” As we will see shortly, the definition of convergent sequence changes drastically. It may not seem obvious that changing the topology will have a big effect on convergence of sequences; after all, the definition of convergence that one meets in a real analysis course does not explicitly mention open sets! But let’s examine this a little closer. In real analysis, convergence is usually defined in regards to a metric. In more general topological spaces, there may be no metric (although in Hilbert Space the metric is induced by the norm), so the definition from real analysis may not be applicable. Nevertheless, we can define convergence in terms of open sets thusly (and this definition works in every topological space, including metric spaces):

Take an open interval about 1 on the vertical axis and eventually, all but finitely many points are in this interval

Let $(x_n)$ be a sequence in a topological space $X$.  We say $x_n \to x$ if for every open set $U \subset X$ containing $x$, we have $x_n \in U$ for sufficiently large $n$. It is clear, now, that convergence depends on the definition of open set. As we introduce new topologies on $B(\ell_2)$, we can describe what convergence “means” with respect to this new topology.

The norm topology on $B(\ell_2)$ is the topology induced by the operator norm. To explain what this means, let us consider that any normed space has a corresponding topology induced by its norm. Think about $\mathbb{R}$ for example. The norm of a point in $\mathbb{R}$ is

The open set O(1.5, 1.5)

just its absolute value. Think about the subsets of $\mathbb{R}$ defined by $O(x,\epsilon) = \{ y \in \mathbb{R}^2 : \vert x - y \vert < \epsilon \}$, where $x \in \mathbb{R}$ and $\epsilon$ is a positive real number. Each set is an open interval centered at $x$ and of radius $\epsilon$. The open sets in $\mathbb{R}$ are open intervals and unions of open intervals, so the collection $\{O(x,\epsilon) : x \in \mathbb{R}, \epsilon > 0 \}$ is a base for the usual topology on $\mathbb{R}$. Now we return to our set $B(\ell_2)$, where the norm topology will be defined analogously. The collection of all subsets of $B(\ell_2)$ of the form $O(T, \epsilon) = \{ S \in B(\ell_2) : {\Vert S - T \Vert}_{op} < \epsilon \}$ is a base for the norm topology on $B(\ell_2)$.  Remember that a norm is a way of defining length or distance in our space.  So the set $O(T, \epsilon)$ is the set of all operators that have distance from $T$ less than $\epsilon$.  It probably seems odd think about the distance between two functions – this is why we need careful and precise definitions of norms and, in particular, the operator norm.  The norm topology is a very important topology on $B(H)$ indeed – it is the topology which makes $B(\ell_2)$ a Banach Space.

Before looking at any special properties of the norm topology, we introduce the next topology on $B(\ell_2)$ because the interesting thing to do is to compare the different topologies. Next we consider the Strong Operator Topology (SOT). The SOT is defined to be the smallest topology containing all sets of the form $U(T,x,\epsilon) = \{ S \in B(\ell_2) : {\Vert S(x) - T(x) \Vert}_2 < \epsilon \}$ where $T$ is any bounded linear operator, $x$ is any element of $H$, and $\epsilon$ is any positive real number. Equivalently, SOT is the smallest topology on $B(\ell_2)$ such that the evaluation maps $T \mapsto T(x)$ are continuous for every choice of $x \in \ell_2$. A word of caution: The sets $U(T,x,\epsilon)$ may seem very similar to the sets we defined in the previous paragraph, but they’re not. Notice that we use the $\ell_2$ norm here, and the operator norm in the preceding paragraph. It is important to keep track of which norm function is being used and what quantity is inside the norm – of course, it wouldn’t make sense to take the operator norm of the quantity $S(x) - T(x)$! We can describe some of the properties of the SOT. The SOT is (somewhat paradoxically) weaker than the norm topology; that is, there are more open sets in the norm topology than there are in the SOT. The SOT is perhaps a more natural choice of topology on $B(\ell_2)$. To explain this, I first pose a question: what does it mean for a sequence of bounded linear operators $(T_n)$ to converge to an operator $T$? Well, it depends on which topology you use! In the SOT, the sequence $(T_n)$ converges to $T$ if for every $x \in \ell_2$, the sequence $(T_n(x))$ converges to $T(x)$. That is, convergence in SOT means that a sequence of operators converges pointwise to some operator. This indeed seems like a very natural definition of convergence. Contrast this with convergence in the norm topology: the sequence $(T_n)$ converges to $T$ in the norm topology if ${\Vert T - T_n \Vert}_{op} \to 0$.  In a way, this definition of convergence seems more complicated and less natural than convergence in SOT.  This already is an advantage of using SOT instead of the norm topology. We mentioned that SOT is weaker than the norm topology. It isn’t too difficult to show that convergence in the norm topology implies convergence in SOT (for the reader who wants a challenge: assume ${\Vert T_n - T \Vert}_{op} \to 0$. Pick $x \in \ell_2$ and show $T_n(x) \to T(x)$). Using the given definitions of convergence in each topology, we can show that the converse is not true. Consider the following sequence of operators $(P_n)$ on $\ell_2$:

$P_n(x) = \sum\limits_{i=1}^n \langle x , e_i \rangle x$,

where $\{e_i\}$ is the basis we defined earlier. The operators $P_n$ are called projections, because they take an input $x$ and project $x$ onto the linear span of the first $n$ basis vectors. It is not hard to see that as $n \to \infty$, we have $P_n(x) \to x$, i.e. $P_n \to I$ in SOT ($I$ is the identity operator). However, the claim is that $P_n \nrightarrow I$ in the norm topology.  We will just sketch a proof here.  Let $m,n \in \mathbb{N}$ with $m > n$.  Then find a lower bound on ${\Vert P_m - P_n \Vert}_{op}$ (a bound of 1 is easy to obtain by picking the unit vector that has a $1$ in the $m^{th}$ entry and else all zeroes).  What this tells us is that every element of the sequence is at least distance 1 from every other element of the sequence, and clearly no sequence with this property can converge.

The third and final topology we introduce on the space $B(\ell_2)$ is the Weak Operator Topology (WOT). The WOT is the smallest topology on $B(\ell_2)$ containing the following sets $U(T,x,y,\epsilon) = \{ S \in B(\ell_2) : \vert \langle T(x) - S(x) , y \rangle \vert < \epsilon \}$, where $T \in B(\ell_2)$, $x, y \in \ell_2$ and $\epsilon$ is a positive real number. Equivalently, the WOT is the smallest topology such that the map (called a linear functional) $T \mapsto \langle T(x) , y \rangle$ is continuous for any choice of $x, y \in \ell_2$.  So a sequence of operators $(T_n)$ converges to an operator $T$ if $\langle T_n(x) , y \rangle \to \langle T(x) , y \rangle$ for every choice of $x, y \in \ell_2$.   In order for the names given to these topologies to make sense, we had better hope WOT is weaker than SOT. Alas, this is indeed the case. Again, it is not hard to prove that SOT convergence implies WOT convergence (the only part that may be difficult is to show that an inner product is continuous). Again we can show the converse does not hold. Recall the definition of the shift operator $S$ on $\ell_2$. Define $S_n$ by composing $S$ $n$ times. That is, $S_n(x_1, x_2, x_3,\ldots) = (0, 0,\ldots,x_1, x_2, x_3,\ldots)$ where the sequence on the right starts with $n$ zeroes. First we can show that $S_n \nrightarrow 0$ in SOT. Consider $x = (1,0,0,\ldots)$. Then the sequence $(S_n(x))$ does not converge to the $0$ sequence. To see this, take any $m,n \in \mathbb{N}$ with $m \neq n$. Then $S_m(x) - S_n(x)$ is a sequence with $1$ in the $m^{th}$ entry and $-1$ in the $n^{th}$ entry, hence we have ${{\Vert S_n(x) - S_m(x) \Vert}^2_{2}} = 2$. Since this is true for any choice of $m$ and $n$, the distance between any two distinct points in the sequence $(S_n(x))$ is $\sqrt{2}$.  So the sequence does not converge to any limit, including $0$. It is harder (but not too difficult) to show that $S_n \to0$ in WOT. The reader who wishes to provide a proof of this statement may want to read about linear functionals and the Riesz Representation Theorem.

Of course, there is much more to say about Hilbert Space (and even about $B(\ell_2)$ than I could fit into this post.  Hilbert Space could easily be the sole focus of a semester- or even year-long course.  In his Mathematics: a Very Short Introduction, mathematician Timothy Gowers wrote, “The notion of a Hilbert Space sheds light on so much of modern mathematics, from number theory to quantum mechanics, that if you do not know at least the rudiments of Hilbert Space theory then you cannot claim to be a well-educated mathematician.”  Hopefully the reader leaves with an appreciation for the fact that Hilbert Space is a (relatively) easy space to understand and that algebra, analysis, and topology are all lurking around in Hilbert Space.

The author Dan Medici was a student in Scott Taylor’s Fall 2014 Topology class at Colby College.

This entry was posted in Uncategorized. Bookmark the permalink.

• ## Using Configuration Spaces to Find Inscribed Squares

As an undergraduate in mathematics, every once in a while, one of your math friends will send you a link to a very interesting unsolved problem in mathematics.  I made the mistake of clicking on one, because after reading it, it captivated my mind for weeks: “The Inscribed Square Problem.” Now, this conjecture says that for any simple closed curve (Jordan curve), there is a square whose corner points all lie in the curve. On first examination, I thought to myself, “wow there’s no way this is true, there are some pretty messed up curves out there, and I bet there’s at least one of them where this does not hold.” So I went to talk to my topology professor about this and we talked about a method of approaching this problem using configuration spaces, which I will talk a little bit about in this blog post.

First we will start off by explaining exactly what a configuration space is. A configuration space is a way to topologically represent how objects can be placed and moved around within certain spaces. For example, if you have a circle and you want to place two points on it, you might start by thinking that for every place you put your first point, the places that you could place the second point can be represented by a circle with a point removed (because both points cannot be in the same place), and so it turns out that the configuration space of two points in a circle (denoted $C^2(S^1)$ where $S^1$ is the circle and the superscript 2 denotes how many bodies are in the space) is $S^1 \times(S^1 - \{a\})$ where a is a point on the circle. Now this is interesting, because $S^1 \times S^1$ is an interesting construction called the torus (it’s pretty much just a doughnut):

However, removing a point from the second circle transforms it into a line segment

so you end up with something similar to $S^1 \times (S^1 - \{a\})$ which looks like the result of rolling a piece of paper up. (Something akin to the outside shell of a hollow cylinder without the circles on the ends)

Now, while you may believe me when I say that each point on this gives a place for two positions on the circle, let us examine how this actually works, here I have drawn a circle with two points A and B on it (I have also drawn an arrow at the top as a reference point).  First let us choose our A position.  The place around the cylinder determines where our first point should go.  We want to place our A point somewhere on the cylinder where the dashed-and-dotted line is because that is where A is in relation to our point of reference (note that if we were to look at the cylinder from the top, that line would correspond exactly to where A is).  Now, the height at which we place our B point on the cylinder is determined by where in relation to A it is.  Here we can see that B is a little after A if we head clockwise around the circle.  So we can place B a little bit away from the top to get the point shown on our cylinder.  Note that this also demonstrates why the bottom and top of our cylinders are open, because as we get to the edges of the cylinder, we get closer and closer to the A point, but can’t actually reach it.  If we could, we could say that the top and bottom of our cylinder were essentially the same circle and “glue” them together to get the torus.

Now, a Jordan curve in the plane can be described as the image of an injective continuous function from the unit circle to the plane. Knowing that our goal is to try and determine whether it has an inscribed square, we should start by examining how 4 points can be configured on our curve, that is $C^4(\phi(S^1))$ where $\phi$ is our injective continuous function. Now, because our curve is continuous and does not cross over itself, it is essentially just a circle which has been squished and pulled to make it our circle, so by reversing our process (finding a continuous function which when composed with $\phi$ gives us a circle), we can deform it back into the circle:

and by doing this, we can notice a few things about the structure of our configuration space. Firstly we already know how to place 2 points on the circle, but we can also realize that placing four points on the circle is exactly the same as placing 2 points on the circle twice! (This is fairly obvious in real life, but its mathematical meaning has a bit more significance) that is

$C^4(S^1) = C^{2}(C^{2}(S^{1}))$

So, we can look at the configuration space of $C^2(\phi(S^1))$ and notice that it will be equal to

$C^{2}(C^{2}(S^{1})) = (C^{2}S^{1}))\times(C^{2}(S^{1})-\{a\})$

So what on earth does this mean? It means that for every point in one of our “cylinders” we can represent two point on the circle by placing one point in our cylinder-like construction and then placing our second point on a different cylinder-like construction with a point missing (Taking the cross product of the two spaces)

Alternatively, you could just declare your configuration space to be

$C^{4}(\phi(S^{1})) = \{(a,b,c,d)\in S^{1} | a\ne b\ne c\ne d \}$

But I find the first definition to be much easier to picture in my head than the second succinct but abstract one.
So, now that we have a rough picture of a configuration space for if our curve was a circle, remember that we simplified this by stretching it into a circle, now we can translate it back to our initial curve, $\phi$, by twisting and bending every circle that we encounter back into our Jordan curve (slightly more formally, we have been composing $\phi$ with a function which continuously deforms it into a circle.  At this point, we stop composing $\phi$ with that function).

Now, let us talk briefly about how we can define some fairly useful functions on configuration spaces.  First let’s look at the distance function $d:C^2(S^1)\rightarrow \mathbb{R}$.  First let us not that this function is continuous, if we change our point in the space by a tiny bit, the distance between the two points will not change drastically.  Also we can see that the closer you get to the edges of the cylinder, the closer the two points are (at the edges, they would occupy the same space), so from this, we can see that the maximum distance is the ring in the very center of our cylinder.  This is a very neat way of seeing that the points in the ring in the center of our cylinder occur exactly when our two points on the circle are placed opposite each other.

We can now define very useful function $f$ from $C^4(\phi(S^1))$ to the set {0,1} such that a point $x \in C^4(\phi(S^1))$ is mapped to 1 if one of the components (the points coming from each mutilated circle) $x_1$ is a distance c away from $x_2$ and $x_3$ and is a distance $c\sqrt{2}$ away from the third one, and furthermore, that $x_3,x_1,x_2$ form a right angle and that $x_1,x_2,x_4$ form a right angle. This will ensure that any point in the configuration space that would make a square in the original curve (remember that the configuration space has coordinates for four points on the curve) gets mapped to 1. Now, we can proceed from here in several different ways, we could take the preimage $f^{-1}(1)$ and determine if it is not empty, or we could define the topology on our configuration space to be the indiscrete topology, (the one where the only open sets are the empty set and the entire space), this has the benefit that the only functions which are continuous are constant functions. So, since there will be at least one point in our configuration space which gets mapped to 0 (otherwise every set of four points is an inscribed square, which is obviously not the case), so if $f$ maps a point to 1, it will be discontinuous, and so all we need to do is check to see if f is continuous.

Now, this is easier said than done, the nature of this function $f$ is such that determining whether it is continuous could be just as difficult as determining the truth of the original statement using geometric means. However, topology has many different ways of determining continuity, so it could just be that someone could come along and prove that this function is always discontinuous (meaning that the conjecture holds) or they use this method to construct a curve where our function is discontinuous (the conjecture does not hold)

We could also define a continuous function $f^\prime:C^2(S^1)\rightarrow \mathbb{R}^6$ whose components are the distances between two respective points.  We’ve already seen that the distance component is continuous, and so since its components are continuous $f^\prime$ will be continuous.  Now, we just have to see where in $\mathbb{R}^6$ the function would satisfy the conditions.  This is not too difficult, it is fairly common knowledge that for the four points in a square, the distance between four pairs of them will be equal, and the distance between the other two pairs will be equal as well.  So, any point in $\mathbb{R}^6$  where 4 of the components are equal and the other two are equal as well will do.  Now, since $f^\prime$ is continuous, we have many tools at our disposal to determine whether or not there is a point in its range which satisfies the conditions for being a square.

For more information on the inscribed square problem and what has been proven about it, visit this website

<i>Professor’s note:</i> Joseph took Topology from me (Scott Taylor) in the Fall of 2014. Although there some inaccuracies in the exploration of configuration spaces above, I was quite taken with the refreshing approach and tone of the piece, so I have left it unedited.

This entry was posted in Uncategorized. Bookmark the permalink.