14
$\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)?

Improve this question
$\endgroup$
5
  • 2
    $\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
    Commented Jul 18, 2015 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
    Commented Jul 18, 2015 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
    Commented Jul 18, 2015 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
    Commented Jul 18, 2015 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
    Commented Jul 18, 2015 at 19:06

2 Answers 2

Reset to default
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. $$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .