Repeated Roots of Polynomials Whose Coefficients are Either 0 or 1

Question

Consider a polynomial of the form: $$f\left(z\right)=1+z^{p_{0}}+z^{p_{1}}+\ldots+z^{p_{N}}$$ where the $p_{n}$s are distinct positive integers. Are the roots of $f$ (in $\mathbb{C}$) necessarily simple (i.e., must they all have multiplicities of $1$)?

Answer 1

No. We can construct as follows: The polynomial $(1+z^a)(1+z^b)$ will have two factors of $1+z$ if $a$ and $b$ are both odd. So if we choose $b$ a good bit bigger than $a$, the cross terms will miss each other and all coefficients will be $1$. For instance,

$$f(z) = (1+z^3)(1+z^5) = 1+z^3+z^5+z^8$$

has $-1$ as a double root.

Answer 2

.I know there's been an answer accepted, but nevertheless since somebody in the comments has asked how this would help, I would like to see if it can fuel a discussion.

So we know that a root of a polynomial is simple if it's not a root of the derivative of that polynomial.

Let $f(z) = 1 + z^{a_0} + ... + z^{a_n}$, where $a_i$ are positive integers, without loss of generality $a_n$ being the largest.

Now, the derivative of $f(z)$ is $a_0z^{a_0 - 1} + a_1z^{a_1-1} + ... + a_{n}z^{a_n - 1}$, as we know it.

We note carefully that $f(-1) = 1 + (-1)^{a_0} + (-1)^{a_1} + ... + (-1)^{a_n}$. This is zero precisely when the number of odd $a_i$ exceeds the number of even $a_i$ by precisely one.

Similarly, $f'(-1) = a_0(-1)^{a_0-1} + a_1(-1)^{a_1-1} + ... + a_n(-1)^{a_n}$. This is zero precisely when this sum is zero, and in that case, we can conclude that $-1$ is a repeated root of $f$.

Observing the sum $f'(-1)$, we note that all odd $a_i$ are being added, while all even $a_i$ are being subtracted. Hence, $f'(-1) = 0$ is the same as saying the sum of all the odd $a_i$ is the same as the sum of all the even $a_i$.

Hence, we want just the following to happen : some number of even $a_i$, just one more number of odd $a_i$, and the sums of these must be the same.

Indeed, in the example given in the other answer, $a_1 = 3,a_2 = 5,a_3 = 8$. We see that the number of odd $a_i$ exceeds the number of even $a_i$ by $1$, and the sum of even and odd $a_i$ are actually equal.

Note that if this condition has to happen, then the number of odd $a_i$ has to be even and the number of even $a_i$ has to be odd (can you see why?)

Finally, we summarize this in a lemma:

Let $n$ be an even number, $\{a_1,...,a_n\}$ be a set of distinct odd numbers , and $\{b_1,...,b_{n-1}\}$ a set of distinct even numbers such that $\sum a_i = \sum b_j$. Then, the polynomial $1 + \sum z^{a_i} + \sum z^{b_j}$ has a repeated root $-1$.

To give a slightly more involved example that the one in the other answer, consider $\{1,3,5,7\}$ and $\{2,4,10\}$. Then, I claim the polynomial $1 + z + z^2 + z^3 + z^4 + z^5 + z^7+ z^{10}$ has the factor $(1+z)^2$. You can check it satisfies all given conditions of the lemma, and indeed: $$ 1 + z + z^2+z^2+z^4+z^5+z^7+z^{10} = (1+z)^2(1+z^2)(1-z+z^2)(1-z^3+z^4) $$

You can use this method to generate all the counter examples you like. If you want a family of counterexamples, you could just do the following : consider $\{3m+1,3m+3,3m+5,3m+7\}$ as a set of odd numbers, and $\{4m+2,4m+4,4m+10\}$ as a set of even numbers for $m$ even, and this again will satisfy all the conditions of the lemma.For example, with $m=2$ you would get the sets $\{7,9,11,13\}$ and $\{10,12,18\}$, which again satisfy the propery.