3.3 Linear Decomposition
For \(k, n \in \mathbb {N}\), the accumulated correction term \(Q(k, n)\) of the Terras map is defined recursively by \(Q(0, n) = 0\) and
If \(j \le k\), then \(Q(j, n) \le Q(k, n)\).
By definition of \(Q(k, n)\) as a sum of non-negative terms.
\(Q(k+1, n) = Q(k, n) + X(T^k(n))\).
Immediate from the definition of \(Q(k, n)\).
For any \(k, n \in \mathbb {N}\), the \(k\)-fold iteration of the Terras map \(T^k(n)\) satisfies the linear identity
where \(Q(k, n)\) is the number of odd iterates as defined in Definition 81.
By induction on \(k\), using the identity \(2 T(m) = 3^{X(m)} m + X(m)\).
This appeared first in Terras (1976) [ 6 ] . See Lemma 109 below for a variant of this formula.
The correction term \(Q(k, n)\) has the closed-form expression
The recursive definition of \(Q(k, n)\) is equivalent to the closed-form sum.
By induction on \(k\).
The decomposition coefficient \(C(k, n)\) is the rational number
The correction ratio \(E(j, n)\) is the rational number
\(E(0, n) = 0\).
Trivial by definition.
The ratio \(E\) satisfies the recurrence
By diving the recurrence for \(Q(k, n)\) by \(2^{k+1}\).
For a fixed parity \(x \in \{ 0, 1\} \), the step map \(a \mapsto \frac{3^x}{2} a + \frac{x}{2}\) is strictly monotone.
Since \(3^x/2 {\gt} 0\) for \(x \in \{ 0, 1\} \).
If \(E(k, m) = E(k, n)\), then \(Q(k, m) = Q(k, n)\).
By induction on \(k\).
Another form of the linear identity is given by:
By substituting the definitions \(C(j, n) = 3^{q(j, n)}/2^j\) and \(E(j, n) = Q(j, n)/2^j\) into the linear identity \(2^j T^j(n) = 3^{q(j, n)} n + Q(j, n)\).
The coefficient stopping time \(\tau (n)\) is the smallest \(j \ge 1\) such that \(C(j, n) {\lt} 1\). If no such \(j\) exists, \(\tau (n) = \infty \).