Thursday, December 17, 2015

Connectedness properties of arithmetic progressions and a topological proof of the infinitude of primes

MathJax LaTeX Example Page

I took a class in point-set topology this fall and we were required to write a final paper for the course. My paper discusses various topologies on the arithmetic progressions and proves theorems regarding their connectedness properties. It has been almost five years since I've posted on Wheels of the Future, and I have been considering bringing it back with the various papers I've been writing, so I thought this was a good opportunity to relaunch the site. Although Wheels of the Future was started to draw analogies to skateboarding from economics and psychology books I had been reading at the time I started the site, it would be cool to take it into a new direction.

In computer science, I find the graph data structure fascinating. Two graphs can have the same vertices, and even store the same data types in those vertices, but differ greatly in how the vertices are connected. There is a property in graph theory called connectedness, which means between any two vertices in the graph, there is a path or series of edges that connects them. If a graph is not connected, it is disconnected. The connectedness property of a graph is extremely important in applications. For example, suppose that you wanted to find the minimum time it would take to get from one city to another in the United States without paying tolls. You could model each city in the United States as a vertex, create an edge, $(v, w)$, from one city to another if it is possible to get to that city without paying a toll, and then associate with each edge the average time (the cost) it would take to get from the city $v$ to the city $w$. One could use a minimum cost path finding algorithm such as Dijkstra's algorithm to find the minimum time it would take to get from a city, $v$, to a city, $w$, without using tolls. If the graph modeling cities is disconnected, there are cities $a$ and $b$ such that there is no path that connects them without paying tolls and the cost is positive infinity, and it is easy to find what those cities are. There is an even stronger notion of connectedness in graph theory called bi-connectedness, which means the removal of any one vertex and its incident edges from a graph will result in a disconnected subgraph. If a graph is connected, but not bi-connected it must have a cut vertex, which is a vertex that if removed along with its incident edges will result in a disconnected subgraph.

Like graph theory, topology has its own notions of connectedness; a connected space is defined to be a space that has no separation. Similar to how a cut vertex in graph theory causes a connected graph to yield a disconnected subgraph if removed, a cut-point in a connected topological space is a point whose removal causes the resulting space to be disconnected. These analogies between connectedness in topology and connectedness in graph theory are why connectedness is one my favorite topological properties. Another reason I find the topological property of connectedness so fascinating is that there are some extremely interesting and rich proofs showing spaces are connected or not despite how simple the definition of connectedness is.

One of my favorite proofs I did this semester in topology was quite early on in the course. The proof was to show that the collection of arithmetic progressions is a basis for a topology on the integers called Furstenberg's topology. We had just learned about the concept of a basis for a topology, and topology in general was all new to me. I think one of the reasons I enjoyed the proof so much is that any arithmetic progression is a simple set to understand, but the process of showing that if an integer, $x$, lies in two different arithmetic progressions, $A_{1}$ and $A_{2}$, that there must be a third arithmetic progression, $A_{3}$, containing $x$, and then showing $A_{3}$ is contained in $A_{1} \cap A_{2}$ was quite a challenging and stimulating task. After solving this problem it was very cool to find out that Hillel Furstenberg used the arithmetic progressions basis to give a topological proof of the infinitude of the set of prime numbers, $P$. Furstenberg's proof got me extremely excited about prime numbers and it was great to find out that Paulina Szczuka discovered some interesting things about one of my favorite topological properties, connectedness, on $P$ as a subspace of $\Bbb{Z}$ with Furstenberg's topology as well as several other topologies on $\Bbb{Z^{+}}$. This paper describes some of those results and applications.

In Section I, we give basic notation, definitions, and thoerems regarding the topologies we will be using. In Section II are theorems I've reconstructed; the first two theorems were originally proven by Paulina Szczuka [1] in 2009 and examine the connectedness of $P$, and the last theorem is another topological proof of the infinitude of primes, proven by Solomon Golomb [2] in 1959.

Section I: Notation and basic definitions

