My question concern's a statement from the classic paper The equivalence problem for regular expressions with squaring requires exponential space.
Regular expressions with squaring are like ordinary regular expression but with a squaring operation. Let $RSQ(\Sigma) = \{ E \mbox{ is a regex with squaring} : L(E) \ne \Sigma^{\ast} \}$ be the test if some RegEx with squaring describes every word. In the paper the following is shown:
Theorem 2.1: There is a finite set $\Sigma$ such that if $M$ is any machine which recognizes $RSQ(\Sigma)$, then there is a constant $c > 1$ such that $M$ requires space (and hence time) $c^n$ on some input of length $n$ for infinitely many $n$.
By coding accepting computations by such regular expressions they continue to show that if $L \subseteq \{0,1\}^*$ is any language with a space bound of $2^n$, then we can reduce the membership problem of $L$ to $RSQ(\Sigma)$ for some $\Sigma$ (the alphabet needs to be enlarged to account for describing sequences of instantaneous descriptions of Turing machines).
Then the argument for the above Theorem relies on the following fact (Fact 2 in the paper) taken from another paper:
Let $S_1(n)$, $S_2(n)$ be tape constructable functions such that $$ \inf_{n\to \infty} \frac{S_1(n)}{S_2(n)} = 0 \qquad \mbox{ and } S_2(n) \ge \log(n). $$ Then there is a language $L \subseteq \{0,1\}^*$ accepted by some space $S_2(n)$ machine but by no space $S_1(n)$ machine.
It is used in the following manner:
Proof of Theorem 2.1: let $L$ be as in Fact 2 [the statement above] with $S_2(n) = 2^n$. Let $\Sigma$ be such that $L$ reduces to $RSQ(\Sigma)$.
If $RSQ(\Sigma)$ is accepted by some space $S(n)$ machine, then $L$ is accepted by some space $S(cn) + cn$ machine for some constant $c$ [this is a general property of reductions as stated earlier]. $$ \inf_{n\to \infty} \frac{S(cn) + cn}{2^n} > 0 $$ implies that $S(n) \ge d^n$ for some constant $d > 1$ and all $n$ which are multiples of $c$.
How do they know that $\inf_{n\to \infty} \frac{S(cn) + cn}{2^n} > 0$? Somehow the order of quantifiers in the statement of the fact seem not to match that kind of deduction. It does not say that if we have any machine with $S'(n)$ which also accepts $L$ then we must have $$ \inf_{n\to \infty} \frac{S'(n)}{S(n)} > 0. $$ It just says that if this equals zero, then we can choose some language accepted in space bound $S(n)$ but not in space bound $S'(n)$, so it depends on the firstly choosen $S'(n)$. But the argument of the proof does not seem to use it that way. Also the introduction "Let $L$ be as in Fact 2 [...]" seems problematic, for what space bound function $S'(n)$ in the numerator is $L$ choosen?
So how do this argument works? What am I missing here? Can someone please explain?
EDIT: Just let me add that if I accept $\inf_{n\to \infty} \frac{S(cn) + cn}{2^n} > 0$ then $S(n) \ge d^n$ for some $d > 1$ and all multiplies of $c$ is clear to me. For then we know for some $\varepsilon > 0$ we have $$ S(cn) > 2^n\varepsilon - cn $$ for all $n > N$ for some $N$. Write with $d > 1$ then $2^n = (d + \delta)^n \ge d^n + n d^{n-1}\delta \ge d^n + d^{n-1}\delta$ and as $\lim_{n\to \infty} \frac{c\varepsilon^{-1}n}{d^{n-1}} = 0$ we have $c\varepsilon^{-1}n \le d^{n-1}\delta$ for all $n$ sufficiently large, which gives $S(cn) \ge \varepsilon d^n$. Now choose $1 < \hat d < d$ and we find $\lim_{n\to \infty} \frac{\hat d^n}{\varepsilon d^n} = 0$, hence $\varepsilon d^n \ge \hat d^n$ for sufficiently large $n$. So understanding the following conclusions is not the problem.