# Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings +
## 4 Lower Bound for Greedy  
We proceed with the lower bound on the approximation ratio of \(\mathsf{Greedy}\). The best lower bound [13] (Theorem 11) that was known previously was  
\[\alpha_{\mathsf{Greedy}}(k,n)\geq\frac{5}{3\log_{3}(5)}=1.13767699\ldots\]  
for all \(k\geq 1\) and infinitely many \(n\). This bound was shown using unary words, which we will also use in our proof for the improved lower bound. A key concept for doing this is the sequence \(x_{n}\) described in the following lemma by [19]:  
Lemma 13 ([19] (Example 2.2)): _Let \(x_{n+1}=x_{n}^{2}+1\) with \(x_{0}=1\) and_  
\[\beta=\exp\left(\sum_{i=1}^{\infty}\frac{1}{2^{i}}\log\!\left(1+\frac{1}{x_{i }^{2}}\right)\right).\]  
_We have \(x_{n}=\left\lfloor\beta^{2^{n}}\right\rfloor\)._  
In this work, we use the shifted sequence \(y_{n}=x_{n+1}\), i.e., we start with \(y_{0}=2\). It follows that \(y_{n}=\left\lfloor\gamma^{2^{n}}\right\rfloor\), where \(\gamma=\beta^{2}=2.25851845\ldots\). Additionally, we need the following lemma:  
Lemma 14: _Let \(m\geq 1\) be an integer. Let \(f_{m}\colon\mathbb{R}_{>0}\to\mathbb{R}\) with_  
\[f_{m}(x)=x+\frac{m^{2}+1}{x}.\]  
_We have \(f_{m}(x)>2m\) for all \(x>0\)._  
Proof. : The unique minimum of \(f_{m}(x)\) is \(2\sqrt{m^{2}+1}\) for \(x=\sqrt{m^{2}+1}\). It follows that \(f_{m}(x)\geq 2\sqrt{m^{2}+1}>2\sqrt{m^{2}}=2m\). Now we can prove the new lower bound for \(\mathsf{Greedy}\):  
Theorem 2: _For all \(k\geq 1\) and infinitely many \(n\), we have_  
\[\alpha_{\mathsf{Greedy}}(k,n)\geq\frac{1}{\log_{3}(\gamma)}=1.34847194\ldots\ \.\]Proof. : Let \(\Sigma=\{a\}\) be a unary alphabet. We define \(w_{k}=a^{y_{k}}\). By Lemma 13, we have \(|w_{k}|\leq\gamma^{2^{k}}\). Applying Lemma 1 yields  
\[g(w_{k})\leq 3\cdot\log_{3}(\gamma)\cdot 2^{k}+o(2^{k}).\]  
In the remaining proof we show that on input \(w_{k}\), Greedy produces an SLP of size \(3\cdot 2^{k}-1\), which directly implies \(a_{\mathsf{Greedy}}(1,n)\geq 3/(3\log_{3}(\gamma))\). We start with the SLP \(\mathbb{A}_{0}\) which has the single rule \(S\to a^{y_{k}}\). Consider now the first round of the algorithm, i.e., we need to find a maximal string \(a^{x}\) of \(\mathbb{A}_{0}\) such that the grammar \(\mathbb{A}_{1}\) with rules  
\[X_{1}\to a^{x},\;S\to X_{1}^{y_{k}\;\mathrm{div}\;x}a^{y_{k}\;\mathrm{mod}\;x}\]  
has minimal size. We have \(|\mathbb{A}_{1}|=x+(y_{k}\;\mathrm{div}\;x)+(y_{k}\;\mathrm{mod}\;x)\geq x+y_{ k}/x\). By the definition of \(y_{k}\) we have \(|\mathbb{A}_{1}|\geq x+(y_{k-1}^{2}+1)/x\). Applying Lemma 14 yields \(|\mathbb{A}_{1}|\geq 2y_{k-1}+1\). Please note that for \(x=y_{k-1}\) this minimum is achieved, i.e., we can assume that [PERSON] selects the maximal string \(a^{y_{k-1}}\) and \(\mathbb{A}_{1}\) is  
\[X_{1}\to a^{y_{k-1}},\;S\to X_{1}^{y_{k-1}}a.\]  
Each maximal string of \(\mathbb{A}_{1}\) is either a unary word over \(X\) or a unary word over \(a\), i.e., we can analyze the behavior of [PERSON] on both rules independently. The rule \(X_{1}\to a^{y_{k-1}}\) is obviously treated similarly as the initial SLP \(\mathbb{A}_{0}\), so we continue with analyzing \(S\to X_{1}^{y_{k-1}}a\). However, again, the same arguments as above show that [PERSON] introduces a rule \(X_{3}\to X_{1}^{y_{k-2}}\) which yields \(S\to X_{3}^{y_{k-2}}X_{1}a\) as the new start rule. This process can be iterated using the same arguments for the leading unary strings of length \(y_{i}\) for some \(i\in[1,k]\). The reader might think of this process as a binary tree, where each node is labeled with a rule (the root is labeled with \(S\to a^{y_{k}}\)) and the children of a node are the two rules obtained by [PERSON] when the rule has been processed. We assume that the left child represents the rule for the chosen maximal string and the right child represents the parent rule where all occurrences of the maximal string are replaced by the new nonterminal. In Figure 2 this binary tree is depicted for the steps we discussed above.