Problem 43: Rank Lower Bound

Suggested by	Madhu Sudan
Source	Bertinoro 2011
Short link	https://sublinear.info/43

We want to prove that the following tall matrix has full column rank. The columns are indexed by $a_1, \ldots ,a_k$ from the field $F_{2^n}$ where $n$ is prime; the rows are indexed by degrees $d_1 \ldots d_r$. The entry in the $i$th column and $j$th row is equal to $a_i^{d_j}$.

Question: Is it true that for all $k$ there exists an $r$ such that for all $d_1,...,d_r$ that are powers of $2$ and for all $a_1,...,a_k$ that are linearly independent over $F_2$, the rank of the matrix is $k$?

Background: Note that if $d_i = i$ and $r \geq k$, then the matrix is Vandermonde and so has full rank. If $d_i = 2^i$, then also the matrix has full rank (Lemma 19 in [GrigorescuKS-08]). The general case, when $d_i$'s are arbitrary, and not successive powers of two remains open (Conjecture 5.9 in [BenSassonGMSS-11]).