# When does the Discrete Fourier Transform Matrix have Nonsingular Submatrices?

I am studying a coding theory problem. The question is this:

Open Question: Is there a prime $p$ and a positive integer $d$ such that all submatrices of the $p\times p$ Discrete Fourier Transform matrix over the field $GF(2^d)$ are nonsingular?

Currently, I have only counterexamples: Let $d$ be the degree of the smallest extension over $GF(2)$ which contains a nontrivial $p$th root of unity. Then, I know a lot of primes $p$ for which the matrix $V$ has a singular submatrix.

In this post, I am going to show a failed attempt to answer this question using the results in this paper by Evra, Kowalski, and Lubotzky.

Let me introduce some more context.

Let $R = E[x]/(x^p - 1)$ be the ring of polynomials of degree at most $p-1$ with coefficients in $E$. Let $Z_p$ be the group $\{0, 1, 2, \cdots, p-1\}$. Every function $f : Z_p \rightarrow E, f \in E^{p}$ can be identified with the polynomial $\sum_{t\in Z_p} f(t) x^t \in R$.  We will abuse the notation and write $f$ to represent both the function and the polynomial, where which-is-which will be clear from the context.

Let $V$ be the matrix representation of the Discrete Fourier Transform $T : R \rightarrow R, \hat{f} = V f$, where $f$ is a vector in $E^p$ containing $f(t)$ at its $t$th coordinate, $t\in Z_p$. We know that the $t$th coordinate of $\hat{f}$ contains $f(\omega_p^t)$. The entries of the matrix $V$ are $V_{ij} = \omega_p^{ij}$. Such a matrix is called the Vandermonde matrix.

For a polynomial $f(x)$, its support is the number of nonzero coefficients.

Satisfying the uncertainty principle. If the inequality

$supp(f) + supp(\hat{f}) \geq p +1$

is satisfied for every polynomial $f \in E[x]/(x^p-1)$ and a prime $p$, we say that the field $E$ satisfies the uncertainty principle for $p$.

If the above inequality is satisfied for all primes, then $E$ satisfies the uncertainty principle. For example, $E = \mathbb{C}$ satisfies the uncertainty principle for all primes $p$.

There is a theorem concerning the determinants of the Vandermonde-submatrices (see the appendix of the EKL paper).

Chebotarev’s Theorem. Let $\omega_p$ be a principal $p$th root of unity in a field $E$ which satisfies the uncertainty principle for $p$.  Then every submatrix of the Vandermonde matrix $V$ is nonsingular.

For example, $E$ can be $\mathbb{C}$, the complex numbers where $\omega_p = e^{-2\pi i/p}$.

Having this view, here are several rephrasals of my first question:

Question: Is there an $m$ and a (family of) prime $p$ such that $E = GF(2^m)$ satisfies the additive uncertainty principle for $p$?

Question: Is there a prime $p$ and an $m$ such that in the field $E = GF(2^m)$, all (square) submatrices of the Vandermonde matrix $V = (\omega_p^{jk})$ are nonsingular? Here, we assume that $E$ contains a $p$th principal root of unity $\omega_p$.

However, the EKL paper shows that the question about which fields satisfy the uncertainty principle is equivalent to the following:

Question (EKL): Is there an asymptotically good cyclic code for an infinite family of primes $p$?

My failed attempt. The Proposition 4.3 in this paper (by Evra, Kowalski, and Lubotzky) says that if $ord(E)$ is a primitive root modulo a prime $p$, then $E$ satisfies the uncertainty principle for $p$. Although the statement says $ord(E)$ has to be a prime, the argument carries through even when $ord(E)$ is a prime power.

Proposition 4.3 in EKL. Suppose $F$ is a field such that $ord(F)$ is a primitive root modulo a prime $p$. Then $F$ satisfies the uncertainty principle.

Although intriguing, this proposition doesn’t lead us to Chebotarev’s theorem.

Let $q(x) = 1+x+x^2+\cdots + x^{p-1}$. The proof of the above proposition requires that $q(x)$ be irreducible over $F$ (which is the case indeed).

In Proposition 4.3, set $F = GF(2), p = 11$. Since 2 is a primitive root modulo 11, the implication is that all polynomials $f$ in the ring $GF(2)[x]/(x^11 - 1)$ satisfies the uncertainty principle i.e., $supp(f) + supp(fhat) > p$. However, Chebotarev’s theorem does not apply here because the field $F$ does not contain $\omega_p$. On the other hand, if we start from Chebotarev’s theorem and require $F$ to contain $\omega_p$, then the proof of the above proposition breaks since it requires $F$ to contain no nontrivial $p$th root of unity.

Therefore, it seems like going as-it-is from Proposition 4.3 to Chebotarev’s theorem is a dead end. We’ve got to do something clever.

Afterthoughts. I have a code to exhaustively search each submatrix of a given Vandermonde matrix. Although my hope was that one can go from Proposition 4.3 to the Chebotarev’s theorem, my code gave me counterexamples. Only during writing this post I understood why.