# Compressed Communication Complexity of _Hamming Distance_
## 3 Compressed Communication Complexity of _Hamming Distance_
### On the Sizes of Non-Self-Referencing LZ77 Factorization of Suffix
#### 3.1.1 Lower Bound for \(\zeta(n)\)  
In this subsection, we present a family of strings \(S\) such that \(\mathsf{zn}(S[i..])>\mathsf{zn}(S)\) for some suffix \(S[i..]\), namely \(\zeta(n)>1\). More specifically, we show the following:  
Lemma 2: \(\zeta(n)\) _is asymptotically lower bounded by \(4/3\)._  
Proof: For simplicity, we consider an integer alphabet \(\{0,1,\ldots,\sigma\}\) of size \(\sigma+1\). Consider the string  
\[S=(012\cdots\sigma-1\ \ \sigma)(0124)(012346)(01234568)\cdots(012\cdots\sigma-2 \ \sigma)\]  
and its proper suffix  
\[S[2..]=(12\cdots\sigma-1\ \ \sigma)(0124)(012346)(01234568)\cdots(012\cdots \sigma-2\ \sigma).\]  
The non-self-referencing LZ77 factorization of \(S\) and \(S[2..]\) are:  
\[\mathsf{LZN}(S) = 0\,|\,1\,|\,2\,|\cdots\,|\sigma-1\,|\,\sigma\,|0124\ \ \ |012346\ \ \ |01234568\ \ |\cdots|012\cdots\sigma-2\ \sigma\ |\] \[\mathsf{LZN}(S[2..]) = 1\,|\,2\,|\cdots\,|\sigma-1\,|\,\sigma\,|01\,|\,24\,|0123\,|46\, |012345\,|68\cdots|012\cdots|\sigma-2\ \sigma\ |\]  
Observe that after the first occurrence of character \(\sigma\), each factor of \(\mathsf{LZN}(S)\) is divided into two smaller factors in \(\mathsf{LZN}(S[2..])\). Since \(\mathsf{zn}(S)=|\mathsf{LZN}(S)|=(\sigma+1)+(\frac{\sigma}{2}-1)=\frac{3 \sigma}{2}\) and \(\mathsf{zn}(S[2..])=|\mathsf{LZN}(S[2..])|=(\sigma)+(\sigma-2)=2\sigma-2\), \(\mathsf{zn}(S[2..])/\mathsf{zn}(S)=\frac{2\sigma-2}{(3\sigma/2)}=\frac{2 \sigma-2}{(3\sigma/2)}=\frac{2\sigma-2}{(3\sigma/2)}=\frac{2\sigma-2}{(3\sigma /2)}=\frac{2\sigma-2}{(3\sigma/2)}=\frac{2\sigma-2}{(3\sigma/2)}=\frac{2 \sigma-2}{(3\sigma/2)}=\frac{2\sigma-2}{(3\sigma/2)}=\frac{2\sigma-2}{(3\sigma /2)}=\frac{2\sigma-2}{(3\sigma/2)}=\frac{2\sigma-2}{(3\sigma/2)}=\frac{2\sigma -2}{(3\sigma/2)}=\frac{2\sigma-2}{(3\sigma/2)}=\frac{2\sigma-2}{(3\sigma/2)}= \frac{2\sigma-2}{(3\sigma/2)}=\frac{2\sigma-2}{(3\sigma/2)}=\frac{2\sigma-2}{ (3\sigma/2)}=\frac{2\sigma-2}{(3\sigma/2)}=\frac{2\sigma-2}{(3\sigma/2)}=\frac {2\sigma-2}{(3\sigma/2)}=\frac{2\sigma-2}{(3\sigma/2)}=\frac{2\sigma-2}{(3 \sigma/2)}=\frac{2\sigma-2}{(3\sigma/2)}=\frac{2\sigma-2}{(3\sigma/2)}=\frac{ 2\sigma-2}{(3\sigma/2)}=\frac{2\sigma-2}{(3\sigma/2)}=\frac{2\sigma-2}{(3\sigma /2)}=\frac{2\sigma-2}{(3\sigma/2)}=\frac{2\sigma-2}{(3\sigma/2)}=\frac{2\sigma -2}{(3\sigma/2)}=\frac{2\sigma-2}{(3\sigma/2)}=\frac{2\sigma-2}{(3\sigma/2)}= \frac{2\(\frac{4}{3}-\frac{2}{3\sigma}\), which tends to \(4/3\) as \(\sigma\) goes to infinity. We finally remark that \(|S|=n=\Theta(\sigma^{2})\) which in turn means that \(\sigma=\Theta(\sqrt{n})\).  
**Remark 1**.: One can generalize the string \(S\) of Lemma 2 by replacing \(0\) with \(0^{h}\) for arbitrarily fixed \(1<h\leq a\cdot\sigma\) for any constant \(a\). The upper limit \(a\cdot\sigma\) comes from the fact that the number of \(0\)'s in the original string \(S\) is exactly \(\frac{\sigma}{2}\). Since \(|S|=n=\Theta(\sigma^{2})\), replacing \(0\) by \(0^{h}\) with \(h<a\cdot\sigma\) keeps the string length within \(O(n)\). This implies that one can obtain the asymptotic lower bound \(4/3\) for any suffix \(S[h..]\) of length roughly up to \(n-\sqrt{n}\).  
Note also that the factorizations shown in Lemma 2 coincide with the self-referencing counterparts \(\mathsf{LZS}(S)\) and \(\mathsf{LZS}(S[2..])\), respectively. The next corollary immediately follows from Lemma 2 and Remark 1.  
**Corollary 1**.: _The Lempel-Ziv 77 factorization with/without self-references is non-monotonic._