Thomson’s Lamp and Determinism (Supertasks II)

In our previous post, we began a discussion of supertasks, or processes with infinitely many steps that are completed in a finite amount of time. Today, we visit the source of the word supertask (or, in its original formulation, super-task), J.F. Thomson’s 1954 paper, “Tasks and Super-tasks”, published in Analysis.

The main thesis of Thomson’s paper is that supertasks are paradoxical, that it is impossible for someone to have completed an infinite sequence of tasks. (He is careful to distinguish between (1) completing an infinite sequence of tasks, which he thinks is impossible and (2) having an infinite number of tasks that one can potentially do. This is essentially the classical distinction between actual and potential infinity that we have discussed here a number of times.)

To illustrate the impossibility of supertasks, Thomson introduces a particular supertask, now known as Thomson’s Lamp. The idea is as follows: Suppose we have a lamp with a button on its base. If the lamp is off, then pressing the button turns it on; if it is on, then pressing the button turns it off. You have probably encountered such a lamp at some point in your life. Now imagine the following sequence of actions. The lamp is initially off. After one second, I press the button to turn it on. After a further 1/2 second, I press the button again to turn it off. After a further 1/4 second, I press the button to turn it on. After a further 1/8 second, I press the button to turn it off. And so on. (As in our last post, we are ignoring the obvious physical impossibilities of this situation, such as the fact that my finger would eventually be moving faster than the speed of light or that the wires in the lamp would become arbitrarily hot.) In the course of 2 seconds, I press the button infinitely many times. Moreover, there is no “last” button press; each press is quickly followed by another. So the question is this: after 2 seconds, is the lamp on or off? Thomson feels that either answer is impossible, and yet one of them must hold:

It cannot be on, because I did not ever turn it on without at once turning it off. It cannot be off, because I did in the first place turn it on, and thereafter I never turned it off without at once turning it on. But the lamp must be either on or off. This is a contradiction.

Thomson concludes that supertasks are impossible. (I am oversimplifying a little bit here; I encourage interested readers to check out Thomson’s original paper, which is fairly short and well-written.) As anyone passingly familiar with the history of philosophy could guess, though, not everybody was convinced by Thomson’s arguments, and Thomson’s paper initiated a small but lively philosophical discussion on supertasks, some of which we may examine in future posts.

Today, though, I don’t want to focus directly on the possibility of supertasks in general or Thomson’s Lamp in particular, but rather to assume that they are possible and think about what this would mean for a topic of great interest in philosophy: determinism.

Roughly speaking, determinism is the assertion that all events are uniquely determined by what has happened before. Given the history of the universe, its future is fixed in stone. The first modern expression of this type of determinism is typically credited to the French mathematician Pierre-Simon Laplace, who imagined the existence of a demon who knows the precise location and momentum of every object in the universe and is therefore able to calculate all future events.

Determinism is a vast subject, and we don’t have nearly enough time to touch on its many connections with topics such as religion, free will, or quantum mechanics. We do have time, however, to show that Thomson’s Lamp, plus a bit of intuition (always dangerous when dealing with infinity, but let’s allow it for the sake of argument), places serious doubt on the truth of determinism.

To see this, let’s suppose that the supertask of Thomson’s Lamp is in fact coherent, and let’s revisit the question: after 2 seconds, is the lamp on or off? I claim that either answer is possible. To see this, let’s be a little bit more precise. Let’s call our supertask, in which the lamp starts off and we press the button infinitely many times in 2 seconds, Process A. Suppose my claim is wrong and that, at the conclusion of Process A, the lamp is necessarily on (if the lamp is necessarily off, then a symmetric argument will work). Now imagine that Process B is the same as Process A but with the role of “on” and “off” reversed: the lamp starts on and, over the course of 2 seconds, we press the button infinitely many times. One would expect that the final state of Process B would just be the reverse of the final state of Process A, namely that the lamp is necessarily off at the conclusion of Process B. (If this doesn’t seem intuitively obvious to you, try imagining a more symmetric situation in which the switch doesn’t turn the lamp on or off but instead switches the color of light emitted from red to blue.) But now suppose that an observer arrives at Process A exactly 1 second late and thus misses the first press of the button. From their perspective, the remainder of the supertask looks exactly like Process B, just sped up by a factor of two. This speeding up intuitively shouldn’t affect the final outcome, so they should rightly expect the lamp to be off at the end of the process, whereas I should rightly expect the lamp to be on at the end of the process, since I know we are completing Process A. We can’t both be correct, so this is a contradiction.

But if, at the end of the supertask, the lamp could consistently either be on or off, then the state of the lamp after two seconds is not uniquely determined by past events. Laplace’s demon cannot predict the behavior of the lamp after two seconds, even if it knows everything about the universe at all times before two seconds have elapsed. In other words, if we accept the coherence of Thomson’s lamp, then determinism must be false!


This was admittedly a very non-rigorous argument, but I hope it provides some food for thought or at least some amusement. Next time, we’ll return to doing some real mathematics and connect ideas of supertasks with the values of infinite series!

Cover image: “L’empire des lumières” by René Magritte

Advertisements

Infinite Collisions, or Something from Nothing (Supertasks I)

Hello! It’s been over a year since my last post; I took some time off as I moved to a new city and a new job and became generally more busy. I missed writing this blog, though, and recently I found myself reading about supertasks, tasks or processes with infinitely many steps but which are completed in a finite amount of time. This made the finitely many things I was doing seem lazy by comparison, so I think I’m going to try updating this site regularly again.

The first supertasks were possibly those considered by Zeno in his paradoxes of motion (which we’ve thought about here before). In the simplest, Achilles is running a 1 kilometer race down a road. To complete this race, though, Achilles must first run the first 1/2 kilometer. He must then run the next 1/4 kilometer, and then the next 1/8 kilometer, and so on. He must seemingly complete an infinite number of tasks just in order to finish the race.

Zeno_Dichotomy_Paradox
Achilles running a race. (Image by Martin Grandjean, CC BY-SA 4.0)

