Thue–Morse sequence

Thue–Morse sequence
5 logical matrices that give the beginning of the T.-M. sequence, when read line by line

Either in set A (vertical index) or in set B (horizontal index)
is an odd number of elements.
This graphic demonstrates the repeating and complementary makeup of the Thue–Morse sequence.

In mathematics, the Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is a binary sequence that begins:

0 1 10 1001 10010110 1001011001101001.... (sequence A010060 in OEIS)

Any other ordered pair of symbols may be used instead of 0 and 1; the logical structure of the Thue–Morse sequence does not depend on the symbols that are used to represent it.

Contents

Definition

There are several equivalent ways of defining the Thue–Morse sequence.

Direct definition

To compute the nth element tn, write the number n in binary. If the number of ones in this binary expansion is odd then tn = 1, if even then tn = 0. For this reason John H. Conway et al. call numbers n satisfying tn = 1 odious numbers and numbers for which tn = 0 evil numbers.

Recurrence relation

The Thue–Morse sequence is the sequence tn satisfying

t0 = 0,
t2n = tn, and
t2n+1 = 1−tn.

for all positive integers n.

L-system

The Thue–Morse sequence is the output of the following Lindenmayer system:

  variables  0  1
  constants  none
  start      0
  rules      (0 → 01), (1 → 10)

Characterization using bitwise negation

The Thue–Morse sequence in the form given above, as a sequence of bits, can be defined recursively using the operation of bitwise negation. So, the first element is 0. Then once the first 2n elements have been specified, forming a string s, then the next 2n elements must form the bitwise negation of s. Now we have defined the first 2n+1 elements, and we recurse.

Spelling out the first few steps in detail:

  • We start with 0.
  • The bitwise negation of 0 is 1.
  • Combining these, the first 2 elements are 01.
  • The bitwise negation of 01 is 10.
  • Combining these, the first 4 elements are 0110.
  • The bitwise negation of 0110 is 1001.
  • Combining these, the first 8 elements are 01101001.
  • And so on.

So

  • T0 = 0.
  • T1 = 01.
  • T2 = 0110.
  • T3 = 01101001.
  • T4 = 0110100110010110.
  • T5 = 01101001100101101001011001101001.
  • T6 = 0110100110010110100101100110100110010110011010010110100110010110.
  • And so on.

Infinite product

The sequence can also be defined by:

 \prod_{i=0}^{} (1 - x^{2^{i}}) = \sum_{j=0}^{\infty} (-1)^{t_j} x^{j} \mbox{,} \!

where tj is the jth element if we start at j = 0.

Some properties

Nested squares generated by successive iterations of Thue–Morse.

Because each new block in the Thue–Morse sequence is defined by forming the bitwise negation of the beginning, and this is repeated at the beginning of the next block, the Thue–Morse sequence is filled with squares: consecutive strings that are repeated. That is, there are many instances of XX, where X is some string. However, there are no cubes: instances of XXX. There are also no overlapping squares: instances of 0X0X0 or 1X1X1.

Notice that T2n is palindrome for any n > 1. Further, let qn be a word obtain from T2n by counting ones between consecutive zeros. For instance, q1 = 2 and q2 = 2102012 and so on. The words Tn do not contain overlapping squares in consequence, the words qn are palindrome squarefree words.

The statement above that the Thue–Morse sequence is "filled with squares" can be made precise: It is a recurrent sequence, meaning that given any finite string X in the sequence, there is some length nX (often much longer than the length of X) such that X appears in every block of length n. The easiest way to make a recurrent sequence is to form a periodic sequence, one where the sequence repeats entirely after a given number m of steps. Then nX can be set to any multiple of m that is larger than twice the length of X. But the Morse sequence is recurrent without being periodic, not even eventually periodic (meaning periodic after some nonperiodic initial segment).

One can define a function f from the set of binary sequences to itself by replacing every 0 in a sequence with 01 and every 1 with 10. Then if T is the Thue–Morse sequence, then f(T) is T again; that is, T is a fixed point of f. In fact, T is essentially the only fixed point of f; the only other fixed point is the bitwise negation of T, which is simply the Thue–Morse sequence on (1,0) instead of on (0,1). This property may be generalized to the concept of an automatic sequence.

In combinatorial game theory

The set of evil numbers (numbers n with tn = 0) forms a subspace of the nonnegative integers under nim-addition (bitwise exclusive or). For the game of Kayles, the evil numbers form the sparse space—the subspace of nim-values which occur for few (finitely many) positions in the game—and the odious numbers are the common coset.

The Prouhet–Tarry–Escott problem

The Prouhet–Tarry–Escott problem can be defined as: given a positive integer N and a non-negative integer k, partition the set S = { 0, 1, ..., N-1 } into two disjoint subsets S0 and S1 that have equal sums of powers up to k, that is:

 \sum_{x \in S_0} x^i = \sum_{x \in S_1} x^i for all integers i from 1 to k.

