  We show that the condition number of any cyclically contiguous $p\times q$
submatrix of the $N\times N$ discrete Fourier transform (DFT) matrix is at
least $$ \exp \left( \frac{\pi}{2} \left[\min(p,q)- \frac{pq}{N}\right]
\right)~, $$ up to algebraic prefactors. That is, fixing any shape parameters
$(\alpha,\beta):=(p/N,q/N)\in(0,1)^2$, the growth is $e^{\rho N}$ as
$N\to\infty$ with rate $\rho = \frac{\pi}{2}[\min(\alpha,\beta)-
  \alpha\beta]$. Such Vandermonde system matrices arise in many applications,
such as Fourier continuation, super-resolution, and diffraction imaging. Our
proof uses the Kaiser-Bessel transform pair (of which we give a self-contained
proof), and estimates on sums over distorted sinc functions, to construct a
localized trial vector whose DFT is also localized. We warm up with an
elementary proof of the above but with half the rate, via a periodized Gaussian
trial vector. Using low-rank approximation of the kernel $e^{ixt}$, we also
prove another lower bound $(4/e\pi \alpha)^q$, up to algebraic prefactors,
which is stronger than the above for small $\alpha, \beta$. When combined, the
bounds are within a factor of two of the numerically-measured empirical
asymptotic rate, uniformly over $(0,1)^2$, and they become sharp in certain
regions. However, the results are not asymptotic: they apply to essentially all
$N$, $p$, and $q$, and with all constants explicit.
