13
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ This is vaguely reminiscent of Frieman's theorem en.wikipedia.org/wiki/Freiman%27s_theorem . If there is no cancellation in expanding your power, then Frieman tells you that taking your terms in an arithmetic progression is roughly optimal. I hope that someone comes along with a better answer soon. $\endgroup$ – David E Speyer Jul 18 '15 at 2:07
  • $\begingroup$ @DavidSpeyer I was not familiar with this theorem, this means that I may generalize the number of terms (considering case 1 only) as $mk - (m-1)$, correct? Also, could you elaborate on the "roughly optimal"? $\endgroup$ – Lucas Perin Jul 18 '15 at 5:16
  • $\begingroup$ A trivial observation concerning case 2: If $q=p^e$ for a prime $p$ and $m=p^l$ ($l \geq 0$), then $f(x)^m$ will have the same number of nonzero terms as $f(x)$, since $(x+y)^p = x^p+y^p$ in characteristic $p$. So unless you exclude $m=p^l$, you can't hope for a lower bound greater than $k$. $\endgroup$ – Gabriel Dill Jul 18 '15 at 14:33
  • $\begingroup$ Yes, this is a good observation. I suppose I should mention now that $q=p$ and $1 \le m \le p-1$. So the freshman's dream does not help me. Also, I'll need to consider that some polynomial $P(x) = f(x) + a_0$ where $P$ is irreducible over $\mathbb{F}_q$. But this would make my question too extensive and hard, so I'll leave it as a comment for now. $\endgroup$ – Lucas Perin Jul 18 '15 at 15:56
  • 1
    $\begingroup$ Arithmetic progressions give indeed the lowest possible number of terms if one considers only case 1: Assume $z_1 < z_2 < \dots < z_k$. Then the $m(k-1)$ numbers $z_{i,j} = iz_{j+1}+(m-i)z_j$ ($i=0,\dots,m-1$, $j=1,\dots,k-1$) are all different from each other and from $z_{0,k}=mz_k$, since $z_{i,j} < z_{i+1,j}$ and $z_{m-1,j} < z_{0,j+1}$ for all $i$ and $j$. $\endgroup$ – Gabriel Dill Jul 18 '15 at 19:06
12
$\begingroup$

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. $$

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.