January 17, 2017
This is a continuation of a previous post.
In the previous post we described a class of numeral systems in terms of five axioms. The third axiom allowed us to determine the value of the \(n\)th base given the preceding \(n-1\) bases. In other words, there exist functions \(f_n\) such that for every \(A \in \mathcal{A}\)
$$ b_n = f_n(a_1,a_2,\ldots,a_{n-1}). $$For our sixth axiom, we will build on this condition by asserting that only a fixed number \(t \) of the preceding digits are required to determine a base, (assuming that there are at least that many digits to begin with). In other words,
There exist integers \(t\) and \(N_f\) and a function \(f\) such that, for every \(A \in \mathcal{A}\) and for every \(n>N_f\),
$$ b_n = f(a_{n-t}, \ldots, a_{n-2}, a_{n-1}). $$Numeral systems that follow this axiom shall be said to have uniformly determined bases.
A numeral \(A\) is said to be repeating if there exist positive integers \(N\) and \(\Delta n\) such that for every \(n>N\), \(a_n = a_{n+\Delta n}\).
A numeral \(A\) is said to have repeating bases if there exist positive integers \(N\) and \(\Delta n\) such that for every \(n>N\), \(b_n = b_{n+\Delta n}\).
If \(A\) is repeating, then it also has repeating bases.
Suppose \(A\) is repeating.
Then there exist integers \(N\) and \(\Delta n \) such that for every \(n > N\), \(a_n = a_{n+\Delta n}\).
Let \(N' = \max(N_f,N+t)\).
Suppose \(n > N'\).
Then \(n > N_f\), so \(b_n = f(a_{n-t}, \ldots, a_{n-2}, a_{n-1})\).
And \(n-t > N \), so
$$ \begin{align} b_n & = f(a_{n-t}, \ldots, a_{n-2}, a_{n-1})\\ & = f(a_{n+\Delta n-t}, \ldots, a_{n+\Delta n-2}, a_{n+\Delta n-1})\\ & = b_{n+\Delta n} \end{align}$$All repeating numerals have rational values.
In words, the value contributions of each digit to the value of the whole numeral can be divided up as follows:
If \(N'\) is the last index before which both bases and digits repeat, then each of the first \(N'\) digits add a rational amount to the total value. Since there are only finitely many of them, their overall contribution is a finite sum of rational numbers, which is rational.
If \(\Delta n \) is the period of the repeating section, then every grouping of digits seperated by multiples of \(\Delta n\), (excluding the first \(N'\) digits) contributes a geometric series with rational ratio and starting term, which converges to a rational number. Since there are only finitely many such groupings, the overall contribution of the repeating section is a finite sum of rational numbers, which is rational.
Adding both contributions together is the same as adding two rational numbers, so the total value of the numeral is rational.
Do all rational numbers have repeating representations?
Turns out the answer is sometimes yes, sometimes no, and sometimes yes and no.
To analyze the problem of whether or not rationals repeat. Recall that every numeral can be constructed by use of one of the division algorithms mentioned in Lemma 3. That is, any given real number \(r\in [0,1]\) has a numeral representation \(A = 0.a_1a_2a_3(\ldots )\) where
$$ a_n = \begin{cases} \sup{\{a : a\leq b_nr_n\}} & \text{Using }v_1^{-1} \\ \sup{\{a : a < b_nr_n\}} & \text{Using }v_2^{-1} \\ \end{cases} $$and
$$ r_n = \begin{cases} r & n=1 \\ b_{n-1}r_{n-1}-a_{n-1} & n > 1 \end{cases}. $$We would like to define state vectors \(s_n\) that describe the progress of the division algorithm after \(n \) iterations. We would like \(a_n\) to be a component of \(s_n\), and we would also like \(s_n\) to contain enough information to uniquely determine \(s_{n+1}\).
Our reasoning is this:
Assume there exists a function \(F\) such that \(F(s_n) = s_{n+1}\) for sufficiently large \(n\) for \(s_n\) to be defined.
Suppose for some \(N \in \mathbb{N}\), \(s_{N} = s_{N+\Delta n}\).
Then \( F(s_{N}) = F(s_{N+\Delta n}) \), or \(s_{N+1} = s_{N+1+\Delta n}\).
So by induction, for every \(n \geq N\), \(s_n = s_{n+\Delta n}\).
Since \(a_n\) is a component of \(s_n\), it follows that \(a_n = a_{n+\Delta n}\) for every \(n \geq N\).
So \(A\) is repeating.
Therefore, if we can show that the same state occurs more than once during the division algorithm, then we can prove that the numeral generated repeats.
For every \(n > N_f\), define state vectors \( s_n = \langle a_{n-t+1},\ldots,a_{n-1},a_n,r_{n+1}\rangle. \)
Then there exists a function \(F\) such that \(F(s_n) = s_{n+1} = \langle a_{n-t+2},\ldots,a_{n},a_{n+1},r_{n+2}\rangle.\)
The digits \(a_{n-t+2},\ldots,a_{n}\) are themselves components of \(s_n\).
\(b_{n+1}\) can be found as a function of the digits \(a_{n-t+1},\ldots,a_{n-1},a_n\), which are components of \(s_n\).
\(a_{n+1}\) can be found as a function of \(b_{n+1}\), which we just found, and \(r_{n+1}\), which is a component of \(s_n\).
Finally, \(r_{n+2}\) can be found as a function of \(b_{n+1}\),\(a_{n+1}\), and \(r_{n+1}\), all of which we have already found.
So all the components of \(s_{n+1}\) can be uniquely determined by the components of \(s_{n}\).
Therefore, there exists a function \(F\) such that \(F(s_n) = s_{n+1}\).
The division algorithm iterates a countably infinite number of times, so if we can prove that the state vector can take on only finitely many states, then it will eventually have to take on the same state twice.
If there is a strict upper bound on the range of possible bases \(b_i\), then this is relatively straight-forward. There are finitely many possible values of \(a_i\), since \(a_i\) is bounded above by \(b_i\) which is itself bounded above. Given a rational \(r_{n} = \frac{p}{q}\), then \(r_{n+1} = \frac{p'}{q}\), and since \(r_n\) is bounded, there are finitely many, (at most \(q\)) possible values of \(r_n\). So since each of the finitely many components of \(s_n\) can only take on finitely many values, \(s_n\) itself can only take on finitely many values. So in such a system, all rationals would repeat.
But some numeral systems will have bases that can get arbitrarily large, so we have to be slightly more clever about those.
Define the magnitude \(|s|\) of a state vector so that it has the following properties:
\(|s| \in X\), where \(X\) is some subset of the reals that for all intents and purposes has the same topology as the natural numbers. That is, \(X\) is bounded below, and every interval contains only finitely points of \(X\).
For every \(x \in X\), there are only finitely many distinct states \(s\) such that \(|s| = x\).
The reasoning behind these conditions is that, if an upper bound can be placed on \(|s|\) then there can be only finitely many distinct \(s_n\).
(Before anyone says anything, I know this is scientifically inaccurate.)
Consider a collection of water particles moving about in a swimming pool.
While in the pool, the particles may move downward or upward and may even break through the water's surface, landing on the pool wall. However, they can only go so far above the surface.
The highest up that the water can go marks the boundary of the splash zone.
Once a particle is out of the pool, it must either stay put or drip downwards, possibly making its way back to the pool.
It is possible to find a water particle above the splash zone (in what I guess you might call the drip zone), but only if it started up there, (like if it were raining or something), and the only direction it can move is down.
So, if we traced out the path of a single particle, we would find that the highest the particle has ever been is either wherever it started, (especially if it started in the drip zone), or the highest point to which it has ever splashed, meaning that we can place a strict upper bound on the particle's height.
Now to put that in terms of math...
If there exists a largest magnitude \(|s|\) for which it is possible that \(|F(s)| > |s|\), then \(|s_n|\) is bounded above.
Then there are only finitely many \(s\) such that \(|F(s)| > |s|\).
So there is a largest \(x \in X\) such that \(|F(s)| = x\) if \(|F(s)| > |s|\).
Let \(M = \max{(|s_{n_0}|,x)}\).
Let \(n = n_0\)
Then \(|s_n| = |s_{n_0}| \leq M\).
Suppose \(|s_n| \leq M\).
Case 1: \(|s_{n+1}| \leq |s_n|\)
\(|s_{n+1}| \leq |s_n| \leq M\)
Case 2: \(|s_{n+1}| > |s_n|\)
Then \(|s_{n+1}| \leq x \leq M\)
So, by induction \(|s_n| \leq M\) for all \(n \geq n_0\).
If there exists a largest magnitude \(|s|\) for which it is possible that \(|F(s)| > |s|\), then \(A \) is repeating.
This follows from Lemma 7.
Define the \(\beta\)-nary plus numeral systems as the numeral systems for which \(b_n = a_{n-1}+\beta\) where \(\beta>1\).
Define the magnitude of a state \(|s_n| = a_n\).
Let \(r = \frac{p}{q} \) where \(p\) and \(q\) are integers.
Suppose we constrain \(a_n < a_{n+1} \).
Using the algorithm \(v_1^{-1}\), we note that
$$ \begin{align} a_{n+1} & \leq b_{n+1}r_{n+1}\\ a_n & < \\ \frac{a_{n}}{b_{n+1}} & < r_{n+1}\\ & < 1-\frac{1}{q} \\ \frac{a_{n}}{a_n+\beta} & < 1-\frac{1}{q} \\ \end{align} $$There is a largest \(a_n\) satisfying this inequality, so there is a largest \(a_n\) such that \(a_{n+1} > a_n\).
So by Theorem 4, \(v_{1}^{-1}(r)\) repeats.
Using the algorithm \(v_2^{-1}\), we note that
$$ \begin{align} a_{n+1} & < b_{n+1}r_{n+1}\\ a_n & < \\ \frac{a_{n}}{b_{n+1}} & < r_{n+1}\\ & < 1 \\ \frac{a_{n}}{a_n+\beta} & < 1 \\ \end{align} $$Unlike the previous algorithm, there is no such restriction on \(a_n\), so we cannot conclude that \(v_2^{-1}(r)\) repeats.
However, we can verify that the only case in which \(v_2^{-1}(r)\) doesn't repeat is whenever \(r\) has two distinct representations, or whenever \(v_1^{-1}(r)\) is terminating.
January 22, 2017
After further inspection, I realize that numerals in uniformly determined numeral systems are essentially generated by a markov process where each real number acts as a random seed. Perhaps I should call them Markovian numeral systems instead.