An Algorithmic Lucidity

Earlier this year, Robert Hasner showed me something that I assume everyone else ("everyone else") already knows, but which I didn't know: every function on ℝ can be decomposed into the sum of an even function and an odd function—

(In fact, as I later read elsewhere, there's nothing essentially twoful about this idea (at least, if you don't care about restricting yourself to ℝ): you can split a function into a sum of \(n\) functions \(f_j\) for \(j \in \{0, ..., n-1\}\) such that \(f_j(\omega z) = \omega^j f_j(z)\) where ω is an \(n\)th root of unity.)

I started seeing the same pattern in my reading, too. Like, every matrix can be decomposed into the sum of a symmetric and a skew-symmetric matrix:

(In fact, I have been given to understand that this observation is actually expressing a deep truth about the nature of linear transformations: every linear transformation is in some sense—which I hope to make more explicit later—the sum of a scaling in orthogonal directions (from the symmetric matrix; consider the spectral theorem) and a rotation (from the skew-symmetric matrix, which is said to represent an infinitesimal rotation).)

Also (and probably related to the matrix thing), in the geometric algebra, the geometric product of vectors can be expressed as the sum of an inner product and an anticommutative outer product.

Are there more examples of this theme of splitting something into symmetric and antisymmetric parts? Is there a general theorem explaining exactly which mathematical objects do this kind of thing?