If this idea leaves you a bit confused, you’re not alone! It seems that the same idea can be applied to any continuous process; first half of the process must take place, then the next quarter, then the next eighth, and so on. How does anything ever get done? Is every task a supertask?

Supertasks reemerged as a topic of philosophical study in the mid-twentieth century, when J.F. Thomson introduced both the term supertask and a new example of a supertask, now known as Thomson’s Lamp: Imagine you have a lamp with an on/off switch. Now imagine that you switch the lamp on at time t = 0 seconds. After 1/2 second, you switch the lamp off again. After a further 1/4 second, you switch the lamp on again. After a further 1/8 second, you switch the lamp off again, and so on. After 1 full second, you have switched the lamp on and off infinitely many times. Now ask yourself: at time t = 1, is the lamp on or off? Is this even a coherent question to ask?

We’ll have more to say about this and other supertasks in future posts, but today I want to present a particularly elegant supertask introduced by Jon Perez Laraudogoitia in the aptly named paper “A Beautiful Supertask”, published in the journal Mind in 1996. Before describing the supertask, let me note that it will obviously not be compatible with our physical universe, or perhaps any coherent physical universe, for a number of reasons: it assumes perfectly elastic collisions with no energy lost (no sound or heat created, for instance), it assumes that particles with a fixed mass can be made arbitrarily small, it assumes that nothing will go horribly wrong if we enclose infinitely much matter in a bounded region, and it neglects the effects of gravity. Let’s put aside these objections for today, though, and simply enjoy the thought experiment.

Imagine that we have infinitely objects, all of the same mass. Call these objects m1, m2, m3, and so on. They are all arranged on a straight line, which we’ll think of as being horizontal. To start, each of these objects is standing still. Object m1 is located 1 meter to the right of a point we will call the origin, object m2 is 1/2 meter to the right of the origin, object m3 is 1/4 meter to the right of the origin, and so on. (Again, we’re ignoring gravity here. Also, so that we may fit these infinitely many objects in a finite amount of space, you can either assume that they are point masses without dimension or you can imagine them as spheres that get progressively smaller (but retain the same mass) as their index increases.) Meanwhile, another object of the same mass, m0, appears to the right of m1, moving to the left at 1 meter per second. At time t = 0 seconds, it collides with m1.

beautiful_supertask
Our system immediately before t = 0.

What happens after time t = 0? Well, since we’re assuming our collisions are perfectly elastic, m0 transfers all of its momentum to m1, so that m0 is motionless 1 meter from the origin and m1 is moving to the left at 1 meter per second. After a further half second, at t = 1/2, m1 collides with m2, so that m1 comes to rest 1/2 meter from the origin while m2 begins moving to the left at 1 meter per second. This continues. At time t = 3/4, m2 collides with m3. At time t = 7/8, m3 collides with m4, and so on.

Where are we after 1 full second? By time t = 1, each object has been hit by the previous object and has in turn collided with the next object. m0 is motionless where m1 started, m1 is motionless where m2 started, m2 is motionless where m3 started, and so on. Our entire system is at rest. Moreover, compare the system {m0, m1, m2, …} at t=1 to the system {m1, m2, m3, …} at t=0. They’re indistinguishable! Our initial system {m1, m2, m3, …} has absorbed the new particle m0 and all of its kinetic energy and emerged entirely unchanged!

Things become seemingly stranger if we reverse time and consider this process backwards. We begin with the system {m0, m1, m2, …}, entirely at rest. But then, at t = -1, for no apparent reason, a chain reaction of collisions begins around the origin (“begins” might not be quite the right terms — there’s no first collision setting it all off). The collisions propagate rightward, and at t = 0 the system spits out particle m0, moving to the right at 1 meter per second, while the system {m1, m2, m3, …} is now identical to the system {m0, m1, m2, …} at time t = -1. The ejection of this particle from a previously static system is an inexplicable event. It has no root cause; each collision in the chain was caused by the one before it, ad infinitum. A moving object has seemingly emerged from nothing; kinetic energy has seemingly been created for free.


Cover Image: “4 Spheres” by Victor Vasarely

Introducing The Humming of the Strings

Hello! I’m sorry that I haven’t been around much in the last few months, which have been rather busy for me. I’m hoping to continue more regular posting now, though, starting with the announcement of a new project: Point at Infinity‘s first spin-off blog, The Humming of the Strings.

Loyal readers will remember a few posts here on Point at Infinity about music. We had a post about the Shepard tone, an aural illusion that seems to perpetually rise in pitch, two posts about the Risset rhythm, the Shepard tone’s rhythmic cousin, and a post about Euclidean rhythms and their surprising connections with nuclear physics, computer graphics, and the Hebrew calendar. These were among the most enjoyable posts for me to write, and some of them were among the favorites of readers as well. Mathematics and music are two passions of mine, and there is a vast field of ideas to explore here, many of which don’t necessarily fit here on Point at Infinity. This is why I’m starting The Humming of the Strings, to provide a place for more in-depth exploration of musical topics that might be out of place here.

There is another, more technical reason for this blog. Over the last couple of years, I’ve sporadically been playing around with SuperCollider, an audio synthesis platform and programming language. It is a wonderful tool for exploring the connections between math and music, and I plan on using it to create music and audio samples for The Humming of the Strings, and on sharing what I learn in this process with the readers. I’m hoping that the details of the computer programming will be of interest to some readers, and I will try to make it as unintrusive as possible for those readers not interested in it. (I’m anticipating that most posts will consist of a non-technical body section followed by a technical appendix with details of the code.)

I hope you will join me over at The Humming of the Strings. I will likely primarily be posting there rather than here in the near future, though there may be some new content on Point at Infinity from time to time. Thanks for reading, and Happy New Year!

Cantor v. Crank

No one shall expel us from the paradise that Cantor has created for us.

-David Hilbert

