# Simply formulated but very hard problem about certain polynomial

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$?

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.

• @ 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? – user64494 Sep 6 '13 at 17:12
• 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. – Luca Bressan Sep 6 '13 at 17:18
• 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$. – Daniel Fischer Sep 6 '13 at 19:36