Recall that in this discussion \(\sigma \)  and \(k\)  in \(H_k\)  both are functions of \(n\) . Now we are to prove that, as it turns out, the \(k\) th order empirical entropy is easily achievable by any LZ-like parsing in which the number of phrases is \(O(\frac{n}{\log _\sigma n})\) : it suffices to use the rightmost encoding and to spend at most \(\log d_j + O(1 + \log \log d_j + \log \ell _j)\)  bits for every pair \((d_j,\ell _j)\)  corresponding to a copying phrase (for instance, applying for \(d_j\)  and \(\ell _j\)  universal codes, like Elias's [1]} or Levenshtein's [2]}). In the sequel we show that, contrary to the case of LZ (see [3]}, [4]}), it is not possible to weaken the assumptions in this result—even for \(\text{ReLZ}\) —neither by using a non-rightmost encoding nor by using \(\log n + O(1 + \log \ell _j)\)  bits for the pairs \((d_j, \ell _j)\) .
