4
$\begingroup$

As increasingly higher degree terms are added to a "random" polynomial, the roots of a polynomial can be proven to approach the unit circle. For example, see the MathOverflow question Why do roots of polynomials tend to have absolute value close to 1? by Andrej Bauer.

The roots are proven to approach the unit circle in some of the answers in that question, while still others help the intuition. The question here is if we can somehow quantitatively describe the speed at which (hopefully all of) the roots approach the unit circle. I'm hoping that this has already been studied, and that someone can provide a reference.

For example, we can assume that $n$ is the degree of the polynomial. I assume that this question will be hard to answer, so any reasonable definition of the coefficients is ok. To this end, I hope that the coefficients will be taken from some random distribution that isn't too specific. However, the main usage is in finding roots that approach the unit circle as fast as possible, so any distribution that accomplishes this should be ok. For example, they could be either real or complex, and taken from some appropriate distribution.

I have a real world application in mind, so that is the reason that I need something more quantitative, rather than just saying that the roots approach a circle. Again, sorry for the lack of details, I'm just hoping that this will give more wiggle room to find a study of the problem!

Just in case someone wants more details, here's the ideal situation…. We have nonnegative integer coefficients less then or equal to $m$, iid. We're trying to find $O(f(m,n))$, where all roots $r$ (of at least one carefully selected polynomial) are guaranteed $\lvert r\rvert < f(m,n)$. Again ideally, we really only need one well chosen polynomial to have roots close to the unit circle.

Improve this question
$\endgroup$
4
  • $\begingroup$ If you want a guarantee then the rate of approach to the unit circle is moot, because there are always going to be polynomials (e.g. $x^n+mx^{n-1}$) with roots that are far from the circle. It's more accurate to say that 'with probability approaching 1 over the space, the roots approach the unit circle' but that doesn't give explicit guaranteed bounds. $\endgroup$
    – Steven Stadnicki
    Nov 20, 2021 at 1:33
  • $\begingroup$ @StevenStadnicki: My mistake... The crux of the matter really is that only one polynomial with roots close to the unit circle is required. But, yes, I am hoping for a guarantee that we can find a polynomial arbitrarily close if we use enough roots. $\endgroup$
    – Likes Algorithms
    Nov 20, 2021 at 3:12
  • $\begingroup$ So to make sure I understand: you don't need a randomness result at all, just that you want a polynomial of degree $n$ with coefficients positive, integral and bounded and all roots close to the unit circle? What about $x^n+1$? $\endgroup$
    – Steven Stadnicki
    Nov 20, 2021 at 16:21
  • $\begingroup$ @StevenStadnicki: That's a good thought, but I can't use $n$th roots of unity for the algorithm. The roots have to be something other than the exact roots of unity. Sorry I didn't mention that. I'm taking very large powers of the roots, so I'm trying to ensure that the roots' absolute values stay very small. My latest idea was to take math software and sum over all possible polynomials with coefficients in some range, and also sum over all roots. If we take the logs of the absolute values, they seem to decrease almost steadily. Proving this would definitely be enough. $\endgroup$
    – Likes Algorithms
    Nov 20, 2021 at 17:50

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.