Skip to main content
added tag
Link
Wolfgang
  • 13.3k
  • 5
  • 45
  • 101
I fixed a typo in one equation, and made the title a bit more succinct.
Source Link
Louis Deaett
  • 1.5k
  • 1
  • 13
  • 24

When does a set Which sets of roots of unity give a polynomial with nonnegative coefficients?

The question in brief:   When does a subset $S$ of the complex $n$th roots of unity have the property that $$\prod_{\alpha\, \in \,S} (z-\alpha)$$ gives a polynomial in $\mathbb R[z]$ with nonnegative coefficients?

Some trivial necessary conditions include $1\not\in S$ and also that $S$ is self-conjugate so that the coefficients will at least be real.

A sufficient condition that is not obvious (to me) is that the roots of unity in $S$ are precisely those lying outside of some wedge-shaped region of the complex plane, i.e., those with $\left|\arg(z)\right| > t$ for some fixed $t > 0$. This follows from the main theorem of

Barnard, R. W., W. Dayawansa, K. Pearce, and D. Weinberg. "Polynomials with nonnegative coefficients." Proceedings of the American Mathematical Society 113, no. 1 (1991): 77-85. Journal link

which says that, given any polynomial with nonnegative coefficients, dividing it by the linear factors corresponding to exactly those of its roots lying in such a region produces a polynomial with only positive coefficients. Applying this to $z^{n-1}+\cdots+z+1$ gives the desired result.

But that theorem is not number-theoretic; it doesn't care at all that we are dealing with roots of unity. So maybe there is a nicer proof in this special case?

More generally, what other necessary and/or sufficient conditions exist? Is there some reasonable number-theoretic or combinatorial characterization of such sets? What tools seem likely to shed some light on this question?

ADDED LATER: A couple of very interesting suggestions have been made in the comments so far, and I'm eager to see where they lead. However, I remain quite curious as to what can be said from a number-theoretic perspective. For example, if $n=p^r$$n=p^r > 1$ for some prime $p$, then the cyclotomic polynomial $\Phi_n(x)=\Phi_p(x^{r-1})$$\Phi_n(x)=\Phi_p(x^{n/p})$ has only nonnegative coefficients. So a sufficient condition that I did not mention above is that $S$ is the set of primitive $n$th roots of unity for some prime power $n$. I believe this is the only way to obtain such a polynomial that is a cyclotomic polynomial, but that doesn't imply that nothing else can be gained from a number-theoretic perspective on this question – however I myself lack the expertise necessary to make the most of such a perspective.

I should also mention that (ironically, given my desire for a number-theoretic perspective on this) the cyclotomic result actually follows from a more general, not number-theoretic result of

Evans, Ronald, and John Greene. "Polynomials with nonnegative coefficients whose zeros have modulus one." SIAM Journal on Mathematical Analysis 22, no. 4 (1991): 1173-1182. Author's link

a special case of which gives that for any proper divisor $d$ of $n$, $(x^n-1)/(x^d-1)$ has only nonnegative coefficients. So thisthat generalizes the cyclotomic resultcase, but not via number theory.!

When does a set of roots of unity give a polynomial with nonnegative coefficients?

The question in brief:   When does a subset $S$ of the complex $n$th roots of unity have the property that $$\prod_{\alpha\, \in \,S} (z-\alpha)$$ gives a polynomial in $\mathbb R[z]$ with nonnegative coefficients?

Some trivial necessary conditions include $1\not\in S$ and also that $S$ is self-conjugate so that the coefficients will at least be real.

A sufficient condition that is not obvious (to me) is that the roots of unity in $S$ are precisely those lying outside of some wedge-shaped region of the complex plane, i.e., those with $\left|\arg(z)\right| > t$ for some fixed $t > 0$. This follows from the main theorem of

Barnard, R. W., W. Dayawansa, K. Pearce, and D. Weinberg. "Polynomials with nonnegative coefficients." Proceedings of the American Mathematical Society 113, no. 1 (1991): 77-85. Journal link

which says that, given any polynomial with nonnegative coefficients, dividing it by the linear factors corresponding to exactly those of its roots lying in such a region produces a polynomial with only positive coefficients. Applying this to $z^{n-1}+\cdots+z+1$ gives the desired result.

But that theorem is not number-theoretic; it doesn't care at all that we are dealing with roots of unity. So maybe there is a nicer proof in this special case?

More generally, what other necessary and/or sufficient conditions exist? Is there some reasonable number-theoretic or combinatorial characterization of such sets? What tools seem likely to shed some light on this question?

ADDED LATER: A couple of very interesting suggestions have been made in the comments so far, and I'm eager to see where they lead. However, I remain quite curious as to what can be said from a number-theoretic perspective. For example, if $n=p^r$ for some prime $p$, then the cyclotomic polynomial $\Phi_n(x)=\Phi_p(x^{r-1})$ has only nonnegative coefficients. So a sufficient condition that I did not mention above is that $S$ is the set of primitive $n$th roots of unity for some prime power $n$. I believe this is the only way to obtain such a polynomial that is a cyclotomic polynomial, but that doesn't imply that nothing else can be gained from a number-theoretic perspective on this question – however I myself lack the expertise necessary to make the most of such a perspective.