To the extent that a mathematical theorem can be considered controversial, Cantor’s Theorem has historically been quite a controversial statement. The theorem, which, we remind you, states that, for any set A, the power set \mathcal{P}(A), which consists of all subsets of A, is strictly larger than A (or, in a commonly cited special case, the set of all real numbers, \mathbb{R}, is strictly larger than the set of all natural numbers, \mathbb{N}), was attacked by a number of Cantor’s illustrious contemporaries, among them Kronecker and Poincaré, who objected to Cantor’s manipulation of infinite sets as mathematical objects in their own right.

Cantor’s work also had prominent defenders, though, most notably David Hilbert, whose quote in the header of this post has become among the most iconic proclamations in modern mathematics. As mathematicians settled into the twentieth century, Cantor’s Theorem and the field of set theory that it helped establish became widely accepted in the community. Today, it is safe to say that Cantor’s Theorem is uncontroversial among the vast majority of mathematicians. Resistance to the theorem or to its extrapolations has not died out, though; it remains present in certain pockets of mathematics, such as ultrafinitism, in some philosophy departments, and among amateur mathematicians. Today, we will look at an example from this last category.


In 1974, the Transactions of the Wisconsin Academy of Sciences, Arts, and Letters published an article by engineer William Dilworth, “A Correction in Set Theory,” in which Dilworth claims to “present an analysis, made possible by modern semantics, of a central fallacy in Cantor’s theory.” The paper is not good, and it should not have been published, but before we jump to excoriate the editors of the journal, we should note a historical fact about science in America. In the 1800s, professors in public colleges and universities, especially in the midwestern and western states, were often academically isolated, not really able to talk to any colleagues at their institutions about their work. State-run academies, such as the Wisconsin Academy of Sciences, Arts, and Letters, sprung up to help these academics communicate with one another. In the twentieth century, though, more specialized national and international academic associations were formed, and more focused academic journals proliferated, and communication became progressively easier, so these state academies became less and less relevant. Certainly by 1974, the Transactions of the Wisconsin Academy of Sciences, Arts, and Letters was not attracting many high-quality submissions (at least in mathematics; I don’t presume to judge the quality of publications in agricultural science or literary criticism), and perhaps published nearly everything it received as a result. The journal had outlived its purpose, but it hung on until 2001, when its final issue was released.

Let us turn now to Dilworth’s paper. The impetus for the work appears to be Dilworth’s displeasure with the Banach-Tarski Paradox, which is a theorem stating roughly that one may take a three-dimensional ball, decompose it into finitely many pieces, and move these pieces around in space so that they form two complete balls, each of the same size as the original ball. On its face, this seems absurd. We have seemingly doubled the amount of stuff we have! Of course, closer inspection dispels the aura of paradox here. The pieces needed to perform the construction are infinitely complicated and non-definable and certainly could not be used in some brilliant gold-proliferating get-rich-quick scheme in the real world. And, when we think about it, there are just as many points in two balls as there are in one (continuum-many, in both cases), so maybe this theorem isn’t so surprising after all?

Dilworth was apparently not convinced, though, He found the Banach-Tarski Paradox to be clearly wrong, and since the result depended on the techniques of the then-young field of set theory, and since set theory was born out of Cantor’s Theorem, there must be something wrong with Cantor’s Theorem.

The paper makes for alternately entertaining and maddening reading. His reasoning is often muddled, but Dilworth does sometimes have a way with words and, though he perhaps goes a bit too far in this direction, the writing has character and flair in a way that I sometimes wish more technical mathematical writing did. For example, when describing Cantor’s diagonal argument and what he sees as its undeserved acceptance by the mathematical community, Dilworth writes,

Historically and up to this date, he has won. The horrendous “alephs” of his endless infinities thunder through the evening skies of academe “with hooves of steel”, as the songwriter put it.

There is a decided lack of Johnny Cash references in today’s mathematical writing. (And yes, I know that Cash’s version of this song was released in 1979 and therefore can’t be the version referenced in this 1974 paper…)

The paper also ends memorably, with an assertion of a conspiracy among mathematicians to cover up the fallacies in Cantor’s proof, followed by a final, simple, cryptic directive:

Remember the spheres.

In substance, though, Dilworth’s writing is at first incomprehensible, and when its meaning has been at least partially uncovered, his error is immediately evident. In attempting to show that the size of the set of all real numbers is exactly the same as the size of the set of all natural numbers, he is not in fact considering all real numbers, but just those whose decimal representations only have finitely many digits (or, in a different reading of his argument, only those whose decimal representations end in endlessly repeating patterns; or, in a still different reading, only those which are definable by a finite sentence). And he is correct in the sense that this subset of the real numbers does have the same size as the set of natural numbers. But by restricting his vision to this subset, he is excluding the vast majority of real numbers.

This is a mistake that could have been pointed out to Dilworth by any mathematician or any sufficiently advanced student of mathematics. And it apparently was pointed out to him on multiple occasions, for Dilworth includes accounts of his interactions with mathematics professors in the paper. For example, in one passage, Dilworth acknowledges the obvious objection to his argument, namely that he is not considering all of the real numbers, but dismisses it out of hand without argument. In another passage, when discussing Cantor’s claim that, if one tries to pair the real numbers off in a one-to-one fashion with the integers, the integers will necessarily “become exhausted” before the process is complete, he relates the following incident:

“Yes sir,” the head of the mathematics department of a Univ. of Illinois section said matter-of-factly to my face, “The integers will become exhausted.” Believe it or not, Georg Cantor made these remarkable claims stick with the world’s mathematicians of his time, and they stick unto this day. The effects of the Cantorian grip on the professional mind have to be experienced to be believed.

It is difficult to judge how much of this disconnect between Dilworth and the professional mathematicians is due to Dilworth’s own stubbornness and unwillingness to admit his error and how much of it is due to the mathematicians’ inability to clearly articulate somewhat complex mathematical ideas to a non-mathematician (something that, as I have discovered through writing this blog, is often quite difficult to do). In any event, something went wrong in this case, which is unfortunate. It is encouraging, and all too rare, to see non-mathematicians become enthusiastic about and engaged in mathematics, so it is always a shame to see them go astray.