This has a solution if N is a multiple of 2k+1, given by:

  • S0 consists of the integers n in S for which tn = 0,
  • S1 consists of the integers n in S for which tn = 1.

For example, for N = 8 and k = 2,

0 + 3 + 5 + 6 = 1 + 2 + 4 + 7,
02 + 32 + 52 + 62 = 12 + 22 + 42 + 72.

The condition requiring that N be a multiple of 2k+1 is not strictly necessary: there are some further cases for which a solution exists. However, it guarantees a stronger property: if the condition is satisfied, then the set of kth powers of any set of N numbers in arithmetic progression can be partitioned into two sets with equal sums. This follows directly from the expansion given by the binomial theorem applied to the binomial representing the nth element of an arithmetic progression.

Fractals and Turtle graphics

A Turtle Graphics is the curve that is generated if an automaton is programmed with a sequence. If the Thue–Morse Sequence members are used in order to select program states:

  • If t(n) = 0, move ahead by one unit,
  • If t(n) = 1, rotate counterclockwise by an angle of π/3,

the resulting curve converges to the Koch snowflake, a fractal curve of infinite length containing a finite area. This illustrates the fractal nature of the Thue–Morse Sequence.

History

The Thue–Morse sequence was first studied by Eugène Prouhet in 1851, who applied it to number theory. However, Prouhet did not mention the sequence explicitly; this was left to Axel Thue in 1906, who used it to found the study of combinatorics on words. The sequence was only brought to worldwide attention with the work of Marston Morse in 1921, when he applied it to differential geometry. The sequence has been discovered independently many times, not always by professional research mathematicians; for example, Max Euwe, a chess grandmaster, who held the world championship title from 1935 to 1937, and mathematics teacher, discovered it in 1929 in an application to chess: by using its cube-free property (see above), he showed how to circumvent a rule aimed at preventing infinitely protracted games by declaring repetition of moves a draw.

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Thue-Morse sequence — See also: Thue Morse constantIn mathematics and its applications, the Thue Morse sequence, or Prouhet Thue Morse sequence, is a certain binary sequence whose initial segments alternate (in a certain sense).The Thue Morse sequence begins:0… …   Wikipedia

  • Generalised Morse sequence — In mathematics and its applications, the Generalized Morse sequence, or Generalized Thue Morse sequence, is a certain integer sequence. It has many properties of the binary Prouhet Thue Morse sequence and can thus be called its generalization:… …   Wikipedia

  • Sucesión de Thue-Morse — La sucesión de Thue Morse (también conocida como sucesión de Prouhet Thue Morse) es una sucesión de dígitos binarios que si se concatenan produce una secuencia con segmentos iniciales alternos. Contenido 1 Definición 2 Algunas propiedades 3… …   Wikipedia Español

  • Suite Prouhet-Thue-Morse — Suite de Prouhet Thue Morse En mathématiques et ses applications, la suite de Prouhet Thue Morse (appelé souvent suite de Thue Morse chez les anglo saxons) est une certaine suite binaire. Elle commence par : 0 1 10 1001 10010110… …   Wikipédia en Français

  • Suite de prouhet-thue-morse — En mathématiques et ses applications, la suite de Prouhet Thue Morse (appelé souvent suite de Thue Morse chez les anglo saxons) est une certaine suite binaire. Elle commence par : 0 1 10 1001 10010110 1001011001101001... (Les espaces ne sont …   Wikipédia en Français

  • Suite de Prouhet-Thue-Morse — En mathématiques, en informatique théorique, en combinatoire des mots et ses applications, la suite de Thue Morse (appelée souvent suite de Prouhet Thue Morse chez les francophones) est une suite binaire. Elle commence par : t =… …   Wikipédia en Français

  • Prouhet–Thue–Morse constant — In mathematics and its applications, the Prouhet Thue Morse constant is the number au whose binary expansion .01101001100101101001011001101001... is given by the Prouhet Thue Morse sequence. That is,: au = sum {i=0}^{infty} frac{t i}{2^{i+1 =… …   Wikipedia

  • Constante De Prouhet-Thue-Morse — En mathématiques et dans ses applications, la constante de Prouhet Thue Morse est le nombre dont le développement binaire est la suite de Prouhet Thue Morse. C’est à dire, où ti est la suite de Prouhet Thue Morse. La série génératrice pour ti est …   Wikipédia en Français

  • Constante de prouhet-thue-morse — En mathématiques et dans ses applications, la constante de Prouhet Thue Morse est le nombre dont le développement binaire est la suite de Prouhet Thue Morse. C’est à dire, où ti est la suite de Prouhet Thue Morse. La série génératrice pour ti est …   Wikipédia en Français

  • Constante de Prouhet-Thue-Morse — En mathématiques et dans ses applications, la constante de Prouhet Thue Morse est le nombre dont le développement binaire est la suite de Prouhet Thue Morse. C’est à dire, où ti est la suite de Prouhet Thue Morse. La série génératrice pour ti est …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”