I should also mention that (ironically, given my desire for a number-theoretic perspective on this) the cyclotomic result actually follows from a more general, not number-theoretic result of

Evans, Ronald, and John Greene. "Polynomials with nonnegative coefficients whose zeros have modulus one." SIAM Journal on Mathematical Analysis 22, no. 4 (1991): 1173-1182. Author's link

a special case of which gives that for any proper divisor $d$ of $n$, $(x^n-1)/(x^d-1)$ has only nonnegative coefficients. So this generalizes the cyclotomic result, but not via number theory.

Which sets of roots of unity give a polynomial with nonnegative coefficients?

The question in brief:   When does a subset $S$ of the complex $n$th roots of unity have the property that $$\prod_{\alpha\, \in \,S} (z-\alpha)$$ gives a polynomial in $\mathbb R[z]$ with nonnegative coefficients?

Some trivial necessary conditions include $1\not\in S$ and also that $S$ is self-conjugate so that the coefficients will at least be real.

A sufficient condition that is not obvious (to me) is that the roots of unity in $S$ are precisely those lying outside of some wedge-shaped region of the complex plane, i.e., those with $\left|\arg(z)\right| > t$ for some fixed $t > 0$. This follows from the main theorem of

Barnard, R. W., W. Dayawansa, K. Pearce, and D. Weinberg. "Polynomials with nonnegative coefficients." Proceedings of the American Mathematical Society 113, no. 1 (1991): 77-85. Journal link

which says that, given any polynomial with nonnegative coefficients, dividing it by the linear factors corresponding to exactly those of its roots lying in such a region produces a polynomial with only positive coefficients. Applying this to $z^{n-1}+\cdots+z+1$ gives the desired result.

But that theorem is not number-theoretic; it doesn't care at all that we are dealing with roots of unity. So maybe there is a nicer proof in this special case?

More generally, what other necessary and/or sufficient conditions exist? Is there some reasonable number-theoretic or combinatorial characterization of such sets? What tools seem likely to shed some light on this question?

ADDED LATER: A couple of very interesting suggestions have been made in the comments so far, and I'm eager to see where they lead. However, I remain quite curious as to what can be said from a number-theoretic perspective. For example, if $n=p^r > 1$ for some prime $p$, then the cyclotomic polynomial $\Phi_n(x)=\Phi_p(x^{n/p})$ has only nonnegative coefficients. So a sufficient condition that I did not mention above is that $S$ is the set of primitive $n$th roots of unity for some prime power $n$. I believe this is the only way to obtain such a polynomial that is a cyclotomic polynomial, but that doesn't imply that nothing else can be gained from a number-theoretic perspective on this question – however I myself lack the expertise necessary to make the most of such a perspective.

I should also mention that (ironically, given my desire for a number-theoretic perspective on this) the cyclotomic result actually follows from a more general, not number-theoretic result of

Evans, Ronald, and John Greene. "Polynomials with nonnegative coefficients whose zeros have modulus one." SIAM Journal on Mathematical Analysis 22, no. 4 (1991): 1173-1182. Author's link

which gives that for any proper divisor $d$ of $n$, $(x^n-1)/(x^d-1)$ has only nonnegative coefficients. So that generalizes the cyclotomic case, but not via number theory!

I changed the format of the citation and also added some additional info regarding the cyclotomic case.
Source Link
Louis Deaett
  • 1.5k
  • 1
  • 13
  • 24

The question in brief:   When does a subset $S$ of the complex $n$th roots of unity have the property that $$\prod_{\alpha\, \in \,S} (z-\alpha)$$ gives a polynomial in $\mathbb R[z]$ with nonnegative coefficients?

Some trivial necessary conditions include $1\not\in S$ and also that $S$ is self-conjugate so that the coefficients will at least be real.

A sufficient condition that is not obvious (to me) is that the roots of unity in $S$ are precisely those lying outside of some wedge-shaped region of the complex plane, i.e., those with $\left|\arg(z)\right| > t$ for some fixed $t > 0$. This follows from a result proved here: Giventhe main theorem of

Barnard, R. W., W. Dayawansa, K. Pearce, and D. Weinberg. "Polynomials with nonnegative coefficients." Proceedings of the American Mathematical Society 113, no. 1 (1991): 77-85. Journal link

which says that, given any polynomial with nonnegative coefficients, dividing it by the linear factors corresponding to exactly those of its roots lying in such a region produces a polynomial with only positive coefficients. Applying this to $z^{n-1}+\cdots+z+1$ gives the desired result.

But that theorem is not number-theoretic; it doesn't care at all that we are dealing with roots of unity. So maybe there is a nicer proof in this special case?

More generally, what other necessary and/or sufficient conditions exist? Is there some reasonable number-theoretic or combinatorial characterization of such sets? What tools seem likely to shed some light on this question?