Let us take a slight detour here to make an observation about education and training. I don’t think it will be particularly controversial to say that the primary aim of mathematics education, particularly at the graduate level, is not the learning of calculation techniques or the statements and proofs of theorems (though this will of course come), but rather a training in the actual practice of doing mathematics, of thinking mathematically, and of being able to communicate mathematical ideas with other mathematicians. In my experience, competence in this practice of mathematics is much harder to come by than mathematical knowledge, perhaps almost impossible to come by without a dedicated mentor, a role typically filled by one’s PhD advisor. It is precisely this conversance with mathematical practice that, at least in modern times, seems to be almost a prerequisite to making any sort of substantial contribution to mathematical knowledge, and it seems to be precisely what Dilworth was lacking.


There is a common and mildly insulting label that often gets applied to people such as William Dilworth: crank. In 1992, Underwood Dudley, then a professor at DePauw University in Indiana, published a comprehensive and encyclopedic compendium of crankery, Mathematical Cranks. In the introduction to the book, Dudley clarifies what he means by the word.

They’re not nuts. Well, a few are, but most aren’t. A lot of them are amateurs — mathematical amateurs who don’t know much mathematics but like to work on mathematical problems. Sometimes, when you can’t convince them that they haven’t done what they thought they’ve done, they turn into cranks, but cranks aren’t nuts, they’re just people who have a blind spot in one direction.

One chapter of Dudley’s book is devoted to cranks attacking Cantor’s Theorem. We meet a person who found five separate mistakes in Cantor’s proof, a person who held that Cantor’s conception of “number” was incorrect, and people who dispute the existence of mathematical infinity. At the end of the chapter, we meet William Dilworth. After running through the problems with Dilworth’s paper, Dudley concludes the chapter with the following sentences (Dudley does not identify the state responsible for publishing Dilworth’s paper, and also refers to Dilworth as W.D.):

His article reads as if it is by someone convinced, whose mind is not going to be changed by anything. It is by, in two words, a crank, and it is no credit to the state of X.


Dilworth was not happy about his inclusion in Mathematical Cranks. As an engineer, an academic outsider, it was hard enough for him to publish his ideas and to be taken seriously by the mathematical establishment. After being publicly labeled a crank, it would become nearly impossible. And so, in 1995, he sued Underwood Dudley for defamation.

The suit was dismissed by a district judge for “failure to state a claim.” More precisely, the judge held that the word “crank” is incapable of being defamatory; it is mere “rhetorical hyperbole.” Dilworth appealed this ruling, and the case ended up in the Seventh Circuit Court of Appeals, before none other than Judge Richard Posner, the “most cited legal scholar of the 20th century” and one of the most prominent modern American judges not to have been appointed to the Supreme Court. And if this whole story gave us nothing else, it would have been worth it solely for Posner’s remarkable decision.

Posner begins by noting that it is crucial for Dilworth’s claim to establish that Dudley acted with “actual malice” in calling Dilworth a crank:

The allegation of actual malice is necessary because the plaintiff is a public figure. Not, it is true, a “public figure” in the lay sense of the term. Dilworth is an obscure engineer. But anyone who publishes becomes a public figure in the world bounded by the readership of the literature to which he has contributed.

(It is good to know that I am, at least legally speaking, a public figure!)

Posner then goes on to consider the district judge’s ruling that “crank” cannot be defamatory because it is mere “rhetorical hyperbole.” He begins by considering past cases that deal with precisely this issue.

Among the terms or epithets that have been held (all in the cases we’ve cited) to be incapable of defaming because they are mere hyperbole rather than falsifiable assertions of discreditable fact are “scab,” “traitor,” “amoral,” “scam,” “fake,” “phony,” “a snake-oil job,” “he’s dealing with half a deck,” and “lazy, stupid, crap-shooting, chicken-stealing idiot.”

These terms, Posner asserts, have both literal and figurative usages. Figurative usages cannot be defamatory; they are mere “rhetorical hyperbole.” Literal usages, on the other hand, that make real factual claims, can be defamatory if false. Decisions on the defamatory nature of these terms, therefore, hinge on a judgment as to whether they are intended literally or figuratively. Posner then goes on to consider whether “crank” falls into this category.

“Crank” might seem the same type of word, but we think not. A crank is a person inexplicably obsessed by an obviously unsound idea — a person with a bee in his bonnet. To call a person a crank is to say that because of some quirk of temperament he is wasting his time pursuing a line of thought that is plainly without merit or promise. An example of a math crank would be someone who spent his time trying to square the circle. To call a person a crank is basically just a colorful and insulting way of expressing disagreement with his master idea, and it therefore belongs to the language of controversy rather than to the language of defamation.

And, before affirming the district judge’s opinion, Posner includes this sentence designed to flatter set theorists everywhere.

As we emphasized in the Underwager case, judges are not well equipped to resolve academic controversies, of which a controversy over Cantor’s diagonal process is a daunting illustration…


Acknowledgments: Our thanks to Peter Smith and his blog, Logic Matters, where we first learned of this story. Cover image from the Bad Postcards Tumblr page.

L’escalier du Diable

Welcome one, welcome all to the Point at Infinity sideshow, where today we present a tantalizing and diabolical selection of musical and mathematical curiosities. Just watch your step; these stairs can be a bit tricky.


A few months ago, you may recall, we published two posts about the Shepard tone and the Risset rhythm, aural illusions in which a tone or rhythm seems to perpetually rise or fall in pitch or in tempo but is actually repeating the same pattern over and over again, the musical equivalents of Penrose stairs.

372px-Impossible_staircase.svg
Penrose stairs. (Image in the public domain.)

To accompany the posts we created some sound samples so the readers could hear the illusions themselves. A couple of weeks ago, one of these samples was used in an internet radio program on audio paradoxes released by Eat This Radio, paired with some work of Jean-Claude Risset. The entire program is really excellent, ranging from a piece by J.S. Bach to mid-twentieth century audio experiments to modern electronic music, and I encourage all of you to listen to it.