Notation. Let $a, b \in \Bbb{Z^{+}}$. $\{an + b\}$ will denote the set $\{an + b \mid n \in \Bbb{Z^{+}} \cup \{0\}\}$ and $\{an\}$ will denote the set $\{an\mid n \in \Bbb{Z^{+}}\}$. $(a, b)$ will denote the greatest common divisor of $a$ and $b$. Let $a \in \Bbb{Z^{+}}$ and $b \in \Bbb{Z}$. $\{az+b\}$ will denote the set $\{az + b\ \mid z \in \Bbb{Z^{+}}\}$.

Definition 1.1. Let $X$ be a space and let $x \in X$. If for each neighborhood, $U$ of $x$ there is some neighborhood $V$ of $x$ contained in $U$ and $V$ is connected, $X$ is locally connected at $x$. If for each $x \in X$, $X$ is locally connected at $x$ then $X$ is locally connected [3].

Definition 1.2. Let $\mathcal{A}$ $= \{\{az + b \} \mid a \in \Bbb{Z^{+}}, \ b \in \Bbb{Z}\}$. $\mathcal{A}$ is a basis for a topology on $\Bbb{Z}$ called the arithmetic progression topology or Furstenberg's topology. When $\Bbb{Z}$ is given Furstenberg's topology, we will denote it by $\Bbb{Z}_{F}$.

Remark 1.3. Hillel Furstenberg used $\mathcal{A}$ to show that there are infinitely many primes in 1955 while an undergraduate at Yashiva University where he majored in mathematics and divinity. Furstenberg currently resides in Israel and retired from a professorship at Hebrew University in Jerusalem in 2003 [4].

