Number of nonzero terms in polynomial expansion (lower bounds) 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)?
 A: Existence of a lower bound that goes to infinity used to be a long-standing problem of Rényi and Erdős. It was finally resolved by Schinzel with a bound of about $\log \log k$. The bound was later improved by Schinzel and Zannier to about $\log k$. Also, Zannier proved a lower bound on the number of terms of $g(f(x))$ for any $g$.
Given an example with $K(f^2)=A$ and $K(f)=B$, one can obtain a polynomial $g$ with $K(g^2)=A^2$ and $K(g)=B^2$. Indeed, consider $g(x)=f(x)f(x^{BIG})$ So, in view of the example posted by Richard Stanley in another answer, it follows that there is an $\varepsilon>0$ and infinitely many polynomials $f$ such that $K(f^2)\leq K(f)^{1-\varepsilon}$.
The question of whether the correct bound is logarithmic or polynomial in $k$ (or is in between) is open.
A: 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. $$
