Andy Latto <andy.latto@pobox.com> wrote:

So there being no discussion on my fallacious proof other than discussion of rot13, ....

As has been mentioned, rot13 is a simple substitution cipher which maps the first half of the alphabet onto the second half and vice versa. It's intended, not for security, but for spoiler warnings and for other stuff that people may not want to see, e.g. offensive jokes. The fact that not everyone here was familiar with it is evidence that the Internet has grown so quickly that many are not familiar with Internet culture and conventions. (This is most evident in this mailing list by the prevalence of quoting in reverse order. You'd think it would be obvious that this is backwards, given that English is read top to bottom, not vice versa, but apparently not.) The longest words that remain words after being rot13'd are Chechen <-> Purpura. Rot13 has a period of two, meaning that encryption and decryption are the same operation. A period of N means that if you encrypt (or decrypt) N times, you'll get the original text back, but never any sooner (unless you avoid certain letters). What periods can simple substitution ciphers have on an alphabet of 26 letters? How many are there of each? In particular, what's the shortest period that doesn't exist, and what's the longest period that does? And how would you compute those for alphabets of other sizes? I'm especially interested in period-two, as I'm interested in bitwise palindromes, i.e. text that remains the same after having its bit pattern time-reversed. Of course the results depend on the choice of character code. Morse code works well, except that some letters don't have reverses. "Footstool" and "taint" are the two longest Morse code single-word palindromes. The old five-bit code, ITA2, often wrongly called Baudot, also works well. ASCII and EBCDIC, not so much. The five bit code seems tailor-made for palindromes. Space maps into itself. Every letter maps into a letter. Common letters map into common letters at a rate that can't possibly be coincidence. The most common letters in English language text, in order, are ETAOIN SHRDLU. The ITA2 palindrome mapping is E<->T, A<->O, I<->N, S<->H, R<->R, D<->L. As if this weren't remarkable enough, <CR> maps into <LF>, so the standard teletype linebreak sequence, <CR><LF>, maps into itself. A little online research explains this in two ways. One, wear on mechanical equipment was proportional to the number of 1 bits, so they were minimized by giving the most common characters the fewest 1 bits. Two, punched paper tapes were sometimes accidentally loaded reversed in one or both dimensions, and they wanted this to be at least somewhat recoverable. (Of course this means the letters are in a weird order if you arrange the codes in the usual binary sequence (E A SIU DRJNFCKTZLWHYPQOBG MXV). You can't have everything.) But suppose I wanted to design a character code for bitwise palindromes. Can I do even better? I don't just want to map common letters into common letters, I want to map common digrams, trigrams, etc. into common digrams, trigrams, etc. What would be a good algorithm? Would it be practical to simply have an automated search over all period-two substitution ciphers, searching each for palindromes? (Actually assigning bit patterns is unnecessary for this purpose. If, say, A maps into B, that means that the bit pattern of A is the time-reverse of the bit pattern of B, but says nothing about what either bit pattern actually is, except that that pattern itself can't be a palindrome.)