Thue-Morse Odiousness

Here is a baby puzzle. On Monday the baby said A, on Tuesday AU, on Wednesday AUUA, on Thursday AUUAUAAU. What will she say on Saturday?

You can see that this very gifted baby increases her talking capacity twice each day. The first half of what she says repeats her speech of the day before; and the second half is like the first half, but switches every A and U. If the baby continues indefinitely, her text converges to an infinite sequence that mathematicians call the Thue-Morse sequence (A010060). Of course, mathematicians use zeroes and ones instead of A and U, so the sequence looks like 0110100110010110100….

This sequence has many interesting properties. For example, if you replace every zero by 01 and every one by 10 in the Thue-Morse sequence, you will get the Thue-Morse sequence back. You can see that this is so if you code A in the baby’s speech by 01 and U by 10. Thus the Thue-Morse sequence is a fixed point under this substitution. Moreover, the only two fixed points under this substitution are the Thue-Morse sequence and its negation (A010059).

The Thue-Morse sequence possesses many other cool properties. For example, the sequence doesn’t contain substrings 000 and 111. Actually any sequence built from the doubles 01 and 10 can’t contain the triples 000 and 111 because we switch the digit after every odd-indexed term of such a sequence. A more general and less trivial statement is also true for the Thue-Morse sequence: it doesn’t contain any cubes. That is, it doesn’t contain XXX, where X is any binary string.

I stumbled upon this sequence when I was playing with evil and odious numbers invented by John H. Conway. A number is evil if the number of ones in its binary expansion is even, and odious if it’s odd. We can define a function, called the odiousness of a number, in the following way: odiousness(n) is one, if n is odious and 0 otherwise. We can apply the odiousness function to a sequence of non-negative integers term-wise. Now I can describe the Thue-Morse sequence as the odiousness of the sequence of non-negative numbers. Indeed, the odiousness of the number 2n + k is opposite of the odiousness of k, if k is less than 2n. That means if we already know the odiousness of the numbers below 2n, the next 2n terms of the odiousness sequence is the bitwise negation of the first 2n terms. So odiousness is built the same way as the Thue-Morse sequence, and you can easily check that the initial terms are the same too.

Let me consider as an example the sequence which is the odiousness of triangular numbers A153638: 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0…. What can we say about this sequence? We can say that the number of zeroes is infinite, as all the terms with indices of the form 2n-1(2n+1) are zeroes. Also, the number of ones is infinite because all the terms with indices of the form 22n-1(22n-1-1) are ones.

Obviously, we can define the evilness of a number or of a sequence with non-negative terms. Namely, the evilness of a number is 1 if the number is evil, and 0 if it is not. The evilness is the bitwise negation of the odiousness. The evilness of the sequence of non-negative integers is the negation of the Thue-Morse sequence. The odiousness sequence of any sequence of zeroes and ones is the sequence itself, and the evilness sequence is its negation.

I would like to define an inverse odiousness operation on binary sequences. Many different sequences can have the same odiousness sequence. In such a case mathematicians usually define the inverse operation as a minimal non-negative sequence whose odiousness is the given sequence. Obviously, the minimal inverse of a binary sequence is the sequence itself, and thus not very interesting. I suggest that we define the inverse as a minimal increasing sequence. In this case the odiousness inverse of the Thue-Morse sequence is the sequence of non-negative numbers.

For example, let me describe the inverse odiousness of the sequence of all ones. Naturally, all the numbers in the sequence must be odious, and by minimality property this is the sequence of odious numbers A000069: 1, 2, 4, 7, 8, 11, 13, 14, 16, 19…. Analogously, the odiousness inverse of the sequence of all zeroes is the sequence of evil numbers A001969: 0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20….

Let us find the odiousness inverse of the alternating sequence A000035: 0, 1, 0, 1, 0, 1…. This is the lexicographically smallest sequence of numbers changing putridity. By the way, “putridity” is the term suggested by John Conway to encompass odiousness and evilness the same way as parity encompasses oddness and evenness.

