Properties of the Wine Tasting Sequence II
Properties of the Wine Tasting Sequence. wb 090723 - 090810, 091103
1. Introductory notes.
1.1.Definitions.
1.1.1. |x| is the absolute value of x: {- x if x ≤ 0, otherwise x}.
1.1.2. sgn x is the sign of x: sgn x ≡ x / |x|.
1.2. By an unfolding sequence, we mean a sequence derived from an initial string (or digit) by repeatedly applying a production which appends to the sequence thus far a specific transform of the sequence thus far. Let f be a string function. If s is a string in the domain of f, &f denotes the function &f(s) ≡ sf(s). The unfolding sequence derived from function f and initial string s in the domain of f is U=&f^∞(s). Trivially, any sequence can in fact be seen as unfolding by a sufficiently perverse choice of f:
f(d(0)d(1)...d(i)) ≡ d(i+1), 0 ≤ i < ∞. We shall simply ignore this, looking at sequences that can usefully be defined by unfolding processes.
2. Unfolding sequences. The Wine Tasting Sequence (WTS).
2.1. Let W be an unfolding sequence of the digits ±1 as follows: f(digit d) = -d; f(st)=f(s)f(t); W=&f^∞(1).
W = 1 -1 -1 1 -1 1 1 -1 -1 1 1 -1 1 -1 -1 1 ...
Suitably redefining f and the initial digit yields the equivalent forms
W1 = 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 ...
W2 = 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 ...
W3 = A B B A B A A B B A A B A B B A ... etc.
We know this sequence as the "Wine Tasting Sequence" from the associated Wine Tasting Problem, q.v.
2.2. Concatenations. Given s(i), i ε I (the s are indexed by I), their concatenation is a sequence written Γ{i ε I, s(i)} or Γ{i, s(i)} or Γs(i). The order of I is assumed to rule (I must be ordered). Let w(i) be the digits of the WTS. W=Γ{0 ≤ i < ∞, w(i)}.
2.3. Transforms. A transform (intuitively, as used here) is a functional which derives from any of a class of functions or similar entities from analysis another, usually different, entity in a uniform way. Well known useful examples: Fourier transform, Laplace transform, dual (of a boolean expression).
2.4. Polynomial transform. If s(i), 0 ≤ i < ∞ are taken from a field (such as the real numbers), the polynomial transform of Γ{i, s(i)} is given by
Poly Γ{i, s(i)} ≡ Σ{i, s(i) x^i}. The variable "x" should be specified somehow, but we'll just understand "x".
2.5. For the WTS, Poly W = 1 - x - x^2 + x^3 - x^4 + x^5 + x^6 - x^7 - x^8 + ... The properties of this series would be hard to reckon, except that for certain unfolding sequences, Poly takes the form of an infinite product; the WTS is one of these.
3. Functional equations. What a difference a sign makes.
3.1. (1+x)Φ(x^2) = Φ(x). The general solution of this functional equation can be expressed in a manner reminiscent of a differential equation: Φ(x) = σ(x) φ(x), where
σ(x) is the general solution of the functional equation Φ(x^2) = Φ(x),
φ(x) is any particular solution of the above equation (1+x)Φ(x^2) = Φ(x).
σ(x) may be expressed in terms of the general periodic function τ(x+π) = τ(x). It will trouble us no more.
Any particular φ(x) will do; we choose
3.1.1. φ(x) ≡ Π{0 ≤ i < ∞, 1+x^(2^i)} = (1+x)(1+x^2)(1+x^4)(1+x^8)..., |x| < 1. This unfolds into
3.1.2. φ(x) = Σ{0 ≤ i < ∞, x^i} = 1 + x + x^2 + x^3 + x^4 + x^5 + ..., |x| < 1. Then φ(x) = 1/(1-x).
Note that 1/(1-x) does indeed satisfy 3.1.
3.2. (1-x)Φ(x^2) = Φ(x). The general solution of this functional equation is Φ(x) = σ(x) φ(x), where
σ(x) is the general solution of the functional equation Φ(x^2) = Φ(x), as before,
φ(x) is any particular solution of the above equation (1-x)Φ(x^2) = Φ(x).
Any particular φ(x) will do; we choose
3.2.1. φ(x) ≡ P{0 ≤ i < ∞, 1-x^(2^i)} = (1-x)(1-x^2)(1-x^4)(1-x^8)..., |x| ≤ 1. This unfolds into
3.2.2. φ(x) = Σ{0 ≤ i < ∞, w(i) x^i} = 1 - x - x^2 + x^3 - x^4 + x^5 + ..., |x| ≤ 1. This is Poly W.
Unlike 3.1.2, it appears to have no simple closed form. Also unlike 3.1.2, it converges at |x| = 1.
3.2.3. Pseudocode for φ(x) = Poly W:
real PolyW(real x) {
P = 1-x;
while MAKINGPROGRESS {
x = x*x;
P = P*(1-x);
}
return P;
}
3.2.4. Binary details for Poly W:
3.2.4.1. φ(1/x) = (x-1)/x · (x^2-1)/x^2 · (x^4-1)/x^4 · (x^8-1)/x^8 · ...
3.2.4.2. φ(1/2) = 1/2 · 3/4 · 15/16 · 255/256 · ... = 1 - 1/2 - 1/4 + 1/8 - 1/16 + 1/32 + 1/64 - 1/128 - ...
φ(1/2) = 0.350183865...
3.2.4.3. In binary radix notation:
1.0010110011010010110100110010110... (a),
0.1101001100101101001011001101001... (b),
0.010110011010010110100110010110... φ(1/2) = a-b = a-(2-a) = 2(a-1).
4. Properties of the WTS function φ(x) = Poly W.
4.1. Ω(x): From 3.2,
4.1.1. (1-x)φ(x^2) = φ(x). Therefore at -x,
4.1.2. (1+x)φ(x^2) = φ(-x). Therefore
4.1.3. Ω(x) ≡ (1+x)φ(x) = (1-x)φ(-x) = Ω(-x). Therefore Ω(x) is even.
4.1.4. φ(-x) = ((1+x)/(1-x)) φ(x) = r φ(x), x <> 1.
4.2. Some values of φ(x) and Ω(x):
x r φ(x) φ ≈ Ω(x)
---- ---- --------------- ---- ---------------
-1 0 0.0 0.0
-3/4 1/7 0.466212439 0.11655311
-2/3 1/5 0.712946495 0.237648832
-1/2 1/3 1.050551595 21/20 0.525275798
-1/3 1/2 1.170374832 0.780249888
-1/4 3/5 1.167279552 7/6 0.875459664
0 1 1.0 1.0
1/4 5/3 0.700367731 7/10 0.875459664
1/3 2 0.585187416 7/12 0.780249888
1/2 3 0.350183865 7/20 0.525275798
2/3 5 0.142589299 1/7 0.237648832
3/4 7 0.066601777 1/15 0.11655311
1 ∞ 0.0 0.0
max φ(x) at x ≈ -1/3; max Ω(x) at x = 0.
5. The mother of the Wine Tasting Sequence (WTS).
5.1. Let V be an unfolding sequence of the natural numbers as follows:
f(digit d) = d+1; f(st)=f(s)f(t); V=&f^∞(0).
V = 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 ... = Γ{0 ≤ i < ∞, v(i)}.
W1 = 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 ...
= Γ{0 ≤ i < ∞, w1(i)} = Γ{0 ≤ i < ∞, mod2 v(i)}.
5.2. w1(i) = mod2 v(i), i = 0,1,2,...
5.3. We cannot express Poly V as an infinite product as we did with Poly W; the best we can do is to use an operator equation, exploiting an operator
5.3.1. E n ≡ n+1, n = 0,1,2,...
5.3.2. φ(x) ≡ P{0 ≤ i < ∞, 1+E x^(2^i)} = (1+E x)(1+E x^2)(1+E x^4)(1+E x^8)....
This cannot be usefully evaluated; in particular, it does not yield a functional equation like 3.1 or 3.2. It can only be regarded as a symbolic convenience. However...
6. New corresponding functional equations
6.1. Entirely analogously to 3.1, consider the equation (1+2x)Φ(x^2) = Φ(x). Here, our choice of φ(x) is
6.1.1. φ(x) ≡ P{0 ≤ i < ∞, 1+2x^(2^i)} = (1+2x)(1+2x^2)(1+2x^4)(1+2x^8)..., |x| < 1. This unfolds into
6.1.2. φ(x) = Σ{0 ≤ i < ∞, u(i) x^i} = 1 + 2x + 2x^2 + 4x^3 + 2x^4 + 4x^5 + ..., |x| < 1. Then
6.1.3. log2 u(i) = v(i).
6.2. Also, consider the equation (1-2x)Φ(x^2) = Φ(x). Here, our choice of φ(x) is
6.2.1. φ(x) ≡ P{0 ≤ i < ∞, 1-2x^(2^i)} = (1-2x)(1-2x^2)(1-2x^4)(1-2x^8)..., |x| < 1. This unfolds into
6.2.2. φ(x) = Σ{0 ≤ i < ∞, t(i) x^i} = 1 - 2x - 2x^2 + 4x^3 - 2x^4 + 4x^5 + ..., |x| < 1. Now we have:
6.2.3. log2 |t(i)| = v(i). (1 - sgn t(i))/2 = mod2 log2 |t(i)| = w1(i).
7. Sequence V is fundamental.
7.1. Definition: An unfolding sequence is homomorphic
iff its generating function f is homomorphic with respect to all &f^n, n = 0,1,2,... Then we can rewrite
7.1.1. s f(s) f(s f(s)) f(s f(s) f(s f(s))) f(s f(s) f(s f(s)) f(s f(s) f(s f(s)))) ... = Γ{0 ≤ i < ∞, f^v(i)(s)}.
Thus a typical homomorphic unfolding sequence is isomorphic to V or to some modulo reduction of V (like W) under the mapping f^k(s) --> k.
7.2. Sometimes the connection is not so obvious.
7.2.1. Consider unfolding sequence S defined by generating function f, f(&f(s)) = s.
7.2.2. Punctuating with dots for clarity,
S: 0.1.0.01.010.01001.01001010.0100101001001....
But this is V, under the mapping 12-->0, 23-->1, etc.
7.2.3. V: 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 1 2 2 ...
0 1 0 0 1 0 1 1 2 0 1 1 2 1 2 2 3 0 ...
0 1 0 0 1 0 1 0 0 1 0 0 1 0 ...
UPDATE (FROM GENE): I have typed Π᾽s in where I have found P. Should the bolded E's be epsilon's as well?
1. Introductory notes.
1.1.Definitions.
1.1.1. |x| is the absolute value of x: {- x if x ≤ 0, otherwise x}.
1.1.2. sgn x is the sign of x: sgn x ≡ x / |x|.
1.2. By an unfolding sequence, we mean a sequence derived from an initial string (or digit) by repeatedly applying a production which appends to the sequence thus far a specific transform of the sequence thus far. Let f be a string function. If s is a string in the domain of f, &f denotes the function &f(s) ≡ sf(s). The unfolding sequence derived from function f and initial string s in the domain of f is U=&f^∞(s). Trivially, any sequence can in fact be seen as unfolding by a sufficiently perverse choice of f:
f(d(0)d(1)...d(i)) ≡ d(i+1), 0 ≤ i < ∞. We shall simply ignore this, looking at sequences that can usefully be defined by unfolding processes.
2. Unfolding sequences. The Wine Tasting Sequence (WTS).
2.1. Let W be an unfolding sequence of the digits ±1 as follows: f(digit d) = -d; f(st)=f(s)f(t); W=&f^∞(1).
W = 1 -1 -1 1 -1 1 1 -1 -1 1 1 -1 1 -1 -1 1 ...
Suitably redefining f and the initial digit yields the equivalent forms
W1 = 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 ...
W2 = 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 ...
W3 = A B B A B A A B B A A B A B B A ... etc.
We know this sequence as the "Wine Tasting Sequence" from the associated Wine Tasting Problem, q.v.
2.2. Concatenations. Given s(i), i ε I (the s are indexed by I), their concatenation is a sequence written Γ{i ε I, s(i)} or Γ{i, s(i)} or Γs(i). The order of I is assumed to rule (I must be ordered). Let w(i) be the digits of the WTS. W=Γ{0 ≤ i < ∞, w(i)}.
2.3. Transforms. A transform (intuitively, as used here) is a functional which derives from any of a class of functions or similar entities from analysis another, usually different, entity in a uniform way. Well known useful examples: Fourier transform, Laplace transform, dual (of a boolean expression).
2.4. Polynomial transform. If s(i), 0 ≤ i < ∞ are taken from a field (such as the real numbers), the polynomial transform of Γ{i, s(i)} is given by
Poly Γ{i, s(i)} ≡ Σ{i, s(i) x^i}. The variable "x" should be specified somehow, but we'll just understand "x".
2.5. For the WTS, Poly W = 1 - x - x^2 + x^3 - x^4 + x^5 + x^6 - x^7 - x^8 + ... The properties of this series would be hard to reckon, except that for certain unfolding sequences, Poly takes the form of an infinite product; the WTS is one of these.
3. Functional equations. What a difference a sign makes.
3.1. (1+x)Φ(x^2) = Φ(x). The general solution of this functional equation can be expressed in a manner reminiscent of a differential equation: Φ(x) = σ(x) φ(x), where
σ(x) is the general solution of the functional equation Φ(x^2) = Φ(x),
φ(x) is any particular solution of the above equation (1+x)Φ(x^2) = Φ(x).
σ(x) may be expressed in terms of the general periodic function τ(x+π) = τ(x). It will trouble us no more.
Any particular φ(x) will do; we choose
3.1.1. φ(x) ≡ Π{0 ≤ i < ∞, 1+x^(2^i)} = (1+x)(1+x^2)(1+x^4)(1+x^8)..., |x| < 1. This unfolds into
3.1.2. φ(x) = Σ{0 ≤ i < ∞, x^i} = 1 + x + x^2 + x^3 + x^4 + x^5 + ..., |x| < 1. Then φ(x) = 1/(1-x).
Note that 1/(1-x) does indeed satisfy 3.1.
3.2. (1-x)Φ(x^2) = Φ(x). The general solution of this functional equation is Φ(x) = σ(x) φ(x), where
σ(x) is the general solution of the functional equation Φ(x^2) = Φ(x), as before,
φ(x) is any particular solution of the above equation (1-x)Φ(x^2) = Φ(x).
Any particular φ(x) will do; we choose
3.2.1. φ(x) ≡ P{0 ≤ i < ∞, 1-x^(2^i)} = (1-x)(1-x^2)(1-x^4)(1-x^8)..., |x| ≤ 1. This unfolds into
3.2.2. φ(x) = Σ{0 ≤ i < ∞, w(i) x^i} = 1 - x - x^2 + x^3 - x^4 + x^5 + ..., |x| ≤ 1. This is Poly W.
Unlike 3.1.2, it appears to have no simple closed form. Also unlike 3.1.2, it converges at |x| = 1.
3.2.3. Pseudocode for φ(x) = Poly W:
real PolyW(real x) {
P = 1-x;
while MAKINGPROGRESS {
x = x*x;
P = P*(1-x);
}
return P;
}
3.2.4. Binary details for Poly W:
3.2.4.1. φ(1/x) = (x-1)/x · (x^2-1)/x^2 · (x^4-1)/x^4 · (x^8-1)/x^8 · ...
3.2.4.2. φ(1/2) = 1/2 · 3/4 · 15/16 · 255/256 · ... = 1 - 1/2 - 1/4 + 1/8 - 1/16 + 1/32 + 1/64 - 1/128 - ...
φ(1/2) = 0.350183865...
3.2.4.3. In binary radix notation:
1.0010110011010010110100110010110... (a),
0.1101001100101101001011001101001... (b),
0.010110011010010110100110010110... φ(1/2) = a-b = a-(2-a) = 2(a-1).
4. Properties of the WTS function φ(x) = Poly W.
4.1. Ω(x): From 3.2,
4.1.1. (1-x)φ(x^2) = φ(x). Therefore at -x,
4.1.2. (1+x)φ(x^2) = φ(-x). Therefore
4.1.3. Ω(x) ≡ (1+x)φ(x) = (1-x)φ(-x) = Ω(-x). Therefore Ω(x) is even.
4.1.4. φ(-x) = ((1+x)/(1-x)) φ(x) = r φ(x), x <> 1.
4.2. Some values of φ(x) and Ω(x):
x r φ(x) φ ≈ Ω(x)
---- ---- --------------- ---- ---------------
-1 0 0.0 0.0
-3/4 1/7 0.466212439 0.11655311
-2/3 1/5 0.712946495 0.237648832
-1/2 1/3 1.050551595 21/20 0.525275798
-1/3 1/2 1.170374832 0.780249888
-1/4 3/5 1.167279552 7/6 0.875459664
0 1 1.0 1.0
1/4 5/3 0.700367731 7/10 0.875459664
1/3 2 0.585187416 7/12 0.780249888
1/2 3 0.350183865 7/20 0.525275798
2/3 5 0.142589299 1/7 0.237648832
3/4 7 0.066601777 1/15 0.11655311
1 ∞ 0.0 0.0
max φ(x) at x ≈ -1/3; max Ω(x) at x = 0.
5. The mother of the Wine Tasting Sequence (WTS).
5.1. Let V be an unfolding sequence of the natural numbers as follows:
f(digit d) = d+1; f(st)=f(s)f(t); V=&f^∞(0).
V = 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 ... = Γ{0 ≤ i < ∞, v(i)}.
W1 = 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 ...
= Γ{0 ≤ i < ∞, w1(i)} = Γ{0 ≤ i < ∞, mod2 v(i)}.
5.2. w1(i) = mod2 v(i), i = 0,1,2,...
5.3. We cannot express Poly V as an infinite product as we did with Poly W; the best we can do is to use an operator equation, exploiting an operator
5.3.1. E n ≡ n+1, n = 0,1,2,...
5.3.2. φ(x) ≡ P{0 ≤ i < ∞, 1+E x^(2^i)} = (1+E x)(1+E x^2)(1+E x^4)(1+E x^8)....
This cannot be usefully evaluated; in particular, it does not yield a functional equation like 3.1 or 3.2. It can only be regarded as a symbolic convenience. However...
6. New corresponding functional equations
6.1. Entirely analogously to 3.1, consider the equation (1+2x)Φ(x^2) = Φ(x). Here, our choice of φ(x) is
6.1.1. φ(x) ≡ P{0 ≤ i < ∞, 1+2x^(2^i)} = (1+2x)(1+2x^2)(1+2x^4)(1+2x^8)..., |x| < 1. This unfolds into
6.1.2. φ(x) = Σ{0 ≤ i < ∞, u(i) x^i} = 1 + 2x + 2x^2 + 4x^3 + 2x^4 + 4x^5 + ..., |x| < 1. Then
6.1.3. log2 u(i) = v(i).
6.2. Also, consider the equation (1-2x)Φ(x^2) = Φ(x). Here, our choice of φ(x) is
6.2.1. φ(x) ≡ P{0 ≤ i < ∞, 1-2x^(2^i)} = (1-2x)(1-2x^2)(1-2x^4)(1-2x^8)..., |x| < 1. This unfolds into
6.2.2. φ(x) = Σ{0 ≤ i < ∞, t(i) x^i} = 1 - 2x - 2x^2 + 4x^3 - 2x^4 + 4x^5 + ..., |x| < 1. Now we have:
6.2.3. log2 |t(i)| = v(i). (1 - sgn t(i))/2 = mod2 log2 |t(i)| = w1(i).
7. Sequence V is fundamental.
7.1. Definition: An unfolding sequence is homomorphic
iff its generating function f is homomorphic with respect to all &f^n, n = 0,1,2,... Then we can rewrite
7.1.1. s f(s) f(s f(s)) f(s f(s) f(s f(s))) f(s f(s) f(s f(s)) f(s f(s) f(s f(s)))) ... = Γ{0 ≤ i < ∞, f^v(i)(s)}.
Thus a typical homomorphic unfolding sequence is isomorphic to V or to some modulo reduction of V (like W) under the mapping f^k(s) --> k.
7.2. Sometimes the connection is not so obvious.
7.2.1. Consider unfolding sequence S defined by generating function f, f(&f(s)) = s.
7.2.2. Punctuating with dots for clarity,
S: 0.1.0.01.010.01001.01001010.0100101001001....
But this is V, under the mapping 12-->0, 23-->1, etc.
7.2.3. V: 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 1 2 2 ...
0 1 0 0 1 0 1 1 2 0 1 1 2 1 2 2 3 0 ...
0 1 0 0 1 0 1 0 0 1 0 0 1 0 ...
UPDATE (FROM GENE): I have typed Π᾽s in where I have found P. Should the bolded E's be epsilon's as well?
Gene,
ReplyDeleteYou apparently (and sensibly) deleted the early note about using bold upper P for upper pi; it is indeed gone.
But the bold upper Ps are still bold upper Ps, at least when I read my post! Mysterious.
Since bold upper E represents a formal operator, I'd leave it.
Gene,
ReplyDeleteWell, we're making progress--slow, but what else do you expect in mathematics? I count one uppercase pi, three bold uppercase Ps. I totally don't understand, especially if you haven't intervened again, in which case a P seems to have spontaneously morphed into a pi. Maybe I just overlooked it the first time. Oh well...