13

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?
Community
  • 1
Wolfgang
  • 13,193
  • 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. – Lucia Nov 09 '14 at 19:29
  • 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. – Michael Albanese Nov 09 '14 at 19:43
  • I can't help but observe the "snake" pattern of 3-s in your list. Does it hold in all of the examples? – Lev Borisov Nov 09 '14 at 20:10
  • 1
    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. – Lev Borisov Nov 09 '14 at 20:26
  • @Lucia: oh yes, of course. In fact I didn't think of the unit circle itself, but of anything off it! – Wolfgang Nov 09 '14 at 20:28
  • @LevBorisov good observation. So in fact the last question is rather moot. – Wolfgang Nov 09 '14 at 20:29
  • @LevBorisov In a sense there is only one example, e.g. for a given $n$ the 10 best polynomials only differ in the 4-5 last coefficients. Of course I wonder if the pattern in the second half of what I have displayed will carry on periodically like that or if it will switch back at some point to the "inverse" snake pattern as in the first half. $$ $$ I haven't tried yet what happens when starting with an arbitrary $\pm1$-polynomial, then multiplying with say z^10 and checking which choice of the 10 smaller coefficients makes the maximal complex root biggest. – Wolfgang Nov 09 '14 at 20:39
  • It is not surprising that the best polynomials differ just a bit at the end. If you change a few of the lower terms in a polynomial, then roots $\xi$ with $|\xi|$ noticeably larger than one will be only mildly affected. – Lev Borisov Nov 09 '14 at 21:06
  • 1
    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. – Pietro Majer Nov 09 '14 at 21:58
  • If the 3 and 4 are really (eventually) periodic, as it seems from your picture, the corresponding (up to subsequences) limit $\pm$-series are rational functions of the form $P(z)/(1-z^{28})$, where $P(z)$ is a $\pm$-polynomial of degree 27, with coefficient signs (++++---+++---+++----++++---), or some cyclic permutations of it. One may check if $1/z_0$ is a root of one of these P(z). – Pietro Majer Nov 09 '14 at 22:22
  • (however this would sound strange: it means that the max (min) modulus of non real roots for $,\pm$-polynomials of any degree is already reached at the degree 27) – Pietro Majer Nov 09 '14 at 22:37
  • 2
    Of interest may be this article by John Baez, Dan Christensen, and Sam Derbyshire: http://www.math.ucr.edu/home/baez/roots/beauty.pdf – Todd Trimble Nov 10 '14 at 01:04
  • It also contains the key-words Littlewood polynomials and Littlewood series. – Pietro Majer Nov 10 '14 at 07:52
  • @PietroMajer I have checked for 43343343 and some cyclic permutations, without success. After that I realized that $1/{z_\infty}$ (I prefer writing ${z_\infty}$ for the limit) cannot be a root, because then $z_\infty$ also would be a root of a (finite) $\pm1$-polynomial. Impossible, as $|z_0|$ grows with $n$. And sure anough, degree 27 would sound strange anyway. I rather tend to think the coefficients form a self-similar sequence. – Wolfgang Nov 10 '14 at 10:18
  • exact, if $|z_n|$ is strictly increasing that sequence can't be (eventually) periodic. – Pietro Majer Nov 10 '14 at 12:19

1 Answers1

11

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.

Lucia
  • 43,311
  • 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) – Wolfgang Nov 12 '14 at 20:32
  • 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? – Lucia Nov 12 '14 at 20:48
  • 1
    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}$$ – Wolfgang Nov 15 '14 at 18:10
  • Very interesting! Clearly there's something to think through there. – Lucia Nov 15 '14 at 19:18