One of the pieces in the radio program is a piano étude written by György Ligeti in the late twentieth century. The étude is named L’escalier du diable, or The Devil’s Staircase, and its repeated ascents of the keyboard have a striking resonance with the never-ending ascent of the Shepard tone.


The Devil’s Staircase is also the colloquial name given to a particular mathematical function introduced by Georg Cantor in the 1880s. It is a function defined on the set of real numbers between 0 and 1 and taking values in the same interval, and it has some quite curious properties. Before we discuss it, let’s take a look at (an approximation to) the graph of the function.

CantorEscalier.svg
Graph of the Devil’s Staircase. By Theon, CC BY-SA 3.0.

To appreciate the strangeness of this function, let us recall some definitions regarding functions of real numbers. Very roughly speaking, a function is called continuous if it has no sudden jumps, or if its graph can be drawn without lifting the pencil from the page. Continuous functions satisfy a number of nice properties, such as the intermediate value theorem.

The derivative of a function at a given point of its domain, if it exists, measures the rate of change of the function at that point. If the x-axis measures time and the y-axis measures the position of an object along some one-dimensional track, then the derivative can be thought of as the velocity of that object. If a function is differentiable at a point (i.e., if its derivative exists there) then it must be continuous at that point, but the converse is not necessarily true. (For example, if the graph of a function has a sharp corner at a point, then the function cannot be differentiable there.)

Let’s think about what it means for a function to have a derivative of 0 at a point. It means that, at that point, the rate of change of the function has vanished. It means that, if we zoom in sufficiently close to that point, the function should look like a constant function. Its graph should look like a horizontal line. What would it mean for a function to have a derivative of 0 almost everywhere? (Here “almost everywhere” is a technical term (which I’m not going to define) and not just me being vague.) One might think that this must imply that the function is a constant function. At almost every point in its domain, the rate of change of the function is 0, so how can the value of the function change?

One will quickly discover that this is not quite right. Consider the function defined on the real numbers whose value is 0 at all negative numbers and 1 at all non-negative numbers.

step

This function has derivative 0 everywhere except at 0 itself, and yet it increases from 0 to 1. It does this quite easily by being discontinuous at 0, which, in hindsight, seems sort of like cheating. So what if we also require our function to be continuous? Now we need more exotic examples, and this is where the Devil’s Staircase comes in, for the Devil’s Staircase is a continuous function, it is differentiable almost everywhere, it has a  derivative of 0 wherever its derivative is defined, and yet it still manages to increase from 0 to 1. Wild!

What is the Devil’s Staircase exactly? I’ll give two different definitions. The first proceeds via an iterative construction. Start with the function f_0(x) = x. Its graph, between 0 and 1, is simply a straight line segment increasing from (0,0) to (1,1). Now, look at the midpoint of this increasing line segment, and draw a horizontal line segment centered there whose length is 1/3 of the horizontal line of the original increasing segment. Now connect the ends of this line segment via straight lines to (0,0) and (1,1). This new curve is the graph of a function that we call f_1. It consists of two increasing line segments with one horizontal line segment between them. Now repeat the process that took us from f_0 to f_1 on each of these increasing line segments, and let f_2 be the function whose graph is the result. Continue in this manner, constructing f_n for every natural number n.

Cantor_function_sequence
First three steps of the iterative construction of the Devil’s Staircase. (Image in the public domain.)

It turns out that, as n goes to infinity, the sequence of functions \langle f_n \mid n \in \mathbb{N} \rangle converges (uniformly) to a single function. This function is the Devil’s Staircase.

A more direct but also more opaque definition is as follows: Given a real number x between 0 and 1, first express x in base 3 (i.e., using only 0s, 1s, and 2s). If this base 3 representation contains a 1, then replace every digit after the first 1 with a 0. Next, replace all 2s with 1s. The result has only 0s and 1s, so we can interpret it as a binary (i.e., base 2) number, and we let f(x) be this value. Then the function f defined in this manner is the Devil’s Staircase. Play around with this definition, and you might get a feel for what it’s doing.


And now, on our way out, some musical addenda. An encore, if you will. First, after making the Risset rhythms for the aforementioned post, I did some further coding and wrote a little program that can take any short audio snippet and make a Risset rhythm out of it. Here’s an example, first accelerating and then decelerating, using a bit from a Schubert piano trio.

You may recognize the sample from the soundtrack to Barry Lyndon.

Finally, I can’t help but include here one of my favorite pieces by Ligeti, Poema sinfónico para 100 Metrónomos.


Cover image: Devil’s Staircase Wilderness, Oregon, USA

Hippasus and the Infinite Descent

Today, dear Reader, we bring you a story. A story of Mathematics and Music, of Reason and Passion, of Drama and Irony. It is the story of Hippasus of Metapontum, of his remarkable life and his equally remarkable death. Before we begin, a note of warning. Not everything presented here is true, but all of it is meaningful.


Ippaso_di_Metaponto
Hippasus of Metapontum

A Greek philosopher and mathematician from the 5th century BCE, Hippasus was a follower of Pythagoras. The Pythagoreans believed in the transmigration of souls, subscribed to the belief that All is Number (where “Number” is, of course, “Whole Number”), made great strides in the study of musical harmony, and eschewed the eating of beans. Our hero was a particularly illustrious Pythagorean. He performed experiments linking the sizes of metal discs to the tones they emit upon being struck, developed a theory of the musical scale and a theory of proportions, and showed how to inscribe a regular dodecahedron in a sphere. The regular dodecahedron is a twelve-sided solid whose faces are regular pentagons, shapes which were dear to the Pythagoreans and central to our story. The pentagram, the five-sided star formed by extending the sides of a regular pentagon, and whose tips themselves form a regular pentagon, was a religious symbol of the Pythagoreans and a mark of recognition amongst themselves.

