[This post, which is based on an ongoing discussion with Alex Russell and Ravi Sundaram, contains some unpublished results.]
Currently, we are asking whether all submatrices of the order- Vandermonde matrix over a finite extension of
are invertible where
is prime. The answer is “no” in general: there are examples of fields where the Vandermonde matrix has a singular submatrix.
We can ask an easier(?) question, though. What happens if we randomly sample a set of columns and look into submatrices formed by a subset of the sampled columns. With a touch of beautiful insight, Professor Russell has connected Szemeredi’s theorem on arithmetic progressions with this question.
Let denote an arithmetic progression of length $latek k$. Let
for
.
The Szemerédi theorem says, any “sufficiently dense” subset contains infinitely many
for all
. A finitary version says: Fix your favourite
. Then, there exists a natural
such that if you look any subset
of size at least
, you will find an
. Yet another version says:
Szemerédi’s Theorem. The size of the largest subset
without an
cannot be too large; in particular, it is
.
Recall that a function is
if it grows too slow compared to
, so that
.
Continue reading “Vandermonde Submatrices and Arithmetic Progressions”