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)?



Number of nonzero terms in polynomial expansion (lower bounds)
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. $$


