Chebotarev's theorem on roots of unity says that all the minors of a prime-length DFT matrix over the complex numbers are nonzero. I was wondering if there was an analogue for finite fields.


More precisely, let $p$ be prime and $\omega=e^{2\pi i/p}$, the complex $p$th root of unity, and let $\Omega$ be the matrix given by $\Omega\_{ij}=\omega^{ij}$, for $i,j \in \{0,1,\dots,p-1\}$. Then Chebotarev's theorem on roots of unity says that every square submatrix of $\Omega$ is nonsingular; see [wikipedia](https://en.wikipedia.org/wiki/Chebotaryov_theorem_on_roots_of_unity).


Alternatively, this is equivalent to stating that, for a complex-valued polynomial $f$ of degree less than $p$, if $f$ evaluates to zero for $t$ distinct powers of $\omega$, then either $f$ is zero, or $f$ has at least $t+1$ terms, or in other words, $$|\mathrm{supp}(f)| + |\mathrm{supp}(\hat{f})| > p.$$


Suppose then that $q$ is a prime power for which $p$ divides $q-1$, such that $\mathbf{F}\_q$ contains a primitive $p$th root of unity $\omega$. Does the analogue hold there? I am particularly interested in the case that $q$ is prime.


The $2 \times 2$ square submatrices will be nonsingular because a polynomial $x^a + cx^b$, where $p>a>b\geq 0$, $c \neq 0$ will have a root $\omega^i$ if and only if $\omega^{(a-b)i}=c$, which will hold for at most one $i \in [p]$. Computation shows the analogue holds for the $p=7$th roots of unity modulo $q=29$.



Finite field analogue of Chebotaryov theorem on roots of unity?
Not for $GF(p)$ of prime cardinality. Consider a nontrivial factorization $p-1=uv$ which always exists. Let $w$ be primitive in $GF(p)^{\ast}$ The "regular" DFT submatrix which is made up of $u^{th}$ row and every $v^{th}$ column entry is an all 1 matrix and singular. More generally, when we have $GF(p^m)$ a primitive element has order $p^m-1$ and since $p^m-1=(p-1)(p^{m-1}+p^{m-2}+\cdots+1)$ is a valid factorization a similar argument holds. Thus the answer is no for any finite field. 


**Edit in response to comment by OP:** Thanks for clarifying the question. I believe that it would fail in that case as well, since there is an extra dependency in finite fields: All elements, including $\omega$ of order $p$ inside a $GF(q)$ with $p|(q-1)$, have a characteristic polynomial $P$ of moderate degree. In this case, the set of determinant polynomials (which is quite large) would have to avoid all multiples of $P$ which is very unlikely.
There may well be a pigeonhole type proof for this. Some quick computations confirmed this. Take $GF(23)$ and $w=2$ of order $11$. Then the indices $I\times J=(0,2,6)\times(0,1,3)$ for example lead to $$[w^{I(k)J(l)}]\_{k,l=1,\ldots,3}$$ the $3\times3$ submatrix with zero determinant.