Theorem 1.4. (Dirichlet's theorem on arithmetic progressions). Let $\{an + b\} \in$ $\mathcal{A}$. If $a$ and $b$ are positive integers and coprime, there are infinitely many prime numbers in $\{an + b\}$.

Definition 1.5. Let $\mathcal{B}$ $= \{\{an + b \} \mid a, b \in \Bbb{Z}^{+},\ (a, b) = 1\}$. $\mathcal{B}$ is a basis for a topology on $\Bbb{Z}^{+}$ called Golomb's topology. When $\Bbb{Z}^{+}$ is given Golomb's topology, we will denote it by $\Bbb{Z}^{+}_{G}$.

Remark 1.6. In addition to giving a proof for the infinitude of primes with the space $\Bbb{Z}^{+}_{G}$ in 1959, Golomb also proved that the space $\Bbb{Z}^{+}_{G}$ is Hausdorff and connected in the same paper. Although, Golomb received his PhD in mathematics from Harvard where he focused on number theory and topology, he became interested in communications theory while working at the Glen L. Martin company and has made great contributions to information theory. For fun Golomb creates mathematical games and is the creator of pentomino, the inspiration for the classic video game, Tetris. He is currently a professor of electrical engineering at USC.

Definition 1.7. Let $x$ be an integer. $x$ is said to be square-free if the only perfect square $x$ is divisible by is $1$.

Definition 1.8. Let $\mathcal{B}' = \{\{an + b \} \mid a, b \in \Bbb{Z}^{+},\ (a, b) = 1,\ b < a,\ a\ \text{ is square-free}\}$. $\mathcal{B}$ is a basis for a topology on $\Bbb{Z}^{+}$ called Kirch's topology. When $\Bbb{Z}^{+}$ is given Kirch's topology, we will denote it by $\Bbb{Z}^{+}_{K}$. It should be noted that Golomb's topology is strictly finer than Girch's topology.

Section II: Theorems

Theorem 2.1 (Szczuka). The set of all prime numbers is disconnected in Golomb's and Kirch's topologies.

proof: Let $P$ be a subspace of $\Bbb{Z}^{+}_{K}$. $$\text{ Suppose }A_{1} = \{3n + 2\}\cup\{5n + 2\}\cup\{5n + 3\}\cup\{5n + 1\} \text{ and } B_{1} = \{15n + 4\}.$$ $A_{1}$ is a union of open sets in $\mathcal{B}'$, and $B_{1}$ is an element of $\mathcal{B}'$. Thus $A_{1}$ and $B_{1}$ are open in $\Bbb{Z}^{+}_{K}$. $A_{1}$ and $B_{1}$ are disjoint and both have infinitely many primes by Dirichlet's theorem, as $\{3n + 2\}\subset A_{1}$ and $\{15n + 4\}\subset B_{1}$ where $2, 3$ are coprime and $15, 4$ are coprime. Thus $A = A_{1}\cap P$ is non-empty and $B = B_{1}\cap P$ is non-empty since there are infinitely many primes in both $A_{1}$ and $B_{1}$. $A$ and $B$ are disjoint since $A_{1}$ and $B_{1}$ are disjoint. Note that $A$ and $B$ are open sets in $P$.

We will show that $A\cup B = P$ and $P$ is disconnected. $$\Bbb{Z}^{+} = A_{1} \cup B_{1} \cup \{15n + 9\} \cup \{15n + 10\}\cup\{15n\} \text{ which means }$$ $$P \cap \Bbb{Z}{+} = P\cap (A_{1}\cup B_{1}\cup\{15n + 9\}\cup\{15n + 10\}\cup\{15n\}) = P$$ Since $P\cap\{15n + 9\}$, $P\cap\{15n + 10\}$, and $P\cap\{15n\}$ are all empty sets, $P = (P\cap A_{1})\cup(P\cap B_{1})$ and $P = A\cup B$. Since $A$ and $B$ are non-empty and disjoint, they form a separation of $P$, and $P$ is disconnected as a subspace of $\Bbb{Z}^{+}_{K}$. Since the topology on $\Bbb{Z}^{+}_{G}$ is strictly finer than the topology on $\Bbb{Z}^{+}_{K}$, $P$ is disconnected as a subspace of $\Bbb{Z}^{+}_{G}$ [1].

Theorem 2.2 (Szczuka). The set of all prime numbers is locally connected in Furstenberg's topology.

proof: Let $P$ be a subspace of $\Bbb{Z}_{F}$. Let $p \in P$, and let $U$ be a neighborhood of $p$. There must be some set $\{az + b\} \in \mathcal{A}$ which is open in $P$, contains $p$, and is contained in $U$. Let $b = 0$ such that $\{pz\} \in \mathcal{A}$ and the only prime number in $\{pz\}$ is $p$. Thus $P\cap \{pz\} = \{p\}$, which is connected as a subspace of $P$ and also is an open set in $P$. Since $p \in \{p\} \subset U$, $P$ is locally connected at $p$, and hence $P$ is locally connected, as $P$ is locally connected for each $p \in P$ [1].

Theorem 2.3 (Szczuka).: The set of all prime numbers is not locally connected in Kirch's or Golomb's topologies.

proof: Let $P$ be a subspace of $\Bbb{Z}^{+}_{K}$. Suppose that $P$ is locally connected. $\{3n + 2\} \in \mathcal{B'}$ and $\{3n + 2\}\cap P$ is a non-empty open set in $P$ since it contains $2$. Since $P$ is locally connected there is a connected neighborhood of $2$, $H$ contained in $\{3n + 2\}\cap P$. Since $H$ is open, there is some set $\{an + b\}\cap P$ in $P$'s basis containing $2$ and contained in $H$. Since $\{an +b\} \in \mathcal{B'}$, $\{an +b\}$ must contain infinitely many prime numbers and $\{an + b\}\cap P$ contains infinitely many prime numbers.

Choose $p_{1} \in \{3n + 2\}\cap P$ such that $p_{1}$ does not equal $2$. $\{3n+1\} \in \mathcal{B'}$ and has infinitely many prime numbers, and we pick $p \in \{3n + 1\}$ such that $p$ is greater than $p_{1}$. Note that $p \not\in \{3n + 2\}$. $$\bigcup\limits_{k=1}^{p}\{pn + k\} = \Bbb{Z}^{+} \text{ and } P \cap \Bbb{Z}^{+} = P \text{ and } P\cap\bigcup\limits_{k=1}^{p}\{pn + k\} = P.$$ $$\{pn + p\}\cap\{3n + 2\} \text{ is empty, so } P\cap\{3n +2\} = P\cap(\bigcup\limits_{k=1}^{p-1}\{pn + k\})\cap\{3n + 2\}.$$ $$\text{Since } p_{1} < p\text{, }p_{1} \in \{pn + p_{1}\}\subset\bigcup\limits_{k=1}^{p - 1}\{pn + k\}\text{ and } 2 \in \{pn + 2\}\cap\bigcup\limits_{k=1}^{p - 1}\{pn + k\}.$$ Let $A = \{pn + p_{1}\}\cap\{3n + 2\}$. If $p_{1} = p - 1$ then let $$B = P\cap(\bigcup\limits_{k=1}^{p-2}\{pn + k\})\cap\{3n + 2\}$$ Otherwise, let $$B = P\cap ((\bigcup\limits_{k=1}^{p_{1} - 1}\{pn + k\} )\cup (\bigcup\limits_{j=p_{1} + 1}^{p - 1}\{pn + j\} ))\cap\{3n + 2\}$$ $A$ does not intersect $B$ and $p_1 \in A$ and $2 \in B$, so $A$ and $B$ are non-empty. Moreover, for each $k \in \Bbb{Z}^{+}$ such that $1 \leq k < p$, $\{pn + k\}\cap P$ is open in $P$ which means both $A$ and $B$ are open in $P$.

$A\cup B = P\cap\bigcup\limits_{k=1}^{p-1}(\{pn + k\})\cap\{3n + 2\} = P\cap\{3n + 2\}$ and $H \subset A \cup B$. Thus $A \cap H$ and $B \cap H$ are open in $H$ since $A$ and $B$ are open in $P$, and $A \cap H$ and $B \cap H$ are disjoint in $H$ since $A$ and $B$ are disjoint in $P$. $A \cap H$ contains $p_{1}$ since both $A$ and $H$ contain $p_{1}$ and $B \cap H$ contains $2$ since both $H$ and $B$ contain $2$. Thus $A \cap H$ and $B \cap H$ are non-empty and form a separation of $H$, a contradiction. Thus $P$ is not locally connected as a subspace of $\Bbb{Z}^{+}_{K}$. Since the topology on $\Bbb{Z}{+}_{G}$ is strictly finer than the topology on $\Bbb{Z}^{+}_{K}$, $P$ is not locally connected as a subspace of $\Bbb{Z}^{+}_{G}$ [1].

Theorem 2.4 (Euclid).: There are infinitely many prime numbers.

proof: Consider $\Bbb{Z}^{+}$ with Golomb's topology. Let $p \in P$. $\{pn\}$ is closed, as $\{pn\}$'s complement is $\bigcup\limits_{k=1}^{p-1}\{pn + k\}$ and open in $\Bbb{Z}^{+}_{G}$ since for each $\{pn + k\}$ such that $k \in \Bbb{Z}^{+} \text{ and } 1 \leq k \leq p-1$ is in $\mathcal{B}'$. Suppose $P$ is finite. $\Bbb{Z}^{+} - \{1\} = \bigcup\limits_{p \in P}\{pn\}$ must be closed, as it the the union of a finite number of closed sets in $\Bbb{Z}^{+}_{G}$. $\Bbb{Z}^{+} - \{1\}$'s complement is $\{1\}$, which is not open in $\Bbb{Z}^{+}_{G}$, as it is not infinite or empty. Thus $\Bbb{Z}^{+} - \{1\}$ cannot be closed and hence $\bigcup\limits_{p \in P}\{pn\}$ must be infinite and there must be infinitely many prime numbers [2].

[1] Paulina Szczuka, “The connectedness of arithmetic progressions in furstenbergs, golombs,and kirchs topologies,” Demonstratio Math, vol. 43, pp. 899–909, 2010.
[2] Solomon Golomb, “A connected topology for the integers,” The American Mathematical Monthly, vol. 66, pp. 663– 665, 1959.
[3] James R. Munkres, Topology. Prentice Hall, Inc., 2000.
[4] JJ O’Connor and EF Robertson, Hillel Furstenberg, 2010. Biographies/Furstenberg.html.
[5] Wikipedia, Solomon Golomb, 2015.

Sunday, January 23, 2011

Thanks After Midnight

I'd like to thank AM for linking up Ariel's footage and Wheels of the Future on their site. You can check out Ariel and the rest of the AM squad below in AM's newest clip. Enjoy!!

On a different note, I'm reading a great book right now about conscious and unconscious decision making. So definitely expect a new write-up about how skateboarding relates to the unconscious workings of the brain!

Monday, January 10, 2011

The Column

I'd like to give a special thanks to Steve Costello and Kevin Susienka for giving me a column on the RAW site. You can check out my first post here.

Also check out this classic Pete Gardini part. Move back to boston homie!

Wednesday, January 5, 2011

Thanks 48 Blocks!

There are a few skateboard websites in my bookmark bar that I check daily. 48 Blocks is one of these sites. While other sites only cover the industry heavy hitters, 48 Blocks keeps it real and covers many of the finer underground metropolitan skateboarders as well as established pros. They do this in the form of in-depth interviews and video spotlights. I want to thank 48 blocks for linking up Ariel's Wheels of the Future part on their site. A couple of years ago, 48 blocks made a great video featuring the likes of Lavar McBride and Nate Keegan called Pandemic. Enjoy!

Tuesday, January 4, 2011

I'm Going to be the One

Last spring and into the summer Ariel and I filmed a ton of "brocam" footage. If you've ever hung around Ariel you'll probably become familiar with many of his famous sayings. One of these sayings is, "I'm going to be the one." One man video parts are becoming all the rage and I figured I'd jump on the bandwagon. It only seemed appropriate that Ariel's one man part would be called, "I'm Going to be the One." What would an Ariel Part be without Max B? Enjoy!

Music: Max B-We Got Doe

Friday, December 31, 2010

A Skateboard Video Study on the Contrast Principle

Do you ride a skateboard? Do you often feel the need to ride it compulsively? Do you often daydream about skateboarding? If you answered 'yes' to any of these questions and are a full-blown skate rat, you may be eligible for participation in a skateboard video research study. Qualified applicants will be compensated in the form of the viewing of dope skate videos. Participants are needed immediately.

Instructions: Watch A and rate it on a scale of 1 to 10; with 10 being the best and 1 being the worst. Write this number down. Immediately watch B and rate it on a scale of 1 to 10. Write this number down. Wait 3 hours. Watch C and rate it on a scale of 1 to 10. Write this number down. Immediately watch D and rate it on a scale of 1 to 10 and write this number down. In the comments section, write down all 4 letters and your corresponding ratings to them. You can also leave your name if you want.

Thank You for your participation. Results will be published in a blog post in the near future. The goal of this study is to test out the contrast principle. For more information on the contrast principle look at the previous post.





Pscycophysics, Copley Square, and What to Do if You Get Bad Grades

Pretend you are a men's suit salesman. You have a customer who comes in and wants to buy a suit and a sweater. You want to sell him both a $500 suit and a $95 sweater. Which item would you show the customer first, in hopes that he would buy both? My guess is that you probably picked the sweater. You probably thought that if a person were to spend $500 on a suit first there would be no way the person would want to spend any more money on anything else. It turns out that it is much more profitable to sell the suit first and then the sweater. After someone has spent a huge chunk of money on an expensive item, the less expensive item relatively inexpensive compared to the more expensive item.

According to psychophysics is "the scientific study of the relationship between stimuli (specified in physical terms) and the sensations and perceptions evoked by these stimuli. The term psychophysics is used to denote both the substantive study of stimulus-response relationships and the methodologies used for this study."

There is a concept in psychophysics called the contrast principle. The contrast principle states that if we are presented two things one after another and these two things are somewhat different from each other we will perceive them as much more different than they actually are. For instance, suppose I ask you to pick up a light object and, right after, I ask you to pick up a heavier object. The heavier object will seem much heavier after picking up the lighter object than if I had just asked you to pick up the heavier object without first picking up the lighter one. The contrast principle not only applies to weight; it also has great psychological implications.

Consider this experiment from the Universities of Montana and Arizona. College students were shown a picture of a potential blind date. One group of the students were shown an episode of Charlie's Angels while viewing the pictures and another group of students weren't. The group of students watching the episode of Charlie's Angels gave a much lower rating of the potential blind date picture than the students who didn't. This is probably because of the highly unrealistic beauty of the Charlie's Angels cast.

The contrast principle holds tremendous power. It is extremely easy to exploit the principle as shown in the men's suit example. When any retail business uses the principle, it is extremely hard for customers to detect it. For all you skate shop owners do yourself a favor and sell those $100 dunks and then the $30 premium collaboration tee-shirt. In fact, it is not only more profitable to sell the more expensive item first; it would be detrimental to sell the less expensive item first (That is, if your goal is to make money). Suppose you sold someone that $30 tee-shirt and then tried to sell him the $100 dunks. The tee-shirt probably seemed pretty expensive on its own, but then being presented with a pair of much more expensive dunks just makes the dunks seem even more costly and the customer would be less likely to buy them. Order of sales matters.

At this time of year, everyone loves going to skate the Copley fountain in Boston. It's a fun little ledge and manny pad that's about 8 inches high. Let's pretend you just learned nose manny nollie flips and you're hyped. Tourists love to go to the fountain and watch the skateboarders. In fact, they are probably judging your ability levels. Suppose you're the only one there and Daewon Song ( rolls up. Unsurprisingly, people will probably think you suck and Daewon is the norm on a skateboard. This is the contrast principle in action.

Finally, if you ever get bad grades in school, send this letter (an extreme example of the contrast principle taken directly out of Influence The Pschology of Persausion by Robert B. Cialdini):

"Dear Mother and Dad,

It has been nearly three months since I left for college. I have been remiss in writing, and I am very sorry for my thoughtlessness in not having written before. I will bring you up to date now; but, before you read on, please sit down. You are not to read any further unless you are sitting down. Okay.

Well, then, I am getting along pretty well now. The skull fracture and the concussion I got when I jumped out of the window of my dormitory when it caught fire shortly after my arrival are pretty well healed now. I only spent two weeks in the hospital, and now I can see almost normally and only get those sick headaches once a day.

Fortunately, the fire in the dormitory and my jump were witnessed by an attendant at the gas station near the dorm, and he was the one who called the Fire Department and the ambulance. He also visited me at the hospital; and, since I had nowhere to live because of the burnt out dormitory, he was kind enough to invite me to share his apartment with him. It's really a basement room, but it's kind of cute. He is a very fine boy, and we have fallen deeply in love and are planning to get married. We haven't set the exact date yet, but it will be before my pregnancy begins to show.

Yes, Mother and Dad, I am pregnant. I know how much you are looking forward to being grandparents, and I know you will welcome the baby and give it the same love and devotion you gave me when I was a child. The reason for the delay in our marriage is that my boyfriend has some minor infection which prevents us from passing our premarital blood tests, and I carelessly caught it from him. This will soon clear up with the penicillin injections I am now taking daily.

I know you will welcome him into our family with open arms. He is kind; and, although not well educated, he is ambitious. Although he is of a different race and religion than ours, I know your oft-expressed tolerance will not permit you to be bothered by the fact that his skin color is somewhat darker than ours. I am sure you will love him as I do. His family background is good too, for I am told that his father is an important gun bearer in the village in Africa from which he comes.

Now that I have brought you up to date, I want to tell you that there was no dormitory fire, I did not get a concussion or a skull fracture, I was not in the hospital, I am not pregnant, I am not engaged, I do not have syphilis, and there is no one in my life. However, I am getting a "D" in History and an "F" in Science, and I wanted you to see these marks in the proper perspective.

Your loving daughter,


Sharon may be failing chemistry, but she gets an "A" in psychology"

Source: Influence The Pschology of Persuasion by Richard B. Cialdini