4

Now I have a polynomial like this $$f(x)=\prod\limits_{i=1}^{n}\left(1+x^{a_i}\right)$$ where $a_i\in\mathbb{N}\,(i=1,2,\cdots,n)$. Let its expanded form be $$f(x)=c_0+c_1x^1+c_2x^2+\cdots+c_tx^t\quad\left(t=\sum\limits_{i=1}^n a_i\right)$$ I want to know the coefficient $c_s$ of a specific term $x^s\,(s\in\mathbb{N})$ in the expanded form of $f(x)$, without really expanding the formula, since the expanded formula would have up to $2^n$ terms, which is too large. I have considered the following approaches:

  1. If we can find the $s$-order derivative of $f(x)$ at $x=0$, then the coefficient of $x^s$ would be $c_s=\frac{f^{(s)}(0)}{s!}$, but this approach seems not practical;
  2. It is relatively easier to calculate the value of $f$ at some specific points, and we may use some interpolation methods to evaluate the coefficient $c_s$; but as far as I know, the methods like Lagrange interpolation and Newton's interpolation are not able to "only" evaluate $c_s$ without performing too much other calculations.

So is there a fast way to calculate $c_s$?

Note:

  1. $a_i$ and $s$ might be very large, so it's not feasible to adopt a method which requires to calculate $c_0,\,c_1,\,\cdots,\,c_s$.
  2. There isn't a specific definition of "fast" here, but I'm generally looking for an approach more "clever" than simply expanding the formula. It would be the best if we can calculate $c_s$ by pen and paper when $n$ and each $a_i$ are as large as $1000$, but if there doesn't exist any approach that fast, any approach that is faster than expanding the formula would be accepted.
  3. It is trivial that when $s=0$, $c_s=2^k$, where $k$ is the number of $a_i$ equal to zero; when $s>t$, we know that $c_s=0$. So we only need to consider the case that $0<s\le t$.
Soha
  • 185
  • 2
    Another way to isolate a specific coefficient is through contour integration (the Cauchy integral formula that calculates derivatives). – Greg Martin Dec 28 '22 at 03:40
  • 3
    Well you have the formula $c_s = #\left\lbrace J \subset \lbrace 1, \ldots, n \rbrace, \sum_{j \in J} a_j = s\right\rbrace$. But without more specifications, it's hard to tell what's a "fast" way to calculate $c_s$. – Zag Dec 28 '22 at 09:36

1 Answers1

3

As Zag's comment mentions, we have $$c_s = \#\left\lbrace J \subset \lbrace 1, \ldots, n \rbrace, \sum_{j \in J} a_j = s\right\rbrace.$$

Note that determining whether $c_s$ is nonzero is precisely the subset sum problem, which is known to be NP-complete.

For practical pen-and-paper computations, I would probably use dynamic programming (e.g. see answers to this question); more sophisticated methods could be adapted from the vast literature on the closely related knapsack problem.

For impractical purposes, you can evaluate at roots of unity to isolate a particular coefficient:

For any $m > t$ and $\zeta = e^{2\pi i/m}$, $$c_s = \frac{1}{m}\sum_{k=0}^{m-1}\frac{f(\zeta^k)}{(\zeta^k)^s}.$$ (For proof, note that $c_s$ is the constant coefficient of $f(x)/x^s$. Summing over all the $m$th roots of unity will leave only the terms with exponent divisible by $m$, so for $m$ large enough we get the desired coefficient.)

This is a discrete version of the Cauchy integral formula mentioned in Greg Martin's comment.

There's also the number-theoretic version: $$c_s \equiv -\sum_{k=1}^{p-1}\frac{f(k)}{k^s} \pmod{p}$$ for any prime $p > t$.

Benjamin Wright
  • 1,611