What is a vector in Euclidean space? Some might say it's an entity characterized by possessing a magnitude and a direction. But scholars of the geometric algebra (such as Eric Chisolm and Dorst et al.) tell us that it's better to decompose the idea of direction into the two ideas of subspace attitude (our vector's quality of living in a particular line) and orientation (its quality of pointing in a particular direction in that line, and not the other). On this view, a vector is an attitudinal oriented length element. But having done this, it becomes inevitable that we should want to talk about attitudinal oriented area (volume, 4-hypervolume, &c.) elements. To this end we introduce the outer or wedge product ∧ on vectors. It is bilinear, it is anticommutative (swapping the order of arguments swaps the sign, so \(\vec{a}\wedge\vec{b} = -\vec{b}\wedge\vec{a}\)), and that's all you need to know.

Suppose we have two vectors \(\vec{a}\) and \(\vec{b}\) in Euclidean space and also a basis for the subspace that the vectors live in, \(\vec{e}_1\) and \(\vec{e}_2\), so that we can write \(\vec{a} := a_1\vec{e}_1 + a_2\vec{e}_2\) and \(\vec{b} := b_1\vec{e}_1 + b_2\vec{e}_2\). Then the claim is that the outer product \(\vec{a}\wedge\vec{b}\) can be said to represent a generalized vector (call it a 2-blade—and in general, when we wedge k vectors together, it's a k-blade) with a subspace attitude of the plane that our vectors live in and a magnitude equal to the area of the parallelogram spanned by them. Following Dorst et al., let's see what happens when we expand \(\vec{a}\wedge\vec{b}\) in terms of our basis—

But the anticommutativity property implies that the outer product of a vector with itself is zero, because \(\vec{e}\wedge\vec{e} = -\vec{e}\wedge\vec{e}\). So we have

It's a determinant! And since determinants tell us about the oriented volumes of parallelepipeds, we can see why these blades defined by this outer product are a sensible generalization of the vector idea. And none can doubt that they shall play but ever such an essential role in our vaunted geometric algebra!

In addition to — and –, there should also be an &rdash; HTML character entity reference which specifies the Unicode high voltage sign U+26A1 (⚡).

Supposedly the method of pomodoros is a great technology for overcoming procrastination: you work in twenty- or twenty-five-minute timed blocks, each of which are atomic, indivisible: you have to work through the block, and if you let yourself wander away to something else, then it doesn't count. Katja Grace explains why this is a good idea:

While working, there are various moments when it would be easier to stop than to continue, particularly if you mostly feel the costs and benefits available in the next second or so, and if you assume that you could start again shortly [...] Counting short blocks of continuous time working pretty much solves this problem for me. [...] [A]t any given moment there might be a tiny short term benefit to stopping for a second, but there is a huge cost to it. In my case this seems to remove stopping as an option, in the same way that a hundred dollar price on a menu item removes it as an option without apparent expense of willpower.

It is a good idea (I can only imagine), and yet one can't help but guess that, like spaced repetition software or any number of other technologies for living a better life, the number of people who have heard of the method of pomodoros and judged it a good idea is far larger than the number of people who have actually given it an honest try. I could lament how terrible this is, and condemn the human spirit as being lazy and therefore evil, but it seems besides the point—we have no reason to care about moral grandstanding, we want something that actually works.

One asks oneself: is this little piece of boring but genuinely-worth-doing work really that bad, really so terrible that setting a twenty-minute timer and actually facing it would be too much to bear? One wants to say that the answer can't possibly be Yes, that if one's actions betray an implicit Yes it can only mean that one wasn't really paying attention to the question. The natural inclination is then to ask if paying attention to the question is really that terrible, but that would be too obvious.

I bought cookie dough, on the thought that maybe I should bake cookies and offer them to people at the University; if they were to ask what the occasion was, I could say, "It seemed like a whimsical thing to do, and I'm a whimsical person." But I'm not sure I'll actually do it.

I used to work for a different store in this chain, the one on Ygnacio Valley. The stores are numbered (internally; the numbers aren't secret, but it's the sort of thing you don't notice unless you work for the company), and the store on Ygnacio Valley is number 1701, which I remember thinking was a very significant number, but I don't remember anyone else agreeing with me, probably because if I told anyone, then they hadn't been a Star Trek fan.

It's how close you come to doing the Right Thing at each and every one of the uncounted millions of decision points that make up your life, with how you play in any particular game only constituting a tiny fraction of these, and it being not at all clear that choosing to play a game just then is closer to the Right Thing than any number of non-game-playing actions you might have chosen instead, but didn't.

It seems as if my outlook on life varies drastically with mood. In the moments when I feel brave and ambitious, I rarely seem to remember that it won't last: that in a week or a day, the moment will be gone and I'll feel weak and scared again—and of course it goes conversely, too.

We don't have the technology or the wisdom to redesign our own emotions. If the moments of weakness-and-fear aren't going away, and if neither mood is exactly a belief that could be destroyed by the truth, then it seems like it would at least be useful to remember, if for no other reason than to avoid wasting cognition devising plans and expectations that aren't sufficiently robust to ordinary emotional variation.

In the study of the elementary algebra, one occasionally hears of the conjugate roots theorem, which says that if \(z_0\) is a root of a polynomial with real coefficients, then its complex conjugate is also a root. Or if you prefer, nonreal roots come in conjugate pairs. It also works in the other direction: if nonreal roots of a polynomial come in conjugate pairs, then the polynomial has real coefficients, because the purely imaginary parts cancel when you do the algebra: \((x - (a + bi))(x - (a - bi)) = x^2 - x(a + bi) - x(a - bi) + (a^2 - (bi)^2) = x^2 - 2ax + a^2 + b^2\).

There's also this idea that conjugation is the unique nontrivial "well-behaved" automorphism on ℂ, a map from ℂ to itself that respects addition and multiplication: the sum (respectively product) of the conjugates is the conjugate of the sum (respectively product). The complex numbers are symmetrical around the real axis in a way that they're not around the imaginary axis: while i and –i are different from each other, you can't "tell which is which" because they behave the same way. Contrast to 1 and –1, which do behave differently: if someone put either 1 or –1 in a box, but they wouldn't tell you which, but they were willing to tell you that "The number in the box squares to itself," then you could figure out that the number in the box was 1, because –1 doesn't do that.

The existence of these two ideas (the conjugate roots theorem and conjugation-as-automorphism) can't possibly be a coincidence; there must be some sense in which nonreal roots of real-coefficient polynomials come in conjugate pairs because the polynomial "can't tell" "which is which". But it would be unsatisfying to just say this much and nothing more ("Theorem: That can't possibly be a coincidence. Proof ...??"); we want to say something much more general and precise. And in fact, we can—

Say that \(L\) is a field, and that \(K\) is a field that lives inside \(L\), and that σ is a member of the group of field automorphisms of \(L\) that leave \(K\) alone (that is, map all members of \(K\) to themselves). Then we can show that

Theorem (generalized conjugate roots theorem). If \(z_0\) is a root of a polynomial with coefficients in \(K\), then σ(\(z_0\)) is too.

Proof. Let

and suppose \(P(z_0) = 0\). Then consider the value of \(P(\sigma(z_0))\). Precisely because σ respects multiplication, we have

and because σ doesn't disturb anything in \(K\), that's the same as

(because \(a\sigma(z) = \sigma(a)\sigma(z) = \sigma(az)\)), and because σ respects addition, that's also the same as

But

and σ(0) has to be zero for the automorphism to work. So \(P(\sigma(z_0))\) is zero, but that's what I've been trying to tell you this entire time.

What the utter novice finds brilliant and fascinating, the slightly-more-experienced novice finds obvious and boring.

When you're trying to think of cool things to do with a system, one of the obvious things to try is to abuse self-reference for all the world as if you were Douglas fucking Hofstadter—but it's not cool, precisely because it is so obvious, and you're not Douglas Hofstadter.

Once I made a Git repository and a Mercurial repository living in the same directory, tracking each other endlessly, one going out of date the moment you committed to the other ...

But that's not interesting.

You can run Emacs inside a terminal, and you can run a terminal inside Emacs—in fact, you can run two (M-x term, M-x ansi-term). Therefore you can run two instances of Emacs within Emacs. Each of those Emacsen could run some natural number of other nested Emacsen, and therefore (to a certain perverse sort of mind) could be said to represent that natural number, which I presume could be determined programmatically (via recursion). Two-counter machines are Turing-complete. So, in principle, if you didn't run out of memory, you could build a computer out of instances of Emacs running on your computer ...

But that's boring.

Judging by the comment moderation queue, this blog is wildly popular among a certain niche audience.

Namely, spambots. Although I can't help but wonder why spammers are so incompetent. Of course spammers have no reason to put any effort into the marginal comment or email. The reason spam exists is precisely because in a magical land of near-zero marginal cost (like the internet), the unscrupulous can afford to send sales pitches to a million people even if only fifteen bite. But that doesn't mean spammers couldn't put a little fixed-cost effort into improving their algorithm for generating those millions of spams. At least conventional advertising is occasionally entertaining; in contrast, most of the spam I see is just noise, to the extent that it once gave me an idea (which I would not implement; it's not my style) for a Reddit novelty account: "CompetentSpammer" would write eloquent, insightful comments that ever-so-subtly worked in references to charm bracelets and sketchy pharmaceuticals.

I know, it sounds as if I'm complaining, but I'm not: we are all grateful that spam is so easily distinguished from actual content; I was only wondering.

If you don't know what I'm talking about, some commentary on spam comments submitted to this blog is below the break—

Would-be commenter "charms" writes on "Summing the Multinomial Coefficients":

I adore thomas family funeral home! I got my initial couple as soon as i was initially 10 yrs old, the sunlight yellow quite short old classic.Now i'm 15 yrs old nowadays and also, since after that, I have got as well received your ebony quite short old classic, your bleak quite short old classic, [...]

And it goes on like that for another ninety words. One wonders: is anyone really going to buy shoes or whatever based on a blog comment like that? Maybe, maybe fifteen out of a million ... which I guess was the point. But again, one imagines that there would be a payoff to spammers for being more discriminating—I guess some them are. I got a few attempted comments referring to Zack Snyder, so someone's at least paying attention to the URL.

I even got one attempted comment that sort-of looks on topic, maybe, if you don't look too closely? "Alexey" writes on "Interpolating Between Vectorized Green's Theorems":

Great! I see how to finish it off now, and I see why given the dftierenfial equation and being told to look at F and f you would see that relation, but just introducing F in the first place well, I guess I just have to accept this proof is awesome. =DYou asked for topic areas: Have you ever seen Euler's proof that the number of partitions of a number into odd numbers equals that of a number into distinct numbers? That is a good one. Other than that, some Galois theory would be nice?

The comment throws around a lot of math terminology, but if it has any non-coincidental relationship to my post, I don't see it. And the URL supplied just goes to a near-empty Facebook profile. What's even the motive here? Maybe I'm wrong to think of this as "spam", when it could be a genuine math enthusiast who's confused, or bad at commmunicating in English? Who can say but that, in the end, what we really hate are low-quality comments, and we don't care whether or not they're trying to sell us something? (See also xkcd #810.)

Not specific enough.

"What?"

You claim that I'm an idiot. Well, sure; I already knew that. If you could point to some specific way in which my thinking is confused and explain how I might do better, then I would be quite grateful. But to just say that I'm stupid, without elaborating, doesn't seem helpful.

(Words are useful insofar as they summarize information about the world. If everyone involved already has a detailed predictive model of someone's various cognitive abilities, then it doesn't matter whether you describe them as an "idiot" or a "genius". As compared to what?)

I think I like the store-brand "sparkling water beverages"; they fill a similar niche as soda (which I never buy at the store, but have been known to occasionally consume at parties or restaurants), but seem like they ought to be less deadly.

I think the "More grains. Less you!" slogan on this box of cereal sounds sinister. I mean, they're probably just talking about weight loss, but still ...

I'm suspicious of processed food products shaped like cartoon characters, as if there are highly-placed cannibals at General Mills plotting to train children that it's okay to eat creatures that can talk. On the other hoof, these fruit-flavored snacks are delicious.

In this modern day and age, it simply cannot be doubted that it is of the very utmost importance that we find the size of the union of some sets. One might try just adding the sizes of all the sets, but that's not correct, because then one would be double-counting the elements that appear in more than one set. But it's a good start. One might then think that one could begin by adding the sizes of the sets, but then subtract the sizes of the intersections of each pair of sets, in order to correct for the double-counting. But this is also incorrect, because then what about the elements that appear in three sets and had thus initially been triple-counted?—after subtracting the pairwise intersections, these elements haven't been included in the count at all! So one realizes that one must then add the sizes of the triplewise intersections ...

And in one of the dark recesses of the human mind, untouched by outside light or sound, silent and unyielding to the invidious scrutiny of introspection and cognitive science—a conjecture is formed—

The size of the union of \(n\) sets is given by the alternating (starting from positive) sum of the sums of the sizes of all \(j\)-way intersections amongst the sets from \(j := 1\) to \(n\)! (N.b., the exclamation mark indicates an excited tone, not "factorial".)

This conjecture turns out to be entirely correct, as demonstrated in the following

Theorem (Inclusion–Exclusion Principle).

Proof. By induction.

(Basis.) \(|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|\)

(Induction.) We want to show that given that we can express a union of n sets using the proposed method, then we can do the same for a union of n+1 sets. From the basis, we can write:

Our inductive hypothesis says that the first term on the right side can be written as our proposed sum of appropriately signed sizes of intersections. Also, we can distribute the intersection-with-\(A_{n+1}\) over the union in the last term on the right side and then use the inductive hypothesis again to likewise rewrite that term as a sum of appropriately signed sizes of intersections. But then notice that we have all the terms we need, and that the signs are correct as well. So this is what I've been trying to tell you this whole time.

The sum of binomial coefficients

equals \(2^n\), because

is the number of ways to pick j elements from a set of size n, and \(2^n\) is the size of the powerset, the set of all subsets, of a set of size n: the sum, over all subset sizes, of the number of ways to choose subsets of a given size, is equal to the number of subsets. You can also see this using the binomial theorem itself:

But of course there's nothing special about two; it works for multinomial coefficients just the same. The sum, over all m-tuples of subset sizes, of the number of ways to split a set of size n into subsets of sizes given by the m-tuple, is equal to the number of ways to split a set of size n into m subsets (viz., mn).

I won't say I told you so except by means of apophasis.

Did you know that boats are useful for moving things over the water??