I'm working through a lower bound argument, to show that most Boolean circuits require exponential circuit size. I've hit a wall trying to fill in the details for a bounding argument and was wondering if anyone would be able to help me fix the issue.
Let $\epsilon \in (0, 1)$. Let $n$ denote the number of inputs for the circuit, and let $G$ be the maximum number of gates allowed in the circuit. Suppose that: $$G < 2^{n}(1-\epsilon)/n - 2n^{2}.$$
Let $a = (3e)^{2}$, and let $x = a(G + 2n^{2})$. Let $y = a2^{n}(1-\epsilon/2)$. We have the following lemma.
Lemma: If $n \geq 2[(1-\epsilon)/\epsilon] \cdot \log_{2}(a(1-\epsilon/2))$, then $x \leq y/\log_{2}(y)$.
Proof (Attempt): Denote: $$ n_{0} = 2[(1-\epsilon)/\epsilon] \cdot \log_{2}(a(1-\epsilon/2)). $$
We have that: \begin{align*} x &= a(G + 2n^{2}) \\ &\leq a2^{n}(1-\epsilon)/n \\ &\leq a2^{n}(1-\epsilon)/n_{0} \\ &\leq a2^{n-1}\epsilon/\log_{2}(a(1-\epsilon/2)). \end{align*}
While I can get $y$ in the numerator (by bounding $\epsilon < 2(1-\epsilon/2)$), I'm struggling with the denominator. In particular, $\log_{2}(a(1-\epsilon/2))$ almost looks like $\log_{2}(y)$. However, increasing the denominator makes the function smaller.
Any insights or suggestions would be greatly appreciated! Thank you in advance to anyone who reads this!