Estimating a sum of cosines related to random walk on $\mathbb{Z}_{n}^{n}$ I'm looking for help asymptotically estimating a sum. For positive integer $n$, let $[n]:=\{0,2,\dots,n-1\}.$ (I know it's nonstandard notation, but it makes the expressions easier to write.) Let $t=t(n)$ also be a positive integer, which goes to infinity with $n.$ The sum of interest is
$$S(n,t):=\sum_{(j_{1},\dots,j_{n}) \in [n]^{n} \setminus \bf{0}} \left(\frac{1}{2n}\sum_{k=1}^{n}\left(1+\cos\frac{2\pi j_{k}}{n}\right)\right)^{2t}$$
where $\bf{0}$ is the all zeros tuple $(0,0,\dots,0).$ Really, I'm looking for the smallest value of $t(n)$ for which $S(n,t)=o(1).$ Here are my initial thoughts:
It seems useful to use the double angle formula to rewrite $S(n,t)$ as
$$\sum_{(j_{1},\dots,j_{n}) \in [n]^{n} \setminus \bf{0}}\left(\frac{1}{n}\sum_{k=1}^{n}\cos^{2}\left(\frac{\pi j_{k}}{n}\right) \right)^{2t}.$$
The inner term $\left(\frac{1}{n}\sum_{k=1}^{n}\cos^{2}\left(\frac{\pi j_{k}}{n}\right) \right)^{2t}$ maximizes when $(j_{1},j_{2},\dots,j_{n})$ is a tuple with $n-1$ coordinates equal to $0$, and the other coordinate set at either $1$ or $n-1$. In this case, the inner term is $\left(\frac{n-1}{n}+\frac{1}{n}\cos^{2}(\pi/n) \right)^{2t}=\left(1 - \frac{\sin^{2}(\pi/n)}{n}\right)^{2t}.$ The ratio $\frac{\sin^{2}(\pi/n)}{n}$ goes to $0$ roughly as $\frac{\pi^{2}}{n^{3}}$, so the largest term in the sum is (roughly) $\left(1-\frac{\pi^{2}}{n^{3}}\right)^{2t} \leq e^{-2\pi^{2} t/n^{3}}.$ Using this somewhat crudely, we can say that the sum is bounded above by 
$$e^{-2\pi^{2}t/n^{3}}\cdot n^{n}$$
by simply factoring the largest term out of the sum and noting that the ratio of any other term to it is at most $1.$ We then need $t=\Omega(n^{4}\log n) $ for the bound $e^{-2\pi^{2}t/n^{3}}\cdot n^{n}$ to even be $O(1)$. 
My thought/hope, however, is that with a less crude bound than the one I've given it can be shown that $t=\Theta (n^{3}\log n)$ is good enough. It seems that more careful accounting of the smaller terms in $S(n,t)$ is needed for this to work, though I haven't made much progress in this regard. 
For context, $S(n,t)$ comes from a problem about the simple lazy random walk on $\mathbb{Z}_{n}^{n}$. Each term in the sum is an eigenvalue of this random walk, and $S(n,t)$ can be used to find a bound on its mixing time, which I know is of order $n^{3}\log n.$
Thanks for the help.
 A: I'll start from $S(n,t)=\sum_{(j_{1},\dots,j_{n}) \in [n] \setminus \mathbf{0}}\left(\frac{1}{n}\sum_{k=1}^{n}\cos^{2}\left(\frac{\pi j_{k}}{n} \right)\right)^{2t}.$ For $(j_{1},\dots,j_{n}) \in [n] \setminus \mathbf{0}$, let $|(j_{1},\dots,j_{n})|=\#\{k \in [n]:j_{k} \neq 0\}.$ For any tuple we consider in $[n] \setminus \mathbf{0}$, then, $|(j_{1},\dots,j_{n})| \geq 1.$ The term corresponding to $(j_{1},\dots,j_{n})$ in the sum $S(n,t)$ can be written 
