12
$\begingroup$

Let $L:=[k_1,\dots,k_n]$ be a list of natural numbers (i.e. $\{1,2,\dots \} $) , repetitions are allowed. How to prove that the sum of the moduli of the coefficients of the polynomial $$ \prod_{j=1}^{j=n}\left(1-x^{k_j}\right)$$ is greater than or equal to $2n$?

$\endgroup$
1
$\begingroup$

As pointed out by Daniel Fischer in the comments, the bound of $2n$ is sharp, so my previous attempt at solving the problem by factoring the polynomial and considering the absolute sum for $(x-1)^n$ doesn't seem to go in the right direction. Since then I've tried to look at the problem in a different way, so I'm going to report here my observations (I don't know if I should write this in a different answer; I'll keep the first one at the end of this).

I noticed that the polynomial $f(x) = \prod_{j=1}^n (1-x^{k_j})$ can be expanded in the following way. Let $L$ be the set of the indices $k_j$, counted with repetitions, as in $$L = \{ (j, k_j) \mid j = 1, \dotsc, n \}.$$ For each $i$ let $C_i = \{ S \subseteq L \mid \lvert S \rvert = i \}$, and for each $c \in C_i$ denote by $t(c)$ the sum of the indices $k_j$ in $c$. Then, $$ f(x) = \sum_{i=0}^n (-1)^i \sum_{c \in C_i} x^{t(c)}. $$ For example, for $n = 3$, we have that $$ (1-x^a)(1-x^b)(1-x^c) = 1-(x^a+x^b+x^c)+(x^{a+b}+x^{a+c}+x^{b+c})-x^{a+b+c}. $$ In this case it is relatively easy to prove that the absolute value is greater than or equal to $6$, by reasoning on how we can cancel some terms (for example, even if $a = b+c$, we can't have less than six terms, otherwise we find a contradiction). Nonetheless the general case seems hard to deal with.

Previous attempt

First recall that, for all $m > 0$, $$ 1-x^m = (1-x)(1+x+\dotsb+x^{m-1}).$$ Then you can factor your polynomial $f(x)$ as $$ f(x) = \prod_{j=1}^n (1-x^{k_j}) = \prod_{j=1}^n [(1-x)(1+x+\dotsb+x^{k_j-1})] = (1-x)^n g(x)$$ for some polynomial $g(x)$ whose coefficients are all positive. Now, since $$ (1-x)^n = \sum_{i=0}^n \binom{n}{i} (-x)^i,$$ the sum of the absolute values of the coefficients of $(1-x)^n$ is $$ \sum_{i=0}^n \binom{n}{i} = 2^n .$$ From this you should get that the sum of the absolute values of the coefficients of $f(x)$ is at least $2^n$.

If you're not convinced, notice that if $p(x) = a_0 + a_1 x + \dotsb + a_m x^m$ and $q(x) = b_0 + b_1 x + \dotsb + b_n x^n$, with $a_i,\, b_j$ integers, then $$ p(x) q(x) = \sum_{d=0}^{m+n} \left ( \sum a_i b_j \right) x^d$$ where the second sum runs for all $(i, j)$ such that $i \le m$, $j \le n$, $i+j = d$. From this it's easy to see that the value you want to calculate never decreases when you multiply a polynomial by another one with positive coefficients.

Edit: This may not be as trivial as I thought, as my last argument was too rushed and now it seems to me that it could even be false. I leave the answer as a possible direction to follow until I can fix it.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ @ Luca Bressan: Thank you for the interest to the question. I find your idea interesting. You wrote:"From this it's easy to see that the value you want to calculate never decreases when you multiply a polynomial by another one with positive coefficients". Could you explain that place in detail? $\endgroup$ – user64494 Sep 6 '13 at 17:12
  • $\begingroup$ Actually, I think I haven't thought it through enough. If some of the $a_i$'s are negative it seems that bad things could happen. I'll edit the answer and leave it as an idea until I figure out how to fix it. $\endgroup$ – Luca Bressan Sep 6 '13 at 17:18
  • $\begingroup$ You have an upper bound of $2^n$ for the sum of coefficients, since that's the sum of coefficients of $\prod (1 + x^{k_j})$. You get smaller (absolute) sums for $\prod(1-x^{k_j})$, e.g. $(1-x)(1-x^2)(1-x^3) = 1 - x - x^2 + x^4+x^5 -x^6$ has an absolute sum of $6 = 2\cdot 3$, so $2n$ would be sharp. The idea of writing $1-x^m = (1-x)(1+x+\dotsc + x^{m-1})$ looks good, though. You get a factor with positive coefficients which sum to $\prod k_j$, and the coefficient of $x^1$ is the number of $k_j$ which are greater than $1$. $\endgroup$ – Daniel Fischer Sep 6 '13 at 19:36

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.