Watch Your Back, Git

Changeset evolution is a big deal.  But nobody seems to be talking about it.  Well, except for this guy:

But even he says it's a small set of incremental improvements.  This is not small.  But it is all a little abstract right now.  Let's write a use case.

The Great Picard Theorem

The great Picard theorem states that, if an analytic function contains an essential singularity, then within any punctured neighborhood of the singularity, the function takes on every value with at most a single exception.

"Studies have shown..."

We've all been told that "studies have shown" something at one time or another.  Sometimes, our interlocutor is kind enough to give us a citation (and sometimes they aren't).  Well, let's do a thought experiment (if you're already familiar with significance testing, feel free to skim the next paragraph).

Suppose you give 20 labs a drug and a placebo, and tell them to test one against the other in clinical trials.  But instead of actually giving them a drug and a placebo, you give them two identical placebos (originally, I was going to use a homeopathic remedy vs. a placebo, but I didn't want to get sidetracked).  Assume the labs all use large sample sizes, statistical normalization, double blinding, and various other best practices.  None of them make any mistakes (or outright fraud, for that matter) and they all conduct proper, well-designed experiments.  Even under these ideal conditions, one of those labs (on average, and for pedants, we're assuming they all use α=5%) will tell you there's a statistically significant difference between the placebo and itself.

Nihilism and optimism

meaning

n. the end, purpose, or significance of something

NB: Emphasis added.

Consider the definition given above by Dictionary.com. We're told the meaning of something is its purpose.  If a thing has a purpose, that purpose must have been intended by someone.  If we're told something has "inherent meaning," we must ask from whence this intent comes.  There doesn't seem to be an obvious answer to this question.

The tragedy of music: part three

In part one, we discussed some issues with Pythagorean tuning, and in part two we continued to quarter-comma meantone.  The logical conclusion is equal temperament, a widely used (though not quite universal) modern system.

Equal temperament is, in a way, simpler than any of the earlier systems.  Instead of building an octave out of some fixed ratio, we start with an octave and subdivide it.  The most natural way to do this is to make a semitone the twelfth root of two.  Note that this is simply "a semitone" rather than a chromatic or diatonic semitone; in equal temperament, those are the same thing.  Everything else can be built rather easily out of this fundamental unit, and we don't have overlapping or separated octaves.  This, in turn, means no wolf fifth.

Still, this fundamental unit can be unwieldy.  Writing out "the twelfth root of two" all the time is annoying, and the mathematical notation for it is rather ugly.  For this purpose, the so-called cent was invented.  There are 1200 cents in an octave; 100 make up a semitone.  It is a logarithmic unit.  Increasing a tone by 1200 cents means doubling its frequency.  700 cents make up a perfect fifth, and 400 cents are a major third.  The cent is a unit of relative measure; it is not meaningful to equate a single note to a given number of cents, except in relation to another note.  That "other note" is often middle A, which, for convenience, is typically tuned to 440 Hz.

This system is very practical, which accounts for its widespread use.  However, this is not a happy story with a happy ending; there is a problem.  The twelfth root of two is an ugly, irrational number, and all of the other intervals are powers of it.  There are no simple integer ratios at all.  While the cent may make the system look nice and clean, it is an artificial unit created to hide the irrational semitone.  In effect, we've taken the sourness of the wolf fifth and extended it over the whole octave, spreading thinly to mask the dissonance.  Practical this may be, but ideal it is not.

This leads me to a stark realization: the Platonist's ideal of "perfect yet unattainable" forms is inapplicable to music.  These problems are not of a physical nature.  Any musical system will suffer from them, except for the trivial system which has one note per octave.  There is a fundamental disconnect between equal temperament and just intonation.  We cannot have both, even in theory.  And that is the tragedy I've been talking about.

The tragedy of music, part two

In part one, we discussed Pythagorean tuning and its failings.  Despite this crucial issue, Pythagorean tuning was highly influential on musical theory.

In the 1500's, a variant of Pythagorean tuning called quarter-comma meantone became popular.  The "comma" in this name is not the Pythagorean comma we saw last time, but an entirely different comma.