$$\left(\frac{1}{n}\sum_{k=1}^{n}\cos^{2}\left(\frac{\pi j_{k}}{n} \right)\right)^{2t}=\left(\frac{n-|(j_{1},\dots,j_{n})|}{n}+\frac{1}{n}\sum_{k: j_{k} \neq 0}\cos^{2}\left(\frac{\pi j_{k}}{n} \right)\right)^{2t}=\left(1-\frac{1}{n}\sum_{k:j_{k} \neq 0}\sin^{2}\left(\frac{\pi j_{k}}{n} \right)\right)^{2t}.$$
Using the inequality $(1-x)^{r} \leq e^{-rx}$ for $x \leq 1$ and $r \geq 0$ on each term in $S(n,t)$, we have
$$S(n,t) \leq \sum_{(j_{1},\dots,j_{n}) \in [n] \setminus \mathbf{0}}\exp\left\{-\frac{2t}{n}\sum_{k:j_{k} \neq 0}\sin^{2}\left(\frac{\pi j_{k}}{n}\right) \right\}=\sum_{(j_{1},\dots,j_{n}) \in [n] \setminus \mathbf{0}}\prod_{k:k \neq 0}\exp\left\{-\frac{2t}{n}\sin^{2}\left(\frac{\pi j_{k}}{n}\right) \right\}.$$
The RHS above is simply $\left(\sum_{j=0}^{n-1}\exp\left\{-\frac{2t}{n}\sin^{2}\left(\frac{\pi j}{n}\right) \right\}\right)^{n}-1.$ Now, 
$$\sum_{j=0}^{n-1}\exp\left\{-\frac{2t}{n}\sin^{2}\left(\frac{\pi j}{n}\right) \right\} \leq 1+2\sum_{j=1}^{\lfloor n/2\rfloor}\exp\left\{-\frac{2t}{n}\sin^{2}\left(\frac{\pi j}{n}\right) \right\}.$$
(If $n$ is odd, then this is an equality; if $n$ is even, then it is an overestimate by only $e^{-2t/n},$ which will end up being negligible with our choice of $t.$) For $x \in [0,\pi/2]$, we have $\sin(x) \geq x-x^{3}/6$, and thus $\sin^{2}(x) \geq x^{2}(1-x^{2}/6)^{2}.$ Therefore,
$$S(n,t) \leq \left(1+2\sum_{j=1}^{\lfloor n/2\rfloor}\exp\left\{-\frac{2t\pi^{2}j^{2}}{n^{3}}\left(1-\frac{\pi^{2}j^{2}}{6n^{2}}\right)^{2} \right\}\right)^{n}-1$$
The sum $\sum_{j=1}^{\lfloor n/2 \rfloor}\exp\left\{-\frac{2t\pi^{2}j^{2}}{n^{3}}\left(1-\frac{\pi^{2}j^{2}}{6n^{2}}\right)^{2} \right\}$ can be shown to be $O\left(\exp\left\{-\frac{2t\pi^{2}}{n^{3}}\right\}\right)$; it isn't too hard to show this, but it is ugly, so I'll omit it here. Long story short, pull out the $j=1$ term and show that the factor which remains $O(1).$
We reach $S(n,t) \leq \left(1+O\left(\exp\left\{-\frac{2t\pi^{2}}{n^{3}}\right\}\right)\right)^{n}-1$. If $t=\frac{1}{2\pi^{2}}n^{3}\log n+cn^{3}$ for $c>0$, then 
$$S(n,t) \leq \left(1+O\left(\frac{e^{-2\pi^{2}c}}{n}\right)\right)^{n}-1=O(e^{e^{-2\pi^{2}c}})-1.$$
This goes to $0$ in $c$. It follows from this that for any $\varepsilon>0$, we may find some $c$ such that for $t=\frac{1}{2\pi^{2}}n^{3}\log n+cn^{3}$, $S(n,t) < \varepsilon.$
