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

Solution 1:

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.