# Vandermonde Submatrices and Arithmetic Progressions

[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-$p$ Vandermonde matrix over a finite extension of $GF(2)$ are invertible where $p$ 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 $AP_k$ denote an arithmetic progression of length $latek k$. Let $[N] := \{1, 2, \cdots, N\}$ for $N \in \mathbb{N}$.

The Szemerédi theorem says, any “sufficiently dense” subset $S \subset [N]$ contains infinitely many $AP_k$ for all $k \in \mathbb{N}$. A finitary version says: Fix your favourite $k \in \mathbb{N}, \delta \in [0, 1]$. Then,  there exists a natural $N := N_{k, \delta}$ such that if you look any subset $S \subset [N]$ of size at least $\delta N$, you will find an $AP_k$. Yet another version says:

Szemerédi’s Theorem. The size of the largest subset $S \subset [N]$ without an $AP_k$ cannot be too large; in particular, it is $o(N)$.

Recall that a function $f(x)$ is $o(g)$ if it grows too slow compared to $g(x)$, so that $\lim_{N\rightarrow \infty}{f(x)/g(x) = 0}$.

Recall that the $(r,c)$ entry of an order-$p$ Vandermonde matrix $V^\prime$ is just $w_p^{(r-1) (c-1)}$ where $\omega_p$ is a principal $p$th root of unity in the field $\mathbb{F}$. This means, the $r$th row of $V^\prime$ is

$x(r) = (1, \omega_p^{(r-1)}, \omega_p^{2(r-1)}, \cdots, \omega_p^{(p-1)(r-1)})$ ,

and the $c$th column is

$y(c) = (1, \omega_p^{(c-1)}, \omega_p^{2(c-1)}, \cdots, \omega_p^{(p-1)(c-1)})^T$ .

We can generalize the row vector $x(r)$ as $x(r;a, d)$ for some integers $a\geq 0, d \geq 1$ where

$x(r; a)_i := \omega_p^{a + (i-1)d}$ so that

$x(r) := x(r; 0,1)$.

Now, let $S = \{s_1, \cdots, s_k\} \in [p]$ be a set of arbitrary distinct nongenative integers. For some positive integer $d$, we can build a generalized Vandermonde matrix $V := V(S, d)$ as follows. The $(r, t)$th entry of $V$ would be

$\omega_p^{s_r + (t-1) d}$

so that the $r$th row becomes

$x(r; s_r, d) = (\omega_p^{s_r}, \omega_p^{s_r+d(r-1)}, \omega_p^{s_r+2d(r-1)}, \cdots, \omega_p^{s_r+(p-1)d(r-1)})$ ,

and the $t$th column of $V$ has the form

$v(t) := (\omega_p^{s_1+(t-1)d}, \omega_p^{s_2+(t-1)d}, \cdots, \omega_p^{s_k+(t-1)d})^{\text{T}}$

Since the exponents of $\omega_p$ along any row of $V$ form an arithmetic progression, it is easy to see that $V$ is invertible. (Why? When computing the determinant, we can factor out $\omega_p^{a_r}$ from the $r$th row for $r \in [k]$, leaving a Vandermonde matrix of order $k$ generated by $\omega_p^d$. This matrix is non singular since $\omega_p^d$ is also a $p$th root of unity.)

Let $A$ be the set of column-indices of $V$ above, and recall that this is an arithmetic progression in $[p]$. What can we say about $A$?

Let $W$ be a proper subspace of $\mathbb{F}^k$ so that $dim(W) < k$. Suppose $A = \{t \in Z_p \mid v(t) \in W\}$. By our observation above, $A$ cannot contain an arithmetic progression of length $k$, because otherwise, the matrix $V(A)$ would be invertible and its columns $\{v(t) : t \in A\}$ would span $\mathbb{F}^k$; since $v(t) \in W$ by assumption, it would imply $dim(V) = k$, a contradiction.

This leads us to the following observation.

Observation: If $A \subset [p]$ contains an arithmetic progression of length $k$, then

$dim\ span\ \cup _{t \in A} v(t) \geq k$.

Now let us ask the following question.

Question: Let $W$ be an arbitrary strict subspace of $\mathbb{F}^k$. If we pick a $t \in \mathbb{Z}_p$ at random, what is the probability that $v(t) \in W$?

Suppose there is a set $A \in \mathbb{Z}_p$ such that the vectors $span\{v(a) \mid a\in A \} = span(W)$. Since $W$ is a strict subspace of $\mathbb{F}^k$, $A$ does not contain an arithmetic progression of length $k$, and $\vert A \vert = o_k(p)$ by Szemeredi’s theorem. The probability that $v(t) \in W$ equals the probability that $t \in A$, which is $\vert A \vert / p = o(1)$, which tends to zero as $p$ goes to infinity.

Lemma (Due to Alex Russell). Let $W$ be an arbitrary strict subspace of $\mathbb{F}^k$. If we pick a $t \in \mathbb{Z}_p$ at random,

$\displaystyle \Pr_{t \sim \mathbb{Z}_p}[ v(t) \in W ] = o_k(p)/p = o_k(1)$

as $p$ goes to infinity.

We are ready to prove the following nontrivial statement about the minors of the Vandermonde matrix. (This theorem is due to Alex Russell and Ravi Sundaram.)

Let $p$ be a prime and $V$ be an order-$p$ Vandermonde matrix over the field $\mathbb{F}$ containing a principal $p$th root of unity. Let $V_{R,C}$ be the submatrix of $V$ indexed by the rows in $R$ and columns in $C$.

Theorem A (Due to Alex Russell).  Let $k < p$ a constant.  Select two size-$k$ subsets $R, A \subset \mathbb{Z}_p$ where $R$ is arbitrary and $A$ is uniformly random. The probability that the submatrix $V_{R,A}$  is invertible is $1 - o_k(1)$, i.e., the probability tends to one as $p$ goes to infinity.

The outline of the proof is as follows. We select $k$ distinct random integers one by one and add it to a set $A$ which is initially empty. At any time, let $W = span \cup_{a \in A} v(a)$. Everytime we pick a random $t \in \mathbb{Z}_p$, we invoke the lemma above to show that $\Pr[v(t) \in W] \leq (k + o(p))/p = o(1)$ as $p$ goes to infinity. We repeat this for $k$ times. Because the samples are independent, the probability that some $t$ (out of the $k$ samples) is bad is at most $k o_k(1)$. If this happens, we say that the subset $C$ is bad. Otherwise, $dim(W) = k$ and we got ourselves an invertible $k\times k$-submatrix $V_{R,A}$ given by the columns $\{v(a)\}$ for all $a\in A$.

A Chebotarev-like Statement.  Suppose the field $\mathbb{F}$ contains all $p$th roots of unity, let $V$ be the corresponding Vandermonde matrix. A matrix is totally invertible if every submatrix is invertible. Chebotarev’s thoerem states that the matrix  $V$ is totally invertible.

Theorem A allows us to make a probabilistic statement which is similar to Chebotarev’s theorem in spirit. Continuing the proof-outline of Theorem A, suppose $D$ is an arbitrary subset of $\mathbf{Z}_p$ of a constant size. Similarly, let $S$ be a uniformly random subset of $\mathbb{Z}_p$ of a constant size. Let $k^\prime = \min{(\vert D \vert, \vert A \vert)}$. Let $V^\prime := V_{D, S}$.

The probability that some order-$k$ submatrix of $V^\prime$ is singular is no more than

$\displaystyle \sum_{2\leq k \leq k^\prime}{ {\vert S \vert \choose k} {\vert D \vert \choose k} k o(1)}.$

This probability is $o(1)$ as long as the sets $S, D$ have constant sizes. Also notice that the same argument holds if we use the transpose $V^{\text{T}}$ for $V$. This leads us to the following corollary.

Corollary. Fix $k \in [p]$. Select two constant-size subsets $D, S \subset \mathbb{Z}_p$ where $D$ is arbitrary and $S$ is uniformly random. Then, the submatrices $V_{S,D}$ and $V_{D,S}$ are totally invertible with probability $1- o(1)$.

An attempt via Schwartz-Zippel. Let $M$ be the set of $p$th roots of unity contained in a field $\mathbb{F}$. Select a set $T = \{t_1, \cdots, t_k\} \subset \mathbb{Z}_p$ and a set of $k$ distinct $p$th roots of unity $X = \{x_1, \cdots, x_k\}$. Let $q(X) := det(V_{T, X})$ be the determinant of the order-$k$ submatrix $V_{T,X}$ of the Vandermonde matrix $V := (\omega_p^{ij})_{i,j\in \mathbb{Z}_p}$ obtained from the rows in $T$ and the columns in $X$.

Notice that $deg(x_j)$ in the $k$-variable polynomial $q(X)$ is $t_j$. It can be shown that the number of zeros of $q(X)$ is at most $\sum_j{t_j}p^{k-1}$. Consequently, if the elements of $X \subset M$ are selected uniformly at random from all size-$k$ subsets, the probability that $q(X) = 0$ will be at most $kd/p$ where $d = \max_j{t_j}$.

For our coding theory problem, $k$ is at most the number of data disks, $d$. Set $T = \{0, \cdots, d-1\}$, and let $X \subset M$ be a random subset of size $d$. Let $V^\prime := V_{T, X}$. The probability that some submatrix of $V^\prime$ is singular is no more than

$\displaystyle \sum_{2 \leq k \leq d}{ {d \choose k}^2 kd/p }.$

This probability is at most ${2d \choose d}d^2/p \approx 2^{2d}d^2/p\sqrt{\pi d}$. It will be at most $1/2$ if $p \geq 2^{2d}d^{3/2}$. Not great, but as Don Knuth said, a bound is a bound.