pentagram_coin
Ancient Greek coin with a pentagram

A corollary to the Pythagorean doctrine that All is Number was a belief, at the time, that any two lengths are commensurable, i.e., that given any two lengths, they are both whole number multiples of some fixed smaller length. In modern language, this amounts to the assertion that, given any two lengths, their ratio is a rational number, i.e., can be expressed as the ratio of whole numbers. It is only fitting that the first evidence to the contrary would come from the pentagram.

It happened when Hippasus was stargazing. He saw five stars forming a perfect regular pentagon, and inside this regular pentagon he formed a pentagram, at the center of which lay another regular pentagon, into which he formed another pentagram, at the center of which lay another regular pentagon, into which he formed another pentagram. An infinite web of similar triangles was woven through his mind and, in a flash of insight, he realized something terrible: the lengths of one side of the regular pentagon and one side of the pentagram found inside it are incommensurable.

first_diagram
The lengths of one side of a regular pentagon and one side of the inscribed pentagram are incommensurable. In other words, if s denotes the length of the black line segment AB and t denotes the length of the blue line segment AC, then t/s (and therefore also s/t) is irrational.

The next day, he told his fellow Pythagoreans of his discovery, and they were horrified. They could not have this knowledge, which struck at the core of their belief system, getting out into the wider world. So they took Hippasus far out to sea, and they threw him overboard.


Infinite descent is a proof technique that morally dates back to the ancient Greeks but really came into its own in the work of Pierre de Fermat in the 17th century. The idea behind it is simple and immediately appealing. Suppose we want to prove that there are no positive integers satisfying a particular property. One way to prove this would be to show that, given any positive integer n satisfying this property, we could always find a smaller positive integer n' satisfying the same property. Repeating the argument with n' in place of n, we could find a still smaller positive integer n'' satisfying the same property. Continuing, we would construct a decreasing sequence of positive integers, n > n' > n'' > n''' > \ldots , the aforementioned “infinite descent”. But of course there can be no infinite decreasing sequences of positive integers (if a decreasing sequence starts with n, it can of course have at most n elements). One thus reaches a contradiction and concludes that there are no positive integers with the given property.

Fermat made great use of the method of infinite descent in his work on number theory. One particularly striking application came in the proof of a special case of his famous Last Theorem: there are no positive integers a,b,c such that a^4 + b^4 = c^4. Fermat showed that, if a_0,b_0,c_0 are positive integers such that a_0^4 + b_0^4 = c_0^4, then we can construct positive integers a_1, b_1, c_1 such that a_1^4 + b_1^4 = c_1^4 and c_1 < c_0. One can then continue, with a_1, b_1, c_1 in place of a_0, b_0, c_0, and obtain a_2, b_2, c_2 with a_2^4 + b_2^4 = c_2^4 and c_2 < c_1. This of course leads to the infinite descent c_0 > c_1 > c_2 > \ldots and a contradiction.

We will use the method of infinite descent to prove the result of Hippasus mentioned above. This will not be exactly the way the ancient Greeks would have presented the proof, but it is very similar in spirit, and we make no apologies for the anachronism. Let’s get started.


Suppose, for the sake of an eventual contradiction, that we have a regular pentagon whose side length is commensurable with the side length of the inscribed pentagram. Let s denote the side length of the pentagon and t denote the side length of the pentagram (i.e., the diagonal of the pentagon). In modern language, our assumption is that \frac{t}{s} is rational, i.e., that there are positive integers p and q such that \frac{t}{s} = \frac{p}{q}. By scaling the pentagon, we can in fact assume that t = p and s = q. So let this be our starting assumption: there is a regular pentagon whose side length s and diagonal length t are both positive integers.

Let us label the vertices of the pentagon by the letters A,B,C,D,E. The center of the pentagram forms another regular pentagon, whose vertices we shall call a,b,c,d,e. This is shown in the diagram below. Note that s is the length of the line segment connecting A and B (we will denote this length by |AB|), and t is |AC|. Let s' denote the side length of the inner pentagon, i.e., |ab|, and let t' denote the length of the diagonal of the inner pentagon, i.e., |ac|.

proof_diagram
Figure 1

We now make use of the wealth of congruent triangles in the diagram. We first observe that, whenever a pentagram is inscribed into a regular pentagon, the diagonals that form the pentagram exactly trisect the angles of the pentagon. (Exercise: Prove this!) Therefore, the triangle formed by A, E and D is congruent to that formed by A, e, and D, on account of their sharing a side and having the same angles on either end of that side. In particular, we have |Ae| = |AE| = s.

Next, consider the triangle formed by A, b, and d. By our observation at the start of the previous paragraph, the angle at b in this triangle has the same measure as the angle at A. But then this triangle is isosceles, so we have |Ad| = |db| = t'. Of course, we clearly have |Ad| = |Bd| = |Be| = |Ce| =…, so all of these lengths are equal to t'.

proof_diagram
Figure 1 again

Let’s now see what we have. Consider first |AC|. By definition, we have |AC| = t. But also |AC| = |Ae| + |Ce|, and we saw previously that |Ae| = s and |Ce| = t'. All together, we have t = |AC| = |Ae| + |Ce| = s + t', or t' = t-s.

Next, consider |Ae|. We have already seen that |Ae| = s. But we also have |Ae| = |Ad| + |de|. We saw previously that |Ad| = t', and by definition we have |de| = s'. All together, we have s = |Ae| = |Ad| + |de| = t' + s', or s' = s - t'. Since we already know that t' = t-s, this yields s' = 2s - t.

This might not seem like much, but we’re actually almost done now! The key observation is that, since s and t are integers, and since s' = 2s - t and t' = t-s, it follows that s' and t' are also (positive) integers. We started with a regular pentagon whose side length s and diagonal length t were integers and produced a smaller pentagon whose side length s' and diagonal length t' are also integers. But now we can continue this process, producing smaller and smaller regular pentagons and producing infinite descending sequences of positive integers, s > s' > s'' > \ldots and t > t' > t'' > \ldots.