A major third is an interval spanning three staff positions and four semitones.  It is not considered "perfect" in the same way as the perfect fifth, but is still regarded as a consonant interval, at least in theory.  Under Pythagorean tuning, the major third was a rather dissonant 81:64.  Quarter-comma meantone flattened this to a nicer 5:4, at the expense of a more dissonant perfect fifth.

Interestingly, we now have irrational intervals: the perfect fifth is the fourth root of 5.  This way, if we move up by four perfect fifths, and down by two octaves, we end up at 5:4, the justly-intoned major third.

This sort of trade-off is debatable, of course, but it was an explicit design goal of quarter-comma meantone; the flatter fifth was viewed as an acceptable price for a just third.

Now, suppose we start at middle C, as we did last time, and move up a major third.  We arrive at middle E at a ratio of 5:4.  Next we move up again to G♯, at a ratio of 25:16.  Finally, we get to C₅, at a ratio of 125:64.  This is not an octave, but unlike in Pythagorean tuning, the interval is too flat rather than too sharp.  This means there's a gap between the octaves, unlike the overlapping octaves of Pythagorean tuning.

Like in Pythagorean tuning, one of the fifths must span this gap.  That fifth is sharpened by 128:125, a much larger interval than the Pythagorean comma.  It sounds extremely dissonant, to the point that it became known as the "wolf fifth" because it sounds like a wolf howling at the moon.  This moniker is sometimes also applied to the diminished sixth produced by Pythagorean tuning under the equivalent problem, but note that quarter-comma meantone is much worse in this regard.

Updated: In part three, we discuss modern equal temperament.

The tragedy of music, part one

Once upon a time, people noticed that certain sounds are pleasant to hear, while others are not.  They began to experiment with it.  The most important early discovery in this vein was the notion that sound is vibration.  This is the fundamental principle of all musical theory, modern or ancient.  The next discovery was that of the octave: If you make two vibrations, one at double the frequency of the other, they sound... the same, in some way.  The faster one is clearly higher pitched, but they're harmonically equivalent.

The Ancient Greeks built upon this discovery, and eventually produced what we now call Pythagorean tuning.  Pythagorean tuning is built around simple frequency ratios; systems like this are called "just intonations."  The most important ratio other than the octave is the so-called "perfect fifth," which describes a gap of five staff positions in modern musical notation.  It spans a gap of seven semitones; there are a total of twelve semitones per octave in "conventional" systems such as Pythagorean tuning.  In Pythagorean tuning, a perfect fifth is a ratio of 3:2, meaning the faster vibration oscillates thrice for every two oscillations of the slower vibration.  So far, this is all very nice, and fits in well with the Pythagorean mathematical ideals of rationality.  But there's a problem.  I told you that a perfect fifth has a ratio of 3:2, is composed of seven semitones, twelve of which make up an octave, and the octave is 2:1.  Suppose we start at middle C (or C₄), and move a perfect fifth up.  We arrive at G₄, at 3:2 times our original frequency.  We continue to D₅, at 9:4.  Next comes A₆, at 27:8.  Then E₆, at 81:16, B₇, at 243:32, F♯₇, at 729:64, C♯₈, at 2187:128, and finally G♯₈ at 6561:256.  Now suppose we go down from C₄.  We find ourselves at F₃ at 2:3, B♭₃ at 4:9, E♭₂ at 8:27, and A♭₁ at 16:81.  The ratio from C₄ to A♭₁ is 81:16, and the ratio from G♯₈ to C₄ is 6561:256.  Multiplying, we see that the ratio from G♯₈ to A♭₁ is 531441:4096.  But A♭ and G♯ are supposed to be the same note.  Going by octaves, we should get 128:1.  The other ratio is rather large and unwieldy, because we have seven octaves of space, so if we divide those out, we get a ratio from G♯ to A♭ of precisely 531441:524288.  This interval is called the Pythagorean comma.  It's the difference (remember, in music, we never add or subtract frequencies, so this is actually the ratio) between a chromatic and a diatonic semitone, among other things.

So what does this actually mean?  It means Pythagorean octaves overlap, if only a little, since G♯ is a little sharper than A♭.  That's a problem for perfect fifths.  One of the twelve "perfect" fifths is ruined by spanning this overlap, being flattened to a rather dissonant diminished sixth.  So Pythagorean tuning, for all its beauty and simplicity, is not perfect.

