3.2 Parity Vectors
A parity vector is a finite sequence of bits (0 and 1). In the formalization, it is represented as a list of boolean values, where false corresponds to 0 and true corresponds to 1.
For a parity vector \(v\), \(q(v)\) is the number of ones (true entries) in \(v\).
The size of a parity vector \(v\), denoted \(|v|\), is its length.
The ones-ratio of a parity vector \(v\) is the rational number \(q(v) / |v|\). If the vector is empty, the ratio is defined to be 0.
For \(j, n \in \mathbb {N}\), the parity vector \(V(j, n)\) of length \(j\) for the compact Collatz sequence starting at \(n\) is defined as
The length of \(V(j, n)\) is \(j\).
Immediate from the definition.
For any \(i {\lt} j\), the \(i\)-th entry of \(V(j, n)\) is \(X(T^i(n))\).
Immediate from the definition.
The elementary precedence relation \(\prec _e\) is defined by swapping a \(01\) subword with \(10\):
The precedence relation \(\preceq \) is the reflexive transitive closure of \(\prec _e\).
For \(k, n \in \mathbb {N}\), the vector \(E(k, n)\) is the function from \(\{ 0, \dots , k-1\} \) to \(\{ 0, 1\} \) defined by
Each entry of \(E(k, n)\) is at most 1.
Immediate from the definition of \(X(n)\).
The number of odd steps \(Q(k, n)\) is equal to the sum of the entries of \(E(k, n)\):
By definition of \(Q(k, n)\) and \(E(k, n)\).
If \(E(k+1, m) = E(k+1, n)\), then \(E(k, m) = E(k, n)\).
The agreement on the first \(k+1\) entries implies agreement on the first \(k\) entries.
If \(E(k, m) = E(k, n)\), then \(Q(k, m) = Q(k, n)\).
Directly from Lemma 94.