pentagons
The infinite descent

This is a contradiction, and we have thus shown that \frac{t}{s} is irrational. But what is this ratio exactly? Well, it turns out to be a fascinating number, easily #2 on the list of Most Famous Ratios of All Time: \phi, a.k.a. the golden ratio! But that is a story for another time…


As a short addendum to today’s story, here’s a little-known fact about the end of Hippasus’ life. It turns out that, after being thrown overboard by his fellow Pythagoreans, he has not and will never in fact reach the seabed! For to get there, he would first have to travel halfway down, and then he would have to travel half of the remaining distance, and then half of the still remaining distance, and so on and so forth, completing an endless sequence of tasks, and thus he remains to this date in the midst of an infinite descent of his own.


Notes:

(1) \sqrt{2} is more commonly cited as being the first irrational number discovered by the Pythagoreans, and it is almost always the first number proven to be irrational in classrooms today. However, the proof of the irrationality of \sqrt{2} possessed by the Greeks is not the simple number-theoretic proof used today and is in fact a rather complex elaboration of the proof of the incommensurability of the side and diagonal lengths of a regular pentagon. Given this fact and the centrality of the pentagram in Pythagorean intellectual life, some scholars have suggested that perhaps this was in fact the first proof of the existence of incommensurability and that the proof of the irrationality of \sqrt{2} came later. We have adopted this hypothesis for the purpose of our story today.

(2) This story is derived from legends that significantly post-date the death of Hippasus. It seems unlikely actually to have happened as presented here.

(3) This post was in part inspired by the episode “Drowned at Sea”, from the excellent podcast, Hi-Phi Nation, by philosopher Barry Lam. Check it out!


Cover image: “Rainstorm Over the Sea” by John Constable

Beats by Bjorklund

You gotta keep ’em separated.

-The Offspring, “Come Out And Play”

(Friendly note to the reader before we begin: If you’re looking for music to listen to while reading this post, just scroll to the bottom…)

The Spallation Neutron Source (SNS), at Oak Ridge National Laboratory in Tennessee, provides the world’s most intense pulsed neutron beams for scientific research. By accelerating proton pulses and directing them towards a mercury target, the laboratory ejects neutrons from the target. By measuring the energies and angles of these scattered neutrons, scientists can uncover information about the magnetic and molecular structure of various materials.

Pulses at the SNS are grouped into super-cycles, each 10 seconds long and consisting of 600 pulses. Commonly, experimenters will want to perform a particular action on a fixed number of pulses (k, say) during each super-cycle and will want to have the executions of the actions spaced as evenly as possible across time. If k evenly divides 600, then the solution to this problem is trivial: just perform the action on pulses 0, \frac{600}{k}, \frac{2 \cdot 600}{k}, \frac{3 \cdot 600}{k}, \ldots, \frac{(k-1) \cdot 600}{k}. If k does not evenly divide 600, though, then the solution is not as obvious.

This is of course a special case of a general problem: Given cycles of length n, how can k events be spaced as evenly as possible across a single cycle? (Naturally, we should have k \leq n here.) As seen above, the problem is trivial if k evenly divides n, so we shall assume this is not the case. In fact, we shall assume that k and n are relatively prime, i.e., that they have no common positive divisors other than 1. We will also assume that k > 1, since it is also trivial to evenly distribute one event across a cycle.

This exact problem was tackled by E. Bjorklund, motivated by timing questions at the SNS. In this paper, he presents an algorithm for generating solutions. For ease of notation, let us denote a cycle by a sequence of 0s and 1s, with a 1 representing an event taking place and a 0 representing an event not taking place. For definiteness, we will always start the sequence with a 1, but, because we are dealing with cyclic phenomena, we will consider two “rotations” of the same base sequence to be the same. For example, we consider 10010 and 10100 to be the same, since the second is just the first “rotated” (and wrapped around) three spaces to the right.

We will not give a formal account of Bjorklund’s algorithm here, but we will illustrate it with an example that we hope will indicate how to carry it out in general. Suppose we are given the specific problem of evenly spacing eight events in a cycle of length thirteen. Our final sequence will thus have eight 1s and five 0s. We start with thirteen individual sequences, each of length one, with all of the 1s first and then all of the 0s:

[1] [1] [1] [1] [1] [1] [1] [1] [0] [0] [0] [0] [0]

You will notice that we have two different sequences in this list ([1] and [0], here). This will be true for every step of the algorithm. In the next step, we take all instances of the second sequence ([0], here) and append them in turn to instances of the first sequence. Since there are five instances of the second sequence, five instances of the first sequence will become longer, and we obtain:

[10] [10] [10] [10] [10] [1] [1] [1]

We again have two different sequences ([10] and [1]). And we again take all instances of the second sequence and append them in turn to instances of the first sequence, obtaining:

[101] [101] [101] [10] [10]

Repeating this process again yields:

[10110][10110][101]

Technically, since there is only one instance of the second sequence in this stage, we could stop here and just append all of the sequences in order to obtain the correct solution, but let us continue for illustration’s sake. Next, we get:

[10110101][10110]

And, finally:

[1011010110110}

(which is just a rotation of what we would have gotten two stages earlier: [1011010110101]). Thus, the optimal way of evenly distributing eight events in a single cycle of length 13 is given by the sequence 1011010110110. A similar process will yield the correct answer in any other specific instance of this problem.

(The astute reader might have noticed that this algorithm bears a resemblance to Euclid’s famous algorithm for calculating the greatest common divisor of two positive integers. This is not a coincidence.)


You might be slightly disturbed by my lack of rigor at this point. Indeed, there are two ways in which I am slightly cheating the reader. First, I have not really said what I mean by having events be spaced “as evenly as possible.” Intuitively, 1011010110110 is more even than 111111110000, or 1101101101100, or, if one thinks about it, 1011011011010, but how do we know it is “as even as possible,” and what do we even mean by this? Second, even if I had given a rigorous definition of “evenness,” I have not proven that Bjorklund’s algorithm does in fact deliver the optimal result (again, this should be intuitively plausible, but should perhaps not be blindly accepted). I will do neither of these things here, but will instead direct the interested reader to the excellent paper, “The distance geometry of music,” by Demaine, Gomez-Martin, Meijer, Rappaport, Taslakian, Toussaint, Winograd, and Wood, from which much of this post was derived.


