Estimating the order of $t$ from the given inequality

Question

While performing certain calculations in the context of Shannon's counting argument for reversible circuits, I came across the following inequality

$$(2^3!)[(n+3t)]^{3t} \geq \frac{(2^n!)}{2}$$

where $!$ denotes factorial.

How to estimate (the order of) $t$ from the above expression (in the asymptotic sense)? I guess the Stirling approximation might be useful somehow.

Answer 1

Expanding to first order in $n$ and $t$ around $(n,t) = (\infty,0)$, we obtain $$ t\geq \frac{\sqrt{2 \pi } \left(2^n+1\right)^{2^n+\frac{1}{2}} \exp \left(-2^n+\frac{1}{12 \left(2^n+1\right)}-\frac{1}{360 \left(2^n+1\right)^3}+\frac{1}{1260 \left(2^n+1\right)^5}-\frac{1}{1680 \left(2^n+1\right)^7}-1\right)-80640}{241920 \log n} \text{,} $$ which is $$ O\left( \frac{(2^n)^{2^n + 1/2}\mathrm{e}^{-2^n}}{\log n} \right) \text{.} $$So the big piece is $(2^n)^{2^n}$ as expected from the Stirling approximation (eqn. (22)), $2^n! \approx \sqrt{2\pi} (2^n)^{2^n+1/2} \mathrm{e}^{-2^n}$.

---

Added in response to comment...

This is computed using Mathematica 11.3.

Assuming[{n > 1},
  Simplify[
    Reduce[
      Normal[Series[
        8! (n + 3 t)^(3 t) - (2^n)!/2, 
        {n, \[Infinity], 1}, 
        {t, 0, 1}
      ]] >= 0, 
      t, 
      Reals
    ]
  ]
]
TeXForm[%]

(* Output:  t >= (-80640 + (1 + 2^n)^(1/2 + 2^n) E^(-1 - 2^n - 1/(1680 (1 + 2^n)^7) + 1/(1260 (1 + 2^n)^5) - 1/(360 (1 + 2^n)^3) + 1/(12 (1 + 2^n))) Sqrt[2 \[Pi]])/(241920 Log[n]) *)
(* Output:  t\geq \frac{\sqrt{2 \pi } \left(2^n+1\right)^{2^n+\frac{1}{2}} \exp \left(-2^n+\frac{1}{12 \left(2^n+1\right)}-\frac{1}{360 \left(2^n+1\right)^3}+\frac{1}{1260 \left(2^n+1\right)^5}-\frac{1}{1680 \left(2^n+1\right)^7}-1\right)-80640}{241920 \log (n)} *)

It can be a good idea to swap the ordering of the expansion variables to see if, and if so, why, there are changes. In this case, there are none.

...
        {t, 0, 1}
        {n, \[Infinity], 1}, 
...

(*  same output  *)