The classic Impagliazzo--Nisan--Wigderson (INW) psesudorandom generator (PRG) (STOC `94) for space-bounded computation uses a seed of length $O(\log n \cdot \log(nwd/\varepsilon))$ to fool ordered branching programs of length $n$, width $w$, and alphabet size $d$ to within error $\varepsilon$. A series of works have shown that the analysis of the INW generator can be improved for the class of $\textit{permutation}$ branching programs or the more general $\textit{regular}$ branching programs, improving the $O(\log^2 n)$ dependence on the length $n$ to $O(\log n)$ or $\tilde{O}(\log n)$. However, when also considering the dependence on the other parameters, these analyses still fall short of the optimal PRG seed length $O(\log(nwd/\varepsilon))$.

In this paper, we prove that any ``spectral analysis'' of the INW generator requires seed length $$\Omega\left(\log n\cdot \log\log(\min\{n,d\})+\log n\cdot \log(w/\varepsilon)+\log d\right)$$ to fool ordered permutation branching programs of length $n$, width $w$, and alphabet size $d$ to within error $\varepsilon$. By ``spectral analysis'' we mean an analysis of the INW generator that relies only on the spectral expansion of the graphs used to construct the generator; this encompasses all prior analyses of the INW generator. Our lower bound matches the upper bound of Braverman--Rao--Raz--Yehudayoff (FOCS 2010, SICOMP 2014) for regular branching programs of alphabet size $d=2$ except for a gap between their $O(\log n \cdot \log\log n)$ term and our $O(\log n \cdot \log\log \min\{n,d\})$ term. It also matches the upper bounds of Koucky--Nimbhorkar--Pudlak (STOC 2011), De (CCC 2011), and Steinke (ECCC 2012) for constant-width ($w=O(1)$) permutation branching programs of alphabet size $d=2$ to within a constant factor.

To fool permutation branching programs in the stronger measure of $\textit{spectral norm}$, we prove that any spectral analysis of the INW generator requires a seed of length $\Omega(\log n\cdot \log\log n+\log n\cdot\log(1/\varepsilon)+\log d)$ when the width is at least polynomial in $n$ ($w=n^{\Omega(1)}$), matching the recent upper bound of Hoza--Pyne--Vadhan (ITCS `21) to within a constant factor.