13
$\begingroup$

For given $n$, consider a polynomial $\sum_{k=0}^na_kz^k$ with all coefficients $a_k\in\{\pm1\}$. I am interested in the following:

How big can the modulus of a non-real root of such a polynomial be?

Wlog we can assume $a_n=1,a_{n-1}=-1$. Then a systematic search for small $n$, looking each time at the 10 or so extremal polynomials, exhibits a clear pattern for the highest coefficients: they come in groups of $3$ or $4$ consecutive +1's or -1's, starting with $z^n-z^{n-1}+++----+++---++++\cdots$. More precisely, the group sizes are displayed here (first line +1's, second line -1's)

1 3 3 4 3 3 3 4 3 3 3 4 3 3 4 4 3 3 4 4 3 3 4 4 3 3 4 . . .
 1 4 3 3 4 4 3 3 4 4 3 3 4 3 3 3 4 3 3 3 4 3 3 3 4 3 . . .

Note that there are never two adjacent groups of size 4 or three of size 3, so the pattern is rather regular, as may be expected.

As $n$ grows, the extremal root $z_0$ (and $\bar z_0$) of the extremal polynomials does not at all jump around, but converges quite rapidly towards $0.93757749648487973269811306454355 \pm 1.2634174429011374851417570421775\; i$, e.g. we have

$n=20\implies z_0\approx 0.937537 \pm 1.26337\;i$

$n=40\implies z_0\approx 0.9375774916 \pm 1.263417437\;i$

$n=60\implies z_0\approx 0.9375774964839 \pm 1.26341744290078\;i$.

$n=80\implies z_0\approx 0.93757749648487963 \pm 1.263417442901137422\;i$.

$n=100\implies z_0\approx 0.937577496484879732688 \pm 1.263417442901137485132\;i$.

The obvious questions:

  • Can the above 3-4-sequences be characterized? E.g. are they periodic? or self-similar?
  • What can be said about the limit value of $z_0$? Is there a (closed form or whatever) formula for $z_0$?

Although the problem is not directly related to Garsia numbers (see the article mentioned here), it naturally leads again to the question of limit points of zeros of such polynomials, given that $z_0$ visibly yields one of those:

  • Are there only countably many non-real limit points of zeros of $\pm1$-polynomials?
Improve this question
$\endgroup$
15
  • $\begingroup$ Most of the zeros of a $\pm 1$ polynomial will cluster around the unit circle, and get equidistributed in angle. So every point on the unit circle is a limit point of zeros. $\endgroup$
    – Lucia
    Commented Nov 9, 2014 at 19:29
  • $\begingroup$ For your last question, the $n^{th}$ roots of unity (other than $1$) are the zeroes of $\sum_{k=0}^{n-1}z^k = \frac{z^n - 1}{z-1}$. As $n$ varies, we get a countable dense subset of $S^1$ of such zeroes, so as Lucia said, every point of $S^1$ is a limit point of the zeroes; in particular, the set of non-real limit points is not countable. $\endgroup$
    – Michael Albanese
    Commented Nov 9, 2014 at 19:43
  • 1
    $\begingroup$ Just a comment: once you have a large root of a polynomial, you can multiply by $(1\pm z^n)$ to another polynomial of twice the length with the same root. $\endgroup$
    – Lev Borisov
    Commented Nov 9, 2014 at 20:26
  • 1
    $\begingroup$ For $\pm$-polynomials of degree n, the problem of the minimum modulus root $z_n$ is clearly equivalent, since we can consider reciprocal polynomials. However, the minimum modulus problem seems more suitable to pass to the limit, since limits of $\pm$-polynomials are $\pm$-series, with radius of convergence 1, thus including the (any) limit of $z_n$. So one may start from the minimum root problem for $\pm$-series. $\endgroup$
    – Pietro Majer
    Commented Nov 9, 2014 at 21:58
  • 2
    $\begingroup$ Of interest may be this article by John Baez, Dan Christensen, and Sam Derbyshire: math.ucr.edu/home/baez/roots/beauty.pdf $\endgroup$
    – Todd Trimble
    Commented Nov 10, 2014 at 1:04

1 Answer 1

Reset to default
11
$\begingroup$

A closely related problem was considered by Odlyzko and Poonen who looked at the class of polynomials with $0$ or $1$ coefficients. On page 330, they discuss the question of the smallest (in size) non-real root in this family (which is of course equivalent to the largest non-real root) and observe that numerically its size is about $0.734$. In Section 6 of their paper they discuss computations plus a simple Rouche's theorem argument which would enable one to compute this as accurately as desired. The same arguments should carry over to this situation. There doesn't seem to be any more natural description of the smallest size of non-real roots in the Odlyzko-Poonen paper.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you Lucia. I'll accept this answer, probably best possible one can do. I am just wondering: would you see any chance that there is a relationship with the cfrac $\frac1{1+\frac1{1+\frac1{3+\frac1{4+\frac1{3+\frac1{3+...}}}}}}$? Just by curiosity, I did a similar search for a $\pm1$-polynomial where the second largest pair of complex roots has maximal modulus. This turns out to be very irregular, starting with $+-+--+++++++--+---+---++++++--++---------$, and the maximal roots are $1.261231263 \pm0.4399400258\;i$ and $0.06954716993\pm 1.333986117\;i$ (asymptotically same modulus) $\endgroup$
    – Wolfgang
    Commented Nov 12, 2014 at 20:32
  • $\begingroup$ Interesting! I don't know what it means! You could also look at the Odlyzko-Poonen situation, and see if there is a pattern to the polynomials there that have largest non-real root. Maybe that problem will have a similar feature to what you're seeing here? $\endgroup$
    – Lucia
    Commented Nov 12, 2014 at 20:48
  • 1
    $\begingroup$ I have looked at the pattern in the Odlyzko-Poonen situation. The maximal root is $-.9299016\pm.9983452\; i $ (indeed $1/|z_0|\approx .73295778$) and the coefficients have a very similar snake pattern! With first line for 1's, 2nd line for 0's, we have group sizes $$\;\text{3 1 1 2 1 1 1 2 1 1 2 1 1 2 2 1 1} \\ \text{ 1 2 1 1 2 2 1 1 2 1 1 2 1 1 1 2}$$ $\endgroup$
    – Wolfgang
    Commented Nov 15, 2014 at 18:10
  • $\begingroup$ Very interesting! Clearly there's something to think through there. $\endgroup$
    – Lucia
    Commented Nov 15, 2014 at 19:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .