Theorem 105 (by Shalosh B. Ekhad)
Consider the following recurrence
if x[n-1], x[n] mod 2 equal, resp. , 1, 1, then,
x[n + 1] = -1/2 x[n - 1] + 1/2 x[n]
if x[n-1], x[n] mod 2 equal, resp. , 1, 0, then, x[n + 1] = -x[n - 1] + x[n]
if x[n-1], x[n] mod 2 equal, resp. , 0, 1, then, x[n + 1] = x[n - 1] + x[n]
if x[n-1], x[n] mod 2 equal, resp. , 0, 0, then,
x[n + 1] = -1/2 x[n - 1] + 1/2 x[n]
based on empirical observation, we are lead to the following
Conjecture: Every trajectory of the rule F
with gcod(x[-1],x[0])=1 eventually
ends in one of the following orbits
{[0, 0], [1, 1, 0, -1, -1, 0], [5, 1, -2, -3, -5, -1, 2, 3]}
We have the following bounds for the general term, x[n]
If x[n-1] mod, 2, equals , 1, and
x[n] mod, 2, equals, 1, then
| x[n] | <= | x[-1] | + 2 | x[0] |
If x[n-1] mod, 2, equals , 1, and
x[n] mod, 2, equals, 2, then
| x[n] | <= | x[-1] | + | x[0] |
If x[n-1] mod, 2, equals , 2, and
x[n] mod, 2, equals, 1, then
| x[n] | <= | x[-1] | + 2 | x[0] |
This can presumbly be proved rigorously by an appropriate scheme
but it is not implemented yet
Without loss of generality we can have the first two elements as, [a, b]
Because of the above inequalities, it is possible to prove
(rigorously!) that the only words in the alphabet, {0,1}
that a trajectory of the rule modulo 2, can have are
{[%1], [%1, [0]], [%1, [1]], [%1, [0, 1]], [%1, [0, 1, 1]], [%1, [0, 1, 1, 0]],
[%1, [0, 1, 1, 0, 1]]}
%1 := [[0, 1, 1, 1], m[1]]
For the regular expression, [[[2, 1, 1, 1], m[1]]]
applying the rule, we see, by induction
that the last two elements are
m[1] m[1] m[1] m[1]
[-1/5 a (-1) - 1/5 b (-1) + 6/5 a (1/4) - 4/5 b (1/4) ,
m[1] m[1] m[1] m[1]
2/5 a (-1) + 2/5 b (-1) + 3/5 a (1/4) - 2/5 b (1/4) ]
By equating the first two elements with the last two elements
we see that a and b must be 0 (or one of the above-found orbits)
unless the following condition holds
m[1] m[1] m[1] m[1]
5 (-1) (1/4) - (-1) - 4 (1/4) + 5 = 0
and this can never happen, unless it (possibly) coincides with the
the above-found orbits (you prove it!)
For the regular expression, [[[2, 1, 1, 1], m[1]], [1]]
applying the rule, we see, by induction
that the last two elements are
m[1] m[1] m[1] m[1]
[2/5 a (-1) + 2/5 b (-1) + 3/5 a (1/4) - 2/5 b (1/4) ,
m[1] m[1] m[1] m[1]
3/10 a (-1) + 3/10 b (-1) - 3/10 a (1/4) + 1/5 b (1/4) ]
By equating the first two elements with the last two elements
we see that a and b must be 0 (or one of the above-found orbits)
unless the following condition holds
m[1] m[1] m[1] m[1]
5 (-1) (1/4) - 7 (-1) - 8 (1/4) + 10 = 0
and this can never happen, unless it (possibly) coincides with the
the above-found orbits (you prove it!)
For the regular expression, [[[2, 1, 1, 1], m[1]], [2]]
applying the rule, we see, by induction
that the last two elements are
m[1] m[1] m[1] m[1]
[2/5 a (-1) + 2/5 b (-1) + 3/5 a (1/4) - 2/5 b (1/4) ,
m[1] m[1] m[1] m[1]
3/5 a (-1) + 3/5 b (-1) - 3/5 a (1/4) + 2/5 b (1/4) ]
By equating the first two elements with the last two elements
we see that a and b must be 0 (or one of the above-found orbits)
unless the following condition holds
m[1] m[1]
((-1) - 1) ((1/4) - 1) = 0
and this can never happen, unless it (possibly) coincides with the
the above-found orbits (you prove it!)
For the regular expression, [[[2, 1, 1, 1], m[1]], [2, 1]]
applying the rule, we see, by induction
that the last two elements are
m[1] m[1] m[1] m[1]
[3/5 a (-1) + 3/5 b (-1) - 3/5 a (1/4) + 2/5 b (1/4) ,
m[1] m[1]
a (-1) + b (-1) ]
By equating the first two elements with the last two elements
we see that a and b must be 0 (or one of the above-found orbits)
unless the following condition holds
m[1] m[1] m[1] m[1]
-8 (-1) - 5 (-1) (1/4) + 3 (1/4) + 5 = 0
and this can never happen, unless it (possibly) coincides with the
the above-found orbits (you prove it!)
For the regular expression, [[[2, 1, 1, 1], m[1]], [2, 1, 1]]
applying the rule, we see, by induction
that the last two elements are
m[1] m[1]
[a (-1) + b (-1) ,
m[1] m[1] m[1] m[1]
1/5 a (-1) + 1/5 b (-1) + 3/10 a (1/4) - 1/5 b (1/4) ]
By equating the first two elements with the last two elements
we see that a and b must be 0 (or one of the above-found orbits)
unless the following condition holds
m[1] m[1] m[1] m[1]
-5 (-1) (1/4) - 12 (-1) + 2 (1/4) + 10 = 0
and this can never happen, unless it (possibly) coincides with the
the above-found orbits (you prove it!)
For the regular expression, [[[2, 1, 1, 1], m[1]], [2, 1, 1, 2]]
applying the rule, we see, by induction
that the last two elements are
m[1] m[1] m[1] m[1]
[1/5 a (-1) + 1/5 b (-1) + 3/10 a (1/4) - 1/5 b (1/4) ,
m[1] m[1] m[1] m[1]
-4/5 a (-1) - 4/5 b (-1) + 3/10 a (1/4) - 1/5 b (1/4) ]
By equating the first two elements with the last two elements
we see that a and b must be 0 (or one of the above-found orbits)
unless the following condition holds
m[1] m[1] m[1] m[1]
-5 (-1) (1/4) + 6 (-1) - (1/4) + 10 = 0
and this can never happen, unless it (possibly) coincides with the
the above-found orbits (you prove it!)
For the regular expression, [[[2, 1, 1, 1], m[1]], [2, 1, 1, 2, 1]]
applying the rule, we see, by induction
that the last two elements are
m[1] m[1] m[1] m[1]
[-4/5 a (-1) - 4/5 b (-1) + 3/10 a (1/4) - 1/5 b (1/4) ,
m[1] m[1] m[1] m[1]
-3/5 a (-1) - 3/5 b (-1) + 3/5 a (1/4) - 2/5 b (1/4) ]
By equating the first two elements with the last two elements
we see that a and b must be 0 (or one of the above-found orbits)
unless the following condition holds
m[1] m[1] m[1] m[1]
5 (-1) (1/4) + 14 (-1) + (1/4) + 10 = 0
and this can never happen, unless it (possibly) coincides with the
the above-found orbits (you prove it!)