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 pth 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 tth coordinate, t\in Z_p. We know that the tth 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 pth 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 pth 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 pth 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.

One thought on “When does the Discrete Fourier Transform Matrix have Nonsingular Submatrices?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s