# Question on deduction that a certain problem requires exponential space

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.

For every space-constructible $$S_2(n)$$, there exists $$L \in \mathbf{DSPACE}(S_2(n))$$ such that for every space constructible $$S_1(n) \leq o(S_2(n))$$, $$L \not \in \mathbf{DSPACE}(S_1(n))$$.