2

Given a univariate polynomial of degree $k$ raised to power $m$ with non-zero constant term $c_0$ and exponents $e_i \ge 1$ present (but not necessarily $k$ of them) it appears to me that $c_n/c_0^n$ (the coefficient of $x^n$ divided by the constant term of the polynomial raised to the power $m$) will be a polynomial of degree $s$ where $s$ is the largest number of elements needed to partition $n$ using values of $e_i$.

For example, consider $P(x) = 2 + x^2 + x^7 + x^{13}$. Here, $k = 13$ and $e_i = {2, 7, 13}$. The coefficient of $x^{51}$ in $P(x)^m$ depends on the value of $m$ until $m>22$, after which the coefficient is given by a polynomial of degree 23. When we look at ways to partition 51 using $e_i$ we find there are 10 different ways: the smallest number of elements needed is 7 (2x2s + 3x7s + 2x13s) while the largest number of elements needed is $s = 23$ (22 x 2s and 1 x 7).

Multinomial coefficients can be used to find the value of $c_{51}$ for a given $m$, but I don't see how a polynomial of degree $s$ can be used for any value of $m \ge s$.

Does this observation seem correct? Is there a simple explanation for the relationship between $s$ and the degree of the polynomial describing the coefficient of $x^n$ in $P(x)^m$ for $m \ge s$?

smichr
  • 359

1 Answers1

0

An answer to this question is given here where the method of creating a generating function for the coefficient of $x^r$ in $p(x)^n$ for arbitrary coefficients is given. The method applies to an all-ones polynomial, too, as described in this question.

In general, if $p(x)$ contains exponents $\in [0, k]$, then when it is raised to the $m$th power, there will be terms of order $n \in [0, mk]$ and the coefficient of $x^n$ will be $p(0)^m \cdot a_n(m)$ where $a_n(m)$ is an $nth$ order polynomial in $m$ if the term is present, else 0: $a_0$ is 1, $a_1(m)$ is linear in $m$, $a_2(m)$ is quadratic in $m$, etc... The exact form of $a_r(m)$ depends on the terms present in $p(x)$. Consider the simple $(2+x)^m$: the first 4 terms in terms of $m$ are $\frac{2^m m (m - 2) (m - 1)}{48}\mathbf{x^3} + \frac{2^m m (m - 1)}{8}\mathbf{x^2} + \frac{2^m m}{2}\mathbf{x} + 2^m$.

So two methods of finding the coefficient of $x^n$ in $p(x)^m$ is to are to either 1) find partitions of $n$ that match the desired level of exponentiation and use those to sum up the multinomial coefficients, or to calculate the coefficients of $x^n$ in the $p(x)^m$ for $m \in [0,n]$ and use those values to construct the corresponding polynomial, $a_r(m)$. The advantage to the latter approach is that once $a_r(m)$ is constructed, it is valid for any value of $m$

smichr
  • 359