Updated: In part two, we discuss quarter-comma meantone, a derivative of Pythagorean tuning.

One-time pads with Python

A one-time pad is a kind of unbreakable encryption.  For most encryption, breaking it is a matter of throwing a lot of computational resources at the problem.  Typically, the amount of resources needed greatly exceeds the amount that is practical to obtain, so most modern cryptography is secure enough.  There are, however, some downsides to modern cryptography, the biggest of which is its complexity.  If we want to use crypto for something like bank transactions, complexity is not that big of a deal, because centralization can hide most of the complexity from end-users.  But if, for instance, you need to implement secure communications without a centralized certificate authority, effectively implementing secure communications becomes a lot harder.

The notepad.exe problem

Quite a long time ago, there was a minor stir over notepad's treatment of text encodings. So many people talked about this that Raymond Chen even got in on the action (twice). As a Linux user, I honestly have no idea whether Microsoft ever got around to fixing this (Raymond's post suggests they consider it impossible to "fix" as such). I'm not really interested in bashing them for using an imperfect algorithm, since, to be honest, you'll never get perfection with this issue. But I do think it provides an interesting framework for a math problem.

Technically, ANSI is Windows-1252 (well, technically the term "ANSI" is wrong, but nobody cares), but in practice I think it's most commonly used as ASCII, in which case it's really equivalent to UTF-8. Now, I know that technically there are probably quite a lot of files out there with non-ASCII symbols encoded as 1252, but honestly, if you're trying to detect 1252 automatically, you've already lost since there are only 5 invalid code points; this means that if you feed totally random data into an ANSI decoder, it will take, on average, 50 bytes before the decoder complains of an invalid code point. This means that it's very likely to accept short runs of totally random data

One thing I notice is that, while Raymond says (implies, probably unintentionally) the string is ANSI, it's also perfectly good UTF-8, and will even produce the same interpretation in UTF-8 as in ANSI. This is, of course, because they're both backwards compatible with ASCII, which is what our string really is. Now, it's difficult to figure out the probability of random data being valid UTF-8 since UTF-8 is variable length. But I would say that it's rather unlikely since valid UTF-8 has quite a few constraints on its behavior: each leader byte must be followed by exactly the right number of continuation bytes, and overlong sequences are also disallowed. Then you look at Unicode itself and find that certain sequences (U+FFFF, for instance) are illegal.