The odiousness inverse of the alternating sequence is the sequence A003159: 0, 1, 3, 4, 5, 7, 9, 11, 12, 13…. By my definition we can describe this sequence as indices of terms of the Thue-Morse sequence that are different from the previous term. This sequence can be described in many other ways. For example, the official definition in the OEIS is that this sequence consists of numbers whose binary expansion ends with an even number of zeroes. It is fun to prove that this is the case. It is also fun to show that this sequence can be built by adding numbers to it that are not doubles of previous terms.

Let us look at the first differences of the previous sequence. This is the sequence A026465: 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2… — the length of n-th run of identical symbols in the Thue-Morse sequence. As we know that the Thue-Morse sequence doesn’t contain three ones or three zeroes in a row, we can state that the terms of this sequence will continue to be ones or twos.

You can define putridity sequences for any non-negative sequence. Which of them are interesting? I do not know, but I know which of them are not very interesting. For example, the putridity of pronic (oblong) numbers sequence is the same as the putridity of the triangular numbers sequence. This is because pronic numbers are twice triangular numbers and putridity is independent of factors of two. Another uninformative putridity sequence is the odiousness of the powers of two. This sequence consists only of ones.

I bet that my readers can find putridity sequences that are interesting.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

6 Comments

  1. Ctibor O. Zizka:

    Dear Tanya,

    the “classic” Thue-Morse seq. can be expressed as a(n)=S2(n)mod 2, where S2(n) = sum of digits of n, n in base-2 notation. A year ago I was looking on the more general case :
    Let Sk(n) = sum of digits of n; n in base-k notation. Let F(t) be some arithmetic function.
    Then a(n)= F(Sk(n)) mod m is a generalised Thue-Morse sequence.
    Nice properties have sequences where F(Sk(n))=floor(Q*Sk(n)); Q is a positive rational number.

    Partial sums of a generalized Thue-Morse sequence a(n)=F(Sk(n)) mod m are fractal –> they consist of series of the generalized batrachion Blancmange function (similarly to Hofstadter’s Q-Sequence, Hofstadter-Conway 10000$ and Mallows seq. etc.). A good article is http://arxiv.org/PS_cache/math/pdf/0406/0406078v1.pdf which mirrors my computational results from an ergodic/Pascal-adic transformation point of view. Partial sums of such generalized Thue-Morse seq. also points to the Minkowski Question Mark function and relates the continued-fraction representation of the real numbers to their k-ary expansion http://arxiv.org/PS_cache/arxiv/pdf/0810/0810.1265v2.pdf.

    I do not know if my note is of interest for you,

    Have a nice day,

    Ctibor

  2. David Wilson:

    Grudgingly, I have to concede that John Conway’s word “putridity” is indeed a word. However, I much prefer the older and more time-honored synonym which I recall as the closing word of Edgar Allan Poe’s tale “The Facts in the Case of M. Valdemar”:

    “Upon the bed, before the whole company, there lay a nearly liquid mass of loathsome——of detestable putrescence.”

    The distastefulness of the subject notwithstanding, don’t you find “putrescence” a much more lilting word than “putridity”?

    🙂

  3. Ingrid Daubechies:

    Parity of a number tells us whether it is even or odd; why not name “perfidy” the property that describes whether a number is evil or odious?

  4. Tanya Khovanova:

    I received a letter from John Conway in reply to Ingid’s suggestion of “perfidy”:

    MUCH BETTER!

    In fact it’s better in two ways – closer still to “parity,” AND a better fit with “evil” and “odious”! Gets my vote right off. JHC

  5. Are you game? (Part II – Numbers are evil! … at least some of them are … others are odious!) « Thesquaredcircle:

    […] called this property putridity. On Tanya Khovanova’s Math blog in a blog entry called Thue-Morse Odiousness, Ingrid Daubechies suggested in a comment that the more appropriate name would be perfidy – a […]

  6. Tanya Khovanova’s Math Blog » Blog Archive » On the Perfidy of Negative Numbers:

    […] Perfidy is to parity as odious is to odd and evil is to even. As a reminder, odious numbers are numbers with an odd number of ones in their binary expansions. From here you can extrapolate what the evil numbers are and the fact that the perfidy of an integer is the parity of the number of ones in its binary expansion. We live in a terrible world: all numbers are perfidious. […]