Showing posts with label topology. Show all posts
Showing posts with label topology. Show all posts
06 December 2011
29 March 2008
Furstenberg's topological proof of the infinitude of primes
I just learned about Furstenberg's proof of the infinitude of primes (link goes to Wikipedia article); it was published in 1955 in the American Mathematical Monthly. (Link goes to JSTOR. Full citation: The American Mathematical Monthly, Vol. 62, No. 5. (May, 1955), p. 353. If you have to do any work to get the article from JSTOR -- for example, logging in through a proxy server because you're at home instead of on campus -- or you don't have JSTOR access -- don't worry, you're not missing much. The article's a third of a page, and the Wikipedia article is probably longer than Furstenberg's original.) Surprisingly, I hadn't seen this before.
Anyway, here's my version of the proof: topologize the integers by taking the (doubly infinite) arithmetic sequences as a basis. (The only thing that needs checking here, to show these form a basis, is that the nonempty intersection of two basis elements contains a basis element; this is true since the intersection of two arithmetic sequences is another arithmetic sequence.) Consider the set which consists of all the integers except -1 and 1; this is the union of the sequences pZ over all primes. Now, there are no nonempty finite open sets in this topology, so there are no cofinite closed sets except Z itself. Thus the union of the pZ isn't closed. So it can't be an union of finitely many closed sets, since finite unions of closed sets are closed. So there are infinitely many sets pZ, and thus infinitely many primes!
(Thanks to an anonymous commentator for pointing out some errors.)
Anyway, here's my version of the proof: topologize the integers by taking the (doubly infinite) arithmetic sequences as a basis. (The only thing that needs checking here, to show these form a basis, is that the nonempty intersection of two basis elements contains a basis element; this is true since the intersection of two arithmetic sequences is another arithmetic sequence.) Consider the set which consists of all the integers except -1 and 1; this is the union of the sequences pZ over all primes. Now, there are no nonempty finite open sets in this topology, so there are no cofinite closed sets except Z itself. Thus the union of the pZ isn't closed. So it can't be an union of finitely many closed sets, since finite unions of closed sets are closed. So there are infinitely many sets pZ, and thus infinitely many primes!
(Thanks to an anonymous commentator for pointing out some errors.)
22 March 2008
When are two algorithms the same?
When Are Two Algorithms The Same?, by Andreas Blass, Nachum Dershowitz, and Yuri Gurevich. Via Lambda the Ultimate and Anarchaia.
My first thought here -- and this is unusual for me, since I'm basically a discrete mathematician -- is that maybe the space of programs is "effectively continuous", in the same sense, that, say, reality is "effectively continuous" but actually has a discrete nature if you look closely enough, thanks to quantum physics. So the right thing to do would be to topologize the set of programs, so you can say that algorithms X and X' are "close to" each other, or perhaps to put a metric on it. But I naturally imagine that, say, if two programs differ by some small number of small changes then they would have to be considered the "same program" if we were looking for an equivalence relation. Imagine a graph whose vertices are programs, and two programs are connected by an edge if they differ by some small number of small changes; then we're naturally led to think of "algorithms" (if they are equivalence classes of programs) as connected components of that graph. But how do we decide what number of changes to allow, or how large they can be? Basically, the relation on the set of programs "expresses the same algorithm" doesn't seem to be transitive, as the authors point out, so "equivalence relation" is the wrong idea.
By the way, I speculate that calling the space of programs a metric space (say, with the metric induced from the graph I alluded to before) is wrong as well, but in a different way -- how does one assign lengths to the edges? That seems a bit subjective and squishy. Topology's the way to go here, although it's not like anybody's holding their breath waiting for an answer to this question. And it sort of feels like a question about moduli spaces (link goes to a post by Jordan Ellenberg), although I know next to nothing about those.
This reminds me (and the authors) of the question asked in Tim Gowers' post when are two proofs essentially the same. (In fact, is this the same question?)
People usually regard algorithms as more abstract than the programs that implement them. The natural way to formalize this idea is that algorithms are equivalence classes of programs with respect to a suitable equivalence relation. We argue that no such equivalence relation exists.
My first thought here -- and this is unusual for me, since I'm basically a discrete mathematician -- is that maybe the space of programs is "effectively continuous", in the same sense, that, say, reality is "effectively continuous" but actually has a discrete nature if you look closely enough, thanks to quantum physics. So the right thing to do would be to topologize the set of programs, so you can say that algorithms X and X' are "close to" each other, or perhaps to put a metric on it. But I naturally imagine that, say, if two programs differ by some small number of small changes then they would have to be considered the "same program" if we were looking for an equivalence relation. Imagine a graph whose vertices are programs, and two programs are connected by an edge if they differ by some small number of small changes; then we're naturally led to think of "algorithms" (if they are equivalence classes of programs) as connected components of that graph. But how do we decide what number of changes to allow, or how large they can be? Basically, the relation on the set of programs "expresses the same algorithm" doesn't seem to be transitive, as the authors point out, so "equivalence relation" is the wrong idea.
By the way, I speculate that calling the space of programs a metric space (say, with the metric induced from the graph I alluded to before) is wrong as well, but in a different way -- how does one assign lengths to the edges? That seems a bit subjective and squishy. Topology's the way to go here, although it's not like anybody's holding their breath waiting for an answer to this question. And it sort of feels like a question about moduli spaces (link goes to a post by Jordan Ellenberg), although I know next to nothing about those.
This reminds me (and the authors) of the question asked in Tim Gowers' post when are two proofs essentially the same. (In fact, is this the same question?)
23 February 2008
links for 2008-02-23
From A neighborhood of infinity: What is topology?, attempting to provide some intuition for the standard axioms that define a topology in terms of "observable sets" (which are just open sets, with different intuition attached to them!)
Also, on a totally unrelated note: John Baez has online notes from the course he gave in Fall '03, Winter '04, Spring '04. The winter notes are particularly interesting to me, because they combine combinatorics (which I know well) and a lot of category-theoretic notions that I'm not too familiar with.
Also, on a totally unrelated note: John Baez has online notes from the course he gave in Fall '03, Winter '04, Spring '04. The winter notes are particularly interesting to me, because they combine combinatorics (which I know well) and a lot of category-theoretic notions that I'm not too familiar with.
21 February 2008
Politics and winding numbers
Confusion about the changing positions of political parties in the U.S., from Andrew at Statistical Modeling, Causal Inference, and Social Science.
There are fairly standard models that allow one to plot political opinions in a two-dimensional "issue space", with the two dimensions being roughly "social" and "economic"; the two-party system dictates that these essentially get projected down to a single dimension. The post alludes to them, and refers to an argument that the Democrats and Republicans may have switched positions in the last century or so via a rotation of 180 degrees in this space. (As counterintuitive as it seems given the current ideological stances of the major parties, the Republicans started out as the anti-slavery party.) Andrew is not convinced -- the argument seems to rely on an assumption that states remain constant in their political leanings, which isn't true -- but it at least seems like something that could happen.
So in another century, could the parties rotate all the way around and get back where they started? And if the alignment of the two major parties in issue space in 2100 ends up being the same as that in 1900, is it more likely to happen by the rotation continuing in the direction it's going, or by reversal? This is basically a question about winding numbers, in a sense I really don't want to make precise because it's kind of silly.
There are fairly standard models that allow one to plot political opinions in a two-dimensional "issue space", with the two dimensions being roughly "social" and "economic"; the two-party system dictates that these essentially get projected down to a single dimension. The post alludes to them, and refers to an argument that the Democrats and Republicans may have switched positions in the last century or so via a rotation of 180 degrees in this space. (As counterintuitive as it seems given the current ideological stances of the major parties, the Republicans started out as the anti-slavery party.) Andrew is not convinced -- the argument seems to rely on an assumption that states remain constant in their political leanings, which isn't true -- but it at least seems like something that could happen.
So in another century, could the parties rotate all the way around and get back where they started? And if the alignment of the two major parties in issue space in 2100 ends up being the same as that in 1900, is it more likely to happen by the rotation continuing in the direction it's going, or by reversal? This is basically a question about winding numbers, in a sense I really don't want to make precise because it's kind of silly.
26 January 2008
Are you living with Third Dimensia?
Are you living with Third Dimensia?, from the Institute for Additional Dimension Adjustment Therapy.
I know, I know, you're a three-dimensional person. (Or are you? On the Internet, nobody knows you're a pancake. Or Kansas.) But we're told that doesn't matter:
Try as I might, though, I couldn't find a reference on that site to my favorite fact about two-dimensional life -- namely that their digestion must work differently from ours, because topologically they are unable to have a digestive tract. Presumably they'd absorb nutrients through the skin, like unicellular life forms in our world do. I suspect larger 2-D life forms would have fractal surfaces, to get a large surface-area-to-volume ratio, similarly to how we have branching networks of blood vessels so that oxygen can get to all our tissues. This is one thing that Edwin Abbott Abbott got wrong.
I know, I know, you're a three-dimensional person. (Or are you? On the Internet, nobody knows you're a pancake. Or Kansas.) But we're told that doesn't matter:
Up until the late 1990s, it was commonly thought that 3rd Dimensia was only a disorder for patients dealing with 2-to-3-dimensional crossover. But today, scientists and doctors know better. Be warned: 3rd Dimensia does not discriminate. It can strike anyone at anytime.One of the diagnostic questions is "Do you settle for just jumping over objects and projectiles?" -- I suspect that part of the reason video game characters can jump so high is because in two dimensions there is only one horizontal dimension, so the more realistic option of swerving around an oncoming enemy simply isn't available to them. If this is so, then I'd suspect characters in 3-D games can't jump as high (relative to their body height) as those in 2-D games; at some point the designers should have realized that real people don't jump that high, and designers probably feel more constrained by real physics in 3-D games than in 2-D games.
Try as I might, though, I couldn't find a reference on that site to my favorite fact about two-dimensional life -- namely that their digestion must work differently from ours, because topologically they are unable to have a digestive tract. Presumably they'd absorb nutrients through the skin, like unicellular life forms in our world do. I suspect larger 2-D life forms would have fractal surfaces, to get a large surface-area-to-volume ratio, similarly to how we have branching networks of blood vessels so that oxygen can get to all our tissues. This is one thing that Edwin Abbott Abbott got wrong.
20 November 2007
A Mobius strip video
A video about the Mobius strip, with an interesting choice of background music.
This video illustrates certain classical facts about the Mobius strip:
- if you draw a line down the middle of the Mobius strip, it runs down "both sides" of it (by which I mean both sides of the original sheet of paper; the Mobius strip isn't orientable)
- if you cut along that line, you end up with a long twisted strip;
- if you cut along a line one-third of the way from one of the edges of the original strip of paper to the other, you get two linked strips, of equal thickness but different lengths;
and another fact I didn't know:
- if you cut along a line one-quarter of the way from one of the original edges to the other, you get three linked strips (I assume at least one of them is Mobius), but now one is twice as wide as the other two. (But I think there's something trickier going on with the cutting here; it's hard to get a good look.)
Also, breaking the underwater one-handed Rubik's-cube-solving record. I can't make this stuff up.
(These are both from is from sciencehack, which is a site for science videos that claims that "every science video on ScienceHack is screened by a scientist to verify its accuracy and quality". Apparently they don't host the videos; they just index other people's science-related videos.) Here is their index of mathematics videos.0
This video illustrates certain classical facts about the Mobius strip:
- if you draw a line down the middle of the Mobius strip, it runs down "both sides" of it (by which I mean both sides of the original sheet of paper; the Mobius strip isn't orientable)
- if you cut along that line, you end up with a long twisted strip;
- if you cut along a line one-third of the way from one of the edges of the original strip of paper to the other, you get two linked strips, of equal thickness but different lengths;
and another fact I didn't know:
- if you cut along a line one-quarter of the way from one of the original edges to the other, you get three linked strips (I assume at least one of them is Mobius), but now one is twice as wide as the other two. (But I think there's something trickier going on with the cutting here; it's hard to get a good look.)
Also, breaking the underwater one-handed Rubik's-cube-solving record. I can't make this stuff up.
(These are both from is from sciencehack, which is a site for science videos that claims that "every science video on ScienceHack is screened by a scientist to verify its accuracy and quality". Apparently they don't host the videos; they just index other people's science-related videos.) Here is their index of mathematics videos.0
13 September 2007
the Bananach-Tarski paradox
From Courtney Gibbons' Brown Sharpie: the Bananach-Tarski theorem. This tells us that a banana can, through some sort of magic, be made into two bananas.
This is of course a restatement of the Banach-Tarski theorem, which tells us that a solid ball can be partitioned into finitely many non-overlapping subsets, which can then be rearranged to form two balls each of the same size as the original ball.
Of course, you couldn't do this with actual bananas (even though a topologist can't tell a banana from an orange, or a doughnut from a coffee cup, or eir pants from a hole in the ground). Damn atoms.
What other fruit-related math jokes are there? The only one I can think of is "What's purple and commutes? An abelian grape," which barely qualifies as a joke.
I found the Bananach-Tarski paradox via the Facebook group I support the right to choose one element from each set in a collection, which asks:
Finally, because this blog is at least nominally about probability: imagine a (randomized) algorithm that outputs a string of letters as follows: start with any three letters a1, a2, a3. Then for each n > 3, consider some corpus of English text, and consider all the occurrences of the string an-3 an-2 an-1 in that corpus. Tabulate the distribution of the letter that follows that string in the corpus. Choose an from that distribution.
I don't have the programming skills or the corpus to work from, but I bet there's a significant chance that if you start with BAN you get BANANANANANA...
This is of course a restatement of the Banach-Tarski theorem, which tells us that a solid ball can be partitioned into finitely many non-overlapping subsets, which can then be rearranged to form two balls each of the same size as the original ball.
Of course, you couldn't do this with actual bananas (even though a topologist can't tell a banana from an orange, or a doughnut from a coffee cup, or eir pants from a hole in the ground). Damn atoms.
What other fruit-related math jokes are there? The only one I can think of is "What's purple and commutes? An abelian grape," which barely qualifies as a joke.
I found the Bananach-Tarski paradox via the Facebook group I support the right to choose one element from each set in a collection, which asks:
Do you believe that an infinite product of nonempty sets should be nonempty? Do you feel that non-measurable subsets of the reals should exist? Or games of perfect information with no winning strategy for either player? Do you believe that every set should have a well-ordering, or that any poset in which every chain has an upper bound is entitled to a maximal element? Do nonzero rings have the right to a maximal ideal? Is every vector space entitled to a basis? Should fields have algebraic closures? Should products of compact topological spaces be compact, and countable unions of countable sets be countable? Do you want to be able to cut a sphere up into a finite number of pieces and reassemble them, with only rigid motions, into a sphere twice as large?
Finally, because this blog is at least nominally about probability: imagine a (randomized) algorithm that outputs a string of letters as follows: start with any three letters a1, a2, a3. Then for each n > 3, consider some corpus of English text, and consider all the occurrences of the string an-3 an-2 an-1 in that corpus. Tabulate the distribution of the letter that follows that string in the corpus. Choose an from that distribution.
I don't have the programming skills or the corpus to work from, but I bet there's a significant chance that if you start with BAN you get BANANANANANA...
18 July 2007
what is the shape of a Moebius strip?
Loopy Logic: Moebius Strip Riddle Solved at Last, from Seed Magazine; also from Scientific American.
Who hasn't heard of the Mobius strip? The Mobius strip is the thing you get if you take a strip of paper, twist one of its ends half a twist, and tape the two ends together. It has the incredibly counterintuitive property that it only has one "side" -- if you were an ant, say, walking along the surface of such a strip, you could walk and walk and walk and suddenly you'd be where you were before but on what you'd think of as the "other side".
The article linked to -- which seems to be derived from a press release as I've found it in a few other places -- says that:
This seems a bit surprising -- it's easy to write down an equation that parametrizes the Mobius surface as basically a thickened circle. If you go to nature.com's writeup of it, though, it begins to make sense. What it actually means is that if you build a model of the Mobius strip out of an actual piece of paper or some other foldable material, the actual shape it will take is difficult to predict. This is what Eugene Starostin and Gert van der Heijden have actually done.
The difference here, then, is that when I hear "Mobius strip" I think of some sort of Platonic object, floating there in space, which could be realized in any material and is not subject to the laws of physics but only the laws of geometry, whereas the vast majority of people picture a piece of paper which has been twisted.
By the way, you can read some quasi-mystical stuff about the Mobius strip at Mobius Products and Services. As far as I know the Mobius strip has nothing to do with the Mobius transformation other than that the same person came up with both of them. But the legitimate journalists are subject to this mysticalism too -- nature.com points out that the Moebius strip, when viewed from a certain angle, looks like ∞, the sign for infinity.
Who hasn't heard of the Mobius strip? The Mobius strip is the thing you get if you take a strip of paper, twist one of its ends half a twist, and tape the two ends together. It has the incredibly counterintuitive property that it only has one "side" -- if you were an ant, say, walking along the surface of such a strip, you could walk and walk and walk and suddenly you'd be where you were before but on what you'd think of as the "other side".
The article linked to -- which seems to be derived from a press release as I've found it in a few other places -- says that:
Since 1930, the Moebius strip has been a classic poser for experts in mechanics. The teaser is to resolve the strip algebraically--to explain its unusual shape in the form of an equation.
This seems a bit surprising -- it's easy to write down an equation that parametrizes the Mobius surface as basically a thickened circle. If you go to nature.com's writeup of it, though, it begins to make sense. What it actually means is that if you build a model of the Mobius strip out of an actual piece of paper or some other foldable material, the actual shape it will take is difficult to predict. This is what Eugene Starostin and Gert van der Heijden have actually done.
The difference here, then, is that when I hear "Mobius strip" I think of some sort of Platonic object, floating there in space, which could be realized in any material and is not subject to the laws of physics but only the laws of geometry, whereas the vast majority of people picture a piece of paper which has been twisted.
By the way, you can read some quasi-mystical stuff about the Mobius strip at Mobius Products and Services. As far as I know the Mobius strip has nothing to do with the Mobius transformation other than that the same person came up with both of them. But the legitimate journalists are subject to this mysticalism too -- nature.com points out that the Moebius strip, when viewed from a certain angle, looks like ∞, the sign for infinity.
Subscribe to:
Posts (Atom)