Unsurprisingly, the problem of evenly distributing k events or items into cycles of length n does not show up only in nuclear physics. Let us briefly look at a couple of other interesting appearances.

Computer graphics: Suppose you want to depict a straight line on a computer screen with a slope of \frac{k}{n}. Computer screens consist of grids of pixels, so, unless the line is horizontal or vertical, it cannot be drawn perfectly straight. Here is an example of a segment of a line with slope -\frac{5}{11}:

832px-Bresenham.svg
A line with slope -5/11, superimposed over a pixel approximation. Created by Crotalus horridus, Public Domain

It should be clear that, at least as long as k < n, the problem of drawing this line consists of choosing k out of every n horizontal spaces after which to move your line one space vertically. To make your line as straight as possible, this distribution should be as even as possible. Indeed, the situation depicted above can be represented by the sequence 10101001010, where 1 indicates a vertical shift and 0 represents the absence of a vertical shift. This is precisely the result one gets (after a rotation) if one applies Bjorklund’s algorithm to the numbers 5 and 11.

Leap year distribution: The problem of reconciling the fact that one revolution of the earth around the sun does not take an exact integer number of days with the desire to have years that last an exact integer number of days is one that affects every calendar design. It is handled particularly interestingly in the Hebrew calendar. The Hebrew calendar is a lunisolar calendar, in which each month lasts one full cycle of the moon, but in which adjustments are made so that each month occurs at roughly the same stage of the solar year during each cycle. The Hebrew calendar reconciles these two contradictory demands by having twelve months in a typical year but, during certain “leap years,” having one of these months (namely, Adar) repeated to yield a year of thirteen months. It turns out that, to keep the Hebrew calendar very close to being in sync with the solar cycles, one needs to have seven out of every nineteen years be leap years. It is also natural to want these leap years to be spaced as evenly as possible. And, indeed, the distribution of these seven leap years in nineteen-year cycles in the Hebrew calendar is given precisely by a rotation of the result of Bjorklund’s algorithm applied to the numbers seven and nineteen.


Perhaps the most interesting appearances of the problem of evenly distributing events in a cycle, though, are in music. If one thinks of a musical measure consisting of n beats as being a cycle of length n, of a 1 as being a note being played, and of a 0 as being the absence of a note being played, then our strings of 1s and 0s can be thought of as musical rhythms. And it turns out that applications of Bjorklund’s algorithm, when interpreted in this way, yield a startling variety of musical rhythms used in practice around the world. We end this post by presenting a few prominent examples.

In what follows, we notationally replace 1s with ‘x’s and 0s with dots. This is more conducive to following along with musical rhythms, as it is visually easier to get lost in strings of 1s and 0s than in strings of ‘x’s and dots. An ‘x’ thus denotes a note being played and a dot denotes the absence of a note being played (or, often, an ‘x’ denotes an accented beat and a dot denotes an unaccented beat).  Given numbers k < n, we denote by E(k,n) the result of Bjorklund’s algorithm applied to k and n. The sequence that follows is the rotation of this result that is actually heard in the piece of music. As before, we restrict ourselves to the interesting cases in which k and n are relatively prime and k > 1. (Of course, the standard waltz rhythm [x .  . ], for example, would be E(1,3), and the standard backbeat rhythm [. x . x ] would be a rotation of E(2,4), but these are sort of boring in this context.)

There’s some good music here. Enjoy!

E(2,5) – (x . . x . ): “Take Five” by The Dave Brubeck Quartet.

E(3,7) – (x . x . x . . ): “Money” by Pink Floyd.

E(3,8) – (x . . x . . x . ): This is the famous tresillo rhythm, which can be heard throughout Latin American and sub-Saharan African music as well as in such songs as “Hound Dog,” “Despacito,” and the song we feature here, “Intro” by The xx.

E(5,8) – (x . x x . x x . ): This is the cinquillo rhythm, an elaboration of the tresillo that is also ubiquitous in Latin American and sub-Saharan African music. It also features prominently in “Come Out and Play” by The Offspring.

E(4,9) – (x . x . x . x . . ): This is our second track from the classic Time Out album, which was inspired by musical styles (especially time signatures) observed during travels in Europe and Asia. Brubeck saw this particular beat being played by Turkish street musicians and then used it for  “Blue Rondo à la Turk” by The Dave Brubeck Quartet.

E(4,11) – (x . . x . . x . . x . ): “Outside Now” by Frank Zappa.

E(5,11) – (x . x . x . x . x . .): “Promenade” from Pictures at an Exhibition by Modest Mussorgsky.

E(7,12) – (x . x . x x . x . x . x): This is one of the most important rhythms in sub-Saharan Africa, often used as a bell pattern. It is also a common beat in the Palo music of the Caribbean. It can be heard played by the claves player in this performance by Los Calderones, which I have been listening to non-stop for the last hour. (Note also that, if one re-interprets this sequence in a harmonic rather than rhythmic setting, in which each step of the cycle represents a half-step in pitch, an ‘x’ represents the inclusion of that note in a scale, and a dot represents the exclusion of that note from a scale, then this sequence (this exact rotation, in fact) precisely corresponds to the major diatonic scale, the most common musical scale in Western music!)

E(4,13) – (x . . x . . x . . x . . . ): This rhythm can be heard in the instrumental sections of “Golden Brown” by The Stranglers.

E(5,16) – (x . . x . . x . . . x . . x . . ): This rhythm forms the basis for much bossa nova music and, when significantly slowed down, “Pyramid Song” by Radiohead.


Cover image: Detail from “Wall Drawing #260” by Sol LeWitt