# Three theorems on the number of nonzero coefficients of a polynomial

The number of positive real roots of a polynomial with real coefficients is strictly smaller than the number of nonzero coefficients of the polynomial. This is an immediate corollary of Descartes' rule of signs.

For a polynomial with complex coefficients of degree at most $p-1$, with $p$ prime, the number of distinct roots of the polynomial which are degree-$p$ roots of unity is strictly smaller than the number of nonzero coefficients of the polynomial. As observed by Tao, this is equivalent to an uncertainty inequality for prime-order groups.

For a polynomial over a field of zero characteristic, the multiplicity of any of its non-zero roots is strictly smaller than the number of nonzero coefficients of the polynomial. To my knowledge, this first appeared in a paper by Brindza.

Are these results reducible to each other? (Well, the ground fields are not quite the same, and yet...) Are there any other similar results known? And, ultimately, is there any "common parent" from which all these results can be derived?

• There are also complementary statements about the number of $\mathbb{Q}_p$-roots, or the number of $\mathbb{F}_q(T)$-roots that a polynomial with $m$ non-zero terms may have. In either case: $\ll m$, with an implied coefficient depending on the local field at hand. Aug 5, 2018 at 19:01
• A higher dimensional extension of such results is found in Khovanskii's theory of fewnomials. For a summary, I can refer to this question that I have asked mathoverflow.net/questions/214671/… Aug 5, 2018 at 19:45
• @VesselinDimitrov: As I see it, a distinguishing feature of the three theorems that I mentioned is their sharpness; the number of certain roots is at most the number of nonzero coefficients less $1$, which is the precise bound.
– Seva
Aug 5, 2018 at 19:51
• @Seva: True, the higher dimensional results on bounding the Betti numbers of a fewnomial's zero locus are less precise, and non-sharp, though in the same spirit. Regarding the variant for non-Archimedean local fields, I have to correct myself in that the $\mathbb{F}_q(T)$ case has actually the sharp bound of $q^{m-1}$ on the number of distinct roots of a polynomial with $m$ non-zero coefficients: see the paper Zeros of sparse polynomials over local fields of characteristic $p$, by Bjorn Poonen. Lenstra's reference there addresses the $\mathbb{Q}_p$ variant, but with a non-sharp bound. Aug 5, 2018 at 20:02

Given a subset $U$ of a field $\mathbb F$ of zero characteristic, and $N\in\mathbb N\cup\{\infty\}$, consider the following property:
For any polynomial $P$ over $\mathbb F$ of degree $\deg P<N$, the number of elements of $U$ which are roots of $P$ is strictly smaller than the number of nonzero coefficients of $P$.
The observation mentioned above is as follows: for a set $U\subseteq\mathbb F^\times$ to have the stated property, it is necessary and sufficient that for any pairwise distinct elements $u_1,\dotsc,u_k\in U$, and any integers $0\le n_0<\dotsb<n_{k-1}<N$, the matrix $$\begin{pmatrix} u_1^{n_0} & \dotsb & u_k^{n_0} \\ \vdots & & \vdots \\ u_1^{n_{k-1}} & \dotsb & u_k^{n_{k-1}} \end{pmatrix}$$ were non-degenerate.