ADDED LATER: A couple of very interesting suggestions have been made in the comments so far, and I'm eager to see where they lead. However, I remain quite curious as to what can be said from a number-theoretic perspective. For example, if $n=p^r$ for some prime $p$, then the cyclotomic polynomial $\Phi_n(x)=\Phi_p(x^{r-1})$ has only nonnegative coefficients. So a sufficient condition that I did not mention above is that $S$ is the set of primitive $n$th roots of unity for some prime power $n$. I believe this is the only way to obtain such a polynomial that is a cyclotomic polynomial, but that doesn't imply that nothing else can be gained from a number-theoretic perspective on this question – however I myself lack the expertise necessary to make the most of such a perspective.

I should also mention that (ironically, given my desire for a number-theoretic perspective on this) the cyclotomic result actually follows from a more general, not number-theoretic result of

Evans, Ronald, and John Greene. "Polynomials with nonnegative coefficients whose zeros have modulus one." SIAM Journal on Mathematical Analysis 22, no. 4 (1991): 1173-1182. Author's link

a special case of which gives that for any proper divisor $d$ of $n$, $(x^n-1)/(x^d-1)$ has only nonnegative coefficients. So this generalizes the cyclotomic result, but not via number theory.

The question in brief:   When does a subset $S$ of the complex $n$th roots of unity have the property that $$\prod_{\alpha\, \in \,S} (z-\alpha)$$ gives a polynomial in $\mathbb R[z]$ with nonnegative coefficients?

Some trivial necessary conditions include $1\not\in S$ and also that $S$ is self-conjugate so that the coefficients will at least be real.

A sufficient condition that is not obvious (to me) is that the roots of unity in $S$ are precisely those lying outside of some wedge-shaped region of the complex plane, i.e., those with $\left|\arg(z)\right| > t$ for some fixed $t > 0$. This follows from a result proved here: Given any polynomial with nonnegative coefficients, dividing it by the linear factors corresponding to exactly those of its roots lying in such a region produces a polynomial with only positive coefficients. Applying this to $z^{n-1}+\cdots+z+1$ gives the desired result.

But that theorem is not number-theoretic; it doesn't care at all that we are dealing with roots of unity. So maybe there is a nicer proof in this special case?

More generally, what other necessary and/or sufficient conditions exist? Is there some reasonable number-theoretic or combinatorial characterization of such sets? What tools seem likely to shed some light on this question?

The question in brief:   When does a subset $S$ of the complex $n$th roots of unity have the property that $$\prod_{\alpha\, \in \,S} (z-\alpha)$$ gives a polynomial in $\mathbb R[z]$ with nonnegative coefficients?

Some trivial necessary conditions include $1\not\in S$ and also that $S$ is self-conjugate so that the coefficients will at least be real.

A sufficient condition that is not obvious (to me) is that the roots of unity in $S$ are precisely those lying outside of some wedge-shaped region of the complex plane, i.e., those with $\left|\arg(z)\right| > t$ for some fixed $t > 0$. This follows from the main theorem of

Barnard, R. W., W. Dayawansa, K. Pearce, and D. Weinberg. "Polynomials with nonnegative coefficients." Proceedings of the American Mathematical Society 113, no. 1 (1991): 77-85. Journal link

which says that, given any polynomial with nonnegative coefficients, dividing it by the linear factors corresponding to exactly those of its roots lying in such a region produces a polynomial with only positive coefficients. Applying this to $z^{n-1}+\cdots+z+1$ gives the desired result.

But that theorem is not number-theoretic; it doesn't care at all that we are dealing with roots of unity. So maybe there is a nicer proof in this special case?

More generally, what other necessary and/or sufficient conditions exist? Is there some reasonable number-theoretic or combinatorial characterization of such sets? What tools seem likely to shed some light on this question?

ADDED LATER: A couple of very interesting suggestions have been made in the comments so far, and I'm eager to see where they lead. However, I remain quite curious as to what can be said from a number-theoretic perspective. For example, if $n=p^r$ for some prime $p$, then the cyclotomic polynomial $\Phi_n(x)=\Phi_p(x^{r-1})$ has only nonnegative coefficients. So a sufficient condition that I did not mention above is that $S$ is the set of primitive $n$th roots of unity for some prime power $n$. I believe this is the only way to obtain such a polynomial that is a cyclotomic polynomial, but that doesn't imply that nothing else can be gained from a number-theoretic perspective on this question – however I myself lack the expertise necessary to make the most of such a perspective.

I should also mention that (ironically, given my desire for a number-theoretic perspective on this) the cyclotomic result actually follows from a more general, not number-theoretic result of

Evans, Ronald, and John Greene. "Polynomials with nonnegative coefficients whose zeros have modulus one." SIAM Journal on Mathematical Analysis 22, no. 4 (1991): 1173-1182. Author's link

a special case of which gives that for any proper divisor $d$ of $n$, $(x^n-1)/(x^d-1)$ has only nonnegative coefficients. So this generalizes the cyclotomic result, but not via number theory.

Source Link
Louis Deaett
  • 1.5k
  • 1
  • 13
  • 24
Loading