Let $f(x) = a_1x^{z_1} + a_2x^{z_2} + \cdots + a_kx^{z_k}$ be a polynomial with coefficients $(a_1, \ldots, a_k) \in \mathbb{F}_q^*$ and $z_i$ are distinct positive integers. If I need to compute the number of nonzero terms in the expansion of $f(x)^m$, the upper bound would be $\binom{m+k-1}{k-1}$ (from the multinomial theorem). Instead, I'd like to compute the lower bound, since sometimes there will be cancellations, for example:
Case 1: From $a_1a_3x^{z_1+z_3} + \cdots + a_2a_4x^{z_2+z_4} + \cdots$, if $z_1+z_3 = z_2+z_4$ then we have a collision $(a_1a_3 + a_2a_4)x^{z_1+z_3}$. From this, the number of nonzero terms decreases by 1.
Case 2: If $a_1a_3 + a_2a_4 \equiv q\mbox{ (mod q)}$ then this term is completely cancelled and the number of terms is decreased by an additional 1 (2 in total).
How can I compute this lower bound?
Also, is it possible to determine the best value for the exponents in $f(x)$ so that the lower bound is the lowest possible? I have a special case where $f(x) = a_1x^{z} + a_2x^{z + \alpha} + \cdots + a_kx^{z + (k-1)\alpha}$ seems to be the best case but I can't prove it. It seems that, if I use an arithmetic progression, the number of nonzero terms considering only exponents collisions (case 1) is $mk – (m-1)$. So for a fixed $k$, this is really not bad, but is it possible to prove that the number of collisions is optimal (maximum)?
Best Answer
Let $K(f)$ denote the number of nonzero terms of the polynomial $f$. Let $\epsilon>0$. It is known that there are polynomials $f$ with integer coefficients (and hence over finite fields of sufficiently large characteristic) such that $K(f^2)<\epsilon K(f)$. See pp. 261--263 of M. Kreuzer and L. Robbiano, Computational Commutative Algebra 1.
In particular, if $K(f^2)<K(f)$ then $\deg f\geq 12$. An example of such a polynomial of degree 12 is $$ 13750x^{12}+5500x^{11}-1100x^{10}+440x^9-220x^8+220x^7$$ $$ \qquad -15x^6-50x^5 +10x^4-4x^3+2x^2-2x-1. $$