*[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”