3
$\begingroup$

Let $f\in \mathbb{Z}[x_1,\dots,x_n]$ be a polynomial. I want to show that a certain monomial $m$ shows up with non-zero coefficient in the $r^{th}$ power of $f$.

If you're lucky, you can do this as follows:

Regrade $\mathbb{Z}[x_1,\dots,x_n]$ such that $m$ appears with non-zero coefficient in the initial form $(\textrm{init}f)^r$. Then because $m$ has highest weight, no trailing terms of $f^{r}$ can cancel $m$. This means you can take a hard calculation with a long, complicated polynomial and turn it into an easy calculation with a short polynomial.

Sadly, $m$ may be interior in the Newton polytope of $f^r$, in which case the above trick has no hope of working.

I would be grateful for other techniques people use for showing that monomials show up with non-zero coefficent in powers (and products) of polynomials.

Thanks!

(In fact, I really care about the situation $f\in \mathbb{F}_p[x_1,\dots,x_n]$ and $r = p-1$ for some prime $p$.)

1 Answers 1

1

The coefficient of $\prod_{i=1}^nx^{k_i}$ in $f$ is the same thing as $(\partial_{(\bar{k})} f)|_{\bar{x}=\bar{0}}$, where $\partial_{(\bar{k})}=\prod_{i=1}^n\frac{\partial_{x_i}^{k_i}}{k_i!}$. You can take advantage of this to simplify calculations. As a small example, consider $$\begin{align}f(x,y,z) &= 1+x +y -2xy + 3xz^2 & m&=x^2y^2z^2\end{align}$$ with $r = 5$.

$$\begin{align} (\partial_{(2,2,2)} f^5)|_{(x,y,z)=\bar{0}} & =\frac{1}{8}(\partial_{x}^2\partial_{y}^2\partial_{z}^2 f^5)|_{(x,y,z)=\bar{0}}\\ & =\frac{1}{8}(\partial_{x}^2\partial_{y}^2\partial_{z} 5f^4f_z)|_{(x,y,z)=\bar{0}}\\ & =\frac{1}{8}\partial_{x}^2\partial_{y}^2 (20f^3f_z^2+5f^4f_{zz})|_{(x,y,z)=\bar{0}}\\ \end{align} $$ Now that we will never again differentiate by $z$, it is acceptable to evaluate at $z=0$. Let $g(x,y)=f(x,y,0)=1+x+y-2xy$. Note that $f_z(x,y,0)=0$ and $f_{zz}(x,y,0)=6x$, simplifying what we have so far. We are left with: $$\begin{align} (\partial_{(2,2,2)} f^5)|_{(x,y,z)=\bar{0}} & =\frac{1}{8}\partial_{x}^2\partial_{y}^2 (30xg^4)|_{(x,y)=\bar{0}}\\ & =\frac{1}{8}\partial_{x}^2\partial_{y} (120xg^3g_y)|_{(x,y)=\bar{0}}\\ & =\frac{1}{8}\partial_{x}^2(360xg^2g_y^2+120xg^3g_{yy})|_{(x,y)=\bar{0}}\\ & =\frac{1}{8}\partial_{x}^2(360xg^2g_y^2)|_{(x,y)=\bar{0}}\\ \end{align} $$

where we used the fact that $g_{yy}=0$. As we will never again differentiate with respect to $y$... let $h(x)=g(x,0)=1+x$. $$\begin{align} (\partial_{(2,2,2)} f^5)|_{(x,y,z)=\bar{0}} & =\frac{1}{8}\partial_{x}^2(360xh^2(1-2x)^2)|_{(x)=\bar{0}}\\ & =\frac{1}{8}\partial_{x}^2(360x(1+x)^2(1-2x)^2)|_{(x)=\bar{0}}\\ & =\frac{1}{8}\partial_{x}^2(360x(1+2x+x^2)(1-4x+4x^2))|_{(x)=\bar{0}}\\ & =\frac{1}{8}\partial_{x}^2(360x(1+2x)(1-4x))|_{(x)=\bar{0}}\\ & =\frac{1}{8}\partial_{x}^2(360x(1-2x-8x^2))|_{(x)=\bar{0}}\\ & =\frac{1}{8}\partial_{x}^2(-720x^2)|_{(x)=\bar{0}}\\ & = \frac{1}{8}(-720)(2)\\ & = -180 \end{align} $$ where in this final block we have stayed conscious of the degree to which we are differentiating and that we will evaluate at $0$ .

I think this strategy (using derivatives and evaluating at $0$) will generally be more efficient than directly computing $f^r$. This should also be applicable to products of polynomials.

  • 0
    If you work modulo $p$, you need to do all of the modular reductions _after_ you have divided by the factorials.2012-06-17
  • 0
    Yup. I'll just work over $\mathbb{Z}$. This is a great idea! Thanks!2012-06-17
  • 0
    Incidentally, do you know if this is how computer algebra programs do this sort of thing? In general, polynomial multiplication is pretty slow. But getting bounds on degrees should be quick, and your idea of differentiating should be reasonably quick..at least this is what my (probably poor) intuition tells me..2012-06-17
  • 0
    Hmm.. I searched around a bit and apparently people use Fast Fourier Transforms. I don't know anything about these, but figured I may as well include it in a comment here for the sake of completion.2012-06-17
  • 0
    @jrajchgot No I don't know if this is how a computer would do this with large $r$. I have used this approach before though.2012-06-17
  • 0
    Ok. I was just curious. In any case, thanks again for a very helpful answer!2012-06-17