UTF-16, on the other hand, is a much denser representation. Most 2 byte sequences are legal, unless they happen to form an invalid surrogate pair or result in an illegal code point (again, U+FFFF and friends). Now, the "illegal code point" problem is common to both encodings, so we can ignore it for our purposes (though technically, I suppose UTF-8 has the code points U+D800 to U+DFFF illegal, which UTF-16 can't even represent). But how likely is it that you get an invalid surrogate? Well, the likelihood of a random 16-bit value being (say) a leading surrogate is 1/64, since the first 6 bits are constrained (so you get 2^-6). This is the same for a trailing surrogate. Now we need the probability of a leading surrogate followed by something which is not a trailing surrogate, or a trailing surrogate followed by anything. Well, if we crunch the numbers, we find that it takes about 31 2-byte values, or 62 bytes, before you encounter an invalid surrogate pair in random data. This is actually worse than ANSI. However, that's not a valid comparison since we've been ignoring the invalid code points problem (which is different in ANSI). But there aren't a whole lot of "defined invalid" characters in the Unicode spec, so this only reduces the count a little (remember, the "reserved" U+D800 to U+DFFF cannot be safely represented in UTF-16; that's why they're reserved. Any attempt to do so will produce a (possibly illegal) surrogate pair, which we've already covered).

Earlier I said it's difficult to find the probability for UTF-8. I could, however, find the probability for a discrete code-point being invalid. This is less useful since it's not measured in bytes, but it will at least tell us how many characters your decoder will emit before it yells at you. So an invalid UTF-8 "character" is any of the following:

1. Begins with 0b10 (begins with a continuation byte, or the previous character has too many continuations). (p=1/4)
2. Begins with 0b110, but the next byte doesn't begin with 0b10. (p=3/32)
3. Begins with 0b1110, but either (or both!) of the next two bytes doesn't begin with 0b10. (p=15/256)
4. Begins with 0b11110, but any of the next 3 bytes isn't a continuation. (p=63/2048)
5. Begins with 0b11111 (too long). (p=1/32)
6. Begins with a valid leader byte, but the file ends before the requisite number of continuations have appeared. (p is impossible to calculate without knowing more about the file)

These possibilities are mutually exclusive (except for 6). We've ignored the issue of overlong encodings (other than 5; things beginning with 0xC0 and 0xC1) because they're difficult to account for (they unpleasantly overlap with 2)  and many decoders will silently allow them anyway, as they're unambiguous. If we assume the random data is long enough to avoid 6, we get P=91/2048. So your decoder will emit, on average, one character before it notices something illegal; this is equivalent to "no more than 4 bytes" since there's at most 4 bytes in a UTF-8 character. This is why UTF-8 is not supposed to need a BOM: it is very discriminating already, and it's highly unlikely for random data to be accepted as valid UTF-8. Just look at the PDF chart: after 3 characters (at most 12 bytes), random data has less than a 10% chance of being accepted. Of course, real data is seldom random, so applying this to IsTextUnicode is iffy at best. All this tells us is that, ceteris paribus, UTF-8 is much more likely to reject something which isn't UTF-8 than the other encodings.

So where does this leave us? Well, in my opinion, it leaves us with the conclusion that ANSI should be scrapped since it's both undiscriminating and BOM-less, making it rather difficult to autodetect; furthermore, UTF-8 provides ASCII-compatibility and a much more diverse character set. But Microsoft obviously can't do that since there are a lot of ANSI files floating around and people would be mildly annoyed if they had to be converted (seriously: because lots of legacy programs use ANSI and Microsoft hates breaking such programs, which cannot be easily converted (unlike text files); furthermore, I'm not a Windows programmer, but I don't think the ANSI interface is deprecated in the first place!).

I suppose it also suggests that Microsoft consider UTF-8 before other encodings, but as Raymond Chen said, "[N]o matter how you decide to resolve the ambiguity, somebody will win and somebody else will lose"; there's no general solution to this problem. And as we said before, real data may not follow the probability distributions that random data does.

Truth in turnstiles

We're often told that "logic" is at the heart of mathematics. We're told that you cannot do math without logic, that mathematics requires it. Personally, I subscribe to the view of formalism, which basically says that math is the manipulation of symbols according to rules. Do we need full-blown propositional logic to manipulate symbols? I hope not.

We need to decide what we mean by "logic." There are a lot of different kinds, believe it or not, and it's not just a matter of expressive power. Alternative logics often entirely disagree with "classical" or typical logic. For instance, paraconsistent logic will tolerate a contradiction without going nuts, and relevance logic takes perhaps a more intuitive approach to material implication, though it's also more complex. When we say "logic," we often mean classical logic, but I honestly cannot see why it should be privileged over other logics. Classical logic is more intuitive than paraconsistent logic, but at the cost of increased complexity (and fragility). On the other hand, it's less intuitive than relevance logic, for the sake of simplicity. Now, maybe this is a happy medium along a spectrum of intuition versus simplicity. But it seems to me that if you're building the foundation of mathematics, you'll favor simplicity over intuition; a happy medium isn't your goal.

The foundation of mathematics, in truth, is entailment, represented by the turnstile. Entailment basically means "given some statements (which look like) X, you can prove another statement (which looks like) Y." Note that this is very different from material implication, which isn't even meaningful at this level (because we haven't even picked a logic yet, let alone laid out its axioms). The actual axioms you're working with can then be defined using the turnstile. Those axioms are often logical in nature, to lay a strong foundation for other mathematical principles (such as ZFC), but there's no requirement that we use logic at this stage. You could, for instance, define the rules of untyped lambda calculus (which are themselves fairly simple) using only the turnstile, and then you would have a Turing-complete system that was defined without logic at all!

So where does this leave us? Different logics have different uses, and we can pick which one we want or need on a case-by-case basis. The turnstile is used to formalize this detachment, making it a framework for choosing a logical system. But we should remember that, technically, we don't need to use a logical system at all. It just happens to be quite convenient to do so.