We proceed by induction on \(j\). The base case \(j=k\) follows from the hypothesis. For the inductive step \(j \to j+1\), we assume \(E_j(n) {\lt} E_j(m)\) and \(X(T^j(n)) = X(T^j(m)) = x\). Then:

since \(3^x/2 {\gt} 0\).

Immediate from the definition of \(V_j(n)\).

Since \(E_k(n)\) depends only on the parity bits \(X(T^0(n)), \dots , X(T^{k-1}(n))\), agreement of the first \(k\) entries of the parity vector implies equality of these bits, and thus equality of the correction terms and \(E_k\).

Let the swap occur at positions \(k\) and \(k+1\). Before position \(k\), the parity vectors agree, so \(E_k(n) = E_k(m)\). In \(V_j(m)\), we have bits \((0, 1)\) at \((k, k+1)\), while in \(V_j(n)\) we have \((1, 0)\). Calculating the two-step increase:

Thus \(E_{k+2}(n) {\lt} E_{k+2}(m)\). Since the bits agree for all positions \(i {\gt} k+1\), Lemma 119 implies \(E_j(n) {\lt} E_j(m)\).

This follows by induction on the number of elementary swaps, applying Lemma 122 at each step.

This is exactly the statement that the precedence relation \(V_j(m) \prec V_j(n)\) implies \(E_j(n) {\lt} E_j(m)\), which follows from Lemma 123 by identifying the sequence-based \(E_j\) with the vector-based calculation.