How to generalize the Thue-Morse sequence to more than two symbols?
The Thue-Morse sequence is defined as a binary sequence and can be generated like
0, 01, 01 10, 01 10 10 01, 01 10 10 01 10 01 01 10, ... .
So the second half of the series is always the binary complement of the first half of the series.
But is there a way to generate an analogous ternary sequence? Intuitively my first guess for a ternary Thue-Morse sequence was like
0, 01, 012, 012 120, 012 120 120 201, 012 120 120 201 120 201 201 012, ...
So here the second half of the series is the "ternary complement" (rotation $0 \to 1, 1 \to 2, 2 \to 0 $ instead of $0 \to 1, 1 \to 0 $) of the first half.
But it could also be
0, 01, 012, 012 120 201, 012 120 201 120 201 012 201 012 120, ...
Here the second third is the "ternary complement" of the first third and the third third is the "ternary complement" of the second third.
Does any of my constructions for a ternary Thue-Morse series make sense?
Is there maybe a unique way to generate an analogous ternary sequence?
And how to construct n-ary versions of the Thue-Morse series in general?
It's $0, 012, 012 120 201, 012 120 201 120 201 012 201 012 120, ...$
To easily construct the Thue-Morse sequence, you can do the following:
Start with $0$; Replace $(0\to01)$ and $(1\to10)$. So you get: $$0, 0 1, 01 10, 0110 1001, 01101001 10010110,...$$
To easily construct the ternary version of Thue-Morse sequence, you can do the following:
Start with $0$; Replace $(0\to012), (1\to120), (2\to201).$ So you get: $$0, 0 1 2, 012 120 201, 012120201 120201012 201012120$$
To easily construct the $4$-ary version of Thue-Morse sequence, you can do the following:
Start with $0$; Replace $(0\to 0123), (1\to 1230), (2\to2301), (3\to3012).$ So you get: $$0, 0 1 2 3, 0123 1230 2301 3012, 0123123023013012 1230230130120123 2301301201231230 3012012312302301$$
To easily construct the $n$-ary version of Thue-Morse sequence, you can do the following:
Start with $0$; Replace
$$(0\to012\cdots[n-2][n-1]n), (1\to123\cdots[n-1]n0),$$
$$(2\to234\cdots n01),$$
$$\dots$$
$$(n\to n01\cdots[n-3][n-2][n-1]).$$
To find out a particular number n for b symbols, convert the number to base b, sum the digits, and then modulo by b.
For example, you have two symbols, 0 and 1, and you want to find out what the fifteenth place in this sequence would be. Convert 14 (14 is the fifteenth number since this sequence starts with 0) to base two (the number of symbols), it's 1110. Sum the digits, it's 3. Take 3 modulo two (again, the number of symbols). It's 1. So the fifteenth place in the binary Thue-Morse sequence is 1.
If you have four symbols, 0 and 1 and 2 and 3, and you want to find out the twelfth place in the sequence. Convert 11 to base four, it's 23. Sum the digits, it's 5. Five modulo four is 1, so the twelfth place in the quaternary Thue-Morse sequence is also 1.
That was my own discovery back in 2016.
I knew about
T(2n) = T(n)
T(2n+1) = not T(n)
I saw that
T(2n+1) = not T(n) = (T(n)+1) modulo 2.
and thought that one possible generalization for other numbers of symbols could be:
T(bn) = T(n)
T(bn+y) = (T(n)+y) modulo b
where y is lower than b.
Here is a shellscript that prints 0 to $1 iterations where $p is the amount of symbols.
#!/bin/sh
p=6
for i in `seq 0 $1`
do
echo -n "$(echo "${p}o${i}f"|dc|sed 's/\(.\)/\1 /g') [+lbx]sa[2z>a]dsbx${p}%n"|dc
done
echo
There is another road to arrive at such a generalization using polynomials in $x$ arriving at formal power series in the limit.
Consider the geometric series $f_0(x)=1+x+x^2+x^3 + ... $. That series can be rewritten as an infinite product
$$ f_0(x) = (1+x)(1+x^2)(1+x^4)(1+x^8)... = \prod_{k=0}^\infty (1+x^{2^k}) \tag {1.1}
$$
If we consider now to replace each $+$-sign by the $-$-sign we get
$$ f_1(x) = (1-x)(1-x^2)(1-x^4)(1-x^8)... = \prod_{k=0}^\infty (1-x^{2^k})
\tag {1.2}$$
The power series expression has now alternating signs which alternate according to the Thue-Morse-pattern:
$$ f_1(x ) = 1- x -x^2 + x^3 -x^4 + x^5 + x^6 - x^7 -...+... \tag {1.3}$$
If we insert now $x=1/2$ we get a multiple of the Thue-Morse-constant, but we could also denote it as symbol-concatenation using $0$ for $+$ and $1$ for $-$ getting the well known string 0110 1001 1001 0110 ...
From that product-formula there is a somehow obvious generalization. If we look at the $+$ and $-$ as cofactors $+1$ and $-1$ of the unsigned terms, then those cofactors are the two square-roots of $1$. If we want to generalize then we can step to the three (complex) cube-roots of the complex unit, say $p=1/2(-1+ î\sqrt3)$ and $q=1/2(-1-î \sqrt3) $ . With this we rewrite or product-formulae $$ g_0(x) = (1+x+x^2)(1+x^3+x^6)(1+x^9+x^{18})... = \prod_{k=0}^\infty (1+ x^{3^k}+x^{2 \cdot 3^k}) \tag {2.1} $$ Of course, $g_0(x) = f_0(x)$ , both resulting in the geometric series.
But we get now two variants $$ g_1(x) = (1+px+qx^2)(1+px^3+qx^6)(1+px^9+qx^{18})... = \prod_{k=0}^\infty (1+ px^{3^k}+qx^{2 \cdot 3^k}) \tag {2.2}$$
$$
g_2(x) = (1+qx+px^2)(1+qx^3+px^6)(1+qx^9+px^{18})... = \prod_{k=0}^\infty (1+ qx^{3^k}+px^{2 \cdot 3^k}) \tag {2.3}
$$
When we expand this infinite products formally we arrive at a power series whose coefficients follow the pattern 012 120 201 ... for $g_1(x)$ as indicated by @MLE and 021 210 102 ... for $g_2(x)$.
There are some nice functional relations between that $g_r(x)$-functions.
If we evaluate $w_f=f_0(1/2) \cdot f_1(1/2)$ we get $w_f \approx 0.700367730879$ Here the well known Thue-morse-constant $\tau \approx 0.425091932720$ is involved as rational scaling $w_f = 4 \tau - 1$
If we evaluate $ w_g = g_0(1/2) \cdot g_1(1/2) \cdot g_2(1/2) $ we get $w_g \approx 0.762637186607 $ . I don't have a relation between $w_g$ to some other known constants, but it might be interesting, that $$\sqrt {w_g ^{\phantom {1^1 }}} = 2\prod_{k=0}^\infty (1 - 0.5^{3^k}) \tag{3.1} $$ whose pattern is near to the Thue-Morse-expression in the product-formula (1.2) using $f_1(x)$ for $x=0.5$
Added: the latter relation seems to be generalizable. let $$G(x)=g_0(x)\cdot g_1(x) \cdot g_2(x) \tag{3.2} $$ and similarly to the $f_r()$ functions $$F_3(x)= \prod_{k=0}^\infty (1-x^{3^k}) \tag{3.3} $$ It seems we can write $$\sqrt {G(x)^{\phantom {1^1 }}} = {1 \over 1-x} \cdot F_3(x) \tag{3.4} $$ (but I've not yet proven this algebraically)
The following article might be of interest: see here