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 and a positive integer such that all submatrices of the Discrete Fourier Transform matrix over the field are nonsingular?

Currently, I have only counterexamples: Let be the degree of the smallest extension over which contains a nontrivial th root of unity. Then, I know a lot of primes for which the matrix 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 be the ring of polynomials of degree at most with coefficients in . Let be the group . Every function can be identified with the polynomial .  We will abuse the notation and write to represent both the function and the polynomial, where which-is-which will be clear from the context.

Let be the matrix representation of the Discrete Fourier Transform , where is a vector in containing at its th coordinate, . We know that the th coordinate of contains . The entries of the matrix are . Such a matrix is called the Vandermonde matrix.

For a polynomial , its support is the number of nonzero coefficients.

Satisfying the uncertainty principle. If the inequality

 is satisfied for every polynomial and a prime , we say that the field satisfies the uncertainty principle for .

If the above inequality is satisfied for all primes, then satisfies the uncertainty principle. For example, satisfies the uncertainty principle for all primes .

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

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

For example, can be , the complex numbers where .

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

Question: Is there an and a (family of) prime such that satisfies the additive uncertainty principle for ?

Question: Is there a prime and an such that in the field , all (square) submatrices of the Vandermonde matrix are nonsingular? Here, we assume that contains a th principal root of unity .

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 ?

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

Proposition 4.3 in EKL. Suppose is a field such that is a primitive root modulo a prime . Then satisfies the uncertainty principle.

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

Let . The proof of the above proposition requires that be irreducible over (which is the case indeed).

In Proposition 4.3, set . Since 2 is a primitive root modulo 11, the implication is that all polynomials in the ring satisfies the uncertainty principle i.e., . However, Chebotarev’s theorem does not apply here because the field does not contain . On the other hand, if we start from Chebotarev’s theorem and require to contain , then the proof of the above proposition breaks since it requires to contain no nontrivial 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.