# Repeated Roots of Polynomials Whose Coefficients are Either 0 or 1

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

• Compare this function with it's derivative. That's a good start. You know a root is simple if it's not shared between the function and it's derivative. – астон вілла олоф мэллбэрг Sep 19 '17 at 23:07
• Obviously. But I am working with polynomials where the exponents are undetermined quantities. I cannot simply compare it that way. I was just wondering if there is some general result which bars polynomials of this form from having repeated roots. – MCS Sep 19 '17 at 23:20
• @астонвіллаолофмэллбэрг How can this fact be used? – miracle173 Sep 20 '17 at 6:05
• @miracle173 I've explained the usage of this fact in an answer below. – астон вілла олоф мэллбэрг Sep 20 '17 at 6:36
• Of course the polynomial $z^2$ is the smallest example! Ah, upon reading more carefully, I see you require the zeroth-order coefficient to be $1$. – Jeppe Stig Nielsen Sep 20 '17 at 7:56

.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.

• Beautifully presented. – Prune Sep 20 '17 at 15:19

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.

• As soon as $b>a>0$, the expansion of $(1+z^a)(1+z^b)$ will have the correct form $1+z^a+z^b+z^{a+b}$. The smallest choice for odd exponents is $a=1,b=3$ which gives $1+z+z^3+z^4$. – Jeppe Stig Nielsen Sep 20 '17 at 7:59
• I think you can do the same for other repeated roots than $-1$. For example pick a square root of $-1$ (such as $i$), then $(1+z^2)(1+z^6)$ has that number as a non-simple root. Similarly for any $n$th root of $-1$, we can find a polynomial of the desired form that has that number as a repeated root, namely $(1+z^n)(1+z^{3n})$. – Jeppe Stig Nielsen Sep 20 '17 at 15:33