Let $f(x) = \prod_{i=0}^{n-1}(x - \alpha_i)$ be a polynomial over finite field. Assume there exists $0 \leq j < n$ s.t. $\operatorname{ord}(\alpha_j) > n$. Given only roots $\alpha_i$ being distinct, what is the formula for the number of distinct nonzero coefficients of $f(x)$?

Some special case I am interesting in. Let $\alpha_i = \beta^{t_i}$ for some $t_i$ and $\beta$ s.t. $\operatorname{ord}(\beta) > n$. So $f(x)$ is the generating polynomial of the Reed-Solomon code of length $m > n$ and $\beta$ is a primitive $m$-th root of unity. E.g. $f(x) = (x-1)(x-\beta)(x-\beta^6) = x^3 + (1+\beta^2) x^2 + (1+\beta^2) x + 1$ for $\beta$ being a primitive element of $\mathcal{F}_8 \equiv \mathcal{F}_2[x]/\langle x^3 + x^2 + 1 \rangle$ has only $2$ distinct coefficients.

  • $\begingroup$ Are the roots $\alpha_i $ distinct? $\endgroup$
    – Amr
    Nov 26, 2015 at 15:43
  • $\begingroup$ Try looking up material on cyclotomic polynomials over finite fields. I found e.g. www-groups.mcs.st-and.ac.uk/~neunhoef/Teaching/ff/ffchap4.pdf. Of course over a finite field every non-zero element is a root of unity - some two powers $a^m=a^n$ must give the same result, and $a^{|m-n|}=1$ $\endgroup$ Nov 26, 2015 at 15:51
  • 1
    $\begingroup$ Which finite field is it? In general I doubt that there's very much you can say: you just have to look at which elementary symmetric polynomials of the roots happen to be $0$. $\endgroup$ Nov 26, 2015 at 16:25
  • $\begingroup$ @RobertIsrael: I have no assumptions about the finite field. It can be any $GF(q^p)$ for any prime $q$ and positive $p$. $\endgroup$ Nov 26, 2015 at 16:30
  • $\begingroup$ As long as the cardinality of the field is much larger than $n$, I see no reason that the coefficients can't all be distinct and nonzero. $\endgroup$ Nov 26, 2015 at 16:45


You must log in to answer this question.

Browse other questions tagged .